HMM的模型

 图1文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

如上图所示，白色那一行描述由一个隐藏的马尔科夫链生成不可观测的状态随机序列，蓝紫色那一行是各个状态生成可观测的随机序列文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

话说，上面也是个贝叶斯网络，而贝叶斯网络中有这么一种，如下图：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

代表：c确定时a和b独立。(c为实心圆代表：c已经被确定)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

这时，如果把z1看成a，x1看成b，z2看成c的话，则因为第一个图的z1是不可观测的(所以z1是空心圆)，也就是没确定，则x1和z2就一定有联系。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

进一步，如果把z2、x2合在一起看成c的话，则x1和z2、x2就一定有联系，则x1和x2有联系(不独立)。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

推广之后：x2和x3不独立，x1和x3也不独立，于是xn们互相不独立。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

HMM的确定

初始概率分布

z1可能是状态1，状态2 ... 状态n，于是z1就有个N点分布：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

即：Z1对应个n维的向量。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

上面这个n维的向量就是初始概率分布，记做π。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

状态转移矩阵

但Z2就不能简单的“同上”完事了，因为Z2和Z1不独立，所以Z2是状态1的概率有：Z1是状态1时Z2是状态1，Z1是状态2时Z2是状态1,..., Z1是状态n时Z2是状态1，于是就是下面的表文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

即：Z1->Z2对应个n*n的矩阵。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

同理：Z_i -> Z_i+1对应个n*n的矩阵。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

上面这些n*n的矩阵被称为状态转移矩阵_，用A_n*n表示。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

当然了，真要说的话，Z_i -> Z_i+1的状态转移矩阵一定都不一样，但在实际应用中一般将这些状态转移矩阵定为同一个，即：只有一个状态转移矩阵。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

图1的第一行就搞定了，下面是第二行。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

观测矩阵

如果对于zi有：状态1, 状态2, ..., 状态n，那zi的每一个状态都会从下面的m个观测中产生一个：观测1, 观测2, ..., 观测m，所以有如下矩阵：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

这可以用一个n*m的矩阵表示，也就是观测矩阵，记做B_n*m。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

由于HMM用上面的π，A，B就可以描述了，于是我们就可以说：HMM由初始概率分布π、状态转移概率分布A以及观测概率分布B确定，为了方便表达，把A, B, π 用 λ 表示，即：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

λ = (A, B, π)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

例子

假设我们相对如下这行话进行分词：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

欢迎来到我的博客文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

再假设我们是这样分的：找到“终止字”，然后根据终止字来分词。即：对于这行字，“迎、到、我、的、客”是终止字，于是最终这么分词：欢迎/来到/我/的/博客文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

下面用上面的知识对这个例子建立HMM的A, B, π：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

初始概率分布的确定：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

1，对于每个样本，我们的目标是确定其是不是“终止字”，因此对于每个样本，其状态只有n=2个：状态1 -- 是、状态2 -- 不是。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

2，因此初始概率分布π为：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

π = {p1，p2}文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

P1：整个句子中第一个字是非终止字的概率文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

P2：整个句子中第一个字是终止字的概率文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

状态转移矩阵的确定：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

刚才已经知道状态有n=2个，于是状态转移矩阵就立马得出了，即状态转移矩阵是个n*n的矩阵，如下：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

A=文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

p11：非终止字 -> 非终止字的概率。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

p12：非终止字 -> 终止字的概率。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

p21：终止字 -> 非终止字的概率。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

p22：终止字 -> 终止字的概率。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

观测矩阵的确定：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

如果我们的目标文字使用Unicode编码，那么上面的任何一个字都是0~65535中的一个数，于是我们的观测就会有m=65536个，于是观测矩阵就是个n*m的矩阵，如下：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

B=文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

p1,0：Unicode编码中0对应的汉字是非终止字的概率文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

p1,65535：Unicode编码中65535对应的汉字是非终止字的概率文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

p2,0：Unicode编码中0对应的汉字是终止字的概率文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

p2,65535：Unicode编码中65535对应的汉字是终止字的概率文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

PS：为什么x会有65535个观测啊？“欢迎来到我的博客”这个明明只有8个字。原因是因为真正的HMM面临的情况，即：现有了 Z1=“非终止字”这个状态，然后根据这个状态从65535个字中选出x1=“欢”这个字，然后根据状态转移矩阵，下一次转移到了Z2 =“终止字”，然后根据Z2从65535个字中选出了x2=“迎”这个字，这样，最终生成了这句话。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

