隐马尔可夫模型有例子具体易懂

隐马尔可夫模型

现在是1页\一共有77页\编辑于星期三主要内容马尔可夫模型隐马尔可夫模型隐马尔可夫模型的三个基本问题三个基本问题的求解算法

1.前向算法

2.Viterbi算法

3.向前向后算法隐马尔可夫模型的应用隐马尔可夫模型的一些实际问题隐马尔可夫模型总结现在是2页\一共有77页\编辑于星期三马尔可夫链一个系统有N个状态S1，S2，···，Sn，随着时间推移，系统从某一状态转移到另一状态，设qt为时间t的状态，系统在时间t处于状态Sj的概率取决于其在时间1，2，···，t-1的状态，该概率为：

如果系统在t时间的状态只与其在时间t-1的状态相关，则该系统构成一个离散的一阶马尔可夫链(马尔可夫过程)：现在是3页\一共有77页\编辑于星期三马尔可夫模型如果只考虑独立于时间t的随机过程：其中状态转移概率aij必须满足aij>=0,且，则该随机过程称为马尔可夫模型。现在是4页\一共有77页\编辑于星期三例假定一段时间的气象可由一个三状态的马尔可夫模型M描述，S1：雨，S2：多云，S3：晴，状态转移概率矩阵为：现在是5页\一共有77页\编辑于星期三例（续）

如果第一天为晴天，根据这一模型，在今后七天中天气为O=“晴晴雨雨晴云晴”的概率为：现在是6页\一共有77页\编辑于星期三隐马尔可夫模型

（HiddenMarkovModel,HMM）在MM中，每一个状态代表一个可观察的事件在HMM中观察到的事件是状态的随机函数，因此该模型是一双重随机过程，其中状态转移过程是不可观察（隐蔽）的(马尔可夫链)，而可观察的事件的随机过程是隐蔽的状态转换过程的随机函数(一般随机过程)。现在是7页\一共有77页\编辑于星期三HMM的三个假设对于一个随机事件，有一观察值序列：O=O1,O2,…OT该事件隐含着一个状态序列：Q=q1,q2,…qT。假设1：马尔可夫性假设（状态构成一阶马尔可夫链）

P(qi|qi-1…q1)=P(qi|qi-1)假设2：不动性假设（状态与具体时间无关）

P(qi+1|qi)=P(qj+1|qj)，对任意i，j成立假设3：输出独立性假设（输出仅与当前状态有关）

p(O1,...,OT|q1,...,qT)=Πp(Ot|qt)现在是8页\一共有77页\编辑于星期三HMM定义一个隐马尔可夫模型(HMM)是由一个五元组描述的：

λ＝（N，M，A，B，π）其中：N={q1,...qN}：状态的有限集合M={v1,...,vM}：观察值的有限集合A={aij}，aij=P(qt=Sj|qt-1=Si)：状态转移概率矩阵B={bjk}，bjk

=P(Ot=vk|qt=Sj)：观察值概率分布矩阵π={πi}，πi=P(q1=Si)：初始状态概率分布现在是9页\一共有77页\编辑于星期三观察序列产生步骤给定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,如果t<T，重复步骤3、4，否则结束。现在是10页\一共有77页\编辑于星期三HMM的三个基本问题令λ

={π，A，B}为给定HMM的参数，令O=O1,...,OT为观察值序列，则有关于隐马尔可夫模型（HMM）的三个基本问题：1.评估问题：对于给定模型，求某个观察值序列的概率P(O|λ)；2.解码问题：对于给定模型和观察值序列，求可能性最大的状态序列maxQ{P(Q|O,λ)}；3.学习问题：对于给定的一个观察值序列O，调整参数λ，使得观察值出现的概率P(O|λ)最大。现在是11页\一共有77页\编辑于星期三例:赌场的欺诈某赌场在掷骰子根据点数决定胜负时,暗中采取了如下作弊手段:在连续多次掷骰子的过程中,通常使用公平骰子AB0.90.1A,偶而混入一个灌铅骰子B.

0.80.2公平骰子灌铅骰子现在是12页\一共有77页\编辑于星期三骰子A骰子B1点1/602点1/61/83点1/61/84点1/63/165点1/63/166点1/63/8公平骰子A与灌铅骰子B的区别:现在是13页\一共有77页\编辑于星期三时间1234567骰子AAABAAA掷出点数3345162一次连续掷骰子的过程模拟

隐序列

明序列查封赌场后,调查人员发现了一些连续掷骰子的记录,其中有一个骰子掷出的点数记录如下:

