1. 问题描述

  预测问题（解码问题）：已知模型$\lambda =(A,B,\pi )$和观测序列$O=(o_1,0_2,...o_T)$，求对给定预测序列条件概率 P(I|O)最大的状态序列$I=(i_1,i_2,...,i_T)$。该问题其实是最被常用的，也是我们之前一直提到的如何进行序列标注。解决该问题需要用到维特比算法。第二章详细讲述了维特比

2. 解决方法一：维特比算法

  初看本章目录，可能感觉不太合理，但其实不然，作者故意为之。因为先讲为什么得到结论，也即推导，可能还是不太明白，甚至听完感觉明白了，一做题发现理解错误。所以这里，我们先抛出结论。结论中给出的定义先不要问为什么是这个式子，为什么这么取。假设他是对的，走一遍案例。然后再看推导，结合求解案例的过程，可能会更好理解。

2.1 结论

• 首先给出几个定义：

- ${\delta }_t(i)$：t 时刻，状态为 i 的概率，因为状态有 N 种，故可以求出 N 个${\delta }_t$，简单来讲，可以理解成$P(i_t=q_i)$。但实际上不是这样的，具体的后面讲推导的时候再来更正，现在可以先这么理解。

- 递推：${\delta }_{t+1}(i)$是一个递推式，公式定义为：${\delta }_{t+1}(i)=\underset{1\le j\le N}{\max }[{\delta }_{t-1}(j)a_{ji}]b_i(o_{t+1})$，首先理解下 max 下面加取值范围的含义。max 下的 j 说明了 max 里面变化的是 j，由于 j 的变化会带动${\delta }_{t-1}(j);a_{ji}$的变化，$1\le j\le N$说明了 j 的取值范围。因此 max 下加取值范围的含义是在 j 变化过程中$[{\delta }_{t-1}(j)a_{ji}]$的最大值。上述${\delta }_t$有 N 个取值，每个${\delta }_t(i)$对应一个${\psi }_t(i)$，因此，某一时刻${\delta }_t$计算 N 个取值，相应的，${\psi }_t(i)$计算 N 个取值，且两者一一对应。

- ${\psi }_t(i)$:其定义为$\psi (i)=arg\underset{1\le j\le N}{\max }[{\delta }_{t-1}(j)a_{ji}]$。$argmax$下面挂取值范围，这里就不多做阐述了，其实看到$argmax$就已经知道${\psi }_t(i)$是变量 j 的其中一个值。看 max 里面，不就是递推公式里 max 里面的内容吗。因此连到一起看，${\psi }_t(i)$是在当前时刻状态为 i 时上一时刻的某个状态，且这个状态令${\delta }_{t-1}(j)a_{ji}$最大，也即令当前时刻最大。**

- 维特比算法确定最优路径的过程（此时可以结合下方案例以及手写图片理解）：

- 第一步，根据递推公式，从 t=1 时刻开始计算$\delta$以及对应的$\psi$。

- 比较最后一个时刻的${\delta }_T(1)、{\delta }_T(2)、{\delta }_T(3),...,{\delta }_T(N)$，找到最大值，以及最大值对应的${\psi }_T$。

- 逆向求解最优路径(案例中高亮部分，从后向前看)

2. 2 案例

已知

观测序列$O=(红，白，红)$，观测序列只有两种取值(红，白)，B 的第一列对应红，第二列对应白；隐藏状态取值有 3 种(1, 2, 3)，求最优的状态序列答案解析：

• 第一步：递推求解每一时刻的$\delta$和$\psi$。

t = 1 时：

${\delta }_1(1)={\pi }_1{b}_1(o1=红)=0.2\ast 0.5=0.1$，记${\psi }_1(1)=0$

${\delta }_1(2)={\pi }_2{b}_2(o1=红)=0.4\ast 0.4=0.16$，记${\psi }_1(2)=0$

${\delta }_1(3)={\pi }_3{b}_3(o1=红)=0.4\ast 0.7=0.28$，记${\psi }_1(3)=0$

t = 2 时：

同理求得

因此：

${\delta }_2(1)=0.028；{\psi }_2(1)=3$

t=3 时：

同理求得${\delta }_3(2);{\psi }_3(2);{\delta }_3(3);{\psi }_3(3)$因此：${\delta }_3(1)=0.00756；{\psi }_3(1)=2$${\delta }_3(2)=0.01008；{\psi }_3(2)=2$;==${\delta }_3(3)=0.0147；{\psi }_3(3)=3$

• 第二步：比较最后一个时刻 t=3 时的${\delta }_T$，找出最大值，以及对应的${\psi }_T$:最后一个时刻 t=3 时：${\delta }_3(1)=0.00756；{\psi }_3(1)=2$${\delta }_3(2)=0.01008；{\psi }_3(2)=2$;==${\delta }_3(3)=0.0147；{\psi }_3(3)=3$，其中${\delta }_3(3)$值最大，因此 t=3 时，选择状态 3；其对应的${\psi }_3(3)=3$==

