基于最大间隔马尔可夫网模型的汉语分词方法

李月伦，常宝宝

(北京大学 计算语言学研究所，北京 100871)

1 引言

印欧语系的语言，句子中使用空格将词分开，在中文文本中，句子是一串连续的中文字符。因此，在做汉语自然语言处理中，人们首先要做的工作就是自动分词，在词的边界处做出标记。

长期以来，研究人员一直把未登录词和分词歧义并列为影响分词精度的两大因素[1]。未登录词问题的提出是因为从训练语料中提取出来的词典不可能详尽地列出汉语中的所有词，所以在测试语料中出现但未在词典中出现的词会更难被切分正确。通常，未登录词的召回率是评价一个自动切分性能好坏的重要标志之一。歧义问题出现的原因是汉字可以出现在词的不同位置，比如字符“文”可以作为“日文”一词的词尾，同时也可作为“文章”一词的词首，这样，当切分程序遇到“日文章鱼怎么说”这样一个句子时，必须要判断字符“文”是与字符“日”组成一个词还是与字符“章”组成一个词[2]。

在以往的研究中，研究人员对汉语分词问题提出了很多不同的解决方法，根据这些方法是否使用了词典可将它们分为基于词典的方法与基于字标注的方法。

基于词典的分词方法需要一个提前编制好的词典，将文本中的字符串与词典中的词条进行比较，如果匹配成功，则划分出一个词。在解决未登录词的问题上，基于词典的分词方法需要引入专门的未登录词识别模块。因此，词典构建在很大程度上决定了切分性能的好坏。

基于字标注的分词方法的典型代表是Xue[2]提出的分词方法。该方法对语料库中每个汉字进行标注，根据汉字在词中的不同位置，设置四种标志，分别为LL，RR，MM和LR。如果一个字出现在了一个词的左边界，则这个字被标记为LL；如果一个字出现在了一个词的右边界，则这个字被标记为RR；如果一个字出现在一个词的中间部分，则这个字被标记为MM；如果一个字单独组成了一个词，则这个字被标记为LR。把被标注好的语料以及人工设置的特征模板作为机器学习工具的输入，机器学习的结果将会输出一套特征集，该特征集可对未被标记的文本进行标记，最后用得到的标记对该文本进行切分。鉴于多数汉字都有可能出现在不同词的不同位置上，因此它们都会拥有多于一种的标记，二义性由此产生。为了解决二义性，机器学习的过程应该能根据该汉字的特征以及该汉字所处的上下文特征得出该字的正确标记。与基于词典的分词方法相比，非基于词典的方法不需要预先编译好的词典，但需要大量的被标注好的训练数据，字标注方法近年来得到了较多的采用。

目前常用于分词的机器学习方法有最大熵模型[2]和条件随机场模型[3、4]，尤其是条件随机场模型，由于其考虑到分词问题中的结构依存关系，取得了较好的分词效果。

最大间隔马尔可夫网模型(Max Margin Markov Networks，简称M3N模型),是由B.Taskar等[5]提出的一种新型结构学习的方法，该模型的优势在于用最大间隔的思想训练马尔可夫网络，保持了最大间隔方法的优势，同时又具备处理具有结构的复杂输入的能力。汉语分词问题是典型的序列标注问题，本文将M3N模型用于解决汉语切分问题，考察这一方法在分词问题中的可用性。

本文的组织方式如下：在第2节中，对最大间隔马尔可夫模型进行简单的介绍。第3节是特征的提取方法。在第4节中，详细阐述每组实验的做法，报告结果并做一些相应的分析。

2 最大间隔马尔可夫网模型

与CRF模型类似，最大间隔马尔可夫网模型(M3N)的基础也是无向图(马尔可夫网)模型，与CRF模型不同的是，该方法把马尔可夫网与最大间隔原则联系起来，是对马尔可夫网进行最大间隔训练的一种非概率化模型。

传统无向图模型可以有效地表示出序列标注间的相互关系，但与最大间隔模型相比，推广能力不佳，不支持核函数，因而无法用于高维特征空间。M3N模型将马尔可夫网的学习过程视作寻找最大间隔决策函数的最优化问题，因而将最大间隔模型与无向图模型的优点结合在一起，在改善推广能力的同时也考虑到了序列标注间的相互联系。

在无向图中，我们在每条边上定义基函数(特征函数)f(x,yi,yj)，其中(i,j)∈E，并且假定所有边同质，即每条边都具有相同的基函数。如果每条边都具有n个基函数，那么我们可以定义如下一组特征：

其中，k∈[1,n]。即每个特征是每条边上相应基函数的和。

M3N模型将序列标注问题视为如下的决策问题：

