[2-3]。近年来,交集型歧义的切分问题吸引了众多研究者目光,迄今为止,多种方法被提出,这些方法大体可分为三类: 基于规则的方法、基于实例的方法和基于统计的方法。
   4期任惠等: 融合字特征的平滑最大熵模型消解交集型歧义
中 文 信 息 学 报     2010年
基于规则的方法利用人工编写的语法规则消解交集型歧义,取得了一定的效果^[4]。但人工编写不可避免会遇到系统性、有效性、一致性和可维护性等规则系统的“天然”问题困扰^[5],如今面对互联网上大规模真实文本处理的压力,纯规则的方法基本被抛弃。
   基于实例的方法事先搜集歧义字段及其正确的切分形式形成实例库^[6-7],文献[3,8]在库中还存储实例的上下文信息,歧义消解通过库检索即可实现。基于实例方法简单有效,但其消歧能力依赖于库中实例的数量,泛化能力弱,常常作为其他方法的补充。
   为克服上述两类方法的缺陷,研究人员尝试了多种统计的方法。有指导的概率统计方法通过计算待消歧字段所有可能的切分路径的概率,并把概率最大者作为消歧字段的消解结果^[9-10];无指导的统计方法利用互信息和t-测试差解决歧义切分问题^[11];有些研究人员将歧义消解问题转化为分类问题,通过分类模型来消解歧义^[2,12-13]。上述方法均取得了较好效果,但也存在一些问题,主要集中在消歧知识不足、消歧对象受限、消歧精度有待提高和模型特征难以获取四个方面。
   近年来,最大熵模型被广泛用来解决各种自然语言处理问题,如: 分词^[14]、词性标注^[15]、实体识别^[16]、Chunk识别^[17]、句法分析^[18]和机器翻译^[19]等,对上述问题都达到或超过了其他方法的最好结果。与其他统计机器学习方法相比,最大熵方法能够将各种不同的知识融合在统一的算法框架中,且独立于特定的任务,具有模型简洁、通用和易移植的优点。鉴于该方法在上述诸多自然语言处理题上都取得了相当优异的性能,我们也采用它来解决交集型歧义。我们首先将交集型歧义的消解问题转化为一个二分问题,然后利用融合丰富字特征的最大熵模型来解决该分类问题。此外,为了克服建模时的数据稀疏问题,我们引入了不等式平滑技术^[20]和高斯平滑技术^[21],它们都是通过放松标准最大熵建模时的特征期望等式约束来改善数据稀疏问题。本文的另一大特色是我们选择基于字的特征而不是基于词的特征作为消歧知识。我们这样做基于如下理由: 首先基于字的特征可以直接从未切分文本中获取,这使得本文的算法可以在任何自然语言处理应用中直接应用,大大降低了本算法的应用难度。基于词特征的消歧算法在应用时另外需要一个单独的分词程序。其次,基于字的特征比基于词的特征更加紧凑,这是因为中文词是一个开放集,真实文本中未登录词的比例比生字要高得多。第三,我们观察到在分词任务上,字特征比词特征更加有效^[14]。我们相信在组合型歧义消解问题上依然有效,因为在解决这两个分类任务时都需要相同的知识源。最后,基于字的特征可以产生丰富的单字、双字、多字这样交叠性特征,而最大熵模型最大的优点就是能够将各种特征融合到一个统一的框架,通过逐步增加特征来提高性能。
   本文提出的方法较好地弥补了前人工作的一些不足。首先,模型特征融合了丰富的消歧特征,这些特征不仅包含歧义字段及其上下文信息,还包含歧义字段与其上下文相混合信息。以前的方法仅仅利用歧义字段及其前后词、词性和互信息作为消歧知识源^[2,12-13],消歧知识的不足使消歧对象受限,也制约了消歧性能。文献[13]仅能消解三字长伪歧义,而文献[12]仅能消解三字长伪歧义和部分三字长真歧义,而本文不仅能处理伪歧义,也能处理真歧义;不仅能消解三字长歧义,也能消解其他长度的歧义,同时使消歧性能也大幅度的提高。其次,我们使用基于字的特征,这些特征无需统计、分词及词性标注等深层处理,可直接从文本中抽取,大大降低了算法应用难度。而以前的方法或需要统计信息,或需要词汇和词性信息作为特征^[12-13],在歧义消解时需要词汇词性等深层信息,分词和词性标注的错误不可避免地传播到歧义消解阶段。最后,以前的方法^[2,12-13]都没有采取平滑措施缓解数据稀疏问题,而本文通过采用平滑措施来放松模型中的特征期望约束,有效缓解数据稀疏问题,使得消歧性能得到进一步提高。
   我们在第三届国际分词竞赛的四个数据集上进行了测试,分别获得了96.27%、96.83%、96.56%、96.52%的消歧正确率,对比实验表明: 丰富的特征使消歧性能分别提高了5.87%、5.64%、5.00%、5.00%,平滑技术使消歧性能分别提高了0.99%、0.93%、1.02%、1.37%,不等式平滑使分类模型分别压缩了38.7、19.9、44.6、9.7。我们的方法在四个不同的数据集上获得了相同的结论,证明了我们方法在不同数据集上的一致性。
   2 利用不等式最大熵模型消解交集型歧义2.1 问题定义 本文将交集型歧义消解问题转化为分类问题,分类空间定义在歧义字段的FMM和BMM切分结果O_f和O_b中。这样交集型消解问题可以转化为一个二分问题:
   公式（1）