HMM的两个基本性质

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

 齐次假设

当前状态之和上一个状态有关系，用公式表示的话就是：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

P(z_t|z_t-1,x_t-1, z_t-2, x_t-2, ..., z₁, x₁)= P(z_t | z_t-1)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

 观测独立性假设

所有的观测之间是互相独立的，某个观测之和生成它的状态有关系，即：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

P(x_t|z_t,x_t, z_t-1, x_t-1, z_t-2, x_t-2,..., z₁, x₁) = P(x_t | z_t)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

PS：在一开始时说x1和z2、x2不独立，怎么在这里又说x1和x2独立呢？其实真严格追究的话x1和x2的确不互相独立，因为x1是被z1生成的，x2是被z2生成的， 但z2的形成受z1影响，所以x1和x2一定也会有联系，但是为了研究和应用的方便，就假设：生成x1的z1和生成x2的z2不独立，但x1和x2独立。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

HMM的三个问题

现在有几个问题：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

1，知道HMM的参数 λ = (A, B, π) 和观测序列O = {o₁,o₂, ..., o_T} ，如何计算模型 λ 下观测序列O出现的概率P(O | λ)。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

2，HMM的参数如何确定？文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

比如：对于刚才的中文分词的小例子。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

初始概率分布π好确定：是不是终结词的概率各是。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

观测矩阵B也好确定：1/65535嘛文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

但状态转移矩阵怎么确定？我怎么知道下个词是终结词的概率是多少？文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

3，知道HMM的参数 λ = (A, B, π) 和观测序列O = {o₁,o₂, ..., o_T}，如何计算给定观测序列条件概率P(I|O,  λ )最大的状态序列I，即：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

对于中文分词，我想到底如何分的词。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

上面三个问题：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

第一个问题被称为：概率计算问题。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

解决办法：前向-后向算法(一种动态规划算法)。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

第二个问题被称为：学习问题。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

解决办法：如果状态序列已知，那用最大似然估计就好了，但HMM的状态序列未知，即含有隐变量，所以要使用Baum-welch算法(其实其本质就是EM算法)。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

第三个问题被称为：预测问题/解码问题。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

解决办法：Viterbi算法(一种动态规划算法)。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

概率计算问题

该问题有两种解决办法：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

1，直接/暴力算法。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

2，前向算法/后向算法。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

而上面两个算法中的“暴力方法”是实际应用中绝不会被使用的。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

Q：那为什么还说这玩意！（踹）文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

A：理解了直接/暴力算法可以帮助你推导Baum-welch算法。（回踹！）文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

 直接/暴力计算法

问题：已知HMM的参数 λ，和观测序列O = {o₁, o₂, ...,o_T}，求P(O|λ)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

思想核心：大力出奇迹。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

思路：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

1，列举所有可能的长度为T的状态序列I = {i₁, i₂, ..., i_T}；文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

2，求各个状态序列I与观测序列 的联合概率P(O,I|λ)；文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

3，所有可能的状态序列求和∑_I P(O,I|λ)得到P(O|λ)。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

步骤：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

1，最终目标是求O和I同时出现的联合概率，即：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

P(O,I|λ)= P(O|I, λ)P(I|λ)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

那就需要求出P(O|I, λ) 和 P(I|λ)。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

2，求P(I|λ) ，即状态序列I = {i₁,i₂, ..., i_T} 的概率：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

，P(I|λ) = P(i₁,i₂, ..., i_T |λ)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

=P(i₁ |λ)P(i₂, i₃, ..., i_T |λ)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

=P(i₁ |λ)P(i₂ | i_1, λ)P(i₃, i₄, ..., i_T |λ)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

=......文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

=P(i₁ |λ)P(i₂ | i_1, λ)P(i₃ | i_2, λ)...P(i_T | i_T-1, λ)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

而上面的P(i₁ |λ) 是初始为状态i₁的概率，P(i₂ | i_1, λ) 是从状态i1转移到i2的概率，其他同理，于是分别使用初始概率分布π 和状态转移矩阵A，就得到结果：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

PS：上面的a_i1i2代表A的第i₁行第i₂列。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

3，P(O|I, λ)，即对固定的状态序列I，观测序列O的概率是：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

4，代入第一步求出P(O,I|λ)。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

5，对所有可能的状态序列I求和得到观测序列O的概率P(O|λ)：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

时间复杂度：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

