机器学习9隐马尔科夫模型版

1、隐马尔科夫模型Hidden Markov Model(HMM)王成（副教授）计算机科学与技术学院提 纲隐马尔科夫模型的三个问题应用领域14概率计算问题路径预测问题3参数学习问题一阶马尔可夫模型（Markov Models）隐马尔科夫模型Hidden Markov Model2数学类：概率论、组合数学、矩阵论计算机类：数据结构、算法导论、MATLAB、Mathematica、C/C+等编程技术问题背景：基因遗传学、遗传病学、生态学、人口学与马尔可夫模型(Markov Models)相关的课程1马尔可夫模型马尔可夫模型是数学中具有马尔可夫性质的离散时间随机过程，是用于描述随机过程统计特征的概率模型

2、。S2S3S1SNS1t=1t=2t=3t=T-1t=TS1S2S3SNS1S2S3SNS1S2S3SNS1S2S3SNS1S2S3SNS1S2S3SN系统状态数目(N个)S2S3S1S1SN一条马尔可夫链状态序列=观测序列马氏链模型 系统在每个时期所处的状态是随机的 从一时期到下时期的状态按一定概率转移 下时期状态只取决于本时期状态和转移概率 已知现在，将来与过去无关（无后效性）描述一类重要的随机动态系统（过程）的模型马氏链 (Markov Chain)时间、状态均为离散的随机转移过程t=1t=2t=3t=4t=5S1S2S3S1S2S3系统状态数目(N=3)一阶马尔可夫模型（Markov

3、Models）S1S2S3S1S2S3S1S2S3S1S2S3a11a12a13a22a21a23a31a33a32a11a12a22a21a23a33a32a11a12a22a21a23a33a32a11a12a22a21a23a33a32下时期状态只取决于当前时期状态和转移概率从某时刻状态到下时刻的状态按一定概率转移t-1时刻t时刻qt-1qtqt-1qtq1q2q3t-1时刻t 时刻晴阴雨T=1T=2T=3一阶马尔科夫模型设有n个状态，其中第i个状态记作wi。在任意时刻t的状态记作w(t)。一个长度为T的状态序列记作wT=w(1),w(2),w(T)。例如有一个状态序列可能是：w6=w1

4、,w4,w2,w2,w1,w4。从状态t迁移到状态t+1的概率：P(wj(t+1)|wi(t)记作aij。比如：马氏链模型 系统在每个时期所处的状态是随机的 从一时期到下时期的状态按一定概率转移 下时期状态只取决于本时期状态和转移概率 已知现在，将来与过去无关（无后效性）描述一类重要的随机动态系统（过程）的模型马氏链 (Markov Chain)时间、状态均为离散的随机转移过程通过有实际背景的例子介绍马氏链的基本概念和性质例1. 人的健康状况分为健康和疾病两种状态，设对特定年龄段的人，今年健康、明年保持健康状态的概率为0.8, 而今年患病、明年转为健康状态的概率为0.7，1. 健康与疾病 人的

5、健康状态随着时间的推移会随机地发生转变 保险公司要对投保人未来的健康状态作出估计, 以制订保险金和理赔金的数额 若某人投保时健康, 问10年后他仍处于健康状态的概率Xn+1只取决于Xn和pij, 与Xn-1, 无关状态与状态转移状态转移具有无后效性 120.80.20.30.7 n 0a2(n) 0 a1(n) 1设投保时健康给定a(0), 预测 a(n), n=1,2设投保时疾病a2(n) 1 a1(n) 0 n时状态概率趋于稳定值，稳定值与初始状态无关3 0.778 0.222 7/9 2/9 0.7 0.77 0.777 0.3 0.23 0.223 7/9 2/9 状态与状态转移120

6、.80.20.30.710.80.220.780.221230.10.0210.80.250.180.65例2. 健康和疾病状态同上，Xn=1 健康, Xn=2 疾病p11=0.8, p12=0.18, p13=0.02 死亡为第3种状态，记Xn=3健康与疾病 p21=0.65, p22=0.25, p23=0.1 p31=0, p32=0, p33=1 n 0 1 2 3 a2(n) 0 0.18 0.189 0.1835 a3(n) 0 0.02 0.054 0.0880 a1(n) 1 0.8 0.757 0.7285 设投保时处于健康状态，预测 a(n), n=1,2 不论初始状态如何

7、，最终都要转到状态3 ； 一旦a1(k)= a2(k)=0, a3(k)=1, 则对于nk, a1(n)=0， a2(n)=0, a3(n)=1, 即从状态3不会转移到其它状态。状态与状态转移00150 0.1293 0.0326 0.8381 马氏链的基本方程基本方程马氏链的两个重要类型 1. 正则链 从任一状态出发经有限次转移能以正概率到达另外任一状态（如例1）。w 稳态概率马氏链的两个重要类型 2. 吸收链 存在吸收状态（一旦到达就不会离开的状态i, pii=1）,且从任一非吸收状态出发经有限次转移能以正概率到达吸收状态（如例2）。有r个吸收状态的吸收链的转移概率阵标准形式R有非零元素y

8、i 从第 i 个非吸收状态出发，被某个吸收状态吸收前的平均转移次数。2. 基因遗传背景 生物的外部表征由内部相应的基因决定。 基因分优势基因d 和劣势基因r 两种。 每种外部表征由两个基因决定，每个基因可以是d, r 中的任一个。形成3种基因类型：dd 优种D, dr 混种H, rr 劣种R。 基因类型为优种和混种, 外部表征呈优势；基因类型为劣种, 外部表征呈劣势。生物繁殖时后代随机地（等概率地）继承父、母的各一个基因，形成它的两个基因。父母的基因类型决定后代基因类型的概率完全优势基因遗传父母基因类型决定后代各种基因类型的概率父母基因类型组合后代各种基因类型 的概率DDRRDHDRHHHRD

9、RH1000011 / 21 / 200101 / 41 / 21 / 401 / 21 / 23种基因类型：dd优种D, dr混种H, rr劣种R完全优势基因遗传P(DDH)=P(dddd,dr)=P(ddd)P(ddr)P(RHH)=P(rrdr,dr)=P(rdr)P(rdr)=11/2=1/2=1/21/2=1/4随机繁殖 设群体中雄性、雌性的比例相等，基因类型的分布相同（记作D:H:R） 每一雄性个体以D:H:R的概率与一雌性个体交配，其后代随机地继承它们的各一个基因 设初始一代基因类型比例D:H:R =a:2b:c （a+2b+c=1), 记p=a+b, q=b+c, 则群体中优势