其中,Seg(Seg∈ {O_f,O_b})是歧义字段的消歧结果,P(O_f|C)表示在条件C下歧义字段切分结果为O_f的概率,P(O_b|C)表示在条件C下歧义字段切分结果为O_b的概率。这样,消歧过程就是根据公式(1)选择较大概率的过程。
   2.2 最大熵模型
   最大熵原理要求建模时拟合所有已知事实,而对未知事实不做任何附加假设。与其他的统计机器学习方法相比,最大熵模型能够方便将各种不同的知识(特征)融合在一个统一的算法框架而不需要在这些特征之间存在任何独立性假设。最大熵模型能够应用于任何分类问题,对于交集型歧义消解任务而言,它为歧义字段的每种分类结果(O_f,O_b)产生一个条件概率,该条件概率可以通过公式(2)计算得到:
   公式（2）
其中C表示了歧义字段拥有的特征集,Seg是歧义字段的分类结果,Z_λ(x)是正规化常数。f_i表示了第i个特征,k是该歧义字段拥有的特征总数,最大熵建模时要求每个特征的经验期望值与模型估计期望值相等。即:
   公式（3）
前者为f_i在训练样本中的经验期望值,后者是f_i在模型估计时的模型期望值。
   2.4 模型平滑与特征选择
   从某种程度上讲,最大熵模型也是一种最大似然对数模型,同其他最大似然估计方法一样,当训练数据比较稀疏时,模型也会过度拟合训练数据,这说明应用最大熵法解决NLP任务也需要进行平滑。当前各种平滑算法被引入最大熵模型^[21]。文献[21]在多个NLP任务上,考察了高斯平滑技术与其他平滑技术,测试结果表明: 高斯平滑技术在所有NLP任务上都获得同等或者优于其他其他方法的性能。该方法本质上是利用高斯先验分布通过公式(4)来惩罚那些正值或负值很大的权重,使模型更少拟合训练数据。
   公式（4）
最近文献[20]提出一种称为不等式平滑技术的胖约束,通过赋予期望约束一定宽度的滑动范围来放松该公式(3)所规定的特征期望约束:
   公式（5）