每个时刻有n个状态，一共有t个时刻，而根据上面的第5步可以知道每个时刻需要乘2T-1次，所以时间复杂度是：O((2T-1)n^T)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

 前向算法/后向算法

前向概率-后向概率

如下图所示：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

第一行是观测不到的状态序列，第二行是可以观测到的观测序列。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

前向概率的定义是：当第t个时刻的状态为i时，前面的时刻分别观测到y₁,y₂, ..., y_t的概率，即：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

后向概率的定义是：当第t个时刻的状态为i时，后面的时刻分别观测到y_t+1,y_t+2, ..., y_T的概率，即：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

前向算法

如果令前向概率中的t=T，即：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

α_i(T) = p(y₁,y₂, ..., y_T, q_T = i | λ)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

那这就意味着，最后一个时刻位于第i号状态时，观测到y₁, y₂, ..., y_T的概率，这不就是“直接/暴力计算法”中第4步求出来的P(O,I|λ) 嘛。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

因此，如果对 α_i(T) 的i求和，即：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

α₁(T) +α₂(T) + ...+ α_n(T)  式1文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

那就是观测序列O的概率P(O|λ)。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

那么如何算α₁(T) +α₂(T) + ...+ α_n(T)？文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

这样想：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

嗯..如果能算出第T-1时刻的前向概率，即α₁(T-1) +α₂(T-1) + ... + α_n(T-1) 的话，那就能算出式1了(HMM的参数知道了，根据参数不就得了)。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

进一步，如果能算出T-2时刻的前向概率，那就能得出T-1时刻的，进而就得出时刻T的了。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

按照这个思路：啊！我只要算出1时刻的前向概率不就能算出结果了！文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

刚才得到了有趣的结果，即：我求出第一个1时刻的前向概率 α_i(1) 后就等于求出最终结果了，那 α_i(1) 是啥？文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

不就是第一个时刻状态为第i号状态时观测到y₁的概率吗，即：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

α_i(1) = P(y₁,q₁=i | λ)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

而第一个时刻状态为第i号状态的概率是π_i，在第i号状态时得到y1这个观测的概率是B_iy1，于是：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

α_i(1) =π_i* B_iy1文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

PS：因为不知道当前是几号状态，所以为了以后的步骤，这里需要将所有的状态都算出来，即：计算出所有的 α₁(1)  ~  α_i(1)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

好了，第一个时刻已经求出来了，我们就向后推。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

假设现在到第t个时刻了，而第t个时刻的状态是状态j，那我想求时刻t+1状态为i的前向概率怎么求，这样求：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

时刻t+1的前向概率的 α_i(t+1) 的求法就是：t时刻的状态转移到t+1时刻的状态的概率对所有状态求和 * t时刻的状态得到观测的概率，换句话说就是：t时刻的前向概率对所有的状态求和 * t时刻的状态得到观测的概率。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

即：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

a_i(t+1) = (∑_{_j} a_j(t)a_ji)b_iy(t+1)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

解释一下：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

首先，时刻t时状态为j的前向概率是a_j(t)。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

现在时刻t状态为j的概率知道了，那乘上状态j转移到状态i的转移概率就是时刻t+1时状态为i的概率，即 a_j(t)a_ji 。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

但状态是不可观测的啊，所有我们要计算时刻t时所有状态的情况，于是要对j求和，即：∑_{_j} a_j(t) a_ji，这才是t时刻的状态转移到t+1时刻状态的总概率。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

但这样还没完，因为还要由状态得到观测，所以还要在乘上状态i得到观测y_t+1的概率，于是就是上面的式子了。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

现在a_i(t+1) 知道怎么求了，那不就是所有的的前向概率都知道怎么求了，于是利用刚才的结论：P(O|λ) = α₁(T) +α₂(T) + ... + α_n(T)，不就求出观测序列O的概率P(O|λ)了，即：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

P(O|λ) =∑_i α_i(T)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

OK，前向算法说完了，下面总结下。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

前向算法总结

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

初值：α_i(1) =π_i* B_iy1文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

递推：对于t = 1, 2, …,T-1文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

a_i(t+1) = (∑_{_j} a_j(t)a_ji)b_iy(t+1)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

最终：P(O|λ) =∑_i α_i(T)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

PS：这里的 α_i(t) 中i表示第i号状态，t表示第t时刻。有的教程中会把i和t位置调换一下，变成 α_t(i)，其实都一样。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

前向算法例子

假设有3个盒子，编号为1,2,3，每个盒子都装有红白两种颜色的小球，数目如下：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

