马尔科夫链模型及其应用课件

马尔科夫链模型及其应用,马尔可夫模型及其应用,汇报人：吕昌伟201571672015年12月1日,马尔科夫链模型及其应用,目录,马尔科夫链模型及其应用,马尔科夫链：介绍,马尔可夫链，因安德烈马尔可夫（A.A.Markov，18561922）得名，是数学领域中具有马尔可夫性质的离散时间随机过程。马尔可夫在1906年首先做出了这类过程。而将此一般化到可数无限状态空间是由柯尔莫果洛夫在1936年给出的。,安德烈马尔可夫，俄罗斯人，物理-数学博士，圣彼得堡科学院院士，彼得堡数学学派的代表人物，以数论和概率论方面的工作著称，他的主要著作有概率演算等。1878年，荣获金质奖章，1905年被授予功勋教授称号。,马尔科夫链模型及其应用,马尔科夫链：定义及表示,随机过程是随机变量的集合，指标t通常表示时间，此时，过程X是随时间而变化的随机变量X的取值模型。X(t)是过程在时刻t的状态，用Xt代替X(t)。这里我们着重于特殊类型的离散时间、离散空间随机过程X0,X1,X2,，其中Xt的值依赖于Xt-1的值，但不依赖于导致系统取那个值得状态序列。定义：一个离散时间随机过程X0，X1，X2，是马尔可夫链，如果,马尔可夫性无记忆性,马尔科夫链模型及其应用,马尔科夫链：一般性,假定马尔可夫链的离散状态空间为0,1,2，n(或0,1,2，如果可数无穷)。转移概率是过程i经一步转移到j的概率。马儿可夫性蕴涵马尔可夫链由一步转移矩阵唯一确定。,归一化：对所有i,马尔科夫链模型及其应用,马尔科夫链：m步转移概率,对任意m0,我们将m步转移概率定义为链从状态i经恰好m步到达状态j的概率。,在从i出发经1次转移的条件下，我们有,设P(m)是一个矩阵，其元素为m步转移概率，使得第i行第j列元素为由上式可得经关于m的归纳,设pi(t)表示过程在t时刻处于状态i的概率是在t时刻给出链的状态分布的向量我们将概率分布表示成一个行向量,马尔科夫链模型及其应用,马尔科夫链：加权图表示,马尔可夫链的另一种有用的表示是用一个有向加权图D=(V,E,w).图的顶点集合是链的状态集存在一条有向边,当且仅当Pi,j0,此时边(i,j)的权w(i,j)由w(i,j)=Pi,j给出自圈（一条边开始和结束在同一顶点）是允许的。对每一个i，我们仍要求一个由过程逗留过的状态序列表示为图上的一条有向路径。过程沿着这条路径的概率是路径表的权的乘积。,马尔科夫链模型及其应用,马尔科夫链：例子,计算恰好经过三步从状态0到状态3的概率。,路径：概率0-1-0-33/320-1-3-31/960-3-1-31/160-3-3-33/64总概率：41/192,马尔科夫链,转移矩阵,马尔科夫链模型及其应用,马尔科夫链：应用保险公司,保险公司要对投保人未来的健康状态作出估计，以制订保险金和理赔金的数额例：人的健康状况分为健康和疾病两种状态，设对特定年龄段的人，今年健康、明年保持健康状态的概率为0.8，而今年患病、明年转为健康状态的概率为0.7，若某人投保时健康，问10年后他仍处于健康状态的概率是多少？,状态Xn=,1，第n年健康,2，第n年疾病,p11=0.8p12=1-p11=0.2p21=0.7p22=1-p21=0.3,Xn+1只取决于Xn和pij,与Xn-1,无关,马尔科夫链模型及其应用,马尔科夫链：应用保险公司,状态转移具有无后效性a1(n+1)=a1(n)p11+a2(n)p21a2(n+1)=a1(n)p12+a2(n)p22,给定a(0),预测a(n),n=1,2,设投保时健康,设投保时疾病,n时状态概率趋于稳定值，稳定值与初始状态无关,马尔科夫链模型及其应用,马尔科夫链：应用保险公司,Xn=3为第三种状态死亡,a1(n+1)=a1(n)p11+a2(n)p21+a3(n)p31a2(n+1)=a1(n)p12+a2(n)p22+a3(n)p32a3(n+1)=a1(n)p13+a2(n)p23+a3(n)p33,设投保时处于健康状态，预测a(n),n=1,2,马尔科夫链模型及其应用,隐马尔科夫模型,例如：一个隐居的人可能不能直观的观察到天气的情况，但是民间传说告诉我们海藻的状态在某种概率上是和天气的情况相关的。在这种情况下我们有两个状态集合，一个可以观察到的状态集合（海藻的状态）和一个隐藏的状态（天气状况）。我们希望能找到一个算法可以根据海藻的状况和马尔科夫假设来预测天气的状况。隐藏状态的数目和可以观察到的状态的数目可能是不一样的。在一个有3种状态的天气系统（sunny、cloudy、rainy）中，也许可以观察到4种潮湿程度的海藻（dry、dryish、damp、soggy）。可以观察到的状态序列和隐藏的状态序列是概率相关的。于是我们可以将这种类型的过程建模为有一个隐藏的马尔科夫过程和一个与这个隐藏马尔科夫过程概率相关的并且可以观察到的状态集合。隐马尔可夫模型(HiddenMarkovModel)是一种统计模型，用来描述一个含有隐含未知参数的马尔可夫过程。其难点是从可观察的参数中确定该过程的隐含参数，然后利用这些参数来作进一步的分析。,马尔科夫链模型及其应用,隐马尔科夫模型,下图是一个三个状态的隐马尔可夫模型状态转移图。,x表示隐含状态y表示可观察的输出a表示状态转换概率b表示输出概率,马尔科夫链模型及其应用,隐马尔科夫模型,下图显示了天气的例子中隐藏的状态和可以观察到的状态之间的关系。我们假设隐藏的状态是一个简单的一阶马尔科夫过程，并且他们两两之间都可以相互转换。,MMvsHMM1、在MM中，每一个状态代表一个可观察的事件2、在HMM中观察到的事件是状态的随机函数，因此该模型是一双重随机过程，其中状态转移过程是不可观察（隐藏）的马尔可夫链，而可观察的事件的随机过程是隐藏的状态转换过程的随机函数（一般随机过程）。,马尔科夫链模型及其应用,隐马尔科夫模型,对HMM来说，有如下三个重要假设。假设1：马尔可夫假设（状态构成一阶马尔可夫链）假设2：不动性假设（状态与具体时间无关）假设3：输出独立性假设（输出仅与当前状态有关）,隐藏的状态和可观察到的状态之间有一种概率上的关系，也就是说某种隐藏状态H被认为是某个可以观察的状态O1是有概率的，假设为P(O1|H)。,马尔科夫链模型及其应用,隐马尔科夫模型,如果可以观察的状态有3种，那么P(O1|H)+P(O2|H)+P(O3|H)=1。这样，我们也可以得到一个另一个矩阵，称为混淆矩阵(confusionmatrix)。这个矩阵的内容是某个隐藏的状态被分别观察成几种不同的可以观察的状态的概率，在天气的例子中，这个矩阵如下图：,马尔科夫链模型及其应用,隐马尔科夫模型,一个隐马尔可夫模型HMM可用一个5元组描述：=N,M,A,BN=H1，Hn隐藏状态的有限集合M=O1，Om可观测状态的有限集合，可以通过训练集获得=i为初始状态概率，A=aij为隐藏状态的转移矩阵B=bik表示某个时刻因隐藏状态而可观察的状态的概率，即混淆矩阵在状态转移矩阵和混淆矩阵中的每个概率都是时间无关的，即当系统演化时，这些矩阵并不随时间改变。对于一个N和M固定的HMM来说，用=,A,B表示HMM参数。,模型的演化绿色的圆圈表示隐藏状态紫色的圆圈表示可观察到的状态箭头表示状态之间的依存概率,马尔科夫链模型及其应用,隐马尔科夫模型,在HMM中有三个典型问题：（一）已知模型参数，计算某一给定可观察状态序列的概率（二）根据可观察状态的序列找到一个最可能的隐藏状态序列（三）根据观察到的序列集来找到一个最有可能的HMM,0.4,隐藏状态=（Happy，Unhappy）可观察状态=（DoNothing，Beat，Kiss）开始概率=Happy：0.6，Unhappy：0.4转移概率=Happy：Happy：0.7，Unhappy：0.3，Unhappy：Happy：0.4，Unhappy：0.6发射概率=Happy：Donothing：0.1，Beat：0.4，Kiss：0.5，Unhappy：Donothing：0.6，Beat：0.3，Kiss：0.1,马尔科夫链模型及其应用,隐马尔科夫模型,Day1Kiss,Day2Beat,Day3Donothing,推断这三天她的状态，Happy还是Unhappy？,Start,H0.3,U0.04,0.6*0.5,0.4*0.1,H,U,H,U,*0.7*0.4=0.084,*0.3*0.3=0.027,*0.4*0.4=0.0064,*0.6*0.3=0.0072,*0.7*0.1=0.00588,*0.3*0.6=0.01512,*0.4*0.1=0.00108,*0.6*0.6=0.00972,0.4,马尔科夫链模型及其应用,隐马尔科夫模型,HMM的应用：语音识别音字转换词性标注（POSTagging）基因识别问题状态：编码区域与非编码区域字符：ATCG一般化：任何与线性序列相关的现象语音识别气象、气候预报模式识别问题,马尔科夫链模型及其应用,马尔可夫随机场,马尔可夫随机场（Markovrandomfields)，也叫无向图模型，或称为马尔科夫网（Markovnetwork)马尔科夫网络也有条件独立属性。,条件独立：如果A的任意节点和B的任意节点的任意路径上，都存在至少一个节点属于C那么A和B条件独立于C。,clique”团”的概念：图的一个子图，子图上两两节点都有连接.例如这个图，最大团有两个，分别是(x1,x2,x3)和(x2,x3,x4)：,马尔科夫链模型及其应用,马尔可夫随机场,联合概率分解成一系列potential函数的乘积:,Xc是一个最大团的所有节点，一个potential函数，是最大团的一个函数.这个函数具体的定义是依赖具体的应用。,常量,p(x)是一系列potential函数的乘积，可以将potential函数表示成指数函数:,这样p(x)就可以表示成一系列E(Xc)的和的指数函数，E(Xc)叫做能量函数，转换之后，可以将图理解成一个能量的集合，他的值等于各个最大团的能量的和.,马尔科夫链模型及其应用,马尔可夫随机场,有一个二值图像，观测序列，也就是我们所拥有的图像。,其中i=1,2,D,D代表像素点的个数（包括了所有图像，我们所观测的图像包括噪声）,真实的图像,左边的图像表示真实图像，由xi表示以10%的概率改变真实图像的像素为其原来相反的值，生成右边的图像，由yi表示利用马尔科夫随机场实现噪声图还原为真实图。,马尔科夫链模型及其应用,马尔可夫随机场,yi，是噪声图，紫色表示是已知的，是观察值。xi是未知的，要求出xi，使xi作为像素值得到的图，尽量接近无噪声图片。每个xi的值，与yi相关，也与相邻的xj相关。这里边，最大团是(xi,yi)和(xi,xj)，两类最大团。对于(xi,yi)，选择能量函数E(xi,yi)=-xiyi对于(xi,xj)，选择能量函数E(xi,xj)=-xixj能量函数的意思是：如果xi和yi(或xi和xj)的值相同，则能