基于词边界分类的中文分词方法

2010-06-05李寿山黄居仁

中文信息学报 2010年1期

李寿山，黄居仁

(香港理工大学中文及双语学系，香港)

1 引言

自动分词是中文计算机处理中的一个基本任务[1]。该技术是实现众多中文应用系统的前期基础，例如：中英(英中)机器翻译、信息检索、文本自动分类等。由于中文词边界本身的歧义性，加上大量新词的不断涌现，中文自动分词一直是中文信息处理中的一个长期且艰巨的任务。针对该任务，中文信息处理研究领域先后出现了大量的自动分词方法。

长期以来，分词的方法都是基于词(或词典)的[2]。例如基于规则的最大匹配方法[3]或者基于统计的词的N元语法方法[4]。在大规模词典的帮助下，基于词的分词方法取得了比较好的效果。但是该方法在识别未登录词(OOV)时，结果并不理想，然而未登录词的识别在分词系统的应用中是不可避免的问题。近几年来，基于字的分词方法渐渐得到相当的关注，在这几次的Sighan评测中占主导地位。该方法将分词问题转化为字的分类问题，即判断文本的字是否为某词的开始或者结束[5]。相对于基于词的分词方法，基于字的分词方法的最大优点就是能够取得令人满意的OOV识别率。尽管如此，由于基于字的分词方法需要构建高维的向量空间，而且分类的样本非常庞大，这使得该方法训练和测试的时间复杂度和空间复杂度都非常高。因此，该方法还不能满足一些真正实用的实时分词系统。我们认为一个优秀的实时分词系统不仅仅需要快速对新样本进行分词，还需要能够迅速学习新的标注样本(该特性我们称之为在线学习能力[6])。而目前基于字的分词方法训练需要时间太长，很难满足以上的要求。

文献[7]首先提出一种基于词边界分类的分词方法(Word Boundary Decision，以下简称该方法为WBD)。该方法直接对分词的任务建模，判断字同字之间的边界是否为词的边界。换言之，该方法视分词为一个两类分类问题。相对于一般的基于字的分类方法，类别的数目有所减少，从而降低了分类的复杂度。本文将介绍该分词方法并进一步完善该方法，使得它能够获得接近目前主流方法的分词效果。在此基础上，我们将提出一种基于WBD的在线学习分词方法，能够快速学习新标注样本。鉴于WBD方法的时间复杂度和空间复杂度远远小于基于字的分词方法，我们能够利用它构建一个更实用的分词系统。

本文其他部分安排如下：第2部分详细介绍基于词边界分类的分词方法并提出我们的一些改进；第3部分提出基于WBD的在线学习分词方法；第4部分给出实验结果及分析；第5部分给出相关结论。

2 基于词边界分类的分词方法(WBD)

2.1 WBD方法

自动分词的基本任务是将一段由字串组成的文本切割成由词组成的词序列。举例来说，一段分词前的字序列为“共同创造美好的新世纪”，而分词后的词序列为：“共同创造美好的新世纪”。这样做是便于计算机识别和处理比较完整的一些语义单位，如“创造”、“美好”等，从而有利于进一步的文本处理，如自动翻译、信息检索等。

WBD方法的目标是判断每两个字之间的边界是否为词边界。我们形式化表示一段文本为：

c1I1c2I2,...,ciIi,...,cn-1In-1cn

其中ci表示一个中文字符，Ii表示任意两个字之间的字边界。在原始的中文文本中，这些字边界没有明显的显示出是否为词边界。我们设定如果该字边界为词边界，则记为Ii=1，否则Ii=0。WBD的方法就是直接判断某个字边界是否为词边界。因此，在WBD中，分词任务被转化为一个两类分类问题。然而在基于字的分词方法中，一般会把字的类别数目定义为“开始”、 “中间” 、“结束”和“单字”。在类别数目上面来说，WBD方法要比基于字的分词方法更简单。

WBD方法大致分为两个步骤：N-gram概率信息统计和边界的向量表示。下面分别介绍这两个步骤。

在第一个步骤中，该方法通过收集训练样本中的词边界信息，即N-gram字串关于词边界的统计信息。文献[7]中给出了5种不同的unigram和bigram特征的统计信息，它们分别为PCB、PBC、PCCB、PCBC和PBCC。这些统计信息具体是指N-gram字串相对于词边界的出现概率。其中PCB定义如下：

其中C(ci,Ii=1) 表示在训练语料中字符ci出现在词边界前面的次数。而C(ci)表示字符ci在训练语料中出现的总次数。

另外，PCCB的定义如下：

其中C(ci-1,ci,Ii=1)表示在训练语料中二元字符串ci-1,ci出现在词边界前面的次数。而C(ci-1,ci)是二元字符串ci-1,ci在训练语料中出现的总次数。

