深度学习-----------------------------束搜索
目录
- 贪心搜索（一般来说计算最快的）
- 穷举搜索（一般来说是最好的，但可能算不动）
- 束搜索（Beam Search）
- 总结
贪心搜索（一般来说计算最快的）
在seq2seq中使用贪心搜索来预测序列
将当前时刻预测概率最大的词输出。
但贪心很可能不是最优的：
穷举搜索（一般来说是最好的，但可能算不动）
最优算法：对所有可能的序列，计算它的概率，然后选取最好的那个。
如果输出字典大小为n，序列最长为T，那么需要考察
n
T
n^T
nT个序列
n=10000，T=10：
n
T
n^T
nT=
1
0
40
10^{40}
1040
计算上不可行
束搜索（Beam Search）
保存最好的K个候选
在每个时刻，对每个候选新加一项(n种可能)，在kn个选项中选出最好的k个。
时间复杂度：O(knT)
k=5，n=10000，T=10 ➡ knT=5×
1
0
5
10^5
105
每个候选的最终分数是：
总结
束搜索在每次搜索时保存k个最好的候选。
k=1时是贪心搜索。