@frank-shaw 2015-07-25T09:43:53.000000Z 字数 12733 阅读 5025

3月在线机器学习班第14课笔记--HMM

机器学习

紧随着贝叶斯网络的知识，我们来开启隐马尔科夫模型方面的内容。在之前一直认为与马尔科夫相关的知识点都很难，即使难也得上啊，跟着邹博老师一步一步来去学就没问题了。具体课程笔记如下：

简要回顾

在贝叶斯网络上，记录了一种特殊的贝叶斯网络--马尔科夫模型。
形如下图的贝叶斯网络我们称之为马尔科夫模型。
马尔科夫模型图
如上图所示，M个离散结点形成一条链（各个结点只有一个父结点），每一个结点有 $K$ 个状态，那么根据之前的结论，可以知道描述这M个结点需要的参数个数为 $K-1 + (M-1)K(K-1)$ (有一个结点不包含父结点，剩余M-1个都包含父结点)。可以知道，这是关于长度M的线性函数。
由有向分离可知，在 $x_i$ 给定的条件下， $x_{i+1}$ 和 $x_1,x_2,...,x_{i-1}$ 条件独立。即 $x_{i+1}$ 的分布状态只和 $x_i$ 有关，和其他变量条件独立，这种顺序演变的随机过程模型，叫做马尔科夫模型，因为其满足马尔科夫性质：

P (X n + 1 = x | X 0, X 1, . . ., X n) = P (X n + 1 = x | X n)

$P(X_{n+1} = x|X_0,X_1,...,X_n) = P(X_{n+1} = x|X_n)$

HMM定义

隐马尔科夫模型(HMM, Hidden Markov Model)可用标注问题，在语音识别、NLP、生物信息、模式识别等领域被实践证明是有效的算法。HMM是关于时间序列的概率模型，下图即为HMM的贝叶斯网络：
HMM示意图
HMM描述的是由一个隐藏的马尔科夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测而产生观测随机序列的过程。上图中的 $z_1,z_2,...,z_n$ 称为状态序列，它是不可观测的隐藏的马尔科夫链。每个状态生成一个观测，由此产生的观测随机序列，称为观测序列； $x_1,x_2,...,x_n$ 即为观测序列。
所谓的"隐"，表示的即是我们无法观测到状态序列，而只能通过观测序列来预测状态序列，有一种"听音辨人"的感觉。看到一个生动形象的HMM的例子：一对恋人中，女生有时候喜欢打男朋友，每天十二点可能发作一次。最奇怪是生气时候打，开心时候也打，有时候无缘无故平静还是打。（假设想当天十二点的心情需要参照前天十二点的心情。）能看到的就是妹子外在行动——打人，或者不打人。看不到的，就是隐含的变量：妹子的心情：生气，平静，或者高兴。

就上面的图，请问，在 $z_1,z_2$ 不可观察的前提下， $x_1和z_2$ 独立吗？ $x_1和x_2$ 独立吗？
回答都是不独立的。结合贝叶斯网络中的"tail-to-tail"来判断即可。不仅仅 $x_1和x_2$ 之间不独立，而且 $x_1和x_n$ 之间也不独立，只不过此时 $x_1和x_n$ 相关性相比于 $x_1和x_2$ 要小很多，毕竟 $x_1到x_n$ 已经经过了很多种状态。这种观测序列之间不独立的性质，在很大程度上是符合我们实际情况的。

HMM由初始概率分布 $\pi$ 、状态转移概率分布 $A$ 观测概率分布 $B$ 确定，即HMM三要素。让我们来看看如何定义这三个要素。首先让我们定义：
$Q$ 是所有可能的状态的集合， $N$ 是所有可能的状态数，有： $Q=\{q_1,q_2,...,q_N\}$
$V$ 是所有可能的观测的集合， $M$ 是所有可能的观测数，有： $V = \{v_1,v_2,...,v_M \}$
$I$ 是长度为 $T$ 的状态序列， $O$ 是对应的观测序列，有：

I = {i 1, i 2, . . ., i T} O = {o 1, o 2, . . ., o T}

$I=\{i_1,i_2,...,i_T\}~~~~~~O=\{o_1,o_2,...,o_T\}$

$A$ 是状态转移概率矩阵， $A =|a_{ij}|_{N\times N}$ ，其中

