第二章 隐马尔科夫模型

第二章隐马尔科夫模型2.1引言隐马尔科夫模型（HiddenMarkovModel，HMM）又称隐马氏模型，它的基本理论是20世纪60年代末、70年代初由Baum等人创建的。HMM是在Markov链的基础上发展起来的，由于实际问题比Markov链模型所描述的更为复杂，观察到的事件并不是与状态一一对应的，而是通过一组概率分布相联系，这样的模型被称为HMM。它是一个双重随机过程，其中一个描述的是状态之间的转移；另一个描述的是状态和观察符号之间的统计对应关系。观察符号与状态之间并没有一一对应的关系，因此，只能通过观察符号感知到状态的性质及其特性。HMM模型作为一种统计模型，已经成功地实现了对语音识别(LawrenceR.Rabiner,1989)、生物序列分析(R.Durbinetal.,1998)、自然语言处理（。。。）等复杂问题的建模，并且在生物序列分析的各个领域都获得了广泛应用，比如：序列比对（包括双序列比对及多序列比对），基因发现，系统进化树的构建等等。2.2HMM的基本概念为了对HMM模型有一个直观的认识，让我们首先看一个经典的例子：球和缸的实验，如图2-1所示。图2-1.球和缸的实验设有N个缸、M种不同颜色的球，每个缸中都装有很多彩色的球，球的颜色是由一组概率分布描述的。实验是这样进行的：首先根据某种随机过程选择N个缸中的一个，记为z1，再根据这个缸中球颜色的概率分布，有放回地随机选择一个球，记此球的颜色为o1；然后根据缸的转移概率分布，随机选择下一个缸，记为z2，再根据这个缸中球的颜色的概率分布，有放回地随机选择一个球，记此球的颜色为o2。这样一直进行下去，假设进行了T次，可以得到一个描述球的颜色的序列12,,,TOooo，由于这是观察到的事件，因而被称为观察序列。同时还有一个描述缸选取次序的序列12,,,TZzzz，被称为状态序列，但缸的选取是在幕后进行的，对我们来说是不可见的（隐的）。注意到从每个缸中选取的球的颜色并不是与缸一一对应的，而是由该缸中球的颜色的概率分布决定的，此外，每次选取哪个缸则是由一组转移概率决定的。这就是一个典型的HMM模型，下面给出HMM模型的正式定义：定义2-1(一阶HMM模型)一阶HMM模型由以下元素组成：（1）N：状态数目，设状态集合为12,,,NSsss，记t时刻所处的状态为iz，izS；（2）M：观察符号数目，设观察符号集合为12,,,MEeee，记t时刻观察到的符号为to，toE；（3）111212122212,,,,,,,,,NNNNNNssssssssssssssssssaaaaaaaaaA：状态转移矩阵，其中,ijssa（简记为,ija）表示从状态is转移到状态js的概率；（4）111212122212,,,,,,,,,MMNNNMsesesesesesesesesebbbbbbbbbB：观察符号概率矩阵，其中,ijseb（简记为,ijb）表示当处于状态is时观察到符号je的概率；（5）12,,,Nssspppp：初始状态概率矢量，其中isp（简记为ip）表示初始选取的状态为is的概率；（6）12,,,Nsssqqqq：结束状态概率矢量，其中isq（简记为iq）表示随机过程结束于状态is的概率。并且满足以下各个条件：（1）随机性，即,,111,,1,,,0,1NMNiijijijjiijijiiqabpabpq；（2-1）（2）一阶性，即1111,,,,,tttttPzzzzPzz，（2-2）11,,,,,tttttPozzzPoz；（2-3）（3）稳定性，即,1,:,ijtjtiijtjtitaPzszsbPoezs；（2-4）（4）观察符号独立性，即12121,,,,,,,TTTtttPooozzzPoz。（2-5）这样，一个HMM就可以记为,,,,,NMABpq，或者简记为,,,ABpq。为建模随机过程的开始及结束，我们分别引入一个开始及一个结束状态，并且为方便起见，均记作0s。注意，这样并不会引起任何冲突，因为随机过程只能从开始状态转出，而且也只能转入结束状态。这样，从状态0s转移到状态is的概率0,issa（简记为0,ia）可以被认为初始选取的状态为is的概率，即0,iiap；从状态is转移到状态0s的概率0,issa（简记为,0ia）可以被认为结束于状态is的概率，即,0iiaq。应该注意到，每当我们考虑状态序列12,,,TZzzz时，就隐式地意味着考虑0120,,,,,TZszzzs。2.3HMM要解决的三个基本问题在采用HMM来完成实际的各项课题研究时，需要解决以下三个基本问题：2.3.1输出概率的计算问题给定HMM模型,,,ABpq和观察序列12,,,TOooo，如何有效地计算观察序列O对HMM模型的输出概率PO？由此，可以对已知的n个HMM模型：12,,n，分别计算iPO，1,2,,in，然后按输出概率最大的原则，将12,,,TOooo归为使iPO最大的那个模型，可用于分类。定理2-1给定HMM模型,,,ABpq和观察序列12,,,TOooo，则观察序列O对HMM模型的输出概率PO为111111121,,,,,,1ttttTTTzzozzzozzzztPOpbabq。（2-6）证明利用全概率公式，得,,ZZPOPOZPOZPZ。（2-7）对12,,,TZzzz，因为110110,,,,,,,,TTTTPZPzzzPszzzs011110100,,,,,,,,,TTTTPszzzPzzzsPzsPs01122110,,,,,TTTTTPszPzzPzzPzzPzs111111,11,TttTTTzttzzzzzttpPzzqpaq，（2-8）并且考虑到,11,,ttTTttzottPOZPozb，（2-9）将式（2-8）~（2-9）代入式（2-7），并稍加整理，即可得式（2-6）。通过枚举所有的状态序列，如果利用式（2-6）直接计算输出概率PO，那么时间复杂度为TTNO。具体来说，需要2TTN次乘法运算，以及1TN次加法运算，显然是不现实的。通常的解决办法是采用前向或后向算法，下面将分别对这两个算法做一下简单介绍。定义2-2（前向变量）给定HMM模型,,,ABpq，定义前向变量ti为HMM模型在t时刻，位于状态is时观察到部分序列12,,,tooo的概率，即12,,,,tttiiPooozs，1,2,,iN，1,2,,tT。（2-10）性质2-1（前向递推公式）1,,1tNttijjoijiab。（2-11）算法2-1（前向算法）Step1初始化：11,iioipb，1,2,,iN；Step2递推计算：1,,1tNttijjoijiab，1,2,,iN，2,,tT；Step3终止计算：1NTiiPOiq。此算法采用了动态规划（DP—DynamicProgramming）的思想，有效地将计算输出概率PO的时间复杂度降为2NTO，具体来说，需要N(N+1)(T1)+N次乘法运算，以及N(N1)(T1)次加法运算。定义2-3（后向变量）给定HMM模型,,,ABpq，定义后向变量ti为在t时刻，位于状态is时观察到部分序列12,,,ttTooo的概率，即12,,,,tttTtiiPooozs，1,2,,iN，1,2,,tT。（2-12）性质2-2（后向递推公式）11,,1tNttijjojijab。（2-13）算法2-2（后向算法）Step1初始化：Tiiq，1,2,,iN；Step2递推计算：11,,1tNttijjojijab，1,2,,iN，1,,1tT；Step3终止计算：11,1NiioiPOipb。类似地，此算法也采用了动态规划的思想，时间复杂度为2NTO，具体来说，需要2N2(T1)次乘法运算，以及N(N1)(T1)次加法运算。2.3.2状态序列的解码问题给定HMM模型,,,ABpq和观察序列12,,,TOooo，如何确定一个状态序列12ˆˆˆˆ,,,TZzzz，使得ˆZ最有可能产生观察序列O？该问题也称为解码或译码问题，目的就是要尽可能揭露出模型中与已知的观察序列相对应的状态序列，即确定“最优”的状态序列。最优准则一般有两个：单点状态最优准则和路径最优准则，本文采用路径最优准则。此时就是求解使得概率,PZO最大时所确定的状态序列，即{}{}{},ˆargmax,argmaxargmax,ZZZPZOZPZOPZOPO。（2-14）利用著名的Viterbi算法不仅可以找到满足这一准则的状态序列（路径），而且还可以得到该路径所对应的输出概率。定义2-4（Viterbi变量）给定HMM模型,,,ABpq，设观察序列12,,,TOooo已知，定义Viterbi变量ti为在t时刻，观察到序列前缀12,,,tooo，且tizs的最优状态序列为12,,,tzzz的概率，即12112112,,,max,,,,,,,,ttttitzzziPzzzzsooo，1,2,,iN，1,2,,tT。（2-15）性质2-3（Viterbi递推公式）1,,1,2,,maxtttijjoiNjiab。（2-16）算法2-3（Viterbi算法）Step1初始化：1.111,iioipb，1,2,,iN；1.210i；1,2,,iN；Step2递推计算：2.11,,1,2,,maxtttijjoiNjiab，1,2,,jN，2,,tT；2.21,1,2,,argmaxttijiNjia，1,2,,jN，2,,tT；Step3终止计算：3.1*1,2,,maxTiiNPiq；3.2*1,2,,argmaxTTiiNziq；Step4回溯最优路径：**11tttzz，1,,1tT。不难看出，除多了一步回溯最优路径外，此算法与前向算法非常类似。此算法的时间复杂度也为2NTO，具体来说，需要N(N+1)(T1)+N次乘法运算，N(N1)(T1)次比较运算。2.3.3模型参数的估计问题给定K条相互独立的观察序列12,,,KOOO，其中，12,,,kkkkkTOooo，kT表示kO的长度，模型参数的估计问题是指在模型参数未知或不准确的情况下，如何根据这些观察序列求得或调整模型参数，使得121,,,KKkkPOOOPO最大，即使得11maxKKkkkkPOPO，其中，为HMM模型的参数空间？由HMM的定义可知，HMM本身就是用参数刻画的。所谓模型参数估计就是在一定的已知条件下，利用某种算法选择和优化模型的参数A，B，p及q。这是HMM要解决的三个基本问题中最难的，目前尚没有能够使得1KkkPO全局最大的算法。求解HMM模型的最优参