隐马尔科夫模型.ppt

《隐马尔科夫模型.ppt》由会员分享，可在线阅读，更多相关《隐马尔科夫模型.ppt（77页珍藏版）》请在三一办公上搜索。

1、隐马尔可夫模型,主要内容,马尔可夫模型隐马尔可夫模型隐马尔可夫模型的三个基本问题三个基本问题的求解算法 1.前向算法 2.Viterbi算法 3.向前向后算法隐马尔可夫模型的应用隐马尔可夫模型的一些实际问题隐马尔可夫模型总结,马尔可夫链,一个系统有N个状态 S1，S2，Sn，随着时间推移，系统从某一状态转移到另一状态，设qt为时间t的状态，系统在时间t处于状态Sj 的概率取决于其在时间 1，2，t-1 的状态，该概率为：如果系统在t时间的状态只与其在时间 t-1的状态相关，则该系统构成一个离散的一阶马尔可夫链(马尔可夫过程)：,马尔可夫模型,如果只考虑独立于时间t的随机过程：其中状态转移概率

2、aij 必须满足 aij=0,且，则该随机过程称为马尔可夫模型。,例,假定一段时间的气象可由一个三状态的马尔可夫模型M描述，S1：雨，S2：多云，S3：晴，状态转移概率矩阵为：,例（续）,如果第一天为晴天，根据这一模型，在今后七天中天气为O=“晴晴雨雨晴云晴”的概率为：,隐马尔可夫模型（Hidden Markov Model,HMM）,在MM中，每一个状态代表一个可观察的 事件在HMM中观察到的事件是状态的随机函数，因此该模型是一双重随机过程，其中状态转移过程是不可观察（隐蔽）的(马尔可夫链)，而可观察的事件的随机过程是隐蔽的状态转换过程的随机函数(一般随机过程)。,HMM的三个假设,对于一个

3、随机事件，有一观察值序列：O=O1,O2,OT该事件隐含着一个状态序列：Q=q1,q2,qT。假设1：马尔可夫性假设（状态构成一阶马尔可夫链）P(qi|qi-1q1)=P(qi|qi-1)假设2：不动性假设（状态与具体时间无关）P(qi+1|qi)=P(qj+1|qj)，对任意i，j成立假设3：输出独立性假设（输出仅与当前状态有关）p(O1,.,OT|q1,.,qT)=p(Ot|qt),HMM定义,一个隐马尔可夫模型(HMM)是由一个五元组描述的：（N，M，A，B，）其中：N=q1,.qN：状态的有限集合 M=v1,.,vM：观察值的有限集合 A=aij，aij=P(qt=Sj|qt-1=Si

4、)：状态转移概率矩阵 B=bjk，bjk=P(Ot=vk|qt=Sj)：观察值概率分布矩阵=i，i=P(q1=Si)：初始状态概率分布,观察序列产生步骤,给定HMM模型=(A，B，)，则观察序列 O=O1,O2,OT 可由以下步骤产生：1.根据初始状态概率分布=i,选择一初始状态q1=Si；2.设t=1；3.根据状态 Si的输出概率分布bjk,输出Ot=vk；4.根据状态转移概率分布aij,转移到新状态qt+1=Sj；5.设t=t+1,如果tT，重复步骤3、4，否则结束。,HMM的三个基本问题,令=，A，B 为给定HMM的参数，令 O=O1,.,OT 为观察值序列，则有关于隐马尔可夫模型（HM

5、M）的三个基本问题：1.评估问题：对于给定模型，求某个观察值序列的概率P(O|)；2.解码问题：对于给定模型和观察值序列，求可能性最大的状态序列maxQP(Q|O,)；3.学习问题：对于给定的一个观察值序列O，调整参数，使得观察值出现的概率P(O|)最大。,例:赌场的欺诈,某赌场在掷骰子根据点数决定胜负时,暗中,采取了如下作弊手段:,在连续多次掷骰子的过程中,通常使用公平骰子,A,B,0.9,0.1,A,偶而混入一个灌铅骰子B.0.8,0.2,公平骰子,灌铅骰子,公平骰子A与灌铅骰子B的区别:,一次连续掷骰子的过程模拟,隐序列明序列查封赌场后,调查人员发现了一些连续掷骰子的记录,其中有一个骰子

6、掷出的点数记录如下:124552646214614613613666166466163661636616361651561511514612356234,问题 1 评估问题,给定,一个骰子掷出的点数记录,124552646214614613613666166466163661636616361651561511514612356234,问题,会出现这个点数记录的概率有多大?求P(O|),问题 2 解码问题,给定,一个骰子掷出的点数记录,124552646214614613613666166466163661636616361651561511514612356234,问题,点数序列中的哪些点数