…现在是14页\一共有77页\编辑于星期三问题1–评估问题给定一个骰子掷出的点数记录124552646214614613613666166466163661636616361651561511514612356234问题会出现这个点数记录的概率有多大?求P(O|λ)现在是15页\一共有77页\编辑于星期三问题2–解码问题给定一个骰子掷出的点数记录124552646214614613613666166466163661636616361651561511514612356234问题点数序列中的哪些点数是用骰子B掷出的?求maxQ{P(Q|O,λ)}现在是16页\一共有77页\编辑于星期三问题3–学习问题给定一个骰子掷出的点数记录124552646214614613613666166466163661636616361651561511514612356234问题作弊骰子掷出各点数的概率是怎样的?公平骰子掷出各点数的概率又是怎样的?赌场是何时换用骰子的?现在是17页\一共有77页\编辑于星期三骰子B

本例中HMM的定义

赌场的例子中:隐状态集:S={骰子A,骰子B}明字符集:V={1,2,3,4,5,6}b21=0,b22=b23=1/8,b24=b25=3/16,b26=3/81/61/61/61/61/61/601/81/83/163/163/8初始状态概率:π1=1,π2=0隐状态转移概率:

a11=0.9,a12=0.1

a21=0.8,a22=0.2

初始状态明字符生成概率:

b11=b12=…=b16=1/61.00

1: 2: 3: 4: 5:骰子A6:

0.1

1: 2: 3: 4: 5: 6:0.80.90.2现在是18页\一共有77页\编辑于星期三HMM将两个序列相联系起来：1.由离散隐状态组成的状态序列(路径)Q=(q1,…,qT),每个qt∈S均是一个状态由初始状态概率及状态转移概率(π,A)所决定2.由明字符组成的观察序列O=(o1,…,oT),每个ot∈V均为一个离散明字符由状态序列及各状态的明字符生成概率(Q,B)所决定现在是19页\一共有77页\编辑于星期三赌场的例子中:隐状态明观察AAAABAAAAABAAAAAAAAAAAAAAAAAAAAAAABAABAAAAAAAAA…33454141553663441134625445334223332124225631341…q1q2q3q4qT...o1o2o3o4oT...观察序列O状态序列QHMMλ现在是20页\一共有77页\编辑于星期三本例中三个基本问题1.评估问题•给定观察序列O和HMM

=(π,A,B),判断O是由产生出来的可能性有多大•计算骰子点数序列的确由“作弊”模型生成的可能性2.解码问题•给定观察序列O和HMMλ=(π,A,B),计算与序列O相对应的状态序列是什么•在骰子点数序列中,判断哪些点数是用骰子B掷出的3.学习问题•给定一系列观察序列样本,确定能够产生出这些序列的模型λ=(π,A,B)•如何从大量的点数序列样本中学习得出“作弊模型”的参数现在是21页\一共有77页\编辑于星期三三个基本问题的求解算法评估问题：前向算法定义前向变量采用动态规划算法，复杂度O(N2T)解码问题：韦特比（Viterbi）算法采用动态规划算法，复杂度O(N2T)学习问题：向前向后算法EM算法的一个特例，带隐变量的最大似然估计现在是22页\一共有77页\编辑于星期三解决问题一—前向算法定义前向变量为：“在时间步t,得到t之前的所有明符号序列,且时间 步t的状态是Si”这一事件的概率， 记为

(t,i)=P(o1,…,ot,qt=Si|λ)则

现在是23页\一共有77页\编辑于星期三算法过程

现在是24页\一共有77页\编辑于星期三HMM的网格结构现在是25页\一共有77页\编辑于星期三前向算法过程演示t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1i=Ni=N-1i=5i=4i=3i=2i=1α(t,i)现在是26页\一共有77页\编辑于星期三t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1初始化α(1,i)=π(i)b(i,o1)现在是27页\一共有77页\编辑于星期三t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1现在是28页\一共有77页\编辑于星期三t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1现在是29页\一共有77页\编辑于星期三t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1现在是30页\一共有77页\编辑于星期三t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1现在是31页\一共有77页\编辑于星期三t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=12.递归现在是32页\一共有77页\编辑于星期三t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1

现在是33页\一共有77页\编辑于星期三t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1

现在是34页\一共有77页\编辑于星期三t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1

现在是35页\一共有77页\编辑于星期三t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1

现在是36页\一共有77页\编辑于星期三t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1

现在是37页\一共有77页\编辑于星期三t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1

现在是38页\一共有77页\编辑于星期三

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

现在是39页\一共有77页\编辑于星期三前向算法过程演示t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1i=Ni=N-1i=5i=4i=3i=2i=1

现在是40页\一共有77页\编辑于星期三t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1现在是41页\一共有77页\编辑于星期三t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1现在是42页\一共有77页\编辑于星期三t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1现在是43页\一共有77页\编辑于星期三t=1t=2t=3t=4t=5t=Tt=6t=7t=T-1

