欢迎光临 x-algo
关注算法在工业界应用
Hi, 这是一个关注大数据算法在工业界应用的网站

HMM(hidden Markov model)隐马尔科夫模型

隐马尔科夫模型(后面简称隐马)适用于标注问题的统计学习模型,属于生成模型,隐马的三个基本问题:概率计算问题、算法学习问题、预测问题。隐马在分词、词性标注、语音识别等领域有这广泛的应用。

模型定义

定义(隐马尔科夫模型):隐马是关于时序的概率模型,描述由一个隐藏的『马尔科夫链』随机生成『不可观测的状态随机序列』,再由个个状态生成一个『可观测随机序列』的过程,序列的每一个位置可以看做一个时刻。

用一个有向图可以表示为:

马尔科夫模型定义

隐马是一个生成模型,每一个隐含状态只和前一个状态有关(一阶隐马),每一个观测状态只和对应的一个隐含状态有关。

图中的每一个节点(包括观测节点和隐含节点)是一个随机变量,实际应用中,随机变量的取值是离散的。例如NLP词性标注处理过程中,隐含状态是等待标注的词性,观测状态是观测到的句子(分词的结果)。

例如对句子『教授喜欢画画』进行词性标注,分词之后的结果可能是『教授/喜欢/画/画』,『教授』词性可以是名词和动名词,『喜欢』词性可以是动词和动名词,『画』词性可以是名词和动词,画成图可以表示为:

hmm词性标注例子

隐马是个生成模型,生成的过程是先生成状态节点,根据状态节点再生成观测节点。结合上图,生成过程可以通俗的解释成下面过程:首先先生成『教授』词性是『名词』,然后生成词『教授』;接着根据『教授』的词性节点『名词』生成『喜欢』的词性节点『动词』,然后生成词『喜欢』;接着根据『喜欢』的词性『动词』生成『画』的词性『动词』,然后生成词『画』,最后一个『画』也是这个逻辑。

隐马的两个基本假设

上述的生成过程,其实包含了两个基本假设:

(1)齐次马尔科夫假设:即假设隐藏的马尔科夫链在任一个时刻t的『隐含状态』只依赖前一个时刻的『隐含状态』,与其他时刻的『隐含状态』和『观测状态』无关。通过公式可以表示为:

\(P(i_t|i_1,i_2,...,i_T; o_1,o_2,...,o_T) = P(i_t|i_{t-1})\)

(2)观测独立性假设:即任意时刻的『观测状态』只依赖该时刻的『隐含状态』,与其他状态无关。通过公式可以表示为:

\(P(o_t|i_1,i_2,...,i_T; o_1,o_2,...,o_T) = P(o_t|i_{t})\)

隐马的参数表示

隐马有三类参数

(1)『隐含状态』转移矩阵A

(2)『隐含状态』初始状态分布 \(\pi\)

(3)『隐含状态』生成『观测状态』的矩阵B

隐马模型参数表示形式为:

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

隐马的三个基本问题

在隐马的实际使用中,需要解决隐马的一个或多个基本问题。

三个基本问题为:

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

(2)学习问题,已知观测序列 \( O = (o_1,o_2,...,o_T)\) ,估计模型参数 \(\lambda = (A,B,\pi)\) ,使得在该模型下观测序列概率 \(P(O|\lambda)\) 最大。即用极大似然估计的方法估计参数。

(3)预测问题,也称为解码(decoding)问题,已知模型 \(\lambda = (A,B,\pi)\) 和观测序列 \( O = (o_1,o_2,...,o_T)\) ,求最有可能的隐含状态序列。模型确定后,词性标注就是解决此问题。

概率计算问题

给定模型和观测序列,计算此观测序列的概率,对应上面词性标注的图中例子来说,就是已知『词性转移概率』和『词性生成词』的概率,求给定句子生成的概率。简单的做法就是枚举16种词性序列方案(每一种方案概率不同),然后计算每种方案生成句子的概率,将其加到一起就可以了。这种方案明显太笨了,是状态数的指数级的复杂度。一种优化的方法就是使用动态规划的方法,f(t,i)表示t时刻隐含状态是i结尾,生成前t个观测序列的概率和,递推公式可以写为:

