马尔科夫模型(转载)

隐马尔可夫模型（一）马尔可夫模型马尔可夫模型（Markov Model)描述了一类随机变量随 时间而变化的随机函数。考察一个状态序列（此时随机变量为状态值），这些状态并不是相互独立的，每个状态的值依赖于序列中此状态之前的状态。数学描述：一个系统由 N 个状态 S= s1,s2,.sn,随着时间的推移，该系统从一个状态转换成另一个状态。Q= q1,q2,.qn为一个状态序列，q iS,在 t 时刻的状态为 qt,对该系统的描述要给出当前时刻 t 所处的状态 st，和之前的状态 s1,s2,.st, 则 t 时刻位于状态qt 的概率为：P(q t=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 s3A= 则状态序列 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隐马尔可夫模型（二）隐马尔可夫模型的构成在马尔可夫模型中，每一个状态都是可观察的序列，是状态关于时间的随机过程，也成为可视马尔可夫模型（Visible Markov Model,VMM）。隐马尔科夫模型（Hidden Markov Model,HMM）中的状态是不可见的，我们可以看到的是状态表现出来的观察值和状态的概率函数。在隐马模型中，观察值是关于状态的随机过程，而状态是关于时间的随机过程，因此隐马模型是一个双重随机过程。当考虑潜在事件随机生成表面事件时，可以用 HMM 解决。举个例子，说明隐马模型： 有 4 个暗箱，放在暗处，每个箱子里有 3 种不用颜色的球（红、橙、蓝），从箱子往外拿球是有一定规律的，现在工作人员从暗处的箱子中取球，去了 5 次，我们看到额观察序列是：红蓝蓝橙红。这个过程就是一个隐马模型。暗处的箱子表示状态，箱子的个数表示状态的个数，球的颜色表示状态的输出值，球的颜色个数表示状态输出观察状态的个数，从一个箱子转换成另一个箱子表示状态转换，从暗处箱子中取出的球的观察颜色表示状态的输出序列。因此可以归纳隐马模型的 5 个组成状态：（1）模型中的状态个数 N(例子中的箱子个数)；（2）每个状态的可以输出的不同观测值 M（例子中的球的颜色数目）；（3）状态转移矩阵 A= aij(例子中 aij 表示从第 i 个箱子转移到第 j 个箱子的概率），其中 aij 满足条件：I. aij0， 1i,jNII. aij= P(qt=sj|qt-1=si), III. =1（4）发射矩阵 B=bj(k)，即从状态 sj 观察到符号 vk 的概率分布矩阵.(b j(k)在例子中表示从的 j 个箱子中拿出第 k 个颜色的概率），其中 bj(k)满足条件：I. bj(k)0， 1jN; 1kMII. bj(k)= P(Ot=vk|qt=sj), III. =1（5）初始状态概率分布 = j.(例子中一开始到第 j 个箱子的概率），其中 j满足条件：I. j(k)0， 1jNII. j= P(q1=sj),III. =1一般，一个 HMM 即为五元组 =N,M,A,B,，为了简便，常简记为三元组=A,B,。 HMM 有三个基本问题：（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 个状态.t T 时刻有 N 个状态，这样的话一共有N*N*.*N= NT 种组合，时间复杂度为 O(NT),计算时，就会出现“指数爆炸”，当 T 很大时，简直无法计算这个值。为解决这一问题，Baum 提出了前向算法。归纳过程首先引入 前向变量 t(i):在时间 t 时刻，HMM 输出序列为 O1O2.OT,在第 t 时刻位于状态 si 的概率。当 T=1 时，输出序列为 O1,此时计算概率为 P(O1|）：假设有三个状态（如下图）1、2 、3 ，输出序列为 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(O 1O2,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)所以：P(O 1O2|）=P(O 1O2,q2=s1|）+ P(O1O2,q2=s1|）+ P(O1O2,q2=s1|）=2(1) + 2(2) + 2(3)以此类推。前向算法step1 初始化： 1(i) = i*bi(O1), 1iN step2 归纳计算: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.21step2： 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 int main()float a33 = 0.5,0.2,0.3,0.3,0.5,0.2,0.2,0.3,0.5;float b32 = 0.5,0.5,0.4,0.6,0.7,0.3;float alpha43;int i,j,k, count = 1; /output listint list4 = 0,1,0,1;/step1:Initializationalpha00 = 0.2 * 0.5;alpha01 = 0.4 * 0.4;alpha02 = 0.4 * 0.7;/step2:iterationfor (i=1; i#include #include int main()float a33 = 0.5,0.2,0.3,0.3,0.5,0.2,0.2,0.3,0.5;float b32 = 0.5,0.5,0.4,0.6,0.7,0.3;float result43;int list4 = 0,1,0,1;result30 = 1;result31 = 1;result32 = 1;int i,j,k, count = 3;for (i=2; i>=0; i-)for(j=0; j#include #include int main()float a33 = 0.5,0.2,0.3,0.3,0.5,0.2,0.2,0.3,0.5;float b32 = 0.5,0.5,0.4,0.6,0.7,0.3;float result43;int list4 = 0,1,0,1;int max43;float tmp;/step1:Initializationresult00 = 0.2*0.5; result01 = 0.4*0.4;result02 = 0.4*0.7;int i,j,k, count = 1, max_node;float max_v;/step2:归纳运算for (i=1; i tmp)tmp = resulti-1k * akj* bjlistcount;m