（计算机软件与理论专业论文）基于核函数的中文实体关系抽取新方法.pdf

摘要 实体关系抽取是在自然语言文本中识别实体之间语义关系的任务。 本文首先提出了一套新颖的基于复合型核函数的中文实体关系抽取方法，它 定义在两个独立的核函数基础上，其中一个核函数称为实体核函数，它的关注点 是与实体相关特征的相似度，而另一个核函数称为字符串语义相似度核函数，主 要关注点是表述上下文文本相关特征的相似度。在此基础上分别引入三种组合方 式，分别是线性复合型核函数、半二次复合型核函数和二次复合型核函数，它们 能够更加全面地体现两个关系实例之间的相似度。 在许多已经成功应用于关系抽取的特征之中，位置特征( 如包含、相邻和分 离等) 是最为重要的特征之一。为了能够提供更为丰富的位置结构信息，本文提 出了实体形态树的关系实例表示方法，用以刻画实体之间的位置关系。实体形态 树同时还可以揭示各类实体在关系抽取任务中所扮演的角色。利用这样的树形表 示，本文提出了基于实体形态树核函数的中文关系抽取方法。 在a c e2 0 0 5 数据集上的评测结果，验证了基于核函数的中文实体关系抽取 新方法的有效性和实用性。 关键词：基于核函数的中文实体关系抽取字符串语义相似度核函数复台型 核函数实体形态树 a b s t r a c t e n t i t yr e l a t i o ne x t r a c t i o ni sat a s ko fi d e n t i f y i n gs e m a n t i cr e l a t i o n sb e t w e e n t w o e n t i t i e sf r o mt h et e x t i nt h i sp a p e r , w ep r o p o s ean o v e lc o m p o s i t ek e r n e lf o rc h i n e s er e l a t i o ne x l r a c t l o n t h ec o m p o s i t ek e r n e li sd e f m e da st h ec o m b i n a t i o no ft w oi n d e p e n d e n tk e r n e l s o n e i st h ee n t i t yk e r n e lb u i l tu p o nt h en o n c o n t e n t r e l a t e df e a t u r e s t h eo t h e ri st h es t r i n g s e m a n t i cs i m i l a r i t yk e r n e lc o n c e r n i n gt h ec o n t e n ti n f o r m a t i o n t h r e ec o m b i n a t i o n s ， n a m e l y l i n e a r c o m b i n a t i o n ，s e m i - p o l y n o m i a l c o m b i n a t i o na n d p o l y n o m i a l c o m b i n a t i o na r ei n v e s t i g a t e d a m o n gm a n ys u c c e s s f u l l yu s e de x t r a c t i o nf e a t u r e s p o s i t i o ns t r u c t u r e ( s u c ha s n e s t e d a d j a c c n ta n ds e p a r a t e d ) i st h eo n e m u s tn o tb eo v e r l o o k e d h e r ew ep r o p o s e a ne n t i t ym o r p h o l o g i c a lt r e er e p r e s e n t a t i o n ，w h i c hi sc a p a b l eo fo f f e r i n gm u c hr i c h e r 咖d 眦a li n f o r m a t i o nt oc h a r a c t e r i z et h ep o s i t i o n a lr e l a t i o n s h i p sa m o n ge n t i t i e sa n d m e a n w h i l ep r o v i d e sam e a n st or e v e a lt h er o l eo fc o n t e x t u a le n t i t i e s i nr e l a t i o n e x t r a c t i o n b a s e du p o nt h i sr e p r e s e n t a t i o n , w ed e v e l o p at r e ek e r n e lb a s e da p p r o a c ht o c h i n e s er e l a t i o ne x t r a c t i o n e v a l u a t i o nr e s u l t so nt h ea c e2 0 0 5d a t as e t sa r ep r o m i s i n ga n dd e m o n s t r a t et h e e f f e c t i v e n e s sa n da p p l i c a b i l i t yo ft h ep r o p o s e da p p r o a c h e s k e yw o r d s ：k e r n e l b a s e dc h i n e s er e l a t i o ne x t r a c t i o n ，s t r i n g s e m a n t i c s i m i l a r i t yk e r n e l ，c o m p o s i t ek e r n e l ，e n t i t ym o r p h o l o g i c a lt r e e 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发巷 或撰写过的研究成果，也不包含为获得墨鲞苤鲎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：鬻鸡 签字日期： 7 年6 月7 日 学位论文版权使用授权书 本学位论文作者完全了解：叁鲞盘鲎有关保留、使用学位论文的规定。 特授权丕鲞盘鲎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：致寺襄 导师签名：腰巡 签字日期：幻呷年6 月 ，日 签字日期：2 0 0 尹年6 月 7 目 第一章背景和现状 第一章背景和现状 1 1 中文命名实体关系抽取简介 虽然因特网上的搜索引擎可以让人们更轻易地获取更多的信息，但它们并不 能回答复杂的查询，例如“列出合并过的公司列表”等等。为了回答这种类型的 查询，找出与查询语句最相关的结果，我们需要对待查询文档进行足够的分析， 抽取出更多的语义信息。如刚才的查询，包含有“公司甲与公司乙合并”语句 的文档就可以被自动地查找出来。这方面的工作不仅在信息检索方面十分有用， 对于问题自动回答和摘要自动生成等研究领域也很有意义。 关系抽取的研究目标是检测一篇普通的文档中，是否在一些命名实体之间存 在着语义上的关系。例如文档中包含这样一段话：“很多巴基斯坦人聚集在广场 上”，其中就存在着类别为p e r s o n ( 人) 的实体“很多巴基斯坦人”和一个类别 为a r e a ( 区域) 的实体“广场”，而在这两个实体之间显然存在着l o c a t e d ( 位 于) 关系。实体间的关系抽取在网页文本、生物文献等领域的信息检索方面也有 重要的应用。 1 1 1 推动组织 关于命名实体关系抽取的相关研究，是在信息理解会议( m u c s ) ( m u c ， 1 9 8 7 1 9 9 8 ) 1 和自动内容抽取项目( a u t o m a t i cc o n t e n te x t r a c t i o n ，简称a c e ， 2 0 0 2 2 0 0 7 ) 2 的促进下开展的。 a c e 项目的目标是开发新的信息抽取技术来自动化地处理自然语言数据，例 如通常情况下的未经信息化加工的自然文本。这其中包含基于未加工的自然语言 上的文本分类、过滤和选取等，要完成这些任务，需要开发出能自动而精准地抽 取出自然语言文本所含有的语义信息的技术。所以a c e 项目所研究的目标也被 看成是开发例如命名实体、实体关系和事件等语义元素的抽取技术。 1 1 2 命名实体关系抽取定义 按照a c e 项目的定义，“命名实体”是可以对应于现实世界中的一个对象或 对象集合，每个命名实体都有若干个“实体提及”( e n t i t ym e n t i o n ) ，每个实体提 及都是对实体的一次不同的提及或引用，同一个实体( 对象) 在文本中的每一次 第一章背景和现状 出现都对应于一个不同的实体提及。例如一个指代某个现实对象的实体，在文章 中可能会以名称的简称形式出现，也可能会以它的全称形式出现，或者可能以代 词的形式出现。每次出现都是一个不同的实体提及，在以后的描述中，在不出现 歧义的情况下，“实体”这个概念实质上是指实体提及。 在a c e 项目的定义下，每个实体都有且只有一个实体类别和一个隶属于这 个实体类别之下的实体子类别。当然，在自然语言文本中实体是以词语或词组的 语言形式出现的，所以实体还拥有各自的出现范围。在a c e 项目的定义下，实 体有两种出现范围，分别是外延范围和首部范围。实体外延范围是实体的整个出 现范围，通常包含了所有为了修饰中心词用到的修饰词和修饰短语。而首部范围 则只是实体的出现范围里最重要的中心词或中心短语的范围。a c e 项目对于实 体还定义了一些例如提及类别等概念，由于对实体关系抽取任务作用很小，这里 不作详述。 实体间的关系是a c e 项目的另一个重要概念，是指建立在两个不同实体之 间的明显的、直接的语义联系，这两个实体被称为实体关系的两个参与实体。与 实体的定义类似，每个实体关系也有且仅有一个关系类别和一个隶属于这个关系 类别下的关系子类别：为了方便叙述，如果两个实体之间并没有直接的语义联系， 则称它们之间的关系是“负关系”；反之，则称这个实体对具有“正关系”。 例如在文本“比尔盖茨是微软公司的首席执行官和首席软件架构师”中就出 现了若干个a c e 项目定义下的实体。以“微软公司”这个词组所表示的实体为 例，它本身就是实体的外延范围，中心词“公司”是这个实体的首部范围，实体 类别是o r g a n i z a t i o n ( 组织) ，实体子类别是c o m m e r c i a l ( 商业) 。从这段文本中， 可以抽取出实体“比尔盖茨”和“微软公司”之间的正关系，因为它们之间拥有 直接的语义联系，具体而言就是比尔盖茨和微软公司之间有被雇佣的关系，所以 它们间的关系类别是o r g a f f i l i a t i o n ( 组织归属) 而关系子类别是e m p l o y m e n t ( 雇佣) 。显然，这个关系的两个参与实体就是“比尔盖茨”和“微软公司”所 代表的这两个实体。 1 2 实体关系抽取现状 1 2 1 已有的研究 实体关系抽取任务最开始是在m u c 里的模版关系中介绍和规范的，然后在 a c e 项目的关系检测与表述( r d c ) 任务中进一步得到促进。关于关系抽取这个领 域，已经有很多文献中提出了很多方法，进行不同程度的解决。在这些方法之中， 第一章背景和现状 一般都将关系抽取的原问题转化为普通的空间样本点分类问题，其中又以基于特 征的分类方法和基于核函数的分类方法最为常见和流行。 基于特征的分类方法使用一系列精心挑选的特征来表示每一个样本点，这些 特征需要反映样本点的足够的信息，有的时候选取文本中的例如动词名词等的词 性标注作为特征，这些词性标注可以来自于不同层次的词法和语法解析。有的时 候特征来自于更为复杂的依赖树，而且需要全方位的语法解析。k a m b h a t l a 3 在 2 0 0 4 年的工作引入了最大熵模型，这个模型合并了文章的词法、语法和语义等 方面的不同特征，具体包括词语文本、实体类别、实体提及类别、依赖树和文法 解析树等等。在他的工作基础之上，z h o u 等人 4 】在2 0 0 5 年更深入地进行了研究， 他们融合了基本的文法分块( c h u n k i n g ) 信息、半自动地收集到的名称列表和人 名相关的词汇列表等特征，最后利用支持向量机作为分类器进行分类解决。另外， 他们还系统地开展了一系列详尽的实验来考察不同的独立特征及它们的组合对 于整个任务的贡献，最后他们的结论是文法分块信息对整个结果的改进起了最大 的作用。同年，z h a o 和g r i s h m a n 5 】的研究也扩展出大量可能有潜在作用的特征。 然后j i a n g 和z h a i 6 在2 0 0 7 年的研究中，系统地探究了大量的特征空间，并且 评价了不同的对应于词法解析树和依赖树的特征子空间。他们的实验结论指出只 采用基本的特征子空间就足够可以达到最好的实验结果，而过度使用一些看起来 复杂的特征反而会使实验结果下降。 另一方面，基于核函数的分类方法则希望将关系实例进行的结构化的表示， 在这个基础上设计一套精密的核函数来得到关系实例之间的相似度。z e l e n k o 等 人 7 在2 0 0 3 年的工作中提出了建立在两个文法解析树之间的核函数，核函数的 计算方法是递归地从根节点到叶子节点进行自上而下的匹配。 c u l o t t a 和 s o r e n s e n 8 在2 0 0 4 年扩展了这个工作，他们提出的计算树之间的相似度的方法 建立于依赖树的基础上，并且对于依赖树的每个节点使用例如词性标注、 w o r d n e t 同义词网络 9 等特征进行增强。而b u n e s c u 和m o o n e y 1 0 在2 0 0 5 年的 研究进一步改进了上面的两个工作。 他们提出的观点认为关于实体关系抽取的 必要的信息都可以通过分析参与实体在依赖树中对应的节点在树中的最短路径 来得到。他们提出了另一种完全不同的核函数的计算方法，具体是在最短路径长 度相同的限制下，对同样的路径特征进行计数。而如果两个关系实例所对应的最 短路径长度不相同，则简单地设定他们之间的核函数为0 。这三个核函数的共同 特点是都需要树的整体结构完全一样并且树中对应节点的特征必须完全匹配，由 于这两个条件十分严格，因此他们的实验结果在具有很高的准确度的同时召回率 并不十分理想。其后，z h a n g 等人 1 1 在2 0 0 6 年发展出可以将实体核函数合并到 语法分析树卷积核函数的复合核函数。z h o u 等人【1 2 】在2 0 0 7 的研究中，对于上 第一章背景和现状 下文相关核函数做了大量检验的实验，并且提出了一套可以合并实体核函数和最 优化的线性核函数的复合型核函数，既整合进了简单结构所携带的信息，又整合 进了复杂结构的信息。在a c er d c 数据集上的实验也证明了这样的复合型函数 要好于单纯的线性核函数和树核函数。他们也由此得出结论，认为复合型核函数 能够很好地整合简单结构的信息和复杂结构的信息，所以性能十分令人满意。 1 2 2 中文的实体关系抽取现状 相对于以英文为代表的西方语言在实体关系抽取方面取得的重要进展，对于 中文语料的实体关系抽取的相关研究及成果却十分有限。其中一个很重要的原因 是中文固有的语言特点导致中文的处理和信息抽取相对较为困难。例如中文的词 语之间没有像英文的空格那样明显的分隔，中文也缺乏词形变化等等 1 3 1 。现有 的例如中文分词技术这样的自然语言处理基础技术都还并没有达到令人足够满 意的程度，更不用说性能极差的中文文法解析技术和各种树模型的建模工具。这 也是为什么以前的复杂模型的研究工作都是基于英文语料的原因，并且其中大部 分的解决方法也并不适合在现阶段用于中文的关系抽取。h u a n g 等人 1 4 研究结 果也显示出这一点，他们在a c e2 0 0 7 的中文语料上用简单的基于特征的方法就 达到了6 3 的f m e a s u r e ，但是建立在现有的中文文法分析工具基础上的基于核 函数方法却只得到了令人失望的3 7 的f m e a s u r e 。另外c h e 等人1 1 5 针对中文 实体关系抽取提出过基于改进的编辑距离核函数方法，但他们的研究仅限于 p e r s o n a f f i l i a t i o n 这个实体关系类别。对中文实体关系抽取研究的不足，使得寻 找出适合中文特点的实体关系抽取方法显得至关重要。 1 3 论文结构 依据本论文的研究内容和相关知识的结构性，论文结构如下： 第一章介绍课题的研究背景、目的和意义，综述了实体关系抽取技术在互联 网的应用。 第二章阐述了实体关系抽取中的基础理论知识。 第三章说明了实体关系抽取的具体算法及实现细节。 第四章阐述了实体关系抽取的具体实验设置和实验结果，并在实验结果基础 上得出相应的结论。 第五章总结了本篇论文中提到的研究工作，并且对未来研究工作的方向提出 了建议和展望。 第二章理论基础 2 1 依赖树相关理论 第二章理论基础 弟一早埋记壑们击 为了更好地分析句子的各个基本语法单元之间的相互关系，可以从句子中构 造出一种被称为依赖树的树形结构，用以描述各个语法单元内部和语法单元之间 所包含的语法关系。依赖树中的语法组件之间的顺序信息没有得到保留，所以依 赖树比句法解析树的抽象层次更高一些【1 6 】。但从信息处理的角度看，依赖树却 可以更清楚地表示句问的依赖关系。下图展示了对于句子“闯入贝尔格勒国会大 厦”所生成的依赖树。图中每个方框代表句子的一个语法单元，节点的第一个标 签代表依赖关系，其它的词性标注、词汇登记项( 1 e x i c a le n t r y ) 和串的顺序位置也 可以在每个叶子节点中得到体现。 闯 贝尔格勒国会大厦 图2 1 依赖树结构 把自然语言处理问题中的句子表示成依赖树的最主要的优点，是依赖树的结 构是独立于特定的研究理论的，也就是说对于各种基于语法关系信息的领域，依 赖树都可以作为文本解析的基础工具发挥重要作用。此外依赖树的解析工具比较 多，输出格式也与其他树形解析工具相似。 2 2 中文分词 词是自然语言中最小的有意义的构成单位。由于中文的书写习惯，句子中的 词与词之间的边界标志是隐含的，对于大多数中文的自然语言处理算法，首先就 需要识别这些隐含的词语边界，即添加明显词语边界标志，使得所形成的词串能 更好地反映句子的语义，这个过程就是分词 1 7 。 第二章理论基础 分词问题是中文自然语言处理的一个古老课题，相关的研究始于2 0 世纪8 0 年代初，研究出了很多各具特色的方法，从简单的模式匹配、基于规则的方法到 基于统计的方法。虽然这些方法大大推动了中文分词研究的发展，但在实际应用 中仍然存在词语定义模糊、构词模式自由、词典覆盖能力有限，以及中文语料库 资源缺乏等诸多制约因素。 在处理大规模的自然语言文本时，中文分词系统还面临着以下困难：首先是 很难识别未登录词。由于不存在绝对完备的词典，虽然一般的词典都能覆盖大多 数词语，但依然有相当一部分的词语不可能穷尽地收入到系统词典中，这些词语 称为未登录词或新词。多数情况下，中文人名、地名、机构名称和外国译名等都 容易成为未登录词。其次，如何廉价高效地获取分词规则是构建中文分词系统的 不可忽视的问题之一。人工加工大规模的分词语料是耗费很大的工作，而且每个 汉字对之间都可能是一个词语边界，目前还没有适用于分词的完全有效的非监督 学习模型。另外，中文词语边界歧义问题也是分词问题尚待解决的难题之一。有 的分词歧义问题的解决必须要依赖词语所处的上下文环境，这就需要借助于更深 层的语义分析的结果。 近年来由于中文搜索引擎的快速发展，中文分词技术也受到了更多的关注。 现有的开源中文分词工具有中科院的i c t c l a s 1 8 1 等等 2 3 支持向量机理论 2 3 1 支持向量机分类原理 数据分类是机器学习领域的一个基本问题。假设已经给出了一些数据点和两 个不同类别，并且已经标识了每个数据点都属于这两类之中的哪一类，这时需要 知道对于新引入的数据点，它应该被标记为哪一个类别。这就是监督式学习所研 究的主要问题，而支持向量机( s u p p o r tv e c t o rm a c h i n e ，简称s v m ) ，就是一种典 型的监督式学习的方法 1 9 1 。它被广泛地应用于分类和回归问题的求解过程，并 且性能十分出众。 支持向量机一般会把输入数据看成多维空间中的两个向量集合，然后支持向 量机会构造一个用于分隔这两个向量集合的空间中的超平面，使得这两个数据集 合之间的间隔( m a r g i n ) 可以最大化。为了计算出这个需要的间隔的数值，两个超 平面被构造了出来，原来的分隔超平面的每一边各有一个恰好位于两个数据集合 的上下界的超平面。直观上看，最好的分隔平面离两个不同分类的最近数据点的 距离应该是最大的，因为一般来说两个分类之间的间隔如果越大，那么分类器的 第二章理论基础 泛化误差( g e n e r a l i z a t i o ne r r o r ) 就会越小。 假设支持向量机中的每个数据点都被看成是一个p 维向量，而希望知道这些 点是否可以用一个p 1 维的超平面来分开这些点，使得超平面的每一侧都只有一 个类型的数据点，这被称为线性分类器。事实上在这个p 维空间中可能存在很多 个可以分开不同类型的数据点的超平面，于是可以更进一步找出其中的可以使不 同类别的数据点分隔得最远的那个分割平面。根据这个想法选择使得从分隔平面 到最近的数据点的距离最大的超平面。 这就是最初提出的也是最简单的支持向量机模型，它也被称为最大间隔分类 器。它在特征空间中的数据是线性可分的前提下工作，所以并不能被直接应用于 解决大多数真实世界所碰到的问题。尽管如此它依然是最容易理解的算法，也是 其它更为复杂的支持向量机算法的最重要的基础，它展示了这类学习模型的最关 键的特征 2 0 】。 2 3 2 分类器的形式化 最大间隔分类器的分类策略是通过从原问题到凸优化问题的归约实现的，最 终归约为在线性不等式限制下的二次函数最小化问题。首先应该注意到在线性分 类器的定义下存在着一些固有的自由度，即是如果把超平面的系数修改为 ( 2 w , 2 b ) ，旯r + ，超平面( w ，6 ) 的解析函数并不会发生变化。不过，这会使得另 一个相反于几何上的间隔度量函数输出的间隔产生变化。这个函数输出的间隔被 称为函数间隔。 通过把函数间隔修正为1 ，就可以等价地优化几何上的间隔，然后再最小化 权重向量的范数。函数间隔为1 的超平面有时被称为标准超平面。当函数间隔为 1 时，权重向量记为w ，正类点记为，负类点记为x 。，则可以如下计算它们的 几何上的间隔： 由于函数间隔等于1 可以表示为： ( w ) + 6 = + l w x 一+ b = - 1 在计算几何间隔时则必须归一化w 。生成的分类器的几何间隔就是： y = 吉( 一 2 厕1 ( ( w ) 一( w 彳) ) 第二章理论基础 因此，生成的几何间隔将会是等于志。可以得到如下结论： i l w l l 给出一组线性可分的训练数据集s = ( 0 i 1 ) ，o ，) ) ，如果超平面( w ，6 ) 可以解 决优化问题： 最小化( w w ) 使满足只( ( w t ) + 6 ) 1 ，i = l ， 则这个超平面就是实现了几何间隔y = 志的最大间隔分类的超平面。 1 1 w 0 进一步推导，考虑一组线性可分的训练数据集s = ( l 1 ) ， ，) ) ，如果参数 口可以解决如下的对偶优化问题： 最大化形( 口) = ：。q 一告：产。y , y ，够，( x ，) ， 使满足：ly i a , = 0 ，a i o ，i = 1 ， 那么权重向量w = ：。y i o ：，x , 实现了最大间隔超平面，这时的几何间隔 y ：而1 ：f ，r 垆丽2 【未j j 在把原型的优化问题转化成对偶型的过程中可以得到一个结论，只需要支持 向量( s u p p o r tv e c t o r ) 就可以包含能重新生成分类超平面的所有必须的信息。即使 所有其他的数据点都被去掉，对于这些剩下的支持向量构成的子集依然可以找到 最大间隔分类超平面。这也可以通过观察原问题的对偶问题得到，因为去掉行和 列所对应的非支持向量之后，也会留下同样的未改变的优化问题。利用这个性质 就可以得到分类器的一种压缩方法，因为只要给出由支持向量构成的子集，就可 以重新构造出最大间隔超平面，这个重新构造出的超平面同样能够正确地对整个 训练数据集进行分类。 2 3 3 软间隔 最大间隔分类器是一个很重要的概念，它是分析和构造更紧密和复杂的支持 向量机的起点。但是它不能用于很多现实世界中所遇到的问题：如果数据有噪音， 一般而言它们就会不是在特征空间上线性可分的( 除非刻意地使用更强大的核函 数，但这样很可能会导致数据过拟合问题) 。最大间隔分类器身上最主要的问题 就是那个没有分类误差的假设，它的动机就是依赖于可以完全将数据分开的间 隔，所以在大多数情况下它的基本假设是得不到满足的，除非数据本身就是严格 的可分的。 建立在间隔上的依赖性使得这个系统在某种程度上显得很僵硬，因为在绝大 第二章理论基础 多数真实数据中都不可避免地会出现噪音，即使是很规范的数据也很容易会变得 不能线性可分。此外，在特征空间中的数据不是线性可分的情况下，由于原问题 只有空的可行范围，所以原最优化问题会变得不可解，并且它的对偶问题的目标 函数也会变得无限制。这些问题的存在使得需要引入更为强健的间隔分布的度量 方法，可以容忍噪音和离群点，不只会考虑那些靠近分界面的点，也会更多地考 虑其它位置上的训练点。 由于最大间隔分类器的原优化问题可表示如下： 最小化( w w ) 使满足只( ( w ) + 6 ) l ，扛l ， 为了优化松弛向量的间隔，需要引入松弛变量，这样间隔的约束就可以被打 破： 最小化( w w ) + ( ：。等 使满足只( w w ) + 6 ) 2 1 - ( , 专o ，扛1 ， 或者 最小化( w w ) + c 使满足只w w ) + 6 ) 1 一考，专o ，i = l ， 注意到如果鲁 0 ，那么第一个限制条件依然会保持，如果设置毒= 0 ，就会 使目标函数值减少。 在实践中，参数c 的值有很大的变化范围，为了能确定由c 值取值不同所产 生的性能表现，可以使用独立的验证进行评估，或者采用技术上常用的在训练数 据集上的交叉验证进行评估 2 1 】。如果参数c 的值在一个范围里进行变化，范数 i l 训i 也会平稳地在相应的范围内变化。因此，就实践上的问题而言，对c 选择一 个实践上的值相当于对0w | i 选择一个合适的值，然后在w 值的设定下最小化1 1 ：1 i 。 2 3 4 多类分类方法 从原理上说支持向量机直接解决的分类问题只是二类分类问题，二类分类问 题也可以通过对于每一个类别定义一个权重向量w ，和偏移量b ，进行定义。每次 加入新的实例点而需要辨别类别时，正负两个间隔函数都会被计算。如果 ( w x ) + 包( w - ，x ) + 6 - ，那么点工会被归为正类；否则石就会归为到负类。这 样的策略其实等价于只使用单个超平面进行判别，此时w = w 一地，b = 6 1 6 - 。 对于多类分类问题，输出范围是y _ l ，2 ，z ，而从线性的二类分类模型扩 展到m 类的多类分类模型也比较直接：对这m 个类别中的每一类都关联上一个 权重向量和一个偏移量( w ，匆) ，i l ，聊 ，于是整个多类分类的判定函数就可以 第二章理论基础 按如下方法给出： c ( x ) - a r g m a x ，( 、( 、w , x ) + ”l ，月，、 从几何形态的角度上看，这等价于对于每个类别都关联一个分类超平面，对 于每一个类别待定的数据点它离哪个分类超平面最远就将它分为哪一类。算法 上也等价于构造m 个独立的二类分类器，对于类别i 的分类器，其正类的数据点 就是属于原来第f 类的数据点，而其它类别的数据点在这个分类器中都被标定为 负类。 通常这样的多类分类策略被称为“一对其它”多类分类法，与其相似的还有 一种称为“一对一”多类分类法。对于m 类的多类分类问题，“一对一”多类分 类法对任意两个类别都构造一个分类器，即是一共需要构造个分类器。最后 通常使用投票法决定待分类点应该归属的类别。 2 4 核函数理论 2 4 1 核函数原理 一般而言，复杂的真实世界的应用需要比线性函数更有表达力的假设空间。 因为目标概念常常不能像一个简单的给定属性特征的线性合并一样被表达，在一 般性的需求中，需要挖掘数据的更抽象的特征。对于这个问题，不同层面的带阈 值的线性函数被当作解决方案被提出，于是为了训练这样的系统，多层神经网络 和学习算法例如反向传播等理论和技术得到了发展。 可计算问题的难点不只是使用的特征空间的巨大规模，另一个难点的来源是 机器学习的泛化( g e n e r a l i z a t i o n ) 问题，它可能对于假设的标准函数类别的表示的 维度十分敏感。 很明显，特征选取应该被看成是学习过程本身的一部分，而且应该被尽可能 自动化地解决。另一方面，特征的选取又是多少有些随意性的步骤，选取的标准 反映了选取者在该领域上的目标函数的先验期望。理论上的学习模型也常常需要 考虑到这样一个原则：使用太大的特征集合可能会导致过拟合( o v e r f i t t i n g ) i h 题， 除非泛化问题可以通过一些方式被控制。就因为这个原因维数约减问题才频繁地 受到关注。不过另一方面，泛化问题又可以允许使用无限维的特征空间，可以通 过基于泛化考虑的学习模型避免过拟合问题，同时计算复杂度方面的麻烦可以所 谓的“隐式映射”方式来避免。 一个核函数是一个函数k ，使得对于所有的溉z x k ( x ，z ) = ( ( x ) 矽( z ) ) 第二章理论基础 这里的矽是从空间x 到内积特征空间f 的映射。 核( k e r n e l ) 这个名称来自于积分算子理论，它支持着许多核和他们相应特征空 间的关系的理论。支持向量机的对偶表示的一个重要的结果就是特征空间的维度 规模不会影响计算的规模，而核函数的计算也不需要清楚地描述特征向量。通过 计算核函数，被需要来计算内积的操作数量不需要再与特征的数量成比例。核的 使用使得原空间中的数据点可以映射到一个新的特征空间，并且在映射到的空间 中训练线性分类器，而且潜在地避开了具体的计算特征映射的过程 2 2 】。训练分 类器所必须的信息只是训练样例之间的格拉姆矩阵( g r a mm a t r i x ) ，这个矩阵也被 称为核矩阵。 2 4 2 核函数的性质 判断一个对称函数是否是核函数，关键是要求对于任意有限点集合，用这个 函数定义的矩阵必须是半正定的。利用这个判定标准就可以创造出一系列新的核 函数。下列命题可以被看成核函数所满足的一系列闭合的属性，这些属性使得可 以从基本的核函数出发来创造出更复杂的核函数。 令k l 和憨定义在是在空间x x x ，x r 上的核函数，a r + ，厂( ) 是定义 在x 上的实函数。于是下列的函数也都是核函数： 1 k ( x ，z ) = 墨( x ，z ) + k ( x ，z ) 2 k ( x ，z ) = 口k ( x ，z ) 3 k ( x ，z ) = k ( x ，z ) k ( x z ) 一般地说，支持向量机中定义的核函数必须满足对称半正定的性质。但实际 应用中的一些核函数并不是真正意义上合法的核函数，这样的核函数是无法保证 可以适用于最大间隔分类器模型的 2 3 】。不过h a a s d o n k 2 4 最近阐述了如果可以 在伪欧拉空间中生成凸包的优化分隔，核函数必须满足的一般意义上的半正定限 制是可以被打破的。如果核矩阵能满足一系列适当的标准，那么它对应的核函数 依然可以适用于支持向量机的学习和分类。 第三章算法设计 3 1 基于分类的算法框架 第三章算法设计弟二早舁法阪丌 从计算机解决问题的角度来看，在a c e 项目的实体抽取任务基础上，整个 问题的输入可以看成a c e 项目提供的已经对大量自然语言文本进行了实体抽取 的x m l 文档。在这些x m l 文档中，每个句子里所包含的实体都被标定了出来， 并且在x m l 文档中这些实体的起始位置、实体类别、实体子类别和其他一些有 用的实体所携带的信息都已经被人工标定了出来。除了实体信息被标定出来了以 外，实体之间的正关系的基本信息，包括实体关系的参与实体，还有实体关系的 关系类别和关系子类别也被标定出来了。这些相当于标准答案的人工标定就使得 监督型的机器学习模型能够得到应用，并且学习的最后结果也可以得到规范的评 估。 例如a c e2 0 0 5 语料中提供的标定的文档中，有一篇文档包含如下一句话： “另外第二批团员的家属今天也抵达了温哥华，孙女被安置在市立医院的张 湘婷也是其中的一位。” 这个语句包含下列的实体，它们各自的实体类别和实体子类别也已经在文档 中被标出了： 表3 1 例句中的实体 实体标识符实体外延文本实体首部文本实体类别实体子类别 e 2 0 2 3 孙女 孙女 p e r i i l d i v i d u a l e 1 9 2 2市立医院医院f a c b u i l d i n g - g r o u n d s e 1 8 2 1孙的张湘婷张湘婷p e ri i l d i v i d u a l e 1 6 1 8第的家属家属p e r g r o u p e 1 6 2 4其其p e r g r o u p 以“市立医院”这个实体为例，它在现实世界中拥有具体的事物指代，所以 应该表示为实体。同时市立医院的中心词是“医院”这个文本范围，而“市立” 可以看成是医院的修饰词，因此实体的外延范围的文本是“市立医院”全部，而 首部文本是中心词“医院”。每个实体的内外两个范围对于体现实体本身的位置 第三章算法设计 信息都十分重要，一般而言不同实体的外延范围可能相互包含甚至相互重合( 重 合即是指两个实体的外延范围相同且首部范围不同) ，而头部范围则完全独立， 不会出现重叠或重合的情况。 在上例中的一些实体之间，包含有a c e 项目下定义的实体关系，这些关系 在a c e 的标定文档中也已经给出了： 表3 2 例句中的实体关系 关系类别关系子类别 关系前实体关系后实体 p e r s o c f a m i l y e 1 6 1 8e 1 7 1 9 p h y sl o c a t e de 1 6 1 8e 3 1 2 0 p h y sl o c a t e de 2 0 2 3e 1 9 2 2 p e r s o c f a m i l y e 2 0 2 3e 1 8 2 1 负关系 负关系 其它所有实体对 每个关系( 无论是正关系还是负关系) 必须有两个参与实体，由于实体的首 部范围不会出现重合，因此可以根据实体首部范围的前后顺序将参与实体进一步 细分为前参与实体和后参与实体。根据a c e 项目的定义，每个实体关系都有一 个关系类别和关系子类别。实体关系抽取问题的任务就是判断出关系的类别和子 类别，如果是独立地解决关系类别的判别和关系子类别的判别，那么可采用相同 的分类算法框架。一般而言，对于同样的学习模型，关系子类别的判别性能明显 差于关系类别的判别性能。 当前流行的解决实体关系抽取的算法框架是基于实例分类的算法框架。原理? 是将可能包含正关系的每两个实体的实体对作为向量空间上的实例点( 称为候选 关系实例) ，如果两个实体间已经被标定出具有正关系，则将实例点标定为其关 系类别所对应的实例类别；如果两个实体间没有直接的语义联系，即实体对只具 有负关系，则将实例点标定为负关系所对应的区别于所有正关系类别的实例类 别。 例如e 2 0 2 3 ( 孙女) 和e 1 8 2 1 ( 孙女被安排在市立医院的张湘婷) 这两个 实体的实体对，将它们看成一个整体的实例，也就是看成空间上的一个点。由于 这两个实体之间有着p e r s o c ( 人社会) 类别的正关系，所以应该将这个实例 点标记为p e r s o c 类别所对应的实例类别。 再例如实体对e 1 8 2 1 ( 孙女被安排在市立医院的张湘婷) 和e 1 9 2 2 ( 市立 医院) ，由于它们之间的关系是负关系，所以把代表这个实体对的实例点标记为 “负关系”类别，以使得所有包含负关系的实例点都属于参与分类的同一类别。 第三章算法设计 以所有拥有类别标定的实例点作为训练数据集，则可以学习出泛化性能良好 的多类分类器。对于关系类别有待判别的实体对，如果它所对应的向量空间中的 实例点被分到“负关系”这个实例类别之中，那么这个实体对的两个参与实体之 间就认为只有负关系，换句话说就是参与实体之间没有直接的语义联系；否则， 通过得到的实例点类别就能确定参与实体之间的关系类别。 3 2 实体位置特征及相应算法 到底具有哪些特征的实体之间会含有正关系，首先可以从实体的形态特点上 进行分析。通过观察语料，我们可以发现实体相隔得越远，它们之间有关系的可 能性就越小。统计结果表明，实体对是否含有正关系确实是与参与实体之间的距 离相关的。实体间的距离虽然可以作为表示关系实例的一个特征，但相比实体间 的位置特征而言，距离特征显得不太重要。 从几何形态上看，实体之间可能会有相邻和相隔两种相互位置关系。由于实 体的外延范围可能会相互包含或者重合，所以实体与实体之间实际可能会有包 含、重合、相邻和相隔这四种互不相容的相互位置特征。实体间的位置特征对于 体现实体对所含有的信息特别是语义信息具有重要作用。因为如果参与实体间是 一种包含位置特征，那么这两个实体在语义上就可能有主次或是修饰的关系；而 如果参与实体间是一种相邻位置特征，那么这两个实体很可能是并列的关系；如 果参与实体间是相隔位置特征，那么这两个实体之间很可能含有负关系。 可以形式化地定义实体之间的位置特征：给定一个实体n e m ，用h e m s t a r t 和n e m e n d 表示这个实体的外延范围在语句中的起始位置和终止位置。用 n e m , 3n u m ，来表示( n e r o ) 3， ，)并且i s t a r th e m , e n d ( n e r os t a r tn e me n d ( h e m ，玎p 聊，) (， 。在这个定义的基础上就可以形式化, s t a r t e n dn e r os t a r tn e r oe n d ) 地定义四种最基本的实体间的位置特征。对于两个实体n e m l 和n e r 0 2 ，由于实体 的首部范围不会有重叠部分，所以一定有先后次序。不妨设前参与实体为n e m l ， 而后参与实体为n e m 2 ，则可以定义出四种基本的位置特征，如表3 3 所示： 第三章算法设计 表3 - 3 四种基本位置的定义 位置特征成立条件 包含h e m 2 ：) 门p ，绝 重合n e n h s t a r t = h e m 二f t a r t x 疗p 码e n d = h e m ! e n d n p e n d f l e m 2 s t a r t 相邻 - 1 3 ( n e m , ) ( n e r 0 1 e n d r l e m ，s t a r tan e m ，e n d h e m 2 s t a r t ) 珊，码e n d h e m 2 s t a r t 人 相隔 3 ( n e r o , ) ( 刀嬲e n d n e r o , s t a r tan e r o , e n d n e m 2 s t a r t ) 虽然这四种基本位置特征已经可以反映把实体对的两个实体之间的基本的 位置信息，但是还不够精细。因为有时即使是两个实体已经够成了一种包含位置， 但是如果出现另外的实体夹在这两个实体之间，那么这两个实体的语义关系其实 已经发生了微妙的变化。又比如，虽然两个实体之间没有其他实体相阻隔，按照 定义应该是相邻位置，但如果其中一个实体其实被另外一个实体所包含，那么这 两个参与实体的紧密程度其实已经不及单纯的相邻关系那样。如图3 - 1 所示： 图3 1 第三方实体对位置特征的影响 所以有必要在四个基本的位置特征的基础之上，通过挖掘第三方的实体来定 义更加精细的位置特征。首先需要形式化地定义另一个运算符n e r o k 上 ( 胛p 确，n e m z ) 来表示力p 嘲e n d n e r o k s t a r t 并且h e m k e n d h e m 2 j t a r t 。依然不妨设 前参与实体为n e m l 而后参与实体为n e r 0 2 ，于是可以得到包含原来的四类基本 位置特征的九类更详细位置关系特征，如表3 _ 4 所示： 第三章算法设计 表3 4 九个位置种类的定义 位置特征 成立条件 包含n e r 0 23 p