Hidden Markov Model

隐马尔可夫模型(Hidden Markov Model,HMM)[1]用来描述一个含有隐含未知参数的马尔可夫过程。n阶马尔科夫过过程假设当前状态只依赖于前n个时刻的状态,通常而言,隐马模型指的是一阶.

一般来说,HMM中说到的马尔可夫链其实是指隐含状态链。隐含状态之间存在转移概率分布,隐含状态到观测序列之间是输出概率分布。一般而言,HMM模型由三种参数组成,也即$(\pi,A,B)$。其中,$\pi$为隐含状态的初始化概率分布,$A$为状态转移矩阵,其中$A_{i,j}$表示从隐含状态$i$转移到隐含状态$j$的概率,$B$为混淆矩阵或者观测状态生成矩阵,$B_i(j)$表示隐含状态i生成观测序列元素j的概率。

1. HMM的三个问题

一般和HMM模型有关的算法主要分为三种,以天气和海藻为例(天气为隐含状态,海藻的干湿为观测状态).

  1. 给定HMM模型,以及海藻的观测序列,计算该观测序列出现的概率(评估)
  2. 给定HMM模型,以及海藻的观测序列,推断天气最可能的状态变化序列(解码)
  3. 给定了历史海藻观测状态和天气状态数据(有监督学习)或者仅给出海藻观测状态,学习出HMM的三种参数(学习)[2]

1.1 评估

假定我们现在有描述不同季节的HMM模型,要根据给定观测的海藻状态推断最有可能产生这个海藻状态的季节。常规的思维是枚举每一种可能的隐含状态序列,然后用转移概率分布和生成观测序列的概率分布去计算概率,但是枚举的状态有$N^T$中,其中$T$为观测序列的长度,$N$为隐含状态的数目,计算复杂度过高,不具有实用性,所以需要另辟蹊径。

前向算法

前向算法,是一种动态规划算法,它具有许多独特的性质,如子问题最优,也即全局最优可以通过枚举子问题最优得到。联想到HMM的图模型结构,我们不难得知,在时刻t处于状态i的情况(此时观测序列为$O_1,O_2,O_3,…,O_t$)下,它可以由多种子状态按照HMM的性质转化而来:由时刻t-1处于状态j的情况(此时观测序列为$O_1,O_2,O_3,…,O_{t-1}$)首先从状态i转换到j,然后生成观测状态$O_t$得到,所以可以得到如下状态转移方程:
$$
\alpha_t(i) = \sum_{j=1}^N{\alpha_{t-1}(j) A_{i,j}} B_i(O_t)
$$
上述方程也可以通过贝叶斯公式推导而来,令$P(O_1,O_2,…,O_t,S_i \| \lambda)=a_t(i)$, 则有:

$$
\begin{align}
p(O_1,…,O_t,S_i\|\lambda) & = \sum_j P(O_1,…,O_{t-1},S_j\| \lambda) \\
&= \sum_j P(O_1,…,O_{t-1},S_j\| \lambda) P(O_1,…,O_t,S_i\|O_1,…,O_{t-1},S_j,\lambda) \\
& = \sum_j P(O_1,…,O_{t-1},S_j\| \lambda) P(O_t,S_i\|S_j,\lambda) \\
& = \sum_j P(O_1,…,O_{t-1},S_j\| \lambda) P(S_j\|S_j, \lambda) P(O_t \| S_i, \lambda)
\end{align}
$$

此时$P(O \| \lambda) = \sum_i \alpha_T(i)$.

后向算法

其实后向算法也容易理解,也是一个动态规划的过程。在时刻t处于状态i的前提下,观测序列为O(t+1)…O(T)的情况可以由时刻t+1的状态转移变换得到,也即:
$$
\beta_t(i) = \sum_{j=1}^N{\beta_{t+1}(j) A_{j,i}B_j(O^{t+1})}
$$
此时$P(O\|\lambda) = \sum_i \pi_i b_1(i) B_i(O_1)) $

1.2 解码

解码也即是预测问题,即给定模型$\lambda$和观测序列$X$,预测其状态序列$Y$。可以将问题抽象为在给定的二维概率矩阵中,找到一个转移路径,使得这条路径的转移概率最大。而这条路径上的每个点都是从起始状态到当前状态概率最大的转移路径的终点。令$\alpha_t(i)$为t时刻隐含状态为i的最大概率,$\alpha_t(i)=max{\alpha_{t-1}(j)A_{j,i}B_t{j}}$。在wiki上有这样一个关于天气和健康的HMM模型,viterbi算法的计算流程如下图所示:

在计算得到所有的$\alpha_t{i}$之后,从T时刻逆序,分别取每一个时刻最大概率的隐含状态,便可以得到需要预测的隐含状态序列。viterbi算法除了在HMM中用到之外,在CRF的预测中也有用到,大体思路一致,只不过状态转移的计算要用上特征函数以及权值~ TODO:CTC介绍.

1.3 学习

学习也即参数估计了,如果给定了样本的序列label,那么经过简单的统计便可以计算得到$\pi$, 转移概率矩阵$A$以及观测状态生成矩阵$B$,如分词如果采用BEMS的方式进行标注的话,给定文本和对应的label集合,便可以统计出BEMS之间的转移概率,以及BEMS到对应的中文字符的生成概率. 但是如果没有给定序列label, 可以通过前向后向算法(前向-后向算法(又称之为Baum-Welch算法)进行参数估计。令给定观测状态为O且$t$时刻隐含状态为$S_i$的概率为$P(I_t=S_i,O\|\lambda)$, 则$P(I_t=S_i,O\|\lambda)=\alpha_t(i) \beta_t(i)$,对于单个状态的概率(给定观测状态序列O的前提下,$t$时刻隐含状态为i)$\gamma_t(i)=P(S_i\|O,\lambda)$, 有:
$$
\gamma_t(i) = \frac {P(S_i,O|\lambda)}{P(O|\lambda)} = \frac {P(S_i,O|\lambda)}{\sum_j P(S_j, O|\lambda)} = \frac { \alpha_t(i)\beta_t(i) } {\sum_j \alpha_t(j)\beta_t(j)}
$$

两个状态的概率(t时刻状态为i,t+1时刻状态为j)的概率$\xi_{t}(i,j)=P(i_t=S_i,i_{i+1}=S_j|O,\lambda)$, 则有:

$$
\begin{align} \xi_{t}(i,j) & = \frac {P(i_t=S_i,i_{t+1}=S_j|O,\lambda)}{P(O,\lambda)} \\ &= \frac {P(i_t=S_i,i_{i+1}=S_j|O,\lambda)}{\sum_i\sum_j {P(i_t=S_i,i_{t+1}=S_j|O,\lambda)}} \\ &=
\frac {\alpha_t(i) A_{i,j} \beta_{t+1}(j) B_j(t+1) } { \sum_i\sum_j{ \alpha_t(i) A_{i,j} \beta_{t+1}(j) B_j(t+1)} }
\end{align}
$$

 

参考文献

[1][一文搞懂HMM(隐马尔可夫模型)](http://www.cnblogs.com/skyme/p/4651331.html)
[2][HMM学习最佳范例](http://www.52nlp.cn/hmm-learn-best-practices-four-hidden-markov-models)

Leave a Reply

Your email address will not be published. Required fields are marked *