隐马尔可夫模型

定义概率计算算法直接计算法前向算法后向算法 学习算法监督学习方法Baum-Welch 算法 预测算法近似算法维特比算法 参考文献 隐马尔可夫模型可用于 标注问题，属于 生成模型，在语音识别、自然语言处理、生物信息、模式识别等领域有着广泛的应用。

定义

隐马尔可夫模型是关于时序的概率模型，描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测而产生观测随机序列的过程。隐藏的马尔可夫链随机生成的状态的序列，称为状态序列。每个状态生成一个观测，而由此产生的观测的随机序列，称为观测序列。序列的每一个位置又可以看作是一个时刻。

隐马尔可夫模型的形式定义如下： 设 $Q$ 是所有可能的状态的集合，$V$ 是所有可能的观测的集合： $$A=\{q_1,q_2,...,q_N\},V=\{v_1,v_2,...,v_M\}$$其中，$N$ 是可能的状态数，$M$ 是可能的观测数。

$I$ 是长度为 $T$ 的状态序列，$O$ 是对应的观测序列： $$I=\{i_1,i_2,...,i_T\},O=\{o_1,o_2,...,o_T\}$$ $A$ 是状态转移概率矩阵： $$A=[a_{ij}{]}_{N\times N}$$其中，$a_{ij}=P(i_{t+1}=q_j|i_t=q_i)$，$i=1,2,...,N;j=1,2,...,N$，是在时刻 $t$ 处于状态 $q_i$ 的条件下在时刻 $t+1$ 转移到状态 $q_j$ 的概率。

$B$ 是观测概率矩阵： $$B=[b_j(k){]}_{N\times M}$$其中，$b_j(k)=P(o_t=v_k|i_t=q_j)$，$k=1,2,...,M;j=1,2,...,N$，是在时刻 $t$ 处于状态 $q_j$ 的条件下生成观测 $v_k$ 的概率。

$\pi$ 是初始状态概率向量： $$\pi =({\pi }_i)$$其中，${\pi }_i=P(i_1=q_i)$，$i=1,2,...,N$ 是时刻 $t=1$ 处于状态 $q_i$ 的概率。

隐马尔可夫模型有初始状态概率向量 $\pi$、状态转移概率矩阵 $A$ 和观测概率矩阵 $B$ 决定。$\pi$ 和 $A$ 决定状态序列，$B$ 决定观测序列。因此，隐马尔可夫模型 $\lambda$ 可以用三元符号表示，即： $$\lambda =(A,B,\pi )$$$A,B,\pi$ 称为隐马尔可夫模型的三要素。状态转移概率矩阵 $A$ 与初始状态概率向量 $\pi$ 确定了隐藏的马尔可夫链，生成不可观测的状态序列。观测概率矩阵 $B$ 确定了如何从状态生成观测，与状态序列综合确定了如何产生观测序列。

基本假设：

齐次马尔可夫性假设，即假设隐藏的马尔可夫链在任意时刻 $t$ 的状态只依赖于其前一时刻的状态，与其他时刻的状态及观测无关，也与时刻 $t$ 无关： $$P(i_t|i_{t-1},o_{t-1},...,i_1,o_1)=P(i_t|i_{t-1}),t=1,2,...,T$$观测独立性假设，即假设任意时刻的观测只依赖于该时刻的马尔可夫链的状态，与其他观测即状态无关： $$P(o_t|i_T,o_T,i_{T-1},o_{T-1},...,i_{t+1},o_{t+1},i_t,i_{t-1},o_{t-1},..,i_1,o_1)=P(o_t|i_t)$$

概率计算算法

概率计算问题，就是给定模型 $\lambda =(A,B,\pi )$ 和观测序列 $O=(o_1,o_2,...,o_T)$，计算在模型 $\lambda$ 下观测序列 $O$ 出现的概率 $P(O|\lambda )$。

直接计算法

