基于序列标注的全词消歧方法

周 云，王 挺，易绵竹，张禄彭，王之元,4

(1. 国防科技大学 计算机学院，湖南 长沙 410073； 2. 解放军外国语学院 国防语言文化研究所，河南 洛阳 471003；3. 解放军外国语学院 欧亚语系，河南 洛阳 471003； 4. 国防科技大学 并行与分布处理国家重点实验室，湖南 长沙 410073)

1 引言

词义消歧，即在特定的上下文中确定歧义词的词义。根据词义消歧的范围，可将其分为词样消歧(Lexical-Sample WSD)和全词消歧(All-Words WSD)。词样消歧对给定文本中的某些指定词进行消歧，而全词消歧对给定文本中的所有开放词(包括名词、动词、形容词和副词)进行消歧。词样消歧是一个典型的分类问题，可使用各种成熟的有监督分类算法，如朴素贝叶斯[1]、最大熵算法[2]和支持向量机[3]等。对于全词消歧，目前通常的做法是将其当作词样消歧，对句中出现的每个开放词逐个进行消歧，各个词之间的消歧是独立的。但是，全词消歧中前后两个词的消歧实际上是相互关联的，全词消歧可以看作一个序列标注问题。

序列标注指的是对观察值序列的每个成员指定一个类别标签，因此序列标注可视为一系列的分类任务。由于序列标注利用相邻元素的依赖性对整个序列进行全局优化，一次性为所有观察值给出标签，因而标注性能通常会得到提升。常用的序列标注算法有隐马尔可夫模型(Hidden Markov Model, HMM)[4]、最大熵马尔可夫模型(Maximum Entropy Markov Model, MEMM)[5]和条件随机域[6]等。虽然HMM等序列标注方法在一些自然语言处理任务中取得了突出的成绩，如词性标注[7]和语音识别[8]等，但在词义消歧中的结果却并不理想[9-13]。这可能是由于:第一，HMM的观察值只能是词形，难以有效利用各类语言学特征；第二，全词消歧是一个超大状态问题，序列标注方法存在严重的数据稀疏问题，并且具有很高的时间复杂度。

针对上述问题，本文提出两种基于序列标注的全词消歧方法，主要贡献如下:(1)提出了一种基于HMM的全词消歧方法；(2)将基于HMM的方法推广为基于MEMM的全词消歧方法，将观察值由词形扩展为特征向量，引入了大量的语言学特征；(3)通过柱状搜索和平滑策略解决上述模型中存在的数据稀疏问题，在解决数据稀疏问题的同时，柱状搜索还显著降低了解码的时间复杂度；(4)在Senseval数据集上对序列标注方法进行了系统的评测。

本文结构安排如下。第二节，我们给出一种基于HMM的全词消歧方法。第三节，我们将模型推广为MEMM模型，将观察值扩展为若干特征构成的向量，这些特征包括邻近词词性、局部搭配关系、依存句法关系、WordNet上位词链、WordNet语义标签、WordNet动词框架和词袋等。针对序列标注方法存在的数据稀疏和很高的时间复杂度等问题，在第四节我们设计了平滑策略和柱状搜索Viterbi算法加以解决。第五节，我们在Senseval-2和Senseval-3上对HMM和MEMM方法进行了评测，并与以往的序列标注方法的性能进行了对比。第六节，我们总结全文并讨论下一步工作。

2 基于HMM的全词消歧方法

HMM是一个经典的数学模型[4]，它一般用以解决评估、序列标注(也称为解码)和学习等三个问题，这三个问题分别可用前向算法(或后向算法)、Viterbi算法和前向—后向算法解决。在本文中我们主要关心序列标注问题和Viterbi算法。