7、是用骰子B掷出的?求maxQP(Q|O,),问题 3 学习问题,给定,一个骰子掷出的点数记录,124552646214614613613666166466163661636616361651561511514612356234,问题,作弊骰子掷出各点数的概率是怎样的?公平骰子,掷出各点数的概率又是怎样的?赌场是何时 换用骰子的?,骰子B,本例中HMM的定义赌场的例子中:隐状态集:S=骰子A,骰子B,明字符集:V=1,2,3,4,5,6,b21=0,b22=b23=1/8,b24=b25=3/16,b26=3/8,1/61/61/61/61/61/601/81/83/163/163/8,初始状态

8、概率:1=1,2=0隐状态转移概率:a11=0.9,a12=0.1 a21=0.8,a22=0.2初始状态明字符生成概率:b11=b12=b16=1/6,1.00,1:2:3:4:5:骰子A 6:0.11:2:3:4:5:6:,0.8,0.9,0.2,HMM将两个序列相联系起来：,1.由离散隐状态组成的状态序列(路径),Q=(q1,qT),每个qtS均是一个状态,由初始状态概率及状态转移概率(,A)所决定,2.由明字符组成的观察序列,O=(o1,oT),每个otV均为一个离散明字符,由状态序列及各状态的明字符生成概率(Q,B)所决定,赌场的例子中:,隐状态明观察,AAAABAAAAABAAAA

9、AAAAAAAAAAAAAAAAAAABAABAAAAAAAAA3 3 4 5 4 1 4 1 5 5 3 6 6 3 4 4 1 1 3 4 6 2 5 4 4 5 3 3 4 2 2 3 3 3 2 1 2 4 2 2 5 6 3 1 3 4 1,q1,q2,q3,q4,qT,.,o1,o2,o3,o4,oT,.,观察序列O,状态序列Q,HMM,本例中三个基本问题,1.评估问题,给定观察序列O和HMM=(,A,B),判断O是由产,生出来的可能性有多大,计算骰子点数序列的确由“作弊”模型生成的可能性,2.解码问题,给定观察序列O和HMM=(,A,B),计算与序列O相,对应的状态序列是什么,在

10、骰子点数序列中,判断哪些点数是用骰子B掷出的,3.学习问题,给定一系列观察序列样本,确定能够产生出这些序列的模,型=(,A,B),如何从大量的点数序列样本中学习得出“作弊模型”的参数,三个基本问题的求解算法,评估问题：前向算法定义前向变量采用动态规划算法，复杂度O(N2T)解码问题：韦特比（Viterbi）算法采用动态规划算法，复杂度O(N2T)学习问题：向前向后算法EM算法的一个特例，带隐变量的最大似然估计,解决问题一前向算法,定义前向变量为：,“在时间步t,得到t之前的所有明符号序列,且时间步t的状态是Si”这一事件的概率，记为(t,i)=P(o1,ot,qt=Si|),则,算法过程,HM

11、M的网格结构,前向算法过程演示,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,i=Ni=N-1i=5i=4i=3i=2i=1,(t,i),t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示i=N,i=N-1i=5i=4i=3i=2i=1,初始化(1,i)=(i)b(i,o1),t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示i=Ni=N-1i

12、=5i=4i=3i=2i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示i=N,i=N-1i=5i=4i=3i=2i=1,2.递归,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示i=N,i=N-1i=5i=4i=3i=2i=

13、1,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示i=N,i=N-1i=5i=4i=3i=2i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示i=N,i=N-1i=5i=4i=3i=2i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示i=N,i=N-1i=5i=4i=3i=2i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示i=N,i=N-1i=5i=4i=3i=2i=1,t=1,t=2,t=3,t=

14、4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示i=N,i=N-1i=5i=4i=3i=2i=1,前向算法过程演示i=N,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,i=N-1i=5i=4i=3i=2i=1,前向算法过程演示,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,i=Ni=N-1i=5i=4i=3i=2i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7

15、,t=T-1,前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=7,t=6,t=T-1,前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=T-1,t=6,t=7,前向算法过程演示i=Ni=

16、N-1i=5i=4i=3i=2i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=T-1,t=6,t=7,前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1,前向算法过程演示,t=1,t=2,t=3,t=4,t=5,t=T,t=T-1,t=6,t=7,i=Ni=N-1i=5i=4i=3i=2i=1,3.计算P(O|),t=1,t=2,t=3,t=4,t=5,t=T,t=T-1,t=6,t=7,前向算法过程演示i=N,i=N-1i=5i=4i=3i=2i=1,例子（前向算法应用）,HMM模型如下，试根据前向算法计算产生观察符号序列O=ABAB的概率。,状态集Q=S1,S2,S