最直接的方法是按概率公式直接计算，通过列举所有可能的长度为 $T$ 的状态序列 $I=(i_1,i_2,...,i_T)$，求各个状态序列 $I$ 与观测序列 $O=(o_1,o_2,...,o_T)$ 的联合概率 $P(O,I|\lambda )$，然后对所有可能的状态序列求和，得到 $P(O|\lambda )$。

但是这样的计算量很大，是 $O(T{N}^T)$ 阶的，这种算法不可行。

前向算法

前向概率：给定隐马尔可夫模型 $\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 )$$可以递推地求得前向概率 ${\alpha }_t(i)$ 即观测序列概率 $P(O|\lambda )$。

观测序列概率的前向算法： 输入：隐马尔可夫模型 $\lambda$，观测序列 $O$； 输出：观测序列概率 $P(O|\lambda )$。

初值：${\alpha }_1(i)={\pi }_i{b}_i(o_1),i=1,2,...,N$递推：对 $t=1,2,...,T-1$， $${\alpha }_{t+1}(i)=\left[\sum _{j=1}^N{\alpha }_t(j)a_{ji}\right]b_i(o_{t+1}),i=1,2,...,N$$终止： $$P(O|\lambda )=\sum _{i=1}^N{\alpha }_T(i)$$ 其中，步骤1初始化前向概率，是初始时刻的状态 $i_1=q_i$ 和观测 $o_1$ 的联合概率。步骤2是前向概率的递推公式，计算到时刻 $t+1$ 部分观测序列为 $o_1,o_2,...,o_t,o_{t+1}$ 且在时刻 $t+1$ 处于状态 $q_i$ 的前向概率。对乘积在时刻 $t$ 的所有可能的 $N$ 个状态 $q_j$ 求和，其结果就是到时刻 $t$ 观测为 $o_1,o_2,...,o_t$ 并在时刻 $t+1$ 处于状态 $q_i$ 的联合概率。

前向算法能够减少计算量的原因在于每一次计算直接引用前一个时刻的计算结果，避免重复计算。专业，前向概率计算 $P(O|\lambda )$ 的计算量是 $O(N^{2}T)$ 阶的。

后向算法

后向概率：给定隐马尔可夫模型 $\lambda$，定义在时刻 $t$ 状态为 $q_i$ 的条件下，从 $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 )$$ 观测序列概率的后向算法： 输入：隐马尔可夫模型 $\lambda$，观测序列 $O$； 输出：观测序列概率 $P(O|\lambda )$。

${\beta }_T(i)=1,i=1,2,...,N$对 $t=T-1,T-2,...,1$: $${\beta }_t(i)=\sum _{j=1}^N{a}_{ij}{b}_j(o_{t+1}){\beta }_{t+1}(j),i=1,2,...,N$$$$P(O|\lambda )=\sum _{i=1}^N{\pi }_i{b}_i(o_1){\beta }_1(i)$$ 其中，步骤1初始化后向概率，由于后向概率是基于模型参数和最终状态是 $q_i$的基础上定义的，因此最终的时刻 $T$ 所有状态是确定的，即 ${\beta }_T(i)=1$。步骤2是后向概率的递推公式，为了计算在时刻 $t$ 状态为 $q_i$ 条件下时刻 $t+1$ 之后的观测序列为 $o_{t+1},o_{t+2},...,o_T$ 的后向概率 ${\beta }_t(i)$，只需考虑在时刻 $t+1$ 所有可能的 $N$ 个状态 $q_j$ 的转移概率（即 $a_{ij}项$），以及在此状态下的观测 $o_{t+1}$ 的观测概率（即 $b_j(o_{t+1})$），然后考虑状态 $q_j$ 之后的观测序列的后向概率（即 ${\beta }_{t+1}(j)$项）。

利用前向概率和后向概率的定义可以将观测序列概率统一写成： $$P(O|\lambda )=\sum _{i=1}^N\sum _{j=1}^N{\alpha }_t(i)a_{ij}{b}_j(o_{t+1}){\beta }_{t+1}(j),t=1,2,...,T-1$$此式当 $t=1$ 和 $t=T-1$ 时分别为前两个式子。

