HMM模型之二————Viterbi算法

第二个问题：Viterbi算法

土方法

现在来到了第二个问题，我吃了三天食堂都是红烧肉，我想知道这三天的大厨最有可能是谁，怎么办？直观的思路还是使用枚举法（没办法啊。。。我总是想出这么简单naive的小白算法）。但是前面已经讨论，这种算法无论是从效率上还是逼格上都太低，因此我们考虑其他的方法。

还算好但是不常用的方法

我们上一篇文章提到了我们可以用前向变量和后向变量搭配使用求解t时刻内部变量是\(S_i\)且输出观测序列O的概率，那么算出t时刻全部的内部状态的各自的概率，那么概率最大的那个就是t时刻最有可能的内部状态，对每个时刻都进行这样的计算不就可以得到最有可能的内部序列的吗？还是上次我们提到的例子，我吃到了三天红烧肉，想求出隐藏的后厨序列，下面已经给出计算好的前向变量和后向变量。

前向变量	t=1	t=2	t=3
大爷(i=1)	0.54	0.0018	0.00549
大叔(i=2)	0.03	0.0552	0.011142
大哥(i=3)	0	0.0393	0.004701

后向变量	t=1	t=2	t=3
大爷(i=1)	0.368	0.16	1
大叔(i=2)	0.487	0.23	1
大哥(i=3)	0.487	0.23	1

那么第一天是大爷的“概率”：
$$ \alpha_{t=1}(1)*\beta_{t=1}(1) = 0.54*0.368=0.19872 $$

第一天是大叔的“概率”：
$$ \alpha_{t=1}(2)*\beta_{t=1}(2) = 0.03*0.487=0.01461 $$
而第一天不可能是大哥，所以我们可以认为第一天最有可能的是大爷。此处的概率一词加了引号是因为只是形式意义上的一种可能性的表示，但是不满足概率的归一化的要求。
以此类推，计算第二天第三天，得到最有可能的后厨序列是：大爷-大叔-大叔。这有什么问题呢？

“问题在于在可能性很多的时候可能出现各个时刻得到的最大的可能的内部状态，但是相邻的两个内部状态可能之间的转换概率很小或者甚至为零。”大部分的教材上都是差不多这个理由，但是我这里也是实在不能给出一个这个算法的反例，毕竟前向后向变量也考虑到了序列之间转换的问题，可能出现这种情况要求大量的内部状态。这里不深究啦，毕竟我们有更好的算法。（摊手）

主角登场：维特比算法

我们想要计算最有可能的内部状态序列，也就是说求解该式\(argmax_XP(X|O,\mu)\)。Viterbi算法是一种动态规划算法，类似于其他动态规划算法，关键思路用比较“傻”的方式，可以这么说：“如果我选你了，我也要选你最好的方式”。这句话可能不太像人话，但是举个例子可能更好理解。假设我想去很远的一个地方，中间要休息好几次，我不知道最优路径，但是我假设要去A地休息，我也会选择最近的路去A，假设去A的途中要路过B，我也会选择最近的路去B，这是很直观的想法，问题在于我不知道是否要去A或者B。
类似的思路，我们可以定义Viterbi变量

$$ \delta_t(i)=\max_{q_1q_2…q_{t-1}}P(q_1q_2…q_{t-1},q_t=S_i,O_1O_2…O_t|\mu) $$

这个变量所表示的是**在时间t时，模型沿着最佳路径到达内部状态Si，使得输出观察序列$O_1O_2…O_t$的最大概率**。
假设我只考虑第一天，那么只需要计算第一个内部变量的初始概率乘以对应的输出概率，选取最大值就好了。但是我不知道真正的最有内部序列的第一个状态是不是就是这时算出的最大可能状态，没关系，我把第一步计算出的内部状态的概率记下来，以备后用。计算第二步的时候对每个可能的状态考虑所有上一步的可能性，并选择最大的状态，然后也全部记录下来（不但要记录那个最大概率，也要记录得到最大概率的上一步的选择）。知道计算第i步的时候我只考虑第i-1步就可以，因为我知道i-1步及其之前记录的概率已经是经过选择的最好路径了。这样直到最后一步就得到了最优内部状态序列。我不知道有没有讲明白，talk is cheap，tell you the （伪）code。

• 初始化：
  $$ \delta_{t=1}(i)=\pi_i*b_{i,o_1}，(1\leq i\leq N) $$

• 递归计算：
  $$ \delta_{t}(j)=max_i[\delta_{t-1}(i)*a_{i,j}]*b_{j,o_t} $$
  $$ \varphi_{t}(j)=argmax_i[\varphi_{t-1}(i)*a_{i,j}]*b_{j,o_t} $$

• 结束
  $$ Q_t=argmax_i[\delta_T(i)] $$
  $$ p(Q_T)=max[\delta_T(i)] $$

