Hidden_Markov_Model_及其应用

Hidden_Markov_Model 隐马模型的原理应用

Hidden Markov Model

Hidden_Markov_Model 隐马模型的原理应用

主要内容 HMM介绍 介绍 HMM原理 原理 HMM的构建 的构建 HMM的应用： 的应用： 的应用 Pfam and TMHMM

Hidden_Markov_Model 隐马模型的原理应用

生物学中常用的统计模型 Structured probability models – Markov models – Hidden markov models ARTIFICIAL NEURAL NETWORK,简称 A.N.N

Hidden_Markov_Model 隐马模型的原理应用

Introduction Hidden Markov Models (HMMs) 最早是 在上个世纪60年代末70年代初提出来的。 进入80年代以后，逐渐被利用在各个领域。

Hidden_Markov_Model 隐马模型的原理应用

Introduction Hidden Markov Models 作为一种强有力 的统计学模型，主要被应用在一些连续 行的或时间延续性的事件建模上。主要 的应用领域： 语音识别系统。 生物学中的DNA/protein序列的分析 机器人的控制。 文本文件的信息提取。

Hidden_Markov_Model 隐马模型的原理应用

HMM的优点 的优点 1,它的数学结构非常丰富，适用于各个 领域的研究。 2,在很多领域中，已经证明它的结果和 实际符合的相当好。

Hidden_Markov_Model 隐马模型的原理应用

Probability Review

Hidden_Markov_Model 隐马模型的原理应用

独立事件概率 设想我們再作一连串的实验，而每次实验所 设想我們再作一连串的实验， 。(可 可能发生的結果定为 E1,E2,… En,…。(可 。( 能是有限也可能是無限)。 )。每一個結果 能是有限也可能是無限)。每一個結果 Ek, 我們若能給定一個出現的可能性 pk(即概 ),则对某一特定样本之序列 率),则对某一特定样本之序列 Ej1 Ej2 … Ejn,我們知道它出現的概率是 p(Ej1 Ej2 … Ejn) =pj1 … Pjn。

Hidden_Markov_Model 隐马模型的原理应用

马可夫链 一般及常用的统计中，彼此相互「独立」大 一般及常用的统计中，彼此相互「独立」 概是最有用的一個观念。用简单的术语來说， 概是最有用的一個观念。用简单的术语來说， 互相「独立」就是彼此毫不相干， 互相「独立」就是彼此毫不相干，一點牵涉 都沒有。 都沒有。 但是实际生活中很多事件是相互关联的 [不是互相獨立」也就是說互相关联的意思， 不是互相獨立」 不是互相獨立 也就是說互相关联的意思， 但是要怎样相关呢？ 但是要怎样相关呢？如何在相关中作一些简 单的分类呢？馬可夫连就是要描述在「相关」 单的分类呢？馬可夫连就是要描述在「相关」 這个概念中最简单的一种。但即使如此，有 這个概念中最简单的一种。但即使如此， 关马可夫链的理论已经相当丰富了。 关马可夫链的理论已经相当丰富了。在概率 理論中，它几乎占了绝大的部分。 理論中，它几乎占了绝大的部分。

Hidden_Markov_Model 隐马模型的原理应用

马可夫链 在马可夫鏈中我們考虑最简单的「相关」性。在在 在马可夫鏈中我們考虑最简单的「相关」 这种情况下， 这种情况下，我们不能给任一個事件 Ej 一個概率 pj 但我们给一对事件 (Ej,Ek) 一個概率 pjk,这个时候 pjk 的解释是一种条件概率，就是假设在某次实验

中 的解释是一种条件概率， Ej 已经出现，而在下一次实验中 Ek 出現的概率。 已经出现， 出現的概率。 之外， 除了 pjk 之外，我們还需要知道第一次实验中 Ej 出 有了这些资料后， 現的機率 aj。有了这些资料后，一個样本序列 Ej0 Ej1 … Ejn(也就是说第零次实验结果是 j0,第一次 也就是说第零次实验结果是E 一次是 Ej1……第 n 次实验是 Ejn)的概率就很清楚 第 的是 P(Ej0,Ej1,Ejn) =aj pj0j1 pj1j2 … pjn-1jn。

Hidden_Markov_Model 隐马模型的原理应用

隐马可夫模型 但是在大多数情况下我们所观察到的值并不 是序列本身的元素。 是序列本身的元素。 即观察值不等于状态值。 即观察值不等于状态值。 故我们隐入马可夫模型。 故我们隐入马可夫模型。

Hidden_Markov_Model 隐马模型的原理应用

定义

是一个五元组： 一个隐马尔可夫模型 (HMM) 是一个五元组： ( X , O, A, B, π ) 其中： 其中： X = {q1,...qN}:状态的有限集合 O = {v1,...,vM}:观察值的有限集合 A = {aij},aij = p(Xt+1 = qj |Xt = qi):转移概率 B = {bik},bik = p(Ot = vk | Xt = qi):输出概率 π = {πi}, πi = p(X1 = qi):初始状态分布

Hidden_Markov_Model 隐马模型的原理应用

假设对于一个随机事件，有一个观察值序列： 对于一个随机事件，有一个观察值序列：O1,...,OT 该事件隐含着一个状态序列： 该事件隐含着一个状态序列：X1,...,XT 假设1:马尔可夫假设(状态构成一阶马尔可夫链) 假设 ：马尔可夫假设(状态构成一阶马尔可夫链) p(Xi|Xi-1…X1) = p(Xi|Xi-1) 假设2:不动性假设(状态与具体时间无关) 假设 ：不动性假设(状态与具体时间无关) p(Xi+1|Xi) = p(Xj+1|Xj),对任意 成立 ，对任意i,j成立 假设3:输出独立性假设(输出仅与当前状态有关) 假设 ：输出独立性假设(输出仅与当前状态有关) p(O1,...,OT | X1,...,XT) = Π p(Ot | Xt)

Hidden_Markov_Model 隐马模型的原理应用

马可夫链 Vs 隐马可夫模型 Markov chains have entirely observable states. However a “Hidden Markov Model” is a model of a Markov Source which admits an element each time slot depending upon the state. The states are not directly observed

Hidden_Markov_Model 隐马模型的原理应用

问题

为给定HMM的参数， 的参数， 令 λ = {A,B,π} 为给定 的参数 为观察值序列， 令 σ = O1,...,OT 为观察值序列， 隐马尔可夫模型( 隐马尔可夫模型(HMM)的三个基本问题： )的三个基本问题： 1. 评估问题：对于给定模型，求某个观察值序列 评估问题：对于给定模型， 的概率p( 的概率 σ|λ) ; 2. 解码问题：对于给定模型和观察值序列，求可 解码问题：对于给定模型和观察值序列， 能性最大的状态序列； 能性最大的状态序列； 3. 学习问题：对于给定的一个观察值序列，调整 学习问题：对于给定的一个观察值序列， 参数λ,使得观察值出现的概率p( 最大。 参数 ，使得观察值出现的概率 σ|λ)最大。 最大

Hidden_Markov_Model 隐马模型的原理应用

3种主

要算法 种主要算法 评估问题：向前算法 评估问题：– 定义向前变量 – 采用动态规划算法，复杂度O(N2T) 采用动态规划算法，复杂度

解码问题：韦特比(Viterbi)算法 解码问题：韦特比( )– 采用动态规划算法，复杂度O(N2T) 采用动态规划算法，复杂度

学习问题：向前向后算法 学习问题：EM算法的一个特例，带隐变量的最大似然估计 算法的一个特例， 算法的一个特例