HMM包含两个随机过程Qt,Qt,1≤t≤T，和五个模型参数S,V,A,B,π除特殊说明外，本文均沿用文献[4]中的符号)。其中，(1)S={s1,s2,…,sN}为状态集合；(2)V={v1,v2,…,vM}为观察值集合；(3)A={aij},aij=P(Qt+1=sj|Qt=st),1≤1,j≤N为状态转移概率矩阵；(4)B={bj(k)},bj(k)=P(Qt=vk|Qt=sj),1≤j≤N,1≤k≤M为状态—观察值发射概率矩阵；(5)π={πi},πi=P(Q1=si),1≤i≤N为状态初始分布概率向量。

(1)

这个问题可通过称为Viterbi算法的动态规划方法加以解决，其时间复杂度为O(TN2)。

基于HMM的全词消歧模型需要选择合适的状态集合S和观察值集合V。状态集合S的选择有多种，我们直接取训练集中出现过的synset作为状态集S的一部分。由于封闭词的个数是有限的，我们令每个封闭词为一个状态。另外，对于某些特殊的词类(子类)，我们认为它们的成员对于词义消歧而言是等价的，因而将它们整体作为一个状态，这有利于缓解数据的稀疏性，这包括人名、地名、组织名、其他专有名词、序数词、属格代词、联结词和情态动词。观察值集合V的选择也有多种，我们以词条(lemma)和词性的字符串连接作为观察值。可用作观察值的有:词、词条、词与词性的字符串连接或词条与词性的字符串连接等。文献[13]的实验结果表明，词与词性的字符串连接作为输入效果较好，我们沿用这一作法。A,B,π均由训练集作最大似然估计得到。

3 基于MEMM模型的全词消歧方法

McCallum等人在文献[5]中将HMM改造为MEMM，其不同之处在于:(1)观察值的扩充。HMM的观察值集合一般只能为一个有限的词表；而MEMM对原始观察值抽取若干个非独立特征，构成特征向量，然后根据特征向量计算给定观察序列的状态序列的条件概率； (2)由生成模型到条件模型。在HMM中，当前状态仅依赖于前一状态(马尔可夫性)；在MEMM中，当前状态不仅依赖于前一状态，还依赖于当前特征向量。

在MEMM中，状态转移概率和状态—观察值发射概率被一个统一的新的概率Pqt-1(Qt-qt+Ot=ot)=P(Qt=qt|Ot=ot,Qt-1=qt-1)所代替，即在前一状态为qt-1且当前特征向量为ot时，当前状态为qt的概率。Pqt-1(Qt=qt|Ot=ot)可用某些带概率输出的机器学习算法进行训练得到，如最大熵算法、朴素贝叶斯算法和支持向量机等。最早提出该模型的文献[5]采用了最大熵算法，MEMM模型因此得名。

MEMM模型的要素为S,V,M,π。其中，(1)S={s1,s2,…,sN}为状态集合；(2)V={v1,v2,…}为由观察值抽取的特征向量构成的集合；(3)M={Pqt-1(Q1=qt|Ot=ot},qt∈S,ot∈V},qt-1∈S为概率模型集合；(4)π={PBegin(Q1=q1|O1=o1),q1∈S,o1∈V}为初始概率模型。在MEMM中，序列标注问题为也可通过Viterbi算法加以解决，它与HMM的Viterbi算法是十分类似的。

在基于MEMM的全词消歧模型中，状态集合S与HMM的状态集合S相同。特征向量集合V中的元素为由原始观察值抽取的特征向量构成的集合。我们以文献[2，14]中的特征为基础，设计了以下七类特征:(1)邻近词的词性；(2)局部词形搭配关系；(3)依存句法关系；(4)特定范围内的WordNet上位词(hypernym)链；(5)特定范围内的WordNet语义标签；(6)特征范围内的WordNet动词框架；(7)句中的各个单词构成的词袋。上述特征的详细解释及例子见附录A。对于每一个概率模型Pqt-1(Qt=qt|Ot=ot)，我们通过将训练集中紧接在qt-1后面的所有状态-特征向量对(qt,ot)收集起来，然后用最大熵算法进行训练，就得到了模型Pqt-1(Qt=qt|Ot=ot)。对于初始概率模型PBegin(Q1=q1|O1=o1)，我们则收集句首的状态—特征向量对即可。

