《应用随机过程教程》教学资源（参考资料）与在算法和智能计算中的应用——第10章隐马氏模型（Hidden Markov Model, HMM）及其应用.pdf_大学文库

265 龚光鲁, 钱敏平著应用随机过程教程 – 与在算法和智能计算中的应用清华大学出版社, 2003 第 10 章隐马氏模型（Hidden Markov Model, HMM）及其应用１．熵与相对熵１. 1 离散分布的熵与相对熵熵的概念出自 C.Shannon. 引进这个指标的目的在于刻画一个离散分布(一个离散随机变量)或一个分布密度(一个连续型随机变量)的不确定性的大小. 也就是说知道了此随机变量的取值所获得的信息的大小. 定义１０．１对于离散分布p ( , , , ) = p1 L pn L , 我们定义它的熵为 H(p)=- åi i i p ln p . 又定义分布 p 关于分布 q ( , , , ) = q1 L qn L 的 Kullback- Leibler 相对熵为 h（p,q）=åi i i i q p p ln . 命题１０．２相对熵 h（p,q）≥0，而且 h（p,q）=0, 当且仅当 p = q 时成立等号. 证明 [0,¥) 上函数 g(t)=t -1 - ln t D 在t ¹ 1时恒正 (这一结论可由 g 的导数直接可以看出), 且 g(1) = 0 ．取 i i p q t = ，于是 i i p q ln ≤ i i p q -1, 即 i i q p ln i i p q ³ 1- ，而且等号仅当 = 1 i i q p 时成立．从而有 åi i i i q p p ln ³ å - = i i i i p q p (1 ) 0 ．所以结论成立．这个命题表明，相对熵在相当程度上表达了 p 与 q 的差别：当 p = q 时，h（p,q）=0. 而当所有的 pi 都与 qi 接近时，h（p,q）就很小. 从而 h（p,q）可以看成 p 与 q 之间的一种 “准距离”. 这里我们之所以称它为准距离，是因为它既不对称 (即 h（p,q）¹ h（q,p）)，也不满足三角形不等式。所以不满足第 9 章中的距离公理. 例１０．３ (有限个值的分布的熵) 分布 p ( , , ) 1 N = p L p 的熵满足 H(p)= p p N i i i - å ln £ ln . 且等号当且仅当分布在 N 个值均匀时成立. 即以相同概率取 N 个值的分布(称为离散均匀分布)的熵最大. 证明记分布 n = ) 1 , , 1 ( N N L ．于是本结论是相对熵不等式 h（p,n）≥0 的变形. 例１０．４ (数学期望固定条件下的离散的最大熵分布) 假定存在实数a ,使 x ³ ,(i ³ 1) i a . 对于固定的 ( , , , ) x1 L xn L 与 m , 在满足 P(x = xi ) = pi ,Ex = m

267 H ò = d d d d dx dx q x x p x x p p x x L L L L 1 1 1 1 ( , , ) ( , , ) ( ) ( , , ) ln ), ò = d d d d dx dx q x x p x x h p q p x x L L L L 1 1 1 1 ( , , ) ( , , ) ( , ) ( , , )ln . 同样也有相对熵是非负的．从而由熵的定义, 再利用相对熵非负性质可推得下述结论: 例１０．７ (半直线上均值已知时的最大熵分布密度) 在［0，¥）上具有同均值m 的密度中, 指数分布 m Exp 1 的熵最大.这个最大熵为1+ log m . 例１０．８ (均值与方差已知的分布密度的最大熵) 在均值为 m ，方差为 2 s 的分布密度中, 正态分布的熵最大. 例１０．９ (均值向量与(协)方差矩阵已知的有联合密度的最大熵) 在均值向量为m ，方差矩阵为S 的多维密度中, Gauss 分布 N(m,S) 的熵最大. 请读者自己写出这个最大熵的表达式. 例１０．１０ (有限区间上的最大上密度) 在有限区间[a,b]上取值的分布密度中, 均匀分布的熵最大. 此最大熵为ln( b - a) . 例１０．１０也可以推广到多维情形. 例１０．１１ (在取值于混合概率向量的分布密度中, 关于某个概率向量的平均相对熵给定条件下, 求具最大相对熵的密度) 令样本空间为 W = { x = ( , , ) : 0 1,( ), 1} x1 L xd < xi < i £ d x1 +L+ xd = . W 中的点可以解释为概率向量, 而取值于W 的连续型随机变量的分布密度可以解释为 ”广义的混合分布”. 给定 z = (z1 ,L,zd )Î W , 把 W 中的点看成概率向量, 就有相对熵 h(z, x) , 它是取值于 W 的 x函数. 对于一个取值W 的分布密度 p( x ) ( , , ) x d p x L x D = 定义对于这个分布密度的平均相对熵: m( z ) h(z, x)p( x)d x ò = D ．我们要在平均相对熵 m(z) 相等的分布密度 p(x) 中 , 选取一个 ( ) * p x ，使其熵 ò - p ( x)ln p (x)d x * * 达到最大. 为此我们断言：如下的 Gibbs 型分布密度 ( ) ( ) * p x = C z (z)h( z,x ) e -l (= C(z) ) ( ) ( ) 1 ( ) ln i 1 d i i z z d z z z z z e x x l l l L - å , 其中 ( ) ( , ) 1 ( ) ( ) - - ò C z = e d x l z h z x , l(z)满足 z C z h z x e d x (z)h(z,x) ( ) ( ) ( , ) l m - ò = ，就是我们要的具有最大熵的密度 . 证明如下: 对于任意一个满足 m( z ) h(z, x)p( x)d x ò = D 的分布密度 p(x) ．由相对熵不等式

