這節中你會學到集束搜索（beam search）算法，上節中我們講了對於機器翻譯來說，給定輸入，比如法語句子，你不會想要輸出一個隨機的英語翻譯結果，你想要一個最好的，最可能的英語翻譯結果。
對於語音識別也一樣，給定一個輸入的語音片段，你不會想要一個隨機的文本翻譯結果，你想要最好的，最接近原意的翻譯結果，集束搜索就是解決這個最常用的算法。這節，你會明白怎麼把集束搜索算法應用到你自己的工作中，就用我們的法語句子的例子來試一下集束搜索吧。
“Jane visite l'Afrique en Septembre.”（法語句子），我們希望翻譯成英語，"Jane is visiting Africa in September".（英語句子），集束搜索算法首先做的就是挑選要輸出的英語翻譯中的第一個單詞。
這裡我列出了10,000個詞的詞彙表（下圖編號1所示），為了簡化問題，我們忽略大小寫，所有的單詞都以小寫列出來。在集束搜索的第一步中我用這個網絡部分，綠色是編碼部分（下圖編號2所示），紫色是解碼部分（下圖編號3所示），來評估第一個單詞的概率值，給定輸入序列x，即法語作為輸入，第一個輸出y的概率值是多少。
貪婪算法只會挑出最可能的那一個單詞，然後繼續。而集束搜索則會考慮多個選擇，集束搜索算法會有一個參數B，叫做集束寬（beam width）。
在這個例子中我把這個集束寬設成3，這樣就意味著集束搜索不會只考慮一個可能結果，而是一次會考慮3個，比如對第一個單詞有不同選擇的可能性，最後找到in、jane、september，是英語輸出的第一個單詞的最可能的三個選項，然後集束搜索算法會把結果存到計算機內存裡以便後面嘗試用這三個詞。如果集束寬設的不一樣，如果集束寬這個參數是10的話，那麼我們跟蹤的不僅僅3個，而是10個第一個單詞的最可能的選擇。
所以要明白，為了執行集束搜索的第一步，你需要輸入法語句子到編碼網絡，然後會解碼這個網絡，這個softmax層（上圖編號3所示）會輸出10,000個概率值，得到這10,000個輸出的概率值，取前三個存起來。
讓我們看看集束搜索算法的第二步，已經選出了in、jane、september作為第一個單詞三個最可能的選擇，集束算法接下來會針對每個第一個單詞考慮第二個單詞是什麼，單詞in後面的第二個單詞可能是a或者是aaron，我就是從詞彙表裡把這些詞列了出來，或者是列表裡某個位置，september，可能是列表裡的 visit，一直到字母z，最後一個單詞是zulu（下圖編號1所示）。
為了評估第二個詞的概率值，我們用這個神經網絡的部分，綠色是編碼部分（上圖編號2所示），而對於解碼部分，當決定單詞in後面是什麼，別忘了解碼器的第一個輸出y^(<1>)，我把y^(<1>)設為單詞in（上圖編號3所示），然後把它喂回來，這裡就是單詞in（上圖編號4所示），因為它的目的是努力找出第一個單詞是in的情況下，第二個單詞是什麼。
這個輸出就是y^(<2>)（上圖編號5所示），有了這個連接（上圖編號6所示），就是這裡的第一個單詞in（上圖編號4所示）作為輸入，這樣這個網絡就可以用來評估第二個單詞的概率了，在給定法語句子和翻譯結果的第一個單詞in的情況下。
注意，在第二步裡我們更關心的是要找到最可能的第一個和第二個單詞對，所以不僅僅是第二個單詞有最大的概率，而是第一個、第二個單詞對有最大的概率（上圖編號7所示）。
按照條件概率的準則，這個可以表示成第一個單詞的概率（上圖編號8所示）乘以第二個單詞的概率（上圖編號9所示），這個可以從這個網絡部分裡得到（上圖編號10所示），對於已經選擇的in、jane、september這三個單詞，你可以先保存這個概率值（上圖編號8所示），然後再乘以第二個概率值（上圖編號9所示）就得到了第一個和第二個單詞對的概率（上圖編號7所示）。
現在你已經知道在第一個單詞是in的情況下如何評估第二個單詞的概率，現在第一個單詞是jane，道理一樣，句子可能是"jane a"、"jane aaron"，等等到"jane is"、"jane visits"等等（上圖編號1所示）。你會用這個新的網絡部分（上圖編號2所示），我在這裡畫一條線，代表從y^(<1>)，即jane，y^(<1>)連接jane（上圖編號3所示），那麼這個網絡部分就可以告訴你給定輸入x和第一個詞是jane下，第二個單詞的概率了（上圖編號4所示），和上面一樣，你可以乘以P(y^(<1>) |x)得到P(y^(<1>),y^(<2>) |x)。
針對第二個單詞所有10,000個不同的選擇，最後對於單詞september也一樣，從單詞a到單詞zulu，用這個網絡部分，我把它畫在這裡。來看看如果第一個單詞是september，第二個單詞最可能是什麼。
所以對於集束搜索的第二步，由於我們一直用的集束寬為3，並且詞彙表裡有10,000個單詞，那麼最終我們會有3乘以10,000也就是30,000個可能的結果，因為這裡（上圖編號1所示）是10,000，這裡（上圖編號2所示）是10,000，這裡（上圖編號3所示）是10,000，就是集束寬乘以詞彙表大小，你要做的就是評估這30,000個選擇。
按照第一個詞和第二個詞的概率，然後選出前三個，這樣又減少了這30,000個可能性，又變成了3個，減少到集束寬的大小。假如這30,000個選擇裡最可能的是“in September”（上圖編號4所示）和“jane is”（上圖編號5所示），以及“jane visits”（上圖編號6所示），畫的有點亂，但這就是這30,000個選擇裡最可能的三個結果，集束搜索算法會保存這些結果，然後用於下一次集束搜索。
注意一件事情，如果集束搜索找到了第一個和第二個單詞對最可能的三個選擇是“in September”或者“jane is”或者“jane visits”，這就意味著我們去掉了september作為英語翻譯結果的第一個單詞的選擇，所以我們的第一個單詞現在減少到了兩個可能結果，但是我們的集束寬是3，所以還是有y^(<1>)，y^(<2>)對的三個選擇。
在我們進入集束搜索的第三步之前，我還想提醒一下因為我們的集束寬等於3，每一步我們都複製3個，同樣的這種網絡來評估部分句子和最後的結果，由於集束寬等於3，我們有三個網絡副本（上圖編號7所示），每個網絡的第一個單詞不同，而這三個網絡可以高效地評估第二個單詞所有的30,000個選擇。所以不需要初始化30,000個網絡副本，只需要使用3個網絡的副本就可以快速的評估softmax的輸出，即y^(<2>)的10,000個結果。
讓我們快速解釋一下集束搜索的下一步，前面說過前兩個單詞最可能的選擇是“in September”和“jane is”以及“jane visits”，對於每一對單詞我們應該保存起來，給定輸入x，即法語句子作為x的情況下，y^(<1>)和y^(<2>)的概率值和前面一樣，現在我們考慮第三個單詞是什麼，可以是“in September a”，可以是“in September aaron”，一直到“in September zulu”。
為了評估第三個單詞可能的選擇，我們用這個網絡部分，第一單詞是in（上圖編號1所示），第二個單詞是september（上圖編號2所示），所以這個網絡部分可以用來評估第三個單詞的概率，在給定輸入的法語句子x和給定的英語輸出的前兩個單詞“in September”情況下（上圖編號3所示）。對於第二個片段來說也一樣，就像這樣一樣（上圖編號4所示），對於“jane visits”也一樣，然後集束搜索還是會挑選出針對前三個詞的三個最可能的選擇，可能是“in september jane”（上圖編號5所示），“Jane is visiting”也很有可能（上圖編號6所示），也很可能是“Jane visits Africa”（上圖編號7所示）。
然後繼續，接著進行集束搜索的第四步，再加一個單詞繼續，最終這個過程的輸出一次增加一個單詞，集束搜索最終會找到“Jane visits africa in september”這個句子，終止在句尾符號（上圖編號8所示），用這種符號的系統非常常見，它們會發現這是最有可能輸出的一個英語句子。
你已經瞭解集束搜索是如何工作的了，事實上還有一些額外的提示和技巧的改進能夠使集束算法更高效，我們在下個筆記中一探究竟。
閱讀更多 極客Array 的文章
