（计算机应用技术专业论文）单类中心学习及其在二元关系抽取中的应用.pdf

中文摘要 在互联网上进行二元关系抽取，是当前信息抽取的重要研究方向。为利用互 联网的大量未标定语料，许多文献提出了基于s e l f - t r a i n i n g 机制的学习方法：即 在小标注集上训练初始系统，然后在系统运行过程中，自动标定可靠候选，重新 训练，以改进系统性能。 实践证明：上述方法在二元关系抽取中是行之有效的，但已有文献缺乏对学 习过程的理论分析。 本文首先将在二元关系抽取中的模式学习问题转化为单类文本中心的学习 问题。在文本向量空间中，当初始中心被给定后，可将其足够小邻域内的文本向 量作为自动标定数据。本文要解决的核心问题是：当数据集具有何种特性时，利 用自动标定数据能确定地改进对单类中心的学习? 为解决该问题，本文研究文本向量空间的分布特性。为克服高斯混合模型在 描述具有硬聚类特性的数据分布时的缺点，本文提出了基于k m e a n s 算法划分区 域的t g m k 模型，并揭示了t g m k 模型与k m e a n s 算法、高斯混合模型的密切 联系。实验结果表明：t g m k 模型适合描述多类文本数据。 本文在k - m e a n s 算法基础上提出了s i n g l e m e a n 算法。文中证明：当多类数 据集适合被1 - t g m k 的泛化模型一1 t g m r 模型所描述时，新算法从目标类的 初始中心出发，将收敛到实际中心。至此，完成了对核心问题的解答。实验表明 了新算法在文本数据上的有效性，从而说明了s e l f - t r a i n i n g 机制在二元关系抽取 中的有效性。 本文为二元关系抽取工作建立了基于s i n g l e m e a n 算法的形式化学习模型， 并针对在互联网上进行二元关系抽取的特殊性，提出了新的候选评分方法和自动 标定方法。 本文将学习模型应用到中文问答对和中英文术语对的抽取中。与前人工作不 同的是：本文将s e l f - t r a i n i n g 机制引入中文问答模式和中英文术语模式的学习中， 使得系统对人工标定语料的依赖度减到最小；本文利用启发规则，改进模式和候 选的评分方法。实验表明：与同类系统相比，新系统能在更小的标注集上，实现 更优的性能。 关键词：s e l f - t r a i n i n g 单类中心学习二元关系抽取高斯混合模型问答模式学 习术语模式学习 a b s t r a c t t oe x t r a c tt h eb i n a r yr e l a t i o nf r o mw e bi sa ni m p o r t a n tr e s e a r c hd i r e c t i o ni nt h e f i e l do fi n f o r m a t i o ne x t r a c t i o n m a n yl i t e r a t u r e sh a dp r e s e n t e dl e a r n i n gm e t h o d s b a s e do ns e l f - t r a i n i n gm e c h a n i s m i nt h e s em e t h o d s ，a ni n i t i a ls y s t e mi st r a i n e do na s m a l ll a b e l e dd a t as e t t h e nt h es y s t e ml a b e l st h er e l i a b l ec a n d i d a t ed a t at or e t r a i n i t s e l ff o rb e t t e rp e r f o r m a n c e t h e s el i t e r a t u r e ss h o wt h a tt h ea b o v em e t h o d sa r ee f f i c i e n ti ne x t r a c t i o no f b i n a r yr e l a t i o n b u tn ol i t e r a t u r et r i e st oa n a l y z et h em e t h o d ss t r i c t l y t h i sp a p e rt r a n s f o r m st h ep a t t e r nl e a r n i n gi nt h ee x t r a c t i o no fb i n a r yr e l a t i o ni n t o t h el e a r n i n go fc e n t r eo fs i n g l et e x tc l a s s i nt e x tv e c t o rs p a c e ，t h ev e c t o r si nt h es m a l l n e i g h b o r h o o dr e g i o no ft h ei n i t i a lc e n t r ec o u l db el a b e l e da st h er e l i a b l ed a t a t h i s p a p e ra i m st oa n s w e rt h ek e yp r o b l e m ：w h a tn a t u r et h ed a t as e ts h o u l do w n ss ot h a t t h es e l f - l a b e l e dd a t ac a nd e f i n i t e l yi m p r o v et h el e a r n i n go f s i n g l ec l a s sc e n t r e t h i sp a p e rs o l v e st h ek e yp r o b l e mt h r o u g ht h es t u d yo nt h en a t u r eo ft e x tv e c t o r s p a c e f o rc o n q u e rt h ed e f e c t si nt h ed e s c r i p t i o nf o rd i s t r i b u t i o no f “h a r d d a t as e tb y g a u s s i a nm i x t u r em o d e l ，t h i sp a p e r p r e s e n t san e wm o d e l ：t g m km o d e lb a s e do nt h e p a r t i t i o n sa c q u i r e db yk - m e a n sa l g o r i t h m ，a n de x p o s e st h er e l a t i o n sa m o n gt h e t g m km o d e l ，k m e a n sa l g o r i t h ma n dg a u s s i a n m i x t u r em o d e l t h ee x p e r i m e n t r e s u l ts h o w st h a tt g m km o d e li ss u i t a b l ea st h ed e s c r i p t i o nf o rt h et e x td a t as e to f m u l t i p l ec l a s s e s b a s e do nk - m e a n sa l g o r i t h m ，t h i sp a p e rp r e s e n t san e w a l g o r i t h m ：s i n g l e m e a n a l g o r i t h m t h i sp a p e rp r o v e st h a ti ft h ed a t as e to fm u l t i p l ec l a s s e si ss u i t a b l et ob e d e s c r i b e db y1 - t g m rm o d e lw h i c hi st h eg e n e r a l i z a t i o nv e r s i o no ft g m km o d e l ， t h eo u t p t i tc e n t r eo fs i n g l e m e a na l g o r i t h mw i l ld e f i n i t e l yc o n v e r g et ot h ea c t u a l c e n t r eo fd a t as e tf r o mt h ei n i t i a lc e n t r e t h ea b o v er e s e a r c h e ss o l v et h ek e yp r o b l e m p e r f e c t l y t h ee x p e r i m e n ts h o w st h a ts i n g l e - m e a na l g o r i t h mi se f f i c i e n to nt h et e x t d a t as e to fm u l t i p l ec l a s s e s ，w h i c ha l s os h o w st h a tt h el e a r n i n gm e t h o db a s e do n s e l f - t r a i n i n gm e c h a n i s mi se f f i c i e n ti nt h ee x t r a c t i o no fb i n a r yr e l a t i o n t h i sp a p e rc r e a t e saf o r m a ll e a r n i n gm o d e lf o rt h ee x t r a c t i o no fb i n a r yr e l a t i o n b a s e do ns i n g l e - m e a na l g o r i t h m ，a n dp r e s e n t san e ws c o r em e t h o df o r c a n d i d a t e sa n d an e ws e l f - l a b e l e dm e t h o da g a i n s tt h ep a r t i c u l a r i t yo ft h ee x t r a c t i o no fb i n a r yr e l a t i o n f r o mw e b t h i s p a p e ru s e s t h ef o r m a lm o d e lt o a c q u i r ec h i n e s eq ap a t t e r n s a n d c h i n e s e e n g l i s ht e r m i n o l o g yp a i r s d i f f e r e n t l yw i t ht h ep r e v i o u sw o r k ，t h i sp a p e r p r e s e n t s n e wm e t h o d st ol e a r nc h i n e s e q - ap a r e r n sa n dc h i n e s e - - e n g l i s h t e r m i n o l o g yp a r e r n sb a s e do ns e l f - t r a i n i n gm e c h a n i s m ，w h i c hr e d u c e st h e d e p e n d e n c eo fl a b e l e dd a t as e tt ot h em a x i m u me x t e n t t h i sp a p e ra l s ou t il i z e st h e h e u r i s t i cr u l e st oi m p r o v et h es c o r i n gm e t h o d sf o rt h ep a t t e r n sa n dc a n d i d a t e s t h e e x p e r i m e n tr e s u l t ss h o wt h a tc o m p a r e dw i t ht h es a m ek i n do fs y s t e m s ，o u rs y s t e m s h a v eb e t t e rp e r f o r m a n c e so ns m a l l e r l a b e l e dd a t as e t k e y w o r d s ：s e l f - t r a i n i n g ，t h el e a r n i n go f c e n t r eo fs i n g l ec l a s s ，t h ee x t r a c t i o no f b i n a r yr e l a t i o n ，g a u s s i a nm i x t u r em o d e l ，l e a m i n go fq ap a t t e r n s ，l e a r n i n go f t e r m i n o l o g yp a a e m s 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得苤盗盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：药姥 一， 签字目期：2 一年岁月8 日 学位论文版权使用授权书 本学位论文作者完全了解苤鲞盘堂 有关保留、使用学位论文的规定。 特授权苤盗盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 劣走釜 一，导师硌研丞蘑 签字日期：如譬年，月p 日 签字日期：多年、月g 日 第一章绪论 1 1 研究背景和意义 第一章绪论 随着互联网的迅速发展，网页数量呈指数形式增加，其内容涵盖了政治、经 济、文化、娱乐等各个领域。在互联网上几乎可以获得任何领域的信息。因此， 如何从互联网中快速准确地寻找到所需的信息，成为迫切需要解决的问题。 按照研究的目的不同，在互联网信息处理中主要存在两大研究方向：一是信 息检索，二是信息抽取。 信息检索的目的是从大量的文本集合中找到与用户查询相关的文本列表，并 按照相关性降序排列，用户在返回结果中获取自己所需要的信息。 信息检索的主要难点是：对大量文本集合的快速搜索定位和对返回结果的排 序设计。从文献看，这方面的研究已经较为成熟。现有的主流搜索引擎，如g o o g l e 、 b a i d u 等都是信息检索技术成功应用的典范f 2 】。 但由于信息检索的返回结果是文本列表，而在文本中进行信息的获取还需用 户自行完成，这使得它并不能真正满足用户对信息的需求。 信息抽取研究的目的是：从文本中抽取出特定的信息。例如：由新闻文本中 抽取出恐怖事件的时间、地点、作案者、受害者、袭击目标、使用的武器等。在 许多应用中，不仅需要提取上述信息，还需确定这些信息之间的关系，与此对应 的研究被称为关系抽取【3 】。 美国国家标准技术研究院( n i s t ) 为自动信息抽取的评测定义了多种二元 关系，如：制造使用关系、类属关系、组织从属关系、局部整体关系、人物关系 等 3 - 4 。实际上，二元关系的种类远比上述定义的要多。 互联网上蕴含着大量的二元关系实例，这些实例能够成为人们知识的重要来 源，对自动问答、本体构建1 5 】等领域也起着重要的作用1 6 j 。例如：如果已经从文 本：“红楼梦的作者是曹雪芹 中，抽取出了 关系的实例 ，那么容易回答类似于“红楼梦的作者是谁”这样的问题。 早期的关系抽取通过人工制定规则来实现【7 】。人工制订规则所需的工作量太 大，且不利于规则的扩充和维护，因此，后来的研究都集中在如何利用机器学习 来改进关系抽取哺j 。 为实现关系的自动抽取，一个自然的思路是：把关系抽取问题转化为分类问 第一章绪论 题。例如：在抽取给定文本中的 关系时，可以先列出文本中所有可 能的二元对，然后通过分类器，判决它们是否属于 关系。 早期的研究重点是：利用传统的分类算法，例如s v m i 9 1 ，w i n n o w i o 等构造 二元关系实例的分类器。这些方法要求为二元关系实例构造出特征向量描述，以 适应分类算法的需要。因此，此类方法被称为基于特征向量的方法【1 1 i 。 在构建特征向量时，主要可利用两种特征：一是句法和语义特型1 2 j ；二是以 邻近词条及其次序作为特征】。与传统的分类学习相同，对特征向量的分类器- u j i 练需要人工标定大量语料。 在特征向量方法的基础上出现了基于核函数( k e r n e lf u n c t i o n ) 的学习算法，它 使用核函数来计算两个上下文的相似度，而不再使用特征向量的内积运算【l 引。因 此，它不需要为二元关系建立特征向量，而直接使用上下文的原始形式进行处理。 可选用的核函数有：潜在语义核函数 1 4 j 、主成分分析核函数、树核函数【j 6 】、 图核函数1 7 】、序列核【1 8 1 函数等。核函数方法的优点是能够利用上下文中的复杂 语义信息，以对支持核函数的分类器( 例如s v m ) 进行训练。其缺点是：需要 人工标定大量语料，并且训练分类器和实施分类时的计算量都较大，不适合处理 大型数据j 。 此外，还有一种基于模式的分类学习方法。一个良好定义的模式具有两个功 能：在分类时作为特征使用；在抽取关系时作为定位和抽取的方法使用。因此， 模式实际上可被认为是特征的扩展。由于模式具有上述特性，因此它实际上不仅 用来自动分类，而且还能用来自动抽取二元关系。这两者的结合产生了一种特殊 的学习方法： 先在人工标注少量的二元关系实例，然后训练初始分类器，以获得模式集及 评分；系统在大型的未标定语料集中自动抽取二元关系候选实例，并利用初始分 类器，对所有候选实例进行评分；然后挑选出高于规定阈值的候选实例，加入训 练集，重新训练，以获得更多的模式和改善模式评分。 文献 1 9 2 2 】利用上述方法进行二元关系抽取，其目的是：通过充分利用未标 定语料，减少对标定语料数量的需求。但上述文献均从直观经验出发制定模式评 分和候选选择的方法，未能对其学习机制进行深入探讨。 实际上，上述方法均是“s e l f - t r a i n i n g ”学习机制的具体实现。s e l f - t r a i n i n g l 2 纠 是新近出现的一种半监督学习机制，其核心思想是先利用少量的人工标定数据， 估计出系统初始的参数。系统在实际运行时，如果发现与标定数据相似度较高的 未标定数据，则将其作为“自动标定”数据加入) ) u u j l 练集中，重新训练，以改进 系统性能。 除被应用于二元关系抽取外，文献 2 3 2 4 应用s e l f - t r a i n i n g 来获取特定领域 第一章绪论 的词汇，文献 2 6 】应用s e l f - t r a i n i n g 来改进词义消歧，文献【2 7 】提出在对们隋绪化” 对话和“非情绪化”对话的分类学习中，利用s e l f - t r a i n i n g 来减少对标注集的依 赖，文献 2 8 】则应用s e l f - t r a i n i n g 来改进图像处理中的目标检测工作，实验表明： 该方法的性能与当前流行的学习方法相当。文献 2 9 】利用s e l f - t r a i n i n g 改进分词工 作。文献 3 0 1 提出了个基于s e l f - t r a i n i n g 的知识发现新方法。 1 2 研究主线 本文的主要研究目的是：为基于s e l f - t r a i n i n g 机制的二元关系抽取问题建立 统一的学习模型，分析其学习本质。为此，后文按如下主线进行展开： 在第二章，本文将对文献【1 9 2 4 1 进行详细分析，指出其学习目标实质是对单 类类文本中的词条分布的学习，然后介绍与之相关的单类分类学习领域的研究成 果，指出该问题的特殊性和复杂性。 第三章揭示了词条分布与单类文本中心之间的关系。指出：词条分布与单类 文本中心的学习存在同一性。由此，将学习目标转化为：在向量空间中对单类中 心进行学习。 第四章研究文本向量的分布特性。文中指出：混合高斯模型并不适合描述高 维的向量空间的数据分布，为此，基于k m e a n s 算法的潜在数据假设，本章提出 了一个新的数据模型：t g m k 模型，它在k m e a n s 算法划分的区域内，进行多个 截尾高斯分布的估计。本章揭示了t g m k 模型与k - m e a n s 算法、高斯混合模型 的密切联系。在文本数据上的实验结果表明：t g m k 模型适合描述多类文本数 据。 第五章将k - m e a n s 算法应用到单类中心的学习中，得到了s i n g l e m e a n 算法。 本章证明：当多类数据集适合被t g m k 的泛化模型1 t g m r 模型所描述时， 新算法从目标类的初始中心出发，将收敛至峡际中心。实验表明了新算法在文本 数据上的有效性。 第六章为基于互联网的二元关系抽取问题建立了形式化的学习模型，并使用 s i n g l e m e a n 算法，实现了一个基于s e l f - t r a i n i n g 技术的学习框架。文中讨论了实 施中的具体问题，并对评分方法和自动标定方法进行了修改。 第七章将上述学习模型应用到对问答模式的学习中。文中通过建立骨架序 列，改进了问答模式的定义；通过利用启发规则，改进了候选的评分公式。实验 表明：系统通过自动标定和重训练，确实能改进性能。对比评测表明了本文方法 的优越性。 第八章研究建立一个基于s e l f - t r a i n i n g 机制的中英文术语翻译系统。对比评 第一章绪论 测同样表明了本文方法的优越性。 第九章是总结和展望。 1 3 论文创新点 ( 1 ) 为克服高斯混合模型在描述具有硬聚类特性的数据分布时的缺点，本文 提出了基于k - m e a n s 划分的t g m k 模型，并揭示了t g m k 模型与k m e a n s 、高 斯混合模型的密切联系：本文在k m e a n s 算法基础上提出了s i n g l e m e a n 算法， 文中证明：当多类数据集适合被1 - t g m k 的泛化模型1 t g m r 模型所描述时， 新算法从初始中心出发，将收敛到实际中心；实验表明了新算法在文本数据上的 有效性，从而说明了s e l f - t r a i n i n g 机制在二元关系抽取中的有效性。 ( 2 ) 本文将在二元关系抽取中的模式学习问题转化为单类文本中心的学习问 题；为二元关系抽取工作建立了基于单类中心学习算法：s i n g l e m e a n 算法的形 式化学习模型：针对在互联网上进行二元关系抽取的特殊性，提出了新的候选评 分公式和自动标定方法。 ( 3 ) 本文将学习模型应用到中文问答模式学习和中英文术语对的抽取中。针 对具体问题，提出了新的模式定义，并利用启发规则，进一步改进候选评分公式。 实验表明：在获得极少量标注集的前提下，新系统在中文问答模式学习和术语抽 取中都取得良好的性能。 第二章文献综述与分析 第二章文献综述与分析 2 1 基于s e l f - t r a i n i n g 学习机制的信息抽取技术 2 1 1 文献概述 文献【1 9 】提出了名为d p r e 的系统，在互联网文本中抽取特定二元关系的模 式。例如：二元关系为 ，则可能的模式有：“ t i t l e b y a u t h o r ”和“a u t h o rl | t i t l e 等。具体方法是： ( 1 ) 初始训练集：人工给定关系实例，组成训练集。例如给定 的关系实例： ； ( 2 ) i ) 1 i 练过程：在互联网上搜索，找出包含训练集中关系实例的上下文片段， 根据模式定义获取模型，并加入到模式库中； ( 3 ) 数据获取和重训练：利用已获取到的模式，在互联网上搜索，抽取出二 元关系候选实例，由人工选择正确的实例加入至u - i ) 1 练集中，然后按步骤( 2 ) 重新 训练。 模式定义：模式是一个5 元组： ，其中： o r d e r 表示在模式中t i t l e 与a u t h o r 的前后次序； u r l 表示文本获得的地址； p r e f i x 表示在上下文片段中位于t i t l e ( 或a u t h o r ) 之前的m 个词条( 实际应 用中，m 被设为1 0 ) ； m i d d l e 表示位于t i t l e 和a u t h o r 之间的词条； s u f f i x 表示位于位于t i t l e ( 或a u t h o r ) 之后的m 个词条。 模式p 的可信度计算： c d 矿( 力= 可= = ：= n p i o s t 瓦t i v e = 公式( 2 1 ) 对公式( 2 1 ) 的计算：在利用模式在互联网上抽取新的候选实例时，有一些候 选在训练集中已经出现过，其数目记为n p o s 帆，而对。删，。的计算，则需要在实 际运行中通过用户来确认来进行。 第二章文献综述与分析 文献 2 0 提出名为s n o w b a l l 系统，试图挖掘英语文本中 的关系 实例，例如：“m i c r o s o f t ，r e d m o n d 、“i n t e l ，s a n t ac l a r a 等， 它们可以用模式：“o r g a n i z a t i o n ，l o c a t i o n ”来表示。s n o w b a l l 系统的任务是尽可 能多地找出这样的实例，其方法是： ( 1 ) 初始训练集：人工给定关系实例，组成训练集。例如给定“m i c r o s o f t ， r e d m o n d 作为关系实例； ( 2 ) i l l l 练过程：对每个目标文本，检查是否包含数据对。如果包含，则根据 模式定义，从文本中获取模式，加入模式库； ( 3 ) 数据获取和重训练：利用模式库中的模式，采用实体识别技术，在目标 文本中搜索；将与模式同现的组织实体和地名实体抽取出来，作为候选实例；按 照评估标准，选择评分高于阈值的实例，加入训练集；按步骤( 2 ) 重新训练。 模式定义：一个s n o w b a l l 模式是一个5 元组： ， 其中： t a gl 和t a 9 2 分别是l o c a t i o n 、o r g a n i z a t i o n ，或者是o r g a n i z a t i o n 、 l o c a t i o n ； l e f t 、m i d d l e 、r i g h t 均是向量： 的集合。 一个s n o w b a l l 模式实例： ，权值是通过统计对应词条在上下文片段中的出现频率并 通过归一化处理后得到。 。模式p 的可信度计算： r n f ( p ) 2 瓦j i v p o 瓦s f f l v e = 公式( 2 - 2 ) 其中， r m 。的定义与公式( 2 - 1 ) 相同，但哗。不再寻求人工确定，而 采用如下规则：当利用模式p 获取候选实例时，若获得的候选实例与训练集中某 候选实例的一元相同，而另一元不同，则记其数量为啤一。 例如：设训练集中已经有“m i c r o s o f t ，r e d m o n d ”实例，而新获取的一个候 选实例是：“m i c r o s o f t ，n e w y o r k ”，则认为后者是错误的实例。上述判断显然是 基于一个强假设：二元关系中的两元是一一对应的。该假设在实际应用中并不一 定成立。 候选丁的可信度计算： c o n f ( t ) = 1 - 兀( 1 一c o n f ( p , ) 搴m a t c h ( c j ，只) ) 公式( 2 3 ) 第二章文献综述与分析 其中，e 为通过模式只获取到候选丁时的上下文片段，m a t c h ( c , ，b ) 计算c 与只的匹配程度。 文献【2 l 】将【2 0 】的工作，泛化到了一般性的二元关系抽取上，其中，沿用了 文献 2 0 中的评分方法和候选可信度计算方法，也并未对学习机制作出严格的形 式化。 文献 2 2 抽取 的二元关系，采用了与文献 2 0 】相同的模式评分 方法和候选评分方法。 此外，有不少文献利用s e l f - t r a i n i n g 的方法来进行特定类别词条的抽取，例如 文献 2 3 2 4 。由于其中的方法也适合于二元关系的抽取，因此，本文也做一介绍。 文献 2 3 】的目标是：抽取属于某个特定类别的专有词汇。例如：恐怖组织名 称、公司名称等。具体方法是： ( 1 ) 初始- i ) l i 练集：人工给定词汇实例作为训练集，例如给定某个公司名称： “m i c r o s o f t ”： ( 2 ) 0 1 l 练过程：在语料库中搜索，找出包含训练集中词汇的上下文片段，根 据模式定义进行模式获取，对模式评分后，选出评分最高的模式p 胁； ( 3 ) 数据获取和重训练：利用模式：p 胁，在语料库中搜索，抽取出候选词汇； 对所有候选进行评分，选取评分最高的候选，加入训练集：按步骤( 2 ) 重新训练。 模式p 的评分： 州加争g f 当用候选p 获取到若干候选时，m 为这些候选的数目， 出现在训练集中，则f 记录这部分候选的数目。 候选丁的评分： s c o r e ( t ) = 1 + ( o 0 1 木s c o r e ( p k ) ) 公式( 2 4 ) 若其中有部分候选 其中，是某个候选的上下文片段集中所对应的模式总数。 公式( 2 5 ) 文献【2 4 提出一个名为：b a s i l i s k 的系统，其目标与文献 2 3 】相同，只在学习 流程的两处细节、候选评分上有所不同： 学习流程上的不同： ( 1 ) 每次抽取评分排在前2 0 的模式，进行候选抽取； 第二章文献综述与分析 ( 2 ) 每次挑选评分排在前5 的候选，加入到训练集中重新训练。 候选丁的评分： s c o r e ( t ) ：迦 公式( 2 - 6 ) = 苎! 西风k 二。o ， p i 其中：尸是已学习到的模式集，ip l 是模式的数量，f ( p ，) 是在利用只抽取r 的同时，抽取到的已存在于训练集中候选的数量。 注意到文献 2 3 - 2 4 d ? 对模式和候选进行“评分”，在意义上与文献 1 9 2 2 】中 的“可信度计算”一致。后文为行文上的方便，将主要采用“评分”的表达。 2 1 2 文献分析 由于初始标注集很小，以及能从未标注集中获取的确定性信息有限等原因， 以上文献都试图利用各种启发信息，来改善对模式和候选的评分。下文从三个方 面对文献进行分析和总结。 一、对模式评分的分析 在模式的评分方法中，文献 2 3 2 4 仅用正例信息来对候选进行评分。 文献i 1 9 - 2 2 尝试利用正例和反例来对候选进行评分，其中，对反例的认定有 两种方法： ( 1 ) 文献 19 】通过人工指定来计算； ( 2 ) 文献 2 0 2 2 1 认为：当利用模式获取到新候选实例时，如果新候选的一元 与标注集中某候选的一元相同，而另一元不同，则该新候选被认定为反例。 方法( 1 ) 中存在的问题是完全依赖于人； 方法( 2 ) 中存在的问题是： ( a ) - - 元关系中，两元之间实际上不必是一一对应的。比如在 的二元关系中，一个机构的地址可以存在多种写法。例如： 是一个正确的 关系，而 也是一个正 确的 关系。 ( b ) 假定方法( 2 ) 对反例的认定是正确的，以下将从分类的角度，分析公式 ( 2 1 ) 的实质。为此，先按照分类的术语，做如下定义： c i ：待抽取的二元关系，将其视为一个类； c f ：c l 之外的所有数据的混合类； p j ：用来抽取二元关系候选实例的模式； 第二章文献综述与分析 吲，b ：二元关系向量。 对公式( 2 1 ) 的计算遵从以下假定：标定语料集中的二元关系实例为正例， 而与之一元相同、另一元不同的二元关系实例为反例。 不妨假设标定语料集中只有一个实例，设为： ，而由b 获取到多个 二元关系候选，其中有个候选是 ，有个候选满足：在某一元上与 q ，8 相同，而在另元上则不同。为简化问题，可假定：这n ，个候选的第一 元都是4 ，而第二元都不是e 。 此时，对p j 关于g 的后验概率估计是： 尸( c 1 p ) ：一! ! 刍：旦 ! ! 刍：旦：丝垒立 、“ j p ( c 1 ，只) + 尸( c l ，p i )e ( c i ，p i ，a = 4 ) + 尸( c 1 ，b ，a = a 1 ) p ( b = 墨，p ，a = a 1 )r l l p ( b = 蜀，b ，a = a n ) p ( b 且，髟，a = 4 )碍+ n 2 不难看出，公式( 2 1 ) 便是对p ( c 1p ，) 的估计。 考虑待抽取的二元关系是 ，设机构名称为“m i c r o s o f t ”，模式 为半角的逗号。显然，当语料集较大时，文本中将存在很多的“m i c r o s o f t ， r e d m a n d ，但同时也存在大量的“m i c r o s o f t ，其中，省略号处的文本不是 “r e d m a n d ”o 重新考察对c 的定义。前文把c 之外的所有数据统一称为c 。类，这必然导 致它的构成极其复杂。因此，在其基础上定义p ( c lp ) 并不具有明确的意义，对 p ( c lp ，) 的估计也将是不稳定的。 问题的根源在于：对尸( c 1i 刃) 的计算涉及到了对一个具有未知特性的数据集 的估计。2 3 节将进行进一步分析。 注意到：二元关系具有很强的语义特性。因此，模式在二元关系类的内部将 存在稳定的分布，对p ( p ，lc 1 ) 的估计是可行的学习目标。 直观上，如果有足够多的人工标定语料，那么容易估计出尸( 只ic 1 ) 。但考虑 到互联网上有大量的未标定语料，如果存在一个可靠的候选评分方法，即可自动 挑选出正确候选，来提高对模式分布的估计。 二、对候选评分方法的分析 文献【1 9 - 2 4 存在多种候选评分方法，但其基本思路都相同：当候选的上下文 中出现的模式的数量和种类越多，那么候选越可靠。 模式的获取和评分来自于对标定语料的上下文的学习。如果用已经学习到的 模式来评价标定语料，那么在标定语料的上下文中，这些模式出现的数量和种类 第二章文献综述与分析 将很多。 因此，评分方法的本质是：寻找在模式出现的数量和种类上的表现与标定语 料相似的候选，以作为可靠的候选。 但上述文献均未回答：自动标定的候选是否一定能够改进系统的性能? 如果学习目标确定为：学 - - j 尸( 只lc 1 ) ，那么问题变为：自动标定的候选一定 能够帮助改进对尸( 肼ic 1 ) 的估计吗? 有人也许会认为：样本数量越大，那么对p ( p ，fg ) 的估计就应该越好。但这 是有前提的。在前文实际已经提到：如果有足够多的人工标注语料，对p ( p ，lc 1 ) 的估计将非常好。但需注意：标定语料必须是人工语料，而非程序自动标注的语 料。两者的区别在于： ( 1 ) 人工标定语料集中将存在一些“看起来”并不怎么相似的语料，这使得 语料对尸( p 。ic 1 ) 的估计将能适合实际的数据分布； ( 2 ) 自动标注语料只能挑选那些与标定语料相似的候选。这好比在标定语料 周围画了一个圆形邻域，落入其中的候选才能被认为是可靠的。那么，使用这一 个邻域中的点，是否一定会改善对p ( p ，ic 1 ) 的估计? 要解决该问题，必须在距离 空间中研究相邻候选的模式分布情况，这有待于在下文中进行深入分析。 三、学习流程 文献 1 9 2 4 1 都是采用以下学习流程： ， ， ，哦牟。， 初始训 。= 箸f f 获取模式 i 练集r 并评分 ? f 一 fi jl 1 r i 选择可靠候选 i 候选评分 | i 获取新的候选 图2 1 基于s e l f - t r a i n i n g 的学习流程图 2 1 3 本文要解决的几个基本问题 综合上述分析，本文对指定的二元关系类，研究如何在给定少量标注语料的 基础上，获得对模式在类内分布的可靠估计。需要解决的问题是： ( 1 ) 研究不使用c l 类信息的模式评分方法： 第二章文献综述与分析 ( 2 ) 研究基于( 1 ) 的候选评分方法； ( 3 ) 研究为何扩大人工标定语料集能改进对模式分布的估计； ( 4 ) 研究自动标定数据是否能改进对模式分布的估计； ( 5 ) 基于图2 1 所示的学习流程，建立形式化的学习模型。 评注： 机器学习理论关注：是否能够通过学习来改进系统性能1 3 。 从文献分析可知：以往的相关研究停留在利用些启发性规则来改进实验效 果的基础上，所得到的方法虽然在实际应用中有效，但并未给出理论上的解释。 本文的研究目标是：揭示出基于s e l f - t r a i n i n g 机制的二元关系抽取问题的机 器学习本质。其中的重点问题是( 3 ) 和( 4 ) 。 从直觉上看，在二元关系抽取问题中，( 3 ) 和( 4 ) 都是能够成立的，因此，才 能由此发展出在实践中有效的一系列方法。也正因为此，对( 3 ) 和( 4 ) 给出明确回 答，才显得更加必要。 在开始本文的研究以前，有必要对问题做一些简化，并对问题进行统一描述。 下一节将从文本分类的角度，对问题进行描述。 2 2 二元关系抽取问题在文本分类角度下的描述 绪论中提及：模式实际有两个作用： ( 1 ) 在获取候选时，作为定位和抽取的方法使用。 ( 2 ) 在对候选评分时，作为特征使用。 对模式的定位和抽取作用，本文暂不研究。利用模式特征对候选进行评分， 实际潜藏以下假设： 一 ( 1 ) 各模式的出现是相互独立的； ( 2 ) 利用标定的二元关系实例去获取对应的上下文片段集，若某模式在其中 出现的频度越大，那么该模式越可靠。 不妨把一个二元关系实例所对应的上下文片段集视为一个文本，那么给定一 个二元关系实例集，它们各自对应的文本将组成一个文本集。 按照文本分类的术语，把一个二元关系集所产生文本集称为文本类，模式被 称为词条( 或特征) 。 因此，一个候选被称为是属于指定的二元关系，当且仅当它对应的文本属于 指定的二元关系所对应的文本类。 这样，候选的可靠性评价问题，转化为了对它所对应文本是否属于特定文本 类的判定。为简化起见，以下将指定的二元关系称为目标二元关系，将其对应的 第二章文献综述与分析 文本类称为目标文本类。 图2 - 2 描述了上述对应关系。 图2 2 目标二元关系与目标文本类 2 1 2 节提出：在目标二元关系中，学习目标是获得对模式分布的稳定估计。 从文本分类的角度，该学习目标可解释为：获得词条在目标文本类中的分布。 为研究自动标定数据对学习目标的改进作用，必须在距离空间中研究邻近候 选的模式分布情况，换言之，必须在距离空间中研究相邻文本的词条分布情况。 已有基于距离的聚类研究中，涉及到了对词条分布情况的研究。 k - m e a n s 是一个利用数据积聚特性来进行聚类的算法，它在文本聚类上有广 泛的应用。从直观上看，数据积聚的特性使得在一个球形区域内，离聚类中心更 近一侧的数据密度比离聚类中心更远一侧的数据密度更大，这将有利于进行单类 中心的学习。 为此，在第三章将分析词条分布与k - m e a n s 的中心之间的关系，证明两者之 间存在的同一性。由此，将词条分布问题转化为对目标类文本中心的学习问题。 注意到：把模式视为文本中的词条，实质上是对文献 1 9 2 4 】中定义的复杂模 式的简化。文献中的模式定义，利用了具体问题上的启发信息，对特定问题的解 决是有效的，但对于建立一般性的学习过程并非必要。 后文在进行问答系统和术语翻译系统的设计时，也将针对具体问题，定义合 适的模式。 第二章文献综述与分析 2 3 与两类分类问题的区别 在传统的两类分类问题中，数据被认为属于两类之一。因此，其中的一类可 被看作另一类的反例集。但在二元关系抽取中，我们对目标二元关系外的数据分 布情形缺乏了解。例如：我们无法回答：除目标二元语义类外，还有多少其它二 元语义类? 它们的模式集是什么? 这导致了我们无法对获得充分的反例集。 但出于简便性，不少文献( 如文献【1 9 2 2 】) ，简单地把目标类之外的其它数 据归为一类。这样做的一个好处是：可以利用已有的两类分类方法来进行分类决 策。 文献 3 2 3 3 等也采用了上述分类方法。它们把目标类外的数据称为“异常” ( o u t l i e r ) 类，然后使用普通的分类器来进行分类。但文献 3 4 指出：上述方法有效 的前提是：能获得一个与目标类的数据邻近的“异常”类数据集，以学习出一个 目标类数据和“异常 类数据之间的边界。 但一般