17、3,观察序列集O=A,B,例（续）,初始概率矩阵=(1,0,0),即开始处于状态1。按照前向算法公式，我们依次递推解出 t(i)。解法如下：1.当 t=1时：,例（续）,2.当t=2时：3.当t=3时：,例（续）,4.当t=4时：所以最终有：P(O|)=4(1)+4(2)+4(3)=0.0717696 即观察序列O由HMM模型产生的概率,例（续）,最后将其计算过程示意图表示如下：,问题 2解码问题,所求的 Q 应当在某个准则下是“最优”的,因此也称 Q 为最优路径,解码问题即是确定最优路径的问题。,qt=Si产生出 o1,ot的最大概率，即：,解决问题二Viterbi算法,Viterbi 算法

18、也是类似于前向算法的一种网格结构,Viterbi算法（续）,目标：给定一个观察序列和HMM模型，如何有效选择“最优”状态序列，以“最好地解释”观察序列“最优”概率最大：Viterbi变量：递归关系：记忆变量：记录概率最大路径上当前状态的前一个状态,Viterbi算法（续）,初始化：递归：终结：路径回溯：,例子（Viterbi算法应用）,HMM模型如下，试根据Viterbi算法计算产生观察符号序列O=ABAB的最优状态序列Q。,状态集QS1,S2,S3,观察序列集O=A,B,例（续）,初始概率矩阵=(1,0,0),即开始时处于状 态1。按照上面的公式，我们依次递推解出，以及。解法如下：1.当t=

19、1时：,例（续）,2.当t=2时：3.当t=3时：,例（续）,4.当t=4时：,例（续）,其递推结果为：可以看出，最有可能的状态序列是：S1，S2，S2，S2.,例（续）,其计算结果示意图如下所示：绿色的箭头表示最有可能的状态序列,问题3学习问题,也称训练问题、参数估计问题,化准则，使得观察序列的概率P(O|)最大。,状态序列已知情况,可以由最大似然估计来估计HMM的参数：,EM(Expectation-Maximization)算法,由于HMM中的状态序列是观察不到的（隐变量），以上的最大似然估计不可行。EM算法可 用于含有隐变量的统计模型的最大似然估计。EM算法是一个由交替进行的“期望(E

20、过程)”和“极大似然估计(M过程)”两部分组成的迭代过程：对于给定的不完全数据和当前的参数值，“E过程”从条件期望中相 应地构造完全数据的似然函数值，“M过程”则利用参数的充分统计 量，重新估计概率模型的参数，使得训练数据的对数似然最大。EM算法的每一次迭代过程必定单调地增加训练数据的对数似然值，于是迭代过程渐进地收敛于一个局部最优值。,向前向后算法(Baum-Welch算法),1.初始化：随机地给i，aij，bjk 赋值（满足概率条件），得到模型0，设 i=0；2.EM步骤：E步骤：由i根据公式（1）和（2），计算期望值t（i，j）和 t（i）；M步骤：用E步骤所得的期望值，根据公式（3）重

21、新估计i，aij，bjk，得到模型 i+1;3.循环设计：i=i+1；重复EM步骤，直至i，aij，bjk 值收敛。,期望值(1),给定HMM和观察序列，t（i，j）为在时间t 位于状态i，时间 t+1 位于状态j的概率：,图示,期望值(2),给定HMM和观测序列，在时间t位于状态i的概率：,重估公式(3),HMM的应用,语音识别音字转换词性标注（POS Tagging）基因识别问题 状态:编码区域与非编码区域 字符:ATCG一般化：任何与线性序列相关的现象,HMM的一些实际问题,初始概率分布的选择 1.随机选择 2.利用先验信息 3.来自多序列比对的结果,HMM的一些实际问题（续）,数值计算中的防溢出处理在前向算法、Viterbi算法以及Baum-Welch算法中，概率值的连续乘法运算很容易导致下溢现象。解决办法：1.前向算法中：每一个时间步的运算中都乘以一 个比例因子 2.Viterbi算法中：对概率值取对数后计算,Viterbi算法:连乘积对数求和前向算法:引入比例因子 其中,比例因子,HMM总结,HMM模型可以看作一种特定的Bayes NetHMM模型等价于概率正规语法或概率有限状态自动机HMM模型可以用一种特定的神经网络模型来模拟优点：研究透彻，算法成熟，效率高，效果好，易于训练,