Algorithms

Viterbi算法和beam search的关系与区别

共同点

两者都是通过计算路径得分来找到最优路径，维特比通常用于序列标注，分数由训练过的CRF来提供，而beam search的分数是从每个时间步softmax输出的词表大小的概率分布中获得。

不同点

beam search搜索

在每次预测的时候是选取概率最高的topk个路径。假设词表大小为3，内容为a,b,c, beam width是2。在seq2seq任务decode时：

生成第1个词的时候，选择概率最大的2个词，假设为a,c,那么当前序列就是a,c 生成第2个词的时候，将当前序列a和c分别作为输入，得到新的6个序列：aa,ab,ac,ca,cb,cc。然后又从其中选择得分最高的两个，假如是aa，cb 不断重复这个过程，知道遇到结束符为止。最终输出得分最高的2个序列。

• 要点:

1. 基于贪心算法思想。
2. seq2seq中decoder的预测过程，可以看做一种宽度（或者说是广度）优先图搜索。因为每一步预测候选集（词表大小是10万量级）很大，所以将概率较低的分支删除，即剪枝。这样大大缩小了搜索空间，所以其得到的是近似解，不是全局最优解。是一种启发式算法。
3. beam search只在test的时候需要。训练的时候知道正确答案，并不需要再进行这个搜索。常用于搜索空间非常大的情况，如语言生成任务，每一步是选择一个词，而词表非常大，在十万量级，beam search可以大大减少计算量。

viterbi维特比

多用于序列标注，在序列标注中，从第t时间步的n个状态开始, 计算转移到第t+1时间步的n个状态的分数(转移分数*发射分数), 每个时间步的每个状态保留最大值对应的的路径，然后在最后一个时间步回溯找到最优路径。

• 要点:

1. viterbi是基于动态规划思想。
2. 每一步是根据上一步全部可能选择的最高概率推测当前所有可能选择的最高概率，保证有全局最优解。
3. 适合于搜索宽度较小的图寻找最优路径，即每一步的选择比较少的时候。如在CRF、HMM中使用。

关于seq2seq中的attention机制，主要有Luong和Bahdanau attention两种，两者的区别如下:

1. 在计算第t个时间步的attention score alignment的时候，Luong是用当前t时刻的hidden state即h_{t}来计算的，而Bahdanau的是用h_{t-1}来计算的
2. 关于context vector，Luong是concatenate h_{t}和c{t} 作为预测y_{t}用的vector，而且这个vector作为additional features和y_{t}concatenate作为decoder下一个时间步的输入。而Bahdanau是concatenate c{t}和h_{t-1} 更新h_{t-1}，然后用这个更新的h_{t-1}生成h_{t}，这个h_{t}也用于预测y_{t}.
   详情参考此链接