前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1现在是44页\一共有77页\编辑于星期三t=1t=2t=3t=4t=5t=Tt=7t=6t=T-1

前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1现在是45页\一共有77页\编辑于星期三t=1t=2t=3t=4t=5t=Tt=T-1t=6t=7

前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1现在是46页\一共有77页\编辑于星期三t=1t=2t=3t=4t=5t=Tt=T-1t=6t=7

前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1现在是47页\一共有77页\编辑于星期三前向算法过程演示t=1t=2t=3t=4t=5t=Tt=T-1t=6t=7i=Ni=N-1i=5i=4i=3i=2i=13.计算P(O|λ)现在是48页\一共有77页\编辑于星期三t=1t=2t=3t=4t=5t=Tt=T-1t=6t=7

前向算法过程演示i=Ni=N-1i=5i=4i=3i=2i=1

现在是49页\一共有77页\编辑于星期三例子（前向算法应用）HMM模型如下，试根据前向算法计算产生观察符号序列O={ABAB}的概率。状态集Q={S1,S2,S3}观察序列集O={A,B}现在是50页\一共有77页\编辑于星期三例（续）初始概率矩阵π=(1,0,0),即开始处于状态1。按照前向算法公式，我们依次递推解出t(i)

。解法如下：

1.当t=1时：

现在是51页\一共有77页\编辑于星期三例（续）2.当t=2时：3.当t=3时：

现在是52页\一共有77页\编辑于星期三例（续）4.当t=4时：所以最终有：

P(O|λ)=4(1)+4(2)+4(3)=0.0717696即观察序列O由HMM模型产生的概率现在是53页\一共有77页\编辑于星期三例（续）最后将其计算过程示意图表示如下：现在是54页\一共有77页\编辑于星期三问题2—解码问题

所求的Q应当在某个准则下是“最优”的,因此也称Q为最优路径,解码问题即是确定最优路径的问题。现在是55页\一共有77页\编辑于星期三

qt=Si产生出o1,…ot的最大概率，即：

解决问题二—Viterbi算法Viterbi算法也是类似于前向算法的一种网格结构现在是56页\一共有77页\编辑于星期三Viterbi算法（续）目标：给定一个观察序列和HMM模型，如何有效选择“最优”状态序列，以“最好地解释”观察序列“最优”→概率最大：Viterbi变量：递归关系：记忆变量：记录概率最大路径上当前状态的前一个状态现在是57页\一共有77页\编辑于星期三Viterbi算法（续）初始化：递归：终结：路径回溯：现在是58页\一共有77页\编辑于星期三例子（Viterbi算法应用）HMM模型如下，试根据Viterbi算法计算产生观察符号序列O={ABAB}的最优状态序列Q。

状态集Q｛S1,S2,S3｝观察序列集O={A,B}现在是59页\一共有77页\编辑于星期三例（续）

初始概率矩阵π=(1,0,0),即开始时处于状态1。按照上面的公式，我们依次递推解出，以及。解法如下：

1.当t=1时：

现在是60页\一共有77页\编辑于星期三例（续）2.当t=2时：3.当t=3时：现在是61页\一共有77页\编辑于星期三例（续）4.当t=4时：

现在是62页\一共有77页\编辑于星期三例（续）其递推结果为：可以看出，最有可能的状态序列是：

S1，S2，S2，S2.现在是63页\一共有77页\编辑于星期三例（续）其计算结果示意图如下所示：绿色的箭头表示最有可能的状态序列

现在是64页\一共有77页\编辑于星期三问题3—学习问题也称训练问题、参数估计问题

化准则，使得观察序列的概率P(O|λ)最大。现在是65页\一共有77页\编辑于星期三状态序列已知情况可以由最大似然估计来估计HMM的参数：现在是66页\一共有77页\编辑于星期三EM(Expectation-Maximization)算法由于HMM中的状态序列是观察不到的（隐变量），以上的最大似然估计不可行。EM算法可用于含有隐变量的统计模型的最大似然估计。EM算法是一个由交替进行的“期望(E过程)”和“极大似然估计(M过程)”两部分组成的迭代过程：

·对于给定的不完全数据和当前的参数值，“E过程”从条件期望中相应地构造完全数据的似然函数值，“M过程”则利用参数的充分统计量，重新估计概率模型的参数，使得训练数据的对数似然最大。EM算法的每一次迭代过程必定单调地增加训练数据的对数似然值，于是迭代过程渐进地收敛于一个局部最优值。现在是67页\一共有77页\编辑于星期三向前向后算法(Baum-Welch算法)1.初始化：随机地给πi

，aij

，bjk赋值（满足概率条件），得到模型λ0，设i=0；