马尔科夫模型转载共21页.docx
- 文档编号:14202064
- 上传时间:2023-06-21
- 格式:DOCX
- 页数:30
- 大小:6.95MB
马尔科夫模型转载共21页.docx
《马尔科夫模型转载共21页.docx》由会员分享,可在线阅读,更多相关《马尔科夫模型转载共21页.docx(30页珍藏版)》请在冰点文库上搜索。
马尔科夫模型转载共21页
隐马尔可夫模型(móxíng)
(一)——马尔可夫模型(móxíng)
马尔可夫模型(móxíng)(MarkovModel)描述(miáoshù)了一类随机变量随时间而变化的随机函数。
考察一个状态序列(此时随机变量为状态值),这些状态并不是相互独立的,每个状态的值依赖于序列中此状态之前的状态。
数学描述:
一个系统由N个状态S={s1,s2,...sn},随着时间的推移,该系统从一个状态转换成另一个状态。
Q={q1,q2,...qn}为一个状态序列,qi∈S,在t时刻的状态为qt,对该系统的描述要给出当前时刻t所处的状态st,和之前的状态s1,s2,...st,则t时刻位于状态qt的概率为:
P(qt=st|q1=s1,q2=s2,...qt-1=st-1)。
这样的模型叫马尔可夫模型。
特殊状态下,当前时刻的状态只决定于前一时刻的状态叫一阶马尔可夫模型,即P(qt=si|q1=s1,q2=s2,...qt-1=sj)=P(qt=si|qt-1=sj)。
状态之间的转化表示为aij,aij=P(qt=sj|qt-1=si),其表示由状态i转移到状态j的概率。
其必须满足两个条件:
1.aij≥0 2.
=1
对于有N个状态的一阶马尔科夫模型,每个状态可以转移到另一个状态(包括自己),则共有N2次状态转移,可以用状态转移矩阵表示。
例如:
一段文字中名词、动词、形容词出现的情况可以用有3个状态的y一阶马尔科夫模型M表示:
状态s1:
名词 状态s2:
动词 状态s3:
形容词
状态转移矩阵:
s1 s2 s3
A=
则状态序列O=“名动形名”(假定第一个词为名词)的概率为:
P(O|M)=P(s1,s2,s3,s4}=P(s1)*p(s2|s1)p(s3|s2)p(s1|s3)
=p(s1)*a12*a23*a31
=1*0.5*0.2*0.4
=0.04
隐马尔可夫模型
(二)——隐马尔可夫模型的构成
在马尔可夫模型中,每一个状态都是可观察的序列,是状态关于时间的随机过程,也成为可视马尔可夫模型(VisibleMarkovModel,VMM)。
隐马尔科夫模型(HiddenMarkovModel,HMM)中的状态是不可见的,我们可以看到的是状态表现出来的观察值和状态的概率函数。
在隐马模型中,观察值是关于状态的随机过程,而状态是关于时间的随机过程,因此隐马模型是一个双重随机过程。
当考虑潜在事件随机生成表面事件时,可以用HMM解决。
举个例子,说明隐马模型:
有4个暗箱(ànxiāng),放在暗处,每个箱子里有3种不用(bùyòng)颜色的球(红、橙、蓝),从箱子往外拿球是有一定规律的,现在工作人员从暗处的箱子中取球,去了5次,我们看到额观察序列(xùliè)是:
红蓝蓝橙红。
这个过程就是一个隐马模型。
暗处的箱子表示状态,箱子的个数表示状态的个数,球的颜色表示状态的输出值,球的颜色个数表示状态输出观察状态的个数,从一个箱子转换成另一个箱子表示状态转换,从暗处箱子中取出的球的观察颜色表示状态的输出序列。
因此可以(kěyǐ)归纳隐马模型的5个组成状态:
(1)模型中的状态个数N(例子中的箱子个数);
(2)每个状态的可以输出的不同观测值M(例子中的球的颜色数目);
(3)状态转移矩阵A={aij}(例子中aij表示从第i个箱子转移到第j个箱子的概率),其中aij满足条件:
I. aij≥0,1≤i,j≤N
II.aij=P(qt=sj|qt-1=si),
III.
=1
(4)发射矩阵B={bj(k)},即从状态sj观察到符号vk的概率分布矩阵.(bj(k)在例子中表示从的j个箱子中拿出第k个颜色的概率),其中bj(k)满足条件:
I. bj(k)≥0,1≤j≤N;1≤k≤M
II.bj(k)=P(Ot=vk|qt=sj),
III.
=1
(5)初始状态概率分布π={πj}.(例子中一开始到第j个箱子的概率),其中πj满足条件:
I. πj(k)≥0,1≤j≤N
II.πj=P(q1=sj),
III.
=1
一般(yībān),一个HMM即为五元(wǔyuán)组μ={N,M,A,B,π},为了(wèile)简便,常简记为三元组μ={A,B,π}。
HMM有三个基本(jīběn)问题:
(1)评估问题:
给定一个观察序列O=O1O2...OT和模型μ={A,B,π},如何快速地计算给定模型μ的条件下,观察序列O=O1O2...OT的概率,即P(O|μ)?
(2)解码问题:
给定一个观察序列O=O1O2...OT和模型μ={A,B,π},如何快速地选择在给定模型μ的条件下在一定意义下”最优“的状态序列Q=Q1Q2...QT,是该状态序列”最好地"解释观察序列?
(3)学习问题:
给定一个观察序列O=O1O2...OT,如何调整参数μ={A,B,π},使得P(O|M)最大?
针对HMM的三个基本问题,相应的算法是:
(1)评估问题:
前向后向算法
(2)解码问题:
维特比算法(Viterbi)
(3)学习问题:
前向后向算法(BAUM-WELCH)。
隐马尔可夫模型(三)——隐马尔可夫模型的评估问题(前向算法)
隐马模型的评估问题即,在已知一个观察序列O=O1O2...OT,和模型μ=(A,B,π}的条件下,观察序列O的概率,即P(O|μ}
如果穷尽所有的状态组合,即S1S1...S1,S1S1...S2,S1S1...S3,...,S3S3...S3。
这样的话t1时刻有N个状态,t2时刻有N个状态...tT时刻有N个状态,这样的话一共有N*N*...*N=NT种组合,时间复杂度为O(NT),计算时,就会出现“指数爆炸”,当T很大时,简直无法计算这个值。
为解决这一问题,Baum提出了前向算法。
归纳过程
首先引入前向变量αt(i):
在时间t时刻,HMM输出序列为O1O2...OT,在第t时刻位于状态si的概率。
当T=1时,输出(shūchū)序列为O1,此时计算(jìsuàn)概率为P(O1|μ):
假设有三个状态(zhuàngtài)(如下图)1、2、3,输出(shūchū)序列为O1,有三种可能一是状态1发出,二是从状态2发出,三是从状态3发出。
另外从状态1发出观察值O1得概率为b1(O1),从状态2发出观察值O1得概率为b2(O1),从状态3发出观察值O1得概率为b3(O1)。
因此可以算出
P(O1|μ)=π1*b1(O1)+π2*b2(O1)+ π3*b3(O1)= α1
(1)+ α1
(2)+ α1(3)
当T=2时,输出序列为O1O2,此时计算概率为P(O1O2|μ):
假设有三个状态(如下图)1、2、3,输出序列为O1,有三种可能一是状态1发出,二是从状态2发出,三是从状态3发出。
另外从状态1发出观察值O2得概率为b1(O2),从状态2发出观察值O2得概率为b2(O2),从状态3发出观察值O2得概率为b3(O2)。
要是从状态1发出观察值O2,可能从第一时刻的1、2或3状态装换过来,要是从状态1转换过来,概率为α1
(1)*a11*b1(O2),要是从状态2转换过来,概率为α1
(2)*a21*b1(O2),要是从状态3转换过来,概率为α1(3)*a31*b1(O2),因此
P(O1O2,q2=s1|μ)= α1
(1)*a11*b1(O2) + α1
(2)*a21*b1(O2)+ α1(3)*a31*b1(O2)=α2
(1)
同理:
P(O1O2,q2=s1|μ)=α1
(1)*a12*b2(O2) +α1
(2)*a22*b2(O2)+α1(3)*a32*b2(O2)=α2
(2)
P(O1O2,q2=s1|μ)=α1
(1)*a13*b1(O2) +α1
(2)*a23*b3(O2)+α1(3)*a33*b3(O2)=α2(3)
所以(suǒyǐ):
P(O1O2|μ)=P(O1O2,q2=s1|μ)+P(O1O2,q2=s1|μ)+P(O1O2,q2=s1|μ)
=α2
(1)+α2
(2)+α2(3)
以此类推(yǐcǐlèituī)。
。
。
前向算法(suànfǎ)
step1初始化:
α1(i)=πi*bi(O1),1≤i≤N
step2归纳(guīnà)计算:
step3终结:
P(O|μ)=
时间复杂度
计算某时刻的某个状态的前向变量需要看前一时刻的N个状态,此时时间复杂度为O(N),每个时刻有N个状态,此时时间复杂度为N*O(N)=O(N2),又有T个时刻,所以时间复杂度为T*O(N2)=O(N2T)。
程序例证
前向算法计算P(O|M):
step1:
α1
(1)=π1*b1(red)=0.2*0.5=0.1 α1
(2)=π2*b2(red)==0.4*0.4=0.16 α1(3)=π3*b3(red)==0.4*0.7=0.21
step2:
α2
(1)=α1
(1)*a11*b1(white)+α1
(2)*a21*b1(white)+α1(3)*a31*b1(white)
...
step3:
P(O|M)=α3
(1)+α3
(2)+α3(3)
程序代码
#include
#include
#include
intmain()
{
floata[3][3]={{0.5,0.2,0.3},{0.3,0.5,0.2},{0.2,0.3,0.5}};
floatb[3][2]={{0.5,0.5},{0.4,0.6},{0.7,0.3}};
floatalpha[4][3];
inti,j,k,count=1;
//outputlist
intlist[4]={0,1,0,1};
//step1:
Initialization
alpha[0][0]=0.2*0.5;
alpha[0][1]=0.4*0.4;
alpha[0][2]=0.4*0.7;
//step2:
iteration
for(i=1;i<=3;i++)
{
for(j=0;j<=2;j++)
{
alpha[i][j]=0;
for(k=0;k<=2;k++)
{
alpha[i][j]+=alpha[i-1][k]*a[k][j]*b[j][list[count]];
}
}
count+=1;
}
for(i=0;i<=3;i++)
{
for(j=0;j<=2;j++)
{
printf("a[%d][%d]=%f\n",i+1,j+1,alpha[i][j]);
}
}
//step3:
end
printf("Forward:
%f\n",alpha[3][0]+alpha[3][1]+alpha[3][2]);
return0;
}
运行(yùnxíng)结果
隐马尔可夫模型(móxíng)(四)——隐马尔可夫模型的评估(pínɡɡū)问题(后向算法(suànfǎ))
对于(duìyú)HMM的评估问题,利用动态规划可以用前向算法,从前到后算出前向变量;也可以采用后向算法,从后到前算出后向变量。
先介绍后向变量βt(i):
给定模型μ=(A,B,π),并且在时间 时刻t 状态为si 的前提下,输出序列为Ot+1Ot+2...OT的概率,即
βt(i)=P(Ot+1Ot+2...OT|qt=si,μ)
归纳过程
假设仍然有3个状态
当t=T时,按照定义:
时间t 状态qT 输出为OT+1......的概率,从T+1开始的输出是不存在的(因为T时刻是终止终止状态),即T之后是空,是个必然事件,因此βt(i)=1,1≤1≤N
当t=T-1时,
βT-1(i)=P(OT|qT-1=si,μ)=ai1*b1(OT)*βT
(1) + ai2*b2(OT)*βT
(2) + ai3*b3(OT)*βT(3)
......
当t=1时,
β1
(1)=P(O2O3...OT|q2=s1,μ)=a11*b1(O2)*β2
(1)+a12*b2(O2)*β2
(2)+a13*b3(O2)*β2(3)
β1
(2)=P(O2O3...OT|q2=s1,μ)=a21*b1(O2)*β2
(1)+a22*b2(O2)*β2
(2)+a23*b3(O2)*β2(3)
β1(3)=P(O2O3...OT|q2=s1,μ)=a31*b1(O2)*β2
(1)+a32*b2(O2)*β2
(2)+a33*b3(O2)*β2(3)
P(O1O2...OT|μ)=
=
=
后向算法(suànfǎ)
step1初始化:
βT(i)=1,1≤1≤N
step2归纳(guīnà)计算:
1≤t≤T-1,1≤i≤N
step3求终结(zhōngjié)和:
P(O|μ)=
时间(shíjiān)复杂度
计算某时刻在某个状态下的后向变量(biànliàng)需要看后一时刻的N个状态(zhuàngtài),此时时间复杂度为O(N),每个时刻有N个状态,此时时间复杂度为N*O(N)=O(N2),又有T个时刻,所以时间复杂度为T*O(N2)=O(N2T)。
程序例证
后向算法
计算P(O|M):
step1:
β4
(1)=1 β4
(2)=1 β4(3)=1
step2:
β3
(1)=β4
(1)*a11*b1(white)+β4
(2)*a12*b2(white)+β4(3)*a13*b3(white)
...
step3:
P(O|M)=π1*β1
(1)*b1(O1)+π2*β1
(2)*b2(O1)+π3*β1(3)*b3(O1)
程序代码
#include
#include
#include
intmain()
{
floata[3][3]={{0.5,0.2,0.3},{0.3,0.5,0.2},{0.2,0.3,0.5}};
floatb[3][2]={{0.5,0.5},{0.4,0.6},{0.7,0.3}};
floatresult[4][3];
intlist[4]={0,1,0,1};
result[3][0]=1;
result[3][1]=1;
result[3][2]=1;
inti,j,k,count=3;
for(i=2;i>=0;i--)
{
for(j=0;j<=2;j++)
{
result[i][j]=0;
for(k=0;k<=2;k++)
{
result[i][j]+=result[i+1][k]*a[j][k]*b[k][list[count]];
}
}
count-=1;
}
for(i=0;i<=3;i++)
{
for(j=0;j<=2;j++)
{
printf("b[%d][%d]=%f\n",i+1,j+1,result[i][j]);
}
}
printf("backward:
%f\n",result[0][0]*0.2*0.5+result[0][1]*0.4*0.4+result[0][2]*0.4*0.7);
return0;
}
运行(yùnxíng)结果
隐马尔可夫模型(móxíng)(五)——隐马尔可夫模型(móxíng)的解码问题(维特比算法(suànfǎ))
阅读目录
∙HMM解码问题
∙维特比算法
∙时间复杂度
∙程序例证
回到顶部
HMM解码(jiěmǎ)问题
给定(ɡěidìnɡ)一个观察序列O=O1O2...OT,和模型(móxíng)μ=(A,B,π),如何快速有效(yǒuxiào)地选择在一定意义下“最优”的状态序列Q=q1q2...qT,使该状态最好地解释观察序列。
一种想法是求出每个状态的概率rt(i)最大(rt(i)=P(qt=si,O|μ)),记q't(i)=argQmax(rt(i)),但是这样做,忽略了状态之间的关系,很可能两个状态之间的概率为0,即aq't(i)q't+1(i)=0,这样求得的“最优”状态序列是不合法的。
为防止状态之间转移概率为0(断续问题),换一种思路,不是求单个状态求得最大值,而是求得整个状态序列最大值,即求
Q'=argQmaxP(Q|O,μ)
此时用维特比算法,先定义下维特比变量δt(i):
在时间t,HMM沿着一条路径到达状态si,并输出观察序列O=O1O2...Ot的最大概率:
δt(i)=maxP(q1q2...qt=si,O1O2...Ot|μ)
t t+1
上图中,对于(duìyú)从t时刻(shíkè)三个到t+1时刻(shíkè)的状态1,到底(dàodǐ)取状态1,2还是3,不是看单独状态1,2还是3的概率,而是看在状态1,2,3各自的维特比变量值乘以相应的状态转换概率,从中选出最大值,假设2时最大,那么记下t+1时刻状态1之前的路径是t时刻的状态2,以此类推。
δt(i)的递归关系式:
δt+1(i)=maxj δt(j)*aji*bi(Ot+1),为了记忆路径,定义路径变量ψt(i),记录该路径上的状态si的前一个状态。
回到顶部
维特比算法
step1初始化:
δt(i)=πi*bi(O1),1≤i≤N
ψt(i)=0
step2归纳计算:
δt(i)=max1≤j≤N δt-1(j)*aji*bi(Ot),2≤t≤T;1≤i≤N
记忆路径 ψt(i)=arg[max1≤j≤Nδt-1(j)*aji*bi(Ot)]
step3终结:
QT'=argmax1≤i≤N [δT(i)]
P'(QT')=max1≤i≤N [δT(i)]
step4路径回溯:
qt'=ψt+1(qt+1') ,t=T-1,T-2...1
回到顶部
时间复杂度
计算某时刻的某个状态的前向变量需要比较前一时刻的N个状态,此时时间复杂度为O(N),每个时刻有N个状态,此时时间复杂度为N*O(N)=O(N2),又有T个时刻,所以时间复杂度为T*O(N2)=O(N2T)。
回到顶部
程序(chéngxù)例证
step1初始化:
δ1
(1)=0.2*0.5=0.1 ,δ1
(2)=0.4*0.4=0.16,δ1(3)=0.4*0.7=0.21
step2归纳(guīnà)计算:
δ2
(1)=max[0.1*0.5,0.16*0.3,0.21*0.2]*0.6
...
step3终结(zhōngjié):
最佳(zuìjiā)路径是δ4
(1)δ4
(2)δ4(3)最大的一个对应的状态
step4回溯:
从最后一个状态往回返
程序代码
#include
#include
#include
intmain()
{
floata[3][3]={{0.5,0.2,0.3},{0.3,0.5,0.2},{0.2,0.3,0.5}};
floatb[3][2]={{0.5,0.5},{0.4,0.6},{0.7,0.3}};
floatresult[4][3];
intlist[4]={0,1,0,1};
intmax[4][3];
floattmp;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 马尔科夫 模型 转载 21