Download presentation
Presentation is loading. Please wait.
1
隐马尔可夫模型 Hidden Markov model
徐从富 浙江大学人工智能研究所 2003年10月第一稿 2005年9月修改补充 Modified by siuleung
2
目 录 HMM的由来 马尔可夫性和马尔可夫链 HMM实例 HMM的三个基本算法 主要参考文献
3
HMM的由来 1870年，俄国有机化学家Vladimir V. Markovnikov第一次提出马尔科夫模型 马尔可夫模型 马尔可夫链
隐马尔可夫模型
4
马尔可夫性 如果一个过程的“将来”仅依赖“现在”而不依赖“过去”，则此过程具有马尔可夫性,或称此过程为马尔可夫过程
X(t+1) = f( X(t) )
5
马尔科夫链 时间和状态都离散的马尔科夫过程称为马尔科夫链 记作{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的转移概率。
6
转移概率矩阵 晴天 阴天 下雨 晴天 阴天 下雨 晴天 阴天 下雨
7
转移概率矩阵(续) 由于链在时刻m从任何一个状态ai出发，到另一时刻m+n，必然转移到a1，a2…，诸状态中的某一个，所以有
当Pij(m,m+n)与m无关时，称马尔科夫链为齐次马尔科夫链，通常说的马尔科夫链都是指齐次马尔科夫链。
8
HMM实例 Observed Ball Sequence Urn 3 Urn 1 Urn 2 Veil
9
HMM实例——描述 设有N个缸，每个缸中装有很多彩球，球的颜色由一组概率分布描述。实验进行方式如下
根据缸中球颜色的概率分布，随机选择一个球，记球的颜色为O1，并把球放回缸中 根据描述缸的转移的概率分布，随机选择下一口缸，重复以上步骤。 最后得到一个描述球的颜色的序列O1,O2,…，称为观察值序列O。
10
HMM实例——约束 不能被直接观察缸间的转移 从缸中所选取的球的颜色和缸并不是 一一对应的 每次选取哪个缸由一组转移概率决定
在上述实验中，有几个要点需要注意： 不能被直接观察缸间的转移 从缸中所选取的球的颜色和缸并不是 一一对应的 每次选取哪个缸由一组转移概率决定
11
HMM概念 HMM的状态是不确定或不可见的，只有通过观测序列的随机过程才能表现出来
观察到的事件与状态并不是一一对应，而是通过一组概率分布相联系 HMM是一个双重随机过程，两个组成部分： 马尔可夫链：描述状态的转移，用转移概率描述。 一般随机过程：描述状态与观察序列间的关系， 用观察值概率描述。
12
HMM组成 Markov链 （, A） 随机过程 （B） HMM的组成示意图 状态序列 观察值序列 q1, q2, ..., qT
o1, o2, ..., oT HMM的组成示意图
13
HMM的基本要素 用模型五元组 ＝（ N, M, π ，A，B）用来描述HMM，或简写为 =(π ，A，B) 参数 含义 实例 N 状态数目
缸的数目 M 每个状态可能的观察值数目 彩球颜色数目 A 与时间无关的状态转移概率矩阵 在选定某个缸的情况下，选择另一个缸的概率 B 给定状态下，观察值概率分布 每个缸中的颜色分布 p 初始状态空间的概率分布 初始时选择某口缸的概率
14
HMM可解决的问题 问题1：给定观察序列O=O1,O2,…OT,以及模型 , 如何计算P(O|λ)？
问题2：给定观察序列O=O1,O2,…OT以及模型λ,如何选择一个对应的状态序列 S = q1,q2,…qT，使得S能够最为合理的解释观察序列O？ 问题3：如何调整模型参数 , 使得P(O|λ)最大？
15
解决问题1 基础方法 给定一个固定的状态序列S=(q1，q2，q3…) 表示在qt状态下观测到Ot的概率
N=5, M=100, => 计算量10^72
16
解决问题1 前向法 动态规划 定义前向变量 初始化： 递归： 终结：
17
前向法示意图 N=5, M=100, => 计算量3000 1 ... t t+1 ... qN atN . qi qj ati
aNj aij a1j at1 t t N=5, M=100, => 计算量3000
18
解决问题1 后向法 与前向法类似 定义后向变量 初始化： 递归： 终结：
19
Viterbi算法 目的：给定观察序列O以及模型λ,如何选择一个对应的状态序列S ，使得S能够最为合理的解释观察序列O？
N和T分别为状态个数和序列长度 定义： 我们所要找的，就是T时刻最大的 所代表的那个状态序列
20
Viterbi算法(续) 初始化： 递归： 终结： 求S序列：
21
Baum-Welch算法(模型训练算法)
目的：给定观察值序列O，通过计算确定一个模型l ， 使得P(O| l)最大。 算法步骤： 1. 初始模型（待训练模型） l0, 2. 基于l0 以及观察值序列O，训练新模型 l； 3. 如果 log P(X|l) - log(P(X|l0) < Delta，说明训练已经达到预期效果， 算法结束。 4. 否则，令l0 ＝ l ，继续第2步工作
22
Baum-Welch算法(续) 定义：
23
Baum-Welch算法(续2) 参数估计：
24
几种典型形状的马尔科夫链 a. A矩阵没有零值的Markov链 b. A矩阵有零值的Markov链 c./d. 左－右形式的Markov链
25
HMM的应用领域 语音识别 机器视觉 人脸检测 机器人足球 图像处理 图像去噪 图像识别 生物医学分析 DNA/蛋白质序列分析
26
主要参考文献 1. Lawrence R. Rabiner, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition. Proceedings 1989. ftp:// /课件/徐从富_AI/补充材料/隐Markov模型.pdf 或ftp:// /课件/徐从富_AI/补充材料/隐Markov模型.pdf
27
欢迎批评指正， 谢谢！
Similar presentations
