上個筆記中, 你已經學到了基本的束搜索算法(the basic beam search algorithm)，這個筆記裡,我們會學到一些技巧, 能夠使算法運行的更好。
長度歸一化（Length normalization）就是對束搜索算法稍作調整的一種方式，幫助你得到更好的結果，下面介紹一下它。
前面講到束搜索就是最大化這個概率，這個乘積就是P(y^(<1>)…y^(
這些符號看起來可能比實際上嚇人，但這就是我們之前見到的乘積概率（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上加上指數a，a可以等於0.7。如果a等於1，就相當於完全用長度來歸一化，如果a等於0，T_y的0次冪就是1，就相當於完全沒有歸一化，這就是在完全歸一化和沒有歸一化之間。a就是算法另一個超參數（hyper parameter），需要調整大小來得到最好的結果。不得不承認，這樣用a實際上是試探性的，它並沒有理論驗證。但是大家都發現效果很好，大家都發現實踐中效果不錯，所以很多人都會這麼做。你可以嘗試不同的a值，看看哪一個能夠得到最好的結果。
總結一下如何運行束搜索算法。當你運行束搜索時，你會看到很多長度等於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）的問題。事實上在束搜索上做誤差分析是我發現的最有用的工具之一。
有時你想知道是否應該增大束寬，我的束寬是否足夠好，你可以計算一些簡單的東西來指導你需要做什麼，來改進你的搜索算法。我們在下個筆記裡進一步討論。
閱讀更多 極客Array 的文章