a i j = P (i t + 1 = q j | i t = q i)

$a_{ij} = P(i_{t+1}=q_j|i_t = q_i)$

aij $a_{ij}$ 是在时刻

t $t$ 处于状态

qi $q_i$ 的条件下，时刻

t+1 $t+1$ 转移到状态

qj $q_j$ 的概率。
由定义可知，

A $A$ 矩阵中的第

k $k$ 行表示的是状态

qk $q_k$ 在下一时刻转移到另一个状态的所有可能概率，每一行的概率之和为1。

$B$ 是观测概率矩阵， $B =|a_{ik}|_{N\times M}$ ，其中

b i k = P (o t = v k | i t = q i)

$b_{ik} = P(o_{t}=v_k|i_t = q_i)$

bik $b_{ik}$ 是在时刻

t $t$ 处于状态

qi $q_i$ 的条件下生成观测

vk $v_k$ 的概率。
由定义可知，

B $B$ 矩阵中的第

k $k$ 行表示的是状态

qk $q_k$ 在该时刻生成某一观测的所有可能概率，每一行的概率之和为1。

$\pi$ 是初始状态概率向量， $\pi =(\pi_{i})_N$ ，其中 $\pi_i = P(i_1 = q_i)$ 表示的是时刻 $t=1$ 处于状态 $q_i$ 的概率。

由此可知， $\pi$ 和 $A$ 决定状态序列， $B$ 决定观测序列。我们使用 $\lambda = (A,B,\pi)$ 来表示HMM的三元素。

HMM的两个基本性质

1.齐次假设：

P (i t | i t - 1, o t - 1, i t - 2, o t - 2, . . ., i 1, o 1) = P (i t | i t - 1)

$P(i_t|i_{t-1},o_{t-1},i_{t-2},o_{t-2},...,i_{1},o_{1}) = P(i_t|i_{t-1})$
即状态序列具有马尔科夫性质，时刻

t $t$ 的状态只与时刻

t−1 $t-1$ 的状态有关。

2.观测独立性假设：

P (o t | i t, i t - 1, o t - 1, . . ., i 1, o 1) = P (o t | i t)

$P(o_t|i_t,i_{t-1},o_{t-1},...,i_{1},o_{1}) = P(o_t|i_t)$
即时刻

t $t$ 的观测结果只与时刻

t $t$ 的状态结果有关，和其他无关。

HMM应用举例

假设有3个盒子，编号为1,2,3，每个盒子里面都装有红白两种颜色的小球，数目如下：

盒子号	1	2	3
红球数	5	4	7
白球数	5	6	3

按照下面的方法抽取小球，得到球颜色的观测序列：按照(0.2,0.4,0.4)的概率选择第1个盒子，从该盒子随机抽出1个球，记录颜色后放回盒子；按照A给定的概率选择新的盒子，重复上述过程；最终得到观测序列：“红红白白红”。
这个实例中的各个参数：
- 状态集合：Q={盒子1，盒子2，盒子3}；
- 观测集合：V={红，白}；
- 状态序列和观测序列的长度T=5；
- HMM三要素已知，分别如下表示：
应用举例3要素
我们可以针对3要素来解析其相应含义：
初始概率分布 $\pi$ :选择第一个盒子的时候，1,2,3号盒子被选到的概率分别是：（0.2,0.4,0.4）；
状态转移概率分布 $A$ :先看第一行， $t$ 时刻选择到了1号盒子之时，那么 $t+1$ 时刻1,2,3号盒子被选到的概率分别是：（0.5,0.2,0.3）；再看第二行， $t$ 时刻选择到了2号盒子之时，那么 $t+1$ 时刻1,2,3号盒子被选到的概率分别是：（0.3,0.5,0.2）；第三行类似。
观测概率分布 $B$ :这个例子中该矩阵较为简单，每一行即为每个盒子中红白球数量所占的比例；

HMM的3个基本问题

当我们更加清楚了HMM的三要素之后，我们就有了HMM的3个基本问题。这三个问题的解答也是理解HMM的核心关键所在。