公式中A_i, B_i是第i个特征的宽度滑动范围,通过该滑动范围,可以放松每个特征的期望相等约束(传统最大熵模型规定每个特征的理论期望值应该与通过训练语料计算得到的该特征的期望相等),使得模型不会过度拟合训练数据。
   文献[20]在两个文本分类任务上比较了不等式平滑技术和高斯平滑技术,测试结果表明采用不等式平滑技术比结合频度折扣的高斯平滑技术更优,本文也通过实验对各平滑技术在缓解模型数据稀疏问题上的效果进行了对比。
   2.5 特征选择
   特征选择的任务是从训练样本所有特征中挑出期望值能被可靠估计的特征,不是所有的特征对分类能力都有贡献,太多的特征不仅会增加模型的训练时间,而且导致模型过度拟合训练样本。常用的特征选择方法有: 基于信息增益的方法及其近似算法^[22]和基于频度折扣的方法^[15,17]。基于信息增益的方法每次选择使模型熵增加最多的特征,使得每次特征选择阶段都要计算所有特征的信息增益,因此耗时较多;基于信息增益的近似算法认为加入一个特征后的模型仅依赖于原来的模型和参数λ,该方法比较快,但是不能保证每次加入模型的特征都是最好的;基于频度折扣的方法事先根据经验设定或者根据开发集来调节折扣阈值K,特征选择时认为频度小于或等于K的特征都不可靠,只挑选那些频次大于K的特征,但是Walter Daelemans et al.^[23]指出低频特征也包含对分类有贡献的信息。所以,我们在采用基于频度折扣的特征选择方法时,不是事先设定一个固定的阀值,而是在一定范围内穷举所有可能的阀值,根据开发集来确定最佳阀值。另外,不等式平滑技术能够将特征选择与参数估计无缝结合在一起,从模型中除去那些权重为零的特征而不会影响模型的分类行为。Kazama和Tsujii ^[20]演示了不等式平滑技术在特征选择上比频度折扣方法更优,我们在实验中采用该方法。
   2.6 参数估计
   参数估计用来求解公式(2)中参数λ,参数估计常用的方法有: 通用迭代算法(GIS) ^[24]、改进的迭代算法(IIS) ^[22]、梯度法和变度量法及其变体等。文献[25]在四个NLP任务上考察了GIS、IIS、梯度法和有限存储变量尺度法(LMVM)(变度量法的一种变体),结果显示: 对于NLP分类问题,LMVM性能最好。文献[20]测试了限界约束有限存储变量尺度法(BLMVM)(LMVM一种变体)^[26]也证实了类似结论,并指出,在真实NLP数据集上,BLMVM能在更短的时间达到收敛,而且分类性能有所提高,因此我们在实验中使用BLMVM进行参数估计。
   3 特征表示3.1 利用临界切分法切分文本 歧义检测是消解歧义的前提。目前歧义检测的主要方法有: 双向最大匹配法^[27]、最小分词法^[28]、全切分法^[29]和临界切分法^[30]等。前两种方法都存在检测盲点,全切分法虽然无检测盲点,但它的切分路径随文本长度成指数增长,而临界切分法不仅能检测出所有歧义,而且其切分路径只随文本长度成线性增长。文献[3]详细介绍了上述每种方法优劣并给出了相应的检测实例。
   本文中,我们利用临界切分法切分文本,并将切分得到的临界段作为部分消歧知识源。文献[30]给出了临界切分法的定义并证明: 给定词表,对于任意文本,无论该文本怎样被切分,临界点都是文本中所有非歧义的切分边界,相邻两临界点间字符构成一个临界段。临界切分法的示例见图1。
   
图1 临界切分法示例
算法先逐字正向最大匹配待切分文本,再检查匹配得到的词之间是否相互交叉覆盖关系,并将交叉覆盖的词凝聚成更长的串,如: “地产”、“产”和“房地产”被凝聚成“房地产”;“从前”、“前所未有”、“所”、“未”、“有的”、“的”被凝聚成“从前所未有的”,直到所有串之间不存在任何交叉覆盖关系。临界切分法将文本分割成临界段序列,不同临界段中的字符不相关,而所有相关的字符都必然包含在同一临界段内。
   3.2 特征模板
   最大熵模型分类能力取决于是否选择合适足够的模板,为此我们设计了丰富的基于字的特征模板。并把它们分为歧义字段上下文信息模板,歧义字段自身信息模板和混合信息模板。这些模板详细定义见表1。
   这些模板中,C 表示文本中的字符。模板1表示歧义字段周围六个字符,模板4中C_s表示歧义字段的第一个字符,C_e表示歧义字段最后一个字符。模板2表示歧义字段周围三个临界段,我们用CF₀表示歧义字段自身,这些临界段可以通过3.1中临界切分法获得。模板6表示歧义字段自身包含的汉字体个数。模板1、3、4、6、7独立于具体语言,因为这些模板能够应用于任何语言,并且当它们作用于具体的训练数据时,特征值能从模板中自动获取。而模板2和5依赖于具体语言。
表1 交集型歧义消解用的模板特征定义

特 征 类 型 序号 模 板 模 板 意 义