\(f(t,i)=\left\{\begin{matrix}\pi_iB_{i,o_t} \ \ \ \ \ \ &t=1 \\\left[\sum_j^C{f(t-1,j)A_{j,i}} \right] B_{i,o_{t+1}} \ \ \ \ \ \ \ \ &t=2,3,...,T \end{matrix}\right.\)

最终求一下和就可以了:

\(P(O|\lambda)=\sum_{i=1}^N{f(T,i)}\)

其中C表示所有隐含状态数。

预测问题

预测问题是在确定模型 \(\lambda = (A,B,\pi)\) 和观测序列 \( O = (o_1,o_2,...,o_T)\) 的情况下,求当前『观测序列』最优可能的『隐含状态序列』的问题。

针对词性标注的问题,『预测问题』就是已知『句子』求这个句子的词性标注序列。简单暴力的方法当然是枚举16中可能的词性,分别计算其概率,然后选择概率最大的那一个标注序列。类似『概率计算问题』,接下来这个算法是一种更快的动态规划算法——维特比算法(Viterbi Algorithm)。

f(t,i)表示t时刻隐含状态是i结尾,生成前t个观测序列的最大概率,递推公式可以写为:

\(f(t,i)=\left\{\begin{matrix}\pi_iB_{i,o_t} \ \ \ \ \ \ &t=1 \\\left[\max_{1 \le j \\e C}{f(t-1,j)A_{j,i}} \right] B_{i,o_{t+1}} \ \ \ \ \ \ \ \ &t=2,3,...,T \end{matrix}\right.\)

 这个方法和第一个基本问题『概率计算问题』区别很小,第一个问题是求和,这个问题是求极值。由于最终是要选择出来一种最优的『词性标注序列』,所以每一步计算的过程中要记录下来每一个时刻每一个状态概率最大的前一个节点,方便最后在O(T)的时间找到最优的序列。

学习问题

隐马尔科夫模型的学习,可以根据训练是只包含『观测序列』还是既包含『观测序列』也包含『隐含状态序列』,分别使用非监督学习和监督学习实现,非监督的学习算法是Baum-Welch算法(EM算法)。

有监督学习方法

由于『隐含状态序列』已知,这里有监督的方法是使用极大似然估计的方法,其实大白话就是直接『计数』即可。只要是涉及到『计数』代表概率的场景,现实中往往使用一些平滑算法修正,词性标注中如果不加平滑,效果有可能简直差到不能看。

(1)计数统计『隐含状态』转移矩阵A:

\(A_{i,j} = \frac{N_{i,j}}{\sum_{j=1}{C}N_{i,j}}\)

(2)计数统计发射矩阵B(隐含状态生成观测状态的概率):

\(B_{i,k} = \frac{N_{i,k}}{\sum_{k=1}^{M}{N_{i,k}}}\)

(3)初始状态概率 \(\pi_i\) 的概率估计是统计S个样本中,初始状态为i的频率。

无监督Baum-Welch算法

仔细体会隐马的生成过程,应该不难发现其生成过程和LDA类似,再生成观测序列之前,都是先生成『隐含状态』,再通过『隐含状态』生成『观测状态』,并且损失函数都是极大似然。

假定训练数据只包含S个长度为T的观测序列 \((O_1,O_2,O_3,...,O_S)\) ,『隐含状态序列』看做是不可观测的因变量I,隐马可以看做是一个含有隐含变量的生成模型,其参数学习可以通过EM算法实现,模型可以表示为:

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

似然函数可以写成:

\(\begin{matrix}L_{\lambda} &=& log{\prod_{s=1}^{S}{P(O_s|\lambda)} }\\&=& \sum_{s=1}^S{\log{P(O_s|\lambda)}}\end{matrix}\)

下面就是如何求参数的问题了。接下来不打算推公式了,而是从模型生成过程直观的理解公式推导的过程,理解算法、模型最重要的就是理解其物理意义,接下来忘掉似然函数,忘掉EM算法,只记住这个生成过程即可。

我们只知道观测序列,目标是如何预估生成过程的三个参数 \((A,B,\pi)\)

(1)每个句子,随机初始化一种『隐含状态序列』

(2)通过计数的方式统计出来三个参数(其实就是上面有监督的方法),判断三个参数是否符合迭代终止条件,如果不符合就执行步骤(3)。

(3)对句子 \(O_s\) ,利用上一步的三个参数,计算每一种『隐含状态序列』生成 \(O_s\) 的概率,按照这个概率分布选择一种『隐含状态序列』作为句子 \(O_s\) 的新隐含状态。跳到第(2)步执行。

接下来看看EM的公式吧:

E-step

\(\gamma_t(i) = \frac{\alpha_t(i)\beta_t{(i)}}{p(O|\lambda)} = \frac{\alpha_t(i)\beta_t{(i)}}{\sum_{j=1}^{C}{\alpha_t(j)\beta_t{(j)}}}\)

\(\begin{matrix} \xi_t{(i,j)}=& \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}^C \sum_{j=1}^CP(i_t=q_i,i_{t+1}=q_j,O|\lambda)}\\=& \frac{\alpha_t(i)a_{i,j}b_j(o_{t+1}) \beta_{t+1}(j)}{\sum_{i=1}^C\sum_{j=1}^C\alpha_t(i)a_{i,j}b_j(o_{t+1}) \beta_{t+1}(j)}\end{matrix}\)

M-step:

\(A_{i,j} = \frac{\sum_{i=1}^{T-1}\xi_t(i,j)}{\sum_{t=1}^{T-1}\gamma_t(i)}\)

\(B_{j,k}=\frac{\sum_{t=1,o_t=v_k}^{T}\gamma_t(j)}{\sum_{t=1}^{T}\gamma_t(j)}\)

\(\pi_i=\gamma_1(i)\)

其中, \(\gamma_t(i)\) 表示t时刻处于状态i的概率, \(\xi_t(i,j)\) 表示t时刻处于i状态,t+1时刻处于j状态的概率。 \(\alpha_t(i)\) 表示前向概率, \(\beta_t(j)\) 表示后向概率。

参考资料

李航《统计学习方法》

冯志伟《自然语言处理简明教程》

未经允许不得转载:大数据算法 » HMM(hidden Markov model)隐马尔科夫模型

分享到:更多 ()

评论 抢沙发

*

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

关注大数据算法在工业界应用

本站的GitHub关于本站