1.算法描述
Beam Search算法是以較少的代價在相對受限的搜索空間中找出其最優(yōu)解，得出的解接近于整個搜索空間中的最優(yōu)解侦副。
Beam Search算法一般分為兩部分：
- 路徑搜索：是指在受限空間中檢索出所有路徑
- 路徑打分：是指對某一條路徑進(jìn)行評估打分
Beam Search的一般步驟為：
- 初始化beam_size個序列污它，序列均為空剖踊，這些序列稱之為beam paths；
- 取下一個Frame的前N個候選值（N一般為beam size或者更大衫贬，F(xiàn)rame內(nèi)部侯選值已按照概率倒序排列）德澈，與已存在的beam paths組合形成N * beam_size條路徑，稱之為prob_paths固惯；
- 對prob_paths進(jìn)行打分梆造，取前beam_size個prob_path作為新的beam paths；
若解碼結(jié)束在完成算法葬毫，否則回到2镇辉。
注意：
beam_search只在test的時候需要。
2. motivation動機(jī)
（1）encoder-decoder框架
- Encoder部分是一個兩層的LSTM 神經(jīng)網(wǎng)絡(luò)贴捡，這個神經(jīng)網(wǎng)絡(luò)不做任何輸出忽肛，只輸出最后一步的h,c，我們可以理解這個h,c 是已經(jīng)總結(jié)了的輸入信息烂斋；
- Decoder部分也是一個兩層的LSTM 神經(jīng)網(wǎng)絡(luò)屹逛，并且其隱藏層h,c 的初始值為Encoder 部分輸出的h,c箍镜，然后在Decoder 部分進(jìn)行翻譯。
注意在Encoder 部分每一步并不預(yù)測任何東西煎源，其初始的h,c 為全零向量，并且與Decoder 是完全不同的參數(shù)香缺。
（2）Beam Search
Mismatch between Train and Test
首先需要注意到模型訓(xùn)練和模型預(yù)測是兩個不同的過程手销，在訓(xùn)練時，我們知道每一步真正的reference图张，而在預(yù)測時是不知道每一步的reference 的锋拖。
在上圖的網(wǎng)絡(luò)結(jié)構(gòu)中，都是以上一時刻真正的reference 作為下一時刻的input 來訓(xùn)練模型祸轮。但是在預(yù)測階段我們是不知道reference 的兽埃，我們可以嘗試這樣做，把上一次的輸出作為下一次的輸入适袜。
如果一步錯柄错，可能步步錯，造成嚴(yán)重后果
3. 代碼講解
未完待續(xù)……
4.改進(jìn)
論文1：A Simple, Fast Diverse Decoding Algorithm for Neural Generation
作者：Jiwei Li, Will Monroe and Dan Jurafsky
單位：Stanford
關(guān)鍵詞：seq2seq, diversity, RL
文章來源：arXiv, 2016
問題：seq2seq模型decoder時改進(jìn)beam search苦酱，引入懲罰因子影響排序結(jié)果售貌，并加入強(qiáng)化學(xué)習(xí)模型來自動學(xué)習(xí)diversity rate，使得解碼出的結(jié)果更具多樣性
模型改進(jìn)：對比標(biāo)準(zhǔn)beam search疫萤，本模型引入懲罰因子颂跨。
論文2：DIVERSE BEAM SEARCH: DECODING DIVERSE SOLUTIONS FROM NEURAL SEQUENCE MODELS
作者：
Ashwin K Vijayakumar, Michael Cogswell, Ramprasath R. Selvaraju, Qing Sun1 Stefan Lee, David Crandall & Dhruv Batra
單位：
Virginia Tech, Blacksburg, VA, USA
Indiana University, Bloomington, IN, USA
關(guān)鍵詞：
Beam Search; Diversity; Image Caption; Machine Translation; Visual Question Answer; Chatbot
文章來源：
arXiv, 2016.10
問題：
如何改進(jìn)beam search解碼算法，使其在seq2seq模型中可以生成更加豐富的結(jié)果扯饶？
模型：
經(jīng)典的beam search算法以最大后驗概率作為優(yōu)化目標(biāo)函數(shù)恒削，每一個time step只保留B個最優(yōu)的狀態(tài)，是一種典型的貪心算法尾序，這個經(jīng)典算法常常被用于解碼可選狀態(tài)數(shù)量多的情形钓丰，比如生成對話、生成圖片描述每币、機(jī)器翻譯等斑粱，每一步都有詞表大小的可選狀態(tài)集。seq2seq模型的流行脯爪，讓這種解碼算法的研究變得熱門则北。在生成對話任務(wù)時，用經(jīng)典的beam search會生成類似“我不知道”等這種沒有營養(yǎng)的對話痕慢，雖然沒有語法上的錯誤尚揣，而且可能在一定的評價體系內(nèi)會得到不錯的分?jǐn)?shù)，但實際應(yīng)用效果太差掖举，因此diversity的研究變得熱門快骗。
本文針對diversity的問題，提出了一種改進(jìn)版的beam search算法，旨在生成更加多樣性的話方篮。
新算法的主要思路是將經(jīng)典算法中的Beam進(jìn)行分組名秀，通過引入一個懲罰機(jī)制，使得每一組的相似度盡量低藕溅，這一項保證了生成的話相互之間差異更大一些匕得，即滿足了多樣性的需求，在每一組Beam中巾表，用經(jīng)典的算法進(jìn)行優(yōu)化搜索汁掠。具體的算法流程如下圖：