4 实现

如前所述，序列标注一般通过Viterbi算法解决。全词消歧作为一个超大状态问题，上述两个模型均存在严重的数据稀疏问题，同时还具有过高的时间复杂度。下面提出的柱状搜索Viterbi算法和平滑策略，解决了数据稀疏的问题。另外，柱状搜索在解决数据稀疏问题的同时，还显著地降低了解码的时间复杂度。

4.1 柱状搜索

在全词消歧的HMM模型中，发射概率矩阵是十分稀疏的。状态空间S的非常大，包括训练集中出现过的synset及封闭词等，其规模约为数万。然而，一个观察值ot(lemma)对应的状态数(synset数)却是十分有限的，至多为数十个。为解决这个问题，我们采用柱状搜索Viterbi算法进行解码。我们将观察值ot对应的状态集合记为stateSet(ot)，在Viterbi算法迭代的每一步，只搜索stateSet(ot)，而不是整个状态空间，即

这不仅有效地解决了发射概率矩阵稀疏问题，还显著地降低了解码的时间复杂度。通常，Viterbi算法的时间复杂度为O(TN2)，其中，T为待消歧句子的长度，N为状态空间S的大小。在HMM方法中，由于N的值非常大，该算法的实际运行时间是难以承受的。使用柱状搜索后，Viterbi算法的时间复杂度由O(TN2)降为其中Smax为一个lemma最多可能对应的synset数。MEMM的柱状解码与此十分类似，本文从略。

4.2 平滑策略

在全词消歧的HMM模型中，转移概率矩阵也是稀疏的。Viterbi算法计算概率的乘积，若转移概率为0，则乘积结果为0，无法比较结果的大小。为了避免整个乘积的结果为0，我们必须采用某种平滑策略。在HMM中，转移概率矩阵A中元素aij的极大似然估计为其中C(sisj)表示在训练集中sisj出现的次数。我们令aij平滑后的值为：

其中，I(·)为指示函数，表示观察值v(lemma)对应的状态(synset)数，F(sj)表示sj对应的synset在WordNet中出现的频数。上述公式的直观含义是，我们假设si的转移概率中有1-γ出现在训练集中，有γ未出现在训练集中；对于未出现在训练集中的sj，若sj∈Synsets(v)，我们令其概率与其对应的synset在WordNet中出现的频数F(sj)成正比；对于所有未出现在训练集中的sj，若sj∉Synsents(v)，我们令其概率均相等。在我们的实验中，γ=0.999。

对于MEMM模型,我们令Psi(sj|v)平滑后的值为：

式(3)的直观含义与式(2)类似。

5 实验

在Senseval/Semeval出现之前，曾有少数学者尝试用HMM等序列标注方法进行全词消歧，如Segond等人[9]采用HMM进行全词标注，其标记为WordNet的45个语义标签；Loupy等人[10]采用一种集成了语义标签和词义的混合HMM进行全词标注。但由于上述研究并未使用通用测试集，其结果并不具有可比性。

Senseval/Semeval(2007年之前称为Senseval)是目前国际上最权威的词义消歧评测，我们的测试集来自Senseval-2(2001)[15]、Senseval-3(2004)[16]的English All Words任务，表1给出了这些任务的基本信息。

English All Words为开放测试，只提供测试集，对训练集没有限制。我们仅使用了SemCor[17]的Brown1和Brown2作为训练集，包含359 732个词(不含标点)，其中192 639个词有词义标注。对于训练集中不存在的观察值，我们使用WordNet中的最常用词义进行标注。MEMM方法采用GIS算法训练最大熵模型，迭代次数为100。表2给出了参加英语全词消歧任务系统的性能(F1值)。

表1 英语全词消歧任务基本信息

English All Words对训练集没有限制，因此对不同系统的比较是十分困难的，下面我们试图对实验结果作出一些说明。

首先，本文提出的MEMM方法的性能显著高于相同数据集上的其他序列标注方法，包括本文提出的HMM方法。这证明了将简单观察值扩展为复杂的特征向量确实是有效的， 这得益于大量语言学特征的引入。