• 第三步：逆向求解最优路径:t=3 时选择了状态 3，计算过程中取的是上一时刻 t=2 的状态 3（上一时刻${\delta }_2(3)a_{33}$令${\delta }_3(3)$值最大）;t=2 时选择了状态 3（因为 t=3 时，令${\delta }_3(3)$值最大的上一时刻状态是 3），计算过程中取的是上一时刻 t=1 时刻的状态 3（上一时刻${\delta }_1(3)a_{33}$令${\delta }_2(3)$值最大）t=1 时选择了状态 3（因为 t=2 时，令${\delta }_2(3)$值最大的上一时刻状态是 3），计算过程中取的是上一时刻 t=0 时刻的状态 0（上一时刻${\delta }_1(3)a_{03}$令${\delta }_1(3)$值最大）因此最优路径是(3,3,3)

2.3 推导

  上面先讲了如何计算，本节主要讲述为什么。

• 动态规划原理中最优路径具有特性：如果最优路径在时刻 t 通过结点 $i_t^$，那么这一路径从结点$i_t^$到终点$i_T^$的部分路径，对于从$i_t^$到$i_T^$的所有可能的部分路径来说，必须是最优的。因为如果不是这样，那么从$i_t^$到$i_T^$就有另外一条更好的部分路径存在，如果把它和从$i_1^$到达$i_t^*$的部分路径连接起来，就会形成一条比原来更优的路径。这与动态规划的最优路径的特性定义相矛盾。

• 维特比算法中的动态规划思想：以 2.2 的案例为例，假如现在观测序列变为$O=(红,白)$即只有两个时刻 t=1 和 t=2(为了方便讲解，只选取两个时间)。我们知道观测序列为{红，白}，求的是隐藏序列（来自哪个盒子），可能的结果为{1,1}、{1,2}、{1,3}、{2,1}、{2,2}、{2,3}、{3,1}、{3,2}、{3,3}，问题的本质是求这 9 种可能哪个概率最大，概率最大的那个就是我们的答案。将所有可能的结果呈现在二维图中：

• 对上图进行阐释：在已知第一次为红色时，可以选择第 1、第 2、第 3 个盒子；第二次为白色亦同。由此从第一次红色到第二次白色就有 9 条路径可以选择。

• 假如第一次和第二次结果对应的盒子分别是盒子 1 和盒子 2，也就是说选择了路径 2。那么我们如何确保图中的路径 2 概率最大呢？

• 从第二次结果考虑，只要从开始到第一次结果选择的路径正确，且从第一次结果到第二次结果的转移正确（即第二次正确选择了盒子 2），就能保证我们整个路径正确。

• 广泛地讲：只要从开始到第 t 次结果选择的路径是正确的，且第 t+1 时刻正确选择（t 时刻到 t+1 时刻转移正确）就能保证直到 t+1 时刻我们的选择都是对的，得到的答案就是最优答案。由于 t 时刻选择的结果依赖于 t-1 时刻的选择，因此可以确定好 t 时刻的选择再一直向前推，推导 t-1、t-2...t=1 时刻的结果，就是维特比算法的思想。

• 维特比算法的公式化表示：

• 最优路径：$I^=(I_1^,I_2^,...,I_T^)$

• 定义在时刻 t 状态为 i 的所有单个路径$i_1,i_2,...,i_t$中概率最大值${\delta }_t(i)$：定义方式有点像前后向算法，已知参数，求时刻 t 的状态为 i，求出现观测序列的概率。注意的是有一个要求-时刻 t 的状态为 i。公式见下，注意，公式中的$i_1,...,i_{t-1}$是一组变量，放到 max 下面，指这组变量取哪组值时能让$i_t=i$**的概率最大。**其他的$o_1,...o_t,\lambda$都是已知的量，也即定量，放到公式里，只是说明，我已知这些量。在概率当中，如果 y 为定量，非随机变量，x 为随机变量，概率表达式可以写成 P(x;y)或者 p(x|y)。用条件概率的形式表示，只是想说明，有一个已知的定量，实际并非条件概率。${\delta }_t(i)$**本质是概率，但该概率携带了 t 时刻状态为 i 这一信息。

• 递推公式：根据序列生成任务，t+1 时刻的隐藏状态=t 时刻的隐藏状态×$a_{ij}$（j 为 t+1 时刻的隐藏状态）×$b_j(o_{t+1})$，因此 t+1 时刻的最大概率${\delta }_{t+1}(i)$等于 t 时刻的${\delta }_t(j)$乘转移概率和观测概率。公式表达如下：

• 由递推公式可以看到，${\delta }_{t+1}(i)$的取值（t+1 时刻状态为 i 这一事实）取决于上一时刻${\delta }_{t-1}(j)$，也即上一时刻状态 j 的选择。因此计算${\delta }_{t+1}(i)$需要从${\delta }_1(k)$一点点向后计算到${\delta }_{t-1}(j)$，才能得到${\delta }_{t+1}(i)$，但是确定最优路径时，计算到最后只有${\delta }_T(i)$，不存在后面 T+1 的递推公式了。在时刻 T 只要比较${\delta }_T(1),{\delta }_T(2),...,{\delta }_T(N)$的最大值，也就确定了时刻 T 的状态（假如为状态 2），而根据递推式，时刻 T 的状态 2 取决于上一时刻 T-1 的状态，因此只要 T 时刻的状态 2 一确定，T-1 时刻的状态也就确定了（让 T 时刻状态为 2 的概率最大的那个状态）。因此定义在时刻 t 状态为 i 的所有单个路径$i_1,i_2,...,i_t$中概率最大的路径的第 t-1 个结点(本质是结点

• 总结维特比算法的过程：

3. 解决方法二：近似算法