© 2023 yanghn. All rights reserved. Powered by Obsidian
9.8 束搜索
1.贪心搜索
在 9.7. 序列到序列学习(seq2seq)中我们在每个时间步,在经过 softmax 之后转化为概率,每次都选概率最大的那个词当做下一个词,这种方法是贪心搜索策略,但不能保证是全局最优的:
左边的贪心策略,选出的序列 ABC 不一定有右边非贪心的 ACB 好
2. 穷举搜索
假设我们要计算全部可能的序列,计算其概率,再选取概率最大的序列就是最好的序列,假设字典大小为
, ,计算上不可行
束搜索
在贪心和穷举之间取个折中,每次保留
k=2 的示意图,在每个时间步,考察 k*n 个序列概率最大的 k 个
- 时间复杂度
- 每个候选的最终分数是:
- 其中
是序列长度,通常 , 或者
因为