第4卷第5期 智能系统学报 VoL.4 No.5 2009年10月 CAAI Transactions on Intelligent Systems 0ct.2009 doi:10.3969/j.i8sn.16734785.2009.05.004 基于双向标注融合的汉语最长短语识别方法 鉴萍，宗成庆 (中国科学院自动化研究所模式识别国家重点实验室，北京100190) 摘要：汉语最长短语（最长名词短语和介词短语）具有显著的语言学特点.采用基于分类器的确定性标注方法进行 双向标注，其结果能够显示最长短语识别在汉语句子正（由左至右）反（由右至左）2个方向上的互补性.基于此，利 用确定性的双向标注技术来识别汉语最长短语，并提出了一种基于“分歧点”的概率融合策略以融合该双向标注结 果实验表明，这一融合算法能够有效发掘这2个方向的互补特性，从而获得较好的短语识别效果. 关键词：最长名词短语识别；介词短语识别；序列标注；双向标注；分歧点 中图分类号：TP391 文献标识码：A文章编号：16734785(2009)05040608 A new approach to identifying Chinese maximal-length phrases using bidirectional labeling JIAN Ping,ZONG Cheng-qing National Laboratory of Pattern Recognition,Institute of Automation,Chinese Academy of Sciences,Beijing 100190,China) Abstract:Chinese maximal-length phrases (maximal-length noun phrases and prepositional phrases)possess re- markable linguistic properties.Bidirectional labeling results of Chinese maximal-length phrases obtained using se- quential classifiers reveal complementary properties in both directions.In this paper,both left-right and right-left sequential labeling were employed to identify the Chinese maximal-length noun phrases and prepositional phrases. Then a novel "fork position"based probabilistic algorithm was developed to fuse the bidirectional results.Experi- ments were carried out on the Penn Chinese Treebank,a segmented,part-of-speech tagged,and fully bracketed corpus.The results confirmed that the proposed algorithm is able to effectively exploit the complementary strengths of the two directions. Keywords:maximal-length noun phrase identification;prepositional phrase identification;sequence labeling;bidi- rectional labeling;fork position 组块分析(chunking)是自然语言处理一个重要 自动文摘等其他自然语言处理任务提供帮助， 的子任务，它将句子切分为结构相对独立而且互不 最长名词短语(maximal-length noun phrase, 重叠的组块（短语），以降低完全句法分析的难度. MNP)和介词短语(prepositional phrase,PP)是2种 实际上，与基本短语相比，如果能雅确地分离出句子 重要的、研究较多的短语类型.实际上，介词短语也 中的最长短语成分，将更大程度地降低完全句法分 可以有最长和最短之分，但是由于介词短语的嵌套 析的歧义.所谓最长短语，是指不被其他任何相同类 在汉语句子中比较少见（据统计，宾州中文树库 型短语所包含的短语.它与最短（基本）短语相对， V5.011中共有5.28%的介词短语具有嵌套现象)， 内部可包含多种成分结构，是一个完整的语义单元. 最长介词短语(maximal-length prepositional phrase, 除了作为完全句法分析的预处理以外，最长短语识 MPP)和一般介词短语(PP)通常不做区分.本文以 别后得到的清晰的句子结构框架还将为机器翻译、 汉语最长名词短语和介词短语的识别为任务，并在 以下章节中用MNP和PP分别表示这2种短语.本 收稿日期：200908-28. 基金项目：国家自然科学基金资助项目(60736014、90820303)；“十一 文中的PP严格来说是指MPP. 五”国家科技支撑计划项目(2006BAH03B02):国家“863” 识别MNP和PP的传统方法是估计短语的边界 计划资助项目(2006AA0101084):中国新加坡数字媒体研 究院资助项目. 概率分布[2).而已有实验结果证明这类方法通常 通信作者：鉴萍.E-mail:pjian@nlpr.ia.ac,cm 只有加入了规则或语言知识才能取得较好的效
第5期 鉴萍，等：基于双向标注融合的汉语最长短语识别方法 ·407· 果3].原因是这类短语具有比基本短语等其他类 注结果来识别汉语MNP和PP.首先，通过对汉语语 型的短语更复杂的结构，特别是对汉语来说.汉语的 法现象的初步考察，发现采用基于分类器的确定性 短语套叠现象比较普遍，一个某种类型的最长短语 标注方法进行双向标注，其结果可以体现汉语句子 可以包含其他所有类型的短语成分，甚至可以包含 在2个方向上的互补性.据此，使用短语级融合策略 一个从句.而且它们具有长距离的依存关系，仅依赖 融合该双向结果，但同时证明使用位置级投票结果 边界信息会带来更多歧义.所以研究者们起初都是 的短语级融合在基于历史的标注系统中并不能得到 试图从最长短语的内部结构或其所处的外部环境寻 很好的效果.因此，提出了一种基于“分歧点”的概 找规律，判定它的边界.这需要耗费一定的时间和人 率融合算法，以实验证明这一融合算法能够发掘这 力来熟悉该种语言的短语特性. 2个方向的互补特性，并得到较好的识别精度， 近些年来，采用序列标注模型和复杂机器学习 1 汉语中的特殊语法现象 方法，t如HMMs(hidden Markov models)、SVMs(up port vector machines)CRFs conditional random 汉语不是严格具有中心词方向性(head-direct- fields)等进行组块分析，特别是基本名词短语的识 d)的语言.这给从单一方向进行汉语句法分析带 别，取得了很大的成功[6).作为相似任务，人们也 来了困难.但是如果把组块分析作为完全句法分析 试图将最长短语的识别看作一个序列标注问题，利 的前处理，这一问题将会得到缓解.因为与很多印欧 用机器学习方法提高识别系统的可移植性.文献 语言（如英语）不同，大多数的汉语短语是具有中心 [9]将基于SVM分类器的序列标注算法作为其汉 词方向性的们.例如，汉语名词短语以名词为中心 语MNP识别系统的基线方法，通过加入扩充组块特 词，中心词一般在短语尾部，而英语名词短语的中心 征和分类标点特征来提高识别精度.其基线系统和 词位置要灵活一些.图1给出了2个例子，中心词用 改进系统分别取得了87.01%和89.66%的F,值性 下划线标出， 能.文献[10]使用CRFs进行汉语MNP的标注，其 一般人的看法 二阶模型对长度大于4个词的复杂MNP的识别能 the view of average person 力达到了70.3%.这些工作证明了序列标注算法对 政府和军队邈导人 the government and army leaders 最长短语的识别同样是有效的，但与基本短语相比， 识别性能要差很多.主要原因是基于焦点词周围有 图1名词短语及其中心词举例 限特征信息的序列标注模型很推捕捉最长短语内部 Fig.1 Examples of Chinese NP and their heads 的长距离关联.需要根据语言本身的特性选择合适 据统计，宾州中文树库V5.0的83065个MNP 的标注算法和识别策略。 中约有97.2%是以最后一个词为中心词的.极少数 输出级的系统融合技术已被广泛用于提高基本 是以成对标点（如括号）或词“等”为中心词.另外， 短语识别系统的性能？，12]，多是采用投票的方法 汉语名词短语中频繁使用的结构助词“的”也通常 从多个系统输出结果中产生出一个最好的结果.文 位于短语的后半部分，特别是对长短语来说， 献[7]和[11]在序列的每一个位置上进行投票.因 可以肯定，如果采用基于历史标注结果的决策 为只考虑某一位置上的最好结果，这类方法有可能 模型，句子中的名词和助词“的”必能在该模型由右 生成不合法的输出.文献[12]提出了基于句子和基 至左（即反向）对MNP进行标注时起到指导作用， 于短语的投票方法，拥有最多在位置级投票中获胜 减少判定短语左边界时的歧义.理论上讲，在基于历 的标记的句子级/短语级候选将作为最后输出，候选 史的标注模型中，汉语MNP的反向标注结果要好于 标记序列的合法性可以保证融合结果的合法性.文 正向标注结果 献[12]还以实验证明了以上所述3类融合策略中， 但这并不表明MNP的正向标注没有可取之处， 短语级融合达到了基本短语识别的最好效果.另外， 些冠词和形容词可以作为名词短语的起始标志. 当候选系统数量较少或候选结果得到的票数相等 对于图2中的第1个例子，如果从右向左进行判别， 时，可使用加法准则、乘法准则等概率融合策略代替 标注器可能会受动词“违背”的影响，把“约定”判定 投票，其前提是可以获得各个候选结果的条件后验 为短语的左边界（名词短语常在动词后面做动词的 概率， 宾语).而从左向右标注则更有可能正确识别左边 本文将选择合适的序列标注算法，并融合正向 界“这”，因为语料中限定词(POS(part of speech)标 (由左至右)和反向（由右至左）2个方向的序列标 记为DT)常作为名词短语的起始词.同理，图2第2
·408 智能系统学报 第4卷 个例子中的形容词“惟一”(POS标记为刀)可以作 结点（标记）之间存在一阶马尔可夫性，每一个标注 为正向标注的标志词， 位置(y:)的状态只与前一个位置(：-1)有关.各标 这种违背约定的行为 注位置之间更紧密的关联需要使用高阶的马尔可夫 DT M VV NN DEC NN 依赖模型.例如在二阶CRF模型中，以组块分析为 惟·有资格在欧盟内部发行欧元的机构 例，位置i上的输出可表示为y:=t-1t:,t:-1和t:分 JJ VE NN P NR NN VV NN DEC NN 别是i-1和i位置的组块标记.马尔可夫依赖存在 图2汉语名词短语起始位置的限定词和形容词 于标记组-2t-1和-1t:之间，即y-1=t-2t-1 Fig.2 Determiner and adjective at the beginning of Chinese 与基于CRFs的判别式模型不同，使用序列分 NPs 类器的标注算法本质上是一个确定性模型.它将序 汉语PP以介词为中心词并且中心词多位于短 列标注看作一串分类问题，使用分类器为每一个位 语首（在宾州中文树库中这一比例为98.21%），特 置选择最优标注结果，以单个位置上的局部最优近 殊情况是修饰介词中心词的副词等会出现在介词的 似全局最优.给定当前标注状态c,位置i的最优预 前面.因此，介词是PP识别的一个最明显标志，将 测为 指引标注器正确判断PP的右边界.这也证明了对 y:=arg maxp(yl c,i). 汉语PP的正向标注效果要好于反向标注。 c通常表示为一组当前标注时刻的上下文特征.因 反向标注汉语PP也有可以捕捉的标志词，如 为算法在标注的每一步都做出决策，标注状态确定 表方位的PP“在…上”和“当…时”中的方位词“上” 性地传递，后续的决策可以使用前面已产生的所有 和“时”.另一个反向标注具有的优势是它可以避免 正向标注对PP右边界后面第一个词的过分依赖. 标注结果，即c可以包含y-1,y:-2,…,o·各种分类 算法里，SVMs在序列标注模型中应用最多同时也 因为语料中介词短语常出现在动词前面，所以正向 具有较好的效果] 标注器可能会直到遇见动词才确定短语的右边界， 基于CRFs的标注模型和基于SVMs的标注模 造成标注错误.反向标注则不会出现这样的问题。 型都有很好的特征表达能力.CRF模型的优点是可 综上所述，基于历史特征的标注模型对汉语 以得到全局最优解，但同时也导致其计算因子之间 MNP或PP正反2个方向的识别能力有一定的差 具有不确定性，算法不能很好地捕捉序列中的长距 异.但由于汉语本身的特点，这2个优劣不同的结果 离关联.使用高阶模型可以起到一定的缓和作用，但 之间仍具有互补性.而且在理论上，随着短语长度和 相应的计算消耗也会急剧增加.与此相比，基于 内部依存关系距离的增长，这一互补性也将增强.基 SVMs的确定性模型因为可以参考已有标注结果， 本短语因为结构简单，缺乏能使不同方向标注结果 更易于发现序列元素之间的依存关系，贴合识别汉 产生较大差异的长距离依存歧义，所以其双向标注 语最长短语所需要的“基于历史特征的标注模型” 结果的差异较小，互补性也较弱.文献[7]的实验结 在此类模型中，已有标注历史是以特征的形式应用 果和文献[14]的预备实验结果显示了这一特点在 于当前决策，历史标记元数的增长不会给算法带来 基本名词短语分析任务上的体现， 过多计算负担.因此，结合上一节对汉语最长短语特 2 选择合适的序列标注方法 点的分析，选择基于SVM分类器的确定性标注模型 进行汉语MNP和PP的识别. 判别式的（如基于MEMM(maximal entropy Markov model)或CRFs)序列标注算法和基于分类 3 基于“分歧点”的概率融合 器（如最大熵模型或SVMs)的序列标注算法都是自 然语言处理任务中常用的序列标注方法[78,12,151] 以加法准则为例，常用的分类器融合策略可用下 式表示「（这里仅以等类别先验概率融合为例）： 基于CRFs的序列标注[8]以兼具生成式模型和 R 序列分类器模型的优点著称，可以使用观测序列的 o=arg max∑P(0;|ok) 任何特征并搜索全局最优标注结果.在线性链CRF 式中：0是各分类器中待分类的模式.若K个子分类 模型中，给定观测序列x的最大概率标记序列为 器给出的后验概率的加和最大，则该类别作为最后 y=arg maxpa(J|x)=arg max入∑f(y,x,i). 输出.将加法准则应用到基于分类器的双向序列标 式中：条件概率p(ylx)为全局特征向量∑f(y,x, 注问题，位置i的最佳输出标记为 )的A加权，i表示标注位置.CRFs假设在各个状态 =argmax[P(yl cf)+P(yl c)].(1)
第5期 鉴萍，等：基于双向标注融合的汉语最长短语识别方法 ·409· 式中：c⊙表示某一特定方向的标注器在位置i的分 不能作为正向标注器选择y而不选择的依据.以 析状态，包含取自观测序列的静态特征和取自已标 一对用于短语标注的标记序列为例： 注历史的动态特征，它作为序列分类器的输人；下标 正向：00B I f和b分别表示正向(forwards)和反向(backwards); 和y分别是正向标注器和反向标注器在位置i的 反向：0BII 输出标记类别. i-1 ii+l 当子分类器的个数为2时，上述加法准则可以 其中：“B”(begin)表示一个短语的起始位置，“I” 等价为减法形式.同时我们引入量E来分解原有的 (inside)表示短语内部除起始位置以外的位置，“0” 最大化问题： (outside)表示短语外部.在正向分析中标记为B E(y)=P(I c)-P(I c), 的类别信任度为P(B10)-P(II0)(假设只使用前 E()P(cf)-P(I c). (2) 一个标注结果)：同样在反向分析中标记为I的信任 式中：y和，中使E(y)较大者作为当前位置的输出 度为P(III)-P(B10).显然，概率P(IIO)不具有 标记.实际上，E(y)在这里表达了标记的类别信任 比较意义，因为在该标注体系中串“O”是不合法 度，即分类器有多大把握选择当前输出类别而不是 的，P(II0)接近于0. 其他类别（如另一个分类器给出的候选类别）： 由以上分析可以看出，在基于历史的双向标注 在位置级序列标注融合策略中，每个位置上的 系统中，沿某一方向第一个与另一方向标注结果不 标记是分别计算的： 同的那个位置，才能真实反映该方向整个标记序列 :=arg maxE:(y）, (或一个短语片段)的信任度.将这个位置称作“分 Y=开h 并排列成最后的标记序列.而基于句子和基于短语 歧点”(fork position),并提出了一种基于“分歧点” 的融合试图寻找“一列”最好的标注结果： 的概率融合算法， 5=aU》: 图3为一个双向短语标注示意图，少和分别 此类方法依然使用每个位置的融合结果： 是正向和反向标记序列图中黑色圆表示识别出的 短语起始位置（标记为B的位置）；灰色圆表示识别 (0）=∑4： 出的短语内部（标记为I的位置）；白色圆表示短语 式中： 外部（标记为0的位置）.虚线划出的部分是覆盖某 y:=arg maxe:(y）; 一片段上正反2个方向有效短语标记（即B和I)的 4:= Y=YuTh 最小区域，称之为有效区域，并以此作为融合单位. 0. otherwise. 所以，所要给出的融合算法也是短语级的， 最终结果由候选标记序列（整个句子或一个短语片 x.○-○0○○○○- 段)所含有的在位置级融合中获胜的标记的个数 工4：决定 O+O○O*●0*0O- 但是，上述区域级的融合策略并不适于基于历 史特征的标注模型融合.原因是基于历史的概率模 .-○-○●●●●●*○ 型中某一位置的决策与已标注历史有关，动态特征 ia in 的不一致导致分析状态不一致，相同位置上不同标 图3基于“分歧点”的融合算法示意图 注器输出结果之间是“不公平”竞争.例如，一个错 Fig.3 An illustration of the fork position based algorithm 误的短语识别结果，可能因为后续标记与较早的标 图中和标出的分别是正向标注的分歧点和 记之间具有更小的歧义而获胜. 反向标注的分歧点.整个有效区域内某方向标记序 从另一个角度解释这个问题，把式(2)重写为 列的信任度由该方向分歧点的标记类别信任度来决 E()=P(Ic4,y-)-P(1c4o,-), 定： E()=P(Ico,)-P(lc0,). E(y)=P(l cf)-p(I cfia)), 原标注器分析状态c分解为静态部分c'和动态部分 E(yb)=P(1c6m）-P(y|cm）). y)—2个方向上的已有标注结果(“-”和“+” 因为r和i分别是2个候选序列由左至右和由右至 分别表示i左边和右边的位置).如果y-)与反向 左发生分歧的位置，所以有y）=y-）和y+)= 标记序列中的y-)不一致，概率P(yIc0,y-) y+),分歧点标记的后验概率具有融合意义.上述
·410 智能系统学报 第4卷 融合例子相应地转化为比较P(010)-P(B10) 的距离差作为类别信任度用于融合， (正向，位置i-1)和P(I1I)-P(B1I)(反向， YamCha2]是一个基于SVM分类器的开源序 位置). 列标注工具，因为可以重定义静动态特征并能输出 因为基于历史特征的标注模型对汉语MNP或 类别打分，所以将其作为短语标注器，并使用SVMs PP正反2个方向的识别能力有一定的差异，使用加 的二阶多项式核函数，惩罚参数c设置为0.01. 权融合（权值ω≥0），得到最终的融合算法为 子系统的权值通过在语料库上进行格点搜索 y=arg maxωE(J): （grid search)获得.为简单起见，将反向标注器的权 Y=yKb 值0，固定为1.00，只遍历正向标注器的权值0，搜 4 实验和结果分析 索范围是0.30~2.50，间隔为0.05.所有测试集使 4.1实验设置 用语料库给出的标准分词和POS标注， 实验在宾州中文树库V5.0上进行，使用所有 4.2主要实验结果 《新华日报》语料.该语料分布在698个原始文件 表1和表2分别是上述各系统在9493句语料 中，共9493个句子.本文从中提取出了24436个 上进行十折交叉检验得到的对MNP和PP识别的平 MNP和8282个PP(并列PP如“从…到…”在宾州 均F1值(F1 score).w,固定为1.00时，o:对MNP 中文树库中是以一个最长介词短语出现的，但是考 和PP分别取为0.55和2.00（因为2融合使用的 虑到它表示的是2个相互独立的PP,因此将其看作 是两类别距离差，权值做了相应的映射).融合结果 2个PP).由于对只含有一个词的MNP的识别没有 一栏括号中表示的是融合后F,值与单向结果中较 太大意义，因此本文的实验不包括单个词的MNP; 高值的差 但是单个词的PP多是由于省略了介词中心词，而 表1MNP识别的融合结果(w=0.55)(F,值)】 且数量很少，所以在实验中没有将它们剔除. Table 1 Combining results for MNPs(=0.55)(F score)% 实验使用I0B2标注体系0]，并添加了2个标 融合算法 正向 反向 融合 记符号：“H”和“S”,用来区分短语中心词和非中心 Phrase-based 83.22 85.93 86.09(+0.16) 词.这样，共有5类标记用于最长短语的识别： M1融合 83.22 85.93 86.94(+1.01) “BH”、“BS”、“H”、“S”和“O”. 实验主要比较以下4个标注和融合系统， M2融合 83.1485.86 86.91(+1.05) 1)单向标注：包括对MNP和PP的正向和反向 标注.直接使用序列标注器的输出结果，静态特征窗 表2PP识别的融合结果(w=2.00)(F1值) 口均设为9，动态特征使用五元历史标注结果，即当 Table 2 Combining results for PPs (=2.00)(F score)% 前位置之前的4个历史标记.这一值是根据语料中 融合算法 正向 反向 融合 MNP和PP的平均长度（分别是5.40个词和5.38个 Phrase-based 84.3674.47 84.65(+0.29) 词)选取的， M1融合 84.36 74.47 85.98(+1.62) 2)基于短语的融合算法(phrase-based):实现了 M2融合 83.8474.53 85.51(+1.67) 文献[11]提出的基于短语的融合策略.因为只有2 个候选系统，每个位置上的投票由加法准则代替.当 可以看出，无论是对MNP还是PP,2个方向的 这2个候选序列所含有的在位置级融合中获胜的标 标注结果之间都有明显的差异.MNP的反向标注性 记个数相等时，将退而比较这2个候选序列的各标 能好于正向标注，PP的正向标注性能好于反向标 记后验概率和. 注.相比之下，PP的双向标注结果差别更大，说明介 3)基于“分歧点”的概率融合算法—采用 词对PP的识别具有更强的引导作用.M2融合使用 “one vs..others”多类分类策略(M1融合)：SVM分 “pair-wise”多类分类策略，不同于基于短语的融合 类器使用“one vs.others”模式时，类别打分为该类 和M1融合使用的“one vs..others”策略，所以单向 别到分类面的距离.利用逻辑回归方法，将这些距离 标注结果有细微差别 转化为类别的后验概率用于融合. 比较这3种融合方法，可以发现基于短语的融 4)基于“分歧点”的概率融合算法一采用 合对识别性能有一定的提高，但幅度很小（分别为 “pair-wise”多类分类策略(M2融合)：分类器使用 0.16%和0.29%).本文提出的基于“分歧点”的融 “pair-wise”模式时，分类的依据是两两类别的分类 合算法可以将MNP和PP的识别精度分别提高 情况.本文直接提取2个候选类别在二类分类器中 1.05%和1.67%.M1和M2的融合能力基本相似