隐马尔科夫模型.pptx

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