条件随机场CRF课件.ppt

1、1条件随机场CRF北京10月机器学习班 邹博 2014年12月14日2思考：给定文本标注词性o他估算当前的赤字总额在9月份仅仅降低到18亿。oNN、NNS、NNP、NNPS、PRP、DT、JJ分别代表普通名词单数形式、普通名词复数形式、专有名词单数形式、专有名词复数形式、代词、限定词、形容词3复习：Markov Blanketo一个结点的Markov Blanket是一个集合，在这个集合中的结点都给定的条件下，该结点条件独立于其他所有结点。o即：一个结点的Markov Blanket是它的parents,children以及spouses(孩子的其他parent)4Markov Blanket

2、补充知识：Serum Calcium(血清钙浓度)高于2.75mmo1/L即为高钙血症。许多恶性肿瘤可并发高钙血症。以乳腺癌、骨肿瘤、肺癌、胃癌、卵巢癌、多发性骨髓瘤、急性淋巴细胞白血病等较为多见，其中乳腺癌约1/3 可发生高钙血症。毒素5图像模型o考察X8的马尔科夫毯(Markov blanket)6无向图模型o有向图模型，又称作贝叶斯网络(Directed Graphical Models,DGM,Bayesian Network)o在有些情况下，强制对某些结点之间的边增加方向是不合适的。o使用没有方向的无向边，形成了无向图模型(Undirected Graphical Model,UGM

3、),又被称为 马尔科夫随机场或者马尔科夫网络(Markov Random Field,MRF or Markov network)7条件随机场o设X=(X1,X2Xn)和Y=(Y1,Y2Ym)都是联合随机变量，若随机变量Y构成一个无向图 G=(V,E)表示的马尔科夫随机场(MRF)，则条件概率分布P(Y|X)称为条件随机场(Conditional Random Field,CRF)o注：大量文献将MRF和CRF混用，包括经典著作。后面将考察为何会有该混用。8DGM转换成UGM9DGM转换成UGM10条件独立的破坏o靠考察是否有 ，则计算U的祖先图(ancestral graph)：11MRF的

4、性质o成对马尔科夫性nparewise Markov propertyo局部马尔科夫性nlocal Markov propertyo全局马尔科夫性nglobal Markov propertyo表述说明：随机变量Y=(Y1,Y2Ym)构成无向图G=(V,E)，结点v对应的随机变量是Yv。12考察结点间的独立性13成对马尔科夫性o设u和v是无向图G中任意两个没有边直接连接的结点，G中其他结点的集合记做O；则在给定随机变量Yo的条件下，随机变量Yu和Yv条件独立。o即：P(Yu,Yv|Yo)=P(Yu|Yo)*P(Yv|Yo)14局部马尔科夫性o设v是无向图G中任意一个结点，W是与v有边相连的所有

5、结点，G中其他结点记做O；则在给定随机变量Yw的条件下，随机变量Yv和Yo条件独立。o即：P(Yv,Yo|Yw)=P(Yv|Yw)*P(Yo|Yw)15全局马尔科夫性o设结点集合A，B是在无向图G中被结点集合C分开的任意结点集合，则在给定随机变量YC的条件下，随机变量YA和YB条件独立。o即：P(YA,YB|YC)=P(YA|YC)*P(YB|YC)16三个性质的等价性o根据全局马尔科夫性，能够得到局部马尔科夫性；o根据局部马尔科夫性，能够得到成对马尔科夫性；o根据成对马尔科夫性，能够得到全局马尔科夫性；o可以反向思考：满足这三个性质(或其一)的无向图，称为概率无向图模型。17复习：隐马尔科夫

6、模型18HMM的确定oHMM由初始概率分布、状态转移概率分布A以及观测概率分布B确定。,BA,BA19HMM的参数oQ是所有可能的状态的集合nN是可能的状态数oV是所有可能的观测的集合nM是可能的观测数NqqqQ,21MvvvV,2120HMM的参数oI是长度为T的状态序列，O是对应的观测序列oA是状态转移概率矩阵o其中oaij是在时刻t处于状态qi的条件下时刻t+1转移到状态qj的概率。TiiiI,21ToooO,21 NNijaAitjtijqiqiPa1TiiiI,2121HMM的参数oB是观测概率矩阵o其中，nbik是在时刻t处于状态qi的条件下生成观测vk的概率。o是初始状态概率向量

7、：o其中，ni是时刻t=1处于状态qi的概率。MNikbBitktikqivoPb iiiqiP122HMM的参数总结oHMM由初始概率分布、状态转移概率分布A以及观测概率分布B确定。和A决定状态序列，B决定观测序列。因此，HMM可以用三元符号表示，称为HMM的三要素：,BA,BA23HMM的两个基本性质o齐次假设：o观测独立性假设：1112211,tttttttiiPoioioiiPttTTTTtioPoioioioP1111,24HMM的3个基本问题o概率计算问题n给定模型 和观测序列 ，计算模型下观测序列O出现的概率P(O|)o学习问题n已知观测序列 ，估计模型 的参数，使得在该模型下观