概率计算问题
给定模型 $\lambda = (A,B,\pi)$ 和观测序列 $O={o_1,o_2,...,o_T}$ ，计算模型 $\lambda$ 下观测序列 $O$ 出现的概率 $P(O| λ)$ 。我们也可以将该问题看做是衡量一个给定模型对观测序列 $O$ 的匹配好坏问题。
预测问题
即解码问题：已知模型 $\lambda = (A,B,\pi)$ 和观测序列 $O={o_1,o_2,...,o_T}$ ，求对给定观测序列条件概率 $P(I|O)$ 最大的状态序列 $I$ 。由已知的观测序列推测隐含的状态序列，相当于揭开该问题的神秘面纱。
学习问题
已知观测序列 $O={o_1,o_2,...,o_T}$ ，估计模型 $\lambda = (A,B,\pi)$ 的参数，使得在该模型下观测序列出现的概率 $P(O| λ)$ 最大。这个问题会由是否知道状态序列而分两种情况：
1.如果有一组已知的状态序列以及与之相对应的观测序列，我们称之为训练序列，那么此时这些序列就是用于训练HMM的模型，使得模型参数在训练集中表现最好。这就是监督学习中的训练阶段，可以很快地通过极大似然估计得到相应参数。
2.如果只有一组已知的观测序列，而不知道状态序列，那么这个时候就是非监督学习，智能通过EM算法来解决。下面的相关解法针对的就是不知道状态序列的情况。

概率计算问题的解法

关于该问题的解答，有三种方法，包括直接算法（即暴力算法），前向算法和后向算法。后面两种算法是理解HMM的算法重点。此问题的解答过程如果能够很好理解了，那么后面的两个问题在理解上将会比较简单。可以说理解这个问题是基础。

直接计算法
直接计算法的思想是这样的：按照概率公式，列举所有可能的长度为 $T$ 的状态序列 $I={i_1,i_2,...,i_T}$ ，求各个状态序列 $I$ 与观测序列的联合概率 $P(O,I|λ)$ ，然后对所有可能的 $P(O,I|λ)$ 求和，从而得到 $P(O|λ)$ 。

算法简单直接，具体步骤如下：

任意一个状态序列 $I={i_1,i_2,...,i_T}$ 的概率是： $P (I | λ) = π i 1 a i 1 i 2 a i 2 i 3 . . . a i T - 1 i T$ $P(I|\lambda) = \pi_{i_1}a_{i_1i_2}a_{i_2i_3}...a_{i_{T-1}i_{T}}$
对固定的状态序列 $I$ ，已知的观测序列 $O$ 的概率是： $P (O | I, λ) = b i 1 o 1 b i 2 o 2 . . . b i T o i T$ $P(O|I,\lambda) = b_{i_1o_1}b_{i_2o_2}...b_{i_{T}oi_{T}}$
已知的观测序列 $O和I$ 同时出现的联合概率是 $P(O,I|\lambda) = P(O|I,\lambda)P(I|\lambda)$ ,代入可得：
$P (O, I | λ) = π i 1 b i 1 o 1 a i 1 i 2 b i 2 o 2 . . . a i T - 1 i T b i T o i T$ $P(O,I|\lambda) = \pi_{i_1}b_{i_1o_1}a_{i_1i_2}b_{i_2o_2}...a_{i_{T-1}i_{T}}b_{i_{T}oi_{T}}$
对所有可能的状态序列 $I$ 求和，得到观测序列 $O$ 的概率 $P(O|\lambda)$ :
$P (O | λ) = \sum I P (O, I | λ) = \sum I π i 1 b i 1 o 1 a i 1 i 2 b i 2 o 2 . . . a i T - 1 i T b i T o i T$ $P(O|\lambda) = \sum_I P(O,I|\lambda) =\sum_{I} \pi_{i_1}b_{i_1o_1}a_{i_1i_2}b_{i_2o_2}...a_{i_{T-1}i_{T}}b_{i_{T}oi_{T}}$

针对最终的表达式，我们计算其时间复杂度：由于观测序列 $O$ 是确定的，我们只需考虑状态序列 $I$ ；枚举所有可能的状态序列 $I$ 的时间复杂度为 $O(N_T)$ ，再来看加和符号中有 $2T$ 个相乘的因子，因此，计算最终表达式的时间复杂度为 $O(TN_T)$ 。这个复杂度真的太高了。我们需要更加有效的计算算法。

