隐马尔可夫模型HiddenMarkovmodel.ppt

知知知知识识管理与数据分析管理与数据分析管理与数据分析管理与数据分析实验实验室室室室数据挖掘技数据挖掘技数据挖掘技数据挖掘技术专题术专题隐马尔可夫模型隐马尔可夫模型Hidden Markov modelHidden Markov model周潇周潇2024/9/161知识管理与数据分析实验室知识管理与数据分析实验室内容框架内容框架2024/9/16知识管理与数据分析实验室知识管理与数据分析实验室2隐马尔科夫模型的由来隐马尔科夫模型的基本理论及实例隐马尔科夫模型的三个基本算法隐马尔科夫模型的应用4123隐马尔可夫模型（隐马尔可夫模型（HMMHMM）的由来）的由来 n1870年，俄国有机化学家Vladimir V. Markovnikov第一次提出Markov Model（MM）nBaum 及他的同事于60年代末70年代初提出隐马尔可夫理论，并用于语音识别n80年代末90年代初HMM被用于计算生物学n目前已成功用于人脸识别、手写识别领域2024/9/16知识管理与数据分析实验室知识管理与数据分析实验室3内容框架内容框架2024/9/16知识管理与数据分析实验室知识管理与数据分析实验室4隐马尔科夫模型的由来隐马尔科夫模型的基本理论及实例隐马尔科夫模型的三个基本算法隐马尔科夫模型的应用41232024/9/16知识管理与数据分析实验室知识管理与数据分析实验室5隐马尔可夫模型的基本理论隐马尔可夫模型的基本理论马尔可夫性马尔可夫过程马尔可夫链隐马尔可夫模型马尔可夫性n如果一个过程的“将来”仅依赖“现在”而不依赖“过去”，则此过程具有马尔可夫性马尔可夫性,或称此过程为马尔可夫过程。

用公式表示：马尔可夫过程用公式表示：X(t+1) = f( X(t) )2024/9/16知识管理与数据分析实验室知识管理与数据分析实验室6马尔科夫过程马尔科夫过程n过程或系统在时刻T0所处状态为已知的条件下，过程在时刻T>T0所处状态的条件分布与过程在时刻t0之前所处的状态无关n通俗的说，就是在已经知道过程“现在”的条件下，其“将来”不依赖于“过去”2024/9/16知识管理与数据分析实验室知识管理与数据分析实验室7马尔科夫链•时时间间和状状态态都离散的马尔科夫过程称为马尔科夫链•记作{Xn = X(n), n = 0,1,2,…}–在时间集T1 = {0,1,2,…}上对离散状态的过程相继观察的结果•链的状态空间记做I = {a1, a2,…}, ai∈R. •条件概率Pij ( m ,m+n)=P{Xm+n = aj|Xm = ai} 为马氏链在时刻m处于状态ai条件下，在时刻m+n转移到状态aj的转移概率2024/9/16知识管理与数据分析实验室知识管理与数据分析实验室8隐马尔科夫模型隐马尔科夫模型•HMM是一个双重随机过程，两个组成部分：– 马尔可夫链马尔可夫链：描述状态的转移，用转移概率描述。

– 一般随机过程一般随机过程：描述状态与观察序列间的关系， 用观察值概率描述2024/9/16知识管理与数据分析实验室知识管理与数据分析实验室9隐马尔科夫模型的组成隐马尔科夫模型的组成2024/9/16知识管理与数据分析实验室知识管理与数据分析实验室10MarkovMarkov链链（（ , A, A））随机过程随机过程（（B B））状态序列状态序列观察值序列观察值序列q1, q2, ..., qTo1, o2, ..., oT一个实验一个实验————球缸模型球缸模型n设有N个缸，每个缸中装有很多彩球，球的颜色由一组概率分布描述实验进行方式如下n根据某个初始概率分布，随机选择N个缸中的一个，例如第I个缸n根据这个缸中彩球颜色的概率分布，随机选择一个球，记下球的颜色，记为O1，再把球放回缸中n根据描述缸的转移的概率分布，随机选择下一口缸，重复步骤1n最后我们可以得到一个描述球的颜色的序列O1,O2,…，称为观察值序列 2024/9/16知识管理与数据分析实验室知识管理与数据分析实验室11球缸模型示意图球缸模型示意图2024/9/16知识管理与数据分析实验室知识管理与数据分析实验室12观测到的球序列缸 3缸 1缸 2通道关于球缸模型的说明关于球缸模型的说明n缸之间的转移不能被直接观察到n从缸中所选取的球的颜色和缸并不是 一一对应的n每次选取哪个缸由一组转移概率决定2024/9/16知识管理与数据分析实验室知识管理与数据分析实验室13HMMHMM中状态与观测的对应关系示意图中状态与观测的对应关系示意图2024/9/16知识管理与数据分析实验室知识管理与数据分析实验室14HMM的基本要素2024/9/16知识管理与数据分析实验室知识管理与数据分析实验室15•用模型五元组 ＝（ N, M, π ，A，B）用来描述HMM，或简写为 =(π ，A，B)2024/9/16知识管理与数据分析实验室知识管理与数据分析实验室16HMM可解决的问题给定观测序列 O=O1O2O3…Ot和模型参数λ=(A,B,π)，怎样寻找某种意义上最优的隐状态序列。

