隐马尔可夫模型 Hidden Markov model

Presentation on theme: "隐马尔可夫模型 Hidden Markov model"— Presentation transcript:

1 隐马尔可夫模型 Hidden Markov model
周潇 2019/5/31 知识管理与数据分析实验室

2 内容框架 隐马尔科夫模型的由来 1 2 隐马尔科夫模型的基本理论及实例 3 隐马尔科夫模型的三个基本算法 4 隐马尔科夫模型的应用
2019/5/31 知识管理与数据分析实验室

3 隐马尔可夫模型（HMM）的由来 1870年，俄国有机化学家Vladimir V. Markovnikov第一次提出Markov Model（MM） Baum 及他的同事于60年代末70年代初提出隐马尔可夫理论，并用于语音识别 80年代末90年代初HMM被用于计算生物学 目前已成功用于人脸识别、手写识别领域 2019/5/31 知识管理与数据分析实验室

4 内容框架 隐马尔科夫模型的由来 1 2 隐马尔科夫模型的基本理论及实例 3 隐马尔科夫模型的三个基本算法 4 隐马尔科夫模型的应用
2019/5/31 知识管理与数据分析实验室

5 隐马尔可夫模型的基本理论 马尔可夫 过程 马尔可夫性 马尔可夫链 隐马尔可夫模型 2019/5/31 知识管理与数据分析实验室

6 马尔可夫性 如果一个过程的“将来”仅依赖“现在”而不依赖“过去”，则此过程具有马尔可夫性,或称此过程为马尔可夫过程。用公式表示：X(t+1) = f( X(t) ) 2019/5/31 知识管理与数据分析实验室

7 马尔科夫过程 过程或系统在时刻T0所处状态为已知的条件下，过程在时刻T>T0所处状态的条件分布与过程在时刻t0之前所处的状态无关。
通俗的说，就是在已经知道过程“现在”的条件下，其“将来”不依赖于“过去”。 2019/5/31 知识管理与数据分析实验室