然后按照下面的方法抽取小球，来得到球颜色的观测序列：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

1，按照 π=(, , ) 的概率选择1个盒子，从盒子随机抽出文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

1个球，记录颜色后放回盒子；文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

2，按照下图A选择新的盒子，按照下图B抽取球，重复上述过程；文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

PS：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

A的第i行是选择到第i号盒子，第j列是转移到j号盒子，如：第一行第二列的代表：上一次选择1号盒子后这次选择2号盒子的概率是。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

B的第i行是选择到第i号盒子，第j列是抽取到j号球，如：第二行第一列的代表：选择了2号盒子后抽取红球的概率是。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

求：得到观测序列“红白红”的概率是多少？文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

解：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

1，明确已知：HMM模型的参数已经如上图所示了，那我们就需要再明确两件事：HMM中那“看不见的状态”和“可见的观测”分别是什么。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

“可见的观测”根据题目可知是：y =“红白红”， “看不见的状态”就是这三次分别选择了什么盒子，且一共有3个状态：选中1号盒子、选中2号盒子、选中3号盒子。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

2，根据前向算法，第一步计算 α_i(1)，这很简单：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

α_{i =1} (t=1) 即时刻1时位于状态“选中1号盒子”的前向概率，所以：α₁(1) =“选中1号盒子”*“选中红球” = π₀* B₁₀= * =文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

同理：α₂(1) =* = 6，α₃(1) = *0.7 = 8。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

3，计算 α_i(2)：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

根据公式：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

α₁(2) = (∑_j α₁(2)α_j1) b_1y2文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

= (* + 6*0.3 + 8*) *文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

=0.077文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

α₂(2) = 104文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

α₃(2) =文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

4，同α_i(2)，计算α_i(3)：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

α₁(3) =文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

α₂(3) =文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

α₃(3) =文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

5，最终文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

P(O|λ) = ∑_i α_i(3)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

= + +文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

= 3022文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

后向算法

有了前向算法的基础，后向算法就好说了，因为就是前向算法的反过来：先计算最后一个然后推到第一个，于是详细说明就不在给了，直接上结论：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

后向算法总结

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

初值：β_T(i) = 1文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

PS：概率为1的原因是 -- 本来还需要看看时刻T后面有什么东西，但因为最后一个时刻T 后面已经没有时刻，即不需要再观测某个东西，所以你随便给个什么都行，我不在乎。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

递推：对于t = T-1, T-2,…, 1文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

β_i(t) = (∑_{_j} a_ijb_jy(t+1)β_j(t+1))文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

PS：这一步是根据t+1的后向概率算t时刻的后向概率β_i(t)，因此：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

β_i(t) = 第t时刻位于第i号状态转移到第t+1时刻位于第j号状态的概率a_ij *   第t+1时刻第j号状态给出y(t+1) 观测的概率b_jy(t+1) * 第t+1时刻的后验概率。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

最终：P(O|λ) =∑_i π_ib_iy1β_i(1)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

PS：同第二步，只不过这里是第1时刻。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

前后向概率的关系

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

具体推倒就不给出了，总之：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

拥有所有观测时，第t时刻有第i个状态的概率 = t时刻的前向概率 * t时刻的后向概率，即：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

P(i_t = q_i, Y | λ )  = α_i(t) * β_i(t)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

单个状态的概率

这里的单个状态是什么呢？就是给定观测O和HMM的参数 λ 时，在时刻t时位于隐状态i的概率，记为：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

γ_t(i) = P(i_t= q_i | O, λ)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

PS：这里的O是所有观测的合集，即：O = {y₁ = o₁, y₂ = o₂, …,y_T = o_T}文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

这个就很强啦，因为我们可以估计在t时刻的隐状态，进而求出隐状态序列！文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

PS：这个的确是求隐状态序列的一种方式，但这种有个问题 -- 求出的隐状态之间互相独立，即：没有考虑到第t+1时刻的隐状态是由第t时刻的隐状态转移过来的情况。换言之：这样求得的隐状态是“每个隐状态都是仅在当前时刻最优，可每个隐状态都没考虑到全局情况”。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

而它的求解也很简单，如下：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

两个状态的联合概率

刚才“单个状态的概率”求得的t时刻的隐状态没有考虑到“上下文”，那就考虑下上下文，即：时刻t位于隐状态i时，t+1时刻位于隐状态j，记为：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

