隐马尔科夫模型

1.隐马尔科夫模型的基本概念

1.1 模型的定义

  隐马尔科夫模型适用于标注问题的统计学习模型，描述由隐藏的马尔科夫链随机生成观测序列的过程，属于生成模型。
  隐马尔科夫模型是关于时序的概率模型，观测序列是观测变量，状态序列是隐变量，用观测序列求得状态序列(状态序列有时序性关系)

(1)隐马尔可夫模型用概率图模型来表示
(2)组成三要素

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

• 状态转移概率矩阵A
  A=[$a_{ij}$]_{N×N}                                                                     (1)
  $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×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_{i}$)
  $\pi_{i}$=P($i_{1}$=$q_{i}$),                         i=1,2,…,N
  是时刻t=1处于状态$q_{i}$的概率

  A和$\pi$确定了隐藏的马尔科夫链，生成不可观测的状态序列；B确定了如何从状态序列生成观测序列
(3)两个假设前提

• 齐次马尔可夫模型
  t时刻的状态只依赖前一时刻的状态
• 观测独立性假设
  t时刻观测只依赖于t时刻的状态

2.概率计算方法

介绍计算观测序列概率P(O|$\lambda$)

2.1 直接计算法

  状态序列 I=($i_{1}$,$i_{2}$,…,$i_{T}$)的概率：

  给定状态序列I=($i_{1}$,$i_{2}$,…,$i_{T}$),观测序列O=($o_{1}$,$o_{2}$,…,$o_{T}$)的概率：

  根据贝叶斯公式可得:

  根据联合概率求边缘概率可得：

  但是直接计算的复杂度太高，是O(T$N^{T}$)，算法不可行。

2.2 前向算法

(1)前向算法推导(递推部分)：
$\alpha_{t+1}$(i)=P($o_{1}$,$o_{2}$,…,$o_{t+1}$,$i_{t+1}$=$q_{i}$|$\lambda$)  (前向概率的定义)
           =$\sum^{N}_{j=1}$P($o_{1}$,$o_{2}$,…,$o_{t+1}$,$i_{t+1}$=$q_{i}$,$i_{t}$=$q_{j}$|$\lambda$)
           =$\sum^{N}_{j=1}$P($o_{1}$,$o_{2}$,…,$o_{t+1}$,$i_{t}$=$q_{j}$|$\lambda$)P($o_{t+1}$|$o_{1}$,$o_{2}$,…,$o_{t}$,$i_{t+1}$=$q_{i}$,$i_{t}$=$q_{j}$|$\lambda$)P($i_{t+1}$=$q_{i}$|$o_{1}$,$o_{2}$,…,$o_{t}$,$o_{t+1}$,$i_{t}$=$q_{j}$,$\lambda$)
  根据两个假设前提:t时刻的状态只依赖前一时刻的状态,和t时刻观测只依赖于t时刻的状态
           =$\sum^{N}_{j=1}$P($o_{1}$,$o_{2}$,…,$o_{t+1}$,$i_{t}$=$q_{j}$|$\lambda$)P($o_{t+1}$|$i_{t+1}$=$q_{i}$|$\lambda$)P($i_{t+1}$=$q_{i}$|$i_{t}$=$q_{j}$,$\lambda$)
           =$\sum^{N}_{j=1}$$\alpha_{t}$$a_{ji}$$b_{i}$($o_{t+1}$)

(2)观测序列概率的前向算法
  输入:隐马尔科夫模型$\lambda$,观测序列O
  输出:观测序列概率P(O|$\lambda$)

• 初值：$\alpha_{1}$=$\pi_i$$b_i$($o_i$)          ,i=1,2,…,N(N是状态数)
• 递推：$\alpha_{t+1}$(i)=[$\sum^{N}_{j=1}$$\alpha_{t}(j)$$a_{ji}$]$b_{i}$($o_{t+1}$)
• 终止：P(O|$\lambda$)=$\sum^{N}_{i=1}$$\alpha_{T}(i)$(T是最终的时刻)

