隐马尔科夫模型ppt课件.ppt

隐马尔科夫模型（隐马尔科夫模型（HMMHMM））1;.Table of Contents1.马尔科夫模型2.隐马尔科夫模型3.HMM基本问题3.1 HMM评估问题3.2 HMM解码问题3.3 HMM学习问题4.HMM应用背景4.1 自动文本分类4.2 汉语词性标注4.3 汉语自动分词4.4 文本信息抽取4.5 其他应用领域21.马尔科夫模型马尔科夫模型马尔科夫(Markov)模型是由俄罗斯数学家Andrei A．Markov于20世纪初提出的一个统计模型有限状态的离散时间Markov链是一个长度为T的随机变量序列 ，  的取值范围是有限状态集有限状态集 假定它满足以下两个条件：（1）任一时刻的随机变量只依赖于前一时刻的随机变量任一时刻的随机变量只依赖于前一时刻的随机变量：（2）时间无关性（马尔科夫性）时间无关性（马尔科夫性）：则显然有：3以上随机过程可以称为可观测可观测MarkovMarkov模型模型，因为此过程的输出在每一个时间点是一个状态，并且每一个状态对应一个可观测事件。

上述模型称为一阶Markov模型如把条件（1）适当放松，任一时刻的随机变量只依赖于前两（三，…，k）个时刻的随机变量，则此模型为两（三，…，k）阶Markov模型MarkovMarkov模型模型42.隐马尔科夫模型隐马尔科夫模型一个HMM是不确定的、随机的有限状态自动机，由不可观测的状态转移过程状态转移过程(一个Markov链)和可观测的观察生成过程观察生成过程组成按观测值是离散还是连续的，HMM可分为离散型和连续型我们这里主要介绍离散HMM一阶离散HMM是一个五元组： ，可以简写为 ，其中N是Markov链状态数;M是状态可能生成的观察值数; 表示初始状态概率向量，其中 A为状态转换概率分布矩阵状态转换概率分布矩阵，表示i状态向j状态转换的概率： ，其中: B为观察值概率分布矩阵观察值概率分布矩阵，表示在j状态输出观察值k的概率： ，其中: 隐马尔可夫模型（HMM）是一种在Markov链的基础上发展起来的统计信号模型，能够利用收集的训练样本进行自适应学习。

5隐马尔科夫模型隐马尔科夫模型6HMM拓扑结构拓扑结构左右型的左右型的HMMHMM全连通的全连通的HMMHMM含并行结构的含并行结构的HMMHMM含间隔跳转的含间隔跳转的HMMHMM73.HHM基本问题基本问题HMM理论有3个基本问题：（（2 2）解码问题）解码问题给定一个HHM的模型 和观测序列 ，如何选择对应最佳的状态序列，使它在某种状态下最优（出现的概率最大），以较好地解释观测值（（1 1）评估问题）评估问题给定一个HHM的模型 和观测序列 ，如何高效的计算此模型产生的观测序列的概率（（3 3）学习问题（训练问题））学习问题（训练问题）给定观测序列 ，如何调整模型参数 ，以使得观察序列出现的概率 最大化83.1评估问题评估问题解决HHM评估问题的典型算法有穷举搜索直接计算法、前向算法和后向算法：一、穷举搜索直接计算一、穷举搜索直接计算1、算法思想列举长度为T的所有可能的状态序列                              ，分别求解各个状态序列与观测序列的联合概率                  ，最后求和得到2、算法过程（1）状态序列 出现的概率为：（2）对于其中一种状态序列，观测序列的概率为： 依据贝叶斯公式：9（3）求和：3、算法评价由于每一时刻点所到达的状态有N种可能，所以总的不同的状态序列有     种。

其中每一个状态序列需要2T-1次乘法运算所以总的运算量为                  次乘法运算（此外还需要           次加法运算）穷举算法的时间复杂度为                ，在求解               的过程中存在大量的重复计算，不适用不适用于大的模型和较长的序列于大的模型和较长的序列10二、前向算法二、前向算法1、算法思想到达某网格节点的概率可以用前一时刻N个节点的概率表示出来前向算法通过已经保存了的子路径来计算新路径的概率HHM网状结构网状结构11(3)终止，在时刻T所有隐状态（对应观测值 ）的概率求和:(2)递归，计算t+1时刻处于各隐状态（对应观测值为 ）的概率:2、算法过程定义到时刻t，部分观测序列为                              ，状态    的前向概率前向概率为：(1)初始化,计算t=1时处于各隐状态（对应观测值为 ）的概率:12t t时刻前向概率的递归关系时刻前向概率的递归关系3、算法评价由以上算法过程可知，计算 总共需要 次乘法运算和 次加法运算。

