第9章-隐马尔可夫模型案例.ppt

,Date:,*,File:ML11.,*,Machine Learning,Peng Kaixiang 2014.All rights reserved.,Machine,Learning for,Control Engineering,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第9章,隐马尔可夫模型,(Hidden Markov Models),主要内容,马尔可夫模型,隐马尔可夫模型,隐马尔可夫模型的三个基本问题,三个基本问题的求解算法,1.,前向算法,2.Viterbi,算法,3.,向前向后算法,隐马尔可夫模型的应用,隐马尔可夫模型的一些实际问题,隐马尔可夫模型总结,马尔可夫链,一个系统有,N,个状态,S,1,，,S,2,，,，,S,n,，随着时间推移，系统从某一状态转移到另一状态，设,q,t,为时刻,t,的状态，系统在时刻,t,处于状态,S,j,的概率取决于其在时间,1,，,2,，,，,t-1,的状态，该概率为：,如果系统在,t,时间的状态只与其在时间,t-1,的状态相关，则该系统构成一个离散的,一阶马尔可夫链,(,马尔可夫过程,),：,即：给定当前的状态，未来的系统状态独立于过去的状态,马尔可夫模型,如果只考虑独立于时间,t,的随机过程：,其中,状态转移概率,a,ij,必须满足,a,ij,=0,且,，则该随机过程称为,马尔可夫模型,。,独立于时间,t,：,从状态,S,i,到状态,S,j,的状态转移具有相同的概率，无论这个转移在观测序列中的何时或何地发生。,马尔可夫模型可视为随机有限状态自动机,该有限状态自动机的每一状态转换都有一相应概率，表示自动机采样这状态转换的可能性,假定一段时间的气象可由一个三状态的马尔可夫模型,M,描述，,S,1,：下雨，,S,2,：多云，,S,3,：晴天，状态转移概率矩阵为,：,多云,下雨,晴天,例：,例（续）,如果第一天为晴天，根据这一模型，在今后七天中天气为,O=“,晴晴雨雨晴云晴”的概率为：,可观测状态序列观测概率,定义初始概率,i,，表示序列是,S,i,的概率：,有,:,若有一可观测序列,O,，它是状态序列,O=Q=,q,1,q,2,q,3,q,T,的概率为：,如何学习得到,、,A,给定,K,个长度为,T,的序列，初始概率估计：,转移概率的估计：,隐马尔可夫模型,在,MM,中，每一个状态代表一个可观察的,事件,在,HMM,中观察到的事件是状态的随机函数，因此该模型是一,双重随机过程,，其中状态转移过程是不可观测（隐蔽）的,(,马尔可夫链,),，而可观测的事件的随机过程是,隐蔽的状态转换过程的随机函数,(,一般随机过程,),。,实例,一房间有,N,只容器，每只容器中有,M,种不同颜色的球。根据某一概率分布随机地选择一个,初始容器,，根据,不同颜色球的概率分布从中随机取出一个球,，并,报告球的颜色,。然后,根据某一概率分布随机地选择另一只容器,，再根据不同颜色球的概率分布从中随机取出一个球，并报告球的颜色，。对房间外的观察者，,可观察的过程是不同颜色球的序列,，而容器的序列是不可观察的。,这里每只容器对应,HMM,模型中的状态，球的颜色对应于状态的输出符号，从一只容器转向另一只容器对应于状态转换，从一只容器中取球对应于从一状态输出观察符号。,实例（续）,实验中几个要点,不能直接观察容器间的转移；,从容器中所选取的球的颜色和容器并不是一一对应的；,每次选取哪个容器由一组转移概率决定。,HMM,的三个假设,对于一个随机事件，有一观察值序列：,O=O,1,O,2,O,T,该事件隐含着一个状态序列：,Q=q,1,q,2,q,T,。,假设,1,：,马尔可夫性假设（状态构成一阶马尔可夫链）,P(q,i,|q,i-1,q,1,)=P(q,i,|q,i-1,),假设,2,：,不动性假设（状态与具体时间无关）,P(q,i+1,|q,i,)=P(q,j+1,|q,j,),，对任意,i,，,j,成立,假设,3,：,输出独立性假设（输出仅与当前状态有关）,p(O,1,.,O,T,|q,1,.,q,T,)=,p,(O,t,|q,t,),HMM,的组成,一个隐马尔可夫模型,(HMM),是由一个五元组描述的：,（,N,，,M,，,A,，,B,，,）,其中：,S,=q,1,.q,N,：,N,为模型状态个数,V,=v,1,.,v,M,：,M,为不同观测符号个数,A=a,ij,，,a,ij,=P(q,t,=S,j,|q,t-1,=S,i,),：状态转移概率矩阵,B=b,jk,，,b,jk,=P(O,t,=v,k,|q,t,=S,j,),：给定状态下，观察值概率分布矩阵,=,i,，,i,=P(q,1,=S,i,),：初始状态概率分布,状态转移概率矩阵,观察值概率分布矩阵,初始状态概率分布,观察序列产生步骤,给定,HMM,模型,=(A,，,B,，,),，则观察序列,O=O,1,O,2,O,T,可由以下步骤产生：,1.,根据初始状态概率分布,=,i,选择一初始状态,q,1,=S,i,；,2.,设,t=1,；,3.,根据状态,S,i,的输出概率分布,b,jk,输出,O,t,=v,k,；,4.,根据状态转移概率分布,a,ij,转移到新状态,q,t+1,=S,j,；,5.,设,t=t+1,如果,tT,，重复步骤,3,、,4,，否则结束。,HMM,的三个基本问题,令,=,，,A,，,B,为给定,HMM,的参数，,令,O,=O,1,.,O,T,为观测值序列，则有关于隐马尔可夫模型（,HMM,）的三个基本问题：,1.,评估问题：,对于给定模型，求某个观测值序列的概率,P(,O,|,),；,2.,解码问题：,对于给定模型和观测值序列，求可能性最大的状态序列,max,Q,P(Q|O,),；,3.,学习问题：,对于给定的一个观测值序列,O,，调整参数,，使得观测值出现的概率,P(,O,|,),最大。,骰子,A,骰子,B,1,点,1/6,0,2,点,1/6,1/8,3,点,1/6,1/8,4,点,1/6,3/16,5,点,1/6,3/16,6,点,1/6,3/8,公平骰子,A,与灌铅骰子,B,的区别,:,例,:,赌场的欺诈,某赌场在掷骰子根据点数决定胜负时,暗中,采取了如下作弊手段,:,在连续多次掷骰子的过程中,通常使用公平骰,子,A,B,0.9,0.1,A,偶而混入一个灌铅骰子,B.,0.8,0.2,公平骰子,灌铅骰子,时间,1,2,3,4,5,6,7,骰子,A,A,A,B,A,A,A,掷出,点数,3,3,4,5,1,6,2,一次连续掷骰子的过程模拟,隐,序列,明,序列,查封赌场后,调查人员发现了一些连续掷骰子的记录,其中有一个骰子掷出的点数记录如下,:,124552646214614613613666166466163661636616361651561511514612356234,问题,1,评估问题,给定,一个骰子掷出的点数记录,124552,6,4,6,214,6,14,6,13,6,13,666,1,66,4,66,1,6,3,66,1,6,3,66,1,6,3,6,1,6,515,6,1511514,6,1235,6,234,问题,会出现这个点数记录的概率有多大,?,求,P(O|,),问题,2,解码问题,给定,一个骰子掷出的点数记录,问题,点数序列中的哪些点数是用骰子,B,掷出的,?,求,maxQP(Q|O,),124552,6,4,6,214,6,14,6,13,6,13,666,1,66,4,66,1,6,3,66,1,6,3,66,1,6,3,6,1,6,515,6,1511514,6,1235,6,234,问题,3,学习问题,给定,一个骰子掷出的点数记录,问题,作弊骰子掷出各点数的概率是怎样的,?,公平骰子,掷出各点数的概率又是怎样的,?,赌场是何时换用骰子的,?,124552,6,4,6,214,6,14,6,13,6,13,666,1,66,4,66,1,6,3,66,1,6,3,66,1,6,3,6,1,6,515,6,1511514,6,1235,6,234,骰子,B,本例中,HMM,的定义,赌场的例子中,:,隐状态集,:S=,骰子,A,骰子,B,明字符集,:V=1,2,3,4,5,6,b,21,=0,b,22,=b,23,=1/8,b,24,=b,25,=3/16,b,26,=3/8,1/6,1/6,1/6,1/6,1/6,1/6,0,1/8,1/8,3/16,3/16,3/8,初始状态概率,:,1,=1,2,=0,隐状态转移概率,:,a,11,=0.9,a,12,=0.1,a,21,=0.8,a,22,=0.2,初始状态,明字符生成概率,:,b,11,=b,12,=b,16,=1/6,1.0,0,1:,2:,3:,4:,5:,骰子,A,6:,0.1,1:,2:,3:,4:,5:,6:,0.8,0.9,0.2,HMM,将两个序列相联系起来：,1.,由离散,隐,状态组成的,状态序列,(,路径,),Q=(q,1,q,T,),每个,q,t,S,均是一个状态,由初始状态概率及状态转移概率,(,A),所决定,2.,由,明,字符组成的,观测序列,O=(o,1,o,T,),每个,o,t,V,均为一个离散明字符,由状态序列及各状态的明字符生成概率,(Q,B),所决定,赌场的例子中,:,隐,状态,明,观察,AAAA,B,AAAAA,B,AAAAAAAAAAAAAAAAAAAAAAA,B,AA,B,AAAAAAAAA,3 3 4 5 4 1 4 1 5 5 3 6 6 3 4 4 1 1 3 4 6 2 5 4 4 5 3 3 4 2 2 3 3 3 2 1 2 4 2 2 5 6 3 1 3 4 1,q,1,q,2,q,3,q,4,q,T,.,o,1,o,2,o,3,o,4,o,T,.,观察序列,O,状态序列,Q,HMM,本例中三个基本问题,1.,评估问题,给定观察序列,O,和,HMM,=(,A,B),判断,O,是由,产,生出来的可能性有多大,计算骰子点数序列的确由,“,作弊,”,模型生成的可能性,2.,解码问题,给定观察序列,O,和,HMM,=(,A,B),计算与序列,O,相,对应的状态序列是什么,在骰子点数序列中,判断哪些点数是用骰子,B,掷出的,3.,学习问题,给定一系列观察序列样本,确定能够产生出这些序列的模,型,=(,A,B),如何从大量的点数序列样本中学习得出,“,作弊模型,”,的参数,三个基本问题的求解算法,评估问题：前向算法,/,后向算法,定义前向变量,/,后向变量,采用动态规划算法，复杂度,O(N,2,T),解码问题：韦特比（,Viterbi,）算法,采用动态规划算法，复杂度,O(N,2,T),学习问题：向前向后算法,EM,算法的一个特例，带隐变量的最大似然估计,解决问题一,解决问题一,前向算法,定义,前向变量,为：,“,在时间步,t,得到,t,之前的所有明符号序列,且时间,步,t,的状态是,S,i,”,这一事件的概率，,记为：,t,(i,)=,P(o,1,o,t,q,t,=S,i,|,),则,递归计算,前向算法过程,HMM,的网格结构,前向算法过程演示,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,(,t,i),t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,初始化,1,(i)=,i,b,i,(O,1,),t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,2.,递归,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,前向算法过程演示,i=N,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,i=N-1,i=5,i=4,i=3,i=2,i=1,前向算法过程演示,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=6,t=7,t=T-1,前向算法过程演示,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=7,t=6,t=T-1,前向算法过程演示,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=T-1,t=6,t=7,前向算法过程演示,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,t=1,t=2,t=3,t=4,t=5,t=T,t=T-1,t=6,t=7,前向算法过程演示,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,前向算法过程演示,t=1,t=2,t=3,t=4,t=5,t=T,t=T-1,t=6,t=7,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,3.,计算,P(O|,),t=1,t=2,t=3,t=4,t=5,t=T,t=T-1,t=6,t=7,前向算法过程演示,i=N,i=N-1,i=5,i=4,i=3,i=2,i=1,例子（前向算法应用）,HMM,模型如下，试根据前向算法计算产生观察符号序列,O=ABAB,的概率。,状态集,Q=S1,S2,S3,观察序列集,O=A,B,例（续）,初始概率矩阵,=(1,0,0),即开始处于状态,1,。按照前向算法公式，我们依次递推解出,t,(i),。解法如下：,1.,当,t=1,时：,例（续）,2.,当,t=2,时：,3.,当,t=3,时：,例（续）,4.,当,t=4,时：,所以最终有：,P(O|,)=,4,(1)+,4,(2)+,4,(3)=0.0717696,即观察序列,O,由,HMM,模型产生的概率,例（续）,最后将其计算过程示意图表示如下：,前向变量图示,后向变量,类似前向变量而定义,后向变量,t,(i),，作为在时刻,t,处于状态,S,i,并观测到部分序列,O,t+1,O,T,的概率。,t,(i),P(O,t+1,O,T,|q,t,=S,i,),递归计算,后向算法,后向变量图示,后向变量：,问题 二,解码问题,给定观测序列,O=,O,1,O,2,O,T,和,HMM,的模型,，计算与序列,O,相对应的最佳状态序列,Q=,q,1,q,2,q,T,。,所求的,Q,应当在某个准则下是,“,最优,”,的,因此也称,Q,为最优路径,解码问题即是确定,最优路径,的问题。,解决问题二,Viterbi,算法,Viterbi,算法也是类似于前向算法的一种网格结构,定义,t,(i),为时刻,t,沿状态序列,q,1,q,2,q,t,且,q,t,=S,i,产生出,O,1,O,t,的最大概率，即：,Viterbi,算法（续）,目标：给定一个观察序列和,HMM,模型，如何有效选择,“,最优,”,状态序列，以,“,最好地解释,”,观察序列,“,最优,”,概率最大：,思想：利用动态规划求解，复杂性,O(N,2,T),Viterbi,变量：,递归关系：,记忆变量：记录概率最大路径上当前状态的前一个状态,Viterbi,算法（续）,初始化：,递归：,终结：,从时刻,T,开始，进行路径回溯：,例子（,Viterbi,算法应用）,HMM,模型如下，试根据,Viterbi,算法计算产生观察符号序列,O=ABAB,的最优状态序列,Q,。,状态集,Q,S1,S2,S3,观察序列集,O=A,B,例（续）,初始概率矩阵,=(1,0,0),即开始时处于状,态,1,。按照上面的公式，我们依次递推解出,，以及 。解法如下：,1.,当,t=1,时：,例（续）,2.,当,t=2,时：,3.,当,t=3,时：,例（续）,4.,当,t=4,时：,例（续）,其递推结果为：,可以看出，最有可能的状态序列是：,S1,，,S2,，,S2,，,S2.,例（续）,其计算结果示意图如下所示：,绿色的箭头表示最有可能的状态序列,问题三,学习问题,也称训练问题、参数估计问题,给定一系列观测样本，从中确定产生出这些序列的模型,(,A,B),，以满足某种最优化准则，使得观察序列的概率,P(O|,),最大。,状态序列已知情况,可以由最大似然估计来估计,HMM,的参数：,EM(Expectation-Maximization),算法,由于,HMM,中的状态序列是观察不到的（隐变量），以上的最大似然估计不可行。,EM,算法可用于含有隐变量的统计模型的最大似然估计。,EM,算法是一个由交替进行的“期望,(E,过程,)”,和“极大似然估计,(M,过程,)”,两部分组成的迭代过程：,对于给定的不完全数据和当前的参数值，,“,E,过程,”,从条件期望中相 应地构造完全数据的似然函数值，,“,M,过程,”,则利用参数的充分统计,量，重新估计概率模型的参数，使得训练数据的对数似然最大。,EM,算法的每一次迭代过程必定单调地增加训练数据的对数似然值，于是迭代过程渐进地收敛于一个局部最优值。,定义,t,（,i,，,j,）为给定全部观察序列,O,和,，在时刻,t,处于状态,i,，时刻,t+1,位于状态,j,的概率。,(1),图示,t,(i,),表示在时刻,t,的前,t,个观测并止于状态,S,i,的概率。并以概率,a,ij,转移到状态,S,j,，产生第,t+1,个观测，并在,t+1,时刻从,S,j,开始继续产生其余的观测序列。可通过将,t,除以所有在时刻,t,和时刻,t+1,可能处于的状态进行规范化。,定义,t,（,i,）,给定,HMM,和观测序列，在时间,t,位于状态,i,的概率：,(2),计算模型参数,(3),前向后向算法,(Baum-Welch,算法,),1.,初始化：随机地给,i,，,a,ij,，,b,jk,赋值（满足概率条件），得到模型,0,，设,i=0,；,2.EM,步骤：,E,步骤：由,i,根据公式（,1,）和（,2,），计算期望值,t,（,i,，,j,）和,t,（,i,）；,M,步骤：用,E,步骤所得的期望值，根据公式（,3,）重新估计,i,，,a,ij,，,bjk,，得到模型,i+1,;,3.,循环设计：,i=i+1,；重复,EM,步骤，直至,i,，,a,ij,，,b,jk,值收敛。,期望值,(1),给定,HMM,和观察序列，,t,（,i,，,j,）为在时间,t,位于状态,i,，时间,t+1,位于状态,j,的概率：,期望值,(2),给定,HMM,和观测序列，在时间,t,位于状态,i,的概率：,重估公式,(3),HMM,的应用,语音识别,音字转换,词性标注（,POS Tagging,）,基因识别问题,状态,:,编码区域与非编码区域,字符,:ATCG,一般化：任何与线性序列相关的现象,HMM,的一些实际问题,初始概率分布的选择,1.,随机选择,2.,利用先验信息,3.,来自多序列比对的结果,HMM,的一些实际问题（续）,数值计算中的防溢出处理,在前向算法、,Viterbi,算法以及,Baum-Welch,算法中，概率值的连续乘法运算很容易导致下溢现象。,解决办法：,1.,前向算法中：每一个时间步的运算中都乘以一 个比例因子,2.Viterbi,算法中：对概率值取对数后计算,Viterbi,算法,:,连乘积对数求和,前向算法,:,引入比例因子,其中,比例因子,HMM,总结,HMM,模型可以看作一种特定的,Bayes Net,HMM,模型等价于概率正规语法或概率有限状态自动机,HMM,模型可以用一种特定的神经网络模型来模拟,优点：研究透彻，算法成熟，效率高，效果好，易于训练,人有了知识，就会具备各种分析能力，,明辨是非的能力。,所以我们要勤恳读书，广泛阅读，,古人说“书中自有黄金屋。,”通过阅读科技书籍，我们能丰富知识，,培养逻辑思维能力；,通过阅读文学作品，我们能提高文学鉴赏水平，,培养文学情趣；,通过阅读报刊，我们能增长见识，扩大自己的知识面。,有许多书籍还能培养我们的道德情操，,给我们巨大的精神力量，,鼓舞我们前进,。,