隐马尔可夫模型

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