表2 参加英语全词消歧任务的系统性能(F1值)

其次，在仅采用SemCor作为训练集的情况下，本文提出的MEMM方法也超过了Senseval-2的第2名和Senseval-3的第1名。其中，Senseval-2的第2名[19]采用了基于记忆的方法，并使用多个分类器进行投票；Senseval-3的第1名[20]也采用了基于记忆的方法，它的训练集包括SemCor，Senseval-2的数据以及WordNet中的例子。这说明序列标注方法完全可以用于全词消歧，并且性能与最好的有监督方法相当。我们看到，本文MEMM方法与Senseval-2的第1名[18]还有一定的差距，部分原因是文献[18]采用了很多SemCor以外的数据，如WordNet中的定义和互联网收集的数据等。

在Senseval-2中，Crestan等人[11]采用两阶段HMM进行全词消歧。第一阶段先通过HMM确定词形的语义标签，第二阶段再用HMM确定词形+语义标签的词义，另外还对高频词采用词样消歧的方法进行消歧。就性能而言，这种两阶段HMM方法与与单一HMM方法相当[10]，在本实验中也得到了证实。

在Senseval-2和Senseval-3中，Molina等人[12-13]采用HMM进行全词消歧，其状态为SemCor中的lex_sense[17]。这相当于对synset进行了压缩，其好处在于使状态数减少，从而缓解矩阵稀疏的问题。但是，我们认为这种压缩并不具备语言学基础，有可能造成算法的不稳定性，而且难以将HMM扩展为MEMM。实验表明，本文的HMM方法以synset为状态是合适的，其性能要略好于以lex_sense为状态的文献[12-13]，且具备良好的可扩展性。

6 结束语

全词消歧可以看作一个序列标注问题。然而，现有序列标注方法在全词消歧上的表现却不尽如人意，主要原因在于特征的有效利用和数据稀疏问题。本文从全词消歧的特点出发，针对上述不足，提出了两种基于序列标注的全词消歧方法，并采用柱状搜索和平滑策略解决了数据稀疏和高时间复杂度等问题，其中基于MEMM的全词消歧方法的性能较大幅度地超过了文献中已有的基于序列标注的方法。由于本文仅使用了基本的训练语料，本文提出的方法的实际性能还有进一步提高的空间。实际上，本文提出的方法可适用于一般的超大状态序列优化问题。

无论是一般的分类问题还是序列标注，特征选择都是至关重要的，下一步我们将研究各种特征对整体性能的影响，以便更好地改进算法。另外，条件随机域(CRF)是近来出现、在多个领域均有突出表示的序列标注方法。CRF是HMM和MEMM的推广，一般认为CRF的效果要比HMM和MEMM好。但是，CRF训练的时间复杂度比HMM和MEMM要高得多，一般只用于状态数较少(一般数百个状态以内)的场合。对于全词消歧这类含有数万个状态的问题，即使在采用柱状搜索算法后，CRF的训练仍然不可能在普通的工作站上完成，我们下一步将尝试采用集群计算的方式来解决这个问题。

[1] Mooney R. J. Comparative experiments on disambiguating word senses: An illustration of the role of bias in machine learning [C]//Proceedings of the 1996 Conference on Empirical Methods in Natural Language Processing (EMNLP). 1996. 82-91.

[2] Tratz S., Sanfillippo A., Gregory M., et al.PNNL: A supervised maximum entropy approach to word sense disambiguation [C]//Proceedings of the 4th International Workshop on Semantic Evaluations (SemEval-2007). Stroudsburg, PA, USA, 2007. 264-267.

[3] Escudero G., M rquez L., Rigau, G. On the portability and tuning of supervised word sense disambiguation [C]//Proceedings of the Joint SIGDAT Conference on Empirical Methods in Natural Language Processing and Very Large Corpora (EMNLP). 2000. 172-180.

