markov过程.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,二级,三级,四级,五级,12-7-19,#,Markov,过程,于馨培,马尔科夫过程,马尔科夫链,隐马尔科夫过程,随机过程定义,马尔科夫过程,随机过程与函数的不同：,随机过程将普通函数的概念从实数与实数的对应关系推广到实数与随机变量的对应关系。对普通函数而言，当,t,属于,T,时，总有一个确定的实数与之对应；而对随机过程而言，当,t,属于,T,时，与之对应的是一个随机变量。,马尔科夫过程定义,马尔科夫过程,如果一个随机过,程的“将来”仅依赖“现在”而不依赖“过去”，则此过程具有,马尔可夫性,或称此过程为,马尔可夫过程,X(t+1)=f(X(t),一般表示为：,这种性质好像还在哪听过。,乱入。,马尔科夫过程,最优化原理（最优子结构）,“一个过程的最优决策具有这样的性质：即无论其初始状态和初始决策如何，其今后诸策略对以第一个决策所形成的状态作为初始状态的过程而言，必须构成最优策略”,。,（,bellman,大神说的。）,假设为了解决某一优化问题，需要依次作出,n,个决策,D,1,，,D,2,，,，,D,n,，如若这个决策序列是最优的，对于任何一个整数,k,，,1 k n,，不论前面,k,个决策是怎样的，以,后的最优决策只取决于当前状态,，即以后的决策,D,k+1,，,D,k+2,，,，,D,n,也是最优的,。,。动态规划？！,可以看到马尔科夫过程用的很多算法确实是,DP,马尔科夫过程分类,马尔科夫过程,时间参数离散、状态空间离散的叫,马尔科夫链,。,时间参数连续、状态空间离散的叫,可数状态马尔科夫过程,。,时间参数离散、状态空间连续的叫,马尔科夫序列,。,时间参数和状态空间都连续的叫,连续马尔科夫过程,。,状态空间不确定的叫,隐式马尔科夫过程,。,马尔科夫链研究的问题,马尔科夫链,稳态分析：时间趋向于正无穷时的情况，此时需要关注首达概率、常返状态等问题。,瞬态分析：求某一时刻的概率分布和转移情况。,马尔科夫链,马尔科夫链,记作,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,的,转移概率,。,当,P,ij,(m,m+n),与,m,无关时，称马尔科夫链为,齐次马尔科夫链,，通常说的马尔科夫链都是指齐次马尔科夫链,。齐次才能定量计算，若不是也要近似为齐次。,Chapman-Kolmogorov,方程,马尔科夫链,X,n,n,0,在,n,时处于状态,i,的条件下经过,k+m,步转移于,n+k+m,时到达状态,j,，可以先在,n,时从状态,i,出发，经过,k,步于,n+k,时到达某种中间状态,l,，再在,n+k,时从状态,l,出发经过,m,步转移于,n+k+m,时到达最终状态,j,，而中间状态,l,要取遍整个状态空间,。,齐次马尔可夫链,X,n,n,0,的有限维分布由其初始分布和一步转移概率所完全确定,.,阴天,晴天,下雨,晴天,阴天,下雨,晴天,0.50 0.25 0.25,阴天,0.375 0.25 0.375,下雨,0.25 0.125 0.625,齐次马尔科夫链的转移矩阵,互通性,马尔科夫链,若对某一,n,1,，有,，则称系统,X,可以自状态,I,到达状态,j,，并记,ij,。如果,ij,，并且,ji,，则状态,i,与,j,互通,，并记为,i,j,互通性的性质,自反律：,i i,(,假定每个状态,0,步转移到自己,),对称律：,i j,当且仅当,j i,传递律：,i k,且,k j,，则,i j,i,j,i,与,j,不通,i,k,j,i,，,j,，,k,互通,强连通分量,不可约性,马尔科夫链,不可约闭集：设,C,是闭集，如果,C,中不再含有任何非空真闭子集，则称,C,是,不可约闭集,.,或称,C,是不可约的，或不可分的，或最小的,.,若一个马,氏链的任意两个状态都互通，则此马氏链称为,不可约,马氏链；否则称为可约的马氏链。,2,，,3,闭集,4,闭集,(,吸收态,),1,1/3,0,1,1,2,3,1,2/3,1/3,1,0,1,1,2/3,2,强连通缩点。,设,C,为状态空间,I,的一个子集，,则,C,称为,闭集,。,常返性,马尔科夫链,常返性是考察马氏链由一个状态出发之后能否再次回归到本状态的特性,常返性分三种,正常返（必定会返回，平均返回时间为有限值）,零常返（必定会返回，平均返回时间为,）,非常返（可能不再返回）,首达概率和迟早概率,马尔科夫链,为系统在,0,时从状态,i,出发经过,n,步转移后首次到达状态,j,的概率，简称,首达概率,.,称,为系统在,0,时从状态,i,出发经过有限步转移后迟早要回状态,j,的概率，简称,迟早概率,.,Doeblin,公式,马尔科夫链,Doeblin,公式：,有：,推论,1,：,推论,2,：,证明思路：,（,1,）上极限,存在,（,2,）下极限,存在,（,3,）相,等,状态,i,非常返态,常返态,零常返态（有限状态,markov,不存在）,正常返态,周期,（,d,不等于,1,）,非周期（遍历态）,常返态,非常返态,正常返态,零常返态,马尔科夫链状态分类,应用,马尔科夫链,如,为一状态,概率向量，,P,为状态转移概率矩阵。,若,则称,X,为马尔可夫链的一个,平稳分布,。,一般论文里的应用就是用来预测未来情况，其状态转移矩阵由历史数据得到，算法就是矩阵快速幂+那个神棍的O(N,2.36,)的矩阵乘法。或者也会求平稳分布，依然要用矩阵快速幂。,实例描述隐马尔科夫过程,设有,N,个缸，每个缸中装有很多彩球，球的颜色由一组概率分布描述。实验进行方式如下,根据初始概率分布，随机选择,N,个缸中的一个开始实验,根据缸中球颜色的概率分布，随机选择一个球，记球的颜色为,O,1,，并把球放回缸中,根据描述缸的转移的概率分布，随机选择下一口缸，重复以上步骤。,最后得到一个描述球的颜色的序列,O,1,O,2,，称为观察值序列,O,。,实例约束,隐马尔科夫过程,在上述实验中，有几个要点需要注意：,不能被直接观察缸间的转移,从缸中所选取的球的颜色和缸并不是,一一对应的,每次选取哪个缸由一组转移概率决定,隐马尔科夫过程概念,隐马尔科夫过程,HMM,的状态是不确定或不可见的，只有通过观测序列的随机过程才能表现出来,观察到的事件与状态并不是一一对应，而是通过一组概率分布相联系,HMM,是一个双重随机过程，两个组成部分：,马尔可夫链,：描述状态的转移，用,转移概率,描述。,一般随机过,程,：描述状态与观察序列间,的关系,，,用,观察值概率,描述,。,用模型五元组,（,N,M,，,A,，,B,）用来描述,HMM,，或简写为,=(,，,A,，,B),参数,含义,实例,N,状态数目,缸的数目,M,每个状态可能的观察值数目,彩球颜色数目,A,与时间无关的状态转移概率矩阵,在选定某个缸的情况下，选择另一个缸的概率,B,给定状态下，观察值概率分布,每个缸中的颜色分布,p,初始状态空间的概率分布,初始时选择某口缸的概率,隐马尔科夫过程概念,隐马尔科夫模型解决,的问题,隐马尔科夫模型,问题,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,？,问题,1,基本方法,隐马尔科夫模型,给定一个固定的状态序列,S=(q,1,，,q,2,，,q,3,),表示在,q,t,状态下观测到,O,t,的概率,复杂度？假设状态数为,N,，观察序列长度为,T,问题,1,动态规划,隐马尔科夫模型,DP,，复杂度？,定义前向变量,初始化：,递归：,终结：,问题,2,Viterbi,算法,隐马尔科夫模型,目的：给定观察序列,O,以及模型,如何选择一个对应的状态序列,S,，使得,S,能够最为合理的解释观察序列,O,？,N,和,T,分别为状态个数和序列长度,定义,：,我们所要找,的，就是,T,时刻最大的,所代表的那个状态,序列,问题,2,Viterbi,算法,（续）,隐马尔科夫模型,初始化：,递归：,终结：,求,S,序列：,