其他三个概率信息,PBC(Ii=1|ci+1)，PCBC(Ii=1|ci,ci+1)和PBCC(Ii=1|ci-2,ci-1) 具有类似的定义。为了简单起见，下面我们分别用PCCB(Ii),PCBC(Ii),PBCC(Ii),PCB(Ii),PBC(Ii)表示这5个概率信息统计量。一旦获得了所有N-gram字符串的概率信息，我们将这些数据保存在一个字典中，供以后构建向量使用。我们命名这个包含统计信息的字典为“N-gram数据源”。

在第二个步骤中，WBD方法将所有的字边界表示为下面的向量：

WBD的训练过程和测试过程都会将所有字边界表示为这种向量。剩下的就是一个典型的模式分类问题。我们可以采用各种不同的统计分类方法去训练和测试。由于该向量的维度很低，仅仅需要几千个样本就足够训练出一个比较好的分类器[8]。这一点与基于字的分词方法不同，基于字的分词方法需要训练大量的样本向量。因此，WBD方法大大降低了训练时间。为了更清晰的了解WBD方法，我们给出文本“共I1同I2创I3造I4美I5好”中每个字边界的向量实例，如表1所示。其中，在N-gram数据源中未出现的字串概率一律赋值为0.50。

表1 一段字串的字边界向量实例

2.2 WBD方法的进一步完善

在已有的WBD方法的框架基础上，我们提出一系列进一步完善的措施，包括概率估计的平滑、新N-gram的引入和数字英文字符的预处理。

在估计概率的时候，往往会出现某些字符在语料中出现次数很少的情况，利用上面的统计公式统计概率会带来很大的误差。为了减小这些误差给分类带来的影响，我们尽量使频率出现很少的概率趋向于0.5。以PCB为例，我们改写概率估计函数如下：

另外，上面介绍的WBD方法仅仅考虑到了unigram和bigram字符串的统计信息。在实际分词任务中，为了捕捉更远的分词信息，从而更好地识别多字符的词，我们引入trigram字符串的统计信息。trigram字符串包括CCCB、CCBC、CBCC和BCCC，对应的概率值分别为PCCCB(Ii)、PCCBC(Ii)、PCBCC(Ii)和PBCCC(Ii)。我们将在实验部分测试这些新特征对分词效果的影响。

为了进一步提高WBD方法的分词效果，我们在进行统计N-gram字符串概率之前利用正则表达式进行所有数字和英文字符的识别和替换。

3 基于WBD方法的在线学习分词方法

优秀的实时分词系统不仅仅需要快速对新样本进行分词，还需要能够迅速学习新的标注样本，只有这样，才能让系统能够快速引入不断涌现的新词。换言之，系统应该具备在线学习的能力。在线学习(Online Learning)是指系统在输入新的标注样本后，不需要重新学习原始的训练样本，只是针对新来的标注样本学习就可以了。目前，在线学习本身作为机器学习的一个重要的研究问题，备受模式识别，机器学习，自然语言处理等学术届的重视。

需要强调的是WBD方法的核心部分是N-gram数据源，如果加入新的标注样本，只需要更新N-gram数据源，就相当于更新了训练数据。以其中一个概率PCCB(Ii)为例，更新的概率公式如下：

其中C(ci-1,ci,Ii=1)和C(ci-1,ci)是N-gram数据源里面字符串ci-1ci的词频信息。这些数据都是已经有的，不需要重新学习。Cnew(ci-1,ci,Ii=1)和Cnew(ci-1,ci)则是新标注样本里面字串ci-1ci的统计信息。Cnew(ci-1,ci,I=1)表示在新训练语料中二元字符串ci-1,ci出现在词边界前面的次数，而Cnew(ci-1,ci) 是二元字符串ci-1,ci在新训练语料中出现的总次数。其他几种N-gram的更新公式同上式类似。在实际应用中，如果待测样本和新标注样本比较接近的话，可以通过提高新样本里面统计词频的权重来加重新标注样本对后期分词的影响。

除了更新N-gram数据源之外，训练阶段不需要任何其他的操作。因此，基于WBD的在线学习方法，需要再学习的代价非常小，可以满足实时系统中的分词需要。

4 实验

在本实验中，我们将首先详细给出WBD的分词效果，其次，我们将测试上面提出的基于WBD的在线学习方法。

我们使用第二届国际分词竞赛(Bakeoff-2005)中的四组语料对WBD分词方法进行测试。每组语料中的训练语料用于生成各自的N-gram数据源，并随机生成训练样本中的1 000个字边界的向量训练一个SVM(Support Vector Machine)分类器。在测试过程中，测试语料中的所有字边界由该组的N-gram数据源生成向量。然后用训练好的SVM分类器进行测试。

我们使用基于词的F值作为评估标准，它是准确率P和召回率R的调和平均值：F=2RP/(R+P)。为了和相关工作比较，我们也列出了未登录词的召回率(OOV recall)。表2～表5分别给出了WBD方法及其一些改进方法在四组测试语料上面的分词结果。其中，基准的实现过程完全按照文献[7]里面的描述，只用了5个N-gram的字符串特征。