(3)前向算法例题

• $\alpha_{1}$(2)：在t=1时，状态为2的概率
• $a_{12}$:下一时刻由状态1转换为状态2的概率
• $b_1$($o_2$):状态为1时生成t=2时刻观测的结果的概率
• $\pi_2$:t=1时刻状态为2的概率
  

2.3后向算法

  输入和输出同前向算法

• 初始值：$\beta_{T}$(i)=1,                   i=1,2,…,N
• 递推：$\beta_{t}$(i)=$\sum^{N}_{j=1}$$a_{ij}$$b_j$($o_{t+1}$)$\beta_{t+1}$(j),                   i=1,2,…,N
• 最终：P(O|$\lambda$)=$\sum^{N}_{i=1}$$\pi_{i}$$b_i$($o_1$)$\beta_{1}$(i)

2.4前向-后向算法

  前面步骤基本一致，是前向后向算法的总和，只是最终这里不同：
P(O|$\lambda$)=$\sum^{N}_{i=1}$$\sum^{N}_{j=1}$$\alpha_{ij}$$b_j$($o_{t+1}$)$\beta_{t+1}$(j),                   t=1,2,…,T

3.学习算法

3.1监督学习方法

给定的训练数据：S个长度相同的观测序列和对应的状态序列{($O_1$,$I_1$),($O_2$,$I_2$),…,($O_s$,$I_s$)}

• 转移概率$a_{ij}$的估计
  $a_{ij}$=$A_{ij}$/$\sum^{N}_{j=1}$$A_{ij}$
  分子：样本中状态i到下一时刻转移到状态j的频数
  分母：样本中状态i到下一时刻转移到所有状态的频数

• 观测概率$b_j$(k)的估计
  $b_j$(k)=$B_{jk}$/$\sum^{k=1}_{M}$$B_{jk}$
  分子：样本中状态j观测为k的频数
  分母：样本中状态j观测为所有的频数

• 初始状态概率$\pi_{i}$
  例：10个样本，3个样本的初始状态为$q_1$,那么$\pi_1$=$\frac{3}{10}$

3.2Baum-Welch算法(无监督学习)

给定训练数据：S个观测序列{$O_1$,$O_2$,…,$O_s$}
(1)BW算法