前向算法
该算法没有直接计算相关的概率，而是定义了一个新的概率：前向概率。具体定义：给定 $\lambda$ ，定义到时刻 $t$ 部分观测序列为 $o_1,o_2…o_t$ 且状态为 $q_i$ 的概率为前向概率，记做：

α t (i) = P (o 1, o 2 \dots o t, i t = q i | λ)

$\alpha_t(i) = P(o_1,o_2…o_t,i_t=q_i|\lambda)$
有了该定义，就可以通过递推的方法最终得到观测序列概率

P(O|λ) $P(O|\lambda)$ 哦。挺屌的！让我们来看看具体流程：
1. 初值：

α1(i)=πibio1 $\alpha_1(i) = \pi_i b_{io_1}$
2. 递推：对于

t=1,2,...,T−1 $t = 1,2,...,T-1$ ,

α t + 1 (j) = (\sum i = 1 N α t (i) a i j) b j o t + 1

$\alpha_{t+1}(j) = (\sum_{i=1}^N \alpha_t(i)a_{ij}) b_{jo_{t+1}}$
3. 最终得到：

P(O|λ)=∑Ni=1αT(i) $P(O|\lambda) =\sum_{i=1}^N \alpha_T(i)$

流程只有三步，但是真正理解起来却不简单。
首先，根据定义，初值 $\alpha_1(i)$ 为在第一个时刻观测序列为 $o_1$ 且状态为 $q_i$ 的概率。结合观测序列是已知的，这理解起来不难。
递归的过程中较为重要的即为求和部分 $(\sum_{i=1}^N \alpha_t(i)a_{ij})$ ，求和内部的含义为在 $t$ 时刻状态为 $q_i$ 而 $t+1$ 时刻状态为 $q_j$ 的概率，针对 $i$ 求和即 $t+1$ 时刻状态为 $q_j$ 的概率（即表示不管 $t$ 时刻状态是什么， $t+1$ 时刻状态为 $q_j$ 的概率）。可以用下图来表示这个过程：
前向算法迭代
经过递推，我们可以得到时刻 $T$ 观测序列为 $o_1,o_2…o_T$ (即整个观测序列)且状态为 $q_i$ 的概率 $\alpha_T(i)$ ,对其求和即可求得最终我们需要的 $P(O|\lambda)$ 。

可以验证，前向概率算法的时间复杂度为 $O(TN^2)$ 。

即学即用，考察盒子球模型，计算观测向量 $O=$ “红白红”的出现概率。模型参数不变，如下：
应用举例3要素
步骤一，计算初值(已知信息：观测序列 $O=$ “红白红”)：

α 1 (1) = π 1 b 1 o 1 = 0.2 \times 0.5 = 0.1 α 1 (2) = π 2 b 2 o 1 = 0.4 \times 0.4 = 0.16 α 1 (3) = π 3 b 3 o 1 = 0.4 \times 0.7 = 0.28

$\alpha_1(1) = \pi_1 b_{1o_1} = 0.2 \times 0.5 = 0.1 \\ \alpha_1(2) = \pi_2 b_{2o_1} = 0.4 \times 0.4 = 0.16 \\ \alpha_1(3) = \pi_3 b_{3o_1} = 0.4 \times 0.7 = 0.28 \\$
步骤二：递推（t=1）:

α 2 (1) = (\sum j = 1 N α 1 (j) a j 1) b 1 o 2 = (0.1 * 0.5 + 0.16 * 0.3 + 0.28 * 0.2) * 0.5 = 0.077 α 2 (2) = (\sum j = 1 N α 1 (j) a j 2) b 2 o 2 = (0.1 * 0.2 + 0.16 * 0.5 + 0.28 * 0.3) * 0.6 = 0.1104 α 2 (3) = (\sum j = 1 N α 1 (j) a j 3) b 3 o 2 = (0.1 * 0.3 + 0.16 * 0.2 + 0.28 * 0.5) * 0.3 = 0.0606

