《HMM隐马尔可夫模型解析课件.ppt》由会员分享，可在线阅读，更多相关《HMM隐马尔可夫模型解析课件.ppt（52页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、隐马尔可夫模型隐马尔可夫模型Hidden Markov model目目 录录n nHMM的历史n nHMM的由来n nHMM的表述n nHMM的分类n nHMM的应用HMM的历史的历史n n70年代，由Baum等人创立HMM理论n n80年代，由Bell实验室的Rabiner等人对HMM进行了深入浅出的介绍n n90年代，HMM被引入计算机文字识别和移动通信核心技术“多用户的检测”n n近年来，HMM在生物信息科学、故障诊断等领域也开始得到应用 HMM的由来n n马尔可夫性n n马尔可夫链n n隐马尔可夫模型马尔可夫性马尔可夫性n n如果一个过程的“将来”仅依赖“现在”而不依赖“过去”，则此过
2、程具有马马尔尔可可夫夫性性,或称此过程为马马尔尔可可夫夫过过程程。由俄国数学家A.A.马尔可夫与1907年提出。n nX(t+1)=f(X(t)n n现实中存在很多马尔可夫过程马尔可夫链马尔可夫链n n时间时间时间时间和和状态状态状态状态都离散的马尔可夫过程称为马尔可夫链都离散的马尔可夫过程称为马尔可夫链n n记作记作XXn n=X(n),n=0,1,2,=X(n),n=0,1,2,n n在时间集在时间集T T1 1=0,1,2,=0,1,2,上对离散状态的过程相继观察的结果上对离散状态的过程相继观察的结果n n链的状态空间记做链的状态空间记做I=aI=a1 1,a,a2 2,a,ai iR.
3、R.n n条件概率条件概率P Pij ij(m,m+n)m,m+n)=PXPXm+nm+n=a=aj j|X|Xmm=a=ai i 为马氏链在时为马氏链在时刻刻mm处于状态处于状态a ai i条件下，在时刻条件下，在时刻m+nm+n转移到状态转移到状态a aj j的的转移概转移概转移概转移概率率率率。马尔可夫链马尔可夫链转移概率矩阵转移概率矩阵阴天阴天晴天晴天下雨下雨 晴天晴天 阴天阴天 下雨下雨晴天晴天 0.50 0.25 0.25阴天阴天 0.375 0.25 0.375下雨下雨 0.25 0.125 0.625马尔可夫链马尔可夫链转移概率矩阵性质转移概率矩阵性质n n由由于于链链在在时时
4、刻刻mm从从任任何何一一个个状状态态a ai i出出发发，到到另另一一时时刻刻m+nm+n，必必然然转转移移到到a a1 1，a a2 2，诸诸状状态态中中的的某某一一个个，所以有所以有n n当当P Pij ij(m,m+n)(m,m+n)与与mm无关时，称马尔科夫链为无关时，称马尔科夫链为齐次马齐次马齐次马齐次马尔可夫链尔可夫链尔可夫链尔可夫链，通常说的马尔科夫链都是指齐次马尔，通常说的马尔科夫链都是指齐次马尔科夫链。科夫链。几种典型形状的马尔可夫链几种典型形状的马尔可夫链n n(a)转移矩阵没有零值的Markov链n n(b)转移矩阵有零值的Markov链n n(c)和(d)是左-右形式表
5、示的Markov链HMM实例实例Observed Ball SequenceUrn 3Urn 1Urn 2VeilHMM实例实例描述描述n n设设有有NN个个缸缸，每每个个缸缸中中装装有有很很多多彩彩球球，球球的的颜颜色色由一组概率分布描述。实验进行方式如下由一组概率分布描述。实验进行方式如下n n根据初始概率分布，随机选择根据初始概率分布，随机选择NN个缸中的一个开始实验个缸中的一个开始实验n n根根据据缸缸中中球球颜颜色色的的概概率率分分布布，随随机机选选择择一一个个球球，记记球球的颜色为的颜色为OO1 1，并把球放回缸中，并把球放回缸中n n根根据据描描述述缸缸的的转转移移的的概概率率分
6、分布布，随随机机选选择择下下一一口口缸缸，重复以上步骤。重复以上步骤。n n最后得到一个描述球的颜色的序列最后得到一个描述球的颜色的序列OO1 1,O,O2 2,，称为，称为观察值序列观察值序列OO。HMM实例实例约束约束在上述实验中，有几个要点需要注意：在上述实验中，有几个要点需要注意：n n不能被直接观察缸间的转移不能被直接观察缸间的转移n n从缸中所选取的球的颜色和缸并不是一一对应的从缸中所选取的球的颜色和缸并不是一一对应的n n每次选取哪个缸由一组转移概率决定每次选取哪个缸由一组转移概率决定HMM概念概念n nHMMHMM的的状状态态是是不不确确定定或或不不可可见见的的，只只有有通通过
7、过观观测测序列的随机过程才能表现出来序列的随机过程才能表现出来n n观察到的事件与状态并不是一一对应，而是通过观察到的事件与状态并不是一一对应，而是通过一组概率分布相联系一组概率分布相联系 n nHMMHMM是一个双重随机过程，两个组成部分：是一个双重随机过程，两个组成部分：n n 马尔可夫链马尔可夫链马尔可夫链马尔可夫链：描述状态的转移，用：描述状态的转移，用转移概率转移概率转移概率转移概率描描述。述。n n 一般随机过程一般随机过程一般随机过程一般随机过程：描述状态与观察序列间的关系，：描述状态与观察序列间的关系，用用观察值概率观察值概率观察值概率观察值概率描述。描述。HMM组成组成 HM
8、MHMM组成示意图组成示意图Markov链链（,A）随机过程随机过程（B）状态序列状态序列观察值序列观察值序列q1,q2,.,qTo1,o2,.,oTHMM的表述的表述n n用模型五元组用模型五元组 （NN，MM，A A，B B）用来描述）用来描述HMMHMM，或简写为，或简写为 =(=(，A A，B)B)参数参数参数参数含义含义含义含义实例实例实例实例NN状态数目状态数目缸的数目缸的数目MM每个状态可能的观察值数每个状态可能的观察值数目目彩球颜色数目彩球颜色数目A A与时间无关的状态转移概与时间无关的状态转移概率矩阵率矩阵在选定某个缸的情况下，在选定某个缸的情况下，选择另一个缸的概率选择另一
9、个缸的概率B B给定状态下，观察值概率给定状态下，观察值概率分布分布每个缸中的颜色分布每个缸中的颜色分布p p初始状态空间的概率分布初始状态空间的概率分布初始时选择某口缸的概率初始时选择某口缸的概率HMM可解决的问题可解决的问题n n评估问题：给定观察序列评估问题：给定观察序列O=OO=O1 1,O,O2 2,OOT T,以及模型以及模型=(=(，A A，B),B),如何计算如何计算P(O|)P(O|)？算法：算法：Forward-BackwardForward-Backward算法算法算法算法n n解码问题：给定观察序列解码问题：给定观察序列O=OO=O1 1,O,O2 2,OOT T以及模
10、型以及模型,如何选如何选择一个对应的状态序列择一个对应的状态序列S=qS=q1 1,q,q2 2,q qT T，使得，使得S S能够最为合理能够最为合理的解释观察序列的解释观察序列OO？算法：算法：ViterbiViterbi算法算法算法算法 n n学习问题：如何调整模型参数学习问题：如何调整模型参数=(=(，A A，B),B),对于给定观测对于给定观测值序列值序列O=OO=O1 1,O,O2 2,OOT T，使得使得P(O|)P(O|)最大？最大？算法：算法：Baum-WelchBaum-Welch算法算法算法算法 HMM的应用的应用(1)词性标注词性标注词性标注词性标注已知单词序列已知单词
11、序列w w1 1w w2 2w wn n，求词性序列，求词性序列c c1 1c c2 2c cn n HMMHMM模型：模型：将词性理解为状态将词性理解为状态将单词理解为输出值将单词理解为输出值训练：训练：统计词性转移矩阵统计词性转移矩阵a aij ij和词性到单词的输和词性到单词的输出矩阵出矩阵b bik ik求解：求解：ViterbiViterbi算法算法HMM的应用的应用(2)疾病分析疾病分析疾病分析疾病分析已知疾病序列已知疾病序列w w1 1w w2 2w wn n，求表征序列，求表征序列c c1 1c c2 2c cn n对应状对应状态转移过程态转移过程 HMMHMM模型：模型：将每
12、种疾病理解为状态将每种疾病理解为状态将输入的表征现象理解为输出值将输入的表征现象理解为输出值训练：训练：统计从一种疾病转移到另一种疾病的转移统计从一种疾病转移到另一种疾病的转移矩阵矩阵a aij ij和某一疾病呈现出某一症状的概率和某一疾病呈现出某一症状的概率矩阵矩阵b bik ik求解：求解：ViterbiViterbi算法算法HMM的三个基本问题的三个基本问题1)1)评估问题2)2)解码问题3)3)学习问题基本问题之一：评估问题基本问题之一：评估问题n n给定一个固定的状态序列给定一个固定的状态序列Q=(q1Q=(q1，q2q2，q3q3)n n 表示在表示在qt qt状态下观测到状态下观
13、测到OtOt的概率的概率n n n n由此的复杂度：由此的复杂度：2TN2TNT,T,N=5,M=100,N=5,M=100,计算计算量量10721072基本问题之一：前向算法基本问题之一：前向算法n n定义前向变量n n初始化：初始化：n n递归：递归：n n终结：终结：复杂度：N2T基本问题之一：前向后向算法基本问题之一：前向后向算法 1 .t t+1 .a1jat1qN.qi.qj.q1atNatiaNjaij基本问题之一：后向算法基本问题之一：后向算法n n与前向法类似，只是递推方向不同.n n定义后向变量n n初始化：初始化：n n递归：递归：n n终结：终结：基本问题之一：后向算法
14、基本问题之一：后向算法后向算法示意图：后向算法示意图：基本问题之二：基本问题之二：Viterbi算法n n目的：给定观察序列目的：给定观察序列OO以及模型,如何选择一如何选择一个对应的状态序列个对应的状态序列Q Q，使得，使得QQ能够最为合理的能够最为合理的解释观察序列解释观察序列OO？n nNN和和T T分别为状态个数和序列长度分别为状态个数和序列长度n n定义：定义：n n我们所要找的，就是我们所要找的，就是T T时刻最大的时刻最大的 所代表所代表的那个状态序列的那个状态序列基本问题之二：基本问题之二：Viterbi算法（续）n n初始化：n n递归：n n终结：n n求S序列：我们考虑计
15、算t时刻到达状态X的最可能的路径；这条到达状态X的路径将通过t-1时刻的状态A，B或C中的某一个。因此，最可能的到达状态X的路径将是下面这些路径的某一个（状态序列），A，X（状态序列），B，X （状态序列），C，X我们想找到路径末端是AX,BX或CX并且拥有最大概率的路径。即：Pr(到达状态到达状态A最可能的路径最可能的路径).Pr(X|A).Pr(观察状态观察状态|X)因此，到达状态X的最可能路径概率是：泛化得：基本问题之三：学习问题基本问题之三：学习问题 n n目的：给定观察值序列目的：给定观察值序列OO，通过计算确定一个模型，通过计算确定一个模型l ，使得使得P(O|P(O|l)最大。最
16、大。n n算法步骤：算法步骤：n1.初始模型（待训练模型）l0,n2.基于l0以及观察值序列O，训练新模型 l0；n3.如果 logP(X|l)-log(P(X|l0)Delta，说明训练已经达到预期效果，算法结束。n4.否则，令l0 l，继续第2步工作 n n定义：定义：Baum-Welch算法(续)n n参数估计：参数估计：Baum-Welch算法(续2)HMM结构结构n n全连接全连接n n从左至右从左至右n n无跨越无跨越n n有跨越有跨越n n并行并行n nHMM认为语音按时间顺序，从相对稳定的一段特性（状态）随机地过渡到另一段特性，每个状态又随机地输出一个观察值。n nHMM认为语
17、音t+1时刻的状态由t时刻状态的统计特性，即状态转移概率确定；这个状态产生的输出亦为随机的，取决于该状态生成语音观察量的概率。n n无跨越模型符合人类的语音特点，广泛应用于语音识别中。n n有跨越用于反映音素在发音中可能被吸收或删除的情况。Two types of HMMn nState-emission HMM(Moore machine):n nThe output symbol is produced by states:The output symbol is produced by states:n nBy the from-stateBy the from-staten nBy t
18、he to-stateBy the to-staten nArc-emission HMM(Mealy machine):n nThe output symbol is produce by the edges;i.e.,by The output symbol is produce by the edges;i.e.,by the(from-state,to-state)pairs.the(from-state,to-state)pairs.Output symbols are generated by the from-statesn nState sequence:XState sequ
19、ence:X1,n1,nn nOutput sequence:OOutput sequence:O1,n1,no1onX1X2Xno2Output symbols are generated by the to-statesn nState sequence:X1,n+1n nOutput sequence:O1,no1onX2X3Xn+1o2X1Are the two types of HMMs equivalent?n nFor each state-emission HMM1,there is an arc-emission HMM2,such that for any sequence
20、 O,P(O|HMM1)=P(O|HMM2).n nThe reverse is also true.DHMM：离散的符号作为观测量b bj j(x)(x)b bj j(k)(k)b bj j(x)(x)CHMM：观测量为连续概率密度函数每个状态有不同的一组概率密度函数SCHMM：观测量为连续概率密度函数所有状态共享一组概率密度函数观测序列概率表示方法HMM应用中的问题应用中的问题/注：有些问题结合语音识别来具体解释。注：有些问题结合语音识别来具体解释。梁大为梁大为1 1初始模型选取初始模型选取2 2多个观察值序列训练多个观察值序列训练3 3数据下溢数据下溢4 4训练数据不足训练数据不足初始模
21、型选取初始模型选取1.1.Baum-Welch Baum-Welch 算法的基础参数。算法的基础参数。2.2.全局最大值与局部最大值全局最大值与局部最大值 和和A A的初值选取对结果影响不大。的初值选取对结果影响不大。：1 1=1=1 ，i i=0=0。A A：B B的初值对训练出的的初值对训练出的HMMHMM参数影响较大。对离散参数影响较大。对离散HMMHMM，可以采，可以采用均值或随机设置；在连续用均值或随机设置；在连续HMMHMM中，包含的参数越多越复杂，中，包含的参数越多越复杂，参数初值的设置对于迭代计算的结果越至关重要。语音单位较小参数初值的设置对于迭代计算的结果越至关重要。语音单位
22、较小时可以用手工对输入的语音进行状态划分并统计出相应的概率分时可以用手工对输入的语音进行状态划分并统计出相应的概率分布作为初值；对于较大的语音单位，普遍采用布作为初值；对于较大的语音单位，普遍采用分段分段K-K-均值均值算法。算法。1.1.将所有观察值序列将所有观察值序列 平均分为平均分为NN段，每段对应段，每段对应1 1个个HMMHMM状态状态X Xi i；2.2.利用利用3-83-8所示分段所示分段K-K-均值算法对属于每个状态的所有序列分别进行聚类，均值算法对属于每个状态的所有序列分别进行聚类，得到连续混合正态分布得到连续混合正态分布(GMM)(GMM)，获得初始参数。，获得初始参数。3
23、.3.根据经验、随机或间隔选取根据经验、随机或间隔选取MM个点，分别作为高斯混合函数中个点，分别作为高斯混合函数中MM个类空个类空间间 的中心点的中心点C C1 1，C C2 2，C CMM，其中，其中 表示表示X Xi i段中第段中第j j个个类空间，该类中包含的观察值个数记为类空间，该类中包含的观察值个数记为 ；4.4.根据观察值到各中心点最短的原则，将本段中的所有观察值序列根据观察值到各中心点最短的原则，将本段中的所有观察值序列 分配到类空间分配到类空间 中去，并记类中去，并记类 的的5.5.根据上一过程中每个类根据上一过程中每个类 所获得的观察值序列，计算新的中心点：所获得的观察值序列
24、，计算新的中心点：6.6.将此段中所有观察值序列将此段中所有观察值序列 到其对应类中心距离的平方和到其对应类中心距离的平方和 作为算法收敛的条件。若作为算法收敛的条件。若 与上一次循环相比，如果基本没有与上一次循环相比，如果基本没有变化，则算法收敛，转入第变化，则算法收敛，转入第8 8步，步，7.7.如果循环次数小于最大循环次数如果循环次数小于最大循环次数K K，则转入第，则转入第4 4步继续循环；步继续循环；8.8.根据上述循环计算得到的观察值序列分别情况，利用下列公式，根据上述循环计算得到的观察值序列分别情况，利用下列公式，对状态下的模型参数进行初始化，其中，对状态下的模型参数进行初始化，
25、其中，多个观察值序列训练多个观察值序列训练用用NN个观察序列训练个观察序列训练HMMHMM时，要时，要Baum-WelchBaum-Welch算法的重估公式加以修算法的重估公式加以修正。设正。设NN个观察序列为个观察序列为OO(n)(n)，n=1,2,n=1,2,N,N，其中，其中假定各个观察值序列相互独立，则有假定各个观察值序列相互独立，则有重估公式修正为：重估公式修正为：数据下溢问题数据下溢问题 在前向在前向-后向算法中，计算前向概率变量后向算法中，计算前向概率变量 和后向概率变量和后向概率变量 的过程中，每个参与运算的乘积项都是小于的过程中，每个参与运算的乘积项都是小于1 1。在递归过程
26、中，由于。在递归过程中，由于多项连乘，使得变量越来越小，可能会使数据无限地趋向于零，甚多项连乘，使得变量越来越小，可能会使数据无限地趋向于零，甚至会超出计算机所能表示的范围，带来数据的溢出问题。至会超出计算机所能表示的范围，带来数据的溢出问题。每一步都除以一个小于每一步都除以一个小于1 1的标定系数，使递归过程中的变量所处的标定系数，使递归过程中的变量所处的数量级基本不变。最后，为了使最后结果不受标定系数的影响再的数量级基本不变。最后，为了使最后结果不受标定系数的影响再将标定系数进行分离。令将标定系数进行分离。令t t时刻的标定系数为时刻的标定系数为 ，标定后的前向变，标定后的前向变量和后向变
27、量为：量和后向变量为：，1.1.对对 的处理的处理 初始化：初始化：递递 归：归：2.2.对对 的处理的处理 初始化：初始化：递递 归：归：3.3.对对 的处理的处理4.4.对重估公式的处理对重估公式的处理5.5.对对ViterbiViterbi算法的处理：对数化算法的处理：对数化将将 重新定义为：重新定义为：训练数据不足训练数据不足 模型参数较多，需要大量的训练数据。简单地减少模型中的状模型参数较多，需要大量的训练数据。简单地减少模型中的状态数和每个状态上的混合高斯分量数，也有实际的困难。态数和每个状态上的混合高斯分量数，也有实际的困难。将一个训练较充分，但细节较差的模型将一个训练较充分，但
28、细节较差的模型 1 1与一个训练虽不充分，与一个训练虽不充分，但细节较好的模型但细节较好的模型 2 2进行混合。可以在进行混合。可以在 1 1中将有些状态转移概率及观中将有些状态转移概率及观察输出概率相近的进行察输出概率相近的进行“捆绑捆绑”，即一些转移概率或观察值输出概，即一些转移概率或观察值输出概率共享相同的值，从而可以减少模型参数。率共享相同的值，从而可以减少模型参数。合并两个合并两个HMMHMM的问题可以表示为：的问题可以表示为：=1 1 +(1-+(1-)1 1 =(=(,A,B),A,B)合为结果模型，合为结果模型，1 1=(=(1 1,A,A1 1,B,B1 1)和和 2 2=(=(2 2,A,A 2 2,B,B 2 2)为待合为待合并模型。并模型。设设 和和 为为 1 1和和 2 2中状态中状态j j对应的观察值概率，对应的观察值概率，为为 中状态中状态j j对对应的观察值概率，则：应的观察值概率，则：估计估计 的问题可以转化为训练的问题可以转化为训练HMMHMM参数的问题。所以，可以将参数的问题。所以，可以将所以的训练数据分成几部分，一部分数据用来估计所以的训练数据分成几部分，一部分数据用来估计，其余的数据用，其余的数据用来训练来训练 1 1和和 2 2。End！