前向算法的复杂度为 ，相比于穷举法计算，复杂度降低了几个数量级降低了几个数量级，减少了重复计算132 2．后向算法．后向算法(1)初始化,最终时刻的所有状态的概率规定为：定义从时刻t+1到时刻T，部分观测序列为                           ，状态    的后向概率后向概率为:1、算法思想和前向算法基本一致，唯一的区别是选择的局部状态不同局部状态不同2、算法过程(2)递归，计算t时刻处于各隐状态（对应观测值为 ）的概率:14(3)终止：3、算法评价t t时刻后向概率的递归关系时刻后向概率的递归关系由以上算法过程可知，计算 总共需要 次 乘法运算和 次加法运算后向算法的复杂度与前向算法相等，都是 153.2解码问题解码问题1、算法思想解答解码问题，即寻求对于给定观测序列的最优状态序列最优状态序列有好几种标准可用于定义最优状态序列比如，其中一个可能的优化标准是分别选择每个时刻各自最可能的状态每个时刻各自最可能的状态但是每个时刻最可能的状态的叠加不一定能得到最可能的状态序列。

可能这种得到的最优序列根本是“不合法”的这种算法仅简单地考虑了每一个时刻点各自最可能的状态，而没有考虑到状态序列发生的概率定义优化标准为：寻求单一最佳状态序列，以最大化                  ，运用贝叶斯原理，也即最大化对于上述问题的一个可行的解决方案就是修改优化标准于是提出了解决HMM解码问题的一个典型算法— —Viterbi算法算法16(3)终结：(4)状态序列路径回溯路径回溯： (1)初始化：(2)递归： 2、算法过程定义        为时刻t系统沿单一路径的最高得分，它解释了前t个观测符号，并结束于    ：同时，定义一个参数数组          ，记录目标状态序列的每个时刻t和状态     17在实现上，Viterbi算法和前向算法十分相似最主要的区别在于在Viterbi算法中递归时对以前的状态取最大值，而在前向算法中则对以前的状态取加和3、算法评价 维特比算法的时间复杂度也是O(N2T) 维特比算法的时间复杂度也是               183.3学习问题学习问题解决HMM学习问题的常用算法有前向前向-后向算法（后向算法（Baum-Welch算法）算法）：第三个问题用来解答如何调整一个给定HMM的参数使得在某种准则下，该HMM最大化观测序列的概率，这也是三个问题中难度最大的问题。

目前还没有方法可解析地求解模型的参数使得能最大化观测序列的概率事实上，对于任何一个用作训练用的有限长的观测序列，还没有一个全局最优全局最优的模型参数估计的方法1、算法思想BW算法运用了机器学习中的梯度下降梯度下降的思想首先对于HMM 的参数    进行一个初始的估计（很可能是错误的），然后通过训练评估参数    的有效性并减少它们所引起的错误来更新   ，使得和给定的训练数据的误差变小19定义 为给定训练序列O和模型 时，时刻t时Markov链处于状态 和时刻t+1时状态为 的概率，即2、算法过程2021网格计算关系图网格计算关系图22对模型参数进行重估重估：定义后验概率函数后验概率函数：有：于是，我们从某个模型                      开始（可以预先或随机选择），可以推出如下新的模型：利用上述公式进行反复的参数估计，直到              不再有明显提高233、算法评价BW算法是一种反复爬山法，是EM(期望值最大化期望值最大化)算法算法的一个特例最大化过程被称为在训练集上的训练它只能找到局部最优解局部最优解为了使得到的是全局极大，必须要求   的初始值给得接近全局极大。

这是应用本法的一项难点244.HHM应用背景应用背景254.1自动文本分类自动文本分类自动文本分类领域近年来已经产生了若干成熟的分类算法，如支持向量机支持向量机(SVM)、、K近邻近邻(KNN)、朴素贝叶斯、朴素贝叶斯(NB)等算法，但这些算法主要基于概率统计模型概率统计模型，没有与文本自身的语法和语义建立起联系杨健杨健, 汪海航汪海航. 基于隐马尔可夫模型的文本分类算法基于隐马尔可夫模型的文本分类算法[J]. 计算机应用计算机应用, 2010, 30(9):2348-2350.提出了将隐马尔可夫序列分析模型(HMM)用于自动文本分类的算法该模型通过观察文本的特征词组成及频率特征词组成及频率对不同类别文本进行分类，分别建立HMM分类器HMM中的观察输出就是特征词的组成HMM的状态转换，可以看做是从与该类别不是很相关的词组成的文档输出分布，向与该类别非常相关的词组成的文档输出分布转化的一种过程因此，状态从起始点向终结点转化对应着类别相关词汇的强化26HMM分类器训练分类器训练Ø文本预处理，文档文本预处理，文档→词集词集Ø利用信息增益 (IG)进行特征词选择Ø利用χ2检验进行类特征词集抽取Ø分类器HMM模型参数学习Ø用不同类标号训练文档训练相应的 HMM 分类器27HMM分类器应用分类器应用HMMHMM评估问题评估问题Ø文本预处理文本预处理Ø将类特征集中的特征词升序排列Ø选取分类文档IG最大的k个特征词，组成输出观察序列Ø 利用前向或后向算法，计算类别的Ø依次计算每个类别的 ，选取概率最大的类别作为待分类文档的类标号284.2汉语词性标注汉语词性标注王敏王敏, 郑家恒郑家恒. 基于改进的隐马尔科夫模型的汉语词性标注基于改进的隐马尔科夫模型的汉语词性标注[J]. 计算机应用计算机应用, 2006, 26(s2):197-198.介绍了一种改进的HMM，更能体现词语的上下文依赖关系。

