1.1 定义

隐马尔科夫模型：可用于标注问题，在语音识别、NLP、生物信息、模式识别等领域被实践证明是有效的算法。

HMM是关于时序的概率模型，描述由一个隐藏的马尔科夫链生成不可观测的状态随机序列，再由各个状态生成观测随机序列的过程。(生成模型)

隐马尔科夫模型随机生成的状态随机序列，称为状态序列；每个状态生成一个观测，由此产生的观测随机序列，称为观测序列。

$z_{1},z_{2}...z_{n+1}$ 是主题，我们需要通过词来确定的对象。

$x_{1},x_{2}...x_{n+1}$ 是词，我们所观察的对象。

在 $z_{1},z_{2}$ 不可观察的前提下， $x_{1},z_{2}$ 独立。如下图，将右侧部分看作一个整体，作为X’。因此就可以当作贝叶斯网络。当 $z_{1}$ 不可观察时， $x_{1},x'$ 相互独立。

1.2 HMM模型的确定

HMM由初始概率分布 $\pi$ 、状态转移概率分布A以及观测概率分布B确定。

$\lambda =(A,B,\pi )$

Q是所有可能的状态的集合；N是可能的状态数

V是所有可能的观测的集合；M是可能的观测数

$Q=\left \{ q_{1},q_{2},...,q_{N}\right \}$

$V=\left \{ v_{1},v_{2},...v_{M} \right \}$

参数分析：

I是长度为T的状态序列，O是对应的观测序列：

$I=\left \{ i_{1},i_{2}...,i_{T} \right \}$ ， $O=\left \{ o_{1},o_{2},...,o_{T} \right \}$

隐状态： $A_{nxn}=\begin{pmatrix} a_{11}& a_{12} & ... & a_{1n}\\ a_{21}& a_{22} & ... & a_{2n} \\ \vdots & \vdots & & \vdots \\ a_{n1} & a_{n2} & ...& a_{nn} \end{pmatrix}$ ，其中 $a_{i1}+a_{i2}+...+a_{in}=1,i=1,2...n$

其中 $a_{ij}=P(i_{t+1}=q_{j}|i_{t}=q_{i})$ 是在时刻t处于状态 $q_{i}$ 的条件下时刻t+1转移到状态 $q_{i}$ 的概率。

ps: 隐状态必须是离散的。

$B_{nxm}=\begin{pmatrix} b_{11} & b_{12} & b_{13} & ... &b_{1m} \\ b_{21}&b_{22} & b_{23} & ...& b_{2m}\\ \vdots &\vdots & \vdots & & \vdots \\ b_{n1}& b_{n2} &b_{n3} & ... & b_{nm} \end{pmatrix}$

可观测序列，值是连续或者离散的都可以。

n——隐状态的个数 m——可观测的个数

$b_{ik}=P(o_{t}=v_{k}|i_{t}=q_{i})$ 是在时刻t处于状态 $q_{i}$ 的条件下生成观测 $v_{k}$ 的概率。

$\pi _{i}=P(i_{1}=q_{i})$ 是时刻t=1处于状态 $q_{i}$ 的概率。

总结：HMM由初始概率分布 $\pi$ （向量）、状态转移概率分布A（矩阵）以及观测概率分布B（矩阵）确定。 $\pi$ 和A决定状态序列，B决定观测序列。因此，HMM可以用三元符号表示，称为HMM的三要素： $\lambda =(A,B,\pi )$

1.3 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})$

（2）观测独立性假设： $P(o_{t}|i_{T},o_{T},i_{T-1},...,i_{1},o_{1})=P(o_{t}|i_{t})$

1.4 HMM的实例

问题：求解最终得到{红、白、红}的概率？

设置各个参数如下：
状态集合：Q={盒子1，盒子2，盒子3}

观测集合：V={红，白}

状态序列和观测序列的长度为：T=3+2=5

初始概率分布： $\pi=\begin{pmatrix} 0.2\\ 0.4\\ 0.4 \end{pmatrix}$

