马尔科夫模型(转载)

隐马尔可夫模型（一）——马尔可夫模型

马尔可夫模型（Markov Model)描述了一类随机变量随时间而变化的随机函数。考察一个状态序列（此时随机变量为状态值），这些状态并不是相互独立的，每个状态的值依赖于序列中此状态之前的状态。

数学描述：一个系统由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

隐马尔可夫模型（二）——隐马尔可夫模型的构成

在马尔可夫模型中，每一个状态都是可观察的序列，是状态关于时间的随机过程，也成为可视马尔可夫模型（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. 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

一般，一个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个状态...tT时刻有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(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)

所以：P(O1O2|μ）=P(O1O2,q2=s1|μ）+ P(O1O2,q2=s1|μ）+ P(O1O2,q2=s1|μ）

=α2(1) + α2(2) + α2(3)

以此类推。。。

前向算法

step1 初始化：α1(i) = πi*bi(O1), 1≤i≤N 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.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

int main()

{

float a[3][3] = {{0.5,0.2,0.3},{0.3,0.5,0.2},{0.2,0.3,0.5}};

float b[3][2] = {{0.5,0.5},{0.4,0.6},{0.7,0.3}};

float alpha[4][3];