统计学习方法-隐马尔可夫模型（HMM）-读书笔记

• • 1、前言
  • 2、隐马尔可夫模型
  • • 2.1隐马尔科夫模型的定义
    • 2.2 HMM的两个假设
  • 3、HMM的三个基本问题
  • • 3.1概率计算问题
    • • 3.11直接计算法
      • 3.12前向算法
      • 3.13后向算法
    • 3.2学习算法
    • • 3.21监督学习方法
      • 3.22无监督学习方法-Baum-Welch算法
    • 3.3预测算法
    • • 3.31近似算法
      • 3.32维比特算法

1、前言

隐马尔科夫模型(hidden Markov model,HMM)是用于标注问题的统计学习模型，描述由隐藏的马尔可夫链随机生成观测序列的过程，属于生成模型。隐马尔科夫模型在语音识别、自然语言处理、生物信息、模式识别等领域都有着广泛的应用。

2、隐马尔可夫模型

2.1隐马尔科夫模型的定义

隐马尔可夫模型是关于时序的概率模型，描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测从而产生观测随机序列的过程。隐藏的马尔可夫链随机生成的转台序列称为状态序列(state sequence)；每个状态生成一个观测，由此产生观测的随机序列，称为观测序列。

隐马尔可夫模型由初始概率向量 π \pi π，状态转移概率矩阵A和观测概率矩阵B决定。 π \pi π和A决定状态序列，B决定观测序列。HMM模型 λ \lambda λ可以用三元符号表示即 λ = ( A , B , π ) \lambda=(A,B,\pi) λ=(A,B,π),三者称为HMM模型的三要素。

设Q是所有可能的状态的集合，V是所有可能的观测的集合，观测状态v可见，状态q不可见。I是长度为T的状态序列，O是对应的观测序列

1、定义状态转移概率矩阵A如下：

A = [ a i j ] N ∗ N A=[a_{ij}]_{N*N} A=[aij​]N∗N​

其中 a i j = P ( i t + 1 = q j ∣ i t = q i ) a_{ij}=P(i_{t+1}=q_j|i_t=q_i) aij​=P(it+1​=qj​∣it​=qi​),是在时刻t处于状态qi的条件下在时刻t+1转移到状态qj的概率。

2、观测概率矩阵B定义如下

B = [ b j ( k ) ] N ∗ M B=[b_j(k)]_{N*M} B=[bj​(k)]N∗M​

其中， b j ( k ) = P ( o t = v k ∣ i t = q j ) b_j(k)=P(o_t=v_k|i_t=q_j) bj​(k)=P(ot​=vk​∣it​=qj​),是在时刻t处于状态qj的条件下生成观测vk的概率。

3、 π \pi π是初始概率向量。

2.2 HMM的两个假设

1、齐次马尔可夫性假设。即隐藏的马尔可夫链在任意时刻t的状态只与前一时刻的状态有关，与其他时刻的状态及观测无关，也与时刻t无关。

2、观测独立性假设。即任意时刻的观测只和该时刻的马尔可夫链的状态有关，与其他观测及状态无关。

3、HMM的三个基本问题

3.1概率计算问题

给定模型 λ = ( A , B , π ) \lambda=(A,B,\pi) λ=(A,B,π)和观测序列O，计算在模型 λ \lambda λ下观测序列O出现的概率 P ( o ∣ λ ) P(o|\lambda) P(o∣λ)

3.11直接计算法

列举所有长度为T的状态序列I，然后求出I与观测序列O的联合概率，最后再对所有可能的状态序列求和。

P ( O , I ∣ λ ) = ∑ I P ( O ∣ I , λ ) P ( I ∣ λ ) P(O,I|\lambda)=\sum_{I}{P(O|I,\lambda)}P(I|\lambda) P(O,I∣λ)=I∑​P(O∣I,λ)P(I∣λ)

总体时间复杂度是** O ( T N T ) O(TN^T) O(TNT)**

3.12前向算法

**前向概率：**定义给定隐马尔可夫模型 λ \lambda λ，定义到时刻t为止的观测序列为o1,o2,ot且状态为qi的概率为前向概率，记作

α t ( i ) = P ( o 1 , o 2 , . . . o t , i t = q i ∣ λ ) {\alpha}_t(i)=P(o_1,o_2,...o_t,i_t=q_i|\lambda) αt​(i)=P(o1​,o2​,...ot​,it​=qi​∣λ)

输入：模型 λ \lambda λ，观测序列O

输出：观测序列概率 P ( O ∣ λ ) P(O|\lambda) P(O∣λ)

（1）初值

α 1 ( i ) = π i b i ( o 1 ) {\alpha}_1(i)={\pi}_ib_i(o_1) α1​(i)=πi​bi​(o1​)

(2) 递推

α t + 1 ( i ) = [ ∑ j = 1 N α t ( j ) a j i ] b i ( o t + 1 ) {\alpha}_{t+1}(i)=[\sum_{j=1}^N{{\alpha}_t(j)a_{ji}}]b_i(o_{t+1}) αt+1​(i)=[j=1∑N​αt​(j)aji​]bi​(ot+1​)

(3)终止

P ( O ∣ λ ) = ∑ i = 1 N α T ( i ) P(O|\lambda)=\sum_{i=1}^N{\alpha}_T(i) P(O∣λ)=i=1∑N​αT​(i)

总体时间复杂度是** O ( N 2 T ) O(N^2T) O(N2T)**

3.13后向算法

**后向概率：**定义给定HMM模型 λ \lambda λ，定义在时刻t状态为qi的条件下，从t+1到T的部分观测序列为ot+1,ot+2的概率为后向概率，记作