其中，x为观察序列，y为标注序列。

M3N模型的参数为权值向量w，与支持向量机模型类似，需要通过间隔最大化的原则求解这些参数。在M3N模型中，函数间隔定义如下：

Δfx(y)=f(x,t(x))-f(x,y)

其中，t(x)为x的正确标注序列。

M3N模型扩展了传统的0～1损失函数，提出使用逐标记损失函数，逐标记损失函数定义如下：

其中Δtx(yi)定义如下：

Δtx(yi)≡I(yi≠(t(x))i)

即Δtx(yi)是yi的0～1损失。

逐标记损失函数的引入，使得t(x)与y之间的间隔依赖于序列y的损失函数值，更好地照顾到序列标记的结构特性。

按照最大间隔原则，M3N模型参数训练所对应的原始优化问题和对偶优化问题分别如下：

原始优化问题

对偶优化问题

3 文字标注及特征设置

3.1 用不同的标记集对文字进行标注

为了测试标记集对切分性能的影响，我们在实验中采用了下面三种标记集：

(1) S:单字词，B:词的左边界，M:词的中间部分，E:词的右边界

(2) B:词的左边界，I:词的后续部分

(3) I:词的前续部分，E:词的右边界

给定如下一句话：

中国 共产党 成功 地 召开 了 第十五 次 全国 代表大会 ，

用三种标记集标记的结果分别为：

中国 共产党 成功 地 召开 了 第十五 次 全国 代表大会 ，

(1) BE BME BE S BE S BME S BE BMME S

(2) B I B I I B I B B I B B I I B B I B I I I B

(3) I E I I E I E E I E E I I E E I E I I I E E

3.2 特征设置

相关工作表明，使用当前字前后各两个字(即5个字的窗口宽度)的特征是比较理想的[5]。因此，我们的特征模板设置如下：

第一组：基本特征

a.当前字符左邻的第二个字符(C-2)

b.当前字符左邻的第一个字符(C-1)

c.当前字符(C0)

d.当前字符右邻的第一个字符(C1)

e.当前字符右邻的第二个字符(C2)

f.当前字符，当前字符左邻的第一个字符(C-1C0)

g.当前字符，当前字符右邻的第一个字符(C0C1)

h.当前字符左邻的第二个字符，当前字符左邻的第一个字符(C-2C-1)

i.当前字符右邻的第一个字符，当前字符右邻的第二个字符(C1C2)

j.当前字符左邻的第一个字符，当前字符右邻的第一个字符(C-1C1)

第二组：可选特征组一

k.当前字符左邻的第一个字符，当前字符左邻的第一个字符的标记与当前字符(C-1C0T-1)

l.当前字符左邻的第二个字符，当前字符左邻的第一个字符，当前字符，当前字符左邻的第二个字符的标记，当前字符左邻的第一个字符的标记(C-2C-1C0T-2T-1)

第三组：可选特征组二

m.当前字符左邻的第一个字符的标记(T-1)

n.当前字符左邻的第二个字符的标记(T-2)

第四组：可选特征组三

o:当前字符左邻的第二个字符的标记，当前字符左邻的第一个字符的标记(T-2T-1)

从特征模板提供的信息来看，第一组特征为基本特征，为每次实验的必选特征。第二组特征至第四组特征均为可选特征，我们将测试这些可选特征对分词性能的影响。

4 实验

我们选择北京大学计算语言所开发的1998年1月份《人民日报》的部分语料作为训练语料和测试语料，并进行切分实验。该语料共有57万词左右，实验4.5中1∶50的实验所用的训练语料为全部训练语料。语料中包含切分和词性标注信息，均经过人工校对。该语料中包含新闻题材、文学题材等。

我们一共进行了五组实验，分别验证不同的机器学习模型、不同的标记集、不同的特征模板集、不同的训练迭代次数以及训练不同规模的语料对汉语分词效果的影响。

4.1 实验一：用不同的机器学习模型对语料进行训练

在这个实验中，我们分别用最大熵模型，CRF模型和M3N模型对相同的语料进行训练和测试，比较不同机器学习模型在词语切分性能方面的差异。

(1) 语料设置

考虑到训练效率的问题，我们选择了20万词左右的语料作为训练语料。为了保证训练语料与测试语料划分的合理性，我们把全部语料中的句子以每100句为单位划分，其中第一句用来做测试语料，第2至21句用来做训练语料。得出的训练语料共有22.5万词，测试语料1.1万词左右。在测试语料中，共有未登录词568个，占测试语料的5%。

(2) 特征模板设置

此次实验共用到13个特征模板，如3.2节中模板a～m所示。

(3) 标记集设置

