改進集束搜索 (Refinements to Beam Search)

上個視頻中, 你已經學到了基本的束搜索算法(the basic beam search algorithm)，這個視頻里,我們會學到一些技巧, 能夠使算法運行的更好。長度歸一化（Length normalization）就是對束搜索算法稍作調整的一種方式，幫助你得到更好的結果，下面介紹一下它。

前面講到束搜索就是最大化這個概率，這個乘積就是 $P(y^{<1>}?y^{<T_y>}|X)$ ，可以表示成: $P(y^{<1>}|X)P(y^{<2>}|X,y^{<1>})P(y^{<3>}|X,y^{<1>},y^{<2>})?P(y^{<T_y>}|X,y^{<1>},y^{<2>}?y^{<T_y?1>})$
這些符號看起來可能比實際上嚇人，但這就是我們之前見到的乘積概率（the product probabilities）。如果計算這些，其實這些概率值都是小于1的，通常遠小于1。很多小于1的數乘起來，會得到很小很小的數字，會造成數值下溢（numerical underflow）。數值下溢就是數值太小了，導致電腦的浮點表示不能精確地儲存，因此在實踐中,我們不會最大化這個乘積，而是取 $log$ 值。如果在這加上一個 $log$ ，最大化這個 $log$ 求和的概率值，在選擇最可能的句子 $y$ 時，你會得到同樣的結果。所以通過取 $log$ ，我們會得到一個數值上更穩定的算法，不容易出現四舍五入的誤差，數值的舍入誤差（rounding errors）或者說數值下溢（numerical underflow）。因為 $log$ 函數它是嚴格單調遞增的函數，最大化 $P(y)$ ，因為對數函數，這就是 $log$ 函數，是嚴格單調遞增的函數，所以最大化 $logP(y|x)$ 和最大化 $P(y|X)$ 結果一樣。如果一個 $y$ 值能夠使前者最大，就肯定能使后者也取最大。所以實際工作中，我們總是記錄概率的對數和（the sum of logs of the probabilities），而不是概率的乘積（the production of probabilities）。

對于目標函數（this objective function），還可以做一些改變，可以使得機器翻譯表現的更好。如果參照原來的目標函數（this original objective），如果有一個很長的句子，那么這個句子的概率會很低，因為乘了很多項小于1的數字來估計句子的概率。所以如果乘起來很多小于1的數字，那么就會得到一個更小的概率值，所以這個目標函數有一個缺點，它可能不自然地傾向于簡短的翻譯結果，它更偏向短的輸出，因為短句子的概率是由更少數量的小于1的數字乘積得到的，所以這個乘積不會那么小。順便說一下，這里也有同樣的問題，概率的 $log$ 值通常小于等于1，實際上在 $log$ 的這個范圍內，所以加起來的項越多，得到的結果越負，所以對這個算法另一個改變也可以使它表現的更好，也就是我們不再最大化這個目標函數了，我們可以把它歸一化，通過除以翻譯結果的單詞數量（normalize this by the number of words in your translation）。這樣就是取每個單詞的概率對數值的平均了，這樣很明顯地減少了對輸出長的結果的懲罰（this significantly reduces the penalty for outputting longer translations.）。

在實踐中，有個探索性的方法，相比于直接除 $T_y$ ，也就是輸出句子的單詞總數，我們有時會用一個更柔和的方法（a softer approach），在 $T_y$ 上加上指數 $\alpha$ ， $\alpha$ 可以等于0.7。如果 $\alpha$ 等于1，就相當于完全用長度來歸一化，如果 $\alpha$ 等于0， $T_y$ 的0次冪就是1，就相當于完全沒有歸一化，這就是在完全歸一化和沒有歸一化之間。 $\alpha$ 就是算法另一個超參數（hyper parameter），需要調整大小來得到最好的結果。不得不承認，這樣用 $\alpha$ 實際上是試探性的，它并沒有理論驗證。但是大家都發現效果很好，大家都發現實踐中效果不錯，所以很多人都會這么做。你可以嘗試不同的 $\alpha$ 值，看看哪一個能夠得到最好的結果。

總結一下如何運行束搜索算法。當你運行束搜索時，你會看到很多長度等于1的句子，很多長度等于2的句子，很多長度等于3的句子，等等?？赡苓\行束搜索30步，考慮輸出的句子可能達到，比如長度30。因為束寬為3，你會記錄所有這些可能的句子長度，長度為1、2、 3、 4 等等一直到30的三個最可能的選擇。然后針對這些所有的可能的輸出句子，用這個式子（上圖編號1所示）給它們打分，取概率最大的幾個句子，然后對這些束搜索得到的句子，計算這個目標函數。最后從經過評估的這些句子中，挑選出在歸一化的 $log$ 概率目標函數上得分最高的一個（you pick the one that achieves the highest value on this normalized log probability objective.），有時這個也叫作歸一化的對數似然目標函數（a normalized log likelihood objective）。這就是最終輸出的翻譯結果，這就是如何實現束搜索。這周的練習中你會自己實現這個算法。

最后還有一些實現的細節，如何選擇束寬B。B越大，你考慮的選擇越多，你找到的句子可能越好，但是B越大，你的算法的計算代價越大，因為你要把很多的可能選擇保存起來。最后我們總結一下關于如何選擇束寬B的一些想法。接下來是針對或大或小的B各自的優缺點。如果束寬很大，你會考慮很多的可能，你會得到一個更好的結果，因為你要考慮很多的選擇，但是算法會運行的慢一些，內存占用也會增大，計算起來會慢一點。而如果你用小的束寬，結果會沒那么好，因為你在算法運行中，保存的選擇更少，但是你的算法運行的更快，內存占用也小。在前面視頻里，我們例子中用了束寬為3，所以會保存3個可能選擇，在實踐中這個值有點偏小。在產品中，經常可以看到把束寬設到10，我認為束寬為100對于產品系統來說有點大了，這也取決于不同應用。但是對科研而言，人們想壓榨出全部性能，這樣有個最好的結果用來發論文，也經常看到大家用束寬為1000或者3000，這也是取決于特定的應用和特定的領域。在你實現你的應用時，嘗試不同的束寬的值，當B很大的時候，性能提高會越來越少。對于很多應用來說，從束寬1，也就是貪心算法，到束寬為3、到10，你會看到一個很大的改善。但是當束寬從1000增加到3000時，效果就沒那么明顯了。對于之前上過計算機科學課程的同學來說，如果你熟悉計算機科學里的搜索算法（computer science search algorithms）, 比如廣度優先搜索（BFS, Breadth First Search algorithms），或者深度優先搜索（DFS, Depth First Search），你可以這樣想束搜索，不像其他你在計算機科學算法課程中學到的算法一樣。如果你沒聽說過這些算法也不要緊，但是如果你聽說過廣度優先搜索和深度優先搜索，不同于這些算法，這些都是精確的搜索算法（exact search algorithms），束搜索運行的更快，但是不能保證一定能找到argmax的準確的最大值。如果你沒聽說過廣度優先搜索和深度優先搜索，也不用擔心，這些對于我們的目標也不重要，如果你聽說過，這就是束搜索和其他算法的關系。

好，這就是束搜索。這個算法廣泛應用在多產品系統或者許多商業系統上，在深度學習系列課程中的第三門課中，我們討論了很多關于誤差分析（error analysis）的問題。事實上在束搜索上做誤差分析是我發現的最有用的工具之一。有時你想知道是否應該增大束寬，我的束寬是否足夠好，你可以計算一些簡單的東西來指導你需要做什么，來改進你的搜索算法。我們在下個視頻里進一步討論。

總結

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

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