回忆上次所提到的，隐马尔科夫模型引出的三个基本问题：
1)概率计算问题：给定模型参数$lambda=A,B,pi)$ 以及某个观测序列$O=0_{1},…,0_{T})$, 如何高效地计算出概率$POmid lambda)$?
2)学习问题：已知某个观测序列$O=o_{1},…,o_{T})$, 如何得到参数$lambda=A,B,pi)$使得似然函数$POmidlambda)$极大，或者至少尽量大?
3)预测问题：预测问题，也成为解码问题Decoding Problem)，也就是已知观测序列$O=o_{1},…,o_{T})$, 以及参数$lambda=A,B,pi)$, 求不可观测序列$I$使得概率: egin{equation}PImid O,lambda)end{equation}极大。
这一次就总结一下后面两个问题的算法。
1.学习算法：Baum-Welch算法
将Baum-Welch算法就是将EM算法应用于HMM的参数学习。这时候我们假设某带未知参数$lambda=A,B,pi)$有一可观测序列$O=o_{1},…,o_{T})$，现在我们开始计算E步。
在$E$步中，假设我们第s)次迭代已经有某个参数$lambda^{s)}=A^{s)},B^{s)},pi^{s)})$, 现在我们要计算的是条件期望：
egin{equation}egin{split}&E_{I}log PO,Imid lambda)mid O,lambda^{s)})
ewline =&sum_{I}PImid O,lambda^{s)})log PO,Imid lambda)
ewline =&sum_{I}frac{PO,Imid lambda^{s)})}{POmid lambda^{s)})}log PO,Imid lambda)end{split}end{equation}
由于$POmid lambda^{s)})$为常数，求上述期望的极小值等价于求$POmid lambda^{s)})cdot E_{I}log PO,Imid lambda)mid O,lambda^{s)})$之极小值，这时为了方便起见我们令函数$Qlambda,lambda^{s)}) riangleq POmid lambda^{s)})cdot E_{I}log PO,Imid lambda)mid O,lambda^{s)})=sum_{I}PO,Imid lambda^{s)})log PO,Imid lambda)$, 而不是直接将$Q$定义为条件期望$E_{I}log PO,Imid lambda)mid O,lambda^{s)})$。
注意到，我们直接计算概率：
$$PO,Imid lambda)=prod_{t=1}^{T}B_{o_{t}i_{t}}cdotprod_{t=1}^{T-1}A_{i_{t+1}i_{t}}cdot pi_{i_{1}},$$
从而：
egin{equation}log PO,Imidlambda)=sum_{t=1}^{T}log B_{o_{t}i_{t}}+sum_{t}^{T-1}log A_{i_{t+1}i_{t}}+logpi_{i_{1}},end{equation}
结合定义我们立即得到：
egin{equation}Qlambda,lambda^{s)})=sum_{I}sum_{t=1}^{T}PO,Imidlambda^{s)})log B_{o_{t}i_{t}}+sum_{I}sum_{t=1}^{T-1}PO,Imidlambda^{s)})+sum_{I}PO,Imid lambda^{s)})logpi_{i_{1}}.end{equation}
计算上式第一项：
egin{equation}egin{split}&sum_{I}sum_{t=1}^{T}PO,Imid lambda^{s)})log B_{o_{t}i_{t}}
ewline =&sum_{t=1}^{T}sum_{k=1}^{K}sum_{I:i_{t}=k}PO,Imid lambda^{s)})log B_{o_{t}k}
ewline =&sum_{t=1}^{T}sum_{k=1}^{K}PO,i_{t}=kmidlambda^{s)})log B_{o_{t}k}.end{split}end{equation}
类似地，第二，第三项分别为$sum_{k,l}sum_{t=1}^{T-1}lbrace PO,i_{t}=k,i_{t+1}=lmidlambda^{s)})bracelog A_{lk},$ $sum_{k=1}^{K}PO,i_{1}=kmidlambda^{s)})logpi_{k},$
所以我们自然有：
egin{equation}egin{split}Qlambda,lambda^{s)})=&sum_{t=1}^{T}sum_{k=1}^{K}PO,i_{t}=kmidlambda^{s)})log B_{o_{t}k}+sum_{k,l}sum_{t=1}^{T-1}lbrace PO,i_{t}=k,i_{t+1}=lmidlambda^{s)})bracelog A_{lk}+
ewline &sum_{k=1}^{K}PO,i_{1}=kmidlambda^{s)})logpi_{k},end{split}end{equation}
现在E步完成。
M步中，我们很容易得到当$Qlambda,lambda^{s)})$最大的时候，有：
egin{equation}A_{lk}=frac{sum_{t=1}^{T-1}PO,i_{t}=k,i_{t+1}=lmid lambda^{s)})}{sum_{t=1}^{T-1}PO,i_{t}=kmid lambda^{s)})}end{equation}
egin{equation}B_{alpha k}=frac{sum_{t:o_{t}=alpha}PO,i_{t}=kmidlambda^{s)})}{sum_{t=1}^{T}PO,i_{t}=kmidlambda^{s)})}end{equation}
egin{equation}pi_{i}=frac{PO,i_{1}=imid lambda^{s)})}{POmid lambda^{s)})}end{equation}
算法一（Baum-Welch算法）
输入：观测序列$O=o_{1},…,o_{T})$；
输出：隐马尔科夫模型参数$lambda=A,B,lambda)$
Step1. 初始化参数$lambda^{0)}=A^{0)},B^{0)},lambda^{0)})$;
Step2. 对$s=1,…$不断执行如下操作，直到停止条件满足：
1) 对$t=1,…,T$,$k=1,…K$递归计算：
$alpha_{t,k}^{s)}=B_{o_{1}k}^{s)}pi_{k}^{s)}$ 当$t=1$,
$alpha_{t,k}^{s)}=sum_{l=1}^{K}B_{o_{t}l}^{s)}A_{lk}^{s)}alpha_{t-1,k}^{s)}$当$t>1$
2) 对$t=T,T-1,…,1$,$k=1,…,K$递归计算：
$eta_{t,k}^{s)}=1$ 当$t=T$,
$eta_{t,k}^{s)}=sum_{l=1}^{K}eta_{t+1,l}^{s)}B_{o_{t+1}l}^{s)}A_{lk}^{s)}$
3) 计算概率：
对$t=1,…,T-1$, $k,l=1,…,K$:
$$PO,i_{t}=k,i_{t+1}=lmid lambda^{s)})=eta_{t+1,l}^{s)}B_{o_{t+1}l}^{s)}A_{lk}^{s)}alpha_{t,k}^{s)}$$
对$t=1,…,T$,$k=1,…,K$:
$$PO,i_{t}=kmidlambda^{s)})=eta_{t,k}^{s)}alpha_{t,k}^{s)}$$
计算：
$$POmidlambda^{s)})=sum_{k=1}^{K}alpha_{T,k}^{s)}$$
4) 计算：
egin{equation}A_{lk}^{s+1)}=frac{sum_{t=1}^{T-1}PO,i_{t}=k,i_{t+1}=lmid lambda^{s)})}{sum_{t=1}^{T-1}PO,i_{t}=kmid lambda^{s)})}end{equation}
egin{equation}B_{alpha k}^{s+1)}=frac{sum_{t:o_{t}=alpha}PO,i_{t}=kmidlambda^{s)})}{sum_{t=1}^{T}PO,i_{t}=kmidlambda^{s)})}end{equation}
egin{equation}pi_{i}^{s+1)}=frac{PO,i_{1}=imid lambda^{s)})}{POmid lambda^{s)})}end{equation}
Step3 输出最终得到的参数$lambda^{S)}=A^{S)},B^{S)},pi^{S)})$, 其中$S$为学习步长。
2.预测问题：维特比算法
维特比算法Viterbi Algorithm)就是用动态规划法求最短路径$I$使得$PImid O,lambda)$极大等价于$PO,I)$极大)。首先我们观察一个事实是，如果不可观测序列（也称状态路径）$I=i_{1},…,i_{T})$是一个最优路径的话，那么对于任意$t=1,…,T$，前$t$个状态组成的路径$I_{t}=i_{1},…,i_{t})$也必定是一个固定$t$时刻的状态下的最优路径，具体来说就是：
egin{equation}i_{1},…,i_{t})=mathop{ ext{argmax}}limits_{lbracei^{prime}_{1},…,i^{prime}_{t})mid i^{prime}_{s}inlbrace 1,…,Kbrace, i_{t}^{prime}=i_{t}brace}PO,i_{1}^{prime},…,i_{t}^{prime},i_{t+1},…,i_{T}midlambda).end{equation}
注意到对于满足$t_{t}^{prime}=i_{t}$之序列我们又有： egin{equation}PO,i_{1}^{prime},…,i_{t}^{prime},i_{t+1},…,i_{T}midlambda)=Pi_{t+1},…,i_{T},o_{t+1},…,o_{T}mid i_{t})Po_{1},…,o_{t},i_{1}^{prime},…,i_{t}^{prime}midlambda),end{equation}
所以13)等价于：
egin{equation}i_{1},…,i_{t})=mathop{ ext{argmax}}limits_{lbracei^{prime}_{1},…,i^{prime}_{t})mid i^{prime}_{s}inlbrace 1,…,Kbrace, i_{t}^{prime}=i_{t}brace}Po_{1},…,o_{t},i_{1}^{prime},…,i_{t}^{prime}midlambda).end{equation}
15)可以启发我们设计一个动态规划算法如下：
我们现在想递归地求：
egin{equation}delta_{t,i} riangleq mathop{max}limits_{i_{1},…,i_{t-1})}Po_{1},…,o_{t},i_{1},…,i_{t-1},i_{t}=imidlambda)end{equation}
以及： egin{equation}psi_{t,i} riangleq mathop{ ext{argmax}}limits_{i_{1},…,i_{t-1})}Po_{1},…,o_{t},i_{1},…,i_{t-1},i_{t}=imidlambda))_{t-1},end{equation}
注意的这里$mathop{ ext{argmax}}limits_{i_{1},…,i_{t-1})}Po_{1},…,o_{t},i_{1},…,i_{t-1},i_{t}=imidlambda)$是一个长度为$t-1$的状态序列（路径），而上面公式的下标表示取该序列的最后一个状态，也就是路径终点。上面的定义式中$delta_{t,i}$表示前$t$步最优概率值，当固定第$t$步状态为$i$的情况下；$psi_{t,i}$表示该最优解的倒数第二步的状态，记录该状态以便于回溯。
我们很容易得到递推关系：
egin{equation}delta_{t+1,i}=max_{j} B_{o_{t+1}i}A_{ij}delta_{t,j}end{equation}
egin{equation}psi_{t+1,i}=mathop{ ext{argmax}}limits_{j}A_{ij}delta_{t,j}end{equation}
如果以此由上式递推得到$delta$,$psi$, 我们立即可以得到最优路径$I^{ast}=i^{ast}_{1},…,i^{ast}_{T})$：
egin{equation}i^{ast}_{T}=mathop{ ext{argmax}}limits_{j}delta_{T,j},end{equation}
egin{equation}i^{ast}_{t}=psi_{t+1,i^{ast}_{t+1}}t=T-1,…,1),end{equation}
综上我们总结一下：
算法二（维特比算法）：
输入：观测序列$O=o_{1},…,o_{T})$, 参数$lambda=A,B,pi)$;
输出：预测最优路径$I^{ast}=i^{ast}_{1},…,i^{ast}_{T})$.
Step1. 初始化：$delta_{1,i}=B_{o_{1},i}pi_{i}$, $psi_{1,i}=0$
Step2. 对$t=2,…T$, $i=1,…,K$递推得到：
$$delta_{t,i}=max_{j}B_{o_{t}i}A_{ij}delta_{t-1,j},$$
$$psi_{t,i}=mathop{ ext{argmax}}limits_{j}A_{ij}delta_{t-1,j}$$
Step3. 回溯得到最优路径：
$$i^{ast}_{T}=mathop{ ext{argmax}}limits_{i}delta_{T,i}$$,
对$t=T-1,…,1$:
$$i^{ast}_{t}=psi_{t+1,i^{ast}_{t+1}}$$,
输出$I^{ast}=i^{ast}_{1},…,i^{ast}_{T})$。