AdaBoost.MH算法硕士学位毕业论文

大连理工大学硕士学位论文

摘要

词义排歧在机器翻译、信息检索、句子分析和语音识别等许多领域有重要的作用。因此在自然语言处理领域，词义排歧方法的研究具有重要的理论和实践意义。本文主要研究在标注语料库支持下的基于有指导学习算法的词义排歧方法。

在词义排歧模型中引入有指导的AdaBoost.MH算法。首先通过简单决策树算法对多义词上下文中的知识源进行学习，产生准确率较低的弱规则；之后，通过AdaBoost.MH算法对这些弱规则进行加强；经过若干次迭代后，最终得到一个准确度更高的规则，即为最终的排歧模型。论文还针对系统的学习效率和实用性给出了一种简单终止算法迭代的方法。

为获取多义词上下文中的知识源，本文在采用传统的词性标注和局部搭配序列等知识源的基础上，引入了一种新的知识源，即语义范畴。实验结果表明语义范畴知识源的引入有助于提高算法的学习效率和排歧的正确率。

建立有指导学习算法所需的大规模人工标注语料是相当困难的，本文提出了一种通过WWW资源自动构建适合汉语多义词排歧的标注语料的方法。并通过实验验证了这种语料库的可用性。

在对6个典型汉语多义词和SENSEVAL3中文语料中20个汉语多义词的词义消歧实验中，AdaBoost.MH算法获得了较高的开放测试正确率(85.75%和75.84%）。

关键词：自然语言处理；词义排歧；AdaBoost.MH算法；知识源

一种基于AdaBoost.MH算法的汉语多义词排歧方法

Abstract

Word sense disambiguation (WSD) plays an important role in many areas of natural language processing such as machine translation, information retrival, sentence analysis, speech recognition. The research on WSD has great theoretical and practical significance．The main work in the dissertation is to study the supervised learning algorithm learning WSD knowledge from many kinds of resources based on large sense-tagged Chinese corpus.

An approach based on supervised AdaBoost.MH learning algorithm for Chinese word sense disambiguation is presented. AdaBoost.MH algorithm is employed to learn WSD knowledge from many kinds of resources and to boost the accuracy of the weak stumps rules for decision trees and repeatedly calls a learner to finally produce a more accurate rule. A simple stopping criterion is also presented in view of the efficiency of learning and the utility of system.

As for Chinese WSD, in order to extract more contextual information, we introduce a new WSD knowledge --- semantic categorization as well as two classical knowledge sources: part-of-speech of neighboring words and local collocations. Experimental results show that the semantic categorization knowledge is useful for improving the learning efficency of the algorithm and accuracy of disambiguation.

Due to the flexibility and complexity of bulding up a broad coverage semantically annotated corpus, an approach based on WWW search engines to automatically obtain annotated corpus for Chinse WSD is presented.

AdaBoost.MH algorithm has a higher disambiguation accuracy rates which are 85.75% and 75.84% in open tests for 6 typical polysemous Chinese words and 20 polysemous words from SENSEVAL3 Chinese corpus.

Key Words：Natural Language Processing; Word sense disambiguation;

AdaBoost.MH algorithm；Multiple knowledge sources

毕业设计（论文）原创性声明和使用授权说明

原创性声明

本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。

作者签名：日期：

指导教师签名：日期：

使用授权说明

本人完全了解大学关于收集、保存、使用毕业设计（论文）的规定，即：按照学校要求提交毕业设计（论文）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。

作者签名：日期：

学位论文原创性声明

本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。

作者签名：日期：年月日

学位论文版权使用授权书

本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。

涉密论文按学校规定处理。

作者签名：日期：年月日

导师签名：日期：年月日

指导教师评阅书

评阅教师评阅书

教研室（或答辩小组）及教学系意见

目录

摘要........................................................................................................................................ I Abstract .................................................................................................................................... II 引言 (1)

1 问题描述 (3)

1.1 词义排歧的提出及其意义 (3)

1.1.1词义排歧 (3)

1.1.2词义排歧研究的意义 (4)

1.2 国内外的研究状况 (5)

1.2.1 有指导排歧方法 (5)

1.2.2基于词典的排歧方法 (9)

1.2.3无指导的排歧方法 (10)

1.3 面临的主要问题 (11)

1.3.1 上下文选择 (11)

1.3.2词义的划分 (12)

1.4词义排歧的评测方法 (12)

1.5本文的工作 (12)

2 面向WSD的AdaBoost.MH算法模型 (14)

2.1基本概念 (14)

2.2 AdaBoost.MH算法简介 (15)

2.2.1 AdaBoost算法背景 (15)

2.2.2 AdaBoost算法基本思想 (16)

2.2.3算法误差的分析 (18)

2.2.4多类分类问题 (20)

2.2.5 AdaBoost算法的优缺点 (21)

2.3面向WSD的AdaBoost.MH算法描述 (21)

Z的选取 (23)

2.4弱学习器的设计及

t

3 上下文特征的选择 (25)

3.1相邻词的词性标注（POS） (25)

3.2局部搭配信息 (26)

3.3语义范畴信息 (26)

3.3.1《同义词词林》简介 (26)

3.3.2对《同义词词林》中未登录词的处理 (28)

3.3.3语义范畴信息的选取 (29)

4 汉语AdaBoost.MH -- WSD实验 (31)

4.1语料库 (31)

4.1.1人民日报语料 (31)

4.1.2 SENSEVAL3 中文语料 (31)

4.2实验评测及结果 (32)

4.2.1人民日报语料实验结果与评测 (33)

4.2.2 SENSEVAL3 中文语料实验结果与评测 (34)

4.3算法中迭代次数的确定 (35)

4.4语义信息的引入对排歧效果的影响 (36)

4.4.1人民日报语料实验 (36)

4.4.2 SENSEVAL3 中文语料实验 (37)

5 自动建立带标注的语料库的方法 (39)

5.1自动构建标注语料库的模型 (39)

5.1.1搜索关键字的建立 (40)

5.1.2语料库的建立和修剪 (41)

5.2语料库可用性的评测实验与分析 (43)

5.2.1语料库 (43)

5.2.2语料库中搜索到的新搭配 (43)

5.2.3上下文特征的选取 (43)

5.2.4实验结果及评测 (44)

结论 (46)

参考文献 (47)

附录A SENSEVAL3中文语料示例 (50)

附录B标注语义范畴信息的语料示例 (52)

附录C《同义词词林》语义信息示例 (54)

附录D《同义词词林扩展版》语义信息示例 (54)

攻读硕士学位期间发表学术论文情况 (56)

致谢 (57)

大连理工大学学位论文版权使用授权书 (58)

引言

计算语言学（Computational Linguistics）是一个横跨语言学、数学和计算机科学的新兴交叉学科[1]。它通过建立形式化的数学模型，来分析、处理自然语言，并在计算机上用程序来实现分析和处理的过程，从而达到以机器来模拟人的部分乃至全部语言能力的目的[2]。

计算语言学的研究工作分为两个方面。

第一，从计算的角度来研究语言的性质；

第二，将语言作为计算对象来研究相应的算法。

所谓从计算的角度来研究语言的性质，就是要求将人们对语言的结构规律的认识以精确的、形式化的、可计算的方式呈现出来，而不是像其他语言学研究那样，在表述语言的结构规律时一般采用非形式化的表达形式。所谓将语言作为计算对象来研究相应的算法，就是研究如何以机械的、规定了严格操作步骤的程序来处理语言对象（主要是自然语言对象，当然也可以是形式语言对象），包括识别一个语言片断（比如词组、句子或篇章）中的大小语言单位，分析该语言片断的结构和意义（自然语言理解），以及如何生成一个语言片断来表达确定的意思（自然语言生成），等等。

自然语言处理(Natural Language Processing)是利用计算机技术研究和处理语言的一门学科，即把计算机作为语言研究的强大工具，在计算机的支持下对语言信息进行定量化的研究，并提供可供人与计算机之间能共同使用的语言描写。它属于计算语言学的算法部分[1]，并经过如下的过程——把需要研究的语言学问题加以形式化，使之能以一定的数学形式或者接近于数学的形式，严格而规整地表示出来；把这种严格而规整的数学形式表示为算法，使之在计算上形式化；根据算法编写计算机程序，使之在计算机上加以实现。

自然语言处理是人工智能研究的最重要的课题之一。人类知识大都是以语言的形式表示并流传下来的，据统计，在信息领域中80%以上的信息是以语言文字为载体的。自然语言处理的重大突破，将为知识获取开辟重要来源。同时它也将触发人机接口革命。它将使计算机具有听、说、读、写的能力，人们可以用自然语言和计算机交流，这将给使用者带了极大的方便。自然语言处理系统可以用作专家系统、知识工程、情报检索、办公室自动化的自然语言人机接口，有很大的实用价值。机器翻译将使人们跨越语言壁垒，让全世界的人顺利交流，让每个用户都能共享因特网的浩瀚信息和无限商机。

语言是音义结合的符号系统，而词是语言中能够独立运行的最小符号。因此，研究语言符号的意义都以词作为基本单位[3]。在自然语言处理领域，词义排歧在机器翻译、信息检索、句子分析和语音识别等自然语言处理的许多领域有十分重要的用途。因此词义排歧方法的研究在自然语言处理领域具有重要的理论和实践意义。

任何一个课题的研究与它所在的领域的研究方法息息相关，与当时所具有的各种条件密切相关，词义排歧问题的研究也不例外。它经历了基于直觉的理性主义方法，即定性的方法到基于观察的经验主义方法，即统计方法[5]的发展过程。

进入九十年代以后，随着计算机事业的蓬勃发展，计算机存储容量和运算速度的飞速提高，计算语言学的研究也进入了一个崭新的历史阶段，即语料库语言学的时期[3]。通过使用大规模的语料库，计算机能够自动获得各种统计数据，以此来解决规则方法中知识空缺问题。

在大规模真实文本处理中，基于统计的方法与基于规则的方法相比体现出以下优势：

(1)统计方法获取的知识一致性好。而规则方法，由于每个人思考问题的不同，而会采取不同的处理方法，当需要添加新的规则时，又必须注意协调与已有规则的关系，避免规则之间产生矛盾。

(2)统计方法比较灵活，覆盖面比较广，可以获取语言中那些经验性的、小粒度的知识，能更好的覆盖各种复杂纷繁的语言现象。

目前在语言处理的各个层面上，基于统计的方法几乎都在发挥着重要的作用。

机器学习是对具有学习能力的计算机算法以其经验不断改进其完成任务效果的研究。它是人工智能的一个领域，是知识获取的一个过程。机器学习是一种归纳学习，即对已分类的数据，通过归纳其分类的原因，产生一些概念性描述作为学习的结果。

在词义排歧领域，近几年国内外许多研究人员将统计学和机器学习引入到词义消歧的处理中，提出基于语料库的多义词处理方法。从语料库中学习的方法主要有有指导学习和无指导学习两种。一般来说，有指导的消歧方法要比无指导的方法有更好的效果。

本文的主要工作是研究在标注语料库支持下的有指导的词义排歧算法和利用WWW资源自动构建标注语料库两个方面。

1问题描述

1.1词义排歧的提出及其意义

1.1.1词义排歧

词义指一个词所具有的意义，文本的词义标注就是给文本中每个词表上在所属上下文环境中对应的意义编码。这个意义编码可以有以下四种形式[4]：1）是某个义类词典中的词条所对应的一类代码（如《同义词词林》中的义类代码）；2）是普通词典中一个词条下释义文本对应的编号（如《现代汉语通用词典》中对词条的义项编号）；3）是在转换词典中一个词条对应得目标词，即一种语言中的词对另一种语言的翻译词；4）是在概念词典中概念的定义项（如How-Net中概念的定义）。

如“材料”一词，在《辞海》里面共有3个不同的义项：

义项1：可以直接造成成品的东西；

义项2：可供写作或参考的事实或文字资料；

义项3：比喻适于做某种工作的人。

例如，在机器翻译过程中，当翻译系统遇到如下含有“材料”的句子时，系统就要根据上下文的信息，给句子的多义词“材料”选择一个合适的义项，作为多义词的词义。这个过程就是词义排歧。

以/p/Kb05 树叶/n/Bh11 、/wp/-1 彩布条/n/Bq01 和/c/Kc01 香烟盒纸/n/Bp17 为/v/Ja01 材料/n/Ba06 的/u/Kd01 贺卡/n/Bp18 ，/wp/-1 做工/v/Hj21 虽/c/Kc04 简/a/Ed37 ，/wp/-1 其/r/Ba10 情/n/Df04 却/d/Ka33 浓/a/Eb12 。/wp/-1

对于这个句子，翻译系统中的词义排歧就是指系统根据上下文信息给出多义词“材料”对应的上述正确义项1（可以直接造成成品的东西）的过程。

多义词情况，无论是汉语还是西方语言（如英语、法语）一词多义现象普遍存在。本文对《同义词词林》中的多义词情况进行了统计（参见表1.1）。因此，词义标注的任务就是在某个特定的上下文中，确定多义词所属意义代码，因此词义标注方法的研究实际上就是词义排歧方法的研究。

表1.1 《同义词词林》中多义词的分布情况表

一个义类二个义

类

三个义

类

三个义类以

上

总数歧义比例

一字词1973 833 397 571 3774 48.0%

二字词28154 3837 572 118 32681 16.0%

二字以上

词

12597 999 96 6 13698 9.0%

总计42724 5669 1065 695 50154 14.8%

1.1.2词义排歧研究的意义

词义排歧一直是自然语言处理研究领域十分重要的问题和研究热点之一。它的研究从50年代初期机器翻译的研究起一直收到人们的关注。词义排歧任务本身是一个中间任务，是大多数自然语言处理任务的一个必不可少的中间层次，在自然语言中有着重要用途[5]。例如：

1）机器翻译：机器翻译中的词义排歧有其特殊性，它以目标词区分单词词义。在机器翻译中找一个词的目标词是一重要问题，词义排歧问题解决

的好坏直接影响译文质量。例如：在汉英机器翻译系统中，“interest”

在汉语中对应两个目标词“利益”或“利息”，在具体翻译时必须根据

当前的上下文确定“interest”的正确词义，以翻译成正确的目标词。

2）信息检索和信息分类：在信息检索和信息分类中，受一词多义的影响，系统可能检索出一些包含同义词但是具有不同意义的文本。如：想检索

一些与文档相关的参考资料时，可能以“材料”作为检索词。若只根据

词型检索，则检索出来所有含有“材料”的文章，在这些文章中有些可

能是关于“生产材料”的文本，得到不必要的检索结果。因此在信息检

索中词义排歧也具有重要作用。

3）句法分析：在识别句子的语法结构时，词汇的语义也起着重要作用。因为语法歧义现象在各种语言中普遍存在，而解决这一问题的关键方法就

是引入词义，也就是要依靠句子中词的意义来确定此时句子的结构。如

“参观图书馆的大厅”和“参观图书馆的人们”同样具有

“V+N+的+N”的词性序列，但却有着不同的句法结构，标上词义后可

以靠这些词性之间的不同语义搭配确定它们的结构。

4）自然语言理解：确定句子的语义结构时，必须考虑句子中每个词的词义。在已知句子中每个词的词义前提下，通过语义分析能够得到句子的

语义结构，如句子的格结构。

5）语音识别和音字转换：基于词的N元模型只考虑了词之间的接续关系，在识别结果中存在词之间无意义联系的句子，造成识别错误。在引

入词义后，可以得到意义之间的接续关系，提供词在意义一级上的接续

关系，在一定程度上避免这样的错误。

综上所述，作为自然语言处理过程中一个重要过程，词义排歧的研究具有重要理论和实践意义。它的研究成果可以直接应用于自然语言处理的许多方面。

1.2国内外的研究状况

近几年，国内外研究人员将统计学和机器学习引入到词义消歧的处理中，提出基于语料库的多义词处理方法（Corpus Based Approach，CBA）。从语料库中学习的方法主要有有指导学习和无指导学习两种[5]。一般来说，有指导的消歧方法要比无指导的方法有更好的效果。

有指导的学习中训练数据是已知的（在这里是词义标注），而在无指导的学习中训练事物的分类是未知的。因此，无指导学习通常被称为聚类任务（clustering task），而有指导学习通常被称为分类任务（classification task），也可以称为函数拟合，就是说基于一些数据点推断出函数形态[6]。

然而，在统计自然语言处理领域中，事情往往并非这么简单。由于标注好的语料库非常昂贵，所以人们希望可以从未标注的数据中学习，即无指导的学习，并且试图在自己的算法中使用各种资源，比如词典，或者使用更加复杂的结构化数据。在这些方法中，系统可以建立在一些所谓的“种子”数据集上，然而即可利用这个系统，从未标注的数据中学习，逐步扩大种子数据集。下面分别对这两种方法中比较典型的算法进行论述。

1.2.1有指导排歧方法

在有指导的排歧中，一个已经标注好的语料库被用来训练。在这个样本训练集中，多义词w 每一次出现都被标注了一个语义标签（通常是符合上下文的语义s）。这样就可以为有指导排歧提供统一分类的实例。统计分类的任务就是构建一k

c对新的多义词进行分类。

个分类器，根据上下文

i

在众多的有指导的学习算法中，有一些算法已经被应用到多义词排歧中。其中有两种典型的算法，它们代表了统计自然语言处理中的两个重要理论方法：贝叶斯

分类[7]和信息论[8]。这两种方法同时证明了上下文中的多种完全不同的信息源可以应用到排歧算法中。第一种方法把上下文看做是一个无结构词集，整合了上下文窗口中众多的词汇信息。第二种方法仅仅考虑了上下文中的一个特征信息，这个特征信息可以很灵敏的反应上下文结构。但是，这个特征要谨慎地从大量的潜在信息中选取。其它使用较多的有指导算法还有决策树学习算法和决策表算法。

1.2.1.1 贝叶斯分类

贝叶斯分类器的原理是：它在一个大的上下文窗口中考虑多义词周围的词的信息。每个实词都含有潜在的有用信息，暗示多义词的哪个词义被使用。这个分类器不是简单的进行特征选择，而是组合了所有特征。本文的形式化描述来自于[6]。分类器的有指导训练要求语料库中的多义词都事先被正确的词义标注。

在选择类别的时候，贝叶斯分类器使用贝叶斯决策规则，这个规则最小化了错误概率：

Decide "s if "")|()|(s s for c s P c s P k k ≠>

贝叶斯决策规则是最优化的，因为它最小化了错误概率。对于每个独立的例子，它选择带有最高条件概率的类，因此有最小的错误率。对于一系列类别决策的错误率也会尽可能小。

通常)|(c s P k 的值是未知的，但是可以使用下面的贝叶斯规则来计算它：

)()()|()|(k k k s P c P s c P c s P =

(1.1)

)(k s P 是词义k s 的先验概率，它是不知道任何上下文信息时得到的k s 出现的概率。)(k s P 被综合了上下文信息的因子)(/)|(c P s c P k 校正，然后得到后验概率)|(c s P k 。

如果仅仅是要得到正确的分类，那么可以通过消除)(c P （对于所有的词义，它是一个常量，因此不会影响最大值的选择）来简化这个分类任务。也可以使用概率的对数值来简化计算。然后。我们就能为 w 指定一个词义"

s ：

)](log )|(max[log arg )()|(max arg )|(max arg "

k k k k k s P s c P s P s c P c s P s +===

(1.2)

Gale 等人提出的分类器是一个特殊的贝叶斯分类器，即单纯贝叶斯分类器。它把分类所基于的状态空间描述成一系列的特征，根据出现在上下文的词来描述词w 的上下文。

单纯贝叶斯假设认为用来刻画事物特征的属性都是条件独立的：

∏==inc v k j k j j k j s v P s c in v v P s c P )

|(})|}|({)|(

(1.3)

在词义排歧中，单纯贝叶斯假设有两个结论。第一个是上下文中所有结构和词语顺序都可以被忽略。这通常是指一个可有重复的单词集模型。另一个结论是指在可有重复的单词集中出现的词均独立于其它词。

1.2.1.2 基于信息论的方法

信息论分类方法试图寻找一个单一的上下文特征，它可以可靠地指示出多义词的哪一种词义被使用。为了更好的地应用语料信息，信息的量值需要进行规范化。Brown 等人使用了Flip-Flop 算法来解决这个问题。算法描述如下：

Find random partition P = {P 1，P 2} of {t 1，t 2，…，t m }

While (improving) do

Find partition Q = {Q 1，Q 2} of {x 1，x 2，…，x n }

that maximizes I （P ；Q ）

Find partition P = {P 1，P 2} of {t 1，t 2，…，t m }

that maximizes I （P ；Q ）

End.

Flip-Flop 算法的每一次迭代都必须满足使互信息I （P ；Q ）单调增加，所以算法的一个很自然的中止条件就是互信息I （P ；Q ）不再增加或者增加很少。其中P 为最初的词义划分，Q 为指示器。I （P ；Q ）为P ，Q 的互信息。互信息的定义如下：

∑∑∈∈=X x Y y y p x p y x p y x p Y X I )()(),(l o g ),();( (1.4)

对于计算一个特殊指示器值的最佳划分，Flip-Flop 算法是一个有效的线性时间算法，它基于分裂理论（splitting theorem ）[8]。对所有可能的指示器使用这个算法，然后选择带有最高互信息的指示器。

当指示器和它取值的特殊划分已经确定之后，排歧就很简单了，如下所示：

1） 对于出现的一个多义词，确定它的指示器值i x ；

2） 如果i x 在Q 1中，指定多义词的词义就为词义1；如果i x 在Q 2中，指定多

义词的词义就在词义2中。

1.2.1.3 决策树的学习方法

决策树算法的主要思想是：一棵决策树（decision tree ）是一个“提问-问答”机制。对一个事件，经过一系列的“提问-回答”逐渐较少问题的不确定性，从而做出正确的决策，其中当前的提问与以前的回答有关。形式上，决策树是一棵N 叉树，其中事件与根节点关联，提问与每个内部节点关联，选择与每个叶子节点关联。Black[10]曾采用这种方法学习了5个含有4个词义的多义词的决策树。首先从语料库中抽取每个词的训练样本，每个词各有2000个句子；然后使用“提问-回答”的方式，获得多义词的决策树：根节点对应于多义词的排歧任务，提问是识别多义词词义的一个特征，叶子节点是多义词的一个词义。即学习阶段；最后使用学习得到的决策树对多义词确定词义的阶段，即排歧过程。

1.2.1.4 决策表的学习方法

决策表的形式为一个二元组（条件，值）。Yarowsky[7]曾使用决策表学习词义排歧时使用的知识。在决策表中，条件对应多义词的一个搭配，值是这个多义词在两个不同词义下的概率似然比，决策表按似然比由小到大排列，似然比大的排列被排到决策表的前面位置，表明该搭配可以表征某多义词的词义。

Yarowshy 曾对多义词在一篇文章中和在一个特定上下文环境中具有的词义情况作了实验调查，发现两条规律：1）一个词在每个话题中只对应一个词义；2）一个多义词在一个搭配中只有一个词义。即在给定搭配中每个词只表现出一个词义。不同搭配所对应的词义是不同的，如果能找出对多义词排歧最有用的搭配，则可以用它来解决多义词问题。考虑的搭配类型有多义词左、右两边的第一个词，多义词在窗口长度为左右K 的上下文的词。在对多义词进行手工标注后，按上述搭配类型进行统计，计算对数似然比：

推荐访问:大连理工大学论文翻译 硕士学位 毕业论文 算法

---