隐马尔科夫模型（二）

回忆上次所提到的，隐马尔科夫模型引出的三个基本问题：

1)概率计算问题：给定模型参数$lambda=(A,B,pi)$ 以及某个观测序列$O=(0_{1},…,0_{T})$, 如何高效地计算出概率$P(Omid lambda)$?

2)学习问题：已知某个观测序列$O=(o_{1},…,o_{T})$, 如何得到参数$lambda=(A,B,pi)$使得似然函数$P(Omidlambda)$极大，或者至少尽量大?

3)预测问题：预测问题，也成为解码问题(Decoding Problem)，也就是已知观测序列$O=(o_{1},…,o_{T})$, 以及参数$lambda=(A,B,pi)$, 求不可观测序列$I$使得概率: egin{equation}P(Imid 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 P(O,Imid lambda)mid O,lambda^{(s)})
ewline =&sum_{I}P(Imid O,lambda^{(s)})log P(O,Imid lambda)
ewline =&sum_{I}frac{P(O,Imid lambda^{(s)})}{P(Omid lambda^{(s)})}log P(O,Imid lambda)end{split}end{equation}

由于$P(Omid lambda^{(s)})$为常数，求上述期望的极小值等价于求$P(Omid lambda^{(s)})cdot E_{I}(log P(O,Imid lambda)mid O,lambda^{(s)})$之极小值，这时为了方便起见我们令函数$Q(lambda,lambda^{(s)}) riangleq P(Omid lambda^{(s)})cdot E_{I}(log P(O,Imid lambda)mid O,lambda^{(s)})=sum_{I}P(O,Imid lambda^{(s)})log P(O,Imid lambda)$, 而不是直接将$Q$定义为条件期望$E_{I}(log P(O,Imid lambda)mid O,lambda^{(s)})$。

注意到，我们直接计算概率：

$$P(O,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 P(O,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}Q(lambda,lambda^{(s)})=sum_{I}sum_{t=1}^{T}P(O,Imidlambda^{(s)})log B_{o_{t}i_{t}}+sum_{I}sum_{t=1}^{T-1}P(O,Imidlambda^{(s)})+sum_{I}P(O,Imid lambda^{(s)})logpi_{i_{1}}.end{equation}

计算上式第一项：

egin{equation}egin{split}&sum_{I}sum_{t=1}^{T}P(O,Imid lambda^{(s)})log B_{o_{t}i_{t}}
ewline =&sum_{t=1}^{T}sum_{k=1}^{K}sum_{I:i_{t}=k}P(O,Imid lambda^{(s)})log B_{o_{t}k}
ewline =&sum_{t=1}^{T}sum_{k=1}^{K}P(O,i_{t}=kmidlambda^{(s)})log B_{o_{t}k}.end{split}end{equation}

类似地，第二，第三项分别为$sum_{k,l}sum_{t=1}^{T-1}lbrace P(O,i_{t}=k,i_{t+1}=lmidlambda^{(s)})bracelog A_{lk},$ $sum_{k=1}^{K}P(O,i_{1}=kmidlambda^{(s)})logpi_{k},$

所以我们自然有：

egin{equation}egin{split}Q(lambda,lambda^{(s)})=&sum_{t=1}^{T}sum_{k=1}^{K}P(O,i_{t}=kmidlambda^{(s)})log B_{o_{t}k}+sum_{k,l}sum_{t=1}^{T-1}lbrace P(O,i_{t}=k,i_{t+1}=lmidlambda^{(s)})bracelog A_{lk}+
ewline &sum_{k=1}^{K}P(O,i_{1}=kmidlambda^{(s)})logpi_{k},end{split}end{equation}

现在E步完成。

M步中，我们很容易得到当$Q(lambda,lambda^{(s)})$最大的时候，有：

egin{equation}A_{lk}=frac{sum_{t=1}^{T-1}P(O,i_{t}=k,i_{t+1}=lmid lambda^{(s)})}{sum_{t=1}^{T-1}P(O,i_{t}=kmid lambda^{(s)})}end{equation}

egin{equation}B_{alpha k}=frac{sum_{t:o_{t}=alpha}P(O,i_{t}=kmidlambda^{(s)})}{sum_{t=1}^{T}P(O,i_{t}=kmidlambda^{(s)})}end{equation}

egin{equation}pi_{i}=frac{P(O,i_{1}=imid lambda^{(s)})}{P(Omid 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$:

$$P(O,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$:

$$P(O,i_{t}=kmidlambda^{(s)})=eta_{t,k}^{(s)}alpha_{t,k}^{(s)}$$

计算：

$$P(Omidlambda^{(s)})=sum_{k=1}^{K}alpha_{T,k}^{(s)}$$

4) 计算：

egin{equation}A_{lk}^{(s+1)}=frac{sum_{t=1}^{T-1}P(O,i_{t}=k,i_{t+1}=lmid lambda^{(s)})}{sum_{t=1}^{T-1}P(O,i_{t}=kmid lambda^{(s)})}end{equation}

egin{equation}B_{alpha k}^{(s+1)}=frac{sum_{t:o_{t}=alpha}P(O,i_{t}=kmidlambda^{(s)})}{sum_{t=1}^{T}P(O,i_{t}=kmidlambda^{(s)})}end{equation}

egin{equation}pi_{i}^{(s+1)}=frac{P(O,i_{1}=imid lambda^{(s)})}{P(Omid lambda^{(s)})}end{equation}

Step3 输出最终得到的参数$lambda^{(S)}=(A^{(S)},B^{(S)},pi^{(S)})$, 其中$S$为学习步长。

2.预测问题：维特比算法

维特比算法(Viterbi Algorithm)就是用动态规划法求最短路径$I$使得$P(Imid O,lambda)$极大(等价于$P(O,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_{lbrace(i^{prime}_{1},…,i^{prime}_{t})mid i^{prime}_{s}inlbrace 1,…,Kbrace, i_{t}^{prime}=i_{t}brace}P(O,i_{1}^{prime},…,i_{t}^{prime},i_{t+1},…,i_{T}midlambda).end{equation}

注意到对于满足$t_{t}^{prime}=i_{t}$之序列我们又有： egin{equation}P(O,i_{1}^{prime},…,i_{t}^{prime},i_{t+1},…,i_{T}midlambda)=P(i_{t+1},…,i_{T},o_{t+1},…,o_{T}mid i_{t})P(o_{1},…,o_{t},i_{1}^{prime},…,i_{t}^{prime}midlambda),end{equation}

所以(13)等价于：

egin{equation}(i_{1},…,i_{t})=mathop{ ext{argmax}}limits_{lbrace(i^{prime}_{1},…,i^{prime}_{t})mid i^{prime}_{s}inlbrace 1,…,Kbrace, i_{t}^{prime}=i_{t}brace}P(o_{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})}P(o_{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})}P(o_{1},…,o_{t},i_{1},…,i_{t-1},i_{t}=imidlambda))_{t-1},end{equation}

注意的这里$mathop{ ext{argmax}}limits_{(i_{1},…,i_{t-1})}P(o_{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$递推得到：