本文共 22722 字，大约阅读时间需要 75 分钟。

此文章主要是结合哔站shuhuai008大佬的白板推导视频：

全部笔记的汇总贴：

一、概述

（一）背景

概率图分为有向（Bayesian Network）和无向（Markov Random Field，Markov Network），加上“时间”，则是动态模型（Dynamic Model），包括：HMM； Kalman Filter；Particle Filter。其中，隐马尔可夫模型（HMM）时离散的，另外两种是连续的。

$$DynamicModel\{\begin{array}{c}离散\to HMM\\ 连续\to \{\begin{array}{c}线性\to KalmanFilter\\ 非线性\to ParticleFilter\end{array}\end{array}$$

（二）HMM的概率图模型

• $t$代表时刻，阴影部分为观测变量序列$O$，非阴影部分为状态变量序列$I$

隐马尔可夫模型的参数用$\lambda$表达：$\lambda =(\pi ,A,B)$；其中$\pi$为初始概率分布，是一个多维向量；$A$为状态转移矩阵；$B$为发射矩阵：

$$\begin{gathered} \pi =({\pi }_1,{\pi }_2,\cdots ,{\pi }_N),\sum _{i=1}^N{\pi }_i=1 \\ A=[a_{ij}],a_{ij}=P(i_{t+1}=q_j|i_t=q_i) \\ B=[b_j(k)],b_j(k)=P(o_t=v_k|i_t=q_i) \end{gathered}$$

观测变量取值的集合为$V$，状态变量取值的集合为$Q$：

O = o 1 , o 2 , ⋯   , o t , ⋯ → V = { v 1 , v 2 , ⋯   , v m } I = i 1 , i 2 , ⋯   , i t , ⋯ → Q = { q 1 , q 2 , ⋯   , q n } O=o_{1},o_{2},\cdots ,o_{t},\cdots\rightarrow V=\left \{v_{1},v_{2},\cdots ,v_{m}\right \}\\ I=i_{1},i_{2},\cdots ,i_{t},\cdots\rightarrow Q=\left \{q_{1},q_{2},\cdots ,q_{n}\right \} O=o1​,o2​,⋯,ot​,⋯→V={ v1​,v2​,⋯,vm​}I=i1​,i2​,⋯,it​,⋯→Q={ q1​,q2​,⋯,qn​}

（三）两个假设

1、齐次马尔可夫假设

任意时刻的状态只依赖于前一时刻的状态，即：

$$P(i_{t+1}|i_t,i_{t-1},\cdots ,i_1,o_t,o_{t-1},\cdots ,o_1)=P(i_{t+1}|i_t)$$

2、观察独立假设

任意时刻的观测只依赖于当前时刻的状态，即：

$$P(o_t|i_t,i_{t-1},\cdots ,i_1,o_{t-1},\cdots ,o_1)=P(o_t|i_t)$$

（四）三个问题

1、Evaluation

已知模型的参数$\lambda =(\pi ,A,B)$，计算某个观测序列发生的概率，即求：

$$P(O|\lambda )\to 前向后向$$

2、Learning

已知观测序列，使用EM算法求参数$\lambda$：

$${\lambda }_{MLE}=\underset{\lambda }{\mathrm{argmax}}P(O|\lambda )$$

3、Decoding

已知观测序列$O$和参数$\lambda$，求使概率$P(I|O)$最大的状态序列$I$，即：

$$\hat{I}=\underset{I}{\mathrm{argmax}}P(I|O)$$

$$\{\begin{array}{c}预测\to P(i_{(t+1)}|o_1,o_2,\cdots ,o_t)\\ 滤波\to P(i_t|o_1,o_2,\cdots ,o_t)\end{array}$$

二、Evaluation问题

在隐马尔可夫模型，Evaluation问题是在已知参数$\lambda$的情况下，求解$P(O|\lambda )$：

$$P(O|\lambda )=\sum _{I}P(I,O|\lambda )=\sum _{I}P(O|I,\lambda )P(I|\lambda )$$

对于$P(I|\lambda )$，有：

$$P(I|\lambda )=P(i_1,i_2,\cdots ,i_T|\lambda )=P(i_T|i_1,i_2,\cdots ,i_{T-1},\lambda )\cdot P(i_1,i_2,\cdots ,i_{T-1}|\lambda )$$

根据齐次Markov假设：

$$P(i_t|i_1,i_2,\cdots ,i_{t-1},\lambda )=P(i_t|i_{t-1})=a_{i_{t-1}{i}_t}$$

所以：

$$P(I|\lambda )=\pi (i_1)\prod _{t=2}^T{a}_{i_{t-1}{i}_t}$$

对于上式中的$P(O|I,\lambda )$，有：

$$P(O|I,\lambda )=\prod _{i=1}^T{b}_{i_t}(o_t)$$

因此可得：

$$\begin{gathered} P(O|\lambda )=\sum _I\pi (i_1)\prod _{t=2}^T{a}_{i_{t-1}{i}_t}\prod _{i=1}^T{b}_{i_t}(o_t) \\ =\underset{O(N^T)}{\sum _{i_1}\sum _{i_2}\cdots \sum _{i_T}}\pi (i_1)\prod _{t=2}^T{a}_{i_{t-1}{i}_t}\prod _{i=1}^T{b}_{i_t}(o_t) \end{gathered}$$

（一）前向算法

显然，复杂度太高，为$O(N^T)$，所以我们记：

$${\alpha }_t(i)=P(o_1,o_2,\cdots ,o_t,i_t=q_i|\lambda )$$

所以：

$${\alpha }_T(i)=P(O,i_T=q_i|\lambda )$$

可以得到：

$$P(O|\lambda )=\sum _{i=1}^{N}P(O,i_t=q_i|\lambda )=\sum _{i=1}^N{\alpha }_T(i)$$

对于${\alpha }_{t+1}(j)$：

$$\begin{gathered} {\alpha }_{t+1}(j)=P(o_1,\cdots ,o_t,o_{t+1},i_{t+1}=q_j|\lambda ) \\ =\sum _{i=1}^{N}P(o_1,\cdots ,o_t,o_{t+1},i_{t+1}=q_j,i_t=q_i|\lambda ) \\ =\sum _{i=1}^{N}P(o_{t+1}|o_1,\cdots ,o_t,i_t=q_i,i_{t+1}=q_j,\lambda )P(o_1,\cdots ,o_t,i_t=q_i,i_{t+1}=q_j|\lambda ) \\ =\sum _{i=1}^{N}P(o_{t+1}|i_{t+1}=q_j,\lambda )P(o_1,\cdots ,o_t,i_t=q_i,i_{t+1}=q_j|\lambda ) \\ =\sum _{i=1}^N{b}_j(o_{t+1})P(i_{t+1}=q_j|o_1,\cdots ,o_t,i_t=q_i,\lambda )P(o_1,\cdots ,o_t,i_t=q_i|\lambda ) \\ =\sum _{i=1}^N{b}_j(o_{t+1})P(i_{t+1}=q_j|i_t=q_i,\lambda ){\alpha }_t(i) \\ =\sum _{i=1}^N{b}_j(o_{t+1})a_{ij}{\alpha }_t(i) \end{gathered}$$

这个算法叫做前向算法，其复杂度为$O(T{N}^2)$，利用两个假设得到了一个递推公式。

（二）后向算法

记：

$$\begin{gathered} {\beta }_t(i)=P(o_{t+1},\cdots ,o_T|i_t=q_i,\lambda ) \\ ⋮ \\ {\beta }_1(i)=P(o_2,\cdots ,o_T|i_t=q_i,\lambda ) \end{gathered}$$

所以：

$$\begin{gathered} P(O|\lambda )=P(o_1,\cdots ,o_T|\lambda ) \\ =\sum _{i=1}^{N}P(o_1,\cdots ,o_T,i_1=q_i|\lambda ) \\ =\sum _{i=1}^{N}P(o_1,\cdots ,o_T|i_1=q_i,\lambda )\underset{{\pi }_i}{P(i_1=q_i|\lambda )} \\ =\sum _{i=1}^{N}P(o_1|o_2,\cdots ,o_T,i_1=q_i,\lambda )\underset{{\beta }_1(i)}{P(o_2,\cdots ,o_T|i_1=q_i,\lambda )}{\pi }_i \\ =\sum _{i=1}^{N}P(o_1|i_1=q_i,\lambda ){\beta }_1(i){\pi }_i \\ =\sum _{i=1}^N{b}_i(o_1){\beta }_1(i){\pi }_i \end{gathered}$$

因此如果我们能找到${\beta }_t(i)$到${\beta }_{t+1}(j)$的递推式，就可以由通过递推得到${\beta }_1(i)$，从而计算$P(O|\lambda )$：

$$\begin{gathered} {\beta }_t(i)=P(o_{t+1},\cdots ,o_T|i_t=q_i,\lambda ) \\ =\sum _{j=1}^{N}P(o_{t+1},\cdots ,o_T,i_{t+1}=q_j|i_t=q_i,\lambda ) \\ =\sum _{j=1}^{N}P(o_{t+1},\cdots ,o_T|i_{t+1}=q_j,i_t=q_i,\lambda )P(i_{t+1}=q_j|i_t=q_i,\lambda ) \\ =\sum _{j=1}^{N}P(o_{t+1},\cdots ,o_T|i_{t+1}=q_j,\lambda )a_{ij} \\ =\sum _{j=1}^{N}P(o_{t+1}|o_{t+2},\cdots ,o_T,i_{t+1}=q_j,\lambda )P(o_{t+2},\cdots ,o_T|i_{t+1}=q_j,\lambda )a_{ij} \\ =\sum _{j=1}^{N}P(o_{t+1}|i_{t+1}=q_j,\lambda ){\beta }_{t+1}(j)a_{ij} \\ =\sum _{j=1}^N{b}_j(o_{t+1})a_{ij}{\beta }_{t+1}(j) \end{gathered}$$

上式中红色的一步变换利用了概率图模型中有向图head to tail结构的性质，这种结构满足：

$$\begin{gathered} A\to B\to C \\ headtotail \end{gathered}$$
$$A\perp C|B\iff 若B被观测，则路径被阻塞。$$

这是后向算法，其复杂度也为$O(T{N}^2)$。

三、Learning问题

Learning问题的目标是求解求参数$\lambda$，使用的是Baum Welch算法（也就是EM算法，在EM算法之前）。

EM算法的迭代公式如下：

$${\theta }^{(t+1)}=\underset{\theta }{\mathrm{argmax}}{\int }_{Z}logP(X,Z|\theta )\cdot P(Z|X,{\theta }^{(t)})\mathrm{d}z$$

在隐马尔可夫模型中，隐变量$Z$即为$I$，观测变量$X$即为$O$，参数$\theta$即为$\lambda$，因此隐马尔可夫模型的EM算法迭代公式写为：

$${\lambda }^{(t+1)}=\underset{\lambda }{\mathrm{argmax}}\sum _{I}logP(O,I|\lambda )\cdot P(I|O,{\lambda }^{(t)})$$

其中$P(I|O,{\lambda }^{(t)})=\frac{P(O,I|{\lambda }^{(t)})}{P(O|{\lambda }^{(t)})}$，由于在Learning问题中，观测序列$O$是已知的，所以$P(O|{\lambda }^{(t)})$是个常数，迭代公式可以写为：

$${\lambda }^{(t+1)}=\underset{\lambda }{\mathrm{argmax}}\sum _{I}logP(O,I|\lambda )\cdot P(O,I|{\lambda }^{(t)})$$

根据之前的计算对$Q$函数进行整理：

$$\begin{gathered} Q(\lambda ,{\lambda }^{(t)})=\sum _{I}logP(O,I|\lambda )\cdot P(O,I|{\lambda }^{(t)}) \\ =\sum _I[log\pi (i_1)\prod _{t=2}^T{a}_{i_{t-1}{i}_t}\prod _{i=1}^T{b}_{i_t}(o_t)\cdot P(O,I|{\lambda }^{(t)})] \\ =\sum _I[(log\pi (i_1)+\sum _{t=2}^{T}log{a}_{i_{t-1}{i}_t}+\sum _{i=1}^{T}log{b}_{i_t}(o_t))\cdot P(O,I|{\lambda }^{(t)})] \end{gathered}$$

接下来以求解${\pi }^{(t+1)}$为例展示迭代的过程：

$$\begin{gathered} {\pi }^{(t+1)}=\underset{\pi }{\mathrm{argmax}}Q(\lambda ,{\lambda }^{(t)}) \\ =\underset{\pi }{\mathrm{argmax}}\sum _{I}log\pi (i_1)\cdot P(O,I|{\lambda }^{(t)}) \\ =\underset{\pi }{\mathrm{argmax}}\sum _{i_1}\sum _{i_2}\cdots \sum _{i_T}log\pi (i_1)\cdot P(O,i_1,i_2,\cdots ,i_T|{\lambda }^{(t)}) \\ =\underset{\pi }{\mathrm{argmax}}\sum _{i_1}log\pi (i_1)\cdot P(O,i_1|{\lambda }^{(t)}) \\ =\underset{\pi }{\mathrm{argmax}}\sum _{i=1}^{N}log{\pi }_i\cdot P(O,i_1=q_i|{\lambda }^{(t)}) \end{gathered}$$

结合对$\pi$的约束${\sum }_{i=1}^N{\pi }_i=1$，构建拉格朗日函数：

$$L(\pi ,\eta )=\sum _{i=1}^{N}log{\pi }_i\cdot P(O,i_1=q_i|{\lambda }^{(t)})+\eta (\sum _{i=1}^N{\pi }_i-1)$$

然后对${\pi }_i$求导：

$$\begin{gathered} \frac{\partial L}{\partial {\pi }_i}=\frac{1}{{\pi }_i}P(O,i_1=q_i|{\lambda }^{(t)})+\eta =0 \\ \Rightarrow P(O,i_1=q_i|{\lambda }^{(t)})+{\pi }_i\eta =0 \\ \Rightarrow \sum _{i=1}^N[P(O,i_1=q_i|{\lambda }^{(t)})+{\pi }_i\eta ]=0 \\ \Rightarrow P(O|{\lambda }^{(t)})+\eta =0 \\ \Rightarrow \eta =-P(O|{\lambda }^{(t)}) \end{gathered}$$

代入$P(O,i_1=q_i|{\lambda }^{(t)})+{\pi }_i\eta =0$中，得到：

$${\pi }_i^{(t+1)}=\frac{P(O,i_1=q_i|{\lambda }^{(t)})}{P(O|{\lambda }^{(t)})}$$

以同样的方法对$A^{(t+1)}$$和B^{(t+1)}$求解，然后不断迭代直至收敛，最终求得模型的参数。

四、Decoding问题

Decoding问题是指已知观测序列$O$和参数$\lambda$，求使概率$P(I|O)$最大的状态序列$I$，即：

$$\hat{I}=\underset{I}{\mathrm{argmax}}P(I|O)$$

我们采用动态规划的思想来求解这个问题，首先定义：

$${\delta }_t(i)=\underset{i_1,i_2,\cdots ,i_{t-1}}{\max }P(o_1,o_2,\cdots ,o_t,i_1,i_2,\cdots ,i_{t-1},i_t=q_i)$$

由于参数$\lambda$是已知的，为简便起见省略了$\lambda$，接下来我们需要找到${\delta }_{t+1}(j)$和${\delta }_t(i)$之间的递推式：

$$\begin{gathered} {\delta }_{t+1}(j)=\underset{i_1,i_2,\cdots ,i_t}{\max }P(o_1,o_2,\cdots ,o_{t+1},i_1,i_2,\cdots ,i_t,i_{t+1}=q_j) \\ =\underset{1\le i\le N}{\max }{\delta }_t(i)a_{ij}{b}_j(o_{t+1}) \end{gathered}$$

由此我们就找到了动态规划的递推式，同时我们还需要记录路径，因此定义：

$${\psi }_{t+1}(j)=\underset{1\le i\le N}{\mathrm{argmax}}{\delta }_t(i)a_{ij}$$

因此：

$$maxP(I|O)=max{\delta }_t(i)$$

使$P(I|O)$最大的${\delta }_t(i)$指$t$时刻$i_t=q_i$，然后由${\psi }_t(i)$得到$t-1$时刻$i_{t-1}$的取值，然后继续得到前一时刻的$i_{t-2}$时刻的取值，最终得到整个序列$I$。

五、总结

HMM 是⼀种动态模型（Dynamic Model），是由混合树形模型和时序结合起来的⼀种模型（类似 GMM + Time）。对于类似 HMM 的这种状态空间模型（State Space Model），普遍的除了学习任务（采⽤ EM ）外，还有推断任务。
使用$X$代表观测序列，Z代表隐变量序列，\lambda代表参数。这一类模型需要求解的问题的大体框架为：

$$\{\begin{array}{c}Learning:{\lambda }_{MLE}=\underset{\lambda }{\mathrm{argmax}}P(X|\lambda )【BaumWelchAlgorithm(EM)】\\ Inference\{\begin{array}{c}Decoding:Z=\underset{Z}{\mathrm{argmax}}P(Z|X,\lambda )【ViterbiAlgorithm】\\ Probofevidence:P(X|\lambda )【ForwardAlgorithm、BackwardAlgorithm】\\ Filtering:P(z_t|x_1,x_2,\cdots ,x_t,\lambda )【ForwardAlgorithm】\\ Smoothing:P(z_t|x_1,x_2,\cdots ,x_T,\lambda )【Forward-BackwardAlgorithm】\\ Prediction:\left\{\begin{array}{c}P(z_{t+1}|x_1,x_2,\cdots ,x_t,\lambda )\\ P(x_{t+1}|x_1,x_2,\cdots ,x_t,\lambda )\end{array}\right\}【ForwardAlgorithm】\end{array}\end{array}$$

接下来对Filtering&Smoothing&Prediction问题做一些说明，下面使用$x_{1:t}$代表$x_1,x_2,\cdots ,x_t$，同时也省略已知参数$\lambda$。

（一）Filtering问题

$$P(z_t|x_{1:t})=\frac{P(x_{1:t},z_t)}{P(x_{1:t})}=\frac{P(x_{1:t},z_t)}{{\sum }_{z_t}P(x_{1:t},z_t)}\propto P(x_{1:t},z_t)={\alpha }_t$$

因此使用Forward Algorithm来解决Filtering问题。

Filtering问题通常出现在online learning中，当新进入一个数据，可以计算概率$P(z_t|x_{1:t})$。

（二）Smoothing问题

$$P(z_t|x_{1:T})=\frac{P(x_{1:T},z_t)}{P(x_{1:T})}=\frac{P(x_{1:T},z_t)}{{\sum }_{z_t}P(x_{1:T},z_t)}$$

其中：

$$\begin{gathered} P(x_{1:T},z_t)=P(x_{1:t},x_{t+1:T},z_t) \\ =P(x_{t+1:T}|x_{1:t},z_t)\cdot \underset{{\alpha }_t}{P(x_{1:t},z_t)} \\ =\underset{{\beta }_t}{P(x_{t+1:T}|z_t)}\cdot {\alpha }_t \\ ={\alpha }_t{\beta }_t \end{gathered}$$

这里我们定义$A$集合为$x_{1:t}$，$B$集合为$x_{t+1:T}$，$C$集合为$z_t$，通过$D$划分的方法我们可以知道$x_A\perp x_B|x_C$，即$x_{t+1:T}$与$x_{1:t}$是相互独立的。

由上面的式子我们可以得出：

$$P(z_t|x_{1:T})\propto P(x_{1:T},z_t)={\alpha }_t{\beta }_t$$

因此解决Smoothing问题的算法叫做Forward-Backward Algorithm。

Smoothing问题通常出现在offline learning中，当知道全部观测数据时，来计算概率$P(z_t|x_{1:T})$。

（三）Prediction问题

$$\begin{gathered} P(z_{t+1}|x_{1:t})=\sum _{z_t}P(z_{t+1},z_t|x_{1:t}) \\ =\sum _{z_t}P(z_{t+1}|z_t,x_{1:t})\cdot P(z_t|x_{1:t}) \\ =\sum _{z_t}P(z_{t+1}|z_t)\cdot \underset{Filtering}{P(z_t|x_{1:t})} \end{gathered}$$

上式应用了齐次马尔可夫假设将预测$P(z_{t+1}|x_{1:t})$的问题进行了转化，使用转移概率和求解Filtering问题的方法就可以计算这个概率。

$$\begin{gathered} P(x_{t+1}|x_{1:t})=\sum _{z_{t+1}}P(x_{t+1},z_{t+1}|x_{1:t}) \\ =\sum _{z_{t+1}}P(x_{t+1}|z_{t+1},x_{1:t})\cdot P(z_{t+1}|x_{1:t}) \\ =\sum _{z_{t+1}}P(x_{t+1}|z_{t+1})\cdot \underset{Precition}{P(z_{t+1}|x_{1:t})} \end{gathered}$$

上式应用了观测独立假设将预测$P(x_{t+1}|x_{1:t})$的问题进行了转化，使用发射概率和求解上一个Prediction问题的方法就可以计算这个概率。

下一章传送门：

参考文章