此问题主要用Viterbi算法给定观测序列 O=O1O2O3…Ot和模型参数λ=(A,B,π)，怎样有效计算某一观测序列的概率此问题主要用向前向后算法怎样调整模型参数λ=(A,B,π)，使观测序列 O=O1O2O3…Ot的概率最大此问题主要用Baum-Welch算法评估问题解码问题学习问题内容框架内容框架2024/9/16知识管理与数据分析实验室知识管理与数据分析实验室17隐马尔科夫模型的由来隐马尔科夫模型的基本理论及实例隐马尔科夫模型的三个基本算法隐马尔科夫模型的应用4123向前算法及向后算法向前算法及向后算法n向前算法及向后算法主要解决评估问题，即用来计算给定一个观测值序列O以及一个模型λ时，由模型λ产生出观测值序列O的概率 2024/9/16知识管理与数据分析实验室知识管理与数据分析实验室18向前算法向前算法n向前变量 它的含义是，给定模型λ ，时刻t处在状态i，并且部分观察序列为的概率 显然 n当 已知时根据 ， 迭代计算n最后根据公式 求出概率。

2024/9/16知识管理与数据分析实验室知识管理与数据分析实验室19计算实例：抛掷硬币问题，计算观察到(H H T)的概率2024/9/16知识管理与数据分析实验室知识管理与数据分析实验室20向后算法n向后变量 含义是，给定模型 λ，时刻t处在状态i，并且部分观察序列为 的概率n当已知 ， ，则根据公式 迭代计算最后根据公式 求出概率2024/9/16知识管理与数据分析实验室知识管理与数据分析实验室21计算实例：抛掷硬币问题，计算观察到(H H T)的概率2024/9/16知识管理与数据分析实验室知识管理与数据分析实验室22韦特比算法韦特比算法(Viterbi Algorithm)(Viterbi Algorithm)n对于解码问题，我们常用为比特算法来解决问题，即用来解决给定观测序列 O=O1O2O3…Ot和模型参数λ=(A,B,π)，寻找某种意义上最优的隐状态序列问题。

n在介绍算法前，首先明确两个变量的意义u韦特比变量 变量的含义是，给定模型λ，时刻t处在状态i，观察到的 最佳状态转换序列为的 概率u记录路径的数组 该数组记录在时刻t到达状态i的最佳状态转换序列t-1时刻的最佳状态2024/9/16知识管理与数据分析实验室知识管理与数据分析实验室23韦特比算法（续）韦特比算法（续）n韦特比算法主要有四个步骤：u首先，初始化变量，使得：u第二步，迭代计算u第三步，终止：u第四步，求解最佳路径：2024/9/16知识管理与数据分析实验室知识管理与数据分析实验室24计算实例：抛掷硬币问题，观察到(H H T)，寻找产生该观察序列的最佳路径以及最佳路径的概率2024/9/16知识管理与数据分析实验室知识管理与数据分析实验室25最佳状态转换序列为1 1 1Baum-WelchBaum-Welch算法算法•隐马尔科夫模型的第三个问题是如何根据观察序列O =( o1 o2 o3 …oT )求得模型参数或调整模型参数，即如何确定一组模型参数使得P (O|λ )最大的问题。

