0%

隐马尔科夫模型(HMM)

Posted on Edited on

隐马尔科夫模型(HMM)

  • 基于时序的概率模型

定义

$$
Q=[q_1,q_2…,q_N]是所有可能的状态集合 \qquad V=[v_1,v_2…v_M]是所有目标集合\
I=[i_1,i_2…i_T]表示长度为T的状态序列\qquad O=[o_1,o_2…o_T]表示长度为T的观测序列\
\
概率转移矩阵A=[a_{ij}]{n×n}\qquad a{ij}=P(i_{t+1}=q_j|i_{t}=q_i)\qquad(在t时刻)\
观测概率矩阵B=[b_j(k)]_{N×M}\qquad b_j(k)=P(o_t=v_k|i_t=q_j)\
初始状态概率向量\pi=(\pi_i)\qquad \pi_i=P(i_1=q_i)
$$

综上，HMM可以用模型$\lambda=(A,B,\pi)$表示

基本假设

  • 从定义可知，HMM做了两个基本的假设
    • 1、齐次马尔科夫性假设：假设HMM在任意时刻$t$只依赖于前的任意时刻
    • 2、观察独立性假设：假设任意观察序列只依赖于该时刻的状态与其他状态无关

三个基本问题

  • 1、概率计算问题：已知模型和观测序列，求在该模型下，观测序列出现的概率
  • 2、学习问题：已知观测序列估计模型参数，即用极大似然法估计参数
  • 3、预测问题：也称为解码问题。已知模型和观测序列，求最有可能的状态序列

一、概率计算问题

直接计算法

  • 列举所有可能的状态序列，然后求出状态序列的概率
  • 这样的时间复杂度是$O(TN^T)$级别的

前向算法

$$
设前向概率为\alpha_t(i)=P(o_1,o_2…,o_t,i_t=q_i|\lambda)\
显然有以下的递推公司\
a_{t+1}(i)=[\sum_{j=1}^N\alpha_t(j)a_{ji}]b_i(o_{t+1})\qquad \alpha_1(i)=\pi_ib_i(o_1)\
所以\
P(O|\lambda)=\sum_{i=1}^N \alpha_T(i)
$$

这样的时间复杂度是$O(TN^2)$级别的，这样的优化就在于，用一个递推状态来记录了前面搜索的结果，而不用像第一个方法一样重读搜索。

后向算法

  • 思想和前向的算法差不多，就是倒过来求

$$
设后向概率为\beta_t(i)=P(o_{t+1},o_{t+2},…,o_{T}|i_t=q_i,\lambda)\
\beta_{T}(i)=1\qquad 初始化\
\beta_t(i)=\sum_{j=1}^N a_{ij}b_j(o_{t+1})\beta_{t+1}(j)\
P(O|\lambda)=\sum_{i=1}^N \pi_ib_i(o_1)\beta_1(i)
$$

结合前向后向概率的一些计算

  • 1、给定模型和观测，计算时刻t时处于状态$q_i$的概率

    • 把式子化成上面$P(O|\lambda)$的形式

    • $$
      \gamma_t(i)=P(i_t=q_i|O,\lambda)=\frac{P(i_t=q_i,O|\lambda)}{P(O|\lambda)}=\frac{\alpha_t(i)\beta_t(i)}{\sum_{j=1}^N \alpha_t(j)\beta_t(j)}
      $$

  • 2、给定模型和观测，计算在时刻t处于状态$q_t$，在时刻t+1处于$q_j$的概率

    • 将t+1的状态空出来直接计算
      $$
      \xi_t(i,j)=P(i_t=q_i,i_{i+1}=q_j|O,\lambda)=\frac{P(i_t=q_i,i_{i+1}=q_j,O|\lambda)}{P(O|\lambda)}=\\frac{\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)}{\sum_{i=1}^N\sum_{j=1}^N \alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)}
      $$

  • 3、。。。。。。

二、学习问题

监督学习方法

  • 已知观察序列和状态序列$[(O_1,I_1),(O_2,I_2),…,(O_S,I_S)]$，然后我们利用极大似然估计来计算参数

  • 直接用频率估计即可

非监督学习方法(Baum-Welch算法)

  • 只有观察序列，并没有对应的状态序列。
  • 这种情况也就是假设状态序列是隐变量$I$，然后写出一个含隐变量的概率模型

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

  • 然后我们就可以用EM算法解决，所以其实Baum-Welch算法就是EM算法在HMM上的应用

    • EM算法简单来说就是，先明确隐函数是什么，然后把隐函数写进去写出对数似然，然后对隐变量取期望写出Q函数(E步),然后再极大化Q函数(M步)得到下一轮的参数初值