基于FMM和CRFs双层分词模型的研究

摘要：中文分词是众多自然语言处理任务的基本工作。该文提出了一个用双层模型进行中文分词的方法。首先在低层利用前向最大匹配算法（FMM）进行粗分词，并将切分结果传至高层；在高层利用CRFs对文本重新进行标注，其中低层的识别结果作为 CRFs 的一项特征。最后将对每个字的标注结果转换为相应的分词结果。跟以前单独利用CRF 进行分词的模型相比，低层模型的加入对CRFs模型的标注起到了重要的辅助作用。在北京大学标注的1998年1月份的人民日报语料上进行了大量的实验，取得了精确率93.31%，召回率92.75%的切分结果，证明该方法是切实可行的。

关键词：前向最大匹配算法；条件随机场；双层模型；召回率

中图分类号：TP391文献标识码：A文章编号：1009-3044(2008)28-0166-03

Research on Two-level Word Segmentation Based on FMM & CRFs

LU Qiang,JIN Wei-zu

(Tongji University,Shanghai 201804,China)

Abstract: Chinese word segmentation is the basic work of the many natural language processing tasks. This paper presents a two-level model of Chinese word segmentation. We first use the Former Max Matching algorithm (FMM) to generate rough segmentation results in the lower level, and send the rough results to the higher level. Then segment the text again based on CRFs, and set the rough results as one feature. Finally convert the label to the corresponding results of segmentation. Compared with the former model based on CRF separately, the cascaded model based on CRFs and FMM is more powerfully. Our approach is evaluated on large-scale corpus with open test method using People's Daily (1998). The results show that this approach based on FMM and CRFs is efficient in word segmentation, and the recalling rate achieves 92.75% and the precision rate achieves 93.31%.

Key words: former max matching algorithm; conditional random fields; two-level model; recalling rate

1 引言

中文分词是中文信息处理的前提，是自然语言处理的一项基础性工作。很多自然语言处理的任务都建立在分词的基础之上，分词的准确程度直接影响到一系列后续处理的正确性，如自动索引、自动分类、信息检索、信息抽取等。但由于汉语自身的复杂性，分词问题一直是中文自然语言处理的难题。

人们已经提出了许多分词方法，根据所使用的知识资源不同分为基于规则的方法，基于统计的方法。基于规则的方法一般都需要事先有人工建立好的分词词典和分词规则库。主要是基于字符串匹配的原理进行分词，如最大匹配算法[1]，这一类的算法复杂度一般比较高，无法有效的解决歧义问题，而且在未登录词比较多的时候，无法达到较好的分词效果。现阶段基于统计的方法已经越来越多的应用到自然语言处理的众多任务之中，主要应用的统计模型有：互信息、N元文法模型、神经网络模型、隐马尔可夫模型（HMM）和最大嫡模型（ME）等[2-4]。隐马模型需要严格的独立性假设，而大多数数据不可能表示成一系列独立的数据；最大熵模型可以容纳较多的上下文信息，但是由于局部归一化而存在着标记偏置的缺陷。

CRFs（Conditional Random Fields）模型 [5] 是当今最先进的序列标注模型之一，它的使用使基于字的分词方法有了更大的提高。Fuchun Peng等人已经做了一系列的实验 [6] ，证明该模型的性能要优于其他的统计模型。但是该模型的标注效果和特征选择是紧密相关的，因此仍有改进的余地。

本文分析了一个双层分词模型，首先在低层利用前向最大匹配算法（FMM）对文本进行粗切分，然后将切分结果传至高层；在高层利用CRFs进行标注，并将低层的结果作为CRFs的特征之一。该特征的加入有效的提高了标注精度，取得了较好的分词效果。

2 CRFs模型

John D.Lafferty等将CRFs（Conditional Random Fields）模型用在序列标注的问题上。其核心思想是利用无向图理论使序列标注的结果达到在整个序列上全局最优。CRFs模型克服了传统的隐马尔可夫模型（Hidden Markov Model, HMM）和最大熵马尔可夫模型（Maximum Entropy Markov Model, MEMM）的标记偏置等问题。

2.1 CRFs模型算法描述

CRF是无向图模型的一种形式，在给定将要标记的观测序列的情况下，无向图模型可以被用来在标记序列上定义一个联合概率分布。假设X，Y分别表示需要标记的观察序列和它对应的标记序列的联合分布随机变量，条件随机场（X,Y）就是一个以观测序列X为全局条件的无向图模型。