• E步：
  EM算法的Q函数：

  Q(θ,$θ^{(i)}$) = $\sum_{Z}$P(Z|Y,$θ^{(i)}$) log[P(Y|Z,θ)P(Z|θ)]
                   = $\sum_{Z}$P(Z|Y,$θ^{(i)}$) logP(Y,Z|θ)
                   = $E_{Z}$[P(Z|Y,$θ^{(i)}$) logP(Y,Z|θ)]

  BW算法的Q函数(两者是有区别的)：

  Q(λ,$λ^{'}$) = $\sum_{I}$ logP(O,I|λ)P(O,I|$\lambda^{'}$)      (省略了一个常数因子1/P(O|$\lambda^{'}$))

• M步：
  分别对三个模型参数进行求导=0

(2)BW算法流程
输入：观测数据O
输出：隐马尔科夫模型参数

• 初始化：n=0,选取$a^{(0)}_{ij}$,$b^{0}_{j}$(k),$\pi^{(0)}_{i}$

• 递推：n=1,2,…,
  $\pi^{(n+1)}_{i}$=P(O,$i_1$=i|$\lambda^{'}$)/P(O|$\lambda^{'}$)
             =P($i_1$=i|O,$\lambda^{'}$)
             =$\gamma_1$(i)
  $\gamma_1$(i)：给定模型$\lambda^{'}$和观测O,在时刻t=1时处于状态i的概率

  
  

  $a^{(n+1)}_{ij}$=$\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^{'}$)
             =$\sum^{T-1}_{t=1}$$\xi_{t}$(i,j)/$\sum^{T-1}_{t=1}$$\gamma_t$(i)
  $\xi_{t}$(i,j):给定模型$\lambda$和观测O,状态$q_i$在下一时刻转换为$q_i$的概率
  $\sum^{T-1}_{t=1}$$\xi_{t}$(i,j)：在观测O下由状态i转移到状态j的期望值
  $\sum^{T-1}_{t=1}$$\gamma_t$(i)：在观测O下由状态i转移的期望值

  
  

  $b^{(n+1)}_j$(k)=$\sum^{T}_{t=1}$P(O,$i_t$=j|$\lambda^{'}$)I($o_t$=$v_k$)/$\sum^{T}_{t=1}$P(O,$i_t$=j|$\lambda^{'}$)

                 =$\sum^{T}_{t=1,o_t=v_k}$$\gamma_t$(j)/$\sum^{T}_{t=1}$$\gamma_t$(j)
  $\sum^{T}_{t=1}$$\gamma_t$(j):观测O下状态i出现的期望
  
  

• 最终：得到模型参数

4. 预测算法

当我们有了模型$\lambda$=(A,B,$\pi$)和观测序列O，就可以来预测最有可能的状态序列I了

4.1近似算法

t时刻处于状态$q_i$的概率为:
$\gamma_t$(i)=P(O,$i_t$=$q_i$|$\lambda$)/P(O|$\lambda$)
       =P($o_1$,$o_2$,…,$o_t$,$i_t$ =$q_i$|$\lambda$)/P($o_{t+1}$,$o_{t+2}$,…,$o_T$|$o_1$,$o_2$,…,$o_t$,$i_t$=$q_i$,$\lambda$)
       =P($o_1$,$o_2$,…,$o_t$,$i_t$=$q_i$|$\lambda$)/P($o_{t+1}$,$o_{t+2}$,…,$o_T$|$i_t$=$q_i$,$\lambda$)
       =$\alpha_t$(i)$\beta_t$(i)/$\sum^{N}_{j=1}$$\alpha_t$(j)$\beta_t$(j)     (求和是所有状态)

t时刻最有可能的状态是： $i^{*}_{t}$= arg $max_{1≤i≤N}$ [$\gamma_t$(i)]        ,t=1,2,…,T

从而得到状态序列： $I^*$=($i^{*}_{1}$,$i^{*}_{2}$,…,$i^{*}_{T}$)

缺点：存在转移概率为0的相邻状态,无法解决。

4.2维特比算法

(1)维特比算法的参数
实质：动态规划求解概率最大路径
t时刻最有可能在哪个状态的可能性：$\delta_{t}$(i)=$max_{i_1,i_2,...,i_{t-1}}$P($i_t$=i,$i_{t-1}$,…,$i_1$,$o_t$,…,$o_1$|$\lambda$)
t时刻最有可能是哪个状态：$\varphi_t$(i)=arg $max_{1≤j≤N}$ [$\delta_{t-1}$(i)$a_{ji}$]

(2)维特比算法流程
输入：模型$\lambda$和观测O
输出：最优路径 $I^*$=($i^*_1$,$i^*_2$,…,$i^*_T$)

• 初始化：$\delta_1$(i)=$\pi_i$$b_i$($o_1$)         ,i=1,2,…,N
                $\varphi_1$(i)=0           ,i=1.2,…,N
• 递推：$\delta_{t}$(i)=$max_{1≤j≤N}$ [$\delta_{t-1}$(j)$a_{ji}$]$b_i$($o_t$)        ,i=1,2,…,N
            $\varphi_t$(i)=arg $max_{1≤j≤N}$ [$\delta_{t-1}$(i)$a_{ji}$]        ,i=1,2,…,N
• 最终：$P^*$=$max_{1≤j≤N}$ $\delta_{T}$(i)
              $i^*_T$=arg $max_{1≤j≤N}$ [$\delta_{T}$(i)]
• 最优路径回溯：$i^*_t$=$\varphi_{t+1}$($i^*_{t+1}$)
         最优路径：$I^*$=($i^*_1$,$i^*_2$,…,$i^*_T$)

(3)典型例题