• 回溯路径
  $$ Q_t = \varphi_{t+1}(q_{t+1}) $$

这里重复给出HMM之大学食堂的两个概率矩阵：

转移概率	大爷	大叔	大哥
大爷	0	0.3	0.7
大叔	0.1	0.4	0.5
大哥	0.1	0.4	0.5

输出概率	蕉	西	肉
大爷	0.1	0.3	0.6
大叔	0.3	0.4	0.3
大哥	0.6	0.3	0.1

来个栗子，还是计算前三天都吃到红烧肉的最有可能的内部序列。

• t=1时刻
  $$ \delta_{t=1}(1)=\pi_1*b_{1,o_1}=0.9*0.6=0.54 $$
  $$ \delta_{t=1}(2)=\pi_2*b_{2,o_1}=0.1*0.3=0.03 $$
  $$ \delta_{t=1}(3)=\pi_3*b_{3,o_1}=0*0.1=0 $$

Viterbi变量	t=1	t=2	t=3
大爷	0.54
大叔	0.03
大哥	0

这是此时的以矩阵形式写出的Viterbi变量，由于t=1时不需要从上一时刻的维特比变量中选择最大路径，因此直接计算就可以。

• t=2时刻
  $$ \delta_{t=2}(1)=\max_i[\delta_{t=1}(i) * a_{i,1}] * b_{1,o_2} = 0.03 * 0.1 * 0.6=0.0018 $$
  选择的上一个最佳Viterbi变量是\(\delta_{t=1}(2)\)
  $$ \delta_{t=2}(2)=\max_i[\delta_{t=1}(i) * a_{i,2}] * b_{2,o_2} = 0.54 * 0.3 * 0.3=0.0486 $$
  （选择的上一个最佳Viterbi变量是\(\delta_{t=1}(1)\)）
  $$ \delta_{t=2}(3)=\max_i[\delta_{t=1}(i) * a_{i,3}] * b_{3,o_2} = 0.54 * 0.7 * 0.1=0.0378 $$
  （选择的上一个最佳Viterbi变量是\(\delta_{t=1}(1)\)）

Viterbi变量	t=1	t=2	t=3
大爷	0.54	0.0018（From 2）
大叔	0.03	0.0486（From 1）
大哥	0	0.0378（From 1）

这是此时的以矩阵形式写出的Viterbi变量，并且此时的每一个节点计算后要存储自己是通过上一时刻的哪一个变量计算得到，方便最后一步的回溯。

• t=3时刻
  $$ \delta_{t=3}(1)=\max_i[\delta_{t=2}(i)*a_{i,1}]*b_{1,o_2} = 0.486*0.1*0.6=0.02916 $$
  （选择的上一个最佳Viterbi变量是\(\delta_{t=2}(2)\)）
  $$ \delta_{t=3}(2)=\max_i[\delta_{t=2}(i)*a_{i,2}]*b_{2,o_2} = 0.486*0.4*0.3=0.05832 $$
  （选择的上一个最佳Viterbi变量是\(\delta_{t=2}(2)\)）
  $$ \delta_{t=3}(3)=\max_i[\delta_{t=2}(i)*a_{i,3}]*b_{3,o_2} = 0.486*0.5*0.1=0.0243 $$
  （选择的上一个最佳Viterbi变量是\(\delta_{t=2}(2)\)）

Viterbi变量	t=1	t=2	t=3
大爷	0.54	0.0018（From 2）	0.02916（From 2）
大叔	0.03	0.0486（From 1）	0.05832（From 2）
大哥	0	0.0378（From 1）	0.0243（From 2）

那么计算到最后一步时，我们就算“填好”这个算法中最重要的表格，那么这个算法就已经完成了一大大半的。根据维特比变量的定义，最后一步的维特比变量表示的是“在最后时刻时，模型沿着最佳路径到达最后一个内部状态\(S_i\)，使得输出观察序列\(O_1O_2…O_t\)的最大概率”，那么我们在最后一个时刻的所有我维特比变量中选择最大的一个也就得到了所有可能的内部状态序列中，“输出观察序列\(O_1O_2…O_t\)的最大概率”。
回顾一下这类算法的思想，就是假设我在路径中间选择一个要经过的内部点，那么我到达这个内部点的路径一定要选择最优路径。这就使得我们最后一列维特比变量中在选择最大的一个时，就可以回溯找到到达这一点的最优路径。在这个栗子中就是这样婶儿的：

得到内部状态最优序列：大爷-大叔-大叔，和我们的好一点的土方法的结果一样嘿！当然了，我们在前面说过，第二种土方法不是不好，但是有可能陷入局部最优而找不到全局最优解，那么既然我们有更好的Viterbi为什么不用呢？

第三个问题：Baum-Welch算法（未完待续）