统计学习方法(6)---HMM

HMM,BW算法,维特比

Posted by weber on February 6, 2020

hidden markov model,HMM

1. 一句话概括HMM

HMM描述由隐藏的马尔可夫链生成观测序列的过程。

1.1 三个要素

其中,A为状态转移矩阵,B为观测概率矩阵,$\pi$为初始状态向量。

1.2 两个假设

齐次马尔可夫性假设

观测独立性假设

2. 三类问题

2.1 概率问题

已知HMM参数 $\lambda = (A,B,\pi)$,观测序列 ${o_1,o_2,…,o_t}$,求概率。

前向算法:

  1. $\alpha_1(i)=\pi_ib_i(o_1)$

  2. $\alpha_t(i)= \sum_{j=1}^N \Big[\alpha_{t-1}(j) a_{ji}\Big] b_i(o_t) $

  3. $P(O|\lambda)=\sum_{i=1}^N \alpha_T(i)$

后向算法:

  1. $\beta_T(i)=1$

  2. $\beta_t(i) = \sum_{i=1}^N a_{ij}b_j(o_{t+1})\beta_{t+1}(j)$

  3. $P(O|\lambda) = \sum_{i=1}^N \pi_ib_i(o_{1})\beta_1(i)$

可以得到推论:

  1. 第 t 时刻 状态为 i 的概率: $\gamma_t(i) = P(i_t=q_i) = \frac{\alpha_t(i)\beta(i)}{\sum_{i=1}^N\alpha_t(i)\beta(i)}$

  2. 第 t 时刻 状态为 qi 第 t+1 时刻状态为 qj 的概率:$\xi_t(i,j) = \frac{\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)}{\sum_{i=1}\sum_{j=1}\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)}$

2.2 学习问题

已知S个长度为T的观测序列 ${O_1,O_2,…,O_s}$,估计HMM的参数 $\lambda = (A,B,\pi)$ 。

鲍姆-韦尔奇算法

输入: ${(O_1,I_1),(O_2,I_2),…,(O_s,I_s)}$,其中任意一个观测序列$O_d = {o_1^{(d)},o_2^{(d)},…,o_T^{(d)}}$,对应的状态序列为$ I_d ={i_1^{(d)},i_2^{(d)},…,i_T^{(d)}} $

输出:$\lambda=(A,B,\pi)$

过程:

  1. 随机初始化$\pi_i,a_{ij},b_j(k)$

  2. 对每个样本,根据前向后向算法计算$\gamma_t^{(d)}(i)$,$\xi_t^{(d)}(i,j)$

  3. 更新模型参数:

  1. 迭代至收敛。

算法推导

E步,有期望表达式:

求其中的联合分布概率:

其条件概率有:

而$P(O|\lambda)$为常数(这里的O指的是所有的观测序列的集合),所以期望式等价于:

带入得:

M步,求参数:

同时,$\sum_{i=1}^N \tilde \pi_i=1$,由拉格朗日乘子法,得:

求偏导数,可以得到:

对i=1,..,N个式子求和,得:

带入以消去$\gamma$,得:

由前向后向算法得推论,得:

类似的,可以得到:

同样,可以得到:

b类似,不再赘述。

2.3 预测问题

已知HMM $\lambda = (A,B,\pi)$ 和观测序列 ${O_1,O_2,…,O_s}$,求最可能的状态序列。

方法:维特比算法—动态规划

思想:利用两个局部状态用于递推,$\delta_t(i)$存储在时刻t状态为i的所有可能路径中的概率最大值。$\Psi_t(i)$存储时刻t到状态i的所有 t-1 时刻的结点中概率最大的那个结点。

过程:

  1. 初始化局部状态:
  1. 运用动态规划进行递推:
  1. 计算T时刻最大的 $\delta_T(i)$,以 $\Psi_T(i)$为起始点,开始进行回溯,得到序列。

3. HMM用于中文分词

问题中,我们使用4种标签 {B,E,M,S},分别表示:

B:词语的开始

E:词语的结束

M:词语的中间部分

S:单个字组成的单词

这样的话,带标签的句子构成训练样本,句子为观测序列,标签为状态序列,通过BW算法可以得到$\lambda$的估计。

再使用HMM模型的维特比算法去对新来的句子进行分词预测,得到分词结果。

3.1 使用HMM进行词性标注

与分词同理,标签换为实体的类别就可以了。

3.2 使用HMM进行实体识别

其实一样,标签换为实体。给定一个词的序列,找出最可能的标签序列(内外符号:[内]表示词属于命名实体,[外]表示不属于)。如ICTCLAS实现的人名识别、翻译人名识别、地名识别都是用同一个Tagger实现的。

3.3 总结

HMM是一个通用的方法,可以解决贴标签的一系列问题。