10、基因和劣势基因比例 d:r=p:q (p+q=1)。假设建模状态Xn=1,2,3 第n代的一个体属于D, H, R状态概率 ai(n) 第n代的一个体属于状态i(=1,2,3)的概率。讨论基因类型的演变情况基因比例 d:r=p:q转移概率矩阵状态转移概率随机繁殖马氏链模型自然界中通常p=q=1/2稳态分布D:H:R=1/4:1/2:1/4基因类型为D和H, 优势表征绿色，基因类型为R, 劣势表征黄色。解释“豆科植物的茎，绿色:黄色=3:1”(D+H):R=3:1随机繁殖近亲繁殖在一对父母的大量后代中, 雄雌随机配对繁殖，讨论一系列后代的基因类型的演变过程。状态定义为配对的基因类型组合Xn=1,

11、2,3,4,5,6配对基因组合为DD,RR,DH,DR,HH,HR状态转移概率马氏链模型I0RQ状态1(DD), 2(RR)是吸收态，马氏链是吸收链不论初始如何，经若干代近亲繁殖，将全变为优种或劣种.计算从任一非吸收态出发，平均经过几代被吸收态吸收。纯种(优种和劣种)的某些品质不如混种，近亲繁殖下大约56代就需重新选种.近亲繁殖提 纲隐马尔科夫模型的三个问题应用领域14概率计算问题路径预测问题3参数学习问题隐马尔科夫模型Hidden Markov Model一阶马尔可夫模型（Markov Models）2引例假设你有一个住得很远的朋友，他每天跟你打电话告诉你他那天作了什么。你的朋友仅仅对三种活

12、动感兴趣:公园散步，购物以及清理房间。他选择做什么事情只凭天气。你对于他所住的地方的天气情况并不了解。在他告诉你每天所做的事情基础上，你想要猜测他所在地的天气情况。 你认为天气的运行就像一个马尔可夫链。其有两个状态雨和晴，但是你无法直接观察它们，也就是说，它们对于你是隐藏的。每天你的朋友有一定的机率进行下列活动：散步，购物，或清理。因为你朋友告诉你他的活动，所以这些活动就是你的观察数据。这整个系统就是一个隐马尔可夫模型HMM。 引例states = (Rainy, Sunny)observations = (walk, shop, clean)天气变化概率= Rainy : Rainy: 0.

