CRF基础知识学习

2017-10-24条件随机场ConditionalRandomFields内容隐马尔可夫模型最大熵模型条件随机场模型隐马尔可夫模型隐马尔可夫模型(HiddenMarkovModel，HMM)是统计模型，它用来描述一个含有隐含未知参数的马尔可夫过程。其难点是从可观察的参数中确定该过程的隐含参数。然后利用这些参数来作进一步分析，例如模式识别。离散马尔可夫过程设有N个不同状态的随机过程，令t=1,2,…表示不同的时间点，表示时刻随机过程所处的状态，表示状态到的转移概率。当随机过程满足：当前所处的状态仅与它之前的一个状态有关，即时，该随机过程为马尔可夫随机过程。隐马尔可夫模型一个完整的隐马尔可夫模型要求两个具体的模型参数N和M，和三个概率矩阵A,B,π，也即隐马尔可夫模型可形式化定义为一个五元组(N,M,A,B,π)。1）模型中的状态数N。模型中的各个状态是相互连结的，任何状态能从其它状态到达。用S表示各个状态的集合，，表示t时刻的状态。2）模型中各状态不同的观察符号，即输出字符个数M。V表示各字符集合，。3）状态转移概率分布A。，其中，，当从状态经一步到达时，。4）观察字符在状态j时的概率分布B，，其中。，。5）初始状态分布π，，其中，。给定N，M，A，B，π，HMMs能输出一个观察字符的序列，其中，T是观察序列的字符个数。隐马尔可夫模型隐马可尔可夫模型是一个生成模型，给定一个观察序列，HMMs模型隐含一个与观察序列对应的状态序列。下图为隐马尔可夫模型：上图表示出HMMs内部的条件独立关系，HMMs有三个独立性假设：一是t时刻的状态只依赖于t−1时刻的状态，即。二是t时刻生成的值只依赖于t时刻的状态，即。三是状态与具体时间无关，即对任意的i和j都有。隐马尔可夫模型HMMs的三个基本问题1）给定一个模型λ=(N,M,A,B,π)，如何高效计算某输出字符序列的概率P(O|λ)。2）给定一个模型λ=(N,M,A,B,π)和一个输出字符序列，如何找到产生这一序列概率最大的状态序列。3）给定一个模型λ=(N,M,A,B,π)和一个输出字符序列，如何调整模型的参数使得产生这一序列的概率最大。隐马尔可夫模型HMMs的三个基本解决方法问题1是一个评价问题，即给定一个模型λ和一个观察序列，如何计算由模型产生这一观察序列的概率P(O|λ)，可采用forward-backward算法解决。forward-backward过程：定义forward变量为,即对于模型λ，在t时刻，状态为时的部分观察序列的概率记为为部分观察序列和t时刻的状态的联合分布概率，则可递归得到。12()(,,,)1tttiPxxxyitT　　　11()()1iiibxtT　　　111()[()]()11,1NttijjtijiabxtTjN　　　1(/)()NTiPXi终结：递归：定义前向变量：初始化：forward算法：隐马尔可夫模型隐马尔可夫模型HMMs的三个基本解决方法由各个观察字符的输出状态相互独立，下面给出的递推过程：终结：递归：定义前向变量：初始化：backward算法：隐马尔可夫模型12()(,,,/)11tttTtiPxxxyitT　　　()11TiiN　　　111()()()1,2,...,1,1NtijjttjiabxjtTTiN　11(/)()NiPXi隐马尔可夫模型HMMs的三个基本解决方法问题2是一个解码问题，给定一个模型λ=(N,M,A,B,π)和一个输出字符序列，如何找到产生这一序列概率最大的状态序列，即从个可能的状态序列中找到一个“最优”的状态序列，其中N是HMMs模型中状态的个数，T是观察序列的长度。对于问题2根据不同的“最优”标准，可以有若干个解决方案，所以给定观察序列，找出“最优”状态序列的困难是最优状态序列的定义，即最优标准的选择。一个有效的查找最优路径的算法是Viterbi算法，它基于动态规划方法。隐马尔可夫模型HMMs的三个基本解决方法Viterbi算法：给定观察序列，利用Viterbi算法可以有效率的找到一个最优的状态序列，计算量为，我们定义表示t时刻状态时的最优状态序列和前t个观察序列的联合概率：由t时刻状态时的最优状态序列和前t个观察序列的联合概率可递推得到时刻状态时的最优状态序列和前t+1个观察序列的联合概率：隐马尔可夫模型HMMs的三个基本解决方法Viterbi算法：初始化递归结束得到最优路径11()()iiibx111()max()()ttijjtiNjiabx)(max1iPTNi111()argmax()()ttijjtiNjiabx1argmax()TTiNyi11(),1,,1tttyytT0)(1i隐马尔可夫模型HMMs的三个基本解决方法问题3是模型参数估计问题。给定观察序列Ο，调整模型的参数使得在给定模型λ的条件下该观察序列的概率P(Ο|λ)最大，可以用Baum-Welch方法（等价于EM(Expectation-Modification)方法）或者用梯度技术，通过不断循环迭代更新参数的方法，设法使P(Ο|λ)达到最优。Baum-Welch方法是EM算法的一种实现，因采用爬山法往往得到的是局部最优。隐马尔可夫模型HMMs的三个基本解决方法解题思想：给定一个模型和输出字符序列，任意设定初始参数值，通过不断循环更新参数的方法，设法达到最优。算法步骤：2.基于λ0以及观察值序列X，训练新模型λ；1.初始模型（待训练模型）λ0,3.如果logP(X|λ)-log(P(X|λ0)Delta，说明训练已经达到预期效果，算法结束。4.否则，令λ0＝λ，继续第2步工作隐马尔可夫模型HMMs的局限性1.由于生成模型定义的是联合概率，必须列举所有观察序列的可能值，这对多数领域来说是比较困难的。2.基于观察序列中的每个元素都相互条件独立。即在任何时刻观察值仅仅与状态（即要标注的标签）有关。对于简单的数据集，这个假设倒是合理。但大多数现实世界中的真实观察序列是由多个相互作用的特征和观察序列中较长范围内的元素之间的依赖而形成的。最大熵模型最大熵模型（MEMs）是基于最大熵理论的统计模型，广泛应用于模式识别和统计评估中。最大熵原理的实质是，在已知部分知识前提下，关于未知分布最合理的推断是符合已知知识的最不确定或最随机的推断。最大熵的原理可以概括为，将已知事件作为约束条件，求得可使熵最大化的概率分布作为正确的概率分布。熵的计算公式如下：最大熵模型熵有如下的性质：其中|X|在离散分布时是随机变量的个数。当X为确定值，即没有变化的可能时上式左边的等式成立。由条件：，对熵的计算公式求条件极值，可知当随机变量X服从均匀分布时，成立，即均匀分布时熵最大。最大熵模型介绍最大熵模型的目的有两个，一是得到条件概率的指数形式，二是说明求最大熵的实质是求对数似然函数的最大值。利用最大熵模型建模时，只需集中精力选择特征，而不需要花费精力考虑如何使用这些特征。该模型的另一个优点是特征选择灵活，且不需要额外的独立性假设或内在约束。但最大熵模型时空开销大，存在严重的数据稀疏问题，需要进行平滑处理，且对语料库的依赖性大。条件随机场HMMs需要对观察序列建模，且要求严格的输出独立性假设，导致其不能考虑上下文的特征，限制了特征的选择。MEMs提出了一种条件模型，能够把多种特征信息纳入一个模型中，它用最大熵原理构造分布模型并利用对偶定理得出参数估计的实质是求最大对数似然估计。CRF（conditionalrandomfield）条件随机场模型是一种典型的判别式模型。在观测序列的基础上对目标序列进行建模，重点解决序列化标注的问题，CRF模型既具有判别式模型的优点,又具有产生式模型考虑到上下文标记间的转移概率，以序列化形式进行全局参数优化和解码的特点，解决了其他判别式模型(如最大熵、马尔科夫模型)难以避免的标记偏置问题。条件随机场随机场可以看成是一组随机变量的集合（这组随机变量对应同一个样本空间）,当给每一个位置按照某种分布随机赋予一个值之后，其全体就叫做随机场。马尔可夫随机场（MRF）对应一个无向图。这个无向图上的每一个节点对应一个随机变量，节点之间的边表示节点对应的随机变量之间有概率依赖关系。因此，MRF的结构本质上反应了我们的先验知识——哪些变量之间有依赖关系需要考虑，而哪些可以忽略。具有马尔可夫性质：离当前因素比较遥远(这个遥远要根据具体情况自己定义）的因素对当前因素的性质影响不大。如果给定的MRF中每个随机变量下还有观察值，要确定的是给定观察集合下，这个MRF的分布，也就是条件分布，那么这个MRF就称为CRF。它的条件分布形式完全类似于MRF的分布形式，只不过多了一个观察集合x。CRF本质上是给定了观察值(observations)集合的MRF。条件随机场在以下的条件随机场模型介绍中，随机变量Χ表示需要标记的观察序列集。随机变量Y表示相应的表示标记序列集。所有的被假设在一个大小为N的有限字符集内。随机变量Χ和Y是联合分布，但在判别式模型中我们构造一个关于观察序列和标记序列的条件概率模型p(Y|X)和一个隐含的边缘概率模型p(X)。下面给出条件随机场定义：条件随机场定义：令G=(V,E)表示一个无向图，，Y中元素与无向图G中的顶点一一对应。当在条件Χ下，随机变量的条件概率分布服从图的马尔可夫属性：，其中表示(v,w)是无向图G的边。这时我们称(X,Y)是一个条件随机场。1iyiy1iy1ixix1ix条件随机场关键问题1.特征函数的选择2.参数估计3.模型推断特征函数的选取直接关系模型的性能。从已经标注好的训练数据集学习条件随机场模型的参数，即各特征函数的权重向量λ。在给定条件随机场模型参数λ下，预测出最可能的状态序列。条件随机场1.特征函数的选择CRFs模型中特征函数的形式定义：在定义特征函数的时候，首先构建观察值上的真实特征b(x,i)的集合，即所有i时刻的观察值x的真实特征，结合其对应的标注结果，就可以获得模型的特征函数集。1(,,,)jjifyyxi它是状态特征函数和转移特征函数的统一形式表示。特征函数通常是二值函数，取值要么为1要么为0。1(,)0bxi如果时刻i观察值x是大写开头否则11(,),(,,,)0iiiibxiifytitleyauthorfyyxiotherwise条件随机场2.参数估计极大似然估计（MaximumLikelihoodEstimation，MLE)假定对于训练数据有一组样本集合()(),,1,,,jjDxyjN样本是相互独立的，为训练样本中(x,y)的经验概率，(,)pxy(,),()(,)pxyxyLpyx取对数形式：,()(,)log(,)xyLpxypyx对于某个条件模型，训练数据D的似然函数公式为：,pyx条件随机场CRFs模型中极大似然函数：1,1()(,)((,,,))()log()njjiixyijxLpxyfyyxipxZx,1()(,)()log()nxyixLpxyfpxZx对求导：j11,1,1()(,)(,,)()(,)(,,)nnjiijiixyixyijLpxyfyyxpxpyxfyyx()()(,)(,)(,)(,)kkpxyjjpyxkEfxyEfxy令上式等于0，求λ条件随机场Lafferty提出两个迭代缩放的算法用于估计条件随机场的极大似然参数GIS算法（GeneralisedIterativeScaling）IIS算法（ImprovedIterativeScaling）迭代缩放是一种通过更新规则以更新模型中的参数，通过迭代改善联合或条件模型分布的方法。更新规则如下：jjj其中更新值使得新的值比原来的值