本文主要是介绍Greedy search 和 beam search，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1 Greedy search
一个自然的想法是贪心搜索(greedy search)，即decoder的每一步都选择最可能的单词，最后得到句子的每一个单词都是每一步认为最合适的单词。但这样并不保证整个句子的概率是最大的，即不能保证整个句子最合适。实际上，贪心搜索的每一步搜索都处理成仅仅与前面刚生成的一个单词相关，类似于马尔科夫假设。这显然是不合理的，具体来说，贪心搜索到的句子yy概率是使得下式概率最大：
P(y|x)=∏nk=1p(yk|x,yk−1)P(y|x)=∏k=1np(yk|x,yk−1)
而实际上，根据全概率公式计算得到P(y|x)P(y|x)为：
P(y|x)=∏nk=1p(yk|x,y1,y2,...,yk−1)P(y|x)=∏k=1np(yk|x,y1,y2,...,yk−1)
2 Beam search
译为束搜索。思想是，每步选取最可能的kk个结果，再从最后的kk个结果中选取最合适的句子。kk称为beam size。
具体做法是：
首先decoder第一步搜索出最可能的kk个单词，即找到y11,y12,...,y1ky11,y12,...,y1k，他们的概率p(y11|x),...,p(y1k|x)p(y11|x),...,p(y1k|x)为最大的kk个。
进行第二步搜索，分别进行kk个模型副本的搜索。每个副本ii，根据上一步选取的单词y1iy1i，选取概率最大的kk个结果y21,y22,...,y2ky21,y22,...,y2k。这样，就有了k∗kk∗k个可能的结果，从这些结果中选择kk个概率最大的结果，即p(y1i|x)∗p(y2j|x,y1i)p(y1i|x)∗p(y2j|x,y1i)最大的kk个结果。
进行第三步搜索，从第二步中确定的kk个结果出发，再进行kk个模型副本的搜索，直到最后一步，从最后的kk个结果中选取概率最大者。
显然，若k=1k=1则为贪心搜索，kk越大则占用内存越大，计算代价越大，实际应用中取10即可。
另外，可以发现概率的连乘使得概率越来越小，很可能溢出，为了保证模型的稳定性，常对概率连乘计算+log变为加法。
P(y|x)=log(∏nk=1p(yk|x,y1,y2,...,yk−1))P(y|x)=log(∏k=1np(yk|x,y1,y2,...,yk−1))
3 改进Beam search
从Beam search的搜索过程中可以发现，Beam search偏向于找到更短的句子，也就是说，如果搜索过程中有一支搜索提前发现了<EOS><EOS>,而另外k−1k−1支继续搜索找到其余更长的结果，那么由于概率连乘(或log连加)，越长的结果概率肯定越小。因此有必要进行模型修正，即进行长度归一化，具体来说，即：
选择概率P(y|x)=1nlog(∏nk=1p(yk|x,y1,y2,...,yk−1))P(y|x)=1nlog(∏k=1np(yk|x,y1,y2,...,yk−1))最大的句子，式中，nn为该结果序列长度。
另外，实践中还做了如下修正：
P(y|x)=1nαlog(∏nk=1p(yk|x,y1,y2,...,yk−1))P(y|x)=1nαlog(∏k=1np(yk|x,y1,y2,...,yk−1))
式中，超参数αα取0.7比较合适。
这篇关于Greedy search 和 beam search的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