8、测序列P(O|)最大o预测问题n即解码问题：已知模型 和观测序列 ，求对给定观测序列条件概率P(I|O)最大的状态序列I,BAToooO,21,BAToooO,21,BAToooO,2125概率计算问题o直接算法n暴力算法o前向算法o后向算法n这二者是理解HMM的算法重点26直接计算法o按照概率公式，列举所有可能的长度为T的状态序列 ，求各个状态序列I与观测序列 的联合概率P(O,I|)，然后对所有可能的状态序列求和，从而得到P(O|)ToooO,21TiiiI,2127直接计算法o状态序列 的概率是：o对固定的状态序列I，观测序列O的概率是：TiiiI,21TToioioibbbIOP221

9、1,TTiiiiiiiaaaIP13221128直接计算法oO和I同时出现的联合概率是：o对所有可能的状态序列I求和，得到观测序列O的概率P(O|)TTTTTiiioiiioiiioiiIIbababIPIOPIOPOP,2112221111,TTTToiiioiiioiibababIPIOPIOP12221111,29直接计算法o对于最终式o分析：加和符号中有2T个因子，I的遍历个数为NT，因此，时间复杂度为O(T NT)，过高。TTTTTiiioiiioiiioiiIIbababIPIOPIOPOP,2112221111,30前向算法o定义：给定，定义到时刻t部分观测序列为o1,o2ot且

10、状态为qi的概率为前向概率，记做：o可以递推的求得前向概率t(i)及观测序列概率P(O|)itttqioooPi,2131前向算法o初值：o递推：对于t=1,2T-1o最终：111tioNjjittbaji NiTiOP1 11ioibi32后向算法o定义：给定，定义到时刻t状态为qi的前提下，从t+1到T的部分观测序列为ot+1,ot+2oT的概率为后向概率，记做：o可以递推的求得后向概率t(i)及观测序列概率P(O|),21itTtttqioooPi33后向算法o初值：o递推：对于t=T-1,T-2,1o最终：Njtjoijtjbait111 NiioiibOP111 1iT34后向算法的

11、说明o为了计算在时刻t状态为qi条件下时刻t+1之后的观测序列为ot+1,ot+2oT的后向概率t(i)，只需要考虑在时刻t+1所有可能的N个状态qj的转移概率(aij项)，以及在此状态下的观测ot+1的观测概率(bjot+1)项，然后考虑状态qj之后的观测序列的后向概率t+1(j)35前向后向概率的关系o根据定义，证明下列等式 NittiiOP1 iiOqiPttit,36单个状态的概率o求给定模型和观测O，在时刻t处于状态qi的概率。o记：,OqiPiitt37单个状态的概率o根据前向后向概率的定义，iiOqiPttit,OPOqiPOqiPiititt,NitttttttiiiiOPii

12、i138的意义o在每个时刻t选择在该时刻最有可能出现的状态it*，从而得到一个状态序列I*=i1*,i2*iT*，将它作为预测的结果。o给定模型和观测序列，时刻t处于状态qi的概率为：NitttttttiiiiOPiii139两个状态的联合概率o求给定模型和观测O，在时刻t处于状态qi并且时刻t+1处于状态qj的概率。,1OqiqiPjijtitt40两个状态的联合概率o根据前向后向概率的定义，NiNjjtitjtitjtitjtittOqiqiPOqiqiPOPOqiqiPOqiqiPji111111,jbaiOqiqiPtjoijtjtitt111,41期望o在观测O下状态i出现的期望：o

13、在观测O下状态i转移到状态j的期望：Ttti111,Tttji42学习算法o若训练数据包括观测序列和状态序列，则HMM的学习非常简单，是监督性学习；o若训练数据只有观测序列，则HMM的学习需要使用EM算法，是非监督学习。43再次分析二项分布的参数估计o极大似然估计o简单的例子n10次抛硬币的结果是：正正反正正正反反正正o假设p是每次抛硬币结果为正的概率。则：o得到这样的实验结果的概率是：371111ppppppppppppP44极大似然估计MLEo目标函数：o最优解是：p=0.7n即：使用样本的均值可以作为全体的均值估计o一般形式：37101maxmaxppPp xxppxpL 是实验结果的分

