龚光鲁,钱敏平著应用随机过程教程一与在算法和智能计算中的应用 清华大学出版社,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）. 此例是一个玩具模型. 从这个例子可以看出，在观测出自哪个盒子已知时，状态随机变