0≤Mp)-3h一DA)dx C(=)e H(p)+λ(=)4(=)-hC(=) 得到 (p)≤A(=)(z)-hC(x 于是我们有 C(e-=)In[ C(=e A(=)h(二,x) H(p) dx=(=)(=)-nC()≥H(p) [注1]上面我们用相对熵h(=,x)作为准距离,而不是用更为合理的[h(z,x)+(x,= 也可以用与它相应的h(x,=),只要易于计算,不管用那一个都行 [注2] Dirichlet分布的密度函数为 f(x1…,x)=Cx-1…x c=n(a,a-t( dd) r(a)=xoeg-tdr +a 例10.11中的最大熵分布恰是 Dirichlet分布.在生物信息论中,常常需要估计概率向量组成的空间上的分布密度.例10.11说明,在平均相对熵给定的条件下, Dirichlet分布是”最吃亏的”分布.用它作为先验分布”看起来更为保险".这就解释了在生物信息论中,人们常常喜欢用 Dirichlet分布作为先验分布的原因相对熵应用的一个实例一在各个测试特征(统计量)中选择几个最为有效的相对熵方法 (特征量选取的相对熵方法) 假定我们有两组性质完全不同的群体,例如一组是健康人,另一组是SARS(非典型性肺炎)病毒持带人.又假定人们已经提出了N种区别健康人与SARS病毒持带人的不同特征。我们要在其中选取区别效果最好的M个特征.相对熵方法是较为有效的一种方法,其实际操作为用一个给定的区分特征,对上面的一组健康人测定了一组数据,简称为甲数据组:又对上面的 SARS( Severe Acute Respiratory Syndrome)病毒持带人测定了一组数据,简称为乙数据组.再进行如下的步骤: (1)分别找出此两个数据组的近似分布:从数据组出发,应用统计中的核估计的思想,分别得到其近似分布密度曲线 (2)计算此两个分布密度的相对熵h 实践证明,用数值计算求此两个分布密度的相对熵,对于计算格点大小的划分并不太敏感.相反地,如果直接将两个直方图作为离散分布求相对熵,则对于直方图的计算格点大小的划分十分敏感, 以致得到的计算结果很不稳定) (3)将甲乙两组数据合并再随机地重组为和以前个数相同的两组(随机地重排( Random Sorting)后,再按原来的各组的个数顺序分成两组),用(1),(2)步骤计算其相对熵 (4)重复地作(3)多次(例如1万次),计算其中相对熵大于h。的次数所占的频率,记 P

268 0 ( , ) * £ h p p d x C z e p x p x ò - z h z x = ( ) ( , ) ( ) ( ) ( )ln l = - H( p) + l(z)m(z) - ln C(z) 得到 H( p) £ l(z)m(z) - ln C(z) . 于是我们有 H( * p ) = C z e C z e d x z h z x z h z x ) ln[ ( ) ] ( ) ( , ) ( ) ( , ) l l - - ò - （＝l(z)m(z) - ln C(z) ³ H( p ). [注 1] 上面我们用相对熵h(z, x) 作为准距离, 而不是用更为合理的 [ 2 1 h(z, x) + h( x,z)] . 也可以用与它相应的 h(x, z) , 只要易于计算,不管用那一个都行. [注２] Diriclet 分布的密度函数为 { 1) 1 1 1 1 1 1 ( , , ) + + = - - = d d d d x x f x L x Cx Lx I L a a , 其中 ò ¥ - - G = G + + G G = 0 1 1 1 , ( ) ( ) ( ) ( ) C x e dx x d d a a a a a a L L . 例１０.１１中的最大熵分布恰是 Dirichlet 分布. 在生物信息论中，常常需要估计概率向量组成的空间上的分布密度．例１０.１１说明，在平均相对熵给定的条件下，Dirichlet 分布是＂最吃亏的＂分布．用它作为先验分布＂看起来更为保险＂．这就解释了在生物信息论中，人们常常喜欢用 Dirichlet 分布作为先验分布的原因．相对熵应用的一个实例－在各个测试特征（统计量）中选择几个最为有效的相对熵方法（特征量选取的相对熵方法）假定我们有两组性质完全不同的群体，例如一组是健康人，另一组是SARS（非典型性肺炎）病毒持带人．又假定人们已经提出了 N 种区别健康人与 SARS 病毒持带人的不同特征．我们要在其中选取区别效果最好的 M 个特征．相对熵方法是较为有效的一种方法，其实际操作为: 用一个给定的区分特征，对上面的一组健康人测定了一组数据，简称为甲数据组；又对上面的 SARS (Severe Acute Respiratory Syndrome) 病毒持带人测定了一组数据，简称为乙数据组．再进行如下的步骤：（１）分别找出此两个数据组的近似分布：从数据组出发，应用统计中的核估计的思想，分别得到其近似分布密度曲线；（２）计算此两个分布密度的相对熵 0 h ；（实践证明，用数值计算求此两个分布密度的相对熵，对于计算格点大小的划分并不太敏感．相反地，如果直接将两个直方图作为离散分布求相对熵，则对于直方图的计算格点大小的划分十分敏感 , 以致得到的计算结果很不稳定）．（３）将甲乙两组数据合并,再随机地重组为和以前个数相同的两组 (随机地重排（Random Sorting）后，再按原来的各组的个数顺序分成两组)，用（１），（２）步骤计算其相对熵；（４）重复地作（３）多次（例如１万次），计算其中相对熵大于 0 h 的次数所占的频率，记为 p ．

269 于是对应于一个区分特征就对应地有一个 p 值, 它是一个客观的标准，和各种测试方法的结果（统计量）的绝对大小、量纲都无关．如果要在 N 个不同的用以区分是否感染了SARS 的特征中选取 M 个相对地最为有效的特征，我们只需选取对应的 p 值最小的前 M 个特征即可．２．隐 Markov 模型 (HMM) ２．１一个实例先举一个例子以直观地理解这个模型的实质. 例１０.１２设某人在三个装有红白两种颜色的球的盒子中，任取一个盒子，然后在此盒子中每次抽取一个球，连续地抽取 m 次．假定各个盒子的内容与抽取方式分别为：红球数白球数每次抽取方式盒 1 90 10 随机取一球，记下颜色后不放回，而放进一个与它颜色不同的球. 盒 2 50 50 随机取一球，记下颜色后放回盒 3 40 60 随机取一球，记下颜色后不放回，并放进一个红球. 现在如果某人用上述方法得到了一个记录(红,红,红,红,白)（即m = 5 ），但是不告诉我们球出自哪个盒子，我们应如何推测他是从哪个盒子中抽取的观测样本呢 ? 令 = (k ) n S 在第k 个盒子 (k = 1,2,3) 中第 n 次抽取完成后在各盒中的红球数．那么，在 k 分别固定为１，２，３时，{ : 0} ( ) S n ³ k n 分别为 Markov 链，且其概率转移矩阵分别为: ï ï ï î ï ï ï í ì - = + = - = 0 ( ) ( 1) 100 1 ( 1) 100 (1) 其它情形 j i i j i i pij ，（逢红，红减１；逢白，红加１）， î í ì ¹ = = 0 ( ) 1 ( ) (2) j i j i pij ，（内容总是不变） ï ï ï î ï ï ï í ì - = + = = 0 ( ) ( 1) 100 1 ( ) 100 (3) 其它情形 j i i j i i pij ．（逢红不变；逢白，红加１）而且初值分别为： 90, 50, 40 (3) 0 (2) 0 (1) S0 = S = S = ．于是这３个盒子就分别对应于３个不同的 Markov 链模型．把这３个模型分别简记为 1 2 3 l ,l ,l ，并把某人观测到的样本序列中的第 n 个记为On ．即令 On =抽到的记录列中第n个记录中的白球数（只能为 1 或 0）. 此例是一个玩具模型. 从这个例子可以看出，在观测出自哪个盒子已知时，状态随机变

270 量序列{ }n S 与某人提供的观测随机变量序列{ } On 之间的条件概率计算的关系可以直观地写为： S O S Om i Sm Om Sm , , , , , , 0 1 1 L - -1 ，其中在前面的一段随机变量序列取定值的条件下，继后的那个随机变量取值的条件概率就完全确定了．而且在这３个模型下分别都有 ( | , , , ) ( | ) ( | ) 1 1 1 1 2 1 P S O S O S P S S P S S n+ L n n = n+ n = ， ( | , , , , , ) ( | ) ( | ) 1 1 1 1 1 2 1 P O O S O S O S P O S P O S n+ L m-i m- m m = n+ n = ．于是 ( , , , , , , ) P S0 O1 S1 LOm-i Sm-1 Om Sm ( ) ( | ) ( | ) ( | ) ( | ) ( | ) = 0 1 0 1 0 2 1 m m-1 m m-1 P S P O S P S S P O S LP O S P S S ．具体地，我们有在模型 l1下（把取到的球换色） (( , , , , ) (0,0,0,0,1) | ) P O1 O2 O3 O4 O5 = l1 =0.9×0.89×0.88×0.87×0.13≈0.08．在模型 l2 下（球的内容不变）， On 是独立同分布的随机变量序列，且 ÷ ÷ ø ö ç ç è æ 2 1 2 1 0 1 On ~ ，所以 (( , , , , ) (0,0,0,0,1) | ) P O1 O2 O3 O4 O5 = l2 5 ) 2 1 = ( ≈0.03．在模型 l3 下（取到红则不变，取到白则换为红球） (( , , , , ) (0,0,0,0,1) | ) P O1 O2 O3 O4 O5 = l3 = (0.4) ´ 0.6 » 4 0.015．再用 Bayes 公式分别得到（即取上面3 个概率的归一化值） P(l１｜(O1 ,O2 ,O3 ,O4 ,O5 ) = (0,0,0,0,1)) = 0.64， P(l２｜(O1 ,O2 ,O3 ,O4 ,O5 ) = (0,0,0,0,1)) = 0.24 P(l3 | (O1 ,O2 ,O3 ,O4 ,O5 ) = (0,0,0,0,1)) = 0.12．可见从第一盒抽出样本(红，红，红，红，白)的概率要比从其他两盒中抽出该样本的概率要大得多．这个模型的意义绝对不在于游戏，从中可以抽象出一种能广泛应用的数学模型－隐 Markov 模型（Hidden Markov Model，简记为 HMM）．在这个例子中的不同盒的抽取方式可以抽象为不同的编码方式. 而这个例子正启示了用隐 Markov 模型作模式识别的一种粗略梗概．２．２隐 Markov 模型的描述定义１０．１３设{X : n ³1} n 是取值于有限状态{1,L,L}的随机变量列, 称为状态链，X1 的分布称为其初始分布，记为 m ．假定 Xn 是时齐的 Markov 链．记 ( | ) 1 a P X j X i ij = n+ = n = ， ij i j L A a = , £ ( ) ． (10. 1) 为它的转移矩阵．假定 Xn 的取值，初始分布m 与转移矩阵 A , 都不能测量得到. 而能测量到的是另一个与它有联系的，且可以观测到的一个取值于与有限集 {n1 ,L,n M }的随机变量序列Yn , 称为观测链, 它们合起来还要求满足如下的隐 Markov 条件（HMM 条件）:

P(Y=y,X=x)=b1a42…by,a、-、b (10.2) 其中 N为样本观测的时间长度 X=(X1,…XN),Y=(H1,…,Y),y=(y1;…,yx),x=(1,…,) yn∈{1,VM},1≤in≤L,1≤n≤N,初始概率向量(初始分布)为=(μ1…,).由未知状态链与测量到的观测链一起(X,),就构成了隐 Markov模型,这里“隐”的含义是说状态链是隐藏起来的隐 Markov模型的基本假定是: 参数向量μ,参数矩阵A与B=(b1)(i∈{…,},l∈,…vM})都是未知的,我们将它们合记为参数组λ=(μ,A,B).参数组λ=(μ,A,B)完全确定了状态链与观测连的联合统计规律,所以,我们通常用一个λ表示一个隐 Markov模型,并称之为隐 Markov模型 λ(更确切地为隐 Markov链).在例 0.12中,3个不同的模型就对应了3个不同的参数组.只要令Xn=Sn,Y=On4,它们满足HM条件,因而纳入了隐 Markov模型的框架 (10.2)是(X,Y)的联合分布通过参数表达的形式,它是计算各种边缘概率与条件概率的出发点.而HM条件的含义是:状态链与观测链的联合分布是由一系列简单转移与条件概率的乘积表达的 2.3隐 Markov模型的等价表述由例10.12的启示,可以想到下面的等价条件命题10.14 HM条件等价于:对于任意的i∈(1,…,L}以及l∈{v1,…,vM},有 P(Yn=v|Xn=i,Yn1=ln13Xm1=v,…H1=1,X1=v1)=P(Yn=v2|Xn=1)=bn, P(Xn1=j|Xn=in=Vn,Xn1=in…,X1=1,=v1)=P(xn1=川X,=D)=an 这两个等式的证明只需利用条件概率的定义.所以我们把它留给读者.它们的直观含义就是: n与Xn1相对于历史条件的统计规律只与时间上最接近的Xn有关,而与其它更早的历史无关.在实际问题中,这是比较容易判断的 2.4非线性滤波作为隐 Markov模型的特例设Xn是取值于状态空间S={12…,L}的 Markov链,其样本不能被实际测量得到.而能测量到的是如下的Y的样本 8(Xn) 其中g是一个未知函数,{n}是独立同分布的随机干扰,只取有限个值,且与随机过程 Xn}独立.那么{Xn,Hn}就是一个(二维的)隐 Markov模型.这就把(10.5)的非线性滤波放进了HM的框架 2.5在应用中研究隐 Markov模型的主要方面 (1)从一段观测序列{k,k≤m}及已知模型λ=(μ,A,B)出发,估计Xn的最佳值, 称为解码问题.这是状态估计问题

271 i i y i i iN yN iN iN iN yN P Y y X x b a b a b 1 1 1 1 2 1 1 1 ( , ) - - - = = = m L ， (10. 2) 其中 N 为样本观测的时间长度，而 ( , , ) X = X1 L X N , ( , , ) Y = Y1 L YN , ( , , ) 1 N y = y L y , ( , , ) 1 N x = i L i , y n Î{n1 ,Ln M },1 £ i n £ L,1 £ n £ N , 初始概率向量（初始分布）为 ( , , ) m = m1 L mL .由未知状态链与测量到的观测链一起( , ) Xn Yn , 就构成了隐 Markov 模型，这里“隐”的含义是说状态链是隐藏起来的．隐 Markov 模型的基本假定是：参数向量m ，参数矩阵 A 与 il L M B b ´ D =( ) （ {1, , }, { , , } 1 M i Î L L l Î n L n ）都是未知的，我们将它们合记为参数组 l (m, A,B) D = .参数组 l (m, A,B) D = 完全确定了状态链与观测连的联合统计规律，所以,我们通常用一个l 表示一个隐 Markov 模型，并称之为隐 Markov 模型 l (更确切地为隐 Markov 链). 在例 10.12 中，３个不同的模型就对应了３个不同的参数组．只要令 1 , n = n Yn = On + X S ，它们满足 HMM 条件，因而纳入了隐 Markov 模型的框架． (10.2)是(X ,Y) 的联合分布通过参数表达的形式, 它是计算各种边缘概率与条件概率的出发点. 而 HMM 条件的含义是：状态链与观测链的联合分布是由一系列简单转移与条件概率的乘积表达的．２.３隐 Markov 模型的等价表述由例１０.１２的启示，可以想到下面的等价条件命题１０.１４ HMM 条件等价于: 对于任意的i Î (1,L, L}以及 l Î{n1 ,L,n M }，有 ( | , , , , , ) ( | ) , 1 1 1 1 1 1 1 1 n l n n n n l l n l n il P Y v X i Y i X Y i X P Y v X i b n D = = = =n = =n = = = = - - - - L (10. 3) ( | , , , , , ) ( | ) 1 1 1 1 1 1 1 1 P X j X i Y X i X i Y P X j X i n+ = n = n =nln n- = n- L = =nl = n+ = n = ij a D = , (10. 4) 这两个等式的证明只需利用条件概率的定义．所以我们把它留给读者．它们的直观含义就是： Yn 与 Xn+1 相对于历史条件的统计规律只与时间上最接近的 Xn 有关，而与其它更早的历史无关．在实际问题中，这是比较容易判断的．２．４非线性滤波作为隐 Markov 模型的特例设 Xn 是取值于状态空间S = {1,2,L, L} 的 Markov 链，其样本不能被实际测量得到．而能测量到的是如下的Yn 的样本 n X n wn Y = g( ) + ， (10. 5) 其中 g 是一个未知函数，{ } wn 是独立同分布的随机干扰，只取有限个值，且与随机过程 { } X n 独立．那么 { , } X n Yn 就是一个（二维的）隐 Markov 模型．这就把（１０．５）的非线性滤波放进了 HMM 的框架．２. ５在应用中研究隐 Markov 模型的主要方面 (1) 从一段观测序列{Y , k m} k £ 及已知模型l = (m, A,B) 出发, 估计 X n 的最佳值，称为解码问题. 这是状态估计问题

(2)从一段观测序列{Yk,k≤m}出发,估计模型参数组λ=({,A,B),称为学习问题.就是参数估计问题. (3)对于一个特定的观测链{2k≤m,已知它可能是由已经学习好的若干模型之所得的观测,要决定此观测究竟是得自其中哪一个模型.这称为识别问题.就是分类问题在实际问题中,这3个问题有时并不完全能分开.有时也并不需要解全3个问题.例如在语音识别或手写体汉字或数字的脱机识别中,我们只需要作(2)与(3),这相当于将一个”标准的”语音音素或一个”标准的”手写体汉字“学习成”一个隐 Markov模型,即把它与一个或几个特定的隐 Markov模型绠更确切地说,是特定的一组参数)相对应起来,以便把该模型作为这个音素或手写字的代表模板,这是学习相位;而在进一步用这些模板中的最合适者,作为对于一个需要识别的音素或手写字的分类归属,这是运转相位.至于归入那个模板最合适,就要用合理的距离,或准距离(常用的是相对熵),在此意义下优化 [注1]Xn也可以推广为:取值于平面有限格点的 Markov场,而与它的关系仍如上述这就定义了一个隐 Markov场 [注2]一般地,Yn还可以是连续型随机变量.如果记在Xn=x的条件下,Yn的条件分布密度为f,则λ=(μn,A,fx)就也称为一个(连续的)隐 Markov模型.这时∫常是分布类型已知而带有未知参数的密度.状态是连续的隐 Markov模型至今还未见有人使用 3解码问题-已知模型λ与观测Y=y时状态X的估计 3.1出现当前的观测的概率P(Y=y|)的计算我们仍旧沿用记号 X=(X1…,Xx),Y=(H1,…,Yx),y=(y1…,yx),x=(1,…,x) yn∈{v1;…vM} I<i<l1≤n≤N,初始概率向量μ=(μ1…,μ). 由(10.2),利用条件概率的性质容易算出 P(Y=y|X=(i1,…,x)λ)=b P(Y=y,X=x|1)=H1bam…b4、by P=y1元)=∑H1b1an…a,、b 对于1≤n≤N及观测样值Y=y,记(因为观测样值y是固定的,所以下面我们将在足标中把它略去) a (D=P(Y yn,Xn=iλ)(依赖y) (10.7) 则在模型λ给定下,关于观测资料(y1;…,yn)的长度n(n<N),我们有递推公式(称为向前递推公式或向前算法) an()=∑an()xbn (10.8) 由此得到 (1)基于an()的向前递推公式计算P(Y=y|)的步骤: 算初值a1()=Hbn, 272

272 (2) 从一段观测序列{Y , k m} k £ 出发, 估计模型参数组 l = (m, A,B) ，称为学习问题. 就是参数估计问题. (3) 对于一个特定的观测链{Y , k m} k £ , 已知它可能是由已经学习好的若干模型之一所得的观测, 要决定此观测究竟是得自其中哪一个模型．这称为识别问题. 就是分类问题. 在实际问题中，这 3 个问题有时并不完全能分开．有时也并不需要解全 3 个问题. 例如，在语音识别或手写体汉字或数字的脱机识别中，我们只需要作(2)与(3)，这相当于将一个 ”标准的” 语音音素或一个 ”标准的” 手写体汉字 “学习成”一个隐 Markov 模型, 即把它与一个或几个特定的隐 Markov 模型(更确切地说，是特定的一组参数)相对应起来，以便把该模型作为这个音素或手写字的代表模板, 这是学习相位; 而在进一步用这些模板中的最合适者, 作为对于一个需要识别的音素或手写字的分类归属, 这是运转相位. 至于归入那个模板最合适, 就要用合理的距离, 或准距离（常用的是相对熵）, 在此意义下优化. [注 1] Xn 也可以推广为: 取值于平面有限格点的 Markov 场, 而Yn 与它的关系仍如上述, 这就定义了一个隐 Markov 场 . [注 2] 一般地, Yn 还可以是连续型随机变量．如果记在 X x n = 的条件下, Yn 的条件分布密度为 f , 则 ( , , ) x l = m A f 就也称为一个（连续的）隐 Markov 模型. 这时 f 常是分布类型已知而带有未知参数的密度．状态是连续的隐 Markov 模型至今还未见有人使用．３解码问题 -- 已知模型 l 与观测Y = y 时状态 X 的估计３.１出现当前的观测的概率P(Y = y | l) 的计算我们仍旧沿用记号 ( , , ) X = X1 L X N , ( , , ) Y = Y1 L YN , ( , , ) 1 N y = y L y , ( , , ) 1 N x = i L i , y n Î{n 1 ,Ln M },1 £ i n £ L,1 £ n £ N , 初始概率向量 ( , , ) m = m1 L mN . 由(10. 2)，利用条件概率的性质容易算出 N i y iN yN P Y y X i L i b Lb 1 1 ( | ( , , ), ) = = 1 l = , i i y i i yN yN iN iN iN yN P Y y X x b a b a b 1 1 1 1 2 1 1 ( , | ) - - = = l = m L , N N N N N i i y i i i i i y i i P Y y b a a b 1 1 1 1 2 1 1 , , ( | ) å - = = L L l m ． (10. 6) 对于 1 £ n £ N 及观测样值 Y = y , 记（因为观测样值 y 是固定的, 所以下面我们将在足标中把它略去） ( ) ( , , , | ) an i = P Y1 = y1 L Yn = yn X n = i l (依赖 y ), (10. 7) 则在模型l 给定下, 关于观测资料( , , ) 1 n y L y 的长度 n (n < N) , 我们有递推公式(称为向前递推公式或向前算法) 1 ( ) ( ) 1 å + + = n iy j n n ji a i a j a b . (10. 8) 由此得到 (1) 基于 (i) an 的向前递推公式计算 P(Y = y | l) 的步骤：计算初值 1 ( ) 1 i iy a i = m b

273 用递推公式 1 ( ) ( ) 1 å + + = n iy j n n ji a i a j a b ， (10. 9) 最后得到结论 P(Y y | ) (i) N i = l = å a . (10. 10) 计算 P(Y = y | l) 也可以通过另一种途径, 为此记（观测样值 y 也是是固定的,我们也把它在足标中略去） ( ) (( , , | , ) bn i = P Yn+1 = y n+1 L YN = yN X n = i l . (10. 11) 则在模型l 给定下, 关于观测资料( , , ) 1 n y L y 的长度 n (n < N ) , 我们还有递推公式(称为向后递推公式或向后算法) 1 ( ) ( ) å +1 + = n jy j n n ij b i b j a b 这就得到计算P(Y = y | l) 的另一个算法, 即 (2) 基于 (i) bn 的向后递推公式计算 P(Y = y | l) 的步骤定义 (i) = 1 b N , 用递推公式 1 ( ) ( ) å +1 + = n jy j n n ij b i b j a b (10. 12) 最后得到结论 = = åi i iy P Y y i b 1 ( | ) ( ) l b0 m (10. 13) ３．２解码问题 -- 已知模型l 与观测Y = y 时状态 X 的估计令 g (i) P(X i |Y y, l) n = n = = , (10. 14) 那么 å å = = = = = = i n n n n n i n n i i i i P Y y X i P Y y X i i ( ) ( ) ( ) ( ) ( , | ) ( , | ) ( ) a b a b l l g . (10. 15) ( 推导的思路如下：令 F n (X ,Y ,m n) = s m m £ (右方表示括号内随机变量所生成的 s 代数), { , , } n 1 1 n n Y = Y = y Y = y - L , { , , } n n 1 n 1 N N Y = Y = y Y = y + + + L . 因为 l 是固定的 , 我们在下面记号中也把它（为了记号的方便, 我们在下面有时并不区分取概率的符号与取期望的符号,取概率也理解为取期望）．于是我们有 P(Y y, X i | l) = n = E[(P(Y y, X i | = = n = F n )] E[Y , X i,P(Y | X i, = n n = n n = - + F n )] E[Y , X i, P(Y | X i)] = n n = n n = - + P(Y , X i)P(Y | X i) = n n = n n = - + (i) (i) = an bn ). 对于解码问题的解决, 我们用如下两种考虑方法: 1．对单个时刻的状态的最大概率估计如果 * i 满足 ( ) max ( ) * i i n i N n g g = £ , 则取 * ^ X i n = . 单个时刻的状态的最大概率估计的长处在于简单易算. 但是它忽视了状态链在不同时刻之间的联系，也就不能充分地利用已知的信息. 下面的路径估计法，是在考虑不同时间的联系后的改进方法

274 2 路径的(轨道)最大概率估计 -- Viterbi 算法这是基于动态规划的思想的一种整体性考虑的方法（所谓动态规划实质上就是一种从后向前逐步取优的优化方法）. 令在时刻 n 取到状态 i 的各个路径的最大概率为 ( ) max ( , , , , , , | ) d n i i1 , ,i 1 P X n i X n 1 i n 1 X1 i 1 Yn y n Y1 y1 l n = = - = - = = = L - L L , (10. 16) 那么我们有 ( ) max ( ( ) ) 1 1 n iy j n ji i b j a n d d + + = . (10. 17) 用来计算它的实际程式是如下的 Viterbi 算法: 假定最佳路径为( , , ) ^ 1 ^ X L X N . 今设置一个从 1 ^ X n+ 得到 X n ^ 的对应 : ( 1 ) ^ 1 ^ 1 + + = + n n n yn X y X . 计算 (i) n d 与y n 的递推算法的具体设计如下: 设置初值 1 ( ) 1 i iy d i = m b ; 用递推公式 ( ) max ( ( ) ) 1 1 n iy j n ji i b j a n d d + + = ; 再定义 * 1 (i) j y n + = ，其中 * j 只要满足 n j i n i biy j a n * 1 ( ) ( ) * d 1 d + + = . (10. 18) 最终采取如下的向后递推算法 (相当于动态规划，动态规划的核心思想是：在一切最佳路径上的任意节点出发，其后也应该是最佳路径，因此就能从后向前地逐步求得最佳路径) 得到如下的“最佳”轨道估计( , , ) ^ 1 ^ X L X N ：计算终值 { : ( ) max ( )} * ^ X i i i j N N j N = Î d = d , (10. 19) 反向归纳地取 ( ) ^ 1 1 ^ Xn =yn+ X n+ . (10.20) ４学习问题 – 由观测Y = y 估计模型参数 l ４.1 状态链样本已知时的参数的频率估计设隐 Markov 模型的状态链有充分长的样本．把其中从状态i 到下一个时刻为状态 j 转移的频数记为 Aij ．那么，粗略地可取 å= = N j ij ij ij A A a 1 ^ 为 ij a 的估计. 同样设此观测链样本充分长, 记其中从状态 i 到同一时刻的观测l 转移的频数为Bij , 则可取 å= = M l il il il B B b 1 ^ 为 il b 的估计．不幸的是状态链是经过估计得到的，所以不修正地使用频率估计会增加误差. 再则, 这种估计也过于敏感. ４. 2 模型参数估计的 EM 算法的思想我们取 l 的最大似然估计 ^ l ，即它满足 ( | ) max ( | ) ^ l l l P Y = y = P Y = y (10.21)

《应用随机过程教程》教学资源（参考资料）与在算法和智能计算中的应用——第10章 隐马氏模型（Hidden Markov Model, HMM）及其应用

《应用随机过程教程》教学资源（参考资料）与在算法和智能计算中的应用——第10章隐马氏模型（Hidden Markov Model, HMM）及其应用