14、布模型是估计的概率分布xpxp45直接推广上述结论o假设已给定训练数据包含S个长度相同的观测序列和对应的状态序列(O1,I1),(O2,I2)(Os,Is)，那么，可以直接利用极大似然估计的上述结论，给出HMM的参数估计。46监督学习方法o转移概率aij的估计：n设样本中时刻t处于状态i时刻t+1转移到状态j的频数为Aij，则o观测概率bik的估计：n设样本中状态i并观测为k的频数为Bik，则o初始状态概率i的估计为S个样本中初始状态为qi的概率。NjijijijAAa1MkikikikBBb147Baum-Welch算法o若训练数据只有观测序列，则HMM的学习需要使用EM算法，是非监督学习。

15、48Baum-Welch算法o所有观测数据写成O=(o1,o2oT)，所有隐数据写成I=(i1,i2iT)，完全数据是(O,I)=(o1,o2oT,i1,i2iT)，完全数据的对数似然函数是lnP(O,I|)o假设 是HMM参数的当前估计值，为待求的参数。IOPIOPQI,ln,49EM过程o根据o函数可写成 TTTToiiioiiioiibababIPIOPIOP12221111,IOPbIOPaIOPIOPIOPQITtoiITtiiIiItttt,ln,ln,ln,ln,11111 50极大化o极大化Q，求的参数A,B,o由于该三个参数分别位于三个项中，可分别极大化o注意到i满足加和为1

16、，利用拉格朗日乘子法，得到：NiiIiiiOPIOP11,ln,ln111,ln111NiiNiiiiOP51初始状态概率o对上式相对于i求偏导，得到：o对i求和，得到：o从而得到初始状态概率：0,1iiiOPOPOPiiOPi1,52转移概率和观测概率o第二项可写成：o仍然使用拉格朗日乘子法，得到o同理，得到：NiNjTtttijITtiijiiiOPaIOPatt1111111,ln,ln1 111111111,TttTttTttTtttijijiiiOPjiiiOPa TttTvottTttTtkttikiiiiOPvoIiiOPbkt1,111,53预测算法o近似算法oViterbi算

17、法54预测的近似算法o在每个时刻t选择在该时刻最有可能出现的状态it*，从而得到一个状态序列I*=i1*,i2*iT*，将它作为预测的结果。o给定模型和观测序列，时刻t处于状态qi的概率为：o选择概率最大的i作为最有可能的状态n会出现此状态在实际中可能不会发生的情况 NitttttttiiiiOPiii155Viterbi算法oViterbi算法实际是用动态规划解HMM预测问题，用DP求概率最大的路径(最优路径)，这是一条路径对应一个状态序列。o定义变量i(t)：在时刻t状态为i的所有路径中，概率的最大值。56Viterbi算法o定义：o递推：o终止：111,.,.,.,max121ooiii

18、iPitttiiitt 12111111,.,1max,.,.,maxttiojitNjtttiiitbajooiiiiPi iPTNi1*max 11ioibi57团o无向图G中任何两个结点均有边连接的子集，称作G的团(Clique)。若C是G的一个团，并且不能再加入任何一个G的结点使其称为团，则C称作G的最大团(Maximal Clique)。58下图的最大团是什么？59Hammersley-Clifford定理oUGM的联合分布可以表示成最大团上的随机变量的函数的乘积的形式；这个操作叫做UGM的因子分解(Factorization)。60Hammersley-Clifford定理oUGM

19、的联合概率分布P(Y)可以表示成如下形式：o其中，C是G的最大团，是C上定义的严格正函数，乘积是在UGM所有的最大团上进行的，被称作势函数(Potential Function)。cccYZYP1 YcccYZ ccY61线性链条件随机场o设X=(X1,X2Xn)和Y=(Y1,Y2Ym)都是联合随机变量，若随机变量Y构成一个无向图 G=(V,E)表示的马尔科夫随机场(MRF)，则条件概率分布P(Y|X)称为条件随机场(Conditional Random Field,CRF)o即：o其中，表示与结点v相连的所有结点wo一种重要而特殊的CRF是线性链条件随机场(Linear Chain Cond

20、itional Random Field)，可用于标注等问题。这时，条件概率P(Y|X)中，Y表示标记序列（或称状态序列），X是需要标注的观测序列。vwYXYPvwYXYPwvwv,vw 62线性链条件随机场o线性链条件随机场的无向图模型63线性链条件随机场的定义o设X=(X1,X2Xn)，Y=(Y1,Y2Yn)均为线性链表示的随机变量序列，若在给定随机变量序列X的条件下，随机变量序列Y的条件概率分布P(Y|X)构成条件随机场，即满足马尔科夫性o则称P(Y|X)为线性链条件随机场。在标注问题中，X表示观测序列，Y表述对应的输出标记序列或称状态序列。1121,iiiniYYXYPYYYXYP64