词性标注的任务是计算机通过学习自动地标注出有歧义的词的词性现有的词性标注所采用的语言模型主要可以分为基于规则基于规则的方法和基于统计基于统计的方法基于规则的方法适应性较差，并且非统计模型的本质使它通常作为一个独立的标注器，而很难被用作更大概率模型的组件部分传统的HMM只考虑到了上文对当前词的依赖关系，没有考虑到该词后面即下文与该词的依赖关系词性标注问题可描述为HMM解码问题解码问题，即在给定观察序列（词序列词序列）的条件下搜索最佳的隐马尔科夫状态序列（词性序列词性序列）的问题29传统传统HMMHMM与改进与改进HMMHMM的测试结果比较的测试结果比较304.3汉语自动分词汉语自动分词李家福李家福, 张亚非张亚非. 一种基于概率模型的分词系统一种基于概率模型的分词系统[J]. 系统仿真学报系统仿真学报, 2002, 14(5):544-546.提出了一种基于生语料库（语料库未作任何切分）的算法，基于词的出现概率，根据极大似然原极大似然原则则进行分词词是自然语言处理系统中重要的知识载体与基本操作单元在书面汉语中词与词之间没有明显的切分标志给定词的出现概率，根据极大似然原则（MLP），一个句子分成词                        ，须使              最大。

本模型可以看成一个零阶零阶HHM31HMM模型的训练模型的训练EM算法：算法：Ø随机给出词的概率的初始值随机给出词的概率的初始值Ø使用当前的词的概率值，对语料库中的句子进行分词处理Ø依据分词结果，重新计算词的概率Ø重复这个过程，进行多次迭代，直到概率值收敛32分词算法性能比较分词算法性能比较334.4文本信息抽取文本信息抽取在一阶隐马尔可夫模型中，假设状态转移概率和观察值输出概率仅依赖于模型当前的状态，一定程度降低了信息抽取的精确度而二阶隐马尔可夫模型合理地考虑了概率和模型历史状态的关联性，对错误信息有更强的识别能力信息抽取是指从文本中抽取特定的事实信息从文本中抽取特定的事实信息，被抽取出来的信息以结构化的形式描述，直接存入数据库中，供用户查询以及进一步分析利用周顺先周顺先, 林亚平林亚平, 王耀南王耀南,等等. 基于二阶隐马尔可夫模型的文本信息抽取基于二阶隐马尔可夫模型的文本信息抽取[J]. 电子学报电子学报, 2007, 35(11):2226-2231.提出了一种基于二阶二阶HMM的文本信息抽取算法34假设1：在HMM中，隐藏的状态序列是一个二阶二阶Markov链链，即在t+1时刻的状态的转移概率不仅依赖于t时刻的状态，同时依赖于t-1时刻的状态。

二阶二阶HHM 假设2：在t时刻释放观察值的输出概率，不仅依赖于系统当前所处的状态，同时依赖于系统前一时刻所处的状态 与一阶HMM不同的五元组不同，二阶HMM定义为一个七元组七元组：35Ø初始化初始化HMM：确定模型的状态数，初始化模型的参数：确定模型的状态数，初始化模型的参数Ø训练文本分组预处理Ø训练模型：以分组为单位，应用ML算法计算HMM参数Ø输出HMM模型Ø对输入的论文头部文本进行分组预处理Ø结合训练部分输出的HMM，利用Viterbi算法求最佳状态序列Ø输出最佳状态标记序列36基于基于HMMHMM文本信息抽取算法框图文本信息抽取算法框图37一阶一阶HMMHMM和二阶和二阶HMMHMM的精确度比较的精确度比较38其他应用领域其他应用领域Ø语音识别语音识别Ø语音合成技术Ø图像信号处理Ø视频信号处理Ø计算机辅助驾驶Ø人脸识别Ø生物医学信号处理Ø……….39THANKS !THANKS !40。