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时刻的状态的联合分布概率，那么可递归得到。终结：递归：定义前向变量：初始化：forward算法：隐马尔可夫模型隐马尔可夫模型HMMs的三个根本解决方法由各个观察字符的输出状态相互独立，下面给出的递推过程：隐马尔可夫模型HMMs的三个根本解决方法那么观察序列所有可能的状态序列的概率为，以下图说明了在t时刻从N个状态，到达t+1时刻的状态的forward过程，隐马尔可夫模型HMMs的三个根本解决方法

终结：递归：定义前向变量：初始化：backward算法：隐马尔可夫模型隐马尔可夫模型HMMs的三个根本解决方法

隐马尔可夫模型HMMs的三个根本解决方法

隐马尔可夫模型HMMs的三个根本解决方法问题2是一个解码问题，给定一个模型λ=(N,M,A,B,π)和一个输出字符序列，如何找到产生这一序列概率最大的状态序列，即从个可能的状态序列中找到一个“最优”的状态序列，其中N是HMMs模型中状态的个数，T是观察序列的长度。对于问题2根据不同的“最优”标准，可以有假设干个解决方案，所以给定观察序列，找出“最优”状态序列的困难是最优状态序列的定义，即最优标准的选择。一个有效的查找最优路径的算法是Viterbi算法，它基于动态规划方法。隐马尔可夫模型HMMs的三个根本解决方法Viterbi算法：给定观察序列，利用Viterbi算法可以有效率的找到一个最优的状态序列，计算量为，我们定义表示t时刻状态时的最优状态序列和前t个观察序列的联合概率：

由t时刻状态时的最优状态序列和前t个观察序列的联合概率可递推得到时刻状态时的最优状态序列和前t+1个观察序列的联合概率：隐马尔可夫模型HMMs的三个根本解决方法Viterbi算法：初始化递归结束得到最优路径隐马尔可夫模型HMMs的三个根本解决方法问题3是模型参数估计问题。给定观察序列Ο，调整模型的参数使得在给定模型λ的条件下该观察序列的概率P(Ο|λ)最大，可以用Baum-Welch方法〔等价于EM(Expectation-Modification)方法〕或者用梯度技术，通过不断循环迭代更新参数的方法，设法使P(Ο|λ)到达最优。Baum-Welch方法是EM算法的一种实现，因采用爬山法往往得到的是局部最优。隐马尔可夫模型HMMs的三个根本解决方法解题思想：给定一个模型和输出字符序列，任意设定初始参数值，通过不断循环更新参数的方法，设法到达最优。算法步骤：2.基于λ0以及观察值序列X，训练新模型λ；1.初始模型〔待训练模型〕λ0,3.如果log

