隐马尔可夫模型的原理与实现.doc

隐马尔可夫模型的原理与实现国外医学生物医学工程分册2002年第25卷第6期隐马尔可夫模型的原理与实现?253?刘河生,高小榕,杨福生(清华大学电机工程与应用电子技术系,北京100084)摘要:隐马尔可夫模型正在被愈来愈多地引入到生物医学信号的处理中.本文旨在简述它的基本原理和实现中的问题,并且用简洁的列表形式总结它的算法步骤.关键词:隐马尔可夫模型;信号处理;实现算法中图分类号;R311;R318文献标识码:A文章编号;1001一l110(2002)06025307TheoryofhiddenMarkovmodelinganditsimplementationLIUHesheng,GAOXiaorong,YANGFusheng(DepartmentofElectricalEngineeringandAppliedElectronics,TsinghuaUniversity,Beijing100084,China)Abstract:HiddenMarkovModelisnowbeingappliedincreasinglyinbiomedicalsignalprocessing.Thepapermakesashortreviewonitstheoryandtheproblemsencounteredinitsimplementation.Tablesareusedtoclearlysummarizeitsalgorithmicprocedures.Keywords:hiddenMarkovmodel;signalprocessing;implementalgorithms随着隐马尔可夫模型在语言信号处理中的成功应用,它正被愈来愈多地引入到生物医学信号的处理中.本文旨在简述它的基本原理和实现中的问题,并且用简洁的列表形式总结它的算法步骤.隐马尔可夫模型是马尔可夫模型的进一步发展.马尔可夫模型是马尔可夫过程的模型化,可以用图1(a)的框图形象表示.它把一个总随机过程看成一系列状态的不断转移.时刻t的状态用q表示,它可以是种状态集合S一s,S,SN中的任意一个.马尔可夫模型的特性主要用”转移概率”来表示.后一状态出现的概率决定于其前出现过的状态次序.即:状态q,出现的概率为Pr/q,q,q.如果此概率只决定于前一个状态,即Pr/q,则称为一阶马尔可夫过程.它是研究中引用得最多的形式,即:Prq./q一,q一,q一尸,q/q,-a.隐马尔可夫模型(HiddenMarkovModel,HMM)则认为模型的状态是不可观测的(这便是“隐”得名的由来).能观测到的只是它表现出的一些观测量(observations).例如:睡眠的状态可分为图1(a)马尔可夫过程(b)隐马尔可夫过程隐马尔可夫过程的特性可用下述参数集合来表征:(1)转移概率aijPrsj/s即:由状态i转移到状态的概率(对一阶马尔可夫过程).由于共有种可能的状态,因此a共有x个可能的取值.把它们用矩阵表示成们r【r【=ll?254?1A:Ea且aij一1(2)观察概率bi(正)=PrEu(,即:在状态S下产生观察的概率.如果共有种可能的观察,则6(正)组成N矩阵B.N1日一Ebj(k)且2_5b()一1(3)初始状态概率:指第一个状态q究竟取SEs,S:,SN中哪一个的概率.它组成1N矢量丌:7f.:PrEq1=Si而TI-丌1,丌2,以下讨论中把上述参数合起来用表示:一A,日,丌.它便是表征HMM的参数集合.采用HMM进行研究工作时常遇到三类问题:(1)评价问题:给定模型参数2-EA,B,丌及观察序列O-Eo,O:,o.求此模型产生此观察序列的概率PrEO/).实际工作中常用这一思路来进行信号的分类.即:设有I种待定类别,其模型分别为,:,扎,且皆已知.现在把给定观察0-Eo,0:,o给予这组模型,看哪一个PrEO/2.最大就认为该观察属于一类.这也就是选择与观察最匹配的模型.(2)解码问题:给定模型及观察序列0;问此观察序列是模型中取怎样的状态次序g一g:一-qr得到的.解决此问题的关键是采用什么作为取得结论的判据.通常是取产生此观察序列概率最大的一组状态序列Q-Eq,q,q作为判决.(3)辩识(或称训练)问题:给定HMM的结构(指状态数N,观察类数),由给定的一组供训练用的观察组0,0:,O.j,估计该模型的最优参数.一A,雪,第三类问题是更基本的,因为前两类问题都建立在已知的基础上.但由于第三类问题算法比较复杂,因此以下讨论时把它放在前两类之后.2三类问题的基本解法2.1评价问题:给定HMM参数EA,B,丌,同时还给定一组观察O-Eo,O:,OT一,求此模型产生此观察序列的概率PrEO/2.需要着重指出的是:尽管0已给定,但产生此0国外医学生物医学工程分册2002年第25卷第6期的状态序列Q_-g,q:,gr却并不唯一,因为的每一个取值都能以一定概率产生给定的O例如,设Ot一,则产生此的概率分别是b(),b:(),b().也就是说任何一组状态序列qlqzqT都能依下述联合概率产生观察序列0=Eo,0:,0了,:丌目l6q1(01)日q1q2b(o2)日q2q3bq3(03)aqt-1qTbqr(0了,)(1)式中:是初始时处在q状态的概率;b(0)是在q状态下产生观察0的概率;日日:是由状态q转移到状态q:的概率.由于每一组状态序列都能产生一个这样的概率,而每一个状态q都有N种不同的可能取值.因此类似的路径共有条见图2.图中由q到q的每一条路径都是一个可能的状态序列.把这些路径的概率总和起来就得到我们要求的PrEO/2.即:图2状态转换展开图PrEO/23-b(.):b(o2)ql=lq2q一1aqT-1qTbq7,(0r,)简记作:Pr(Q,0/2)(2)上述概念并不复杂,只是计算量过大:(1)式包含(2T一1)次乘法,因此(2)式包含(2T一1)N2TN次乘法.为了实现Pr0/的计算,需要寻找更高效的算法.考虑到上述计算过程中实际作了许多重复计算,因此改进算法的基本思路是:步步为营的递推算法.其具体策略又可分成三类:(1)前向递推法:其基本思路可借助于图3来说明.令()代表给定模型参数下过程到t时刻为止产生部分给定观察序列o0f,且在t时刻状态为s.的部分概率,记作:此处O是大写字母,指状态序列ol,Oz,t;?所滑给定”D=Col,o2,卵”意即各O的取值已给定;例如国外医学生物医学工程分册2002年第25卷第6期at()=Pro1,02,Ot;qt一/求口f+1()=Pro1,02,0f,0f+1;qf+1一s/与at()的关系.由图3可见:N口()一()fJ6J(.)(3)adooIc2)a/U)图3由()推导at+()由此可得前向递推的步骤如表1所列.此法所需乘法次数约为NT,使(2)式的计算量大为下降.表1前向递推法1.初始化:t=1时的赋值()=7r6,(01)2.递推:():()6J(叭)即(3)式:由左向右逐级递推t1T1,一1N3.终止:止于t=TP(O/h)0:aT()Pr=厶()J1(2)后向递推法:此时改为由过程的后部分(例如十1,十2,丁)向前递推.其基本关系如图4所示.图4由+()推导()令()为在给定模型参数,且q一s.条件下产生观察Oto的部分概率.即:()一P,Eo,O件,0/q,-S,求+()一P,Eo件1,0件2,0/q,+一s,与间的关系.由图五可见:l2N?255?+!oJl:时刻时刻12N1tt8j1:时刻时刻t+2图5t时刻和f+1时刻状态与的关系N_,()一厶口.6J(0件1)+1()(4)=1一1N,tT一1,T一2,1从而得到后向递推过程如表2所示.初始化令()一1是任意给定的.表2后向递推法1.初始化t=T时的赋值()一1,i=12.递推:():(叭)+()即(4)式:由右Jl向左逐级递推一1N;tT一1,丁一2,2,13.终止:止于t=1Pr(O/)=()(3)前后向递推法:也就是把前向递推与后向递推结合起来,Of用前向递推,丁f用后向递推(t值可在1丁间任意选定).此时有:NP(O/)一厶qt()()(5)=12.2解码问题此时的任务是对给定的模型参数EA,B,7r和给定的观察序列OEo,O:,o,求此观察序列最可能由怎样的状态序列QEq,q:,q产生.通常认为最可能产生它的状态序列就是按(1)式计算得概率值最大的一个序列.原理上说,解决此任务的概念也很简单:按图2和(1)式把每条可能路径的概率都求出来,然后取所得概率最大的一条路径便是所求.这种”穷举法”的问题仍然是计算量过大.解决之道仍然是步步为营的递推算法.显然,定义:?256?一一1然后取(f)最大的一个便是所求答案.不过实际更常采用的是逐步搜索前进的Viterbi算法.Viterbi算法的核心是下述递推关系:如果已经确定了对给定部分观察序列0,0”,0时的最优状态序列q,q.,q,如何找到当部分观察序列增1时也就是0,0”,0,Ot+1的最优状态序列q,q,q,qH1.定义辅助变量如下:()一.,P,Eq1,q”,qts/01,0”,0,它的含义是:对给定的模型参数和部分观察序列0o,满足q,处在S状态下使概率最大的状态序列q,q”,q川.称此概率为(),现在以()为出发点来求+()一.PrEq,qz,qt-1,qt-1,qt,qf+1一sJ/01,0f,0+1,不难理解+()一jEs,(i)a)6(o,+)(7)前一因子的含义是在qts”,SN中取()n最大的一个节点;后一因子则是S产生0川的概率,它与qts的选择无关.但值得强调的是:随着()中q一s的不同选择,相应的q一,qt-1最优路径也将随之而变.据此便得出()中递推过程如表3所示.这时的相应路径才是最后判断得的最优路径国外医学生物医学工程分册2002年第25卷第6期Q.一g,g,g.为了方便地获得此最优状态序列,需要在递推的每一步把对应于每个()(一1)的”获胜状态”记录下来,以便到最后再通过回推得出各gf.因此,按表3,最后除得到g外还会得到一个二维矩阵W()(f一1,一1N).根据w就可以逐步反推,由g找到gl:.,从而把最优状态序列确定下来.2.3参数辩识问题此时是用一组观察序列为训练集来优化HMM的参数A,B,丌,使PrOl2达到最大.因此要采用一种优化调节步骤.优化算法不止一种,下面介绍的是BaumWelch算法(也称前,后向算法),它是一种基于期望调节-expectationmodification-概念的算法.为了说明算法,需要引入另一个辅助变量(,).它表示在给定HMM参数和观察序列.下,t时刻处于S状态,而f+1时刻处于S,状态的概率:e,j)=PrEq一si,q一sJ,ol其表示式可以借助图5来考虑.图上突出地画出t时刻的状态S和f+1时刻的状态S两个节点.对于ff+1时段以外的部分,左边(即:时刻<f)用()来统一描述,右边(即时刻>f+1)用+()来统一描述.不难看出:(,)=PrEq一s1,q件1一s/o,PrEq一s,q川一s,o/一由图6可得:“,)=()(0f+】)+()(8)()ab(0川)+()l=1j=l上节提出的y()与此处的(,)存在下述简单关系:()一(,)j=1(9)更进一步,如果把()对所有t(f一1一1)求和,它代表着各种可能取的状态序列中S.被访问的次数,它也就是由S转移出去的次数时刻丁不被考虑,因为它不再转移出去,类似地,把(,)对t一1丁一1求和代表Sis这种转移出现的次数,即:r,一l()一从S转移出去的期望次数?258?参数递推更新时的算法.由(8)式可见b,(o)决定于._,c三项因素,因此更新b,(o)也就是更新这三项因素.文8,9证明了它们的更新公式如表4所列.这些公式从概念上也不难理解.(,k)表示在t时刻用第k个高斯分量表征O时系统处在状态j=下的概率,因此表中(ii)式反映此概率在全时间过程中所占百分数.(iii)式是对(ii)式分子乘以观察值O作为权重,因此它反映系统处在状态下用第k个高斯分量表征O时O的均值.表4连续变量时的参数更新一般言之,连续观察HMM比离散观察所需训练样本数也更多.3.3递推辨识模型参数一A,B,丌时初始值的设定前已指出,前,后向算法收敛后得到的y只是局部的极大似然解.因此如何选择参数的初始值以便使此局部极大就是全局极大是一个值得研究的问题.应该说,目前还没有解决此问题的有理论根据的方法.经验证明,在给定的已知约束条件下(例如某些一O)随机或均匀地选择初始丌和A值是个可行办法.但的初始值选择则影响较大,特别是在观察是连续变量的情况下.解决此问题只能根据具体情况来决定.本文从略.3.4尺度问题(scaling)由(1)(4)式都可看出,a,的计算都涉及多国外医学生物医学工程分册2002年第25卷第6期个概率的乘积.由于概率值必定小于1,所以当状态数目较多时此乘积将愈变愈小,甚至可能低于计算机数据容许动态范围的下限,使计算无从进行.解决此困难的途径有二:一是在计算过程的适当时刻t引入一些与状态i无关的归一化运算.待到计算终了再行复原.但更方便的方法是改用对数将乘法运算改成加法运算.由于对数函数是单调函数,因此这样作不会影响最后结果.例如,可以将表3的Viterbi算法改成对数形式如表5.表5对数形式的Viterbi算法4结束语以上对HMM作了初步但基础性的介绍.目前,HMM不但在许多科技领域得到了广泛应用,而且在其基本框架上也有许多发展.其中与生物医学信号处理关系较密切的有以下方面.(1)灵活的模型结构变种:根据具体任务,从图6基础上发展出多种新的模型例如:是所谓”嵌入式HMM”(EmbeddedHMM)的结构图Do,11.其特点是由两级状态组成,即:超级状态及内置状态.超级状态共有三级,而每一超级状态中又包含一组由内置状态组成的HMM.系统的状态可在各超级状态间转移,且在每一超级状态下实际上是在该状态包含的内含状态间转移.各超级状态的内含状态却不能直接转移.这种结构特别适用于具有二维结构的信息分析(如图像分析等).又如是文ElZ提出的计算生物学中用于蛋白质建模和符号序列分析的HMM.每一位置包括三种状态,矩形块为匹配状态,菱形块为插入状态,园形块为删除状态,各联线之间各有一个转移概率互相联系.其具体解释可参看文13.(2)与其他方法的结合:生物医学信号处理的发展趋势是,不能企图只靠单一方法完全解决问题,需要把多种方法分层次地结合起来,让不同方法在不同层次上发挥其优势.文13介绍一种将人工神经网络与HMM相结合的处理方法,文14则介绍一国外医学生物医学工程分册2002年第25卷第6期种把独立分量分析(IcA)与HMM相结合的分析方法.总之,HMM是一种灵活性比较强,适用性较广的随机模型.研究者在其中大有游刃余地.在信号及图像处理中很有应用前景.参考文献:1RabinerLR.AtutorialonhiddenMarkovmodelsandselectedapplicationsinspeechrecognitionJ.ProcIEEE,1989,77(2):257286.r2RabinerLR.AnintroductiontohiddenMarkovmodelsJ.IEEEASSPMagazine,1986,3(1):4-16.r3CohenA.HiddenMarkovmodelsinbiomedicalsignalprocessingrC.Proc20InternationalConferenceEMBS/IEEE,Hongkong,1998.4BurratC,HugheyR.KarplusK.ScoringhiddenMarkovmodelsJ.ComputerApplicationinBioscience,1997,13:191199.5DellerJR,HsuD,FerrierLJ.EncouragingresultsintheautomatedrecognitionofcerebralpalsyspeechrJ.IEEETransBME,1988,BME一55;218-220.6DellerJR,HsuD,FerrierLJ.OntheuseofhiddenMarkovmodellingforrecognitionofDysarthricspeechJ.CompMethodsandProgramsinBiomed,1991,35:】25139.?259?7CoastDA,StemRM,CanoGG,eta1.AnapproachtocardiacarrhythmiaanalysisusinghiddenMarkovmodelsl-J.IEEETransBME,1990,BME一17(9):826835.891OliporaceLA.MaximumlikelihoodestimationformultirateobservationofMarkovsourcesrJ.1986,IT一32(2):307309.JuangBH,LevinsonSV,SondhiMM.MaximumlikelihoodestimationformultivartiatemixtureobservationsofMarkovchainsJ.IEEETransonInformationTheory,1986,IT一32(2):307309.KuoS,AgazziE.Keywordspottinginpoorlyprinteddocumentsusingpseudo2-DMarkovmodelJ.IEEETransonPatternAnalysisandMachineIntelligence,1994,PAMI一16(8):842848.r11NefianAV,HayesMH.AnembeddedHMMbasedapproachforfacedetectionandrecognitionC.ProcIEEEInternationalConferenceonASSP,1999,35533556.i12lKroghA,BrownM,MianIS,eta1.HiddenMarkovmodelsincomputationbiology:Applicationtoproteinmodelingi,J.JMolBiol,1994,235:15011531.13TrentinE,CoriM.AsurveyofhybridANN/HMMmodelsforautomaticspeechrecognitionIJ.NeuralComputing,2001,37:91126.14XuLei.TemporalBYYlearningforstatespaceapproach,HiddenMarkovmodelandblindsourceseparationFJ.IEEETransonSignalProcessing,2000,SP一48(7):21322144.肝脏组织工程学中的胚胎干细胞胡安斌,郑启昌(华中科技大学同济医学院协和医院普外科,湖北武汉430030)摘要:肝脏组织工程是新近兴起的一门学科,其目的是经过培养形成有独立代谢功能的肝脏器官.其中,种子细胞来源是关键,胚胎干细胞由于不存在来源短缺及异种排斥问题,是理想的选择,现在许多学者进行了由胚胎干细胞向肝细胞的转化研究,并与人工材料,基因调控等技术结合