隐马尔可夫模型初步Chapter9HiddenMarkovModel.ppt
第九讲 隐马尔可夫模型初步 Chapter 9 Hidden Markov Model (Part A),目 录,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, aiR. 条件概率Pij ( m ,m+n)=PXm+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实例,HMM实例描述,设有N个缸，每个缸中装有很多彩球，球的颜色由一组概率分布描述。实验进行方式如下 根据初始概率分布，随机选择N个缸中的一个开始实验 根据缸中球颜色的概率分布，随机选择一个球，记球的颜色为O1，并把球放回缸中 根据描述缸的转移的概率分布，随机选择下一口缸，重复以上步骤。 最后得到一个描述球的颜色的序列O1,O2,，称为观察值序列O。,HMM实例约束,在上述实验中，有几个要点需要注意： 缸间的转移不能被直接观察 每次选取哪个缸由一组转移概率决定 从缸中所选取的球的颜色和缸并不是 一一对应的,HMM概念,HMM的状态是不确定或不可见的，只有通过观测序列的随机过程才能表现出来 观察到的事件与状态并不是一一对应，而是通过一组概率分布相联系 HMM是一个双重随机过程，两个组成部分： 马尔可夫链：描述状态的转移，用转移概率描述。 一般随机过程：描述状态与观察序列间的关系， 用观察值概率描述。,Markov链 （, A）,随机过程 （B）,状态序列,观察值序列,q1, q2, ., qT,o1, o2, ., oT,HMM的组成示意图,HMM组成,HMM的基本要素,用模型五元组 （ N, M, ，A，B）用来描述HMM，或简写为 =( ，A，B),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, 其计算量为1072！,解决问题1 前向法,动态规划 定义前向变量 初始化： 递归： 终结：,前向法示意图,1 . t t+1 .,a1j,at1,qN . qi . qj . . . . q1,atN,ati,aNj,aij,当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,欢迎批评指正， 谢谢！,
