如何使用貪婪搜索和束搜索解碼演算法進行自然語言處理

本文介紹了貪婪搜索解碼演算法和束搜索解碼演算法的定義及其Python實現。

自然語言處理任務如圖像描述生成和機器翻譯，涉及生成一系列的單詞。通常，針對這些問題開發的模型的工作方式是生成在輸出辭彙表上的概率分布，並通過解碼演算法對概率分布進行採樣以生成可能性最大的單詞序列。在本教程中，你將學習可用於文本生成問題的貪婪搜索和束搜索解碼演算法。

完成本教程，你將了解：

• 文本生成問題中的解碼問題；

• 貪婪搜索解碼演算法及其在Python中的實現；

• 束搜索解碼演算法及其在Python中的實現。

文本生成解碼器

在自然語言處理任務中，如圖像描述生成、文本摘要和機器翻譯等，需要預測的是一連串的單詞。通常，針對此類問題開發的模型會輸出每個單詞在對應的輸出序列辭彙表上的概率分布，然後解碼器將其轉化為最終的單詞序列。

當你使用循環神經網路解決以文本作為輸出的NLP任務時，你很可能會遇到這種情況。神經網路模型的最後一層對輸出辭彙表中的每個單詞都有對應的一個神經元，同時softmax激活函數被用來輸出辭彙表中每個單詞成為序列中下一個單詞的可能性。

解碼最有可能的輸出序列包括根據它們的可能性搜索所有可能的輸出序列。辭彙表中通常含有成千上萬個單詞，甚至上百萬個單詞。因此，搜索問題根據輸出序列的長度呈指數級變化，並且很難做到完全搜索（NP-complete）。

實際上，對於給定的預測，可以用啟發式搜索方法返回一或多個逼近或「足夠好」的解碼輸出序列。由於搜索圖的範圍是根據源語句長度呈指數級的，所以我們必須使用近似來有效地找到解決方案。

候選單詞序列的分數是根據它們的可能性評定的。通常，使用貪婪搜索或束搜索定位文本的候選序列。本文將研究這兩種解碼演算法。

每個單獨的預測都有一個關聯的分數（或概率），我們對最大分數（或最大概率）的輸出序列感興趣。一種流行的近似方法是使用貪婪預測，即在每個階段採用得分最高的項。雖然這種方法通常是有效的，但顯然不是最佳的。實際上，用束搜索作為近似搜索通常比用貪婪搜索要好得多。

貪婪搜索解碼器

一個簡單的近似方法是使用貪婪搜索，即在輸出序列的每一步中選擇最有可能的單詞。該方法的優點是非常快，但最終輸出序列的質量可能遠非最佳。

我們可以用Python中的一個小例子來展示貪婪搜索的解碼方式。我們從一個包含10個單詞的序列的預測問題開始。每個單詞的預測是其在五個單片語成的辭彙表上的概率分布。

我們假定單詞是整數編碼的，這樣，列索引就可以用來查找辭彙表中的相關單詞。因此，解碼任務就變成從概率分布中選擇整數序列的任務。argmax() 數學函數可用於選擇具有最大值的數組的索引。我們可以用該函數選擇在序列每個步驟中最有可能的單詞索引。這個函數是直接在numpy中提供的。

下面的 greedy_decoder() 函數用argmax函數實現了這個解碼思路。

下面展示了貪婪解碼器的完整示例。

運行這個示例會輸出一系列整數，然後這些整數可以映射回辭彙表中的單詞。

[4, 0, 4, 0, 4, 0, 4, 0, 4, 0]

束搜索解碼器

另一種流行的啟發式演算法是在貪婪搜索的基礎擴展而來的束搜索，它返回的是可能性最大的輸出序列列表。相對於在構建序列時就貪婪地選擇最有可能的下一步，束搜索選擇擴展所有可能的下一步，並保持k是最有可能的，k是用戶指定的參數，它通過一系列概率控制束或並行搜索的數量。

本地束搜索演算法跟蹤k個狀態，而不僅僅只跟蹤一個。它從k個隨機生成的狀態開始，在每一步中都生成所有k個狀態的所有後繼者。如果這其中的任何一個後繼者是目標，那麼演算法就會停止。否則，它將從完整列表中選擇k個最佳後繼者並不斷重複。

我們不需要從隨機狀態開始；相反 ，我們以k個最可能的單詞開始，作為序列的第一步。對於貪婪搜索，常見的束寬度值為1，對於機器翻譯中常見的基準問題，它的值為5或10。由於多個候選序列增加了更好地匹配目標序列的可能性，所以較大的束寬度會使模型性能提高。性能的提高會導致解碼速度降低。

在NMT中，新的句子通過一個簡單的束搜索解碼器被翻譯，該解碼器可以找到一個近似最大化已訓練NMT模型的條件概率的譯文。束搜索從左到右逐詞完成翻譯，同時在每一步中都保持固定數目（束）的活躍候選者。增大束尺寸可以提高翻譯性能，但代價是解碼器的速度顯著降低。

搜索過程可以通過達到最大長度、到達序列結束標記或到達閾值可能性來分別停止每個候選項。

讓我們用一個例子來具體說明這個問題。

我們可以定義一個函數來執行給定序列概率和束寬度參數k的束搜索。在每一步中，每個候選序列都被擴展為所有可能的後續步驟。每個候選步驟的分數通過概率相乘得到。選擇具有最大概率的k個序列，並刪去其他候選項。然後重複該過程直到序列結束。

概率是很小的數，而把小的數相乘就會得到更小的數。為了避免浮點數的下溢，可將概率的自然對數相乘，這樣使得到的數字更大、更易於管理。此外，通過最小化分數來進行搜索也是很常見的，因此，可以將概率的負對數相乘。這個最後的調整使我們能夠按照分數對所有候選序列進行升序排序，並選擇前k個序列作為可能性最大的候選序列。

下面的 beam_search_decoder() 函數實現了束搜索解碼器。

我們可以將它與上一節的樣本數據結合在一起，這次返回的是3個可能性最大的序列。

運行該示例將輸出整數序列及其對數似然函數值。

試用不同的k值。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！