ξ_t(i, j) =P(i_t = q_i, i_t+1 = q_j | O, λ)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

求解推导：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

一些期望

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

学习问题

学习问题分两种：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

1，        观测序列和隐状态序列都给出，求HMM。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

PS：这种学习是监督学习。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

2，        给出观测序列，但没给出隐状态序列，求HMM。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

PS：这种学习是非监督学习，利用Baum-Welch算法。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

观测序列和隐状态序列都给出

这种其实求法超简单：用大数定理用频率来估算HMM的三种概率就OK了。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

解释：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

还是用最开始的分词的例子。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

初始概率：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

i = 0：第一个文字是终止字的次数 / (第一个文字是终止字的次数 + 不是终止字的次数)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

i = 1：第一个文字不是终止字的次数 / (第一个文字是终止字的次数 + 不是终止字的次数)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

转移概率：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

i=0,j=0：第t个字是终止字，第t+1个字是终止字的次数 / (第t个字是终止字，第t+1个字是终止字的次数 + 第t个字是终止字，第t+1个字不是终止字的次数 + 第t个字不是终止字，第t+1个字是终止字的次数 + 第t个字不是终止字，第t+1个字不是终止字的次数)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

i=0,j=1、i=1, j=0、i=1, j=1同理。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

观测概率：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

i=0,k=0：Unicode编码中编码为0的字是终止字的次数 / (Unicode编码中编码为0的字是终止字的次数 + Unicode编码中编码为0的字不是终止字的次数)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

i=1,k=0：Unicode编码中编码为0的字不是终止字的次数 / (Unicode编码中编码为0的字是终止字的次数 + Unicode编码中编码为0的字不是终止字的次数)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

其他k=j同理。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

Baum-Welch算法

其实该算法的本质就是EM算法，因为它解决的问题就是：有了观测值X，而观测值有个隐变量Z时，求在HMM参数 λ下的联合概率P(X, Z | λ) 。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

PS：我总结的EM算法地址如下：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

这里在贴一下EM算法的步骤：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

上面的步骤写成统一的式子就是：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

因此EM算法对应到HMM的学习问题就是：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

所有观测数据写成O=(o₁, o₂ …o_T)，所有隐数据写成I=(i₁, i₂ …i_T)，完全数据是(O, I)=(o₁, o₂ …o_T  ,i₁,i₂ … i_T)，完全数据的对数似然函数是lnP(O, I | λ)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

于是：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

就有如下推导：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

解释：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

第一行：EM的Q函数。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

第二行：条件概率公式。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

第三行：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

第一：第二行分母代表“上一次求出的参数与观测集合的联合概率”，对本次的估计没帮助，所以可以舍去。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

第二：第三行那个是正比符号，即使没有上一个解释可是可以保证第二行与第三行是成正比的。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

话说，P(O, I | λ) 在“HMM概率计算问题”的“直接/暴力计算法”中已经解出了，这里再贴下截图：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

于是上面可以进一步做如下推导：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

对于上式，除了HMM的参数 λ = (A, B, π) 外都是已知的了。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

话说上图将最后一个等号写在3行是为了表述一点：这三行的每一行仅包含HMM的一个参数，而我们的目标是求Q函数的最大，于是只要求最后三行的最大就好了。为了方便说明，我将上图最后三行的三个式子从上向下依次命名为：π式，α式，β式。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

求 π 式

π 式有个约束：所有π_i的和为1。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

于是对于有约束的求极值为题就拉格朗日乘子法的伺候！文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

1，拉格朗日函数文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

2，上式对 π_i 求偏导文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

3，上式对i求和后 π_i 的和为1就把 π 约掉了，从而求出拉格朗日参数文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

4，将上式带入第二步的式子就求出了π：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

而上式的 γ 就是“HMM概率计算问题”中“单个状态的概率”中的 γ(PS：不是拉格朗日参数)，于是 π 就求出来了！文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

求 α 式

α 式可以写成文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

仍然使用拉格朗日乘子法，得到文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

上式的 γ 是“HMM概率计算问题”中“单个状态的概率”中的 γ，上式的 ξ 是“HMM概率计算问题”中“两个状态的联合概率”中的 ξ。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

求 β 式

同理，得到：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

上式的 γ 是“HMM概率计算问题”中“单个状态的概率”中的 γ。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

预测问题

预测问题有两种解决办法：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

1，        近似算法。其实就是“HMM概率计算问题”中“单个状态的概率”的解法。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

2，        Viterbi 算法。下面讲解这个。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

