龚光鲁,钱敏平著应用随机过程教程一与在算法和智能计算中的应用 清华大学出版社,2003 第10章隐马氏模型( Hidden markov model,HM)及其应用 1.熵与相对熵 1.1离散分布的熵与相对熵 熵的概念出自C. Shannon.引进这个指标的目的在于刻画一个离散分布(一个离散随机 变量)或一个分布密度(一个连续型随机变量)的不确定性的大小.也就是说知道了此随机变量 的取值所获得的信息的大小 定义10.1对于离散分布p=(P1…Pn…),我们定义它的熵为 H(p)=∑php 又定义分布p关于分布q=( )的Kul|back- Le ibler相对熵为 P Pi 命题10.2相对熵h(p,q)≥0,而且h(p,q)=0,当且仅当p=q时成立等号. 证明[O,∞)上函数g(t)=t-1-ht在t≠1时恒正(这一结论可由g的导数直接可以看 ),且g()=0.取t=9,于是h9≤9-1,即hP≥1-9,而且等号仅当 Pi Pi P=1时成立.从而有 ∑p2h2≥∑p-9)=0 q P 所以结论成立 这个命题表明,相对熵在相当程度上表达了p与q的差别:当p=q时,h(p,q)=0.而 当所有的p都与q1接近时,h(p,q)就很小.从而h(p,q)可以看成p与q之间的一种 准距离”.这里我们之所以称它为准距离,是因为它既不对称(即h(p,q)≠h(q,p)), 也不满足三角形不等式。所以不满足第9章中的距离公理 例10.3(有限个值的分布的熵) 分布p=(P12…,PN)的熵满足 ∑p,hP,≤hN 且等号当且仅当分布在N个值均匀时成立.即以相同概率取N个值的分布(称为离散均匀分 布)的熵最大 证明记分布nN’).于是本结论是相对熵不等式h(p,n)≥0的变形 例10.4(数学期望固定条件下的离散的最大熵分布) 假定存在实数a,使x1≥a,(≥1).对于固定的(x1…,xn;…)与μ,在满足 P(=x)=p1,E5=
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
的离散分布p=(P1…,pn…)中,具有最大熵的分布为p,且 P 其中λ满足条件 这个最大熵为u20-hC 证明对于任意λ≠0,只要∑e<m,相对熵不等式 0≤h(p,p') In P Pi SB+∑px-hC 就是 (p)=∑Php1≤-hC 所以 H(p)=∑Ce-lnCe]=-hC≥H) 例10.5(数学期望和方差都固定时的最大熵) 在均值为μ,方差为02,且取值为x4(k=1.2,…)的离散分布中,分布p (x2-a)2 PA ,C=( 的熵最大,此最大嫡为+(-a)2 hC,其中α,βB满足 (x-a)2 (=0,1,2),p xe ∑e")=D∑e"1∑xej (证明类似) 1.2分布密度的熵与相对熵 定义1o.6对于概率分布密度,我们可以仿效前面的思想,把分布密度p(x)的熵(其 实是微分熵)定义为 H(p)=-p(x)hn p( 而把分布密度p(x)对分布密度q(x)的相对熵定义为 ,)=p(r)In P 这个定义可以推广到多维密度p(x1,…x)与q(x1,…,x)
266 的离散分布 p ( , , , ) = p1 L pn L 中, 具有最大熵的分布为p * , 且 å - - - = = i x x i i i p Ce ,(C ( e ) ) * l0 l0 1 , 其中l0满足条件 å < ¥ - i xi e l0 , å < ¥ - i x i i x e l0 , i i x i i i x e x e 0 0 l l m - - å = å , 这个最大熵为 ml０ - ln C . 证明 对于任意 l ¹ 0 , 只要 å < ¥ - i xi e l , 相对熵不等式 0 £ h（p,p * ） å - = i x i i Ce i p p l ln = å + å - i i i i pi ln pi l p x ln C 就是 H(p)= p p C i i i - å ln £ lm - ln . 所以 H(p * ) = -å = - ³ - - Ce Ce C i xi ln[ ] ln 0 0 0 l m l l H(p). 例１０．５ （数学期望和方差都固定时的最大熵） 在均值为μ，方差为σ 2 ，且取值为 k x (k = 1,2,L)的离散分布中，分布 p * : 1 ( ) ( ) * , ( ) 2 2 2 2 - - - - - = = å k x x k k k p Ce C e b a b a 的熵最大, 此最大熵为 ln C ( ) 2 2 2 - + - b s m a , 其中a, b 满足 ( ) ,( 0,1,2) 2 2 ( ) å < ¥ = - - x e l k x l k k b a , å - - k xk e 2 2 ( ) b a m , 2 2 ( ) å - - = k x k k x e b a å = - - 2 ( ) 2 ( ) 2 2 k x k e b a s [ ] 2 2 ( ) å - - k x k e b a [ ] 2 2 ( ) 2 å - - k x k k x e b a å - - - k x k k x e 2 ( ) ( ) 2 2 b a . (证明类似). １.２ 分布密度的熵与相对熵 定义１０.６ 对于概率分布密度, 我们可以仿效前面的思想, 把分布密度 p(x) 的熵 (其 实是微分熵)定义为 H ò ( p) = - p( x)ln p(x)dx . 而把分布密度 p(x)对分布密度 q(x)的相对熵定义为 ò = dx q x p x h p q p x ( ) ( ) ( , ) ( )ln . 这个定义可以推广到多维密度 ( , , ) 1 d p x L x 与 ( , , ) 1 d q x L x :
()=Jmx…x)h列(x1…工) dx1…dx,) Mpq)-mx…x)h“在 gx 同样也有相对熵是非负的.从而由熵的定义,再利用相对熵非负性质可推得下述结论 例10.7(半直线上均值已知时的最大熵分布密度) 在[0,∞)上具有同均值μ的密度中,指数分布EP1的熵最大这个最大熵为1+logH 例10.8(均值与方差已知的分布密度的最大熵) 在均值为,方差为σ2的分布密度中,正态分布的熵最大 例1o.9(均值向量与(协)方差矩阵已知的有联合密度的最大熵) 在均值向量为μ,方差矩阵为Σ的多维密度中, Gauss分布N(μ,Σ)的熵最大.请读者自 己写出这个最大熵的表达式 例10.10(有限区间上的最大上密度) 有限区间[a,b]上取值的分布密度中,均匀分布的熵最大.此最大熵为m(b-a) 例10.10也可以推广到多维情形 在取值于混合概率向量的分布密度中,关于某个概率向量的平均相对熵 给定条件下,求具最大相对熵的密度) 令样本空间为 ={x=(x1…,x4):0<x1<1,(≤d),x1+…+x4=1 Ω中的点可以解释为概率向量,而取值于Ω的连续型随机变量的分布密度可以解释为”广义 的混合分布”.给定z=(1,…,4)∈Ω,把Ω中的点看成概率向量,就有相对熵h(二,x), 它是取值于Ω的x函数.对于一个取值g的分布密度p(x)=p(x2…,xa)定义对于这个分布 密度的平均相对熵 u( )=he,x)p(x)dx 我们要在平均相对熵μ(-)相等的分布密度p(x)中,选取一个p(x),使其熵 p(x)hp(x)dx达到最大 为此我们断言:如下的 Gibbs型分布密度 p(x)=(=)e-i(()= C(/e (2: \n4oP-1.xd-) 其中 -()h(x)dx) λ(-)满足 ()=C()=、x)))dx, 就是我们要的具有最大熵的密度·证明如下:对于任意一个满足以(=)=h(=,x)p(x)d 的分布密度p(x).由相对熵不等式 267
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 ．
于是对应于一个区分特征就对应地有一个p值,它是一个客观的标准,和各种测试方法的结果 (统计量)的绝对大小、量纲都无关.如果要在N个不同的用以区分是否感染了SARS的特征中 选取M个相对地最为有效的特征,我们只需选取对应的p值最小的前M个特征即可 2.隐 Markov模型(HMMD 2.1一个实例 先举一个例子以直观地理解这个模型的实质 例10.12设某人在三个装有红白两种颜色的球的盒子中,任取一个盒子,然后在此 盒子中每次抽取一个球,连续地抽取m次.假定各个盒子的内容与抽取方式分别为 红球数白球数每次抽取方式 盒19010随机取一球,记下颜色后不放回,而放进一个与它颜色不同的球 盒250 随机取一球,记下颜色后放回 随机取一球,记下颜色后不放回,并放进一个红球 现在如果某人用上述方法得到了一个记录(红,红,红,红,白)(即m=5),但是不告诉 我们球出自哪个盒子,我们应如何推测他是从哪个盒子中抽取的观测样本呢? S6)=在第k个盒子(k=1,2,3)中第n次抽取完成后在各盒中的红球数 那么,在k分别固定为1,2,3时,{S):n≥0}分别为 Markov链,且其概率转移矩阵 分别为 (=i-1) (=i+1),(逢红,红减1;逢白,红加1) 0(其它情形) p=100≠’(内容总是不变) (=i) 100 +1).(逢红不变;逢白,红加1) 0(其它情形 而且初值分别为:S0=90,502)=50,S03)=40.于是这3个盒子就分别对应于3个不同的 Markoⅴ链模型.把这3个模型分别简记为λ1,2,3,并把某人观测到的样本序列中的第n个 记为O.即令 On=抽到的记录列中第n个记录中的白球数(只能为1或0) 此例是一个玩具模型.从这个例子可以看出,在观测出自哪个盒子已知时,状态随机变
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）. 此例是一个玩具模型. 从这个例子可以看出，在观测出自哪个盒子已知时，状态随机变
量序列{Sn}与某人提供的观测随机变量序列{On}之间的条件概率计算的关系可以直观地写 S0,O12S1 其中在前面的一段随机变量序列取定值的条件下,继后的那个随机变量取值的条件概率就完全 确定了.而且在这3个模型下分别都有 P(SnIO, S,,O S)=P(Sn+ISn)=P(S,IS,), P(OO,S,,"Om-,Sm_,On, Sm)=P(onISm)=P(O2 IS,) 于是 P(So, O, SI,.Omi,Sm-l, Om, Sm) =P(SoP(O, I So)P(, ISo)P(O,IS)-P(Om Sm-pP(Sm I_) 具体地,我们有 在模型气下(把取到的球换色) P(O1,O2,O3O42O3)=(00,00.1)141)=0.9×0.89×0.88×0.87×0.13≈0.08 在模型2下(球的内容不变),O是独立同分布的随机变量序列,且On-1 22 所以 P(O,O2O3O4O3)=0,0.0,0.1)2)=()3≈0.03 在模型λ3下(取到红则不变,取到白则换为红球) P(O,O2,O2O4,O3)=00001)123)=0.4)4×06≈0.015 再用 Bayes公式分别得到(即取上面3个概率的归一化值) P(O1,O2,O3O4O)=(0.0.0,0,1)=0.64 P(A2O,O2,O3,O4,O3)=(0001)=0.2 P(A3(O1,O2,O3,O4,O3)=(00,0,1))=0.12 可见从第一盒抽出样本(红,红,红,红,白)的概率要比从其他两盒中抽出该样本的概率要 大得多 这个模型的意义绝对不在于游戏,从中可以抽象出一种能广泛应用的数学模型一隐 Markov 模型( Hidden markov model,简记为HMM).在这个例子中的不同盒的抽取方式可以抽象 为不同的编码方式.而这个例子正启示了用隐 Markov模型作模式识别的一种粗略梗概. 2.2隐 Markov模型的描述 定义10.13设{Xnn≥l是取值于有限状态{…,D}的随机变量列,称为状态 链,X1的分布称为其初始分布,记为μ·假定Xn是时齐的 Markov链.记 au=P(n=jIX,=i), A=(ai)ijsL (10.1) 为它的转移矩阵.假定Xn的取值,初始分布μ与转移矩阵A,都不能测量得到.而能测量到 的是另一个与它有联系的,且可以观测到的一个取值于与有限集{v1,…,VM}的随机变量序 列Y,称为观测链,它们合起来还要求满足如下的隐 Markov条件(HM条件) 270
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
用递推公式an1()=∑an(b (10.9) 最后得到结论P(Y=y14)=∑ax() (10.10) 计算P(Y=yλ)也可以通过另一种途径,为此记(观测样值y也是是固定的,我们也把它在 足标中略去) B,(O=P(OYMI=YH,.YN=yNIX=i,n) (10.11) 则在模型λ给定下,关于观测资料(y1;…,yn)的长度n(n<N),我们还有递推公式(称为向 后递推公式或向后算法) B()=∑Bn1()anbm 这就得到计算P(Y=y|)的另一个算法,即 (2)基于B()的向后递推公式计算P(=y)的步骤 义Bk() 用递推公式B2()=∑Bn(x,bm (10.12) 最后得到结论P(Y=y14)=∑()Hbm (10.13) 3.2解码问题一已知模型λ与观测Y=y时状态X的估计 yn()=P(Xn=i|=y,元), (10.14) 那么 rn(= P(r=y,X=il2) n(1)Bn(1) (10.15) ∑P(Y=y,X2=14)∑an()B2( (推导的思路如下:令7n=0(Xm,Ym,m≤n)(右方表示括号内随机变量所生成的σ代数) Yn={11= n =Y yn1…,Yy=y}.因为元是固定的,我们在下面记 号中也把它(为了记号的方便,我们在下面有时并不区分取概率的符号与取期望的符号,取概率也理解为取期 望).于是我们有 P(r =y, Xn=i2)=E[(P(r=y, Xn=i7n]=ElYn,Xn=i, P(n|,=i,7n) EIY, Xn=i, P(Y IX,=D]= P(Y, X, =iP(Y IX, =i=a,(DB,(i)) 对于解码问题的解决,我们用如下两种考虑方法 1.对单个时刻的状态的最大概率估计 如果满足yn()= maxin y(),则取Xn=i 单个时刻的状态的最大概率估计的长处在于简单易算.但是它忽视了状态链在不同时刻 的联系,也就不能充分地利用已知的信息.下面的路径估计法,是在考虑不同时间的联系 改进方法
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 = . 单个时刻的状态的最大概率估计的长处在于简单易算. 但是它忽视了状态链在不同时刻 之间的联系，也就不能充分地利用已知的信息. 下面的路径估计法，是在考虑不同时间的联系 后的改进方法
2路径的(轨道)最大概率估计- Viterbi算法 这是基于动态规划的思想的一种整体性考虑的方法(所谓动态规划实质上就是一种从后向 前逐步取优的优化方法).令在时刻n取到状态i的各个路径的最大概率为 8n()=max4P(Xn=i,Xn1=in1,…,X1=i,Yn=yn,…1=y14),(10.16 那么我们有 8n+1(i)=biy,, max, (8n()aji) (10.17) 用来计算它的实际程式是如下的 Viterbo i算法:假定最佳路径为(X1,…,XN).今设置 个从Xm1得到Xn的对应vn+1:Xn=Vn(Xn+1).计算6n(1)与vn的递推算法的具体设计如 设置初值81(1)=H1b1 用递推公式n+1()=bmax,(nO)an) 再定义vn+1(1)=j,其中广只要满足 n-(1)=b,5n()a (10.18) 最终采取如下的向后递推算法(相当于动态规划,动态规划的核心思想是:在一切最佳 路径上的任意节点出发,其后也应该是最佳路径,因此就能从后向前地逐步求得最佳路 得到如下的“最佳”轨道估计(X1,…,XN): 计算终值XN=1∈:8(=max,8xO)}, (10.19) 反向归纳地取xn=vn(xn+1) (10.20) 4学习问题-由观测Y=y估计模型参数λ 4.1状态链样本已知时的参数的频率估计 设隐 Markov模型的状态链有充分长的样本.把其中从状态i到下一个时刻为状态j转移的 频数记为A·那么,粗略地可取a=”为an的估计,同样设此观测链样本充分长记 ∑A 其中从状态到同一时刻的观测1转移的频数为B,则可取b=B-为b1的估计,不幸的 ∑Bn 是状态链是经过估计得到的,所以不修正地使用频率估计会增加误差.再则,这种估计也过于 敏感 4.2模型参数估计的EM算法的思想 我们取λ的最大似然估计λ,即它满足 P(=ylA)=max P(r=y|2) (10.21) 274
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)
