隐马尔科夫模型ppt课件

1、隐马尔科夫模型（隐马尔科夫模型（HMMHMM）1;.2Table of Contents马尔科夫模型隐马尔科夫模型HMM基本问题3.1 HMM评估问题3.2 HMM解码问题3.3 HMM学习问题HMM应用背景4.1 自动文本分类4.2 汉语词性标注4.3 汉语自动分词4.4 文本信息抽取4.5 其他应用领域31.马尔科夫模型马尔科夫模型马尔科夫(Markov)模型是由俄罗斯数学家Andrei AMarkov于20世纪初提出的一个统计模型。有限状态的离散时间Markov链是一个长度为T的随机变量序列 ， 的取值范围是有限状态集有限状态集 。12Q=q ,q .q Tqt12S ,S .S N假定

2、它满足以下两个条件：（1）任一时刻的随机变量只依赖于前一时刻的随机变量任一时刻的随机变量只依赖于前一时刻的随机变量：121(q =S |q=S ,q=S .)(q =S |q=S )tjtitktjtiPP（2）时间无关性（马尔科夫性）时间无关性（马尔科夫性）：121(q =S |q=S )(q =S |q =S ), 1,tjtijiijPPai jN则显然有：0,ijai j ，11, ,Nijjai j4以上随机过程可以称为可观测可观测MarkovMarkov模型模型，因为此过程的输出在每一个时间点是一个状态，并且每一个状态对应一个可观测事件。上述模型称为一阶Markov模型。如把条件（

3、1）适当放松，任一时刻的随机变量只依赖于前两（三，k）个时刻的随机变量，则此模型为两（三，k）阶Markov模型。MarkovMarkov模型模型52.隐马尔科夫模型隐马尔科夫模型一个HMM是不确定的、随机的有限状态自动机，由不可观测的状态转移过程状态转移过程(一个Markov链)和可观测的观察生成过程观察生成过程组成。按观测值是离散还是连续的，HMM可分为离散型和连续型。我们这里主要介绍离散HMM。一阶离散HMM是一个五元组： ，可以简写为 ，其中N是Markov链状态数;M是状态可能生成的观察值数; 表示初始状态概率向量，其中 ,N MA B,A B1(,.,)N1(q =S ), 1ii