P(X|λ)-log(P(X|λ0)<Delta，说明训练已经到达预期效果，算法结束。4.否那么，令λ0＝λ，继续第2步工作隐马尔可夫模型HMMs的三个根本解决方法Baum-Welch算法：

隐马尔可夫模型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)是一个条件随机场。条件随机场关键问题1.特征函数的选择2.参数估计3.模型推断特征函数的选取直接关系模型的性能。从已经标注好的训练数据集学习条件随机场模型的参数，即各特征函数的权重向量λ。在给定条件随机场模型参数λ下，预测出最可能的状态序列。条件随机场1.特征函数的选择CRFs模型中特征函数的形式定义：在定义特征函数的时候，首先构建观察值上的真实特征b(x,i)的集合，即所有i时刻的观察值x的真实特征，结合其对应的标注结果，就可以获得模型的特征函数集。它是状态特征函数和转移特征函数的统一形式表示。特征函数通常是二值函数，取值要么为1要么为0。如果时刻i观察值x是大写开头否则条件随机场2.参数估计极大似然估计〔MaximumLikelihoodEstimation，MLE)假定对于训练数据有一组样本集合样本是相互独立的，为训练样本中(x,y)的经验概率，取对数形式：对于某个条件模型，训练数据D的似然函数公式为：条件随机场CRFs模型中极大似然函数：对求导：令上式等于0，求λ条件随机场Lafferty提出两个迭代缩放的算法用于估计条件随机场的极大似然参数GIS算法〔GeneralisedIterativeScaling〕IIS算法〔ImprovedIterativeScaling〕迭代缩放是一种通过更新规那么以更新模型中的参数，通过迭代改善联合或条件模型分布的方法。更新规那么如下：其中更新值使得新的值比原来的值更接近极大似然值。迭代缩放条件随机场迭代缩放的根本原理假定我们有一个以为参数的模型并且要找到一组新的参数：使得在该参数条件下的模型具有更高的对数似然值。通过迭代，使之最终到达收敛。对于条件随机场对数似然值的变化可以表示为：条件随机场引入辅助函数：定义为在观察序列和标记序列为(x,y)的条件下，特征值为1的特征的个数。根据寻找使最大化的∆，使用迭代算法计算最大似然参数集。条件随机场（A）将每个设初始值；（B）对于每个，计算，即迭代过程：应用更新规则，更新每个参数，直到收敛。条件随机场GIS算法：GIS是迭代缩放的一种，为了确保参数收敛的结果达到全局最优，GIS需要对特征集进行约束，即令每个训练数据中的事件。定义了一个全局修正特征S(x,y)：其中C是训练语料中所有的x和y情况下T(x,y)的最大值，即等于最大可能的特征个数，特征S(x,y)的参加确保了T(x,y)=C。假定对于所有的事件，条件随机场选定的特征的总和是常量C。更新值按下式计算条件随机场1.GIS算法的收敛速度由计算更新值的步长确定。C值越大，步长越小，收敛速度就越慢；反之C值越小，步长越大，收敛的速度也就越快。问题：2.GIS算法是依赖于一个额外的全局修正特征S(x,y)，以确保对于每个(x,y)对的有效特征的总和是一个常量。但是一旦参加这个新的特征，就认为这个特征和特征集中所有其他的特征之间是相互独立的，并且它的参数也需要使用上式来更新。计算期望需要对所有可能的标记序列求和，这将是一个指数级的计算过程。条件随机场IIS算法：重新定义：将每个对观察序列和标记序列对(x,y)起作用的特征值的和近似等于对于观察序列x的最大可能的观察特征的和使用牛顿一拉夫森方法求解条件随机场3.模型推断第二个问题通过Viterbi算法解决。Viterbi算法是一种动态规划算法，其思想精髓在于将全局最正确解的计算过程分解为阶段最正确解的计算。二、对于未标记的序列，求其最可能的标记。常见的两个问题：

一、在模型训练中，求边际分布和；第一个问题采用前向后向法解决；条件随机场势函数尽管在给定每个节点的条件下，分配给该节点一个条件概率是可能的，但条件随机场的无向性很难保证每个节点在给定它的邻接点条件下得到的条件概率和以图中其它节点为条件得到的条件概率一致。因此导致我们不能用条件概率参数化表示联合概率，而要从一组条件独立的原那么中找出一系列局部函数的乘积来表示联合概率。选择局部函数时，必须保证能够通过分解联合概率使没有边的两个节点不出现在同一局部函数中。最简单的局部函数是定义在图结构中的最大团(clique)上的势函数(Potentialfunction)，并且是严格正实值的函数形式。但是一组正实数函数的乘积并不能满足概率公理，那么必须引入一个归一化因子Z，这样可以确保势函数的乘积满足概率公理，且是G中节点所表示的随机变量的联合概率分布。其中C为最大团集合，利用Hammersley-Clifford定理，可以得到联合概率公式如下：条件随机场势函数基于条件独立的概念，条件随机场的无向图结构可以用来把关于的联合分布因式化正的和实值的势函数的乘积，每个势函数操作在一个由G中顶点组成的随机变量子集上。根据无向图模型条件独立的定义，如果两个顶点间没有边，那么意味着这顶点这些顶点对应的随机变量在给定图中其它顶点条件下是条件独立的。所以在因式化条件独立的随机变量联合概率时，必须确保这些随机变量不在同一个势函数中。满足这个要求的最容易的方法是要求每个势函数操作在一个图G的最大团上，这些最大团由随机变量相应顶点组成。这确保了没有边的顶点在不同的势函数中，在同一个最大团中的顶点都是有边相连的。在无向图中，任何一个全连通〔任意两个顶点间都有边相连〕的子图称为一个团(clique)，而称不能被其它团所包含的才为最大团(maximalclique)。

