相信大多數學習過人工智能課程的讀者，當聽到算法的時候，都會有一種既熟悉又陌生的感覺。說算法熟悉，是因為一聽到這個算法，就想起那本厚厚的《人工智能——一種現代的方法》，想起這個算法似乎是人工智能課程考試的重點；說算法陌生，是因為大家現在在從事人工智能相關的研究和開發工作時，似乎又很少用到這個算法，大部分時間都花在了研究數據處理和處理實驗設置上面。而在NAACL2022上，一群來自AI2的自然語言處理研究者們利用算法開發了一種新的自然語言生成解碼方式，還被授予了NAACL2022 Best New Method paper。看起來已經過時的A*算法，居然能在深度學習時代有如此的妙用，看完這篇論文，筆者情不自禁地打開了《人工智能——一種現代的方法》，想看看還有什么經典算法可以深挖一下！

論文標題:
NEUROLOGIC A*esque Decoding: Constrained Text Generation with Lookahead Heuristics

論文鏈接:
https://arxiv.org/pdf/2112.08726.pdf

問題背景

自然語言生成任務一般指給定一個輸入序列，生成一個輸出序列。目的是解出使得目標函數最大化的序列，其中, , 而衡量對約束條件的滿足。傳統的Beam Search不考慮全局的最優，而是最優化當前步驟添加的Token.

為了達到全局最優的效果，需要滿足如下的優化目標

主要方法

前向啟發算法

直接優化全局最優目標面臨著搜索空間過大的問題。而A算法可以被用來解決這個搜索問題。A算法是一個最優優先的搜索算法，可以解決這樣形式的搜索問題：

其中是迄今為止的分數，是對于未來分數的啟發式估計。因此我們將優化目標修改為如下形式

同時，需要限制前向搜索的長度為，避免模型無限制地向前搜索

在前向生成的過程中有幾種不同的方法。方法只生成一個序列，從開始，每次選擇概率最大的Token。方法采用插值的思想，混合方法和隨機選擇一個Token的概率分布。方法從開始進行步的Beam Search，選擇前個概率最大的序列, 而方法則是直接從按照概率進行采樣。

無限制生成

在無限制生成的場景下，使用的優化函數為

其中控制的是對未來估計的重視程度，類似于加權算法

受限制生成

在受限制生成任務上，作者們基于之前的工作NeuroLogic進行改進。首先我們簡要介紹一下NeuroLogic方法。首先，將對生成文本的限制表示為合取范式。其中每一個表示一個限制條件，。NeuroLogic的優化目標可以寫為

其中遠大于0，用來懲罰不滿足的約束。在每一步搜索時，NeuroLogic利用如下的打分函數進行計算

其中是約束條件的前綴，這個優化函數的目標是獎勵那些滿足約束條件的樣本。接下來，作者們加入了前向啟發函數

這樣的前向啟發函數有兩個好處，如果是滿足多Token約束的一個Token，前向啟發函數包含了全部約束的分數，如果不是約束的一部分，如果被選中，這一前向策略能考慮到未來約束的分數。

實驗結果

無限制生成

作者們在故事生成任務上開展了實驗，可以發現提出的方法不論是在流暢性，豐富性還是人工評估上都有著很好的表現。

受限制生成

在受限制生成方面，作者們在常識生成，機器翻譯，表格到文本生成，問題生成等任務上開展了實驗。在這里展示常識生成方面的結果。這一任務的主要內容是給定一系列概念，利用全部概念生成一個合理的句子.

可以發現，作者們提出的方法在多個指標上都明顯超越了基線模型，取得了很好的效果。

從文章中給出的例子來看，作者們提出的方法確實有著更好的生成效果。

結語

本文的方法實現并不復雜，所用到的原理和思想也是非常經典的人工智能算法，但卻取得了非常不錯的性能，一舉摘得了NAACL2022的最佳方法論文。看來，好的研究并不是追逐熱點，調參魔改結構的增量式創新，而是打好數學基礎，深入地思考研究問題，廣泛接觸各個領域的算法，才能在發現領域的關鍵待解決問題時取得成果~

審核編輯 ：李倩