【HMM】理论篇



2017年11月11日    Author:Guofei

文章归类: 0x21_有监督学习    文章编号: 280

版权声明:本文作者是郭飞。转载随意,但需要标明原文链接,并通知本人
原文链接:https://www.guofei.site/2017/11/11/hiddenmarkov.html


阅读本文前,请先保证已经了解马尔科夫过程

模型介绍

隐马尔可夫过程(HMM, Hidden Markov Model)用于描述由隐藏的马尔可夫链生成贯彻序列的过程1

隐藏的马尔科夫链随机生成序列,称为 状态序列(state sequence)
每个状态生成一个观测,观测组成的的序列,称为 observation sequence

变量定义

Q是所有隐藏状态的集合,V是所有可能地观测的集合
\(Q=\{ q_1,q_2,...q_N\}, V=\{v_1,v_2,...v_M\}\)
N是所有可能地状态数,M是所有可能地观测数
$A_{N\times N}$是状态转移矩阵,$B_{N\times M}$是从状态生成观测的概率矩阵,$\pi$是初始状态概率
\(I=\{i_1,i_2,...,i_T\}\)是状态序列,\(O=\{o_1,o_2,...,o_T\}\)是观测序列,
一个隐马尔可夫模型表示为$\lambda =(A,B,\pi) $

从定义知道,隐马尔科夫模型有两个基本假设:

  1. 齐次马尔可夫性假设:任意时刻t的状态,只与t-1状态有关,与其他时刻的状态无关。
  2. 观测独立性假设:t时刻的观测,只与t时刻的马尔可夫链有关。

3个基本问题

  1. 概率计算问题。给定模型$\lambda =(A,B,\pi)$和观测序列\(O=\{o_1,o_2,...,o_T\}\),求观测序列发生的概率$P(O\mid \lambda)$
  2. 学习问题。已知观测序列\(O=\{o_1,o_2,...,o_T\}\),估计模型$\lambda =(A,B,\pi)$中的参数,使得$P(O\mid \lambda)$最大(也就是MLE方法)
  3. 预测问题。已知模型$\lambda =(A,B,\pi)$,以及观测序列\(O=\{o_1,o_2,...,o_T\}\),求最可能的状态序列\(I=\{i_1,i_2,...,i_T\}\), 也就是使得$P(I\mid O)$最大的I

问题1:概率计算问题

直接法

这是一个不太可行的方法。
先算出所有状态的概率,再求出所有观测的概率。
最后加总
算法复杂度$O(TN^T)$

前向算法

定义前向概率$\alpha_t(i)=P(o_1,o_2,…o_t,i_t=q\mid \lambda)$

前向算法对t=1:T-1,每步迭代求当前序列发生的概率
(算法略)
算法复杂度为$O(N^2T)$

后向算法

定义后向概率$\beta_t(i)=P(o_{t+1},o_{t+2},…o_T\mid i=q_i,\lambda)$

问题2:学习算法

包括监督学习法和Baum-Welch算法(也就是EM算法)

监督学习法

已知\(\{(O_1,I_1),(O_2,I_2),...,(O_S,I_S)\}\)
具体方法是记频数,然后用频数代替概率 (李航《统计学习方法》上写,这个方法是监督学习法,而且是极大似然估计法,我的理解是这样的:)

  • 叫做监督学习法,是因为需要取得状态数据,这往往需要很大的代价。
  • 叫做极大似然估计法,是因为记频数这种方法可以使似然值最大化。

Baum-Welch算法

给定\(\{O_1,O_2,...,O_S\}\),求$\lambda=(A,B,\pi)$的参数

用极大似然估计来求解。

在求最优似然值时,用EM算法

问题3:预测问题

有两种解决此问题的算法
近似算法 :简单,但有误差的
维特比算法:用的是动态规划的原理。

参考资料


您的支持将鼓励我继续创作!