β t ( i ) = P ( o t + 1 , o t + 2 , o T ∣ i t = q i , λ ) {\beta}_t(i)=P(o_{t+1},o_{t+2},o_T|i_t=q_i,\lambda) βt​(i)=P(ot+1​,ot+2​,oT​∣it​=qi​,λ)

输入：模型 λ \lambda λ，观测序列O

输出：观测序列概率 P ( O ∣ λ ) P(O|\lambda) P(O∣λ)

（1）初值

β T ( i ) = 1 {\beta}_T(i)=1 βT​(i)=1

根据定义，从T+1到T的部分观测序列其实不存在，所以硬性规定这个值是1

（2）递推

对t=T-1,T-2…1

β t ( i ) = ∑ j = 1 N a i j b j ( o t + 1 ) β t + 1 ( j ) {\beta}_t(i)=\sum_{j=1}^N{a_{ij}b_j(o_{t+1}){\beta}_{t+1}(j)} βt​(i)=j=1∑N​aij​bj​(ot+1​)βt+1​(j)

（3）终止

P ( O ∣ λ ) = ∑ i = 1 N π i b i ( o 1 ) β 1 ( i ) P(O|\lambda)=\sum_{i=1}^N{{\pi}_ib_i(o_1){\beta}_1(i)} P(O∣λ)=i=1∑N​πi​bi​(o1​)β1​(i)

3.2学习算法

已知观测序列O，估计模型 λ \lambda λ参数，使得在该模型下观测序列概率 P ( O ∣ λ ) P(O|\lambda) P(O∣λ)最大。

3.21监督学习方法

使用极大似然估计进行估计HMM的参数。

1、转移概率aij的估计

设样本中时刻t处于状态i时刻t+1转移到状态j的频数为Aij,那么状态转移概率aij的估计是

a ^ i j = A i j ∑ j = 1 N A i j \hat{a}_{ij}=\frac{A_{ij}}{\sum_{j=1}^N{A_{ij}}} a^ij​=∑j=1N​Aij​Aij​​

2、观测概率bj(K)的估计

设样本中状态为j并观测为k的频数是B_{jk}，那么状态为j观测为k的概率的估计是

b ^ j ( k ) = B j k ∑ k = 1 M B j k \hat{b}_j(k)=\frac{B_{jk}}{\sum_{k=1}^M{B_{jk}}} b^j​(k)=∑k=1M​Bjk​Bjk​​

3.22无监督学习方法-Baum-Welch算法

将观测序列数据看作观测数据O，状态序列数据看作不可观测的隐数据I，首先确定完全数据的对数似然函数KaTeX parse error: Undefined control sequence: \logP at position 1: \̲l̲o̲g̲P̲(O,I|\lambda),

由EM算法实现，求Q函数

Q ( λ , λ ^ ) = ∑ I log ⁡ π i 1 P ( O , I ∣ λ ) + ∑ I ( ∑ t = 1 T − 1 log ⁡ a i t i t + 1 ) P ( O , I ∣ λ ) + ∑ I ( ∑ t = 1 T log ⁡ b i t ( o t ) ) P ( O , I ∣ λ ) Q(\lambda,\hat{\lambda})=\sum_{I}{\log {\pi}_{i1}}P(O,I|\lambda)+\sum_{I}{(\sum_{t=1}^{T-1}{\log a_{i_ti_{t+1}}})P(O,I|\lambda)}+\sum_{I}(\sum_{t=1}^T{\log b_{i_t}(o_t)})P(O,I|\lambda) Q(λ,λ^)=I∑​logπi1​P(O,I∣λ)+I∑​(t=1∑T−1​logait​it+1​​)P(O,I∣λ)+I∑​(t=1∑T​logbit​​(ot​))P(O,I∣λ)

EM算法M步，极大化Q函数，求模型参数A,B， π \pi π

用拉格朗日乘子法极大化Q函数求模型参数

a i j = ∑ t = 1 T − 1 P ( O , i t = i , i t + 1 = j ∣ λ ) ∑ t = 1 T − 1 P ( O , i t = i ∣ λ ) a_{ij}=\frac{\sum_{t=1}^{T-1}{P(O,i_t=i,i_{t+1}=j|\lambda)}}{\sum_{t=1}^{T-1}{P(O,i_t=i|\lambda)}} aij​=∑t=1T−1​P(O,it​=i∣λ)∑t=1T−1​P(O,it​=i,it+1​=j∣λ)​

b j ( k ) = ∑ t = 1 T P ( O , i t = j ∣ λ ) I ( o t = v k ) ∑ t = 1 T P ( O , i t = j ∣ λ ) b_j(k)=\frac{\sum_{t=1}^T{P(O,i_t=j|\lambda)I(o_t=v_k)}}{\sum_{t=1}^T{P(O,i_t=j|\lambda)}} bj​(k)=∑t=1T​P(O,it​=j∣λ)∑t=1T​P(O,it​=j∣λ)I(ot​=vk​)​

π i = P ( O , i 1 = i ∣ λ ) P ( O ∣ λ ) {\pi}_i=\frac{P(O,i_1=i|\lambda)}{P(O|\lambda)} πi​=P(O∣λ)P(O,i1​=i∣λ)​

3.3预测算法

也称解码问题，已知模型 λ \lambda λ和观测序列O，求对给定观测序列条件概率P（I|O）最大的状态序列I。

3.31近似算法

在每个时刻t选择在该时刻最有可能出现的状态，从而得到一个状态序列作为预测的结果，优点是计算简单，缺点是不能保证状态序列整体是最有可能的状态序列。（贪心的思想）

3.32维比特算法

动态规划的思想

递推地计算各部分路径的最大概率，存储状态转移过程中概率最大路径的前一个状态j，每一次状态更新记录概率值，最终求出最优路径概率。