学习算法

已知观测序列 $O=(o_1,o_2,...,o_T)$，估计模型 $\lambda$ 参数，使得在该模型下观测序列概率 $P(O|\lambda )$ 最大。根据训练数据是包括观测序列和对应的状态序列还是只有观测序列，可以分别由监督学习与非监督学习实现。

监督学习方法

假设已给训练数据包含 $S$ 个长度相同的观测序列和对应的状态序列 $\{(O_1,I_1),(O_2,I_2),...(O_S,I_S)\}$，那么可以利用极大似然估计法来估计隐马尔可夫模型的参数。具体方法如下：

转移概率 $a_{ij}$ 的估计： 设样本中时刻 $t$ 处于状态 $i$，时刻 $t+1$ 转移到状态 $j$ 的频数为 $A_{ij}$，那么 $${\hat{a}}_{ij}=\frac{A_{ij}}{{\sum }_{j=1}^N{A}_{ij}},i=1,2,...,N;j=1,2,...,N$$观测概率 $b_j(k)$ 的估计： 设样本中状态为 $j$ 并观测为 $k$ 的频数是 $B_{jk}$，那么 $${\hat{b}}_j(k)=\frac{B_{jk}}{{\sum }_{k=1}^M{B}_{jk}},j=1,2,...,N;k=1,2,...,M$$初始状态概率 ${\pi }_i$ 的估计： 为 $S$ 个样本中初始状态为 $q_i$ 的频率

Baum-Welch 算法

如果只有观测序列，而没有对应的状态序列，这是可以采用非监督学习的Baum-Welch算法（也就是EM算法）。将观测序列数据看作观测数据 $O$，状态序列数据看作不可观测的隐数据 $I$，那么马尔可夫模型事实上是一个含有隐变量的概率模型： $$P(O|\lambda )=\sum _{I}P(O|I,\lambda )P(I|\lambda )$$ Baum-Welch算法： 输入：观测数据 $O=(o_1,o_2,...,o_T)$； 输出：隐马尔可夫模型参数。

初始化 对 $n=0$，选取 $a_{ij}^{(0)},b_j(k{)}^{(0)},{\pi }_i^{(0)}$，得到模型 ${\lambda }^{(0)}=(A^{(0)},B^{(0)},{\pi }^{(0)})$。递推，对 $n=1,2,...,$： $$\begin{gathered} a_{ij}^{(n+1)}=\frac{{\sum }_{t=1}^{T-1}{\xi }_t(i,j)}{{\sum }_{t=1}^{T-1}{\gamma }_t(i)} \\ {b}_j(k{)}^{(n+1)}=\frac{{\sum }_{t=1,o_t=v_k}^T{\gamma }_t(j)}{{\sum }_{t=1}^T{\gamma }_t(j)} \\ {\pi }_i^{(n+1)}={\gamma }_1(i) \end{gathered}$$其中 $$\begin{gathered} {\gamma }_t(i)=\frac{{\alpha }_t(i){\beta }_t(i)}{P(O|\lambda )}=\frac{{\alpha }_t(i){\beta }_t(i)}{{\sum }_{j=1}^N{\alpha }_t(j){\beta }_t(j)} \\ {\xi }_t(i,j)=\frac{{\alpha }_t(i)a_{ij}{b}_j(o_{t+1}){\beta }_{t+1}(j)}{{\sum }_{i=1}^N{\sum }_{j=1}^N{\alpha }_t(i)a_{ij}{b}_j(o_{t+1}){\beta }_{t+1}(j)} \end{gathered}$$终止。得到模型参数 ${\lambda }^{(n+1)}=(A^{(n+1)},B^{(n+1)},{\pi }^{(n+1)})$。

预测算法