使用3.1节中第(1)组标记集合，即4个切分标记。

(4) 实验结果(表1)

表1 使用不同机器学习模型得到的分词结果

从结果中可以看出，结构化模型要明显好于非结构化模型，因为结构化模型考虑了句子内部标记之间的相关性。最大熵模型因为没有考虑到这一点，因而产生了“标记偏见”问题[3]，因此切分精度较低。

从CRF和M3N得出的结果中可以看出，M3N得到的F值比CRF高1%，但在OOV_recall方面却有下降。总的来说，将M3N模型运用到汉语分词中取得了不错的效果，基于M3N模型的性能略优于CRF模型。

为了更直观地比较M3N模型与CRF模型性能上的差异，我们随机选择了一些被M3N模型切分正确但被CRF模型切分错误的语句进行对比(错误切分指的是与人工标注的标准答案不一致)。基于是否属于未登录词，可将它们分为已登录词(IV)和未登录词(OOV)两组，分别如表2及表3所示。

表2显示，针对已登录词，M3N表现出了较好的切分歧义消解能力。在未登录词识别方面，虽然实验结果表明M3N模型得到的未登录词召回率略低于CRF模型，但通过随机抽取的一些错误样例(如表3所示)可以发现，M3N模型对长词的捆绑能力似乎优于CRF模型，M3N模型似乎可以更好地利用上下文语境信息。

当然，在实验结果中，也存在被CRF模型正确处理，但被M3N模型错误处理的句子，表4列出了一些这样的切分实例。

表2 M3N模型与CRF模型切分结果的对比1(已登录词)

表3 M3N模型与CRF模型切分结果的对比2(未登录词)

表4 M3N模型与CRF模型切分结果的对比3

4.2 实验二：用不同的标记集对语料进行训练

在这个实验中，我们用到的训练语料、测试语料以及特征模板与实验一相同，基于M3N模型进行训练和测试。

我们用三种不同的标记集对训练语料进行标记，如3.1节所示。

实验结果如表5所示。

表5 使用不同标记集合得到的分词结果

从实验结果可以看出，三个实验的结果依次递减，说明SBME标记集使分词结果达到最好。IE标记集得到的OOV_recall也较低。

4.3 实验三：用不同的特征模板集对语料进行训练

在这个实验中，我们用到的语料与实验一相同，使用四个标记的标记集(SBME标记)，基于M3N模型进行训练和测试。

我们需要用到的15个特征模板如3.2节中a～o所示。

4.3.1 特征模板选择原则

在3.2节中已经提到，第一组特征模板为基本特征，在训练过程中必不可少，第二组特征至第四组特征可以起到相似的作用，均是要得到当前字符之前字符的标记信息。但第二组特征与第三、四组特征的区别在于第二组特征中包含了当前字以及左邻第一、第二个字的信息。

我们要对上述特征模板集中那些效果相似的模板进行排列组合，与必须包括的模板a～j合并构成若干个特征模板集，找出效果最好的特征模板集合，并对其中的模板进行一些分析。

具体而言，在每次实验中，我们都必须要得到当前字符左邻第一个字以及第二个字的标注信息，要得到该信息可以对特征模板k～o进行如下组合：

4.3.2 实验结果

我们一共进行了12组实验，实验所用的模板以及实验结果如表6所示。

表6 使用不同特征模板集合得到的分词结果

从实验结果可以看出，用第(8)组模板得到了最高的F值。

通过不同实验之间的对比，可以大致总结出如下结论：

(1) 11_1与11_2，12_1与12_2比较均表明：特征模板m，o似比特征模板k，l更加有效。尤其在OOV_recall方面，特征模板l，k对召回率影响较大。因为特征模板l需要知道该字符左邻字符的信息，因此该特征具有稀疏性，而特征模板o只需知道该字符左邻字符的标记，不具有稀疏性。

(2) 11_1与12_2比较表明：特征模板l易造成OOV_recall降低，因为对于未登录词来说，提供更多的字符标记信息比提供字符信息更加有用。

(3) 11_2与12_1比较表明：特征模板o与特征模板m，n相比，前者对f值有贡献，后者对OOV_recall有贡献。

(4) 13_2与14_1比较表明：f值越高并不意味OOV_recall也越高。

(5) 整体来说，在特征模板给定合理的情况下，特征模板的数量越多，训练效果越好。

(6) 每个特征模板都有存在的必要，缺少一个都会使F值下降。

(7) 特征模板o对OOV_recall的贡献比较大。

4.4 实验四：用不同的迭代次数对语料进行训练

