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

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

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

問題背景

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

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

主要方法

前向啟發(fā)算法

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

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

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

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

無限制生成

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

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

受限制生成

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

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

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

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

實(shí)驗(yàn)結(jié)果

無限制生成

作者們?cè)诠适律扇蝿?wù)上開展了實(shí)驗(yàn)，可以發(fā)現(xiàn)提出的方法不論是在流暢性，豐富性還是人工評(píng)估上都有著很好的表現(xiàn)。

受限制生成

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

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

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

結(jié)語

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

審核編輯 ：李倩