HMM——隐马尔可夫模型
HMM模型
1. 概述
首先需要明确的是HMM不是算法,它本质上是一个模型,但是借助该模型能够解决三种问题,概括而言,隐马尔科夫模型针对的三类问题为
1)求解概率问题
2)求解模型参数问题
3)预测问题
这三类问题的解决都是建立在模型的三个参数上的,常见的HMM有关的模型描述中都会出现同一句话“给定HMM模型 λ=(A, B, π)”,这一句话中即已经包含HMM模型所涉及到的三个关键参数,对三个参数的解释首先需要通过隐马尔科夫链进行说明,
隐马尔可夫链在实际问题中常常是由两部分组成,假设总的时刻长度为T,从开始到最终T时刻的时间里,会出现如下两条链,
序列链 | 含义 |
---|---|
观测序列链 | 每个时刻观察到的观测值,O={O1, O2, O3, ……, OT} |
状态序列链 | 每个时刻观测时的状态,I={I1, I2, I3,……, IT} |
由这两条链引出了HMM模型的三个重要参数,A、B和π,下面是对每个参数的解读,
参数 | 含义 | 解释 |
---|---|---|
A | 状态转换矩阵 | t时刻观测值Ot对应的状态It,t+1时刻观测值Ot+1对应的状态It+1,HMM的基本假设之一是“当前状态仅与上一时刻状态有关”,所以由 It转到任何一种可能的t+1时刻的状态 It+1的概率会形成一个矩阵。假设整个观测过程可能存在n种状态,则状态转换矩阵的维度为n×n。 |
B | 观测概率矩阵 | 假设整个过程中观测值可能有m种不同的情况,t时刻时候状态为 It,这一状态下每一种观测值都有其出现的的可能性。假设整个观测过程存在n种状态,则观测矩阵的维度为n×m。 |
π | 初始概率矩阵 | 在t=1时,状态为I1,整个观测过程的n种状态都可能在t=1时刻出现,但是每种状态的初始概率可能不同,所以形成了一个维度为 1×n的初始概率矩阵,表示每种状态作为I1出现的概率。 |
以一个3种可能状态,4种可能观测的HMM模型作为示范,
有了隐马尔科夫链和三个参数的概念,就能够解决三个重要的问题。
解决问题1:概率求解问题
概率求解问题的条件:给定HMM模型λ=(A, B, π),同时给定观测序列 O={O1, O2, O3, ……, OT},求某一时刻t的状态为 qi 的概率。这一概率又分为前向概率和后向概率,对这两种概率进行说明,
概率 | 说明 | 符号表示 |
---|---|---|
前向概率αt(i) | 给定模型λ=(A, B, π)的条件下,从开始到t时刻的观测序列为 O={O1, O2, O3, ……, Ot},且t时刻状态为 qi 的概率。 | P(O1,O2,O3,……Ot, It=qi | λ) |
后向概率βt(i) | 给定模型λ=(A, B, π),且t时刻状态为 qi的条件下,从t时刻开始到T时刻的观测序列 O={Ot+1, Ot+2, Ot+3, ……, OT}的概率。 | P(Ot+1,Ot+2,Ot+3,……OT | It=qi, λ) |
对于这两种概率分别进行推导。
前向概率
前向概率的说明如上表所示,一般情况下,将 P(O1,O2,O3,……Ot, It=qi | λ) 表示为αt(i),求解前向概率有两种计算方式,
1)暴力求解
这种计算方式理论上是可行的,但是在实际的操作过程中如果观测序列极长,此时就会出现内存不够用的情况,由此引出了更简洁的计算方式。
2)前向算法
后向概率
后向概率的说明如上表所示,一般情况下,将 P(Ot+1,Ot+2,Ot+3,……OT | It=qi, λ) 表示为βt(i)。,后向概率的推导过程比前向概率复杂,下面的推导过程可以多看几次,对理解后向概率的推导很有帮助。
后向概率推导建立在两个假设上面,
假设1:当前时刻的状态仅与前一时刻有关。
假设2:当前时刻的观测结果仅与当前时刻的状态有关,与其他时刻观测无关。
(一定要记住这两个假设,它们在推导过程中很重要)
具体的推导过程如下,前向概率从t=0时刻开始推导,后向概率与之相反,从最终时刻T向前一时刻推导,
其他重要概率
前向概率和后向概率的计算式整个HMM过程的基础,由这两个概率可以拓展延伸得到其他一些很重要的概率,这些概率在HMM的其他两个问题的解决中是起到决定性作用。
1)求取γt(i)
通过
2)求取ξt(i, j)
3)观测序列为O时,任意时刻出现状态qi的概率
从初始时刻1到终止时刻T期间均有可能出现状态qi。
4)观测序列为O时,任意时刻从状态qi转移到qj的概率
从初始时刻1到终止时刻T-1期间均有可能出现状态qi。
解决问题2:参数估计问题
此时状态序列和观测序列都已知,给出一直状态和观测序列 {I, O} = { (I1, O1), (I2, O2), (I3, O3), …(IT, OT) } ,通过运用算法得到一组最优的HMM模型的参数A、B和 π。有两种方法能够解决这个问题。
方法1:极大似然估计(不推荐使用)
可以简单地理解为一般的求解先验概率,
其中,N 表示存在N种不同的状态;M 表示每个状态下都存在相同的M种观测值;
Aij 是在状态i 转换到状态j 的总次数,aij 的极大似然概率就是在状态i 转换不同的N 种状态的总次数中,从状态i 转换到状态j 的占比。
bjk 是在状态j 的条件下观测值为k的总次数,bjOk 表示在状态j 下观测到
方法2:Baum-Welch法(推荐使用)
极大似然法求取各项参数的过程很简单,通过对频率的计算就能够得到。但是一般情况下,状态序列 I 是不可见的,只有观测序列 O 是可见的,存在隐变量时,不能简单使用极大似然法求取先验概率,正确的方式是使用EM算法(EM:期望最大化)。该算法可以分为E步和M步。
下面的推导依旧建立在有不同的 N种状态,每种状态都有相同的 M种观测值的前提假设之上。
E步
假设当前模型的参数的估计值为 ,而模型的最优参数为 。
M步
M步通过多轮的迭代得到最优的一组参数值。为了使得期望E最大化,可以分别针对上面的每一项求最大值,最大值时对应的参数 即为HMM模型的最优参数。对上式中的三项中的每一个进行拆解,每一项都可以用拉格朗日乘子法得到一组最优的解。
对第一项进行拆解,
故初始概率 能够使用概率问题中的相关计算得到。注意:上面的推导过程中t(i)对应HMM模型的概率1(i),即 P(I1=qi | , ),其中={ O1, O2, …, OT }。而则是拉格朗日乘子法的乘子。
对第二项进行拆解,
上式最后可以转换为上一节内容中的两个简洁的符号表示,
对第三项进行拆解,
可以进一步的简化表示为,
解决问题3:预测问题(解码问题)
已知模型 = (A, B,) 和 观测序列 = (O1,O2, …, OT),求给定观测序列和模型参数的条件下,使得概率 P( | ) 最大时对应的状态序列 = (i1, i2, …, iT)。
同样存在两种方式求解这一类问题。
方法1:近似算法(不推荐)
在整个观测过程的每个时刻t,选取最有可能出现的状态 i,对于给定模型和观测序列,t时刻状态为 i 的概率在前向、后向概率计算的一节中已经有讲解,
则t时刻最有可能的状态为,
即N种不同的状态中,使得最大时所对应的状态。
方法2:Viterbi算法(推荐)
该方法是使用动态规划的思想求解HMM预测问题,通过已知的观测序列,求取最优的状态序列。
t=1时刻开始,递推t∈[1, T] 时刻状态为i的各部分路径的最大概率。当t=T时刻的最大概率即为最优解的路径P*,可以确定T时刻的状态 IT。由 IT向前可以逐步推得其余时刻 IT-1、 IT-2… I2、 I1,由此得到整个观测过程的状态。该状态对应最大的 P( | )。VB算法的基本思路如下,
具体步骤为,
Viterbi算法示例
递推过程,
推导过程完毕,从最终的T时刻选取最优的路径终点,
回溯过程开始,