通常，我们定义G=(V，E)是一个无向图，Y={Yv/v∈V}。即V中的每个结点对应着一个随机变量所表示的标记序列的成分Yv。因而，整个图和与图相关的分布类别以X为条件，所以与G相关的联合分布的类别的形式是P(y1,…,yn/X)，这里y和X分别是类别序列和观测序列。如果每个随机变量Yv满足关于G的马尔可夫属性，给定X和Yv以外的所有随机变量，则随机变量Yv的概率式如下：

P(Yv/X,Yu,u≠v)=P(Yv/X,Yu,u ~ v)

其中。u ~ v，表示u与v在图G中相邻，那么(X,Y)就是一个条件随机场。

理论上，图G的结构可以是任意的，它描述标记序列中的条件独立性。但在建立模型时，最简单和最普遍的无向图结构是线性链的结构，与Y的元素相对应的结点形成了一个简单的一阶链(First-order Chain)。我们将这种条件随机场称为线性链条件随机场(CRFs)。

在给定观测序列X的情况下，CRFs模型定义标记序列的概率可表示如下：

■

Z是归一化因子：

■

其中每个fk(yi-1,yi,x)是观察序列X中位置为i和i-1的输出节点的特征，每个gk(yi,x)是位置为i的输入节点和输出节点的特征，λ和μ是特征函数的权重。我们分别为训练数据中的每一个状态-状态对(y',y)和状态-观察值对 (y,x) 定义特征如下：

■

■

现在我们用CRF建立了P(Y|X)的统计模型，求解序列标记任务就是求得Y*满足P(Y|X)最大，可表示如下：

■

使用Viterbi等动态优化方法，即可求出最优解Y*。

2.2 标注集的选择

本文将分词任务转换为序列标注任务，首先要定义适合该任务的标注集合，标注集合的选择也直接影响到识别的效果。近几年的基于序列标记的分词系统中，广泛的通过字在词中的位置来定义标注集。最常用的是四字位的标注集；后来又出现了六字位的标注集；详细信息如表1所示。下表给出了这两种标注集的描述；我们通过实验和分析，发现六字位的标注集能取得更好的效果，因此本文采用六字位的标注集。

表1四字位、六字位的详细信息

■

3 基于FMM和CRFs的双层分词模型

模型的识别流程图如图1所示。

3.1 语料的预处理

由于语料中存在大量的数字、符号、时间词即字母等，这些一般都是未登录词，一方面非常容易造成切分错误，另一方面又为切分提供了有用的信息，比如文本中有多个字母连续出现的情况时，即可得到一些潜藏的信息，这些连续的字母可以作为一个词切分出来。因此本文将这些特殊的情况进行特殊处理。

我们将文本中的字分为五大类：1）普通汉字，如“我”“学”等，其类别标为1；2）数字，如0，1，二，三等，其类别标为2；3）符号，包括标点符号和其他的特殊符号，如“&”“￥”等，其类别标为3；4）时间词，如“年”“时”等，其类别标为4；5）字母，如“A”“b”等，其类别标为5。

首先根据上述分类对语料进行标注，使每一个字都属于某一类。

3.2 FMM的粗切分模型

我们首先在模型的低层，采用正向最大匹配算法（FMM）对文本进行粗切分。FMM的具体算法可以描述如下：

设Maxlen表示最大词长D为分词词典。

1) 从待切分语料中按正向取长度为Maxlen的字串str，令Len=Maxlen。

2) 把str与D中的词相匹配。

3) 若匹配成功，则认为该字串为词，指向待切分语料的指针向前移Len个汉字，返回到步骤（1）。

4) 若匹配不成功，如果Len大于1，则把Len减1，从待切分语料中取长度为Len的字串str，返回到（2）。否则，得到长度为1的单字词，指向待切分语料的指针向前移动1个汉字，返回到（1）。

FMM方法原理简单，易于在计算机上实现，时间复杂度也比较低，但是识别精度有限。我们将该粗分结果按照前面标记集的定义转换成六字位的标记形式，以便于应用到高层的分词模型中。

3.3 CRFs的标记模型

CRFs具有很强的推理能力，能够使用复杂的、重叠性的和非独立的特征进行训练和推理，还可以任意地添加其他外部特征，同时解决了最大熵模型中的标记偏置问题和隐马模型的独立性假设，是一个优秀的序列标注器。因此本文在高层采用基于字的CRFs对文本进行重新标注。