13、7, Sunny: 0.3, Sunny : Rainy: 0.4, Sunny: 0.6, 不同天气下进行各种活动的概率= Rainy : walk: 0.1, shop: 0.4, clean: 0.5, Sunny : walk: 0.6, shop: 0.3, clean: 0.1, 引例隐马尔可夫模型简介X1X2XTO1O2OT假设对于一个随机事件，有一个观察值序列：O1,.,OT该事件隐含着一个状态序列：X1,.,XT假设1：马尔可夫假设（状态构成一阶马尔可夫链） p(Xi|Xi-1X1) = p(Xi|Xi-1)假设2：不动性假设（状态与具体时间无关） p(Xi+1|Xi) =

14、p(Xj+1|Xj)，对任意i,j成立假设3：输出独立性假设（输出仅与当前状态有关） p(O1,.,OT | X1,.,XT) = p(Ot | Xt) 定义一个隐马尔可夫模型 (HMM) 是一个五元组： (X , O, A, B, )其中： X = q1,.qN：状态的有限集合 O = v1,.,vM：观察值的有限集合 A = aij，aij = p(Xt+1 = qj |Xt = qi)：转移概率 B = bik，bik = p(Ot = vk | Xt = qi)：输出概率 = i， i = p(X1 = qi)：初始状态分布3. 隐马尔可夫模型t=1t=2t=3t=T-1t=TS1S2

15、S3SNS1S2S3SNS1S2S3SNS1S2S3SNS1S2S3SNS1S2S3SN隐藏状态S2S3S1S1SNt=1t=2t=3t=T-1t=T观测状态Q1Q2QMQ1Q2QMQ1Q2QMQ1Q2QMQ1Q2QMQ1Q2隐藏状态序列观察状态序列Q1QMQ2QMHMM状态序列观测序列Q1QM一般随机过程马儿科夫过程t=1t=2t=3t=4t=5S1S2S3一阶隐马尔可夫模型（Hidden Markov Models）图解S1S2S3S1S2S3S1S2S3S1S2S3a11a12a13a22a21a23a31a33a32a11a12a22a21a23a33a32a11a12a22a21a2

