隐马尔可夫模型课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,知识管理与数据分析实验室,*,隐马尔可夫模型,Hidden Markov model,2024/9/8,1,知识管理与数据分析实验室,内容框架,隐马尔科夫模型的由来,隐马尔科夫模型的基本理论及实例,隐马尔科夫模型的三个基本算法,隐马尔科夫模型的应用,4,1,2,3,2024/9/8,2,知识管理与数据分析实验室,隐马尔可夫模型（,HMM,）的由来,1870,年，俄国有机化学家,Vladimir V. Markovnikov,第一次提出,Markov Model,（,MM,）,Baum,及他的同事于,60,年代末,70,年代初提出隐马尔可夫理论，并用于语音识别,80,年代末,90,年代初,HMM,被用于计算生物学,目前已成功用于人脸识别、手写识别领域,2024/9/8,3,知识管理与数据分析实验室,内容框架,隐马尔科夫模型的由来,隐马尔科夫模型的基本理论及实例,隐马尔科夫模型的三个基本算法,隐马尔科夫模型的应用,4,1,2,3,2024/9/8,4,知识管理与数据分析实验室,隐马尔可夫模型的基本理论,马尔可夫性,马尔可夫,过程,马尔可夫链,隐马尔可夫模型,2024/9/8,5,知识管理与数据分析实验室,马尔可夫性,如果一个过程的“将来”仅依赖“现在”而不依赖“过去”，则此过程具有,马尔可夫性,或称此过程为,马尔可夫过程。用公式表示：,X(t+1) = f( X(t) ),2024/9/8,6,知识管理与数据分析实验室,马尔科夫过程,过程或系统在时刻,T,0,所处状态为已知的条件下，过程在时刻,TT,0,所处状态的条件分布与过程在时刻,t,0,之前所处的状态无关。,通俗的说，就是在已经知道过程“现在”的条件下，其“将来”不依赖于“过去”。,2024/9/8,7,知识管理与数据分析实验室,马尔科夫链,时间,和,状态,都离散的马尔科夫过程称为马尔科夫链,记作,X,n,= X(n), n = 0,1,2,在时间集,T,1,= 0,1,2,上对离散状态的过程相继观察的结果,链的状态空间记做,I = a,1, a,2, a,i,R.,条件概率,P,ij,(,m ,m+n)=PX,m+n,= a,j,|X,m,= a,i,为马氏链在时刻,m,处于状态,a,i,条件下，在时刻,m+n,转移到状态,a,j,的转移概率。,2024/9/8,8,知识管理与数据分析实验室,隐马尔科夫模型,HMM,是一个双重随机过程，两个组成部分：,马尔可夫链,：描述状态的转移，用转移概率描述。,一般随机过程,：描述状态与观察序列间的关系， 用观察值概率描述。,2024/9/8,9,知识管理与数据分析实验室,隐马尔科夫模型的组成,Markov,链,（, A,）,随机过程,（,B,）,状态序列,观察值序列,q,1, q,2, ., q,T,o,1, o,2, ., o,T,2024/9/8,10,知识管理与数据分析实验室,一个实验,球缸模型,设有,N,个缸，每个缸中装有很多彩球，球的颜色由一组概率分布描述。实验进行方式如下,根据某个初始概率分布，随机选择,N,个缸中的一个，例如第,I,个缸。,根据这个缸中彩球颜色的概率分布，随机选择一个球，记下球的颜色，记为,O,1,，再把球放回缸中。,根据描述缸的转移的概率分布，随机选择下一口缸，重复步骤,1,。,最后我们可以得到一个描述球的颜色的序列,O,1,O,2,，称为观察值序列。,2024/9/8,11,知识管理与数据分析实验室,球缸模型示意图,观测到的球序列,缸,3,缸,1,缸,2,通道,2024/9/8,12,知识管理与数据分析实验室,关于球缸模型的说明,缸之间的转移不能被直接观察到,从缸中所选取的球的颜色和缸并不是,一一对应的,每次选取哪个缸由一组转移概率决定,2024/9/8,13,知识管理与数据分析实验室,HMM,中状态与观测的对应关系示意图,2024/9/8,14,知识管理与数据分析实验室,HMM,的基本要素,用模型五元组 （,N, M, ,，,A,，,B,）用来描述,HMM,，或简写为,=(,，,A,，,B),2024/9/8,15,知识管理与数据分析实验室,HMM,可解决的问题,给定观测序列,O=O1O2O3Ot,和模型参数,=(A,B,),，怎样寻找某种意义上最优的隐状态序列。此问题主要用,Viterbi,算法。,给定观测序列,O=O1O2O3Ot,和模型参数,=(A,B,),，怎样有效计算某一观测序列的概率。此问题主要用向前向后算法。,怎样调整模型参数,=(A,B,),，使观测序列,O=O1O2O3Ot,的概率最大。此问题主要用,Baum-Welch,算法。,评估问题,解码问题,学习问题,2024/9/8,16,知识管理与数据分析实验室,内容框架,隐马尔科夫模型的由来,隐马尔科夫模型的基本理论及实例,隐马尔科夫模型的三个基本算法,隐马尔科夫模型的应用,4,1,2,3,2024/9/8,17,知识管理与数据分析实验室,向前算法及向后算法,向前算法及向后算法主要解决评估问题，即用来计算给定一个观测值序列,O,以及一个模型,时，由模型,产生出观测值序列,O,的概率 。,2024/9/8,18,知识管理与数据分析实验室,向前算法,向前变量 它的含义是，给定模型,，时刻,t,。处在状态,i,，并且部分观察序列为的概率 显然,当 已知时根据,，,迭代计算,最后根据公式 求出概率。,2024/9/8,19,知识管理与数据分析实验室,计算实例：抛掷硬币问题，计算观察到,(H H T),的概率,2024/9/8,20,知识管理与数据分析实验室,向后算法,向后变量,含义是，给定模型,，时刻,t,。处在状态,i,，并且部分观察序列为 的概率。,当已知 ， ，则根据公式,迭代计算。,最后根据公式 求出概率,2024/9/8,21,知识管理与数据分析实验室,计算实例：抛掷硬币问题，计算观察到,(H H T),的概率,2024/9/8,22,知识管理与数据分析实验室,韦特比算法,(Viterbi Algorithm),对于解码问题，我们常用为比特算法来解决问题，即用来解决给定观测序列,O=O1O2O3Ot,和模型参数,=(A,B,),，寻找某种意义上最优的隐状态序列问题。,在介绍算法前，首先明确两个变量的意义,韦特比变量,变量的含义是，给定模型,，时刻,t,处在状态,i,，观察到的,最佳状态转换序列为的 概率,。,记录路径的数组,该数组记录在时刻,t,到达状态,i,的最佳状态转换序列,t-1,时刻的最佳状态,。,2024/9/8,23,知识管理与数据分析实验室,韦特比算法（续）,韦特比算法主要有四个步骤,：,首先，初始化变量，使得：,第二步，迭代计算,第三步，终止：,第四步，求解最佳路径：,2024/9/8,24,知识管理与数据分析实验室,计算实例：抛掷硬币问题，观察到,(H H T),，寻找产生该观察序列的最佳路径以及最佳路径的概率,最佳状态转换序列为,1 1 1,2024/9/8,25,知识管理与数据分析实验室,Baum-Welch,算法,隐马尔科夫模型的第三个问题是如何根据观察序列,O,=(,o,1,o,2,o,3 ,oT,),求得模型参数或调整模型参数，即如何确定一组模型参数使得,P,(,O,|,),最大的问题。在模型,(,),未知的情况下，如果给定观察序列的同时，也给定了状态转换序列，此时可以通过有指导的学习方法学习模型参数。常用算法：,Baum-Welch,算法。,首先，定义变量 它表示在给定模型以及观察序列的情况下，,t,时刻处在状态,i,的概率。用公式表示：,观察序列,O,中，从状态,i,出发的转换的期望概率为,观察序列,O,中，从状态,i,到状态,j,的转换的期望概率,隐马尔科夫模型的第三个问题是如何根据观察序列,O,=(,o,1,o,2,o,3 ,oT,),求得模型参数或调整模型参数，即如何确定一组模型参数使得,P,(,O,|,),最大的问题。在模型,(,),未知的情况下，如果给定观察序列的同时，也给定了状态转换序列，此时可以通过有指导的学习方法学习模型参数。常用算法：,Baum-Welch,算法。,首先，定义变量 它表示在给定模型以及观察序列的情况下，,t,时刻处在状态,i,的概率。用公式表示：,观察序列,O,中，从状态,i,出发的转换的期望概率为,观察序列,O,中，从状态,i,到状态,j,的转换的期望概率,2024/9/8,26,知识管理与数据分析实验室,Baum-Welch,算法（续）,关于,A,B,，给出一种合理的估计方法：,在,t=1,时处在状态,i,的概率：,从状态,i,到状态,j,的转换的期望概率除以从状态,i,出发的转换的期望概率：,其中分子表示在状态,j,观察到的期望概率，并且当 时， ；当 时， ；分母表示处在状态,j,的期望概率,根据以上结论可进行模型估算，反复迭代，直至参数收敛。,2024/9/8,27,知识管理与数据分析实验室,内容框架,隐马尔科夫模型的由来,隐马尔科夫模型的基本理论及实例,隐马尔科夫模型的三个基本算法,隐马尔科夫模型的应用,4,1,2,3,2024/9/8,28,知识管理与数据分析实验室,隐马尔科夫模型的应用,隐马尔科夫模型,应用于,语音识别,书面语理解,基因预测,人脸识别,2024/9/8,29,知识管理与数据分析实验室,语音识别,隐马尔可夫模型在语音识别中的应用,20,世纪,80,年代,美国,CMU,大学的,J. K. Baker,等人将,HMM,应用到语音识别领域,在语音识别中获得了极大的成功,成为语音识别的主要方法。,目前应用最为成功的语音识别系统大多是基于隐马尔可夫模型构造的,.,如,CMU,的,Kai2Fu lee,等研制的,SPH INX,连续语音识别系统,对,997,个词在有无文法限制的条件下,识别率分别为,96%,和,82%. IBM,构造的,Tango ra2000,词语音识别系统得到,95%,的识别率。用,HMM,进行汉语声母、韵母、单音节及连续语音识别,都得到了很好的性能。,2024/9/8,30,知识管理与数据分析实验室,书面语理解上的应用,在词性标注方面,采用隐马尔可夫模型的标注方法具有很强的健壮性,是当前主流的标注方法。,词性标注就是在给定的句子中判定每个词的语法范畴,确定词性并加以标注的过程,它发生在对文本执行分词处理之后,是对切分所得的词进行分析、运算,确定词在上下文中合适的词类性质并加以标注的过程。,在隐马尔可夫模型下,词性标注问题可以表述为,:,在给定观察值和模型参数的情况下,求状态序列,T=t1, t2, t3,tm,使得这一状态序列可以“最好地解释”观察值序列,W=w1, w2, w3, wm,。,T,为最终的标注结果,即概率最大的词性序列。,2024/9/8,31,知识管理与数据分析实验室,生物学基因预测上的应用,隐马尔可夫模型,(HMM),研究是当前机器学习的热点领域,该模型在,80,年代末,90,年代初该模型就被应用于计算生物学。隐马尔可夫模型能很好地模拟生物的进化过程,其在生命科学特别是生物信息领域很受欢迎,特别是在生物信息检测领域,已用于基因预测、蛋白质家族的构建方面。,