歧义字段上下文信息 1 Cn(n=-3,-2, -1, 1, 2,3) 歧义字段前后各三个字符 2 CFn(n=-3, -2,-1, 1,2,3) 歧义字段前后各三个临界段 3 C-1C1, C-2C-1, C1C2 指定序号的连续两个字符

歧义字段自身信息 4 Cs, Ce 歧义字段的首字和尾字 5 CF0 歧义字段自身 6 Length 歧义字段包含的汉字个数

混合信息 7 C-1Cs, CeC1 歧义字段混合其上下文

4 实验4.1 实验数据准备和歧义字段分布 实验数据来自第三届国际分词竞赛提供的四个训练语料和测试语料。我们从四个训练语料中分别抽取交集型歧义字段及其特征(特征模板见表1)形成样本空间作为训练集,从四个测试语料中抽取交集型歧义字段及其特征作为测试集。歧义检测采用临界切分法,临界切分法所用的词表直接从各自训练语料中获取。因为本文主要考察最大熵模型的分类能力,对于那些切分结果不在分类空间(O_f或O_b)中的歧义字段,我们将它们从样本中剔除出去。表2显示了各个训练集、开发集和测试集中的交集型歧义分布情况。

表2 训练集、开发集和测试集中的交集型歧义分布情况

语料 Of (Of≠Ob) Ob(Of≠Ob) Of=Ob 语料 Of(Of≠Ob) Ob(Of≠Ob) Of=Ob

CKIP CTU Train 35 860 43 291 49 759 MSR Train 15 048 12 029 20 048 Eval 739 862 1 227 Eval 556 478 881 Train 7 068 11 792 17 071 UPUC Train 5 820 7 429 11 105 Eval 196 243 407 Eval 493 573 1 146

4.2 模型训练和控制参数调节
   在实验中,我们比较了结合频度折扣的标准最大熵模型(Cut-off)、高斯最大熵模型(Gaussian)和不等式最大熵模型(Inequality)三种平滑技术,模型中的参数λ采用BLMVM^[26]进行估计,最大熵模型软件包来自互联网^[31],实验中所使用的版本为1.3.2。该软件包提供了这三种模型的训练和测试接口,这样我们能够在同等基础上比较这些模型的性能。实验中我们来计算消歧正确率(消歧正确率=(利用最大熵算法正确消歧的个数)/(测试语料中交集型歧义的个数))。由于最大熵模型中需要事先确定某些控制参数,我们利用开发集在一定范围内以穷举的方式搜索最好的控制参数,也就是说,当模型在开发集上达到最佳性能时,即可得到最佳控制参数。标准最大熵模型的控制参数是频度阈值cthr,我们在[0,5]范围内以步长为1的递增方式进行穷举式搜索;高斯最大熵模型的控制参数是方差σ,虽然公式(4)允许我们为每种不同的特征采用不同的方差,在实验中我们使用相同的方差,并在[100, 1 000]范围内以步长为100的递增方式进行穷举式搜索;不等式最大熵模型的控制参数是宽度因子W,虽然公式(5)允许每种特征的宽度因子可以不同,实验中我们为所有特征设置相同的宽度因子W,并分别在[10^-5,10^-1]区间中以10倍递增方式和[0.1,1]区间以步长为0.1的递增方式进行穷举式搜索。实验中我们采用公式(6)来计算每个宽度值:
   公式（6）
表3给出了各种模型在各个开发集上的最优控制参数值。
表3 最优控制参数一览表

UPUC 模型 参数 值 Cut-off cthr 0 Gaussian σ 0 Inequality W 8 MSR 模型 参数 值 Cut-off cthr 2 Gaussian σ 0 Inequality W 10

CTU Cut-off cthr 0 Gaussian σ 0 Inequality W 3 CKIP Cut-off cthr 0 Gaussian σ 0 Inequality W 1

4.3 测试
   利用得到的各种最优模型对测试集进行测试。表5显示了不等式平滑技术的特征选择能力,相比最优Cut-off模型,不等式平滑技术能有效压缩模型规模。

表5 不等式平滑技术的特征选择能力

UPUC 模型 特征 数目 压缩比 Cut-off 55 787 Inequality 1 440 38.7 MSR 模型 特征 数目 压缩比 Cut-off 112 702 Inequality 2 529