集束搜索 (Beam Search)

這節視頻中你會學到集束搜索（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所示），用這種符號的系統非常常見，它們會發現這是最有可能輸出的一個英語句子。在本周的練習中，你會看到更多的執行細節，同時，你會運用到這個集束算法，在集束寬為3時，集束搜索一次只考慮3個可能結果。注意如果集束寬等于1，只考慮1種可能結果，這實際上就變成了貪婪搜索算法，上個視頻里我們已經討論過了。但是如果同時考慮多個，可能的結果比如3個，10個或者其他的個數，集束搜索通常會找到比貪婪搜索更好的輸出結果。

你已經了解集束搜索是如何工作的了，事實上還有一些額外的提示和技巧的改進能夠使集束算法更高效，我們在下個視頻中一探究竟。

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的3.3 集束搜索-深度学习第五课《序列模型》-Stanford吴恩达教授的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。