条件随机场CRF.ppt
条件随机场CRF,北京10月机器学习班 邹博 2014年12月14日,2,思考：给定文本标注词性,他估算当前的赤字总额在9月份仅仅降低到18亿。NN、NNS、NNP、NNPS、PRP、DT、JJ分别代表普通名词单数形式、普通名词复数形式、专有名词单数形式、专有名词复数形式、代词、限定词、形容词,3,复习：Markov Blanket,一个结点的Markov Blanket是一个集合，在这个集合中的结点都给定的条件下，该结点条件独立于其他所有结点。即：一个结点的Markov Blanket是它的parents,children以及spouses(孩子的其他parent),4,Markov Blanket,补充知识：Serum Calcium(血清钙浓度)高于2.75mmo1/L即为高钙血症。许多恶性肿瘤可并发高钙血症。以乳腺癌、骨肿瘤、肺癌、胃癌、卵巢癌、多发性骨髓瘤、急性淋巴细胞白血病等较为多见，其中乳腺癌约1/3 可发生高钙血症。,毒素,5,图像模型,考察X8的马尔科夫毯(Markov blanket),6,无向图模型,有向图模型，又称作贝叶斯网络(Directed Graphical Models,DGM,Bayesian Network)在有些情况下，强制对某些结点之间的边增加方向是不合适的。使用没有方向的无向边，形成了无向图模型(Undirected Graphical Model,UGM),又被称为 马尔科夫随机场或者马尔科夫网络(Markov Random Field,MRF or Markov network),7,条件随机场,设X=(X1,X2Xn)和Y=(Y1,Y2Ym)都是联合随机变量，若随机变量Y构成一个无向图 G=(V,E)表示的马尔科夫随机场(MRF)，则条件概率分布P(Y|X)称为条件随机场(Conditional Random Field,CRF)注：大量文献将MRF和CRF混用，包括经典著作。后面将考察为何会有该混用。,8,DGM转换成UGM,9,DGM转换成UGM,10,条件独立的破坏,靠考察是否有，则计算U的祖先图(ancestral graph)：,11,MRF的性质,成对马尔科夫性parewise Markov property局部马尔科夫性local Markov property全局马尔科夫性global Markov property表述说明：随机变量Y=(Y1,Y2Ym)构成无向图G=(V,E)，结点v对应的随机变量是Yv。,12,考察结点间的独立性,13,成对马尔科夫性,设u和v是无向图G中任意两个没有边直接连接的结点，G中其他结点的集合记做O；则在给定随机变量Yo的条件下，随机变量Yu和Yv条件独立。即：P(Yu,Yv|Yo)=P(Yu|Yo)*P(Yv|Yo),14,局部马尔科夫性,设v是无向图G中任意一个结点，W是与v有边相连的所有结点，G中其他结点记做O；则在给定随机变量Yw的条件下，随机变量Yv和Yo条件独立。即：P(Yv,Yo|Yw)=P(Yv|Yw)*P(Yo|Yw),15,全局马尔科夫性,设结点集合A，B是在无向图G中被结点集合C分开的任意结点集合，则在给定随机变量YC的条件下，随机变量YA和YB条件独立。即：P(YA,YB|YC)=P(YA|YC)*P(YB|YC),16,三个性质的等价性,根据全局马尔科夫性，能够得到局部马尔科夫性；根据局部马尔科夫性，能够得到成对马尔科夫性；根据成对马尔科夫性，能够得到全局马尔科夫性；可以反向思考：满足这三个性质(或其一)的无向图，称为概率无向图模型。,17,复习：隐马尔科夫模型,18,HMM的确定,HMM由初始概率分布、状态转移概率分布A以及观测概率分布B确定。,19,HMM的参数,Q是所有可能的状态的集合N是可能的状态数V是所有可能的观测的集合M是可能的观测数,20,HMM的参数,I是长度为T的状态序列，O是对应的观测序列A是状态转移概率矩阵其中aij是在时刻t处于状态qi的条件下时刻t+1转移到状态qj的概率。,21,HMM的参数,B是观测概率矩阵其中，bik是在时刻t处于状态qi的条件下生成观测vk的概率。是初始状态概率向量：其中，i是时刻t=1处于状态qi的概率。,22,HMM的参数总结,HMM由初始概率分布、状态转移概率分布A以及观测概率分布B确定。和A决定状态序列，B决定观测序列。因此，HMM可以用三元符号表示，称为HMM的三要素：,23,HMM的两个基本性质,齐次假设：观测独立性假设：,24,HMM的3个基本问题,概率计算问题给定模型 和观测序列，计算模型下观测序列O出现的概率P(O|)学习问题已知观测序列，估计模型 的参数，使得在该模型下观测序列P(O|)最大预测问题即解码问题：已知模型 和观测序列，求对给定观测序列条件概率P(I|O)最大的状态序列I,25,概率计算问题,直接算法暴力算法前向算法后向算法这二者是理解HMM的算法重点,26,直接计算法,按照概率公式，列举所有可能的长度为T的状态序列，求各个状态序列I与观测序列 的联合概率P(O,I|)，然后对所有可能的状态序列求和，从而得到P(O|),27,直接计算法,状态序列 的概率是：对固定的状态序列I，观测序列O的概率是：,28,直接计算法,O和I同时出现的联合概率是：对所有可能的状态序列I求和，得到观测序列O的概率P(O|),29,直接计算法,对于最终式分析：加和符号中有2T个因子，I的遍历个数为NT，因此，时间复杂度为O(T NT)，过高。,30,前向算法,定义：给定，定义到时刻t部分观测序列为o1,o2ot且状态为qi的概率为前向概率，记做：可以递推的求得前向概率t(i)及观测序列概率P(O|),31,前向算法,初值：递推：对于t=1,2T-1最终：,32,后向算法,定义：给定，定义到时刻t状态为qi的前提下，从t+1到T的部分观测序列为ot+1,ot+2oT的概率为后向概率，记做：可以递推的求得后向概率t(i)及观测序列概率P(O|),33,后向算法,初值：递推：对于t=T-1,T-2,1最终：,34,后向算法的说明,为了计算在时刻t状态为qi条件下时刻t+1之后的观测序列为ot+1,ot+2oT的后向概率t(i)，只需要考虑在时刻t+1所有可能的N个状态qj的转移概率(aij项)，以及在此状态下的观测ot+1的观测概率(bjot+1)项，然后考虑状态qj之后的观测序列的后向概率t+1(j),35,前向后向概率的关系,根据定义，证明下列等式,36,单个状态的概率,求给定模型和观测O，在时刻t处于状态qi的概率。记：,37,单个状态的概率,根据前向后向概率的定义，,38,的意义,在每个时刻t选择在该时刻最有可能出现的状态it*，从而得到一个状态序列I*=i1*,i2*iT*，将它作为预测的结果。给定模型和观测序列，时刻t处于状态qi的概率为：,39,两个状态的联合概率,求给定模型和观测O，在时刻t处于状态qi并且时刻t+1处于状态qj的概率。,40,两个状态的联合概率,根据前向后向概率的定义，,41,期望,在观测O下状态i出现的期望：在观测O下状态i转移到状态j的期望：,42,学习算法,若训练数据包括观测序列和状态序列，则HMM的学习非常简单，是监督性学习；若训练数据只有观测序列，则HMM的学习需要使用EM算法，是非监督学习。,43,再次分析二项分布的参数估计,极大似然估计简单的例子10次抛硬币的结果是：正正反正正正反反正正假设p是每次抛硬币结果为正的概率。则：得到这样的实验结果的概率是：,44,极大似然估计MLE,目标函数：最优解是：p=0.7即：使用样本的均值可以作为全体的均值估计一般形式：,45,直接推广上述结论,假设已给定训练数据包含S个长度相同的观测序列和对应的状态序列(O1,I1),(O2,I2)(Os,Is)，那么，可以直接利用极大似然估计的上述结论，给出HMM的参数估计。,46,监督学习方法,转移概率aij的估计：设样本中时刻t处于状态i时刻t+1转移到状态j的频数为Aij，则观测概率bik的估计：设样本中状态i并观测为k的频数为Bik，则初始状态概率i的估计为S个样本中初始状态为qi的概率。,47,Baum-Welch算法,若训练数据只有观测序列，则HMM的学习需要使用EM算法，是非监督学习。,48,Baum-Welch算法,所有观测数据写成O=(o1,o2oT)，所有隐数据写成I=(i1,i2iT)，完全数据是(O,I)=(o1,o2oT,i1,i2iT)，完全数据的对数似然函数是lnP(O,I|)假设 是HMM参数的当前估计值，为待求的参数。,49,EM过程,根据函数可写成,50,极大化,极大化Q，求的参数A,B,由于该三个参数分别位于三个项中，可分别极大化注意到i满足加和为1，利用拉格朗日乘子法，得到：,51,初始状态概率,对上式相对于i求偏导，得到：对i求和，得到：从而得到初始状态概率：,52,转移概率和观测概率,第二项可写成：仍然使用拉格朗日乘子法，得到同理，得到：,53,预测算法,近似算法Viterbi算法,54,预测的近似算法,在每个时刻t选择在该时刻最有可能出现的状态it*，从而得到一个状态序列I*=i1*,i2*iT*，将它作为预测的结果。给定模型和观测序列，时刻t处于状态qi的概率为：选择概率最大的i作为最有可能的状态会出现此状态在实际中可能不会发生的情况,55,Viterbi算法,Viterbi算法实际是用动态规划解HMM预测问题，用DP求概率最大的路径(最优路径)，这是一条路径对应一个状态序列。定义变量i(t)：在时刻t状态为i的所有路径中，概率的最大值。,56,Viterbi算法,定义：递推：终止：,57,团,无向图G中任何两个结点均有边连接的子集，称作G的团(Clique)。若C是G的一个团，并且不能再加入任何一个G的结点使其称为团，则C称作G的最大团(Maximal Clique)。,58,下图的最大团是什么？,59,Hammersley-Clifford定理,UGM的联合分布可以表示成最大团上的随机变量的函数的乘积的形式；这个操作叫做UGM的因子分解(Factorization)。,60,Hammersley-Clifford定理,UGM的联合概率分布P(Y)可以表示成如下形式：其中，C是G的最大团，是C上定义的严格正函数，乘积是在UGM所有的最大团上进行的，被称作势函数(Potential Function)。,61,线性链条件随机场,设X=(X1,X2Xn)和Y=(Y1,Y2Ym)都是联合随机变量，若随机变量Y构成一个无向图 G=(V,E)表示的马尔科夫随机场(MRF)，则条件概率分布P(Y|X)称为条件随机场(Conditional Random Field,CRF)即：其中，表示与结点v相连的所有结点w一种重要而特殊的CRF是线性链条件随机场(Linear Chain Conditional Random Field)，可用于标注等问题。这时，条件概率P(Y|X)中，Y表示标记序列（或称状态序列），X是需要标注的观测序列。,62,线性链条件随机场,线性链条件随机场的无向图模型,63,线性链条件随机场的定义,设X=(X1,X2Xn)，Y=(Y1,Y2Yn)均为线性链表示的随机变量序列，若在给定随机变量序列X的条件下，随机变量序列Y的条件概率分布P(Y|X)构成条件随机场，即满足马尔科夫性则称P(Y|X)为线性链条件随机场。在标注问题中，X表示观测序列，Y表述对应的输出标记序列或称状态序列。,64,线性链条件随机场的参数化形式,设P(Y|X)为线性链条件随机场，则在随机变量X取值为x的条件下，随机变量Y取值为y的条件概率有以下形式：其中，上式中，tk和sl是特征函数，kl是对应的权值，Z(x)是规范化因子。,65,参数说明,tk是定义在边上的特征函数，称为转移特征，依赖于当前和前一个位置；sl是定义在结点上的特征函数，称为状态特征，依赖于当前位置；tk 和sl都依赖于位置，是局部特征函数；通常，tk 和sl取值为1或者0；满足特征条件时取1，否则取0；CRF完全有特征函数tk、sl和对应的权值kl确定。线性链条件随机场模型属于对数线性模型。,66,例,设有一标注问题：输入观测序列为X=(X1,X2,X3)，输出标记序列为Y=(Y1,Y2,Y3)，Y1,Y2,Y3的取值范围为1,2。,67,例,t2=t2(y1=1,y2=1,x,2)2=0.5t3=t3(y2=2,y3=1,x,3)3=1t4=t4(y1=2,y2=1,x,2)4=1t5=t5(y2=2,y3=2,x,3)5=0.2s1=s1(y1=1,x,1)l=1s2=s2(y2=2,x,i)2=0.5s3=s3(y1=1,x,i)3=0.8s4=s4(y3=2,x,i)4=0.5,68,CRF的简化形式,为方便起见，将转移特征和状态特征及其权值同统一的符号表示。设有K1个转移特征，K2个状态特征，K=K1+K2，则在各个位置求和:,69,CRF的简化形式,用w表示统一的权值：则CRF可表示成：,70,CRF的简化形式,以F(y,x)表示全局特征向量：则CRF可以写成向量内积的形式：,71,CRF的矩阵形式,引入特殊的起点、终点标记：y0=start,yn+1=stop定义m阶矩阵(m是标记yi取值的个数),72,CRF的矩阵形式,条件概率P(y|x)为：其中，Z(x)是归一化因子：,73,CRF的两个问题,CRF的概率计算问题前向后向算法CRF的预测算法Viterbi算法,74,CRF的概率计算问题,给定条件随机场P(Y|X)，输入序列x和输出序列y，计算条件概率P(Yi=yi|x)，P(Yi=yi,Yi=yi|x)前向后向算法,75,前向向量,i(yi|x)：在位置i的标记是yi并且到位置i的前部分标记序列的非规范化概率。yi可取的值有m个：i(yi|x)是m维列向量,76,前向向量,初始化：,77,后向向量,i(yi|x)：在位置i的标记是yi并且从i+1到n的后部分标记序列的非规范化概率。yi可取的值有m个：i(yi|x)是m维列向量,78,后向向量,初始化：,79,归一化因子,归一化因子Z(x)：,80,概率计算,条件概率P(Yi=yi|x)，P(Yi=yi,Yi=yi|x)分别为：,81,预测算法,CRF的预测问题，是给定条件随机场P(Y|X)和输入序列(观测序列)x，求条件概率最大的输出序列(标记序列)y*，即对观测序列进行标注。Viterbi算法,82,最优路径的目标函数,根据推导：CFR的预测问题即非规范化概率最大的最优路径问题。,83,最优路径的目标函数,其中，,84,最优路径的目标函数,目标函数：其中：,85,Viterbi算法,定义：位置i的各个标记l=1,2,m的非规范化概率的最大值。,86,参考文献,Machine Learning:A Probabilistic Perspective,Kevin P.Murphy,The MIT Press,2012Conditional Random Fields:An Introduction,Hanna M.Wallach,2004An Introduction to Conditional Random Fields,Charles Sutton,Andrew McCallum,2012统计学习方法，李航著，清华大学出版社，2012年Pattern Recognition and Machine Learning Chapter 13,Bishop M,Springer-Verlag,2006Radiner L,Juang B.An introduction of hidden markov Models.IEEE ASSP Magazine,January 1986,87,感谢大家！恳请大家批评指正！,
