如何實現自然語言處理的波束搜索解碼器 · Machine Learning Mastery 博客文章翻譯

# 如何實現自然語言處理的波束搜索解碼器 > 原文： [https://machinelearningmastery.com/beam-search-decoder-natural-language-processing/](https://machinelearningmastery.com/beam-search-decoder-natural-language-processing/) 自然語言處理任務，例如字幕生成和機器翻譯，涉及生成單詞序列。針對這些問題開發的模型通常通過在輸出詞的詞匯表中生成概率分布來操作，并且由解碼算法來對概率分布進行采樣以生成最可能的詞序列。在本教程中，您將發現可用于文本生成問題的貪婪搜索和波束搜索解碼算法。完成本教程后，您將了解： * 解碼文本生成問題的問題。 * 貪婪的搜索解碼器算法以及如何在 Python 中實現它。 * 光束搜索解碼器算法以及如何在 Python 中實現它。讓我們開始吧。 ![How to Implement Beam Search Decoder for Natural Language Processing](img/1420681abf00887764bb6e8e4d7b981b.jpg) 如何為自然語言處理實現波束搜索解碼器照片由[參見 1，Do1，Teach1](https://www.flickr.com/photos/mpaulmd/14695285810/) ，保留一些權利。 ## 用于文本生成的解碼器在自然語言處理任務（例如字幕生成，文本摘要和機器翻譯）中，所需的預測是一系列單詞。為這些類型的問題開發的模型通常在輸出序列中的每個單詞的詞匯表中的每個單詞上輸出概率分布。然后將其留給解碼器處理以將概率轉換為最終的單詞序列。在自然語言處理任務中使用循環神經網絡時，您可能會遇到這種情況，其中文本生成為輸出。神經網絡模型中的最后一層具有輸出詞匯表中每個單詞的一個神經元，并且 softmax 激活函數用于輸出詞匯表中的每個單詞作為序列中的下一個單詞的可能性。解碼最可能的輸出序列涉及基于其可能性搜索所有可能的輸出序列。詞匯量的大小通常是數十或數十萬個單詞，甚至數百萬個單詞。因此，搜索問題在輸出序列的長度上是指數級的，并且難以完全搜索（NP-complete）。在實踐中，啟發式搜索方法用于為給定預測返回一個或多個近似或“足夠好”的解碼輸出序列。 > 由于搜索圖的大小在源句長度中是指數的，我們必須使用近似來有效地找到解。 - 第 272 頁，[自然語言處理與機器翻譯手冊](http://amzn.to/2xQzTnt)，2011。候選詞的序列根據其可能性進行評分。通常使用貪婪搜索或波束搜索來定位候選文本序列。我們將在這篇文章中介紹這兩種解碼算法。 > 每個單獨的預測都有一個相關的分數（或概率），我們感興趣的是具有最大分數（或最大概率）的輸出序列[...]一種流行的近似技術是使用貪婪預測，在每個階段獲得最高得分項目。雖然這種方法通常很有效，但它顯然不是最佳的。實際上，使用光束搜索作為近似搜索通常比貪婪方法好得多。 - 第 227 頁，[自然語言處理中的神經網絡方法](http://amzn.to/2fC1sH1)，2017。 ## 貪婪的搜索解碼器一個簡單的近似是使用貪婪搜索，在輸出序列的每一步選擇最可能的單詞。這種方法的好處是速度非常快，但最終輸出序列的質量可能遠非最佳。我們可以用 Python 中的一個小設計示例來演示解碼的貪婪搜索方法。我們可以從涉及 10 個單詞序列的預測問題開始。每個單詞被預測為 5 個單詞的詞匯表上的概率分布。 ```py # define a sequence of 10 words over a vocab of 5 words data = [[0.1, 0.2, 0.3, 0.4, 0.5], [0.5, 0.4, 0.3, 0.2, 0.1], [0.1, 0.2, 0.3, 0.4, 0.5], [0.5, 0.4, 0.3, 0.2, 0.1], [0.1, 0.2, 0.3, 0.4, 0.5], [0.5, 0.4, 0.3, 0.2, 0.1], [0.1, 0.2, 0.3, 0.4, 0.5], [0.5, 0.4, 0.3, 0.2, 0.1], [0.1, 0.2, 0.3, 0.4, 0.5], [0.5, 0.4, 0.3, 0.2, 0.1]] data = array(data) ``` 我們假設單詞已經整數編碼，這樣列索引可用于查找詞匯表中的相關單詞。因此，解碼任務成為從概率分布中選擇整數序列的任務。 [argmax（）](https://en.wikipedia.org/wiki/Arg_max)數學函數可用于選擇具有最大值的數組的索引。我們可以使用此函數來選擇序列中每個步驟最有可能的單詞索引。該功能直接在 [numpy](https://docs.scipy.org/doc/numpy-1.9.3/reference/generated/numpy.argmax.html) 中提供。下面的 _greedy_decoder（）_ 函數使用 argmax 函數實現此解碼器策略。 ```py # greedy decoder def greedy_decoder(data): # index for largest probability each row return [argmax(s) for s in data] ``` 綜上所述，下面列出了演示貪婪解碼器的完整示例。 ```py from numpy import array from numpy import argmax # greedy decoder def greedy_decoder(data): # index for largest probability each row return [argmax(s) for s in data] # define a sequence of 10 words over a vocab of 5 words data = [[0.1, 0.2, 0.3, 0.4, 0.5], [0.5, 0.4, 0.3, 0.2, 0.1], [0.1, 0.2, 0.3, 0.4, 0.5], [0.5, 0.4, 0.3, 0.2, 0.1], [0.1, 0.2, 0.3, 0.4, 0.5], [0.5, 0.4, 0.3, 0.2, 0.1], [0.1, 0.2, 0.3, 0.4, 0.5], [0.5, 0.4, 0.3, 0.2, 0.1], [0.1, 0.2, 0.3, 0.4, 0.5], [0.5, 0.4, 0.3, 0.2, 0.1]] data = array(data) # decode sequence result = greedy_decoder(data) print(result) ``` 運行該示例會輸出一個整數序列，然后可以將這些整數映射回詞匯表中的單詞。 ```py [4, 0, 4, 0, 4, 0, 4, 0, 4, 0] ``` ## 光束搜索解碼器另一種流行的啟發式算法是波束搜索，它擴展了貪婪搜索并返回最可能的輸出序列列表。在構建序列時，不是貪婪地選擇最可能的下一步，波束搜索擴展了所有可能的后續步驟并且最有可能保持 _k_ ，其中 _k_ 是用戶指定的參數并通過概率序列控制光束數量或平行搜索。 > 局部波束搜索算法跟蹤 k 個狀態而不僅僅是一個狀態。它以 k 個隨機生成的狀態開始。在每個步驟中，生成所有 k 個狀態的所有后繼者。如果任何一個是目標，則算法停止。否則，它從完整列表中選擇 k 個最佳后繼者并重復。 - 第 125-126 頁，[人工智能：現代方法（第 3 版）](http://amzn.to/2x7ynhW)，2009。我們不需要從隨機狀態開始;相反，我們從 _k_ 開始，最可能是單詞作為序列的第一步。對于貪婪搜索，公共波束寬度值為 1，對于機器翻譯中的常見基準問題，公共波束寬度值為 5 或 10。較大的波束寬度導致模型的更好表現，因為多個候選序列增加了更好地匹配目標序列的可能性。這種增加的表現導致解碼速度降低。 > 在 NMT 中，通過簡單的波束搜索解碼器轉換新的句子，該解碼器找到近似最大化訓練的 NMT 模型的條件概率的平移。波束搜索策略從左到右逐字地生成翻譯，同時在每個時間步長保持固定數量（波束）的活動候選。通過增加光束尺寸，轉換表現可以以顯著降低解碼器速度為代價而增加。 - [神經機器翻譯的光束搜索策略](https://arxiv.org/abs/1702.01806)，2017。搜索過程可以通過達到最大長度，到達序列結束標記或達到閾值可能性來分別停止每個候選。讓我們以一個例子來具體化。我們可以定義一個函數來對給定的概率序列和波束寬度參數 _k_ 進行波束搜索。在每個步驟中，使用所有可能的后續步驟擴展每個候選序列。通過將概率相乘來對每個候選步驟進行評分。選擇具有最可能概率的 _k_ 序列，并修剪所有其他候選者。然后重復該過程直到序列結束。概率是小數字，將小數字相乘可以產生非常小的數字。為了避免使浮點數下溢，概率的自然對數相乘，這使得數字更大且易于管理。此外，通常通過最小化分數來執行搜索也是常見的，因此，概率的負對數相乘。最后的調整意味著我們可以按照他們的分數按升序對所有候選序列進行排序，并選擇第一個 k 作為最可能的候選序列。下面的 _beam_search_decoder（）_ 函數實現了波束搜索解碼器。 ```py # beam search def beam_search_decoder(data, k): sequences = [[list(), 1.0]] # walk over each step in sequence for row in data: all_candidates = list() # expand each current candidate for i in range(len(sequences)): seq, score = sequences[i] for j in range(len(row)): candidate = [seq + [j], score * -log(row[j])] all_candidates.append(candidate) # order all candidates by score ordered = sorted(all_candidates, key=lambda tup:tup[1]) # select k best sequences = ordered[:k] return sequences ``` 我們可以將它與前一節中的樣本數據聯系起來，這次返回 3 個最可能的序列。 ```py from math import log from numpy import array from numpy import argmax # beam search def beam_search_decoder(data, k): sequences = [[list(), 1.0]] # walk over each step in sequence for row in data: all_candidates = list() # expand each current candidate for i in range(len(sequences)): seq, score = sequences[i] for j in range(len(row)): candidate = [seq + [j], score * -log(row[j])] all_candidates.append(candidate) # order all candidates by score ordered = sorted(all_candidates, key=lambda tup:tup[1]) # select k best sequences = ordered[:k] return sequences # define a sequence of 10 words over a vocab of 5 words data = [[0.1, 0.2, 0.3, 0.4, 0.5], [0.5, 0.4, 0.3, 0.2, 0.1], [0.1, 0.2, 0.3, 0.4, 0.5], [0.5, 0.4, 0.3, 0.2, 0.1], [0.1, 0.2, 0.3, 0.4, 0.5], [0.5, 0.4, 0.3, 0.2, 0.1], [0.1, 0.2, 0.3, 0.4, 0.5], [0.5, 0.4, 0.3, 0.2, 0.1], [0.1, 0.2, 0.3, 0.4, 0.5], [0.5, 0.4, 0.3, 0.2, 0.1]] data = array(data) # decode sequence result = beam_search_decoder(data, 3) # print result for seq in result: print(seq) ``` 運行該示例將打印整數序列及其對數似然。嘗試不同的 k 值。 ```py [[4, 0, 4, 0, 4, 0, 4, 0, 4, 0], 0.025600863289563108] [[4, 0, 4, 0, 4, 0, 4, 0, 4, 1], 0.03384250043584397] [[4, 0, 4, 0, 4, 0, 4, 0, 3, 0], 0.03384250043584397] ``` ## 進一步閱讀如果您希望深入了解，本節將提供有關該主題的更多資源。 * [維基百科上的 Argmax](https://en.wikipedia.org/wiki/Arg_max) * [Numpy argmax API](https://docs.scipy.org/doc/numpy-1.9.3/reference/generated/numpy.argmax.html) * [維基百科上的光束搜索](https://en.wikipedia.org/wiki/Beam_search) * [神經機器翻譯的光束搜索策略](https://arxiv.org/abs/1702.01806)，2017。 * [人工智能：現代方法（第 3 版）](http://amzn.to/2x7ynhW)，2009。 * [自然語言處理中的神經網絡方法](http://amzn.to/2fC1sH1)，2017。 * [自然語言處理和機器翻譯手冊](http://amzn.to/2xQzTnt)，2011。 * [法老：用于基于短語的統計機器翻譯模型的光束搜索解碼器](https://link.springer.com/chapter/10.1007%2F978-3-540-30194-3_13?LI=true)，2004。 ## 摘要在本教程中，您發現了可用于文本生成問題的貪婪搜索和波束搜索解碼算法。具體來說，你學到了： * 解碼文本生成問題的問題。 * 貪婪的搜索解碼器算法以及如何在 Python 中實現它。 * 光束搜索解碼器算法以及如何在 Python 中實現它。你有任何問題嗎？在下面的評論中提出您的問題，我會盡力回答。