采用CRFs进行标注时非常重要的一步是针对特定的任务选择合适的特征集。原则上是选择的特征越多越好，但特征过多又会产生冗余信息，反而降低识别精度。本文选择两类特征：原子特征和复合特征，以下分别做简要介绍。

1）原子特征：为充分利用字的上下文信息、类别等影响分词的因素，可以使用原子特征模板，我们需要从以下几方面考虑：

首先，字本身包含的信息非常的丰富，而且是最容易得到的，因此这是必不可少的一类特征。

其次，通过前面的分析可以知道不同类型的字对切分的指导作用是不同的，因此字的类型也是非常有用的一类特征。

再次，低层的粗切分结果无疑可以带给CRFs更多的上下文信息，这是一类非常重要的特征。

综合上面的考虑，我们选定原子特征如下表2所示：

表2原子特征表

■

其中n为表示位置的变量，取值为-1，0，1。n=0表示当前位置，n=-1表示当前位置的前一位置，n=1表示当前位置的后一位置。

原子特征均用二值函数来表示，当特征函数取特定值时，特征模板被实例化，就可以得到具体的特征。

2）复合特征：由于在真实文本中，影响分词的因素往往不只一类，若只考虑原子特征模板并不能很好的反映实际情况，因而需要同时考察多个因素。对上面表中所示的原子特征模板进行适当的组合，即得到表3所示的复合特征模板。由于复合特征多为原子特征组合而成。因此，通常条件下复合特征比原子特征更为复杂。如果使用复合特征过多还可能导致模型效率下降，通过实验确定复合特征如表3所示：

表3复合特征表

■

在复合特征模板实例化过程中，首先将每个原子特征模板实例化，然后结合当前标注结果来构成复合特征。与原子特征的表示方法类似，复合特征也同样用二值函数来表示。复合特征的加入更好的挖掘了有用的上下文信息，进一步提高了分词的精度。

3.3 后续处理

由于不同的上下文环境会产生不同的识别结果，因此同一个词在不同的环境中可能被切分为不同的结果，导致前后结果不一致的情况发生。我们将置信度大于某阈值的标注结果提取到一个词典中，在最后进行一次二次扫描，，这样可以修正一部分标注结果不一致的情况，在一定程度上提高了识别精度。

4 实验与评估

4.1 评测标准与语料

选取的评价标准如下：

机构名识别精确率：■

机构名识别召回率： ■

机构名识别F值：■

本文选取的语料是北京大学标注的1998年1月份的人民日报。

4.2 实验结果

我们一共设计了三个实验，实验一是只采用CRF进行分词，实验二将FMM与CRF结合进行分词，实验三增加后续处理，实验结果如表4所示：

表4实验结果表

■

通过上面的实验结果可以看出，FMM的加入提高了0.3个百分点，后续处理对结果的影响较小，但也在一定程度上提高了分词精度，达到了相对满意的分词效果。

5 本文总结以及今后工作

本文提出了一个有效的双层分词模型，把FMM与CRFs较好的结合在一起。首先在低层采用FMM进行粗切分，然后将该结果作为CRFs的特征之一，在高层对文本进行重新标注。我们在对CRFs的特征选择上进行了深入的研究，加入了粗分结果和字的类型两类非常有效的特征，提高了标注的精度。最后还进行了一个有效的后处理，解决了部分标注不一致的情况，进一步提高了分词精度，实验证明该方法是有效的。

如果在低层利用双向最大匹配算法，则能进一步提高粗分的精度，这是下一步实验的方向。另外对CRFs的特征选择方面，没有对一些领域知识进行考察，下一步可以从语言学角度进行分析，增加更有效的特征。

参考文献：

[1] 陈力为,袁琦.中文信息处理应用平台工程[M].北京:电子工业出版社,1995.

[2] 李家福,张亚非.基于EM算法的汉语自动分词算法[J].情报学报,2002,21(3):269-272.

[3] 陈桂林,王永成.一种改进的快速分词算法[J].计算机研究与发展,2000,37(4):418-424.

[4] 刘群,张华平,俞鸿魁,等.基于层叠隐马模型的汉语词法分析[J].计算机研究与发展,2004,41(8):1421-1429.

[5] Zhao H, Huang C N, Li M, et al. Effective tag set selection in Chinese word segmentation via conditional random field modeling[A]. In: PACLIC-20[C],Wuhan,China,,2006:87-94.

[6] Peng F C, Feng F F, McCallum A. Chinese segmentation and new word detection using Conditional Random Fields[A].In: COLING 2004 [C], Geneva, Switzerland,2004:562-568.