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

論文標(biāo)題:
NEUROLOGIC A*esque Decoding: Constrained Text Generation with Lookahead Heuristics

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

問題背景

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

為了達到全局最優(yōu)的效果，需要滿足如下的優(yōu)化目標(biāo)

主要方法

前向啟發(fā)算法

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

其中是迄今為止的分?jǐn)?shù)，是對于未來分?jǐn)?shù)的啟發(fā)式估計。因此我們將優(yōu)化目標(biāo)修改為如下形式

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

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

無限制生成

在無限制生成的場景下，使用的優(yōu)化函數(shù)為

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

受限制生成

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

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

其中是約束條件的前綴，這個優(yōu)化函數(shù)的目標(biāo)是獎勵那些滿足約束條件的樣本。接下來，作者們加入了前向啟發(fā)函數(shù)

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

實驗結(jié)果

無限制生成

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

受限制生成

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

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

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

結(jié)語

本文的方法實現(xiàn)并不復(fù)雜，所用到的原理和思想也是非常經(jīng)典的人工智能算法，但卻取得了非常不錯的性能，一舉摘得了NAACL2022的最佳方法論文。看來，好的研究并不是追逐熱點，調(diào)參魔改結(jié)構(gòu)的增量式創(chuàng)新，而是打好數(shù)學(xué)基礎(chǔ)，深入地思考研究問題，廣泛接觸各個領(lǐng)域的算法，才能在發(fā)現(xiàn)領(lǐng)域的關(guān)鍵待解決問題時取得成果~

審核編輯 ：李倩