状态转移概率分布： $A=\begin{bmatrix} 0.5&0.2 &0.3 \\ 0.3 &0.5 &0.2 \\ 0.2 &0.3 &0.5 \end{bmatrix}$

观测概率分布： $B=\begin{bmatrix} 0.5 &0.5 \\ 0.4& 0.6\\ 0.7& 0.3 \end{bmatrix}$

求解：见1.6

1.5 HMM的3个基本问题

概率计算问题（重点）：前向-后向算法——动态规划

给定模型 $\lambda =(A,B,\pi )$ 和观测序列 $O=\left \{ o_{1},o_{2},...,o_{T} \right \}$ ，计算模型 $\lambda$ 下观测序列O出现的概率 $P(O|\lambda )$ 。

学习问题：Baum-Welch算法（状态未知）——EM

已知观测序列 $O=\left \{ o_{1},o_{2},...,o_{T} \right \}$ ，估计模型 $\lambda =(A,B,\pi )$ 的参数，使得在该模型下观测序列 $P(O|\lambda )$ 最大。

预测问题：Viterbi算法——动态规划

解码问题：已知模型 $\lambda =(A,B,\pi )$ 和观测序列 $O=\left \{ o_{1},o_{2},...,o_{T} \right \}$ ，求给定观测序列条件概率 $P(I|O,\lambda )$ 最大的状态序列 $I$ 。

1.6 概率计算问题

直接计算（暴力算法）

按照概率公式，列举所有可能的长度为T的状态序列 $I=\left \{ i_{1},i_{2},...,i_{T} \right \}$ ,\，求各个状态序列I和观测序列 $O=\left \{ o_{1},o_{2},o_{3},...,o_{T} \right \}$ 的联合概率 $P(O,I|\lambda )$ ，然后对所有可能的状态序列求和，从而得到 $P(O|\lambda )$ 。

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

前向算法

前向算法的定义：给定 $\lambda$ ，定义到时刻t部分观测序列为 $o_{1},o_{2}...o_{t}$ ，且状态为 $q_{i}$ 的概率称为前向概率，记作： $\alpha _{t}(i)=P(o_{1},o_{2},...,o_{t},i_{t}=q_{i}|\lambda )$

计算观测序列概率 $P(O|\lambda )$ ：

（1）初值： $\alpha _{1}(i)=\pi _{i}b_{io_{1}}$

（2）递推：对于 $t=1,2,...,T-1$ ， $\alpha _{t+1}(i)=(\sum_{j=1}^{N}\alpha _{t}(j)a_{ji})b_{io_{t+1}}$

（3）最终： $P(O|\lambda )=\sum_{i=1}^{N}\alpha _{T}(i)$

时间复杂度是 $O(N^{2}T)$

1.4实例可以通过前向算法求解：

（1）计算初值

$\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$

(2)递推

$\alpha _{2}(1)=(\sum_{j=1}^{N}\alpha _{1}(j)a_{j1})b_{1o_{2}}=(0.1\times 0.5+0.16\times 0.3+0.28\times 0.2 )=0.077$

同理： $\alpha _{2}(2)=0.1104,\alpha _{2}(3)=0.0606$

$\alpha _{3}(1)=0.04187,\alpha _{3}(2)=0.03551,\alpha _{3}(3)=0.05284$

（3）最终

$P(O|\lambda )=\sum_{i=1}^{3}\alpha _{3}(i)=0.04187+0.03551+0.05284=0.13022$

后向算法

给定 $\lambda$ ，定义到时刻t状态为qi的前提下，从t+1到T的部分观测时序为 $o_{t+1},o_{t+2},...,o_{T}$ 的概率为后向概率，记作： $\beta _{t}(i)=P(o_{t+1},o_{t+2},...,o_{T}|i_{t}=q_{i},\lambda )$

计算观测序列概率 $P(O|\lambda )$ ：

（1）初值 $\beta _{T}(i)=1$

