《隐马尔可夫模型》PPT课件

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,隐马尔可夫模型,Hidden Markov model,徐从富,浙江大学人工智能研究所,2003年10月第一稿,2005年9月修改补充,Modified by siuleung,目 录,HMM的由来,马尔可夫性和马尔可夫链,HMM实例,HMM的三个基本算法,主要参考文献,HMM的由来,1870,年，俄国有机化学家,Vladimir V.,Markovnikov,第一次提出马尔科夫模型,马尔可夫模型,马尔可夫链,隐马尔可夫模型,马尔可夫性,如果一个过程的“将来”仅依赖“现在”而不依赖“过去”，则此过程具有,马尔可夫性,或称此过程为,马尔可夫过程,X(t+1)=f(X(t),马尔科夫链,时间,和,状态,都离散的马尔科夫过程称为马尔科夫链,记作X,n,=X(n),n=0,1,2,在时间集T,1,=0,1,2,上对离散状态的过程相继观察的结果,链的状态空间记做I=a,1,a,2,a,i,R.,条件概率,P,ij,(,m,m+n),=,PX,m+n,=a,j,|X,m,=a,i,为马氏链在时刻,m,处于状态,a,i,条件下，在时刻,m+n,转移到状态,a,j,的,转移概率,。,转移概率矩阵,阴天,晴天,下雨,晴天 阴天 下雨,晴天,0.50 0.25 0.25,阴天,0.375 0.25 0.375,下雨,0.25 0.125 0.625,转移概率矩阵(续),由于链在时刻m从任何一个状态a,i,出发，到另一时刻m+n，必然转移到a,1,，a,2,，诸状态中的某一个，所以有,当,P,ij,(m,m+n),与,m,无关时，称马尔科夫链为,齐次马尔科夫链,，通常说的马尔科夫链都是指齐次马尔科夫链。,HMM,实例,Observed Ball Sequence,Urn 3,Urn 1,Urn 2,Veil,HMM实例,描述,设有N个缸，每个缸中装有很多彩球，球的颜色由一组概率分布描述。实验进行方式如下,根据初始概率分布，随机选择N个缸中的一个开始实验,根据缸中球颜色的概率分布，随机选择一个球，记球的颜色为O,1,，并把球放回缸中,根据描述缸的转移的概率分布，随机选择下一口缸，重复以上步骤。,最后得到一个描述球的颜色的序列,O,1,O,2,，称为观察值序列,O,。,HMM实例,约束,在上述实验中，有几个要点需要注意：,不能被直接观察缸间的转移,从缸中所选取的球的颜色和缸并不是,一一对应的,每次选取哪个缸由一组转移概率决定,HMM概念,HMM的状态是不确定或不可见的，只有通过观测序列的随机过程才能表现出来,观察到的事件与状态并不是一一对应，而是通过一组概率分布相联系,HMM是一个双重随机过程，两个组成部分：,马尔可夫链,：描述状态的转移，用,转移概率,描述。,一般随机过程,：描述状态与观察序列间的关系，用,观察值概率,描述。,Markov链,（,A,）,随机过程,（,B,）,状态序列,观察值序列,q,1,q,2,.,q,T,o,1,o,2,.,o,T,HMM的组成示意图,HMM组成,HMM的基本要素,用模型五元组 （N,M,，A，B）用来描述HMM，或简写为 =(，A，B),参数,含义,实例,N,状态数目,缸的数目,M,每个状态可能的观察值数目,彩球颜色数目,A,与时间无关的状态转移概率矩阵,在选定某个缸的情况下，选择另一个缸的概率,B,给定状态下，观察值概率分布,每个缸中的颜色分布,p,初始状态空间的概率分布,初始时选择某口缸的概率,HMM可解决的问题,问题1：给定观察序列O=O,1,O,2,O,T,以及模型 ,如何计算,P(O|),？,问题2：给定观察序列O=O,1,O,2,O,T,以及模型,如何选择一个对应的状态序列 S=q,1,q,2,q,T,，使得S能够最为合理的解释观察序列O？,问题3：如何调整模型参数 ,使得P(O|)最大？,解决问题1 基础方法,给定一个固定的状态序列,S=(q,1,，q,2,，q,3,),表示在,q,t,状态下观测到,O,t,的概率,N=5,M=100,=计算量1072,解决问题1 前向法,动态规划,定义前向变量,初始化：,递归：,终结：,前向法示意图,1 .t t+1 .,a,1j,a,t,1,q,N,.,q,i,.,q,j,.,.,q,1,a,t,N,a,t,i,a,Nj,a,ij,N=5,M=100,=计算量3000,解决问题1 后向法,与前向法类似,定义后向变量,初始化：,递归：,终结：,Viterbi,算法,目的：,给定观察序列O以及模型,如何选择一个对应的状态序列S，使得S能够最为合理的解释观察序列O？,N和T分别为状态个数和序列长度,定义：,我们所要找的，就是T时刻最大的 所代表的那个状态序列,Viterbi,算法(续),初始化：,递归：,终结：,求S序列：,Baum-Welch,算法(模型训练算法),目的：给定观察值序列O，通过计算确定一个模型,l,，,使得,P(O|,l,),最大。,算法步骤：,1.,初始模型（待训练模型）,l,0,2.,基于,l,0,以及观察值序列,O，,训练新模型,l,；,3.,如果,logP(X|,l,)-log(P(X|,l,0,)Delta,，,说明训练已经达到预期效果，算法结束。,4.,否则，令,l,0,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.,课件/徐从富_AI/补充材料/隐Markov模型.pdf,或,课件/徐从富_AI/补充材料/隐Markov模型.pdf,欢迎批评指正，,谢谢！,