$\alpha_2(1) = (\sum_{j=1}^N \alpha_1(j)a_{j1}) b_{1o_{2}} = (0.1*0.5+0.16*0.3+0.28*0.2)* 0.5 = 0.077\\ \alpha_2(2) = (\sum_{j=1}^N \alpha_1(j)a_{j2}) b_{2o_{2}} = (0.1*0.2+0.16*0.5+0.28*0.3)*0.6 = 0.1104 \\ \alpha_2(3) = (\sum_{j=1}^N \alpha_1(j)a_{j3}) b_{3o_{2}} = (0.1*0.3+0.16*0.2+0.28*0.5)*0.3 = 0.0606 \\$
递推（t=2):

α 3 (1) = (\sum j = 1 N α 2 (j) a j 1) b 1 o 3 = (0.077 * 0.5 + 0.1104 * 0.3 + 0.0606 * 0.2) * 0.5 = 0.04187 α 3 (2) = (\sum j = 1 N α 2 (j) a j 2) b 2 o 3 = (0.077 * 0.2 + 0.1104 * 0.5 + 0.0606 * 0.3) * 0.4 = 0.03551 α 3 (3) = (\sum j = 1 N α 2 (j) a j 3) b 3 o 3 = (0.077 * 0.3 + 0.1104 * 0.2 + 0.0606 * 0.5) * 0.7 = 0.05284

$\alpha_3(1) = (\sum_{j=1}^N \alpha_2(j)a_{j1}) b_{1o_{3}} = (0.077*0.5+0.1104*0.3+0.0606*0.2)* 0.5 = 0.04187\\ \alpha_3(2) = (\sum_{j=1}^N \alpha_2(j)a_{j2}) b_{2o_{3}} = (0.077*0.2+0.1104*0.5+0.0606*0.3)*0.4 = 0.03551 \\ \alpha_3(3) = (\sum_{j=1}^N \alpha_2(j)a_{j3}) b_{3o_{3}} = (0.077*0.3+0.1104*0.2+0.0606*0.5)*0.7 = 0.05284\\$
步骤三：最终：

P(O|λ)=∑Ni=1αT(i)=0.04187+0.03551+0.05284=0.13022 $P(O|\lambda) =\sum_{i=1}^N \alpha_T(i) = 0.04187+0.03551+0.05284 = 0.13022$

后向算法
实际上，使用前向算法已经能够很好解决概率计算问题了，但是为了更方便地解决接下来的问题，我们引入后向算法。和前向算法相似，该算法也定义了一个新的概率：后向概率。具体定义：给定模型 $\lambda$ ,定义在时刻 $t$ 的状态为 $q_i$ 的前提下，从 $t+1$ 到 $T$ 的部分观测序列为 $o_{t+1},o_{t+2},...,o_{T}$ 的概率为后向概率，记做：

β t (i) = P (o t + 1, o t + 2, . . ., o T | i t = q i, λ)

$\beta_t(i) = P(o_{t+1},o_{t+2},...,o_{T}|i_t = q_i,~\lambda)$
和前向算法相似，经过递推，就可以得到观测序列概率

P(O|λ) $P(O|\lambda)$ 。具体流程如下：
1. 初值：

βT(i)=1 $\beta_T(i) = 1$
2. 递推：对于

t=T−1,T−2,...,1 $t = T-1,T-2,...,1$ ,

β t (i) = \sum j = 1 N (a i j b j o t + 1 β i + 1 (j))

$\beta_{t}(i) = \sum_{j=1}^N (a_{ij} b_{jo_{t+1}} \beta_{i+1}(j))$
3. 最终得到：

P(O|λ)=∑Ni=1πibio1β1(i) $P(O|\lambda) =\sum_{i=1}^N \pi_i b_{io_1} \beta_1(i)$

递归：假设已知 $t$ 时刻的状态为 $q_i$ ，我需要得到 $o_{t+1},o_{t+2},...,o_{T}$ 出现的概率。首先，需要知道所有可能的在 $t+1$ 时刻的状态 $q_j$ (即需转化概率项 $a_{ij}$ );只有在 $t+1$ 时刻的状态 $q_j$ 的前提下，才可能得到 $t+1$ 时刻的观测 $o_{t+1}$ （即需观测概率项 $b_{jo_{t+1}}$ ）;得到了 $t+1$ 时刻的观测 $o_{t+1}$ ，乘上状态 $q_j$ 时 $o_{t+2},o_{t+3},...,o_{T}$ 出现的概率(即后向概率 $\beta_{i+1}(j))$ )，即得到了我们需要的概率值。
可以用下图来表示这个过程：
前向算法迭代