VIterbi算法

在介绍维特比算法之前，我先用通俗的语言描述下它。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

假设我们遇到了这么个问题：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

大学时你让室友帮你带饭(如果你上过大学，别告诉我你没干过这事....)，然后你室友问你想吃啥？你回答：“你吃啥我吃啥，不过回来时帮忙带瓶雪碧，谢啦”。于是有趣的事就发生了：你室友给你带回了饭和雪碧并兴高采烈的说：“我去，食堂换大厨了，那个小卖部的收银员换成了个漂亮妹子！！”然后你问他：“你去的哪个食堂和小卖部？”，他想了想回答：“你猜。”文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

好了，你猜吧~文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

我猜你妹啊(╯‵□′)╯︵┻━┻文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

嘛，先别慌掀桌，不管如何你室友帮你带了饭，所以咱们就满足下他那小小的恶作剧，就当做是给他跑腿的辛苦费好了。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

PS：假设你学校有2个小卖部和2个食堂。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

于是，mission start！文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

首先，问他：你先去得小卖部？他回答：是的。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

OK，买东西的先后顺序搞定了，如下图：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

接下来开始思考：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

第一步：从宿舍到小卖部A和B的距离都差不多，不好判断，即从宿舍到小卖部A的概率 = 从宿舍到小卖部B的概率，如下图；文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

第二步：从小卖部A、B到食堂1、2有四种路线(A1, A2, B1, B2)，然后这四种路线中到食堂1最短的是A1，到食堂2最短的是B2，然后这货绝对那个近选哪个，所以如果去食堂1，则他会选择A1，如果去食堂2，则他会选择B2，如下图：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

第三步：看看他给带来的饭，嗯....这个饭我记得食堂1有卖，食堂2不知道，就当没有吧，那就假设他去的是食堂1，如下图：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

第四步：OK，终点已经确定，接下来反推回去，就好了，即：他绝壁选个最近的小卖部，所以他会选择距离食堂1最近的小卖部A，如下图：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

第五步：对他说：“你先去小卖部A然后去食堂1对吧”，他说：“我次奥，你咋知道的”。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

OK，例子举完了，我们来看看维特比算法，其实维特比算法就是上面的过程：         1，先从前向后推出一步步路径的最大可能，最终会得到一个从起点连接每一个终点的m条路径(假设有m个终点)。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

2，确定终点之后在反过来选择前面的路径。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

3，确定最优路径。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

下面看看Viterbi算法的定义。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

Viterbi 算法的定义

定义变量δt(i)：表示时刻t状态为i的所有路径中的概率最大值，公式如下：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

过程：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

上面的符号之前都已经见过，这里不再解释，下面为了更好地理解这几步，我们来举个例子。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

例子

还是盒子球模型。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

盒子和球模型λ= (A, B,π)，状态集合Q={1, 2, 3}，观测集合V={红, 白}，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

已知观测序列O=(红，白，红)，试求最优状态序列，即最优路径I*= (i₁^*, i₂^*, i₃^*)。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

解：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

如下图所示(图中的数字在之后的步骤中会一一推导出来)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

要在所有可能的路径中选择一条最优路径，按照以下步骤出来。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

1，初始化文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

t=1时，对每个状态i, i=1, 2, 3，求状态为i观测o₁为红的概率，记此概率为δ₁(i)，则：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

δ₁(i) = π_ib_i(o₁)=π_ib_i(红)， i = 1, 2, 3文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

代入实际数据文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

δ₁(1) = 0，δ₁(2) =6，δ₁(3) = 8文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

记ψ₁(i) = 0，i = 1, 2, 3。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

2，在t=n时文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

t=2时，对每个状态i，求在t=1时状态为j观测为红并且在t=2时状态为i观测为白的路径的最大概率，记概率为δ₂(t)，则根据：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

同时，对每个状态i, i = 1, 2, 3，记录概率最大路径的前一个状态j：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

计算：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

同样，在t=3时文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

3，求最优路径的终点文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

以P*表示最优路径的概率，则文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

最优路径的终点是i₃^*:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

4，逆向找i₂^*,i₁^*：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

在t=2时，i₂^* = ψ₃(i₃^*) =ψ₃(3) = 3文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

在t=2时，i₁^* = ψ₂(i₂^*) =ψ₂(3) = 3文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html

于是求得最优路径，即最有状态序列I* = (i₁^*,i₂^*, i₃^*) = (3, 3, 3)。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/10959.html