表2 WBD及其改进方法在Pku语料测试语料上的结果

表3 WBD及其改进方法在Cityu语料测试语料上的结果

表4 WBD及其改进方法在Msr语料测试语料上的结果

表5 WBD及其改进方法在As语料测试语料上的结果

在改进的方法中，我们只报告了CCBC和CBCC的结果，这是因为CCCB和BCCC字串的加入对结果基本没有影响。从这些表中可以看出，平滑在两个语料上都有较好的表现，在另外两个语料中基本保持原来的分词效果。其他两个改进在所有的语料中都有不同程度的提高。

为了便于比较WBD同基于字的分词方法，我们利用Porket CRF[9]工具实现了基于字的分词方法，实验使用了字符的四种标识类别[10]。表6中给出该方法在Pku和Msr两个语料上面的封闭测试结果(没有用到数字英文字符识别)。相对于CRF实现的基于字的分词方法，虽然WBD的分词效果要稍微差一点，但是WBD所需要的训练时间(包括N-gram字符串概率的搜集和SVM分类器的训练)要远远小于CRF的训练时间(我们用python实现的WBD方法)。

在实际分词系统的应用中，训练样本和测试样本并不能像分词竞赛那样限制为来自相同来源。为了模拟实际分词无法预知测试语料来源的状况，我们交换了Pku和Msr的测试语料。也就是说，我们让CRF和WBD在Pku的训练语料上面训练，但是在Msr的测试语料上面测试，这样分词的F值结果会大大减低到0.856和0.850(Pku→Msr)。在这个时候，CRF和WBD方法的差异已经小到没有统计上的相关性了。

表6 WBD与CRF实现的基于字标注的分词方法的比较结果

最后，我们利用WBD方法构建一个真正实用的分词系统，该系统使用Sinica研究院平衡语料产生N-gram数据源。该语料是来自中国台湾研究员的繁体语料，由于Sinica语料在各个领域的分布比较均匀，我们认为该语料库能够比较好的反映各种字符串同词边界的关系[11]。为了测试我们系统的效果以及上面提到的基于WBD的在线学习方法，我们使用部分Cityu的训练样本用作我们系统新的标注样本。图1给出了我们系统在Cityu测试语料上面的F值结果，横坐标表示加入新样本的规模。从图中可以看出，在不使用任何Cityu训练样本的情况下，我们的系统已经取得了近88%的F值。如果利用我们的在线学习方法，渐渐融入少量Cityu的训练样本，系统的表现会越来越好。

图1 系统在Cityu测试语料上面的F值

图2 系统在Cityu测试语料上面的OOV Recall值

图2给出系统在引入新语料后的OOV Recall值的变化曲线。从该图可以看出，系统性能提高的一个重要原因就是新的语料给系统带来了许多新词，例如：“海陆空”、“社工”等词，使得系统能够更好的分好这些新词。通过对比在线学习前后的分词结果，我们还发现另外一个提高系统性能的重要原因：Cityu测试语料和Sinica语料的分词标准在某些词方面不一致，而加入Cityu的少量训练语料，能够有效的校正不同的分词标准。例如：在Sinica训练语料里面，“有些”被认为是两个词，而在Cityu里面“有些”被认为是一个词。另一个出现比较多的例子是，在Sinica训练语料里面，“x月x日”分词为“x月 x 日”(其中“x”代表数字，“x”和“日”是分开的)，而在Cityu里面被分为“x月 x日”(“x”和“日”是不分开的)。

5 结论

本文研究了一种基于词边界分类的分词方法并提出改进方法。在此基础上，我们实现了一种在线学习的分词方法。实验结果表明，这种新的分词方法能够获得接近目前主流方法的分词效果，但只需要很少的训练时间。同时，我们利用提出的在线学习分词方法和Sinica研究院平衡语料库构建了我们的分词系统，该系统能够在来自不同地方的语料中获得比较满意的分词效果，并且能够很迅速地学习新的样本，使我们的系统具备很好的更新能力。

[1] 黄昌宁. 中文信息处理的分词问题[J]. 语言文字应用, 1997, 11(1):72-78.

[2] 黄昌宁, 赵海. 中文分词十年回顾[J]. 中文信息学报, 2007, 21(3):8-20.

[3] 骆正清, 陈增武, 胡上序. 一种改进的MM分词方法的算法设计[J]. 中文信息学报, 1996，10(3): 30-36.

[4] 吴春颖, 王士同. 基于二元语法的N-最大概率中文粗分模型[J]. 计算机应用, 2007, 27(12): 332-339.

[5] Xue N. and L. Shen. Chinese word segmentation as LMR tagging[C]//Proceedings of the Second SIGHAN Workshop on Chinese Language Processing. 2003.

[6] Crammer K., O. Dekel, J. Keshet, S. Shalev-Shwartz, and Y. Singer. 2006. Online passive-aggressive algorithms[J]. Journal of Machine Learning Research, 2006(7): 551-585.