阅读本文前,请先保证已经了解马尔科夫过程
模型介绍
隐马尔可夫过程(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) $
从定义知道,隐马尔科夫模型有两个基本假设:
- 齐次马尔可夫性假设:任意时刻t的状态,只与t-1状态有关,与其他时刻的状态无关。
- 观测独立性假设:t时刻的观测,只与t时刻的马尔可夫链有关。
3个基本问题
- 概率计算问题。给定模型$\lambda =(A,B,\pi)$和观测序列\(O=\{o_1,o_2,...,o_T\}\),求观测序列发生的概率$P(O\mid \lambda)$
- 学习问题。已知观测序列\(O=\{o_1,o_2,...,o_T\}\),估计模型$\lambda =(A,B,\pi)$中的参数,使得$P(O\mid \lambda)$最大(也就是MLE方法)
- 预测问题。已知模型$\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:预测问题
有两种解决此问题的算法
近似算法 :简单,但有误差的
维特比算法:用的是动态规划的原理。