（2）递推，对于t=T-1,T-2,...,1， $\beta _{t}(i)=\sum_{j=1}^{N}(a_{ij}b_{jo_{t+1}}\beta_{t+1} (j))$

（4）最终： $P(O|\lambda )=\sum_{i=1}^{N}\pi _{i}b_{io_{1}}\beta _{1}(i)$

前向概率、后向概率的关系

$P(i_{t}=q_{i},O|\lambda )=P(O|i_{t}=q_{i},\lambda )P(i_{t}=q_{i}|\lambda ) =P(o_{1},...,o_{t},o_{t+1},...,o_{T}|i_{t}=q_{i},\lambda )P(i_{t}=q_{i}|\lambda ) =P(o_{1},...,o_{t}|i_{t}=q_{i},\lambda)P(o_{t+1},...,o_{T}|i_{t}=q_{i},\lambda)P(i_{t}=q_{i}|\lambda )=P(o_{1},...,o_{t},i_{t}=q_{i}|\lambda)P(o_{t+1},...,o_{T}|i_{t}=q_{i},\lambda)=\alpha_{t} (i)\beta _{t}(i)$

1.7 单个状态的概率

求给定模型 $\lambda$ 和观测 $O$ ，在时刻t处于状态qi的概率：

记作： $\gamma _{t}(i)=P(i_{t}=q_{i}|O,\lambda )$

$\gamma _{t}(i)=P(i_{t}=q_{i}|O,\lambda )=\frac{P(i_{t}=q_{i},O|\lambda )}{P(O|\lambda )}=\frac{\alpha_{t} (i)\beta _{t}(i)}{P(O|\lambda )}=\frac{\alpha_{t} (i)\beta _{t}(i)}{\sum_{i=1}^{N}\alpha_{t} (i)\beta _{t}(i)}$

$\gamma$ 的意义为：在每个时刻t选择在该时刻最有可能出现的状态 $i_{t}^{*}$ ，从而得到一个状态序列

$I^{*}=\left \{ i_{1}^{*},i_{2}^{*},...,i_{T}^{*} \right \}$ 将它作为预测的结果。

例如：对于一句话“今天我吃了一个火龙果”，划分词是可能出现的状态有（begin,mid,end,single）

若这么划分词：今天|我|吃|了|一个|火龙果。

则：

begin:“今”，“一”、“火”

mid:“龙”

end:“天”、“个”

single:“我”、“吃”、“了”

期望：在观测O下状态i出现的期望： $\sum_{t=1}^{T}\gamma _{t}(i)$

1.8 两个状态的联合概率

求给定模型 $\lambda$ 和观测 $O$ ，在时刻t处于状态qi的概率并且时刻t+1处于状态qi的概率：
$\zeta _{t}(i,j)=P(i_{t}=q_{i},i_{t+1}=q_{j}|O,\lambda )$

$\zeta _{t}(i,j)=P(i_{t}=q_{i},i_{t+1}=q_{j}|O,\lambda )=\frac{P(i_{t}=q_{i},i_{t+1}=q_{j},O|\lambda )}{P(O|\lambda )}=\frac{P(i_{t}=q_{i},i_{t+1}=q_{j},O|\lambda )}{\sum_{i=1}^{N}\sum_{j=1}^{N}P(i_{t}=q_{i},i_{t+1}=q_{j},O|\lambda )}$

其中： $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 )$

期望：在观测O下状态i转移到状态j的期望： $\sum_{t=1}^{T-1}\zeta _{t}(i,j)$

1.9 学习算法

若训练数据包括观测序列和状态序列，则HMM的学习非常简单，是监督学习；

若训练数据只有观测序列，则HMM的学习需要使用EM算法，是非监督学习。

（1）监督学习

假设已经给定训练数据包括S个长度相同的观测序列和对应的状态序列 $\left \{ (O_{1},I_{1}),(O_{2},I_{2}),...,(O_{s},I_{s}) \right \}$ ，那么可以直接利用Bernoulli大数定理的结论“频率的极限是概率”，给定HMM的参数估计。