已知模型 $\lambda =(A,B,\pi )$ 和观测序列 $O=(o_1,o_2,...,o_T)$，求对该给定观测序列，条件概率 $P(O|\lambda )$ 最大的状态序列 $I=(i_1,i_2,..,i_T)$。即给定观测序列，求对应的最有可能的状态序列。

近似算法

近似算法的思想是，在每个时刻 $t$ 选择在该时刻最有可能出现的状态 $i_t^{\ast }$，从而得到一个状态序列 $I^{\ast }=(i_1^{\ast },i_2^{\ast },..,i_T^{\ast })$，将它作为预测的结果。

给定隐马尔可夫模型 $\lambda$ 和观测序列 $O$，在时刻 $t$ 处于状态 $q_i$ 的概率 ${\gamma }_t(i)$ 是： $${\gamma }_t(i)=\frac{{\alpha }_t(i){\beta }_t(i)}{P(O|\lambda )}=\frac{{\alpha }_t(i){\beta }_t(i)}{{\sum }_{j=1}^N{\alpha }_t(j){\beta }_t(j)}$$在每一时刻 $t$ 最有可能的状态 $i_t^{\ast }$ 是： $$i_t^{\ast }=\arg \underset{1\le i\le N}{\max }[{\gamma }_t(i)],t=1,2,...,T$$从而得到状态序列 $I^{\ast }=(i_1^{\ast },i_2^{\ast },..,i_T^{\ast })$。

维特比算法

维特比算法是用动态规划求概率最大路径，这时一条路径对应着一个状态序列。首先导入两个变量 $\delta$ 和 $\psi$。定义在时刻 $t$ 状态为 $i$ 的所有单个路径 $(i_1,i_2,...,i_t)$ 中概率最大值为： $${\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 ),i=1,2,...,N$$由定义可得变量 $\delta$ 的递推公式： $$\begin{gathered} {\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\le j\le N}{\max }[{\delta }_t(j)a_{ji}]b_i(o_{t+1}),i=1,2,...,N;t=1,2,...,T-1 \end{gathered}$$定义在时刻 $t$ 状态为 $i$ 的所有单个路径 $(i_1,i_2,...,i_{t-1},i)$ 中概率最大的路径的第 $t-1$ 个结点为： $${\psi }_t(i)=\arg \underset{1\le j\le N}{\max }[{\delta }_{t-1}(j)a_{ji}],i=1,2,...,N$$ 维特比算法： 输入：模型 $\lambda =(A,B,\pi )$ 和观测 $O=(o_1,o_2,...,o_T)$； 输出：最优路径 $I^{\ast }=(i_1^{\ast },i_2^{\ast },..,i_T^{\ast })$。

初始化： $$\begin{gathered} {\delta }_1(i)={\pi }_i{b}_i(o_1),i=1,2,...,N \\ {\psi }_1(i)=0,i=1,2,...,N \end{gathered}$$递推。对 $t=2,3,...,T$： $$\begin{gathered} {\delta }_t(i)=\underset{1\le j\le N}{\max }[{\delta }_{t-1}(j)a_{ji}]b_i(o_t),i=1,2,...,N \\ {\psi }_t(i)=\arg \underset{1\le j\le N}{\max }[{\delta }_{t-1}(j)a_{ji}],i=1,2,...,N \end{gathered}$$终止 $$\begin{gathered} P^{\ast }=\underset{1\le i\le N}{\max }{\delta }_T(i) \\ {i}_T^{\ast }=\arg \underset{1\le i\le N}{\max }\left[{\delta }_T(i)\right] \end{gathered}$$最优路径回溯。对 $t=T-1,T-2,...,1$： $$i_t^{\ast }={\psi }_{t+1}(i_{t+1}^{\ast })$$求得最优路径 $I^{\ast }=(i_1^{\ast },i_2^{\ast },...,i_T^{\ast })$。

参考文献

[1] 李航. 统计学习方法. 清华大学出版社. 2012