隐马尔可夫模型 Hidden Markov model 徐从富 浙江大学人工智能研究所 2003年10月第一稿 2005年9月修改补充 Modified by siuleung

目 录 HMM的由来 马尔可夫性和马尔可夫链 HMM实例 HMM的三个基本算法 主要参考文献

HMM的由来 1870年，俄国有机化学家Vladimir V. Markovnikov第一次提出马尔科夫模型 马尔可夫模型 马尔可夫链 隐马尔可夫模型

马尔可夫性 如果一个过程的“将来”仅依赖“现在”而不依赖“过去”，则此过程具有马尔可夫性,或称此过程为马尔可夫过程 X(t+1) = f( X(t) )

马尔科夫链 时间和状态都离散的马尔科夫过程称为马尔科夫链 记作{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的转移概率。

转移概率矩阵 晴天 阴天 下雨 晴天 阴天 下雨 晴天 0.50 0.25 0.25 阴天 0.375 0.25 0.375 下雨 0.25 0.125 0.625

转移概率矩阵(续) 由于链在时刻m从任何一个状态ai出发，到另一时刻m+n，必然转移到a1，a2…，诸状态中的某一个，所以有 当Pij(m,m+n)与m无关时，称马尔科夫链为齐次马尔科夫链，通常说的马尔科夫链都是指齐次马尔科夫链。

HMM实例 Observed Ball Sequence Urn 3 Urn 1 Urn 2 Veil

HMM实例——描述 设有N个缸，每个缸中装有很多彩球，球的颜色由一组概率分布描述。实验进行方式如下 根据缸中球颜色的概率分布，随机选择一个球，记球的颜色为O1，并把球放回缸中 根据描述缸的转移的概率分布，随机选择下一口缸，重复以上步骤。 最后得到一个描述球的颜色的序列O1,O2,…，称为观察值序列O。

HMM实例——约束 不能被直接观察缸间的转移 从缸中所选取的球的颜色和缸并不是 一一对应的 每次选取哪个缸由一组转移概率决定 在上述实验中，有几个要点需要注意： 不能被直接观察缸间的转移 从缸中所选取的球的颜色和缸并不是 一一对应的 每次选取哪个缸由一组转移概率决定

HMM概念 HMM的状态是不确定或不可见的，只有通过观测序列的随机过程才能表现出来 观察到的事件与状态并不是一一对应，而是通过一组概率分布相联系 HMM是一个双重随机过程，两个组成部分： 马尔可夫链：描述状态的转移，用转移概率描述。 一般随机过程：描述状态与观察序列间的关系， 用观察值概率描述。

HMM组成 Markov链 （, A） 随机过程 （B） HMM的组成示意图 状态序列 观察值序列 q1, q2, ..., qT o1, o2, ..., oT HMM的组成示意图

HMM的基本要素 用模型五元组 ＝（ N, M, π ，A，B）用来描述HMM，或简写为 =(π ，A，B) 参数 含义 实例 N 状态数目 缸的数目 M 每个状态可能的观察值数目 彩球颜色数目 A 与时间无关的状态转移概率矩阵 在选定某个缸的情况下，选择另一个缸的概率 B 给定状态下，观察值概率分布 每个缸中的颜色分布 p 初始状态空间的概率分布 初始时选择某口缸的概率

HMM可解决的问题 问题1：给定观察序列O=O1,O2,…OT,以及模型 , 如何计算P(O|λ)？ 问题2：给定观察序列O=O1,O2,…OT以及模型λ,如何选择一个对应的状态序列 S = q1,q2,…qT，使得S能够最为合理的解释观察序列O？ 问题3：如何调整模型参数 , 使得P(O|λ)最大？

解决问题1 基础方法 给定一个固定的状态序列S=(q1，q2，q3…) 表示在qt状态下观测到Ot的概率 N=5, M=100, => 计算量10^72

解决问题1 前向法 动态规划 定义前向变量 初始化： 递归： 终结：

前向法示意图 N=5, M=100, => 计算量3000 1 ... t t+1 ... qN atN . qi qj ati aNj aij a1j at1 1 ... t t+1 ... N=5, M=100, => 计算量3000

解决问题1 后向法 与前向法类似 定义后向变量 初始化： 递归： 终结：

Viterbi算法 目的：给定观察序列O以及模型λ,如何选择一个对应的状态序列S ，使得S能够最为合理的解释观察序列O？ N和T分别为状态个数和序列长度 定义： 我们所要找的，就是T时刻最大的 所代表的那个状态序列

Viterbi算法(续) 初始化： 递归： 终结： 求S序列：

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步工作

Baum-Welch算法(续) 定义：

Baum-Welch算法(续2) 参数估计：

几种典型形状的马尔科夫链 a. A矩阵没有零值的Markov链 b. A矩阵有零值的Markov链 c./d. 左－右形式的Markov链

HMM的应用领域 语音识别 机器视觉 人脸检测 机器人足球 图像处理 图像去噪 图像识别 生物医学分析 DNA/蛋白质序列分析

主要参考文献 1. Lawrence R. Rabiner, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition. Proceedings 1989. ftp://10.11.11.111/课件/徐从富_AI/补充材料/隐Markov模型.pdf 或ftp://10.214.1.200/课件/徐从富_AI/补充材料/隐Markov模型.pdf

欢迎批评指正， 谢谢！