16、3a33a32a11a12a22a21a23a33a32下时期状态只取决于当前时期状态和转移概率从某时刻状态到下时刻的状态按一定概率转移t-1时刻t时刻qt-1qt4. 隐马尔可夫模型(Hidden Markov Models,HMM)Q3Q4Q1Q1O2I-隐藏状态转移概率生成概率b2(Q3)b3(Q4)b1(Q1)b1(Q1)b2(Q2)II-观察序列S2S3S1S1S2qt-1qtq1q2q3t-1时刻t 时刻T=1T=2T=3t=1t=2t=3t=T-1t=TS1S2S3S1S2SNS1S2SNS1S2SNS1S2SNO1O2O3OT-1S2SNS1S1S25. 隐马尔可夫模型(Hid

17、den Markov Models,HMM)HMM模型五元组表示： （ N, M, , A, B）用来描述HMM，或简写为 =( , A, B)一阶隐马尔可夫模型（Hidden Markov Models）数学定义 OTA转移概率矩阵OMOMOMOMOMB生成概率矩阵NM一阶隐马尔科夫模型在任意时间t，系统在状态是w(t)时，发出可见信号v(t)。设有n个可见状态，其中第i个状态记作vi。定义一个可见的状态序列记作：vT=v(1),v(2),v(T)。例如有一个可见状态序列可能是：v6=v5,v1,v3,v4,v1,v4。一个状态可能产生多个可见状态，设在状态wj(t)的时候发出可见状态vk(

18、t)的概率是：P(vk(t)|wj(t)记作bjk。比如：可以看到对于隐马尔科夫模型，有两个特性：提 纲隐马尔科夫模型Hidden Markov Model应用领域14概率计算问题路径预测问题3参数学习问题隐马尔科夫模型的三个问题一阶马尔可夫模型（Markov Models）2问题令 = A,B, 为给定HMM的参数，令 = O1,.,OT 为观察值序列，隐马尔可夫模型（HMM）的三个基本问题： 评估问题：对于给定模型，求某个观察值序列的概率p(|) ；解码问题：对于给定模型和观察值序列，求可能性最大的状态序列；学习问题：对于给定的一个观察值序列，调整参数，使得观察值出现的概率p(|)最大。算

19、法评估问题：向前算法定义向前变量采用动态规划算法，复杂度O(N2T)解码问题：韦特比（Viterbi）算法采用动态规划算法，复杂度O(N2T)学习问题：向前向后算法EM算法的一个特例，带隐变量的最大似然估计算法：向前算法（一）定义前向变量为HMM在时间t输出序列O1Ot，并且位于状态Si的概率：算法：向前算法（二）迭代公式为：结果为：变化连续输出模型输出矩阵变为某种概率分布，如高斯分布多阶转移矩阵3.1概率计算问题(1)概率计算问题：已知一个HMM的aij，bjk。根据一个可见状态序列VT，求解它是由这个HMM产生的概率。例如：你建立了一个马尔科夫模型，你朋友告诉你连续5天他的活动是：购物、清

20、理、清理、散步、购物，求解它是由这个HMM产生的概率。注：其它模型包括：修改这个模型参数；修改这个模型结构；由周六周日作为隐含状态等等。已知一个HMM的aij，bjk。根据一个可见状态序列VT，求解它是由这个HMM产生的概率。 这个模型产生一个可见状态序列VT的概率是：设有rmax个可能的隐含状态序列，r表示其中第r个序列。求和符号里面的含义是，对于第r个隐含状态序列，这个隐含状态序列T产生的概率*这个隐含状态序列T发出可见状态VT的概率。 3.1概率计算问题其中： 因此：3.1概率计算问题这样需要计算的次数很多，有的算法可以很大程度上提高计算速度。估值问题的一个应用是：在语音识别里，根据语音

21、识别到底是那个单词？比如有两个HMM：cat，dog。看哪个模型产生这个语音的概率大。 3.1概率计算问题t=1t=2t=3t=T-1t=TS1S2S3S1S2SNS1S2SNzS1S2SNS1S2SNa11a12a13a22a21a23aN1aNNaN2a11a12a22a21a23a33a32a11a12a22a21a23a33a32O1O2O3OT-1OTA转移概率矩阵B生成概率矩阵问题1：给定观察序列O=O1,O2, ,OT,以及模型=(,A,B),计算P(O|)？a01a02a0N：初始概率向量1. 隐马尔可夫模型-全概率计算S2问题本质：计算产生观测序列O的所有可能的状态序列对应的

22、概率之和共 N T 个可能路径（指数级计算）N=5, T=100, = 计算量1072t=1t=2t=3S1S2S1S2S1S2BES4S4S4S5S5S5S3S3S3t=4S1S2S4S5S3a01a02a03a04a05aT1aT2aT3aT4aT5O1O2O3O4前向算法后向算法问题1：给定观察序列O=O1,O2, ,OT,以及模型=(,A,B),如何计算P(O|)？SkSkS1SNOtS1SNSkS1SN0t-1OT tT0SkS1SN1O1初始化阶段(t = 1)中间递归阶段（t = 2,T）结束阶段2. 概率计算问题：前向算法（Forward Algorithm）前进Ot-1前进N

23、=5, T=100, = 计算量3000SkOt+1S1SNSkS1SN0OT tT0SkS1SN1O1.问题1：给定观察序列O=O1,O2, ,OT,以及模型=(,A,B),如何计算P(O|)？3. 概率计算问题：后向算法（Forward Algorithm）OtSkS1SNt+1.后退后退初始化阶段(t = T)中间递归阶段（t = T-1, 2,1）结束阶段(2) 路径预测问题：已知一个HMM的aij，bjk。根据一个可见状态序列VT，求解最可能的隐藏状态序列。例如：你朋友告诉你连续5天他的活动是：购物、清理、清理、散步、购物。你猜测这5天最可能的天气。3.2路径预测问题3.2路径预测问

24、题已知一个HMM的aij，bjk。根据一个可见状态序列VT，求解最可能的隐藏状态序列。一个简单方法是，列出这个HMM所有可能的隐含状态序列T，每个隐含状态序列产生VT的概率是： 具有最大概率的隐含状态序列T就是要求的结果。可以看到这个速度更慢。同样也有算法可以在很大程度上提高计算速度。 1.隐马尔可夫模型-路径预测问题2：给定观察序列O=O1,O2, ,OT,以及模型,如何推测最可能的状态序列S ? t=1t=2t=3t=T-1t=TS1S2SNS1S2SNS1S2SNzS1S2SNS1S2SNaN1A转移概率矩阵B生成概率矩阵a01a02a0N：初始概率向量S2问题本质：计算产生观测序列O的

25、最可能的一条隐藏状态序列QO1O2O3OT-1OT已知观察序列？解决方法：Viterbi算法S2SNS1S1S2viterbi算法t=1t=2t=3S1S2S1S2S1S2BES4S4S4S5S5S5S3S3S3t=4S1S2S4S5S3a01a02a03a04a05a1-0a2-0a3-0a4-0a5-0O1O2O3O42. 隐马尔可夫状态路径预测：Viterbi算法t=1t=2t=3S1S2S1S2S1S2BES4S4S4S5S5S5S3S3S3t=4S1S2S4S5S3a01a02a03a04a05a1-0a2-0a3-0a4-0a5-0O1O2O3O4动画演示：由Viterbi算法计算

26、产生观测序列O的最可能的一条隐藏状态序列QSkSkS1SNOtS1SNSkS1SN0t-1时刻OT t时刻T时刻0SkS1SN1时刻O1初始化阶段(t = 1)中间递归阶段（t = 2,T）结束阶段Ot-1问题2：给定观察序列O=O1,O2, ,OT,以及模型,如何推测最可能的状态序列S ? MaxS1SNSkS1S？S？S？S1Max路径回溯向量3. 预测隐马尔可夫状态路径：Viterbi算法表示t时刻，沿状态路径q1, q2, ,qt,且qt=Sk时，产生已知的观察序列的前面t个子序列o1,o2,ot的最大概率值表示t时刻，到达隐状态sk，且其乘积最大的那个状态对应的标记序号值。路径回溯(

27、3)参数学习问题：已知一个HMM的大致结构，包括各种状态数量。根据一些可见状态序列，求各种状态转移参数aij，bjk。例如：你朋友告诉你很多连续5天他的活动。你猜测天气转换概率和在不同天气下他进行各种活动的概率。3.3参数学习问题1. 隐马尔可夫模型-参数训练问题问题3：给定观察值序列O,如何调整模型参数=(,A,B),使得P(O|)最大 ?t=1t=2t=3t=T-1t=TS1S2SNS1S2SNS1S2SNzS1S2SNS1S2SNaN1A转移概率矩阵B生成概率矩阵a01a02a0N：初始概率向量S2问题本质：参数=(,A,B)的估值问题O1O2O3OT-1OT已知观察序列O？情形1：路径

28、已知时的参数估计 (监督学习方法)情形2：路径未知时的参数估计 (非监督学习方法)问题3：给定观察值序列O,如何调整模型参数=(,A,B),使得P(O|)最大 ?2. 隐马尔可夫模型-参数训练问题即：由最大似然估计法对HMM的参数进行估计S2S3S1S5S2S2S3S1S5V1V3V2V2V1V4V3V4V1?V1V3V2V2V1V4V3V4V1?Baum-Welch算法（EM算法特例）对HMM参数估计转移概率生成概率3. 参数训练算法：Baum-Welch算法基础(将乘积因子按定义展开)前向算法后向算法(将分子中的按其递归计算公式展开)令其为令其为前后向算法关系图4. 参数训练算法：Baum

29、-Welch算法（单观测序列）但在实际应用中,训练一个HMM用到的观测值序列往往不止一个,那么,对于多个观测值序列训练时,要对BW算法的重估公式进行修正.A转移概率矩阵B生成概率矩阵初始概率矩阵A转移概率矩阵B生成概率矩阵0-初始概率矩阵5. 参数训练算法：Baum-Welch算法（多观测序列）这种多观测序列正好适用于蛋白质家族序列中相关问题的解决：如多序列比对情形1：路径已知时的参数估计 (监督学习方法)情形2：路径未知时的参数估计 (非监督学习方法)6. 参数训练算法：Baum-Welch算法过程纵览S2S3S1S5S2S2S3S1S5V1V3V2V2V1V4V3V4V1?V1V3V2V2V1V4V3V4V1?Baum-Welch算法转移概率生成概率初始概率极大似然统计法转移概率生成概率初始概率提 纲隐马尔科夫模型Hidden Markov Model隐马尔科夫模型的三个问题14概率计算问题路径预测问题3参数学习问题应用领域一阶马尔可夫模型（Markov Models）2例子：病情转化假设：某一时刻只有一种疾病，且只依赖于上一时刻疾病一种疾病只有一种症状，且只依赖于当时的疾病症