条件随机场综述

http://www.paper.edu.cn -1- 中国科技论文在线 条件随机场理论综述 韩雪冬 1，周彩根 2 1北京邮电大学计算机学院 ，北京（100876 ) 2中国人民解放军总参谋部第五十四研究所，北京（100083） E-mail：hanxuedong@bupt.cn 摘 要： 条件随机场理论可以用于序列标记、数据分割、组块分析等自然语言处理任务。在 中文分词、中文人名识别、歧义消解等汉语自然语言处理任务中都有应用，表现很好。与一 般介绍条件随机场理论的论文有所不同，本文给出了条件随机场理论的概率模型的推导，参 数估计的函数形式为对数似然函数的原因及条件随机场矩阵计算的图例说明，能使读者掌握 条件随机场理论的依据和整体。 关键词：条件随机场；CRFs；最大熵模型；中文分词 中图分类号：TP301.6 1 引言 条件随机场理论（CRFs）可以用于序列标记、数据分割、组块分析等自然语言处理任 务中。在中文分词、中文人名识别、歧义消解等汉语自然语言处理任务中都有应用，表现很 好。目前基于 CRFs 的主要系统实现有 CRF，FlexCRF，CRF++[1]。 本文主要介绍条件随机场理论。因为条件随机场理论与它先前的基于统计方法的模型有 着联系，所以先是介绍了隐马尔可夫模型，而后介绍了最大熵模型，给出了概率模型的推导 过程和其参数估计函数形式。最后重点介绍了条件随机场模型。 2 隐马尔可夫模型 隐马尔可夫模型(Hidden Markov Models，HMMs)研究始于 1966，基于统计方法的隐马 尔可夫模型在若干年后变得很受欢迎，原因有二个，一是该模型有丰富的数学理论结构，能 被广泛的应用；二是在若干重要应用上经恰当的运用表现的很出色。在讲述隐马尔可夫模型 之前，我们先简单介绍以下几个模型用到的马尔可夫随机过程。 2.1 离散马尔可夫过程 设有 N 个不同状态{ }nSSS ,,, 21 " 的随机过程，令 t=1,2,…表示不同的时间点， tq 表示 t 时刻随机过程所处的状态， ija 表示状态 iS 到 jS 的转移概率。当随机过程满足：当前所处 的状态仅与它之前的一个状态有关，即 ]|[],,|[ 121 jtitktjtit SqSqPSqSqSqP ====== −−− " （1） 时，该随机过程为马尔可夫随机过程。而且我们考虑（1）式右边的随机过程是独立于时间 的，从而得到状态间的转移概率 ija ， ],|[ 1 jtitij SqSqPa === − Nji ≤≤ ,1 (2) 转移概率 ija 具有两个属性： 0≥ija 和 1 1 =∑ = N j ija ，因此 ija 服从概率约束。 以上介绍了离散马尔可夫随机过程，下面我们先介绍隐马尔可夫模型的要素，而后介绍 隐马尔可夫模型面临的三个基本问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 及解决方法。 2.2 隐马尔可夫要素 http://www.paper.edu.cn -2- 中国科技论文在线 隐马尔可夫模型有五个要素[2]组成： 1）N ，表示模型中的状态数。模型中的各个状态是相互连结的，任何状态能从其它状 态到达。我们用 S 表示各个状态的集合， { }NsssS ,,, 21 "= ， tq 表示 t 时刻的状态。 2）M ，表示模型中每个状态不同的观察符号，即输出字符的个数。我们用 V 表示各 个字符的集合， { }MvvvV ,,, 21 "= 。 3）A，状态转移概率分布。 { }ijaA = ，其中， ]|[ 1 jtitij SqSqPa === − ， Nji ≤≤ ,1 ， 当从状态 iS 经一步到达 jS 时， 0>ija ，否则 0=ija 。 4） B ，观察字符在状态 j 时的概率分布， { })(kbB j= ，其中 ]|[)( jtkj SqvPkb == ， Nj ≤≤1 ， Mk ≤≤1 。 5）π ，表示初始状态分布， { }jππ = ，其中 ][ 1 jj SqP ==π ， Nj ≤≤1 。 给定 π,,,, BAMN ，HMMs 能输出一个观察字符的序列 TΟΟΟ=Ο "21 ，其中 Vt ∈Ο ， T 是观察序列的字符个数。 从以上的讨论可知，一个完整的隐马尔可夫模型要求两个具体的模型参数N 和M ，和 三个概率矩阵 π,,BA ，也即隐马尔可夫模型可形式化定义为一个五元组 ( )π,,,, BAMN 。 以上介绍了隐马尔可夫模型的五个要素，下面我们介绍隐马尔可夫模型的三个基本问题 及相应的解决方法。 2.3 隐马尔可夫模型的三个基本问题 1 ）给定一个模型 ( )πλ ,,,, BAMN= ，如何高效的计算某一输出字符序列 TΟΟΟ=Ο "21 的概率 )|( λΟP 。 2）给定一个模型 ( )πλ ,,,, BAMN= 和一个输出字符序列 TΟΟΟ=Ο "21 ，如何找到 产生这一序列概率最大的状态序列 Tji sssQ "= 。 3）给定一个模型 ( )πλ ,,,, BAMN= 和一个输出字符序列 TΟΟΟ=Ο "21 ，如何调整 模型的参数使得产生这一序列的概率最大。 为了方便分析问题和给出解决方案，这里先介绍一下隐马尔可夫模型的条件独立性假 设。隐马可尔可夫模型是一个生成模型，给定一个观察序列，HMMs 模型隐含一个与观察 序列对应的状态序列。隐马可夫模型图示如下，图中清楚的表示出了隐马尔可夫模型内部的 条件独立关系，有三个独立性假设：一是 t时刻的状态 it sq = 只依赖于 1−t 时刻的状态 jt sq =−1 ，即 ( ) ( )λλ ,|,| 111 −− = tttt qqPqqqP " 。二是 t时刻所生成的值 )( tib Ο 只依赖于 t时刻的状态 it sq = ，即 ( ) ( )∏ = Ο=ΟΟΟ T t ttTT qPqqqP 1 2121 |,| λ"" 。三是状态与具体 时间无关，即对任意的 i 和 j 都有 ( ) ( )λλ ,|,| 11 −− = jjii qqPqqP 。 http://www.paper.edu.cn -3- 中国科技论文在线 下面我们给出三个基本问题的解决方法。 2.4 forward-backward 算法 问题 1 是一个评价问题，即给定一个模型λ和一个观察序列 TΟΟΟ=Ο "21 ，如何计 算由模型产生这一观察序列的概率 )|( λΟP 。最直接的方法是枚举所有长度为 T，输出观察 序列为Ο的可能的状态序列。假设状态数为 N ，时枚举方法的计算量为 TNT ⋅2 ，使该方 法的在计算上不可行。目前可采用 forward-backward 算法解决这个问题。 forward-backward 过程[3][4]：定义 forward 变量 )(itα 为 ( )λα |,)( 21 ittt sqPi =ΟΟΟ= " （3） 即对于模型λ，在 t 时刻，状态为 iS 时的部分观察序列 tΟΟΟ "21 的概率记为 )(itα ， )(itα 为部分观察序列 tΟΟΟ "21 和 t时刻的状态 iS 的联合分布概率，则 )(itα 可递归得到。 由各个观察字符的输出状态相互独立，下面给出 )1( +tjα 的递推过程： )|,()1( 1121 λα jttj sqPt =ΟΟΟ=+ ++" )|(),|( 11121 λλ jtjtt sqPsqP ==ΟΟΟ= +++" )|(),|(),|( 111121 λλλ jtjttjtt sqPsqPsqP ==Ο=ΟΟΟ= ++++" ∑ = +++ =Ο==ΟΟΟ= N i jttjtitt sqPsqsqP 1 11121 ),|()|,,( λλ" ∑ = +++ =Ο===ΟΟΟ= N i jttititjtt sqPsqPsqsqP 1 11121 ),|()|(),|,( λλλ" ∑ = +++ =Ο====ΟΟΟ= N i jttititjtitt sqPsqPsqsqPsqP 1 11121 ),|()|(),|(),|( λλλλ" ∑ = +++ =Ο===ΟΟΟ= N i jttitjtitt sqPsqsqPsqP 1 11121 ),|(),|()|,( λλλ" )()( 1 1 + = Ο⎥⎦ ⎤⎢⎣ ⎡= ∑ tjijN i i batα 则观察序列所有可能的状态序列的概率为， 1q 2q 3q 1−Tq Tq 1Ο 2Ο 3Ο 1−ΟT TΟ … … 图 1 HMMs http://www.paper.edu.cn -4- 中国科技论文在线 .)()|( 1 ∑ = =Ο N i T iP αλ (4) 下图说明了在 t时刻从N 个状态 iS ， Ni ≤≤1 到达 1+t 时刻的状态 jS 的 forward 过程， 由以上可知 )(itα 是观察序列 tΟΟΟ "21 和 t时刻所处的状态 is 的联合概率， ijt ai)(α 是观察序列 tΟΟΟ "21 的在 t时刻的输出状态序列和在 1+t 时刻经 is 到达 js 的联合概率， 从 t时刻所有N 个可能的状态 is ， Ni ≤≤1 到达 1+t 的 js 状态的概率和，而后乘以 1+t 时 刻观察字符 1+Ο t 在状态 js 的概率 )( 1+Ο tjb 为 1+t 时刻在 js 状态的概率，即得到 )(1 jt+α ， Nj ≤≤1 , 1,,2,1 −= Tt " 。最终的 forward 变量 )(iTα 为， )|,()( 21 λα iTTT sqPi =ΟΟΟ= " （5） 因此 )|( λΟP 等于各个 )(iTα 的和，其中 Ni ≤≤1 。forward 算法计算 )|( λΟP 需要计 算 )( jtα ，而 Nj ≤≤1 ， Tt ≤≤1 ，所以总计算量为 TN 2 ，远小于直接计算 )|( λΟP 所用 的 TNT ⋅2 的计算量。 与定义 forward 变量类似，我们可以定义 backward 变量 )(itβ 为 ),|()( 21 λβ itTttt sqPi =ΟΟΟ= ++ " (6) 即 t时刻，部分观察序列从 1+Ο t 到 TΟ ,给定模型λ和状态 is 条件下的概率，由 HMMs 的特 性，我们可以递推 )(itβ ： ),|()( 21 λβ itTttt sqPi =ΟΟΟ= ++ " ∑ = +++ ==ΟΟΟ= N j itjtTtt sqsqP 1 121 ),|,( λ" ∑ = ++++ ===ΟΟΟ= N j itjtjtTtt sqsqPsqP 1 1121 ),|(),|( λλ" ( )∑ = +++++ ===Ο=ΟΟ= N j itjtjttjtTt sqsqPsqPsqP 1 11112 ),|(,|),|( λλλ" ∑ = ++Ο= N j ttjij jba 1 11 )()( β # 1s 2s Ns js ja1 ja2 Nja 图 2 forward 计算 t t+1 )(itα )(1 jt+α http://www.paper.edu.cn -5- 中国科技论文在线 给定观察序列Ο和模型 λ 条件下， t时刻状态为 it sq = 时的状态序列的概率定义为 ( )λ,|Ο= it sqP 。由 )(itα ， )(itβ 可知观察序列和 t 时刻状态为 it sq = 时的联合概率 ( )λ|,Ο= it sqP 和观察序列的概率 ( )λ|ΟP 分别为： ( ) )()(|, iisqP ttit βαλ =Ο= (7) ( ) ( ) ∑∑ == =Ο==Ο N i tt N i it iisqPP 11 )()(|,| βαλλ (8) 由上面两式可知： ( ) ( )( ) ∑ = =Ο Ο==Ο= N i tt ttit it ii ii P sqP sqP 1 )()( )()( | |, ,| βα βα λ λλ (9) 图示如下： 2.5 Viterbi 算法 问题 2 是一个解码问题，即从 TN 个可能的状态序列中找到一个“最优”的状态序列，其 中 N 是 HMMs 模型中状态的个数，T 是观察序列的长度。不像问题 1 能给出一个确定的解 决方案，对于问题 2 根据“最优”的标准不同，可以有若干个解决方案，所以给定观察序列， 找出“最优”状态序列的困难是最优状态序列的定义，即最优标准的选择。例如一个最优标准 是去选择在 t时刻，状态为 tq 的单个概率为最大，这个最优标准是使状态序列中正确的单个 状态的数学期望值最大。但最广泛应用的标准是考虑使整个状态序列最优，也即是最优路径 问题，这种方法试图找到最大的 ( )λ,|ΟQP ，由于 ( )λ|ΟP 的概率对找到最大的 ( )λ,|ΟQP 没有影响，实际上等于找到最大的 ( )λ|,ΟQP 。一个有效的查找最优路径的算法是 Viterbi 算法，它基于动态规划方法。 Viterbi 算法[5][6]：给定观察序列 TΟΟΟ=Ο "21 ，利用 Viterbi 算法可以有效率的找到 一个最优的状态序列 TqqqQ "21= ，计算量为 2NT ，我们定义 )(itδ 表示 t 时刻状态 it sq = 时的最优状态序列和前 t个观察序列的联合概率： ( )λδ |,max)( 2121,, 121 titqqqt sqqqPi t ΟΟΟ== − """ (10) 由 t时刻状态 it sq = 时的最优状态序列和前 t个观察序列的联合概率 )(itδ 可递推得到 1+t 时刻状态 jt sq =+1 时的最优状态序列和前 1+t 个观察序列的联合概率 )(1 jt+δ ： 1s # 2s Ns is 1ia 2ia iNa 图 3节点概率计算 t t+1 # 1s 2s Ns ia1 ia2 Nia t-1 )(),( ii tt βα )(1 jt+β)(1 jt−α http://www.paper.edu.cn -6- 中国科技论文在线 ).(])(max[)( 111 +≤≤+ Ο⋅= tjijtNit baij δδ (11) 在实际应用中，为了由当前最优路径中的最后一个状态检索出最优状态序列，我们需要用数 组 )( jtϕ 保存 t时刻的各个状态处于最优路径时的前一个状态索引。发现最优状态序列的完 整过程如下： 1）初始化， )()( 11 Ο= iibi πδ ， 0)(1 =iϕ ， Ni ≤≤1 ； 2)递归得到： ，baij tjijtNit )(])(max[)( 11 Ο⋅= −≤≤ δδ Tt ≤≤2 , Nj ≤≤1 (12a) ],)([maxarg)( 1 1 ijt Ni t aij −≤≤ = δϕ Tt ≤≤2 , Nj ≤≤1 (12b) 3)最终完整状态序列的最大概率 ∗P 和最大概率的状态序列的最后一个状态记为 ∗Tq ，则 )]([max 1 iP TNi δ≤≤∗ = (13a) )]([maxarg 1 iq T Ni T δ≤≤ ∗ = (13b) 4）让 ∗tq 表示最优状态序列 t时刻的状态索引，则最优路径或状态序列的逆向索引为： ),( 11 ∗ ++ ∗ = ttt qq ϕ .1,,2,1 "−−= TTt (14) 除了逆向找出状态索引的步骤不同，Viterbi 算法与 forward 计算过程很相似，其最主要 区别是 Viterbi 算法是在根据先前的状态序列找出转到当前状态有最大概率的那个状态，而 forward 算法是根据先前的状态序列计算转移到当前状态的概率和。它们都可以采用格子 (Lattice or trellis)的结构形式实现有效的计算。 2.6 参数估计 问题 3 是模型参数估计问题。给定观察序列Ο，调整模型的参数使得在给定模型λ的 条件下该观察序列的概率 ( )λ|ΟP 最大。无法用解析方法求解，事实上，给定任意有限的观 察序列作为训练数据，不存在一个最优的方法去估计模型参数，然而我们可以用 Baum-Welch 方法（等价于 EM(Expectation-Modification)方法）或者用梯度技术，通过不断循环迭代更新 参数的方法，设法使 ( )λ|ΟP 达到最优。Baum-Welch 方法是 EM 算法的一种实现，因采用 爬山法往往得到的是局部最优。 2.7 隐马尔可夫模型的局限性 应用 HMMs 模型，在序列标记任务中，我们的目标是找到一个给定观察序列 TΟΟΟ=Ο "21 的条件下，使标记序列 TqqqQ "21= 的条件概率最大的那个标记序列 maxQ ，即 )|(maxargmax Ο= QPQ allQ 。隐马尔可夫模型定义的是观察序列和状态序列的联 合概率 ),( QP Ο ，由贝叶斯 公式 小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载 ： )()|(),()()|( ΟΟ=Ο=Ο PQPQPQPQP (15) 可知 )( ),(maxargmax Ο Ο= P QPQ allQ ，可以看出生成模型定义的是观察序列和标记序列的联合概 率分布 ),( QP Ο 。但在标记数据时模型关心的是在给定观察序列Ο的条件下，标记序列Q的 http://www.paper.edu.cn -7- 中国科技论文在线 条件分布 )|( ΟQP 。定义观察序列和标记序列的联合分布意味着所有可能的观察序列必须 是可枚举的，如果观察序列中存在长距离依赖，枚举所有可能的观察序列是十分困难的，因 此，为了便于模型处理问题，生成模型给出了一个严格的输出独立性假设。例如在隐马尔可 夫模型中，我们假设 t时刻的观察值只依赖于 t时刻的状态，这确保了序列中的所有观察值 互相独立。但事实上，数据序列并不能完全地表示为一组独立的单元。当序列中的数据元素 存在长距离依赖时，允许这种长距离依赖并且使观察序列可以表示为非独立的交叉特征的模 型才是比较合适的。 下面所提到的条件模型或判别模型克服了生成模型所要求的严格的独立假设，它定义了 一个在给定观察序列Ο的条件下，状态序列Q的条件分布 ( )OQP | 。下一小节我们将介绍 最大熵模型，主要是其条件概率模型的推导和参数估计的函数形式。 3 最大熵模型 最大熵模型（Maximum Entropy Models, MEMs）[7][8][9]是基于最大熵理论的统计模型， 广泛应用于模式识别和统计评估中。最大熵原理有一个很长的历史，其中最大熵理论方面的 先驱 E.T.Jaynes 在 1990 年给出了最大熵原理的基本属性[10]：最大熵概率分布服从我们已知 的不完整信息的约束。主要思想是，在用有限知识预测未知时，不做任何有偏的假设。根据 熵的定义，一个随机变量的不确定性是由熵体现的，熵最大时随机变量最不确定，对其行为 做准确预测最困难。最大熵原理的实质是，在已知部分知识前提下，关于未知分布最合理的 推断是符合已知知识的最不确定或最随机的推断，这是我们可以做出的唯一不偏不倚的选 择。最大熵的原理可以概括为，将已知事件作为约束条件，求得可使熵最大化的概率分布作 为正确的概率分布。熵的计算公式如下[11]： ∑ ∈ −≡ Xx xpxpXH )(log)()( （16） 熵有如下的性质： ||log)(0 Χ≤≤ XH （17） 其中 || X 在离散分布时是随机变量的个数。当 X 为确定值，即没有变化的可能时上式 左边的等式成立。由条件：∑ ∈ = Xx xp 1)( ，对熵的计算公式（16）求条件极值，可知当随机 变量 X 服从均匀分布时， ||log)( Χ=XH 成立，即均匀分布时熵最大。 最大熵模型用到熵的计算公式是有条件约束的，如 3.0)()( 21 =+ xpxp 条件约束下的 最大熵，或者更多约束条件时的最大熵。我们的目的是找到一个能同时满足这些约束条件的 最均匀的模型。由此最大熵模型面临两个问题，一是如何确定模型是均匀的，二是根据一个 约束集如何找到一个最优的均匀分布。由上面熵取得最大值时分布可知，当熵模型在满足约 束条件下取得最大值时，熵模型是均匀的。下面我们介绍这二个问题的解决过程。 自然语言处理中的很多问题可以归结为统计分类问题，因此可以将自然语言处理任务的 所有输出值构成一个类别有限集Υ ，对于每个 Υ∈y ，其生成均受上下文信息 x的影响和 约束。已知与 y有关的所有上下文信息组成的集合为Χ，则模型的目标是，在给定上下文 信息 Χ∈x ，计算输出为 Υ∈y 的条件概率 )|( xyp ，模型的输入为人工标注后训练数据样 本集 )},(,),,(),,{( 2211 ΓΓ= yxyxyxD " 。我们可以从训练样本归结出随机变量 x和 y的 联合经验概率分布 ),(~ yxp ， http://www.paper.edu.cn -8- 中国科技论文在线 Γ= 数在样本中同时出现的次),(),(~ yxyxp （18） 其中Γ为整个样本空间D的大小。特殊情况，样本空间中 ),( yx 根本没有同时出现， 或者在一些上下文中出现了多次。 3.1 最大熵模型的约束条件 我们的目标是构造一个能生成训练样本分布 ),(~ yxp 的统计模型，建立特征方程。该特 征必须能较完整地表达训练样本中数据的特性。例如，在中文分词任务中，可以引入特征函 数 ),( yxf ， ⎩⎨ ⎧ === otherwise xandgleyif yxf 0 ','sin1 ),( 设 )(~ fp 是相对于经验分布 ),(~ yxp ，特征函数 f 的数学期望，称为经验期望，公式为： ∑= yx yxfyxpfp , ),(),(~)(~ （19） )( fp 是相对于由模型确定的概率分布 ),( yxp 的数学期望，称为模型期望，公式如下： ),()|()(~),(),()( ,, yxfxypxpyxfyxpfp yxyx ∑∑ == （20） 其中 )(~ xp 是随机变量 x在训练样本中的经验分布，即在样本中出现的频率。我们约束 由模型得到的特征函数的数学期望等于由训练样本得到的特征函数的经验数学期望，即： )(~)( fpfp = （21） 由上面的三个式子（19）（20）（21）可以得到下面的等式： ),(),(~),()|()(~ ,, yxfyxpyxfxypxp yxyx ∑∑ = （22） 我们把等式（21）称为模型的约束等式，或者简单的称为约束。 我们现在可以用 )(~ fp 描述训练样本的统计现象的内在属性，同时也要求由模型得到的 )( fp 能完整的展现这些统计现象的内在属性，即 )(~)( fpfp = 。 3.2 最大熵模型的原则 下面介绍最大熵模型的原则，先定义Ρ为所有条件分布的集合，根据 )|( xyp 的定义， 有 Ρ∈)|( xyp 。假设我们选择m个对模型真正有用的特征函数 if ，用以体现统计数据的特 性。约束条件下所产生的集合C是Ρ的一个子集，即 Ρ⊂C ，定义如下： { }},,2,1{),(~)(| mifpfppC ii "∈=Ρ∈= （23） 满足约束条件的模型很多。模型的目标是产生在约束集下具有最均匀分布的模型，条件 熵 )|( XYH 是作为条件概率 )|( xyp 均匀性的一种数学测度方法。为了强调熵对概率分布 p的依赖，我们用 )( pH 代替 )|( XYH ，得条件分布的熵公式如下： ∑−≡ )|(log)|()(~)( xypxypxppH （24） 对于任意给定的约束集C，能找到唯一的 Cp ∈∗ 使 )( pH 取得最大值，如何找到 ∗p ， 是一个约束最优化问题。我们给出 ∗p 的等式， http://www.paper.edu.cn -9- 中国科技论文在线 )(maxarg pHp Cp∈ ∗ = （25） 对于简单的约束条件，我们能用解析的方法找到最优的概率分布，但对于一般性问题， 这种方法是不可行的。为解决一般性约束最优化问题，我们应用了约束最优化理论中的 Lagrange 乘子 定理 三点共线定理勾股定理的证明证明勾股定理共线定理面面垂直的性质定理 解决这个问题。首先对模型中的每一个特征 if 都引入一个参数 iλ ，即 Lagrange 乘子。由条件熵定义 )( pH 和约束条件 )(~)( fpfp = ，我们定义 Lagrange 函数为 ),( λpΛ ， ∑ = −+=Λ m i iii fpfppHp 1 ))(~)(()(),( λλ （26） 假设 Lagrange 函数 ),( λpΛ 中的变量λ固定，我们可以求出无约束的 Lagrange 函数 ),( λpΛ 的最大值时的 p， Ρ∈p 。我们定义λ固定时 Lagrange 函数 ),( λpΛ 的最大值记 为 )(λΨ ， ),( λpΛ 为最大值时的 p记为 λp ，即有： ),(max λλ pagrp p Λ≡ Ρ∈ (27a) ),()( λλ λpΛ≡Ψ (27b) )(λΨ 是对偶函数，即 )(maxarg },,2,1{ i mi λλ Ψ= ∈ ∗ " 与 )(maxarg pHp Cp∈ ∗ = 是对偶关系。称 )(maxarg pHp Cp∈ ∗ = 为原问题， )(maxarg },,2,1{ i mi λλ Ψ= ∈ ∗ " 为对偶问题，利用 KT(Kuhn-Tucker) 对偶定理：在合适条件下，初始问题和对偶问题是紧密联系的。如果 ∗λ 是对偶问题的解， 那么 ∗p 就是初始化问题的解， λpp =∗ 。下面给出求 λp 和 )(λΨ 的过程： ∑ ∑∑ ++−=∂Λ∂ yx i iiyx xyp yxfxpxp p p ,, )|( ),()(~)1)((~),( log λλ (28) 使上式 ),( λpΛ 对 p的一阶偏导数等于零，可得到： ∑=∗ i ii yxfe p )),(exp(1 λλ (29) 为使 ∗λp 满足经典概率规则 1)|( =∑ ∗ xyp y λ ，需要引入归一化因子 )(xZ ∗λ ，则有， )),(exp(1 yxf e Z i y i i∑ ∑=∗ λλ (30) 常数 e 1 对概率分布和求最值没有影响，所以概率 λp 和归一化因子 )(xZ λ 可写为下列 形式： ∑= i ii yxfxZ p )),(exp( )( 1 λ λ λ (31) )),(exp()( yxfxZ i y i i∑ ∑= λλ (32) ),()( λλ λpΛ≡Ψ 和 λp 可知： http://www.paper.edu.cn -10- 中国科技论文在线 ( ) ∑∑ +−=Ψ i ii x fpxZxp )(~)(log~)( λλ λ (33) 由对偶最优化理论可知，我们的最终问题求解 )(maxarg },,2,1{ i mi λλ Ψ= ∈ ∗ " ，可以用无约束最 优化方法找到 )(λΨ 最大时的λ。在求解对偶问题之前，我们先给出 )(λΨ 与对数似然函数 的关系。 设 )(~ pLp 是由模型估计的经验分布 p~ 的对数似然，则： ∑∏ == yxyx yxp p xypyxpxyppL ,, ),(~ ~ )|(log),(~)|(log)( (34) 事实上可以推知，指数分布模型 λp 的对数最大似然与 )(λΨ 存在相等关系，即： )()( ~ λλ pLp=Ψ (35) 求解 ∗λ 转化为求解最大对数似然时的λ，对数似然函数 )(~ pLp 是平滑的凸函数，存在 最优解 ∗λ 。可以用坐标爬升法、梯度爬升法和共轭梯度法等数学方法来计算 ∗λ 。在实现最 大熵的估计时利用了 IIS(Improved Iterative Scaling)迭代算法来求解。在此不作介绍。我们介 绍最大熵模型的目的有两个，一是得到条件概率的指数形式，二是说明求最大熵的实质是求 对数似然函数的最大值。 利用最大熵模型建模时，我们只需集中精力选择特征，而不需要花费精力考虑如何使用 这些特征。该模型的另一个优点是特征选择灵活，且不需要额外的独立性假设或内在约束。 但最大熵模型时空开销大，存在严重的数据稀疏问题，需要进行平滑处理，且对语料库的依 赖性大。下面一节介绍条件随机场理论。 4 条件随机场理论 条件随机场(Conditional Random Fields, CRFs)[12]最早由 Lafferty 等人于 2001 年提出的， 其模型思想的主要来源是最大熵模型，模型的三个基本问题的解决用到了 HMMs 模型中提 到的方法如 forward-backward 和 Viterbi。我们可以把条件随机场看成是一个无向图模型或马 尔可夫随机场，它是一种用来标记和切分序列化数据的统计模型。该模型是在给定需要标记 的观察序列的条件下，计算整个标记序列的联合概率，而不是在给定当前状态条件下，定义 下一个状态的分布。标记序列(Label Sequence)的分布条件属性，可以让 CRFs 很好的拟和现 实数据，而在这些数据中，标记序列的条件概率信赖于观察序列中非独立的、相互作用的特 征，并通过赋予特征以不同权值来表示特征的重要程度。 4.1 条件随机场定义 在以下的条件随机场模型介绍中，随机变量Χ表示需要标记的观察序列集。随机变量Υ 表示相应的表示标记序列集。所有的 Υ∈Υi 被假设在一个大小为 N 的有限字符集内。随机 变量Χ和Υ 是联合分布，但在判别式模型中我们构造一个关于观察序列和标记序列的条件 概率模型 )|( XYp 和一个隐含的边缘概率模型 )(Xp 。下面给出条件随机场定义： 条件随机场定义：令 ),( EVG = 表示一个无向图， Vvv ∈Υ=Υ )( ，Υ 中元素与无向图G 中的顶点一一对应。当在条件Χ下，随机变量 vΥ 的条件概率分布服从图的马尔可夫属性： )~,,|(),,|( vwpvwp wvwv ΥΧΥ=≠ΥΧΥ ，其中 vw ~ 表示 ),( vw 是无向图G 的边。这 http://www.paper.edu.cn -11- 中国科技论文在线 时我们称 ),( ΥΧ 是一个条件随机场。 4.2 势函数 尽管在给定每个节点的条件下，分配给该节点一个条件概率是可能的，但条件随机场的 无向性很难保证每个节点在给定它的邻接点条件下得到的条件概率和以图中其它节点为条 件得到的条件概率一致。因此导致我们不能用条件概率参数化表示联合概率，而要从一组条 件独立的原则中找出一系列局部函数的乘积来表示联合概率。选择局部函数时，必须保证能 够通过分解联合概率使没有边的两个节点不出现在同一局部函数中。最简单的局部函数是定 义在图结构中的最大团(clique)上的势函数(Potential function)，并且是严格正实值的函数形 式。但是一组正实数函数的乘积并不能满足概率公理，则必须引入一个归一化因子 Z ，这 样可以确保势函数的乘积满足概率公理，且是G 中节点所表示的随机变量的联合概率分布。 ∑∏ ∈ Φ= i c v Cc cv vZ )( （36） 其中C为最大团集合，利用 Hammersley-Clifford 定理，可以得到联合概率公式如下： ∏ ∈ Φ= Cc cvN vZ vvvp c )(1),,,( 21 " (37) 基于条件独立的概念，条件随机场的无向图结构可以用来把关于 Υ∈Υv 的联合分布因 式化正的和实值的势函数的乘积，每个势函数操作在一个由G 中顶点组成的随机变量子集 上。根据无向图模型条件独立的定义，如果两个顶点间没有边，则意味着这顶点这些顶点对 应的随机变量在给定图中其它顶点条件下是条件独立的。所以在因式化条件独立的随机变量 联合概率时，必须确保这些随机变量不在同一个势函数中。满足这个要求的最容易的方法是 要求每个势函数操作在一个图G 的最大团上，这些最大团由随机变量相应顶点组成。这确 保了没有边的顶点在不同的势函数中，在同一个最大团中的顶点都是有边相连的。在无向图 中，任何一个全连通（任意两个顶点间都有边相连）的子图称为一个团(clique)，而称不能 被其它团所包含的才为最大团(maximal clique)。 理论上讲，图G 的结构为任意，然而，在构造模型时，CRFs 采用了最简单和最重要的 一阶链式结构。如下图所示，条件随机场 ),( ΥΧ 以观察序列Χ作为全局条件，并且不对Χ 做任何假设。这种简单结构可以被用来在标记序列上定义一个联合概率分布 )|( xyp ，我们 主要关心的是两个序列： ),,,( 21 TΧΧΧ=Χ " 和 ),,,( 21 TΥΥΥ=Υ " 。 1Υ 2Υ 3Υ 1−ΥT TΥ TΧΧΧ=Χ "21 … 图 4 CRFs http://www.paper.edu.cn -12- 中国科技论文在线 4.3 条件随机场概率模型的形式 Lafferty 对 CRFs 势函数的选择很大程度上受最大熵模型的影响[13]。定义每个势函数的 形式如下： )),|,(exp()( ∑=Φ k kkcy xcycfyc λ (38) 其中 cy | 表示第 c个团中的节点对应的随机变量， kf 是一个布尔型的特征函数，则 )|( xyp 为： ∑∑ ∈ = Cc k ckk xycfxZ xyp ),,(exp( )( 1)|( λ (39) 其中 )(xZ 是归一化因子， ∑ ∑∑ ∈ = y Cc k ckk xycfxZ ),,(exp()( λ (40) 在一阶链式结构的图 ),( EVG = 中，最大团仅包含相邻的两个节点，即是图G 中的边。 对于一个最大团中的无向边 ),( 1 ii vve −= ，势函数一般表达形式可扩展为： )),,(),,,(exp()( 1∑ ∑+=Φ − k k ikkiikkcy ixysixyytyc μλ (41) 其中 ),,,( 1 ixyyt iik − 是整个观察序列和相应标记序列在 1−i 和 i时刻的特征，是一个转 移函数。而 ),,( ixys ik 是在 i时刻整个观察序列和标记的特征，是一个状态函数。联合概率 的表达形式可以写为： )),,(),,,(exp( )( 1)|( 1 ∑∑∑∑ += − i k ikk i k iikk ixysixyytxZ xyp μλ (42) 其中，参数 kλ 和 kμ 可以由从训练数据中估计，大的非负参数值意味着优先选择相应的 特征事件，大的负值所对应的特征事件不太可能发生。 定义特征函数之前，先构造观察序列的实数值特征 ),( ixb 集合来描述训练数据的经验分 布特征，这些特征与模型同分布。例如： ⎩⎨ ⎧ == otherwise septemberxif ixb i 0 1 ),( (43) 每个特征函数表示为观察序列的实数值特征 ),( ixb 集合中的一个元素，如果当前状态 （状态函数）或前一个状态和当前状态（转移函数）具有特定的值，则所有的特征函数都是 实数值。例如转移函数： ⎩⎨ ⎧ === −− otherwise MyByifixb ixyyt iiiik 0 ,),( ),,,( 11 (44) 为了统一转移函数和状态函数的表达形式，我们可以把状态函数写为下式： ),,(),,( 1 ix，yysixys iikik −= (45) 并用 ),,( 1 ix，yyf iik − 统一表示， kf 可能是状态函数 ),,( 1 ix，yys iik − 或转移函数 ),,,( 1 ixyyt iik − ，又令： http://www.paper.edu.cn -13- 中国科技论文在线 ∑ = −= T i iikk ixyyfxyF 1 1 ),,,(),( (46) 从而结定观察序列 x条件下，相应的标记序列为 y的概率可以写为： )),(exp( )( 1)|( ∑= k kk xyFxZ xyp λ (47) 其中 )(xZ 是归一化因子。 4.4 条件随机场模型的参数估计 以上的 CRFs 理论介绍给出了 CRFs 的概率形式公式，主要是基于最大熵理论，下面将 介绍的是 CRFs 模型的参数估计，由最大熵模型可知参数估计的实质是对概率的对数最大似 然函数求最值，即运用最优化理论循环迭代，直到函数收敛或达到给定的迭代次数。 假设给定训练集 { }),(,),,(),,( 2211 ΓΓ ΥΧΥΧΥΧ= "D ，根据最大熵模型对参数λ估 计采用最大似然估计法。条件概率 ),|( λxyp 的对数似然函数形式为： ∑∏ == yxyx yxp xypyxpxypL ,, ),(~ ),|(log),(~),|(log)( λλλ (48) 已知条件概率 ),|( λxyp 的形式化公式为： )),(exp( )( 1),|( ∑= k kk xyFxZ xyp λλ 其中归一化因子 )(xZ 的表达式为： ∑ ∑= y k kk xyFxZ )),(exp()( λ 对于该 CRFs 概率模型来说，对数最大似然参数估计的任务是从相互独立的训练数据中 估计参数 ),,,( 21 nλλλλ "= 的值，则对数似然函数可写为下式： ∑∑ ∑ −= xyx k kk xZxpxyFyxpL )(log)(~),(),(~)( , λλ (49) 为了表达，假设链式结构的无向图分别有一个特殊的起始节点和终止节点，分别用 0Υ 和 1+Υn 表示。则经验分布概率和由模型得到的概率的数学期望为： ][),(),(~),,,(),(~][ ~ , 1 1 1 , ~ kpk yx n i iik yx def kp FEyxFyxpixyyfyxpfE === ∑∑∑ + = − (50) ][),(),|()(~),,,(),|()(~][ , 1 1 1 , kpk yx n i iik yx def kp FEyxFxypxpixyyfxypxpfE === ∑∑∑ + = − λλ (51) 我们根据对数似然函数对相应的参数 kλ 求一阶偏导数： ∑ ∑ ∑∑ ⎥⎥ ⎥⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎣ ⎡ ⎥⎦ ⎤⎢⎣ ⎡ ⋅ −=∂ ∂ x y k kk yx k k xZ yxFyxF xpxyFyxpL )( ),()),(exp( )(~),(),(~)( ,λ λ http://www.paper.edu.cn -14- 中国科技论文在线 )( ),()),(exp( )(~][ , ~ xZ yxFyxF xpFE k kk yx kp ∑∑ ⋅ −= ∑−= yx kkp yxFxypxpFE , ~ ),(),|()(~][ λ ][][~ kpkp FEFE −= (52) 通过梯度为零来求解参数λ并不一定总是得到一个近似解，因而需要利用一些迭代技术 来选择参数，使对数似然函数最大化。通常采用的方法是改进的迭代缩放（Improved Iterative Scaling, IIS）或者基于梯度的方法来计算参数。以上的介绍中，我们给出了对数似然函数 )(λL 梯度的计算表达形式，即经验分布 ),(~ yxp 的数学期望与由模型得到的条件概率 ),|( λxyp 的数学期望的差。而经验分布的数学期望为训练数据集中随机变量 ),( yx 满足特 征约束的个数，模型的条件概率的数学期望的计算实质上是计算条件概率 ),|( λxyp ，在下 一节中我们将介绍条件概率的有效计算方法。 4.5 条件概率的矩阵计算 建立条件随机场模型的主要任务是从训练数据中估计特征的权重λ。下面主要对 CRFs 用到最大似然估计方法进行介绍。 由上面可知，条件随机场对数似然函数的梯度公式如下： ][][)( ),|(),(~ kxypkyxp k FEFEL λλ λ −=∂ ∂ 如果直接使用对数最大似然估计，可能会发生过度学习问题，通常引入罚函数的方法解 决这一问题。如使用惩罚项 2 2 2σ λ∑ k k ，则对数似然函数和对数似然梯度公式变为： 2 2 , 2 )(log)(~),(),(~)( σ λ λλ ∑∑∑ ∑ −−= k k xyx k kk xZxpxyFyxpL (53) 2),|(),(~ ][][ )( σ λ λ λ λ k kxypkyxp k FEFEL −−=∂ ∂ (54) 由此，参数估计问题可以用最优化方法解决，可以使用迭代方法或 L-BFGS 算法。 对于一个链式条件随机场，我们在图的模型中添加一个开始状态 0Υ 和一个结束状态 1+Υn 。У 为按字母排序的标记列表， yyi ′=−1 和 yyi = 是取自该列表中的标记。我们定义 一组矩阵{ }1,,2,1|)( += nixM i " ，其中每个 )(xM i 是 У×У阶的随机变量矩阵。 )(xM i 中 的每个元素 )|,( 1 xyyM iii − 定义为： )),,,(exp()|,( 11 ∑ −− ==′= k iikkiii ixyyfxyyyyM λ )),,(),,,(exp( 1 ∑∑ += − k ikk k iikk ixysixyyt μλ (55) 其中 1−iy 为 iy 的前一个标记， )|,( 1 xyyM iii − 是前一个状态到当前状态的转移概率与 当前状态以观察序列为条件的概率的乘积，图示如下： http://www.paper.edu.cn -15- 中国科技论文在线 如上图显示 ))|()|,(exp()|,( 331312 ∑∑ += k kk k kk xysxyytxyyM λλ ，且有： [ ])|,()|,()|,()( 3012011011 xyyMxyyMxyyMxM = ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ = )|,()|,()|,( )|,()|,()|,( )|,()|,()|,( )( 332232132 322222122 312212112 2 xyyMxyyMxyyM xyyMxyyMxyyM xyyMxyyMxyyM xM ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ = + + + + )|,( )|,( )|,( )( 31 21 11 1 xyyM xyyM xyyM xM nn nn nn n 因为 ),|( λxyp 实际上是从开始节点到结点节点的一条路径的概率，所以有： ∏+ = −= 1 1 1 )|,()( 1),|( n i iii xyyMxZ xyp λ (56) 其中 )(xZ 为归一化因子，为所有路径概率的和，表达式如下： ∏+ = = 1 1 )()( n i i xMxZ (57) 不论是使用迭代缩放还是 L-BFGS 算法进行参数估计与训练，为了计算最大似然参数 值，就需要对训练数据中的每个观察值Χ对应的标记序列的条件概率相对特征函数的数学 期望进行有效的计算。枚举计算是不可行的，Lafferty 提出了动态规划方法来计算 ][),|( kxyp fE λ 。 ∑∑ + = −= 1 1 1 , ),,,(),|()(~][ n i iik yx def kp ixyyfxypxpfE λ 上式的右边可以改写为： ∑∑∑ + = ′ −− =′==′= 1 1 , 11 ),,,(),|,()(~ n i yy iikii x ixyyyyfxyyyypxp λ (58) 而后，可使用动态规划方法计算 ),|,( 1 λxyyp ii− ，该方法与隐马尔可夫模型中介绍的 forward-backward 算法类似，我们分别定义 forward 向量和 backward 向量为 )(xiα 和 )(xiβ ， 则构造步骤如下： 3 2 1 3 2 1 3 2 1 1x 2x nx 0 n … … … 图 5 M 矩阵计算 )(1 xM )(2 xM )(1 xM n+ ))|,(exp( 31∑ k kk xyytλ ))|(exp( 3∑ k kk xysμ http://www.paper.edu.cn -16- 中国科技论文在线 ⎩⎨ ⎧ == otherwise startyif xy 0 1 )|(0α ⎩⎨ ⎧ ==+ otherwise stopyif xyn 0 1 )|(1β (59) 递归关系表示为： )()()( 1 xMxx i T i T i −=αα )()()( 11 xxMx iii ++= ββ (60) 由以上公式可知，在给定观察序列 x条件下， yyi ′=−1 和 yyi = 的概率为： )( )|()|,()|( )|,( 11 xZ xyxyyMxy xyyyyp iiiii βα ′′==′= −− (61) 由上式可以有效计算出条件概率的数学期望。