预测问题的解法

和概率计算问题不同的是，预测问题不仅仅存在一个解，而是需要从众多的解中选取一个最优解：找到一个最优的状态序列，在给定一个观测序列和已知模型参数的前提下。该问题的难点在于，如何选取一个衡量是否是最优解的准则？一个可能的衡量准则是在时刻 $t$ 选择最可能的状态 $i_t$ （individually most likely）。为了求解预测问题，我们定义变量：

γ t (i) = P (i t = q i | O, λ)

$\gamma_t(i) = P(i_t = q_i|O,\lambda)$
表示的是在模型

λ $\lambda$ 已知，观测序列

O $O$ 给定的条件下，时刻

t $t$ 状态为

qi $q_i$ 的概率。

γt(i) $\gamma_t(i)$ 可以使用前向-后项概率来表示：

γ t (i) = P ( i t = q i , O | λ ) P ( O | λ ) = α t ( i ) β t ( i ) \sum N i = 1 α t ( i ) β t ( i )

$\gamma_t(i) = \frac{P(i_t = q_i,O|\lambda)}{P(O|\lambda)} = \frac{\alpha_t(i)\beta_t(i)}{\sum_{i=1}^{N}\alpha_t(i)\beta_t(i)}$
因为根据前向概率与后向概率

αt(i)、βt(i) $\alpha_t(i)、\beta_t(i)$ 的定义，可以得到

P(it=qi,O|λ)=αt(i)βt(i) $P(i_t = q_i,O|\lambda) = \alpha_t(i)\beta_t(i)$ 。
另外，从等式中可以看出：

\sum i = 1 N γ t (i) = 1

$\sum_{i=1}^{N} \gamma_t(i) = 1$

使用 $\gamma_t(i)$ ，我们可以求解得到在衡量准则--时刻 $t$ 选择最可能的状态 $i_t$ （individually most likely）--的情况下，选择最优的解:

i t = argmax 1 \leq i \leq N [γ t (i)], 1 \leq t \leq T

$i_t = \operatorname*{argmax}_{1 \leq i \leq N}[\gamma_t(i)],~~~~1 \leq t \leq T$
即每个时刻

t $t$ 都选择使得

γt(i) $\gamma_t(i)$ 最大的那个状态。
这样的衡量准则并不是没有缺点的，因为它只考虑了单个状态的最优，而并没有考虑与之相关的下一个状态的情况（我们知道隐藏的状态序列是一条马尔科夫链，相邻两个状态之间是有关联的）。当某个状态转移概率

aij=0 $a_{ij} = 0$ 时，该衡量准则得出的状态序列很有可能是无效的。
为了对这个衡量准则做出修正，我们可以选择考虑了相邻两个状态的准则，但是更常见的情况是我们考虑的是将整个状态序列（

T $T$ 个状态同时考虑）都放进来考察，以此为基准建立衡量准则。即找到某一个最好的状态序列

I $I$ ，使得

P(I|O,λ) $P(I|O,\lambda)$ 最大。Viterbi算法即是一种满足要求的常用算法。

Viterbi算法
Viterbi算法实际上是利用动态规划的思想去解HMM，用动态规划求概率最大的路径（最优路径），这里的一条路径对应一个状态序列。在Viterbi算法中，定义变量：

δ t (i) = max i 1, . . ., i t - 1 P (i t = i, i t 1, . . ., i 1, o t, . . ., o 1 | λ)

$\delta_t(i) = \operatorname*{max}_{i_1,...,i_{t-1}}P(i_t = i,i_{t_1},...,i_1,o_t,...,o_1|\lambda)$
表示沿着一条路径

i1,...,it−1,it $i_{1},...,i_{t-1},i_t$ ,使得前

t $t$ 个观测序列为

ot,...,o1 $o_t,...,o_1$ ，且

t $t$ 时刻状态为

i $i$ 的最大概率。
通过递归，我们可以得到：

δ t + 1 (j) = [max i (δ t (i) α i j)] b j o t + 1

$\delta_{t+1}(j) =[\operatorname*{max}_i(\delta_t(i)\alpha_{ij})]b_{jo_{t+1}}$
为了能够跟踪状态每一步所取的值（最后需要求解的是状态序列），我们定义数组：