8 马尔科夫链 时间和状态都离散的马尔科夫过程称为马尔科夫链 记作{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的转移概率。 2019/5/31 知识管理与数据分析实验室

9 隐马尔科夫模型 HMM是一个双重随机过程，两个组成部分： 马尔可夫链：描述状态的转移，用转移概率描述。
一般随机过程：描述状态与观察序列间的关系， 用观察值概率描述。 2019/5/31 知识管理与数据分析实验室

10 隐马尔科夫模型的组成 Markov链 （, A） 随机过程 （B） 状态序列 观察值序列 q1, q2, ..., qT
o1, o2, ..., oT 2019/5/31 知识管理与数据分析实验室

11 一个实验——球缸模型 设有N个缸，每个缸中装有很多彩球，球的颜色由一组概率分布描述。实验进行方式如下
根据某个初始概率分布，随机选择N个缸中的一个，例如第I个缸。 根据这个缸中彩球颜色的概率分布，随机选择一个球，记下球的颜色，记为O1，再把球放回缸中。 根据描述缸的转移的概率分布，随机选择下一口缸，重复步骤1。 最后我们可以得到一个描述球的颜色的序列O1,O2,…，称为观察值序列。 2019/5/31 知识管理与数据分析实验室

12 球缸模型示意图 观测到的球序列 缸 3 缸 1 缸 2 通道 2019/5/31 知识管理与数据分析实验室

13 关于球缸模型的说明 缸之间的转移不能被直接观察到 从缸中所选取的球的颜色和缸并不是 一一对应的 每次选取哪个缸由一组转移概率决定
2019/5/31 知识管理与数据分析实验室

14 HMM中状态与观测的对应关系示意图 2019/5/31 知识管理与数据分析实验室

15 HMM的基本要素 用模型五元组 ＝（ N, M, π ，A，B）用来描述HMM，或简写为 =(π ，A，B) 2019/5/31
知识管理与数据分析实验室

16 HMM可解决的问题 评估问题 解码问题 学习问题
给定观测序列 O=O1O2O3…Ot和模型参数λ=(A,B,π)，怎样寻找某种意义上最优的隐状态序列。此问题主要用Viterbi算法。 给定观测序列 O=O1O2O3…Ot和模型参数λ=(A,B,π)，怎样有效计算某一观测序列的概率。此问题主要用向前向后算法。 怎样调整模型参数λ=(A,B,π)，使观测序列 O=O1O2O3…Ot的概率最大。此问题主要用Baum-Welch算法。 评估问题 解码问题 学习问题 2019/5/31 知识管理与数据分析实验室

17 内容框架 隐马尔科夫模型的由来 1 2 隐马尔科夫模型的基本理论及实例 3 隐马尔科夫模型的三个基本算法 4 隐马尔科夫模型的应用
2019/5/31 知识管理与数据分析实验室

18 向前算法及向后算法 向前算法及向后算法主要解决评估问题，即用来计算给定一个观测值序列O以及一个模型λ时，由模型λ产生出观测值序列O的概率 。
2019/5/31 知识管理与数据分析实验室

19 向前算法 最后根据公式 求出概率。 向前变量 它的含义是，给定模型λ ，时刻t。处在状态i，并且部分观察序列为的概率 显然
当 已知时根据 ， 迭代计算 最后根据公式 求出概率。 2019/5/31 知识管理与数据分析实验室

20 计算实例：抛掷硬币问题，计算观察到(H H T)的概率
2019/5/31 知识管理与数据分析实验室

21 向后算法 向后变量 含义是，给定模型 λ，时刻t。处在状态i，并且部分观察序列为 的概率。 当已知 ， ，则根据公式 迭代计算。
当已知 ， ，则根据公式 迭代计算。 最后根据公式 求出概率 2019/5/31 知识管理与数据分析实验室

22 计算实例：抛掷硬币问题，计算观察到(H H T)的概率
2019/5/31 知识管理与数据分析实验室

23 韦特比算法(Viterbi Algorithm)
对于解码问题，我们常用为比特算法来解决问题，即用来解决给定观测序列 O=O1O2O3…Ot和模型参数λ=(A,B,π)，寻找某种意义上最优的隐状态序列问题。 在介绍算法前，首先明确两个变量的意义 韦特比变量 变量的含义是，给定模型λ，时刻t处在状态i，观察到的 最佳状态转换序列为的 概率。 记录路径的数组 该数组记录在时刻t到达状态i的最佳状态转换序列t-1时刻的最佳状态。 2019/5/31 知识管理与数据分析实验室

24 韦特比算法（续） 韦特比算法主要有四个步骤： 首先，初始化变量，使得： 第二步，迭代计算 第三步，终止： 第四步，求解最佳路径：
2019/5/31 知识管理与数据分析实验室

25 计算实例：抛掷硬币问题，观察到(H H T)，寻找产生该观察序列的最佳路径以及最佳路径的概率
最佳状态转换序列为1 1 1 2019/5/31 知识管理与数据分析实验室

26 Baum-Welch算法 隐马尔科夫模型的第三个问题是如何根据观察序列O =( o1 o2 o3 …oT )求得模型参数或调整模型参数，即如何确定一组模型参数使得P (O|λ )最大的问题。在模型(λ)未知的情况下，如果给定观察序列的同时，也给定了状态转换序列，此时可以通过有指导的学习方法学习模型参数。常用算法：Baum-Welch算法。 首先，定义变量 它表示在给定模型以及观察序列的情况下，t时刻处在状态i的概率。用公式表示： 观察序列O中，从状态i出发的转换的期望概率为 观察序列O中，从状态i到状态j的转换的期望概率 隐马尔科夫模型的第三个问题是如何根据观察序列O =( o1 o2 o3 …oT )求得模型参数或调整模型参数，即如何确定一组模型参数使得P (O|λ )最大的问题。在模型(λ)未知的情况下，如果给定观察序列的同时，也给定了状态转换序列，此时可以通过有指导的学习方法学习模型参数。常用算法：Baum-Welch算法。 首先，定义变量 它表示在给定模型以及观察序列的情况下，t时刻处在状态i的概率。用公式表示： 观察序列O中，从状态i出发的转换的期望概率为 观察序列O中，从状态i到状态j的转换的期望概率 2019/5/31 知识管理与数据分析实验室

27 Baum-Welch算法（续） 关于,A,B，给出一种合理的估计方法： 在t=1时处在状态i的概率：
从状态i到状态j的转换的期望概率除以从状态i出发的转换的期望概率： 其中分子表示在状态j观察到的期望概率，并且当 时， ；当 时， ；分母表示处在状态j的期望概率 根据以上结论可进行模型估算，反复迭代，直至参数收敛。 2019/5/31 知识管理与数据分析实验室

28 内容框架 隐马尔科夫模型的由来 1 2 隐马尔科夫模型的基本理论及实例 3 隐马尔科夫模型的三个基本算法 4 隐马尔科夫模型的应用
2019/5/31 知识管理与数据分析实验室

29 隐马尔科夫模型的应用 隐马尔科夫模型 应用于 语音识别 书面语理解 基因预测 人脸识别 2019/5/31 知识管理与数据分析实验室

30 语音识别 隐马尔可夫模型在语音识别中的应用20 世纪80 年代, 美国CMU 大学的J. K. Baker等人将HMM应用到语音识别领域, 在语音识别中获得了极大的成功, 成为语音识别的主要方法。 目前应用最为成功的语音识别系统大多是基于隐马尔可夫模型构造的.如CMU 的Kai2Fu lee 等研制的SPH INX 连续语音识别系统, 对997 个词在有无文法限制的条件下,识别率分别为96% 和82%. IBM 构造的Tango ra2000 词语音识别系统得到95% 的识别率。用HMM 进行汉语声母、韵母、单音节及连续语音识别, 都得到了很好的性能。 2019/5/31 知识管理与数据分析实验室

31 书面语理解上的应用 在词性标注方面, 采用隐马尔可夫模型的标注方法具有很强的健壮性, 是当前主流的标注方法。
词性标注就是在给定的句子中判定每个词的语法范畴, 确定词性并加以标注的过程, 它发生在对文本执行分词处理之后, 是对切分所得的词进行分析、运算,确定词在上下文中合适的词类性质并加以标注的过程。 在隐马尔可夫模型下, 词性标注问题可以表述为:在给定观察值和模型参数的情况下, 求状态序列T=t1, t2, t3, ⋯tm, 使得这一状态序列可以“最好地解释”观察值序列W=w1, w2, w3, ⋯, wm。T°为最终的标注结果,即概率最大的词性序列。 2019/5/31 知识管理与数据分析实验室

32 生物学基因预测上的应用 隐马尔可夫模型(HMM)研究是当前机器学习的热点领域,该模型在80年代末90年代初该模型就被应用于计算生物学。隐马尔可夫模型能很好地模拟生物的进化过程,其在生命科学特别是生物信息领域很受欢迎,特别是在生物信息检测领域,已用于基因预测、蛋白质家族的构建方面。

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