【HMM】理论篇

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

模型介绍

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

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

变量定义

Q是所有隐藏状态的集合，V是所有可能地观测的集合
Q={q1,q2,...qN},V={v1,v2,...vM}Q={q1,q2,...qN},V={v1,v2,...vM}
N是所有可能地状态数，M是所有可能地观测数
AN×NAN×N是状态转移矩阵，BN×MBN×M是从状态生成观测的概率矩阵，ππ是初始状态概率
I={i1,i2,...,iT}I={i1,i2,...,iT}是状态序列，O={o1,o2,...,oT}O={o1,o2,...,oT}是观测序列，
一个隐马尔可夫模型表示为λ=(A,B,π)λ=(A,B,π)

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

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

3个基本问题

1. 概率计算问题。给定模型λ=(A,B,π)λ=(A,B,π)和观测序列O={o1,o2,...,oT}O={o1,o2,...,oT}，求观测序列发生的概率P(O∣λ)P(O∣λ)
2. 学习问题。已知观测序列O={o1,o2,...,oT}O={o1,o2,...,oT},估计模型λ=(A,B,π)λ=(A,B,π)中的参数，使得P(O∣λ)P(O∣λ)最大(也就是MLE方法)
3. 预测问题。已知模型λ=(A,B,π)λ=(A,B,π)，以及观测序列O={o1,o2,...,oT}O={o1,o2,...,oT}，求最可能的状态序列I={i1,i2,...,iT}I={i1,i2,...,iT}, 也就是使得P(I∣O)P(I∣O)最大的I

问题1：概率计算问题

直接法

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

前向算法

定义前向概率αt(i)=P(o1,o2,…ot,it=q∣λ)αt(i)=P(o1,o2,…ot,it=q∣λ)

前向算法对t=1:T-1，每步迭代求当前序列发生的概率
（算法略）
算法复杂度为O(N2T)O(N2T)

后向算法

定义后向概率βt(i)=P(ot+1,ot+2,…oT∣i=qi,λ)βt(i)=P(ot+1,ot+2,…oT∣i=qi,λ)

问题2：学习算法

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

监督学习法

已知{(O1,I1),(O2,I2),...,(OS,IS)}{(O1,I1),(O2,I2),...,(OS,IS)}
具体方法是记频数，然后用频数代替概率 (李航《统计学习方法》上写，这个方法是监督学习法，而且是极大似然估计法，我的理解是这样的：)

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

Baum-Welch算法

给定{O1,O2,...,OS}{O1,O2,...,OS},求λ=(A,B,π)λ=(A,B,π)的参数

用极大似然估计来求解。

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

问题3：预测问题

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

参考资料