21、线性链条件随机场的参数化形式o设P(Y|X)为线性链条件随机场，则在随机变量X取值为x的条件下，随机变量Y取值为y的条件概率有以下形式：o其中，o上式中，tk和sl是特征函数，kl是对应的权值，Z(x)是规范化因子。kiliilliikkixysixyytxZxyP,1,exp1 ykiliilliikkixysixyytxZ,1,exp65参数说明otk是定义在边上的特征函数，称为转移特征，依赖于当前和前一个位置；osl是定义在结点上的特征函数，称为状态特征，依赖于当前位置；otk 和sl都依赖于位置，是局部特征函数；o通常，tk 和sl取值为1或者0；满足特征条件时取1，否则取0；oCRF

22、完全有特征函数tk、sl和对应的权值kl确定。o线性链条件随机场模型属于对数线性模型。66例o设有一标注问题：输入观测序列为X=(X1,X2,X3)，输出标记序列为Y=(Y1,Y2,Y3)，Y1,Y2,Y3的取值范围为1,2。67例ot2=t2(y1=1,y2=1,x,2)2=0.5ot3=t3(y2=2,y3=1,x,3)3=1ot4=t4(y1=2,y2=1,x,2)4=1ot5=t5(y2=2,y3=2,x,3)5=0.2os1=s1(y1=1,x,1)l=1os2=s2(y2=2,x,i)2=0.5os3=s3(y1=1,x,i)3=0.8os4=s4(y3=2,x,i)4=0.568

23、CRF的简化形式o为方便起见，将转移特征和状态特征及其权值同统一的符号表示。o设有K1个转移特征，K2个状态特征，K=K1+K2，则o在各个位置求和:21111,2,1;,2,1,KllKkixysKkixyytixyyfiliikiikKkixyyfxyfniiikk,2,1,1169CRF的简化形式o用w表示统一的权值：o则CRF可表示成：yKkkkxyfwxZ1,expKwwww21 KkkkxyfwxZxyP1,exp170CRF的简化形式o以F(y,x)表示全局特征向量：o则CRF可以写成向量内积的形式：xyfxyfxyfxyFK,21 yTwxyFwxZ,exp xZxyFwxyP

24、T,exp71CRF的矩阵形式o引入特殊的起点、终点标记：oy0=start,yn+1=stopo定义m阶矩阵(m是标记yi取值的个数)KiiikkiiiixyyfwxyyW111,xyyMxMiiii,1xyyWxyyMiiiiii,exp,1172CRF的矩阵形式o条件概率P(y|x)为：o其中，Z(x)是归一化因子：111,1niiiiwwxyyMxZxyP stopstartnwxMxMxMxZ,12173CRF的两个问题oCRF的概率计算问题n前向后向算法oCRF的预测算法nViterbi算法 74CRF的概率计算问题o给定条件随机场P(Y|X)，输入序列x和输出序列y，计算条件概率

25、P(Yi=yi|x)，P(Yi=yi,Yi=yi|x)n前向后向算法75前向向量oi(yi|x)：在位置i的标记是yi并且到位置i的前部分标记序列的非规范化概率。nyi可取的值有m个：i(yi|x)是m维列向量xyyMxyxyiiiiTiiTi,111 xMxxiTiTi176前向向量o初始化：startystartyxy00000177后向向量oi(yi|x)：在位置i的标记是yi并且从i+1到n的后部分标记序列的非规范化概率。nyi可取的值有m个：i(yi|x)是m维列向量xyxyyMxyiiiiiii111,xxMxiii1178后向向量o初始化：stopystopyxynnnn1111

26、0179归一化因子o归一化因子Z(x)：xxxZTTn11180概率计算o条件概率P(Yi=yi|x)，P(Yi=yi,Yi=yi|x)分别为：xZxyxyxyYPiiiTiii xZxyxyyMxyxyYyYPiiiiiiTiiiii,1111181预测算法oCRF的预测问题，是给定条件随机场P(Y|X)和输入序列(观测序列)x，求条件概率最大的输出序列(标记序列)y*，即对观测序列进行标注。nViterbi算法82最优路径的目标函数o根据推导：oCFR的预测问题即非规范化概率最大的最优路径问题。xywFxywFxZxywFxyPyyywywy,maxarg,expmaxarg,expmaxarg|maxarg*83最优路径的目标函数o其中，Kwwww21xyfxyfxyfxyFK,21niiikkixyyfxyf11,84最优路径的目标函数o目标函数：o其中：ixyyfixyyfixyyfxyyFiiKiiiiiii,112111niiiiyxyyFw11,max85Viterbi算法o定义：位置i的各个标记l=1,2,m的非规范化概率的最大值。mlxlyjyFwjliiiimji,2,1,max111 mjxjystartyFwj,2,1,1011 jynmjn1*maxarg