李沐63_束搜索——自学笔记

贪心搜索

1.在seq2seq中使用贪心搜索来预测序列：将当前时刻预测概率最大的词输出

2.贪心可能不是最优解（步步最优不代表全局最优）

穷举搜索

1.最优算法：对所有可能的序列，计算它的概率，选取最好的那个

2.如果输出字典大小为n，序列长度为T，需考察n^{T个序列，即n=10000，T=10，需考察10}40

束搜索

1.保存最好的k个候选

2.在每个时刻，对每个候选新加一项（n种可能），在kn个选项中选出最好的k个

3.时间复杂度O(knT)：k=5,n=10000,T=10,knT=5X10^5

4.束搜索在每次搜索时保存k个最好的候选：k=1时候是贪心算法，k=n时是穷举算法，一般k取5或者是10，但是越大实时性较差