[4] Lawrence R. Rabiner. A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition [C]//Proceedings of the IEEE. 1989. 257-286.

[5] Andrew McCallum, Dayne Freitag, Fernando Pereira. Maximum Entropy Markov Models for Information Extraction and Segmentation [C]//Proceedings of the 17th International Conference on Machine Learning. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.， 2000. 591-598.

[6] John Lafferty, Andrew McCallum, Fernando Pereira. Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data [C]//Proceedings of the 18th International Conference on Machine Learning. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2001. 282-289.

[7] El-B ze M., M rialdo B.. HMM Based Taggers [C]//H. Van Halteren eds. Syntactic Wordclass Tagging. Kluwer Academic Publishers, 1999.

[8] F. Jelinek. Statistical Methods for Speech Recognition [M]. Cambridge: MIT Press, 1998.

[9] Segond F., Schiller, A., Grefenstette, G., et al. An Experiment in Semantic Tagging using Hidden Markov Model Tagging [C]//Proceedings of the Joint ACL/EACL Workshop on Automatic Information Extraction and Building of Lexical Semantic Resources. Stroudsburg, PA, USA, 1997. 78-81.

[10] Claude de Loupy, MarcEl-Beze, Pierre-Fran ois Marteau. Word Sense Disambiguation using HMM Tagger [C]//Proceedings of the 1st International Conference on Language Resources and Evaluation (LREC). Granada, Spain, 1998. 1255-1258.

[11] E. Crestan, M. El-Beze, C. De Loupy. Improving WSD with Multi-Level View of Context Monitored by Similarity Measure [C]//Proceedings of the 2nd International Workshop on Evaluating Word Sense Disambiguation Systems. Toulouse, France, 2001. 67-70.

[12] Antonio Molina, Ferran Pla, Encarna Segarra. A Hidden Markov Model Approach to Word Sense Disambiguation [C]//Proceedings of the 8th Ibero-American Conference on AI: Advances in Artificial Intelligence. Longdon, UK: Springer-Verlag. 2002. 655-663.

[13] Antonio Molina, Ferran Pla, Encarna Segarra. WSD system based on Specialized Hidden Markov Model [C]//Proceedings of the Third International Workshop on the Evalution of Systems for the Semantic Analysis of Text, 2004.

[14] Yoong Keok Lee, Hwee Tou Ng. An Empirical Evaluation of Knowledge Sources and Learning Algorithms for Word Sense Disambiguation [C]//Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP). Stroudsburg, PA, USA, 2002. 41-48.

[15] Edmonds P., Cotton S. Senseval-2: Overview [C]//Proceedings of the 2nd Internationnal Workshop on Evaluating Word Sense Disambiguation Systems. 2001. 1-6.

[16] Benjamin Snyder, Martha Palmer. The English All-Words Task [C]//Proceeding of Senseval-3: The 3rd International Workshop on the Evaluation of Systems for the Semantic Analysis of Text. Barcelona, Spain, 2004. 41-43.

[17] Miller G.A., Chodorow M., Landes S., et al. Using a Semantic Concordance for Sense Identification [C]//Proceedings of the ARPA Workshop on Human Language Technology. Stroudsburg, PA, USA, 1994. 240-243.

[18] Mihalcea R. Word sense disambiguation with pattern learning and automatic feature selection [J]. Natural Language Engineering, 2002,8(4):348-358.

[19] Hoste V., Hendrickx I., Daelemans W., et al. Parameter optimization for machine learning of word sense disambiguation [J]. Natural Language Engineering, 2002,8(4):311-325.

[20] Decadt B., Hoste V., Daelemans W., et al. GAMBL, genetic algorithm optimization of memory-based WSD [C]//Proceedings of the 3rd International Workshop on the Evaluation of Systems for the Semantic Analysis of Text. 2004. 108-112.

[21] Mihalcea R., Faruque E. Senselearner: Minimally supervised word sense disambiguation for all words in option text [C]//Proceedings of the 3rd International Workshop on the Evaluation of Systems for the Semantic Analysis of Text. 2004. 155-158.