ψ t + 1 (j) = [argmax i (δ t (i) α i j)]

$\psi_{t+1}(j) = [\operatorname*{argmax}_i(\delta_t(i)\alpha_{ij})]$
完整的Viterbi算法流程如下：

初始化： $δ 1 (i) = π i b i o 1, 1 \leq i \leq N ψ 1 (i) = 0, 1 \leq i \leq N$ $\delta_1(i) = \pi_ib_{io_1},~~1 \leq i \leq N\\ \psi_{1}(i) =0,~~1 \leq i \leq N$
递归：
$δ t (j) = [max i (δ t - 1 (i) α i j)] b j o t, 2 \leq t \leq T, 1 \leq j \leq N ψ t (j) = argmax i [δ t - 1 (i) α i j], 2 \leq t \leq T, 1 \leq j \leq N$ $\delta_{t}(j) =[\operatorname*{max}_i(\delta_{t-1}(i)\alpha_{ij})]b_{jo_{t}},~~2 \leq t \leq T, 1 \leq j \leq N \\ \psi_{t}(j) = \operatorname*{argmax}_i[\delta_{t-1}(i)\alpha_{ij}],~~2 \leq t \leq T, 1 \leq j \leq N$
停止：
$p * = max i [δ T (i)] i * T = argmax i [δ T (i)]$ $p^* = \operatorname*{max}_i[\delta_T(i)] \\ i_T^* = \operatorname*{argmax}_i[\delta_T(i)]$
最优状态序列的查找：
$i * t = ψ t + 1 (i * t + 1)$ $i_t^* = \psi_{t+1}(i_{t+1}^*)$

学习问题的解法

在观测序列已知、状态序列不可知的情况下，我们采用EM算法来解决学习问题，HMM中的EM算法我们称之为Baum-Welch算法。
定义变量：

ε t (i, j) = P (i t = q i, i t + 1 = q j | O, λ)

$\varepsilon_t(i,j) = P(i_t =q_i, i_{t+1} = q_j | O,\lambda )$
表示的是在给定模型参数

λ $\lambda$ 与观测序列

O $O$ 的条件下，时刻

t $t$ 的状态为

qi $q_i$ 且时刻

t+1 $t+1$ 的状态为

qj $q_j$ 的概率。
而根据定义可以得到：

P (i t = q i, i t + 1 = q j, O | λ) = α t (i) a i j b j o t + 1 β t + 1 (j)

$P(i_t =q_i, i_{t+1} = q_j,O |\lambda ) = \alpha_t(i)a_{ij}b_{jo_{t+1}}\beta_{t+1}(j)$
由此可得：

ε t (i, j) = P ( i t = q i , i t + 1 = q j , O | λ ) P ( O | λ ) = α t ( i ) a i j b j o t + 1 β t + 1 ( j ) \sum N i = 1 \sum N j = 1 α t ( i ) a i j b j o t + 1 β t + 1 ( j )

$\varepsilon_t(i,j) =\frac{P(i_t =q_i, i_{t+1} = q_j,O |\lambda ) }{P(O|\lambda)} = \frac{\alpha_t(i)a_{ij}b_{jo_{t+1}}\beta_{t+1}(j)}{\sum_{i=1}^N \sum_{j=1}^N \alpha_t(i)a_{ij}b_{jo_{t+1}}\beta_{t+1}(j)}$
相关的变量在图表中的表示为：
Baum-Welch算法

之前我们就已经定义过

γt(i) $\gamma_t(i)$ ，表示的是在模型

λ $\lambda$ 已知，观测序列

O $O$ 给定的条件下，时刻

t $t$ 状态为

qi $q_i$ 的概率。如今，我们可以将

γt(i) $\gamma_t(i)$ 与

εt(i,j) $\varepsilon_t(i,j)$ 关联在一起：

γ t (i) = \sum j = 1 N ε t (i, j)

$\gamma_t(i) = \sum_{j=1}^N \varepsilon_t(i,j)$
如果我们将时刻

1≤t≤T−1 $1 \leq t \leq T-1$ 的

γt(i) $\gamma_t(i)$ 求和，可以得到一个新的变量，它用于衡量在