条件随机场势函数理论上讲，图G的结构为任意，然而，在构造模型时，CRFs采用了最简单和最重要的一阶链式结构。如以下图所示，条件随机场(X,Y)以观察序列Χ作为全局条件，并且不对Χ做任何假设。这种简单结构可以被用来在标记序列上定义一个联合概率分布p(y|x)，主要关心的是两个序列和。条件随机场概率模型的形式Lafferty对CRFs势函数的选择很大程度上受最大熵模型的影响。定义每个势函数的形式如下：

其中y|c表示第c个团中的节点对应的随机变量，是一个布尔型的特征函数，那么p(y|x)为：

其中Z(x)是归一化因子，

在一阶链式结构的图G=(V,E)中，最大团仅包含相邻的两个节点，即是图G中的边。条件随机场概率模型的形式对于一个最大团中的无向边

，势函数一般表达形式可扩展为：

其中

是整个观察序列和相应标记序列在i−1和i时刻的特征，是一个转移函数。而是在i时刻整个观察序列和标记的特征，是一个状态函数。联合概率的表达形式可以写为：其中，参数

和

可以由从训练数据中估计，大的非负参数值意味着优先选择相应的特征事件，大的负值所对应的特征事件不太可能发生。条件随机场概率模型的形式定义特征函数之前，先构造观察序列的实数值特征b(x,i)集合来描述训练数据的经验分布特征，这些特征与模型同分布。例如：

每个特征函数表示为观察序列的实数值特征b(x,i)集合中的一个元素，如果当前状态〔状态函数〕或前一个状态和当前状态〔转移函数〕具有特定的值，那么所有的特征函数都是实数值。例如转移函数：为了统一转移函数和状态函数的表达形式，我们可以把状态函数写为下式：并用统一表示，可能是状态函数或转移函数，又令：从而结定观察序列x条件下，相应的标记序列为y的概率可以写为：其中Z(x)是归一化因子。条件随机场条件随机场模型的参数估计以上的CRFs理论介绍给出了CRFs的概率形式公式，主要是基于最大熵理论，下面将介绍的是CRFs模型的参数估计，由最大熵模型可知参数估计的实质是对概率的对数最大似然函数求最值，即运用最优化理论循环迭代，直到函数收敛或到达给定的迭代次数。假设给定训练集，根据最大熵模型对参数λ估计采用最大似然估计法。条件概率p(y|x,λ)的对数似然函数形式为：条件概率p(y|x,λ)的形式化公式为：条件随机场条件随机场模型的参数估计对于该CRFs概率模型来说，对数最大似然参数估计的任务是从相互独立的训练数据中估计参数的值，那么对数似然函数可写为下式：为了表达，假设链式结构的无向图分别有一个特殊的起始节点和终止节点，分别用和表示。那么经验分布概率和由模型得到的概率的数学期望为：条件随机场条件随机场模型的参数估计我们根据对数似然函数对相应的参数

求一阶偏导数：条件随机场条件随机场模型的参数估计通过梯度为零来求解参数λ并不一定总是得到一个近似解，因而需要利用一些迭代技术来选择参数，使对数似然函数最大化。通常采用的方法是改进的迭代缩放ImprovedIterativeScaling,IIS〕或者基于梯度的方法来计算参数。以上的介绍中，我们给出了对数似然函数L(λ)梯度的计算表达形式，即的数学期望与由模型得到的条件概率p(y|x,λ)的数学期望的差。而经验分布的数学期望为训练数据集中随机变量(x,y)满足特征约束的个数，模型的条件概率的数学期望的计算实质上是计算条件概率p(y|x,λ)，在下一节中我们将介绍条件概率的有效计算方法。条件随机场条件概率的矩阵计算建立条件随机场模型的主要任务是从训练数据中估计特征的权重λ。下面主要对CRFs用到最大似然估计