附录A MEMM模型采用的特征

MEMM模型与一般HMM的最大不同，就是语言学特征的使用。相对于lemma而言，特征的引入可以捕获目标词的上下文中的各类语言学特征，有利于对目标词义的消歧。这些特征主要包括七类： 邻近词的词性、局部搭配关系、依存句法关系、特定范围内的上位词(hypernym)链、特定范围内的WordNet语义标签、特征范围内的WordNet动词框架和句中的各个单词。

A.1 邻近词词性(七维)

我们用Pi(P-i)表示当前词w右(左)边第i个词的词性，使用以下七个特征：P-3,P-2,P-1,P0,P1,P2,P3。所有的词不能跨越句子的边界。例如，句子”Reid/NNP saw/VBD me/PRP looking/VBG at/IN the/DT iron/NN bars/NNS ./.”，当前词为bars，则它的邻近词词性特征为，其中ε为跨越句子后的标记。

A.2 局部搭配关系(11维)

我们用Ci,j表示当前词的从第i个词到第j个词的词条的字符串连接，使用以下11个特征：C-1，-1,C1，1,C-2，-2,C2，2,C-2，-1,C-1，1,C1，2,C-3，-1,C-2，1,C-1，2,C1，3。 例如，句子”Reid/NNP saw/VBD me/PRP looking/VBG at/IN the/DT iron/NN bars/NNS ./.”，当前词为bars，则它的C-2，1特征为the_iron_bar_.。

A.3 依存句法关系(10维)

该特征假设当前词的语义与和其有直接依存关系的词有关，这在某种程度上反映了语义的长距离(句法)依赖关系。依存句法假设，句法结构是用非对称的二元关系将词连接而成的。这种二元关系称为依存关系，被支配的词称为依赖词(dependent)，另一个词则称为头词(head)。我们使用以下特征： 当前词w的头词h的词条，h与w的依存关系类型，h的词性，h与w的相对位置(h在w的左边还是右边)；当前词w左边最近的依赖词l的词条，l与w的依存关系类型，l的词性；当前词w右边最近的依赖词r的词条，r与w的依存关系类型，r的词性。例如，句子”Reid/NNP saw/VBD me/PRP looking/VBG at/IN the/DT iron/NN bars/NNS ./.”， 其依存关系见图A1，当前词为looking，则它的依存句法关系特征为。

图A1 依存关系

A.4 特定范围内的上位词链

特定范围，指目标单词的前后三个邻近词及依存关系链三步以内的词，下同。上位词从WordNet中抽取，我们包含给定范围内的词的最常用词义(MFS, Most Frequent Sense)的整个上位词链。例如，句子”Reid/NNP saw/VBD me/PRP looking/VBG at/IN the/DT iron/NN bars/NNS ./.”，当前词为looking.looking的前后三个邻近中具有上位词的词有saw和iron，而looking的三步以内依存关系链中具有上位词的词有iron和bars，则共有saw，iron和bars三个单词具有上位词链，他们分别为,和。

A.5 特定范围内的WordNet语义标签

语义标签从WordNet中抽取，我们包含给定范围内的词的最常用词义的语义标签。例如，句子”Reid/NNP saw/VBD me/PRP looking/VBG at/IN the/DT iron/NN bars/NNS ./.”，当前词为looking。特定范围内具有语义标签的词为saw，iron和bars，则语义标签特征为。

A.6 特定范围内的WordNet动词框架

动词框架从WordNet中抽取，我们包含给定范围内的词的最常用词义的动词框架。例如，句子”Reid/NNP saw/VBD me/PRP looking/VBG at/IN the/DT iron/NN bars/NNS ./.”，当前词为looking。特定范围内具有动词框架的词为，则动词框架特征为<2,8,9>。在WordNet中框架号2表示句式”Somebody——s”，框架号8表示句式”Somebody——s something”，框架号9表示句式”Somebody——s somebody”。

A.7 句中的各个单词

我们直接将句中的每个单词作为当前观察值的一个特征。