在模型(λ)未知的情况下，如果给定观察序列的同时，也给定了状态转换序列，此时可以通过有指导的学习方法学习模型参数常用算法：Baum-Welch算法•首先，定义变量 它表示在给定模型以及观察序列的情况下，t时刻处在状态i的概率用公式表示： 观察序列O中，从状态i出发的转换的期望概率为 观察序列O中，从状态i到状态j的转换的期望概率2024/9/16知识管理与数据分析实验室知识管理与数据分析实验室26•隐马尔科夫模型的第三个问题是如何根据观察序列O =( o1 o2 o3 …oT )求得模型参数或调整模型参数，即如何确定一组模型参数使得P (O|λ )最大的问题在模型(λ)未知的情况下，如果给定观察序列的同时，也给定了状态转换序列，此时可以通过有指导的学习方法学习模型参数常用算法：Baum-Welch算法•首先，定义变量 它表示在给定模型以及观察序列的情况下，t时刻处在状态i的概率用公式表示： 观察序列O中，从状态i出发的转换的期望概率为 观察序列O中，从状态i到状态j的转换的期望概率Baum-WelchBaum-Welch算法（续）算法（续）n关于,A,B，给出一种合理的估计方法：u在t=1时处在状态i的概率： u从状态i到状态j的转换的期望概率除以从状态i出发的转换的期望概率：u 其中分子表示在状态j观察到的期望概率，并且当 时， ；当 时， ；分母表示处在状态j的期望概率u根据以上结论可进行模型估算，反复迭代，直至参数收敛。

2024/9/16知识管理与数据分析实验室知识管理与数据分析实验室27内容框架内容框架2024/9/16知识管理与数据分析实验室知识管理与数据分析实验室28隐马尔科夫模型的由来隐马尔科夫模型的基本理论及实例隐马尔科夫模型的三个基本算法隐马尔科夫模型的应用4123隐马尔科夫模型的应用2024/9/16知识管理与数据分析实验室知识管理与数据分析实验室29隐马尔科夫模型 应用于语音识别语音识别语音识别语音识别书面语理书面语理解解基因预测基因预测人脸识别人脸识别人脸识别人脸识别语音识别语音识别n隐马尔可夫模型在语音识别中的应用20 世纪80 年代, 美国CMU 大学的J. K. Baker等人将HMM应用到语音识别领域, 在语音识别中获得了极大的成功, 成为语音识别的主要方法n目前应用最为成功的语音识别系统大多是基于隐马尔可夫模型构造的.如CMU 的Kai2Fu lee 等研制的SPH INX 连续语音识别系统, 对997 个词在有无文法限制的条件下,识别率分别为96% 和82%. IBM 构造的Tango ra2000 词语音识别系统得到95% 的识别率用HMM 进行汉语声母、韵母、单音节及连续语音识别, 都得到了很好的性能。

2024/9/16知识管理与数据分析实验室知识管理与数据分析实验室30书面语理解上的应用书面语理解上的应用n在词性标注方面, 采用隐马尔可夫模型的标注方法具有很强的健壮性, 是当前主流的标注方法n词性标注就是在给定的句子中判定每个词的语法范畴, 确定词性并加以标注的过程, 它发生在对文本执行分词处理之后, 是对切分所得的词进行分析、运算,确定词在上下文中合适的词类性质并加以标注的过程n在隐马尔可夫模型下, 词性标注问题可以表述为:在给定观察值和模型参数的情况下, 求状态序列T=t1, t2, t3, ⋯tm, 使得这一状态序列可以“最好地解释”观察值序列W=w1, w2, w3, ⋯, wmT°为最终的标注结果,即概率最大的词性序列2024/9/16知识管理与数据分析实验室知识管理与数据分析实验室31生物学基因预测上的应用生物学基因预测上的应用•隐马尔可夫模型(HMM)研究是当前机器学习的热点领域,该模型在80年代末90年代初该模型就被应用于计算生物学隐马尔可夫模型能很好地模拟生物的进化过程,其在生命科学特别是生物信息领域很受欢迎,特别是在生物信息检测领域,已用于基因预测、蛋白质家族的构建方面。

结语结语•隐马尔可夫模型(HMM)研究是当前研究的热点领域,已经得到广泛的应用正如前面所说，隐马尔科夫模型在语音识别、书面语言理解、生物学基因预测上的都取得了重大的成就，目前，已成功用于人脸识别、手写识别等领域可以预测，在今后这一模型的还会得到更加广泛的应用。