4、PiN A为状态转换概率分布矩阵状态转换概率分布矩阵，表示i状态向j状态转换的概率： ，其中: *()ijN NAat 1= (q=S |q =S ), 1,ijjtiaPi jNB为观察值概率分布矩阵观察值概率分布矩阵，表示在j状态输出观察值k的概率： ，其中: *( ( )jN MBb kj( )= (=|q =S ), 1, 1jtktb kP ONjkM隐马尔可夫模型（HMM）是一种在Markov链的基础上发展起来的统计信号模型，能够利用收集的训练样本进行自适应学习。6隐马尔科夫模型隐马尔科夫模型7HMM拓扑结构拓扑结构左右型的左右型的HMMHMM全连通的全连通的HMMHMM含并行结构

5、的含并行结构的HMMHMM含间隔跳转的含间隔跳转的HMMHMM83.HHM基本问题基本问题HMM理论有3个基本问题：（2 2）解码问题）解码问题给定一个HHM的模型 和观测序列 ，如何选择对应最佳的状态序列，使它在某种状态下最优（出现的概率最大），以较好地解释观测值12( ,.,)TOO OO（1 1）评估问题）评估问题给定一个HHM的模型 和观测序列 ，如何高效的计算此模型产生的观测序列的概率12( ,.,)TOO OO(| )P O（3 3）学习问题（训练问题）学习问题（训练问题）给定观测序列 ，如何调整模型参数 ，以使得观察序列出现的概率 最大化12( ,.,)TOO OO(|)P O9

6、3.1评估问题评估问题解决HHM评估问题的典型算法有穷举搜索直接计算法、前向算法和后向算法：一、穷举搜索直接计算一、穷举搜索直接计算1、算法思想列举长度为T的所有可能的状态序列 ，分别求解各个状态序列与观测序列的联合概率 ，最后求和得到12,.,TQq qq(,|)P O Q(|)P O2、算法过程（1）状态序列 出现的概率为：11 22 31(|).TTii ii iiiP Qaaa（2）对于其中一种状态序列，观测序列的概率为： 依据贝叶斯公式：1212(|, )()().()TiiiTP O QbO bObO111 22112(,|,)(|,) (|)()().()TTTiii iiiii

7、TP OQP O QP QbO abOabO12,.,TQq qq10（3）求和：111 2211212,.,(|)(|, ) (|)()().()TTTTiii iiiiiTIi iiP OP O QP Qb O a bOabO3、算法评价由于每一时刻点所到达的状态有N种可能，所以总的不同的状态序列有 种。其中每一个状态序列需要2T-1次乘法运算。所以总的运算量为 次乘法运算（此外还需要 次加法运算）。(21)TNT 1TN TN穷举算法的时间复杂度为 ，在求解 的过程中存在大量的重复计算，不适用不适用于大的模型和较长的序列于大的模型和较长的序列。()TO TN(|)P O11二、前向算法二

8、、前向算法1、算法思想到达某网格节点的概率可以用前一时刻N个节点的概率表示出来。前向算法通过已经保存了的子路径来计算新路径的概率。HHM网状结构网状结构12(3)终止，在时刻T所有隐状态（对应观测值 ）的概率求和:1(|)( )NTiP OiTO(2)递归，计算t+1时刻处于各隐状态（对应观测值为 ）的概率:t+111( )( )b (O) , 1, 1Ntijjtiji atT-1jN1tO2、算法过程定义到时刻t，部分观测序列为 ，状态 的前向概率前向概率为：12( )(,.,| ) , 2 ttttiiP O OO qST12,.,tOO OOiq(1)初始化,计算t=1时处于各隐状态（

9、对应观测值为 ）的概率:11( )=b (O ) , 1iiiiN1O13t t时刻前向概率的递归关系时刻前向概率的递归关系3、算法评价由以上算法过程可知，计算 总共需要 次乘法运算和 次加法运算。( )ti(1)(1)N NTN(1)(1)N NT前向算法的复杂度为 ，相比于穷举法计算，复杂度降低了几个数量级降低了几个数量级，减少了重复计算。2()O TN142 2后向算法后向算法(1)初始化,最终时刻的所有状态的概率规定为：( )=1 , 1iTi N定义从时刻t+1到时刻T，部分观测序列为 ，状态 的后向概率后向概率为:1+2( )(,.,|, ) , 1 ttttTtiiP OOOqS

10、T-1t1 ,.,tTOO OOiq1、算法思想和前向算法基本一致，唯一的区别是选择的局部状态不同局部状态不同。2、算法过程(2)递归，计算t时刻处于各隐状态（对应观测值为 ）的概率:t111( )b (O)( )1iNijjttjiaj， t=T-1,T-2,.,1 NtO15(3)终止：111(|)=b (O )( )NiiiP Oi3、算法评价t t时刻后向概率的递归关系时刻后向概率的递归关系由以上算法过程可知，计算 总共需要 次 乘法运算和 次加法运算。( )ti21T 2N（）(1)(1)N NT后向算法的复杂度与前向算法相等，都是 。2()O TN163.2解码问题解码问题1、算法

11、思想解答解码问题，即寻求对于给定观测序列的最优状态序列最优状态序列。有好几种标准可用于定义最优状态序列。比如，其中一个可能的优化标准是分别选择每个时刻各自最可能的状态。每个时刻各自最可能的状态。但是每个时刻最可能的状态的叠加不一定能得到最可能的状态序列。可能这种得到的最优序列根本是“不合法”的。这种算法仅简单地考虑了每一个时刻点各自最可能的状态，而没有考虑到状态序列发生的概率。定义优化标准为：寻求单一最佳状态序列，以最大化 ，运用贝叶斯原理，也即最大化(,|)P Q O(|, )P Q O对于上述问题的一个可行的解决方案就是修改优化标准。于是提出了解决HMM解码问题的一个典型算法 Viterb

12、i算法算法。17(3)终结：*max ( )TPi1 i N*arg max( )TTqi1iN(4)状态序列路径回溯路径回溯： *11() , =1,2,.,1tttqqTT1 i Nt(1)初始化：11( )b (O ) , 1iiiiN1( ) 0 , 1iiN(2)递归： 1( )max( )b (O ) , 21ttijjtji a1iNtT, jN1( )arg max( ) , 21ttijji a1iNtT, jN2、算法过程定义 为时刻t系统沿单一路径的最高得分，它解释了前t个观测符号，并结束于 ：1( ) iiS12112112q ,q ,.,q( )maxq ,q ,.,

13、q,q,.,| ttttitiPS O OO同时，定义一个参数数组 ，记录目标状态序列的每个时刻t和状态 iS( )tj18在实现上，Viterbi算法和前向算法十分相似。最主要的区别在于在Viterbi算法中递归时对以前的状态取最大值，而在前向算法中则对以前的状态取加和。3、算法评价 维特比算法的时间复杂度也是O(N2T) 维特比算法的时间复杂度也是 。2()O TN193.3学习问题学习问题解决HMM学习问题的常用算法有前向前向-后向算法（后向算法（Baum-Welch算法）算法）：第三个问题用来解答如何调整一个给定HMM的参数使得在某种准则下，该HMM最大化观测序列的概率，这也是三个问题

14、中难度最大的问题。目前还没有方法可解析地求解模型的参数使得能最大化观测序列的概率。事实上，对于任何一个用作训练用的有限长的观测序列，还没有一个全局最优全局最优的模型参数估计的方法。1、算法思想BW算法运用了机器学习中的梯度下降梯度下降的思想。首先对于HMM 的参数 进行一个初始的估计（很可能是错误的），然后通过训练评估参数 的有效性并减少它们所引起的错误来更新 ，使得和给定的训练数据的误差变小。20定义 为给定训练序列O和模型 时，时刻t时Markov链处于状态 和时刻t+1时状态为 的概率，即( , )ti jjSiS11(q,q,| )( , )(q,q|, )(| )titjttitjP

15、SS Oi jPSSOP O2、算法过程11(|q,q, )* (q,q| ) (| )titjtitjP OSSPSSP O1211+211 ( ,.,|q,q, ) (,.,|q,q, )* (q,q| )( | )ttitjttTtitjtitjPO OOSSPO OOSSPSSPO121+211 (,.,|q, ) (,.,|q, )* (q,q| ) (|)ttittTtjtitjP O OOSP OOOSPSSP O2111( )()()(|)tijjtti a bOjP O12111+211 ( ,., ,q| ) (|q, ) (,.,|q, )* (q,q| ) (q| )

16、( | )ttittjttTtjtitjtiPO OOSPOSPO OOSPSSPSPO111( )b (O)( )*(q,q| ) (q| ) (|)tjtttitjtiijPSSPSP O22( , )ti j网格计算关系图网格计算关系图23对模型参数进行重估重估：11=W11( )( )( )tkTttOjTttjbkj且1111( ,)( )TttijTttijai1( )ii( )(|,)ttiiP qSO定义后验概率函数后验概率函数：1( )( ,)Nttjiij有：, (|)(|)AP OP OB并且于是，我们从某个模型 开始（可以预先或随机选择），可以推出如下新的模型：,A B

17、(| )P O利用上述公式进行反复的参数估计，直到 不再有明显提高。243、算法评价BW算法是一种反复爬山法，是EM(期望值最大化期望值最大化)算法算法的一个特例。最大化过程被称为在训练集上的训练。它只能找到局部最优解局部最优解。为了使得到的是全局极大，必须要求 的初始值给得接近全局极大。这是应用本法的一项难点。254.HHM应用背景应用背景264.1自动文本分类自动文本分类自动文本分类领域近年来已经产生了若干成熟的分类算法，如支持向量机支持向量机(SVM)、K近邻近邻(KNN)、朴素贝叶斯、朴素贝叶斯(NB)等算法，但这些算法主要基于概率统计模型概率统计模型，没有与文本自身的语法和语义建立起

18、联系。杨健杨健, 汪海航汪海航. 基于隐马尔可夫模型的文本分类算法基于隐马尔可夫模型的文本分类算法J. 计算机应用计算机应用, 2010, 30(9):2348-2350.提出了将隐马尔可夫序列分析模型(HMM)用于自动文本分类的算法。该模型通过观察文本的特征词组成及频率特征词组成及频率对不同类别文本进行分类，分别建立HMM分类器。HMM中的观察输出就是特征词的组成。HMM的状态转换，可以看做是从与该类别不是很相关的词组成的文档输出分布，向与该类别非常相关的词组成的文档输出分布转化的一种过程。因此，状态从起始点向终结点转化对应着类别相关词汇的强化。27HMM分类器训练分类器训练 文本预处理，文

19、档文本预处理，文档词集词集 利用信息增益 (IG)进行特征词选择 利用2检验进行类特征词集抽取 分类器HMM模型参数学习 用不同类标号训练文档训练相应的 HMM 分类器28HMM分类器应用分类器应用HMMHMM评估问题评估问题 文本预处理文本预处理 将类特征集中的特征词升序排列 选取分类文档IG最大的k个特征词，组成输出观察序列 利用前向或后向算法，计算类别的 依次计算每个类别的 ，选取概率最大的类别作为待分类文档的类标号(|)P O(|)P O294.2汉语词性标注汉语词性标注王敏王敏, 郑家恒郑家恒. 基于改进的隐马尔科夫模型的汉语词性标注基于改进的隐马尔科夫模型的汉语词性标注J. 计算机

20、应用计算机应用, 2006, 26(s2):197-198.介绍了一种改进的HMM，更能体现词语的上下文依赖关系。词性标注的任务是计算机通过学习自动地标注出有歧义的词的词性。现有的词性标注所采用的语言模型主要可以分为基于规则基于规则的方法和基于统计基于统计的方法。基于规则的方法适应性较差，并且非统计模型的本质使它通常作为一个独立的标注器，而很难被用作更大概率模型的组件部分。传统的HMM只考虑到了上文对当前词的依赖关系，没有考虑到该词后面即下文与该词的依赖关系。词性标注问题可描述为HMM解码问题解码问题，即在给定观察序列（词序列词序列）的条件下搜索最佳的隐马尔科夫状态序列（词性序列词性序列）的问

21、题。30传统传统HMMHMM与改进与改进HMMHMM的测试结果比较的测试结果比较314.3汉语自动分词汉语自动分词李家福李家福, 张亚非张亚非. 一种基于概率模型的分词系统一种基于概率模型的分词系统J. 系统仿真学报系统仿真学报, 2002, 14(5):544-546.提出了一种基于生语料库（语料库未作任何切分）的算法，基于词的出现概率，根据极大似然原极大似然原则则进行分词。词是自然语言处理系统中重要的知识载体与基本操作单元。在书面汉语中词与词之间没有明显的切分标志。给定词的出现概率，根据极大似然原则（MLP），一个句子分成词 ，须使 最大。本模型可以看成一个零阶零阶HHM。()iP w12,.,mwww32HMM模型的训练模型的训练EM算法：算法： 随机给出词的概率的初始值随机给出词的概率的初始值 使用当前的词的概率值，对语料库中的句子进行分词处理 依据分词结果，重新计算词的概率 重复这个过程，进行多次迭代，直到概率值收敛33分词算法性能比较分词算法性能比较344.4文本信息抽取文本信息抽取在一阶隐马尔可夫模型中，假设状态转移概率和观察值输出概率仅依赖于模型当前的状态，一定程度降低了信息抽取的精确度。而二阶隐马尔可