t=1到t=T−1 $t=1到t = T-1$ 这段时间内状态

qi $q_i$ 在状态转换过程中被访问到的次数的均值。类似的，我们时刻

1≤t≤T−1 $1 \leq t \leq T-1$ 的

εt(i) $\varepsilon_t(i)$ 求和，表示的含义是在

t=1到t=T−1 $t=1到t = T-1$ 这段时间内从状态

qi $q_i$ 被转换到状态

qj $q_j$ 在状态转换过程中被访问到的次数的均值。即：

使用上面定义的公式，我们可以给出一种HMM对当前参数进行更新的方法。假设初始的模型为

λ=(A，B，π) $\lambda = (A，B，\pi)$ ，那么更新的参数为：

π ¯ i = γ 1 (i), 1 \leq i \leq N a ¯ i j = \sum T - 1 t = 1 ε t ( i , j ) \sum T - 1 t = 1 γ t ( i ) 1 \leq i, j \leq N b ¯ j k = \sum T - 1 t = 1 , o t = v k γ t ( i ) \sum T - 1 t = 1 γ t ( i )

$\bar \pi_i = \gamma_1(i),~~1 \leq i \leq N \\ \bar a_{ij} = \frac{\sum_{t=1}^{T-1} \varepsilon_t(i,j)}{\sum_{t=1}^{T-1}\gamma_t(i) } ~~1 \leq i,j \leq N \\ \bar b_{jk} = \frac{\sum_{t=1,o_t = v_k }^{T-1}\gamma_t(i)}{\sum_{t=1}^{T-1}\gamma_t(i) }$
更新过后的模型参数

λ¯=(A¯，B¯，π¯) $\bar \lambda = (\bar A，\bar B，\bar \pi)$ 。Baum及其同事已经证明了，

P(O|λ¯)≥P(O|λ) $P(O|\bar \lambda) \geq P(O| \lambda)$ 。具体证明过程如下：
定义变量：

Q (λ, λ ¯) = \sum I [(l n P (O, I | λ)) P (O, I | λ ¯)]

$Q(\lambda, \bar \lambda) = \sum_I [(lnP(O,I|\lambda))P(O,I|\bar \lambda)]$
根据之前得到的等式：

P (O, I | λ) = π i 1 b i 1 o 1 a i 1 i 2 b i 2 o 2 . . . a i T - 1 i T b i T o i T

$P(O,I|\lambda) = \pi_{i_1}b_{i_1o_1}a_{i_1i_2}b_{i_2o_2}...a_{i_{T-1}i_{T}}b_{i_{T}oi_{T}}$
上式可写成：

Q (λ, λ ¯) = \sum I [(l n P (O, I | λ)) P (O, I | λ ¯)] = \sum I l n π i 1 P (O, I | λ ¯) + \sum I (\sum t = 1 T - 1 l n a i t i t + 1) P (O, I | λ ¯) + \sum I (\sum t = 1 T l n b i t o t) P (O, I | λ ¯)

$Q(\lambda, \bar \lambda) = \sum_I [(lnP(O,I|\lambda))P(O,I|\bar \lambda)] = \sum_I ln\pi_{i_1}P(O,I|\bar \lambda)+\sum_I (\sum_{t=1}^{T-1}ln a_{i_ti_{t+1}})P(O,I|\bar \lambda)+\sum_I (\sum_{t=1}^{T}ln b_{i_to_{t}})P(O,I|\bar \lambda)$
极大化

Q(λ,λ¯) $Q(\lambda, \bar \lambda)$ 所得的参数

λ¯ $\bar \lambda$ ,可推出：

max λ ¯ [Q (λ, λ ¯)] ⟹ P (O | λ ¯) \geq P (O | λ)

$\operatorname*{max}_{\bar \lambda}[Q(\lambda, \bar \lambda)] \Longrightarrow P(O|\bar \lambda) \geq P(O| \lambda)$
由于这三个参数分别位于三个项中，可分别极大化。领用拉格朗日乘子法即可分别求得三个参数的最优解表达式，具体表达式上面已经推导出，这里不再复述。值得注意的是，由Baum-Welch算法最终的到的最优参数结果并不是全局最优解，而只是局部最优解。

参考文献：
A Tutorial on Learning With Bayesian Networks,David Heckerman, 1996