[L2]Seq2Seq中Beam Seach贪心算法和维特比算法
- 2020 年 4 月 8 日
- 筆記
爱是一种无尽的宽恕,是一束缠绕在心头的温柔的目光。
全文字数：2413字
阅读时间：14分钟
前言
由于在公众号上文本字数太长可能会影响阅读体验，因此过于长的文章，我会使用"[L1]"来进行分段。这系列将介绍Seq2Seq模型中的Beam Search算法。第一篇文章：[L1]Seq2Seq中Beam Seach的应用场景。
a
贪心算法
上面说了那么多，无非就是想要说明，如果target sequence词汇表的大小为
的话，对于解码器的
步输出，他的搜索空间
。随着
的增大，那这个效率会非常低。所以我们才想要通过一些算法去找出使得概率最大的输出序列。
下面使用简单的例子来说明，比如我的target sequence词汇表中仅有三个单词，也就是
，现在假设已经输入了待翻译的句子， 也就是
已知了。想要求的是使
的
，那
。
▲机器翻译示意图
我们知道
，为了直观，我们可以使用概率图模型进行表示：
▲概率图模型~来自小象学院
我们要计算
，我们可以展开成
，那我们直观的想法就是让每一步都选择最大的
，把它们相乘就是我最终的输出序列
。这就是贪心算法的思想，每一步都选择最大的概率。那么根据上面的概率图可以求出：
，也就是
;
，也就是
;
，也就是
;
综合起来 ：
，那最后使用贪心算法算出的输出序列是
，那很明显这并不是最优解。
b
Viterbi Algorithm（维特比算法）
如果我们把
看成是三个状态：
▲HMM
那可以看成是HMM，对于HMM来说，求给定观测序列条件概率
最大的状态序列，属于HMM的第三个基本问题~预测问题。在HMM中，我们使用了Viterbi Algorithm。那类似的，我们会想到使用Viterbi Algorithm应用到求最大序列的问题上。
Viterbi Algorithm用动态规划的思想来求解概率最大的路径（最优路径），这个最终的最优路径就是我们想要得到的最终的输出序列。简单的说我们只需从第1步开始，递推地计算在第
步输出单词为
的各条部分路径的最大概率，直至得到最后一步输出单词
的各条路径的最大概率。下面使用一个简单的例子来说明一下Viterbi Algorithm：
那假设现在只有两个单词，即
，那么我们可以画出下面的概率图模型出来（这里为了简单，状态转移值）：
我们想得到最优路径（路径上概率值乘积最大），根据动态规划的思想那么可以认为每一步都是最优的。我们可以发现每一个节点都对应着部分路径，比如对于第二步来说：
- 对于第二步的
结点来说：
，
两条路径，那现在假设
的值最大，也即认为对于第二步的
结点来说
是最优的序列；
- 对于第二步的
结点来说：
，
两条路径，那现在假设
的值最大，也即认为对于第二步的
结点来说
是最优的序列；
对于第二步的每一个节点我们都有了一个对于这个结点来说最优的序列，那现在我们加上第三步：
- 对于第三步的
结点来说：
，
，
，
四条路径：
- 对于
，
这两条路径来说，因为我们前面在第二步的
结点中已经确定了到达第二步结点
时候的最优路径，所以我们选择
这条路径；
- 对于
，
这两条路径来说，因为我们前面在第二步的
结点中已经确定了到达第二步结点
时候的最优路径，所以我们选择
这条路径；
然后我们可以知道对于第三步的
结点来说，是
大还是
概率值大，选择最大的概率值对应的序列作为第三步结点
的最优路径。这样不断的迭代知道最后一步，选择概率最大的结点最为最终的最优路径。当然我们需要的是使得最终概率值最大的序列，所以我们需要计算每一个结点最优路径的时候，需要记住保留路径的父节点，比如对于第二步的
结点来说，我们得到
最为最优路径，那对于第二步的
结点来说，我们需要记住被选择的父节点也就是第一步的
结点。
有了上面简单的介绍，现在我们用公式来定义：
表示以
结尾的最大概率的sequence的概率；
表示第
步从
到第
步的
的概率，也就是转移概率，在概率图模型中就是
和
路径上的概率值；
动态规划的递推公式：
那对于我们前面那个概率图，怎么使用Viterbi Algorithm来计算最优的路径呢？
▲概率图模型~来自小象学院
对于Viterbi Algorithm来说实质上就相当于是一个填表的过程：
▲Viterbi算法的表格
- 第一步：
，
，
- 第二步：
从上面计算可以看出0.15最大，也就是对于第二步的
结点来说，
是最优的路径，然后把
填到
对应的表格中，依次类推，可以得到下面表格：
▲使用Viterbi算法的表格
可以看出在最后一步
，最大的序列概率值为0.105，也就是回溯父节点，可以得出最优的路径也就是使得概率最大的序列
。
下面来看一看使用Viterbi算法的复杂度：
- 从上面的表格可以看出计算复杂度为
，那对于表格中的每一个单元，需要从前面的
的数据中去遍历，所以计算复杂度为
。比如对于
来说，计算这个值我们需要计算
也就是需要去遍历出
；
- 空间复杂度也就是表格中所有数据，即空间复杂度
；
那可以看出，Viterbi算法还是很不错的，能够得到最优的值，但是如果target sequence词汇表
特别大的话，效率还是不高，当然target sequence词汇表
很小的时候，Viterbi算法会是一个很不错的选择，但是通常我们的target sequence词汇表
很大。所以就有了Beam search算法，他通过舍弃一些精度来提高效率。
参考： 1.《统计学习方法》 2.小象学院
