NLP語言模型，機器翻譯任務中的貪心搜索 Greedy search 和集束搜索 Beam search（學習心得）
Picking the most likely sentence
可以把機器翻譯，想像成建立一個條件語言模型 a conditional language model
語言模型，可以用來估計一個語句的概率
也可以根據第一個輸入，來產生後續的輸出
機器翻譯模型，有兩個網絡，分別是編碼網絡和解碼網絡，對應上面的綠色和紫色
可以發現，後面的解碼網絡，和語言模型非常類似
所以這兩個模型的區別在於，語言模型是從零向量 vector of zeros 開始
而機器翻譯模型是輸入的句子編碼
所以機器翻譯模型又被叫做：條件語言模型 conditional language model
輸出 the probability of the output English translation（前提條件：conditions on some input French sentence）
之前的語言模型：輸出 the probability of any sentence
我們得到的其實是一個概率分佈，然後模型會有對應於這個概率分佈的輸出
但是問題在於：
雖然最大概率的輸出是最優的翻譯，但是不能保證每次都採用到最大的概率
我們希望得到的，不是隨機採用，而是使得條件概率最大化的那個句子
所以針對機器翻譯，要設計一個算法，來找出最合適的 y 值，使得條件概率最大化
解決這一問題最常用的是：集束搜索 Beam Search
那為什麼不用貪心搜索 Greedy Search 呢？
貪心搜索：
- 生成第一個詞的分佈
- 選擇可能性最高的詞（條件概率下），輸入機器翻譯模型
- 然後同樣選擇第二個詞，第三個詞，直到最後
但是我們真正想要的，是一次性選出整個單詞序列 pick the entire sequence of words（最高可能性）
可以想像的是，有的時候雖然每個詞是最高可能性的，但是組成的句子未必讓人滿意，因為沒有一個好的全局觀
所以我們要最大化的是 整體概率 joint probability
比如上面的結果中，第一句我們更喜歡，因為簡潔明了
第二句雖然正確，但是有點啰嗦
由於 going 跟在 is 後面的概率會更高，所以單詞最優會出現第二句的結果
這就是單詞最優和整句最優的區別
由於句子的組合是非常多的，比如 10000 個詞的詞典，構成一個 10 個字的句子，那粗略算來就是 10000^10 這麼多的可能性，所以我們沒辦法直接做全局最優的搜索
需要用一個 近似搜索算法 approximate search algorithm
這個算法會嘗試選到一個概率最大的句子（雖然不能保證找到的 y 一定使得概率最大化，但常常足夠用了）
Beam search
-
嘗試選擇第一個要輸出的詞 try to pick the first words ，比如 10000 詞的詞表（這裡忽略了大小寫）
-
使用編碼和解碼網絡，輸入句子後，衡量第一個詞的概率（softmax 層輸出 10000 個詞對應的概率）
-
這裡多了一個參數 B，假設定為 3（beam width），即一次考慮 3 個概率最高的詞，暫存結果
-
針對 3 個詞，分別考慮第二個單詞（3 次，每次生成 10000 個詞的概率）
-
這裡的 3 個詞，都是在 y_hat<1> 的地方轉為下一個序列的輸入，計算得到 y_hat<2>
-
這裡我們得到的條件概率結果的前提條件是：輸入的法語句子 + 第一個詞
-
然後，我們要計算 「第一個詞 + 第二個詞」 的條件概率，前提條件是：輸入的法語句子
-
根據條件概率公式，可以拆解為兩個概率的乘積
-
其中前面一項，已經在第一個詞的計算中，對應保留了 3 個詞的概率
-
第二項，是在第二個詞的計算中得到
-
所以第二個詞計算完畢後，我們得到了 3✖️ 10000 = 30000 種可能性，在其中選出 3 中概率最高的，存儲最為下一個詞的輸入
值得注意的是，如果第二個詞計算的時候發現，第一個詞的 3 個候選中，有 1 個沒有排進前 3，那相當於這個候選就被淘汰了
然後我們每次，要根據前面的詞，做 30000 次的 概率評估，選擇前 3
相當於我們每一步，都複製了 3 個完全一樣的網絡副本
然後到了集束搜索的下一步，繼續下一個詞，直到最後一個詞（結尾標記）
如果我們設定 B=1，那就是貪心搜索算法了