在这个实验中，我们用到的语料与实验一相同，使用四个标记的标记集(SBME标记)，在M3N工具上进行训练和测试，使用3.2节中的特征模板 a～m(即可以使F值达到最大的特征模板集)。通过进行不同迭代次数的实验，检验其对分词结果的影响。得到的实验结果如表7所示：

表7 使用不同迭代次数得到的分词结果

为了更直观地对实验结果进行分析，得到该结果的线状图如图1所示。

图1 不同迭代次数与分词精度的关系

从图中可以看出，F值并没有随着迭代次数的增加而增加，其中F值在21次迭代处达到最大值，对应表4可以看出，OOV_recall在15和21次迭代处达到最大值，说明OOV_recall不会随F值的增大而增大。

此外，随着迭代次数的不断增加，训练时间增加的幅度也比较大，但时间的代价并没有得到效果的提升。

4.5 实验五：用不同规模的语料进行训练

在这个实验中，我们使用四个标记的标记集(SBME标记)，使用3.2节中的特征模板a～m，在M3N工具上进行训练和测试。保持测试语料规模不变，每次增加5%的训练语料(在最后一组实验(1∶50)中，我们增加了20%的实验数据)。

得到的训练语料与测试语料的相关信息如表8所示：

表8 测试语料与不同规模训练语料的相关结果

实验结果如表9所示：

表9 使用不同训练语料规模得到的分词结果

在实验1∶50中，F值达到了0.992 851，这是因为在该实验中，OOV_rate非常小，只有0.000 126(71个词)。

为了更直观地对实验结果进行分析，得到该结果的线状图如图2所示。

图2 不同规模训练语料与分词精度的关系

从图中可以看出，当训练数据集合较小时，F值较低(实验1∶5)。F值大体上随着训练语料规模的增大而增大，但实验 1∶15 得出的结果比实验 1∶20 得到的结果略高。

从表9中可以看出，OOV_recall在整个实验中变化幅度不大。

该实验同时说明，字符标注的方法比较好地解决了未登录词的识别问题，且解决能力在训练集较小时也很有效。这是因为字标注的过程能够平衡地看待词表词和未登录词的识别问题[1]。

根据实验的结果，我们也可以看出未登录词识别问题仍然是困扰汉语切分问题的瓶颈。随着训练语料规模的逐步增大，切分精度稳步上升，但未登录词召回率却一直维持在70%的水平。分词精度之所以提升，是因为测试语料中未登录词的数量越来越少。在实际应用中，未登录词的数量往往是不可控制的，需要切分的实际语料规模常常会多于切分系统的训练语料，因此如何加强未登录词的处理能力就值得认真考虑。为此，我们的初步考虑如下：一是引入专门的未登录词处理识别预处理模块，并将识别结果以特征函数形式纳入基于M3N模型的分词程序；二是探索半指导的学习技术，使得在面向特定的切分任务时，能以补充任务中语料的方式增加切分系统的适应性。

5 结束语

最大间隔马尔可夫网模型是一种将最大间隔原则与无向图模型结合所提出的一种结构学习模型，理论上该模型具有较好的推广能力，本文将该模型用于汉语分词任务并进行了相关实验验证，总体来看，基于最大间隔马尔可夫网模型的分词性能较好，与基于CRF模型的分词系统性能具有可比性，甚至略为领先。

不过，与CRF模型类似，M3N模型训练的时间代价也是相当大的，训练算法的优化应是结构化学习模型需要关心的问题。此外，M3N模型支持核函数，我们也将在未来的工作中考察核函数的引入是否会引起分词性能的改善。

[1] 黄昌宁，赵海. 中文分词十年回顾[J]. 中文信息学报，2007，21(3)：8-19.

[2] N. Xue. Chinese Word Segmentation as Character Tagging[J]. Computational Linguistics and Chinese Language Processing, 2003, 8(1), 29-48.

[3] 李双龙，刘群，王成耀. 基于条件随机场的汉语分词系统[J]. 微计算机信息，2006，22，(10-1): 178-200.

[4] 迟程英，于长远，战学刚. 基于条件随机场的中文分词方法[J]. 情报杂志，2008，(5)：79-81.

[5] Ben Taskar, Carlos Guestrin，Daphne Koller. Max-Margin Markov Networks[C]//Proceedings of Neural Information Processing Systems Conference(NIPS), 2003.

[6] Huang Chu-Ren, Yo Ting-Shuo, Petr Simon and Hsieh Shu-Kai. A Realistic and Robust Model for Chinese Word Segmentation[C]//Proceedings of the 20th Conference on Computational Linguistics and Speech Processing(ROCLING), 2008.

[7] 孙茂松，肖明，邹嘉彦. 基于无指导学习策略的无词表条件下的汉语自动分词[J]. 计算机学报，2004,27(6):736-742.