条件随机场

条件随机场ConditionalRandomFields条件随机场模型是Lafferty等人于2001年在最大熵模型和隐马尔可夫模型的基础上提出的一种无向图学习模型，是一种用于标注和切分有序数据的条件概率模型。条件随机场概述CRF最早是针对序列数据分析提出的，现已成功应用于自然语言处理、生物信息学、机器视觉及网络智能等领域。目前基于CRFs的主要系统实现有CRF，FlexCRF，CRF++序列标注[PRPHe][VBZreckons][DTthe][JJcurrent][NNaccount][NNdeficit][MDwill][VBnarrow][TOto][RBonly][##][CD1.8][CDbillion][INin][NNPSeptember][..][He][reckons][the][current][account][deficit][will][narrow][to][only][#][1.8][billion][in][September][.]原句标注后产生式模型和判别式模型•产生式模型(Generative)：构建o和s的联合分布p(s,o)，如HMM，BNs，MRF。产生式模型：无穷样本==》概率密度模型=产生模型==》预测判别式模型：有限样本==》判别函数=预测模型==》预测•判别式模型(Discriminative)：构建o和s的条件分布p(s|o)，如SVM，CRF，MEMM。两种模型比较：产生式模型和判别式模型Generativemodel：从统计的角度表示数据的分布情况，能够反映同类数据本身的相似度，不关心判别边界。优点:•实际上带的信息要比判别模型丰富，研究单类问题比判别模型灵活性强•能更充分的利用先验知识•模型可以通过增量学习得到缺点：•学习过程比较复杂•在目标分类问题中易产生较大的错误率产生式模型和判别式模型两种模型比较：Discriminativemodel：寻找不同类别之间的最优分类面，反映的是异类数据之间的差异。优点:•分类边界更灵活，比使用纯概率方法或生产模型得到的更高级。•能清晰的分辨出多类或某一类与其他类之间的差异特征•适用于较多类别的识别缺点：•不能反映训练数据本身的特性。二者关系：由产生式模型可以得到判别式模型，但由判别式模型得不到产生式模型。隐马尔可夫模型(HMM))|()|(),(11iiNiiiyxPyyPYXPHMM是一个五元组λ=(Y,X,π,A,B)，其中Y是状态（输出）的集合，X是观察值（输入）集合，π是初始状态的概率，A是状态转移概率矩阵，B是输出观察值概率矩阵。隐马尔可夫模型(HMM)模型定义的是联合概率，必须列举所有观察序列的可能值，这对多数领域来说是比较困难的。基于观察序列中的每个元素都相互条件独立。即在任何时刻观察值仅仅与状态（即要标注的标签）有关。大多数现实世界中的真实观察序列是由多个相互作用的特征和观察序列中较长范围内的元素之间的依赖而形成的。隐马尔可夫模型的局限性：概率图模型概率图模型：是一类用图的形式表示随机变量之间条件依赖关系的概率模型。是概率论与图论的结合。(,)GVE:V顶点/节点，表示随机变量:E边/弧，表示随机变量间的条件依赖关系概率图模型根据图中边有无方向，常用的概率图模型分为两类：无向图：亦称马尔可夫随机场(MarkovRandomFields,MRF’s)或马尔可夫网络(MarkovNetworks)有向图：亦称贝叶斯网络(BayesianNetworks)或信念网络(BeliefNetworks,BN’s).概率图模型1X2X3X4X5X121(,)(())NNiiiPXXXpXX，，有向图的联合概率分布：1251213242534(,)()()()()()PXXXpXpXXpXXpXXpXXX，，图中概率如下概率图模型尽管在给定每个节点的条件下，分配给该节点一个条件概率是可能的，无向图的无向性导致我们不能用条件概率参数化表示联合概率，而要从一组条件独立的原则中找出一系列局部函数的乘积来表示联合概率。最简单的局部函数是定义在图结构中的团(clique)上的势函数(Potentialfunction)，并且是严格正实值的函数形式。无向图模型概率图模型clique:无向图中的最大全联通子图图中的clique：{X1,X2},{X1,X3}{X3,X4},{X2,X4,X5}概率图模型potentialfunction:对应于无向图中clique的非负函数，用于计算clique中随机变量的联合概率的相对值。无向图模型的联合概率分布：1211(,)()NNiiiPXXXCZ，，12,1()NNiiXXXiZC，，},,,,{542443331221154244333122115432154321)},,(),(),(),({),,(),(),(),(),,,,(XXXXXXXXXXXXXXXXXXXXXXXXXXXXP随机场随机场可以看成是定义在同一样本空间上的一组随机变量的集合。马尔科夫随机场（MRF）具有马尔可夫性质的随机场，对应一个无向图模型。MRF的结构本质上反应了我们的先验知识——哪些变量之间有依赖关系需要考虑，而哪些可以忽略。(X1,X2,X3….Xn-1,Xn)条件随机场如果给定的MRF中每个随机变量下面还有观察值，我们要确定的是给定观察集合下，这个MRF的分布，也就是条件分布，那么这个MRF就称为CRF。它的条件分布形式完全类似于MRF的分布形式，只不过多了一个观察集合x。从通用角度来看，CRF本质上是给定了观察值(observations)集合的MRF。条件随机场CRF定义：设G=（V，E）是一个无向图，vYYvV是以G中节点为索引的随机变量构成的集合。在给定X的条件下，如果每个随机变量服从马尔可夫属性即u~v表示u和v是相邻的边，则就构成一个条件随机场。vYvY,XY),,|(),,|(~vuYXYPvuYXYPuvuv条件随机场CRFs是在给定需要标记的观察序列的条件下，计算整个标记序列的联合概率，即求条件分布：P(Y|O)，而不是在给定当前状态条件下，定义下一个状态的分布(HMM),即求联合分布：P(Y,O)1iyiy1iy1ixix1ixLinear-chainCRFs模型：条件随机场令表示观察序列12,,,nxxxx12,,,nyyyy是有限状态的集合根据随机场的基本理论：1,exp(,,,)(,,)jjiikkijkpyxtyyxisyxi1(,,,):jiityyxi对于观察序列的标记位置i-1与i之间的转移特征函数(,,):kisyxi观察序列的i位置的状态特征函数条件随机场将两个特征函数统一为：1(,,,)jiifyyxi111,exp(,,,)()njjiiijpyxfyyxiZx则有：11()exp(,,,)njjiijijZxfyyxi其中：条件随机场关键问题1.特征函数的选择2.参数估计3.模型推断特征函数的选取直接关系模型的性能从已经标注好的训练数据集学习条件随机场模型的参数，即各特征函数的权重向量λ在给定条件随机场模型参数λ下，预测出最可能的状态序列。条件随机场1.特征函数的选择CRFs模型中特征函数的形式定义：它是状态特征函数和转移特征函数的统一形式表示。特征函数通常是二值函数，取值要么为1要么为0在定义特征函数的时候，首先构建观察序列的实数值特征b(x,i)集合来描述训练数据的经验分布特征。例如：1(,)0bxi如果时刻i观察值x是大写开头otherwise1(,,,)jiifyyxi条件随机场1.特征函数的选择每个特征函数表示为观察序列的实数值特征b(x,i)集合中的一个元素，如果前一个状态和当前状态具有特定的值，则所有的特征函数都是实数值11(,),(,,,)0iiiibxiifytitleyauthorfyyxiotherwise条件随机场2.参数估计建立条件随机场模型的主要任务是从训练数据中估计特征的权重λ假设给定训练集{(X1,Y1),(X2,Y2),,(Xn,Yn)}对参数λ估计采用极大似然估计法。条件概率p(y|x,λ)的对数似然函数形式为：1,1()(,)((,,,))()log()njjiixyijxLpxyfyyxipxZx2.参数估计条件随机场(,)pxy其中：是随机变量x在训练样本中的经验分布样本空间的容量数在样本中同时出现的次),(),(~yxyxP)(~xP为训练样本中(x,y)的经验概率样本空间的容量在样本中出现的次数)(~xxP2.参数估计条件随机场11,1,1()(,)(,,)()(,)(,,)nnjiijiixyixyijLpxyfyyxpxpyxfyyx分别对对似然函数L(λ)中的j令上式等于0，求出j上述方法直接使用对数最大似然估计，可能会发生过度学习问题，通常引入惩罚函数的方法解决这一问题。2.参数估计条件随机场由于极大似然估计并不一定能得倒一个近似解，因而需要利用一些迭代技术来选择参数，使对数似然函数最大化。使用惩罚项222jj对数似然函数公式变为：xjjyxnijiijjxZxpixyyfyxpL22,112)(log)(~)),,,((),(~)(对上式中每个求偏导，并令结果为0，求jj2.参数估计条件随机场Lafferty提出两个迭代缩放的算法用于估计条件随机场的极大似然参数GIS算法（GeneralisedIterativeScaling）IIS算法（ImprovedIterativeScaling）3.模型推断条件随机场111,exp(,,,)()njjiiijpyxfyyxiZx对于一个给定观察序列x(x1,x2,x3…..,xn),求使得该观察序列出现概率最大的标记序列(状态序列)y(y1,y2,y3……,yn)。对比HMM第二个问题。11()exp(,,,)njjiijijZxfyyxi3.模型推断条件随机场对于一个链式条件随机场，在图的模型中添加一个开始状态和一个结束状态0Y1nY定义一组矩阵{|i=1,2,,n+1}，其中每个是N×N阶的随机变量矩阵。中的每个元素定义如下:)(xMi)(xMi)(xMi)|,(1xyyMiii)|,(1xyyyyMiiinijiijjixyyf11),,,(expkikkkiikkixysxiyyt),,()),,(exp(13.模型推断条件随机场))|()|,(exp()|,(331312kkkkkkxysxyytxyyM3.模型推断条件随机场因为p(y|x,λ)实际上是从开始节点到结点节点的一条路径的概率，所以有：111)|,()(1),|(niiiixyyMxZxyP11)()(niixMxZ其中Z(x)为归一化因子，为所有路径概率的和，表达式如下：条件随机场CRF简单评价：条件随机场使用一种概率图模型，具有表达长距离依赖性和交叠性特征的能力，能够较好地解决标注（分类）偏置等问题的优点，而且所有特征可以进行全局归一化，能够求得全局的最优解。缺点：模型训练时收敛速度比较慢。条件随机场CRF应用领域：条件随机场的本质是通过给定的观察序列求一组对应的状态序列的过程。词性标注机器翻译语音识别动作识别……….条件随机场CRF研究方向：1.复杂拓扑结构的CRF(skip-CRFs,层叠CRFs)2.模型训练和推断的快速算法3.CRF模型特征的选择和归纳条件随机场参考文献：AnIntroductiontoConditionalRandomFieldsforRe