初始概率 $\widehat{\pi _{i}}=\frac{|q_{i}|}{\sum_{i}|q_{i}|}$

转移概率 $\widehat{a_{ij}}=\frac{|q_{ij}|}{\sum_{j=1}^{N}|q_{ij}|}$

观测概率 $\widehat{b_{ik}}=\frac{|s_{ik}|}{\sum_{k=1}^{M}|s_{ik}|}$

(2)非监督学习

Baum-Welch算法：

所有观测数据为 $O=(o_{1},o_{2},...,o_{T})$ ，所有隐数据为 $I=(i_{1},i_{2},...,i_{T})$ ，完全数据是 $(O,T)=(o_{1},o_{2},...,o_{T},i_{1},i_{2},...,i_{T})$ ，完全数据的对数似然函数为 $lnP(I|O,\lambda )$ 。

假设 $\overline{\lambda }$ 是HMM参数的当前估计值， $\lambda$ 为待求的参数。

$Q(\lambda ,\overline{\lambda })=\sum_{I}(lnP(O,I|\lambda ))P(I|O,\overline{\lambda } )=\sum_{I}(lnP(O,I|\lambda ))\frac{P(O,I|\lambda )}{P(O,\overline{\lambda })}$

EM过程：

因为 $P(O,I|\lambda )=P(O|I,\lambda )P(I|\lambda )=\pi _{i_{1}}b_{i_{1}o_{1}}a_{i_{1}i_{2}}...a_{i_{T-1}i_{T}}b_{i_{T}o_{T}}$

所以 $Q(\lambda ,\overline{\lambda })=\sum_{I}(lnP(O,I|\lambda ))P(I|O,\overline{\lambda } )=\sum_{I}ln\pi _{i_{1}}P(O,I|\lambda )+\sum_{I}(\sum_{t=1}^{T-1}lna_{i_{t}i_{t+1}})P(O,I|\overline{\lambda })+\sum_{I}(\sum_{t=1}^{T}lnb_{i_{t}o_{t}})P(O,I|\overline{\lambda })$

拉格朗日乘子法：
$\sum_{i=1}^{N}(ln\pi _{i})P(O,i_{1}=i|\overline{\lambda} )+\gamma (\sum_{i=1}^{N}\pi _{i}-1)$ ，其中 $\sum_{i=1}^{N}\pi _{i}=1$

先对 $\pi_{i}$ 求偏导：

$P(O,i_{1}=i|\overline{\lambda })+\gamma \pi _{i}=0$

∴ $\sum_{i=1}^{T}P(O,i_{1}=i|\overline{\lambda })+\sum_{i=1}^{T}\gamma \pi _{i}=0$

∴ $\gamma =-P(O|\overline{\lambda })$

∴初始状态概率为 $\pi_{i}=\frac{P(O,i_{1}=i|\overline{\lambda })}{P(O|\overline{\lambda })}= \frac{P(O,i_{1}= i|\overline{\lambda })}{\sum_{i=1}^{N}P(O,i_{1}=i|\overline{\lambda })}=\gamma _{1}(i)$

转移概率和观测概率：

1.10 Viterbi算法

Viterbi算法实际是用动态规划解HMM预测问题，用DP求概率最大的路径（最优路径），这是一条路径对应一个状态序列。

定义变量 $\delta _{t}(i)$ ：在时刻t状态为i的所有路径中，概率的最大值。

$\delta _{t}(i)=\underset{i_{1},i_{2},...,i_{t-1}}{max}P(i_{t}=i,i_{t-1},...,i_{1},o_{t},...o_{1}|\lambda )$

递推： $\delta _{1}(i)=\pi _{i}b_{io_{1}}$

$\delta _{t+1}(i)=\underset{i_{1},i_{2},...,i_{t}}{max}P(i_{t+1}=i,i_{t},...,i_{1},o_{t+1},...o_{1}|\lambda )=\underset{1\leq j\geq N}{max}(\delta _{t}(j)a_{ji})b_{io_{t+1}}$