隐马尔科夫模型PPT.ppt
隐马尔科夫模型（HMM）,Table of Contents,马尔科夫模型 隐马尔科夫模型 HMM基本问题 3.1 HMM评估问题 3.2 HMM解码问题 3.3 HMM学习问题 HMM应用背景 4.1 自动文本分类 4.2 汉语词性标注 4.3 汉语自动分词 4.4 文本信息抽取 4.5 其他应用领域,1.马尔科夫模型,马尔科夫(Markov)模型是由俄罗斯数学家Andrei AMarkov于20世纪初提出的一个统计模型。,有限状态的离散时间Markov链是一个长度为T的随机变量序列 ， 的取值范围是有限状态集 。,假定它满足以下两个条件：（1）任一时刻的随机变量只依赖于前一时刻的随机变量：,（2）时间无关性（马尔科夫性）：,则显然有：,以上随机过程可以称为可观测Markov模型，因为此过程的输出在每一个时间点是一个状态，并且每一个状态对应一个可观测事件。,上述模型称为一阶Markov模型。,如把条件（1）适当放松，任一时刻的随机变量只依赖于前两（三，k）个时刻的随机变量，则此模型为两（三，k）阶Markov模型。,Markov模型,2.隐马尔科夫模型,一个HMM是不确定的、随机的有限状态自动机，由不可观测的状态转移过程(一个Markov链)和可观测的观察生成过程组成。按观测值是离散还是连续的，HMM可分为离散型和连续型。我们这里主要介绍离散HMM。,一阶离散HMM是一个五元组： ，可以简写为 ，其中N是Markov链状态数;M是状态可能生成的观察值数; 表示初始状态概率向量，其中,A为状态转换概率分布矩阵，表示i状态向j状态转换的概率： ，其中:,B为观察值概率分布矩阵，表示在j状态输出观察值k的概率： ，其中:,隐马尔可夫模型（HMM）是一种在Markov链的基础上发展起来的统计信号模型，能够利用收集的训练样本进行自适应学习。,隐马尔科夫模型,HMM拓扑结构,左右型的HMM,全连通的HMM,含并行结构的HMM,含间隔跳转的HMM,3.HHM基本问题,HMM理论有3个基本问题：,（2）解码问题 给定一个HHM的模型 和观测序列 ，如何选择对应最佳的状态序列，使它在某种状态下最优（出现的概率最大），以较好地解释观测值,（1）评估问题 给定一个HHM的模型 和观测序列 ，如何高效的计算此模型产生的观测序列的概率,（3）学习问题（训练问题） 给定观测序列 ，如何调整模型参数 ，以使得观察序列出现的概率 最大化,3.1评估问题,解决HHM评估问题的典型算法有穷举搜索直接计算法、前向算法和后向算法：,一、穷举搜索直接计算,1、算法思想 列举长度为T的所有可能的状态序列 ，分别求解各个状态序列与观测序列的联合概率 ，最后求和得到,2、算法过程,（1）状态序列 出现的概率为：,（2）对于其中一种状态序列，观测序列的概率为： 依据贝叶斯公式：,（3）求和：,3、算法评价,由于每一时刻点所到达的状态有N种可能，所以总的不同的状态序列有 种。其中每一个状态序列需要2T-1次乘法运算。所以总的运算量为 次乘法运算（此外还需要 次加法运算）。,穷举算法的时间复杂度为 ，在求解 的过程中存在大量的重复计算，不适用于大的模型和较长的序列。,二、前向算法,1、算法思想,到达某网格节点的概率可以用前一时刻N个节点的概率表示出来。 前向算法通过已经保存了的子路径来计算新路径的概率。,HHM网状结构,(3)终止，在时刻T所有隐状态（对应观测值 ）的概率求和:,(2)递归，计算t+1时刻处于各隐状态（对应观测值为 ）的概率:,2、算法过程,定义到时刻t，部分观测序列为 ，状态 的前向概率为：,(1)初始化,计算t=1时处于各隐状态（对应观测值为 ）的概率:,t时刻前向概率的递归关系,3、算法评价,由以上算法过程可知，计算 总共需要 次乘法运算和 次加法运算。,前向算法的复杂度为 ，相比于穷举法计算，复杂度降低了几个数量级，减少了重复计算。,2后向算法,(1)初始化,最终时刻的所有状态的概率规定为：,定义从时刻t+1到时刻T，部分观测序列为 ，状态 的后向概率为:,1、算法思想 和前向算法基本一致，唯一的区别是选择的局部状态不同。,2、算法过程,(2)递归，计算t时刻处于各隐状态（对应观测值为 ）的概率:,(3)终止：,3、算法评价,t时刻后向概率的递归关系,由以上算法过程可知，计算 总共需要 次 乘法运算和 次加法运算。,后向算法的复杂度与前向算法相等，都是 。,3.2解码问题,1、算法思想,解答解码问题，即寻求对于给定观测序列的最优状态序列。有好几种标准可用于定义最优状态序列。比如，其中一个可能的优化标准是分别选择每个时刻各自最可能的状态。 但是每个时刻最可能的状态的叠加不一定能得到最可能的状态序列。可能这种得到的最优序列根本是“不合法”的。这种算法仅简单地考虑了每一个时刻点各自最可能的状态，而没有考虑到状态序列发生的概率。,定义优化标准为：寻求单一最佳状态序列，以最大化 ，运用贝叶斯原理，也即最大化,对于上述问题的一个可行的解决方案就是修改优化标准。于是提出了解决HMM解码问题的一个典型算法 Viterbi算法。,(3)终结：,(4)状态序列路径回溯：,(1)初始化：,(2)递归：,2、算法过程,定义 为时刻t系统沿单一路径的最高得分，它解释了前t个观测符号，并结束于 ：,同时，定义一个参数数组 ，记录目标状态序列的每个时刻t和状态,在实现上，Viterbi算法和前向算法十分相似。最主要的区别在于在Viterbi算法中递归时对以前的状态取最大值，而在前向算法中则对以前的状态取加和。,3、算法评价,维特比算法的时间复杂度也是O(N2T),维特比算法的时间复杂度也是 。,3.3学习问题,解决HMM学习问题的常用算法有前向-后向算法（Baum-Welch算法）：,第三个问题用来解答如何调整一个给定HMM的参数使得在某种准则下，该HMM最大化观测序列的概率，这也是三个问题中难度最大的问题。目前还没有方法可解析地求解模型的参数使得能最大化观测序列的概率。事实上，对于任何一个用作训练用的有限长的观测序列，还没有一个全局最优的模型参数估计的方法。,1、算法思想,BW算法运用了机器学习中的梯度下降的思想。首先对于HMM的参数 进行一个初始的估计（很可能是错误的），然后通过训练评估参数 的有效性并减少它们所引起的错误来更新 ，使得和给定的训练数据的误差变小。,定义 为给定训练序列O和模型 时，时刻t时Markov链处于状态 和时刻t+1时状态为 的概率，即,2、算法过程,网格计算关系图,对模型参数进行重估：,定义后验概率函数：,有：,于是，我们从某个模型 开始（可以预先或随机选择），可以推出如下新的模型：,利用上述公式进行反复的参数估计，直到 不再有明显提高。,3、算法评价,BW算法是一种反复爬山法，是EM(期望值最大化)算法的一个特例。最大化过程被称为在训练集上的训练。它只能找到局部最优解。为了使得到的是全局极大，必须要求 的初始值给得接近全局极大。这是应用本法的一项难点。,4.HHM应用背景,4.1自动文本分类,自动文本分类领域近年来已经产生了若干成熟的分类算法，如支持向量机(SVM)、K近邻(KNN)、朴素贝叶斯(NB)等算法，但这些算法主要基于概率统计模型，没有与文本自身的语法和语义建立起联系。,杨健, 汪海航. 基于隐马尔可夫模型的文本分类算法J. 计算机应用, 2010, 30(9):2348-2350.提出了将隐马尔可夫序列分析模型(HMM)用于自动文本分类的算法。,该模型通过观察文本的特征词组成及频率对不同类别文本进行分类，分别建立HMM分类器。HMM中的观察输出就是特征词的组成。HMM的状态转换，可以看做是从与该类别不是很相关的词组成的文档输出分布，向与该类别非常相关的词组成的文档输出分布转化的一种过程。因此，状态从起始点向终结点转化对应着类别相关词汇的强化。,HMM分类器训练,HMM分类器应用,HMM评估问题,4.2汉语词性标注,王敏, 郑家恒. 基于改进的隐马尔科夫模型的汉语词性标注J. 计算机应用, 2006, 26(s2):197-198.介绍了一种改进的HMM，更能体现词语的上下文依赖关系。,词性标注的任务是计算机通过学习自动地标注出有歧义的词的词性。现有的词性标注所采用的语言模型主要可以分为基于规则的方法和基于统计的方法。基于规则的方法适应性较差，并且非统计模型的本质使它通常作为一个独立的标注器，而很难被用作更大概率模型的组件部分。,传统的HMM只考虑到了上文对当前词的依赖关系，没有考虑到该词后面即下文与该词的依赖关系。,词性标注问题可描述为HMM解码问题，即在给定观察序列（词序列）的条件下搜索最佳的隐马尔科夫状态序列（词性序列）的问题。,传统HMM与改进HMM的测试结果比较,4.3汉语自动分词,李家福, 张亚非. 一种基于概率模型的分词系统J. 系统仿真学报, 2002, 14(5):544-546.提出了一种基于生语料库（语料库未作任何切分）的算法，基于词的出现概率，根据极大似然原则进行分词。,词是自然语言处理系统中重要的知识载体与基本操作单元。在书面汉语中词与词之间没有明显的切分标志。,给定词的出现概率，根据极大似然原则（MLP），一个句子分成词 ，须使 最大。本模型可以看成一个零阶HHM。,HMM模型的训练,EM算法：,分词算法性能比较,4.4文本信息抽取,在一阶隐马尔可夫模型中，假设状态转移概率和观察值输出概率仅依赖于模型当前的状态，一定程度降低了信息抽取的精确度。而二阶隐马尔可夫模型合理地考虑了概率和模型历史状态的关联性，对错误信息有更强的识别能力。,信息抽取是指从文本中抽取特定的事实信息，被抽取出来的信息以结构化的形式描述，直接存入数据库中，供用户查询以及进一步分析利用。,周顺先, 林亚平, 王耀南,等. 基于二阶隐马尔可夫模型的文本信息抽取J. 电子学报, 2007, 35(11):2226-2231.提出了一种基于二阶HMM的文本信息抽取算法。,假设1： 在HMM中，隐藏的状态序列是一个二阶Markov链，即在t+1时刻的状态的转移概率不仅依赖于t时刻的状态，同时依赖于t-1时刻的状态。,二阶HHM,假设2： 在t时刻释放观察值的输出概率，不仅依赖于系统当前所处的状态，同时依赖于系统前一时刻所处的状态。,与一阶HMM不同的五元组不同，二阶HMM定义为一个七元组：,基于HMM文本信息抽取算法框图,一阶HMM和二阶HMM的精确度比较,其他应用领域,THANKS !,
