2007年Banko发表的这篇文章,第一次提出了Open IE(OIE)的概念,所设计的系统为TEXTRUNNER。这个设计打破了传统的“封闭式”IE系统,使用一种无监督的方式可以提取出类型更加多样的关系元组,且运行效率较传统的IE系统有质的飞跃。let's begin...
原文链接:https://www.aaai.org/Papers/IJCAI/2007/IJCAI07-429.pdf
摘要:
传统的信息抽取存在的限制主要是:在小型同质语料库上实现高精度、范围窄且预先指定的提取请求。举个栗子:给定N场某篮球队的比赛文字解说,提取出每一场比赛的开赛时间、最终比分及某球员的最终得分等。这样的提取是需要大量人工参与的,例如:预先标注数据、预先设定提取关系等。一旦将该类信息抽取应用于其他领域就会再次要求人工再次参与,包括:命名目标关系、创建新的提取规则、标记训练样本等,且工作量与目标关系的数量呈线性关系。
在这篇文章中提出了一种新的提取范式(OIE),在该范式上的系统在整个语料库中执行一次基于数据驱动的遍历,将在没有任何人工参与的情况下提取大量的关系元组。本文还提出了TEXTRUNNER系统,这是一个已完全实现、高度可扩展的OIE系统,其为每个元组分配概率并建立索引,以支持通过用户查询进行有效的提取和利用。
对比实验是TEXTRUNNER和KNOWITALL(这是当时最先进的Web IE系统)在900W个Web页面上的比较。TEXTRUNNER在一组提取的比较中将错误减少了33%。此外,在使用KNOWITALL对预先定义好的关系进行提取所花费的时间里,TEXTRUNNER具有更为广泛的实体集,这也表明该系统可以即时发现更多数量组的关系。通过对来自TEXTRUNNR的1100W个最大概率元组统计发现,其中包含了超过100W个具体实体和超过650W个抽象断言。
1、引言及动机
OIE是一种新的提取范式,有助于从文本中提取出独立于领域的关系发现,并易于扩展到Web语料库级别的多样性和数量级上。OIE系统的唯一输入是语料库,在语料库上进行一次遍历就保证了语料库大小的可扩展性,最终输出一组提取的关系。而传统的IE则依靠大量的手工参与,如提取规则制定、训练数据标注、感兴趣关系制定等。虽然随着技术的进步使得IE变得越来越自动化,但对于像Web这个级别数量巨大且多样的语料库而言,要使用传统IE来枚举所有潜在感兴趣的关系以构建提取就存在很大的问题了。因此,要使用用户在异构的语料库上执行查询,IE系统必须在系统架构中放弃掉要求在查询之前指定关系这一需求,应当采用旨在发现文本中所有可能的关系。
以前,IE应用于类似的小型语料库,通过繁重而复杂的语言学技术调整到用户关注的领域,例如:依赖解析和命名实体识别。由于两种技术的参数都是固定的且数量较少,因此这些系统的设计没有相对于语料库的大小或提取的关系数进行缩放。
然而,从Web中提取信息的问题就违反了传统IE的假设。当前面临的语料库庞大且种类繁多,感兴趣的关系也是无法预料的并且其数量有可能很大。接下来详细考虑这些挑战:
自动化。要实现IE系统的自动化的第一步就必须要将基于知识的系统过渡到可训练的系统,这些可训练的系统以手工标记的实例或文本段作为输入,自动学习特定于领域的提取模式。不少工作通过少量标记的种子实例、为某种关系提供少量手工提取模式来启动训练过程,进一步减少了特定关系的文本提取所需的人工成本。但是,创建合适的训练数据需要大量的专业知识、必须预先指定关系、对于提取的每个关系都需要大量手工操作。
异构的语料库。传统的关系提取方法包括基于内核的方法、最大熵模型、图模型以及共现统计数据等,但这些方法都是在规模较小、领域特定的语料库和有限的关系集上实现的。NER和依赖解析器的使用都是一个统一的线程,该线程与以前的工作大多一致。但将这些“复杂”的语言学技术应用于Web上的异构文本时就会有问题了。当在特定类型的文本上训练并使用解析器时可以很好地工作,但Web文本的多样性将会使解析器产生更多的错误。此外,Web上实体类型的数量及复杂性也意味着现有的NER系统是不适用的。
效率问题。当前最先进的Web IE系统是KNOWITALL,其通过使用一组与领域无关的提取模式来学习标记其自身的训练样本,还通过依靠词性触发器这类浅层关系代替解析器来解决语料库的异构性,而且不需要使用NER。KNOWITALL需要进行大量的搜索引擎查询以及Web页面的下载,因此其实验可能需要数周才能完成 ,而且该系统使用关系name作为输入,每一次设定不同感兴趣的关系时都必须重新运行提取过程。现在的OIE保留了KNOWITALL的优势,但消除了其效率低下的问题。
这篇论文提出的系统名为TEXTRUNNER,这是一个可扩展、独立于各领域的OIE系统,可以从文本中提取关系元组,此外还为每个元组分配一个概率并建立索引,支持通过用户查询进行有效的提取和检索。最重要的是,TEXTRUNNER是一个已完全实现的系统。总的来说,本文的贡献主要有以下几个方面:
(1)介绍了一种新的关系提取范式,即开放式信息提取(OIE)。其可以在只对语料库进行一次遍历的前提下自动发现可能感兴趣的关系,消除了关系的特异性。
(2)文章提出了完全实现的OIE系统TEXTRUNNER,并且重点描述了该系统架构的关键组成部分。文章还通过实验对比了KNOWITALL和TEXTRUNNER的性能,表明TEXTRUNNER在相当数量的提取中实现了33%的相对误差减少。
(3)在TEXTRUNNER的1100W个最高概率提取的统计报告表明了该系统的可扩展性,这助于评估提取项的质量并为今后的工作提供指导。
2、TEXTRUNNER系统介绍
本节将重点介绍TEXTRUNNER的体系结构,以及其如何应对第1节中提到的每个挑战。从IPO层面来看,TEXTRUNNER的唯一输入是语料库,其输出是提取项的集合,该集合可以有效建立索引以支持用户通过查询进行利用。其处理过程主要包括三个关键模块:
(1)自监督学习器:给定一个小的语料库样本作为输入,学习器将输出一个将候选提取项标记为“trustworthy”或否的分类器,该学习器不需要任何手工标记的数据。
(2)单遍提取器:该提取将在整个语料库上做单次遍历处理来提取所有可能的关系元组。该提取器不使用解析器,其从每个句子中生成一个或多个候选元组,再将每个候选元组送入分类器,并保留标记为trustworthy的那些元组。
(3)基于冗余的评估器:评估器基于[Downey et al.,2005]提出的文本中冗余度的概率模型,为每个保留的元组分配一个概率。
2.1 自监督学习器
学习器的执行过程分为两步。首先,自动将自己的训练数据标记为正或负;然后,使用标记的数据来训练Naive Bayes分类器,该分类器后续将用于Extractor模块。
在Web规模内,虽然应用深层语言学解析器来提取对象间的关系是不可行的,但我们假设解析器可以帮助训练训Extractor。因此,在进行全面规模范围内的关系提取前,学习器使用[Klein and Manning,2003]提出的一种解析器来自动识别和标记一组trustworthy或untrustworthy的提取项,这些标记的提取项将用作Naive Bayes的正/负训练样本。当应用于异构的Web文本时,解析器将会产生较多错误,因此本文使用了耐噪的学习算法来帮助系统从这些错误中恢复回来。
提取项表现为元组的形式:,其中
是用于表示实体的字符串,
是用于表示两个实体间关系的字符串。训练器解析了几千个句子来获取其依赖图表示,对于每个解析的句子系统都会找到所有的基本名词短语成分
;对于每对名词短语
,系统将遍历连接它们的语法结构,找到可以在元组t中成为两实体间潜在关系的单词序列。如果满足
共享句法结构上的某些确定约束,学习器将会将t标记为正样本。即使这些解析树可能包含一些局部错误,但认为这些约束试图提取的关系是正确的;如何有任何限制不满足了,则将t标记为负样本。该系统使用的一些启发式方式如下:
a、间的依赖链不长于一个特定的长度;
b、沿语法树上间的路径不会跨越类似句子级的边界(例如:相对从句);
c、两个实体均不是代词。
一旦学习器找到并标记了一组形式为的元组,其将把每个元组映射为一个特征向量表示。每个特征都是领域独立的,并且可以在不使用解析器的情况下在提取时间内进行评估。这些特征包括:关系
中存在的词性标签序列、关系
中token的数量、关系
中停用词的数量、实体e是否为专有名词、
左边的词性标签、
右边的词性标签。接下来就是进行特征提取,学习器使用这些自动标记的特征向量作为输出来训练Naive Bayes分类器。
学习器的输出是特定于语言的,但不包含特定于关系或词汇的特征,因此该分类器可以以独立于领域的方式进行使用。在应用学习方法前,文章的一位作者手动构建了与关系无关的提取项分类器。关系提取的第一个尝试是将识别到的两个实体间的整个字符串视为感兴趣的内容,不出意料的是,这种宽窄的做法将会得到很多无关紧要的信息。换另一种极端的思路,即仅仅寻找与一对名词相关的动词这样的严格做法,会导致其他重要链接的丢失,例如那些专有名词或以属性为中心的关系,如:(Oppenheimer,professor of, theoretical physics)和(trade schools, similar to, colleges)。以纯动词为中心的方法倾向于提取不完整的关系,例如:(Berkeley,located, Bay Area)将代替(Berkeley, located in, Bay Area)。基于启发式的方法试图暴露一些困难,这些困难涉及到以一种通用的方式来预测一个关系及其观点。最终的手工构建分类器是另一个学习器的基线,在准确率上充其量为学习器准确率的三分之一。
2.2 单遍提取器
提取器在整个语料库上执行单次遍历,自动为每个句子中的每个词标注其最有可能的词性。通过使用轻量级名词短语块识别名词短语后再使用这些词性标签来发现实体(据文章脚注说明,该过程使用OpenNLP库来实现,分析过程则使用的是最大熵模型来处理词性标注和名词短语块问题。对于词性标签和名词短语可以在不同领域和语言上构建高精度的模型。而使用相对轻量级的NLP技术可以使用TEXTRUNNER在Web层面这样高度多样性的文本中更有鲁棒性)。关系的发现主要是通过以下操作:检查名词短语间的文本,与此同时还启发式地消除那些非必要的短语(如:scientists from many universities are studying...将被分析为scientists are studying)或单独的token,例如副词(eg:definitely developed被简化为developed)。
对于每个找到的名词短语,分块器还为每个块分配一个概率,其前提是块中的每个词都被当作是实体的一部分。这些概率后续将用来决定丢弃包含置信度低的实体的元组。最后,将每个候选元组t输入分类器,如果分类器将t标为trustworthy,则该元组就由TEXTRUNNER提取的并进行存储。
2.3 基于冗余的评估器
在提取过程中,TEXTRUNNER创建了关系的规范化形式,该形式省略了动词和名词的非必要修饰词,例如was developed by 就是was originally developed by的一种规范形式。在整个语料库上执行提取操作后,TEXTRUNNER自动合并实体与规范化关系都相同的元组,并统计每个提取项在不同句子中出现的次数。
在提取后,评估器根据这些计数,使用先前在无监督IE系统KNOWITALL中用到的概率模型为每个元组分配概率。在没有手工标记数据的情况下,该模型可以有效的估计,从k个不同句子中在实体间提取的关系
(表示为元组
)是正确实例的概率。该模型表明,相比基于噪声和配对互信息的方法来说,对于IE系统其估计准确率更高。
2.4 查询过程
TEXTRUNNER能够以交互的速度响应数百万个元组的查询,这主要是由于存在分布于计算机群组中的倒排索引。在元组提取期间,找到的每个关系都将分配给群组中的独立计算机。然后,每台计算机都会在本地存储元组的文本上计算一个倒排索引,从而确保每台机器都可以存储所有的元组:这些元组均包含了一条引用,该引用连接分配给该机器的关系。【据脚注说,倒排索引是使用Lucene开源搜索引擎建立的】
在TEXTRUNNER中对元组进行高效的检索意味着,当用户通过命名一个或多个元素来访问元组子集时,相关子集可以在几秒钟时间内完成检索,而不相关的提取项将不会出现。由于TEXTRUNNER中的关系名称是直接从文本中获取的,因此直觉上隐式地制定搜索查询是有效的。一旦TEXTRUNNER能够知道哪些关系与其他关系同义,查询有关系的三元组将变得更加容易。但是,让用户来“猜测正确的单词”对所有搜索引擎都是难题,这表明该系统只对比较naive的用户比较好管理。
最后,TEXTRUNNER以关系为中心的索引实现了复杂的关系查询,而这些复杂的查询是当前的搜索引擎使用标准的倒排索引无法实现的。这些复杂的查询包括:关系查询、未命名项目查询以及多属性查询,每一荐都在[Cafarella et al,2006]中进行了详细介绍。
2.5 分析
TEXTRUNNER中的元组提取时间复杂度为O(D),其中D表示语料库中文档的数量。接下来还要花费O(TlogT)的时间进行排序、统计和评估系统发现的元组集T。相反,每次传统IE系统用于发现一组新关系R的实例时,都可能被迫检查语料库中的大部分文档,从而使得系统运行时间为O(R*D)。当D和R都很大时(如通常情况是在Web上),TEXTRUNNER拥有能够一次为所有关系提取信息的能力,而且不需要在输入中进行明确命名,这也使得与传统的IE系统(包括KNOWITALL)相比有更明显的可扩展性优势。
TEXTRUNNER以每句0.036 CPU秒的平均速度提取实体。与依赖解析器平均花费3秒来处理一个句子相比,TEXTRUNNER在相同语料库上运行速度快了80倍。平均而言语料库中的一个网页包含18个句子,这使TEXTRUNNER对每个文档的平均处理速度为0.65个CPU秒,从900万网页语料库中提取元组的总时间少于68个CPU小时。由于语料库很容易分成多个独立的部分,因此在20台计算机的集群上进行处理的总时间少于4小时。TEXTRUNNER还需要花费额外的5个小时才能对提取的元组进行合并和排序,将在3.1节中比较TEXTRUNNER与最新Web IE系统的性能。
TEXTRUNNER可扩展性的关键是处理时间在D上是线性的(在R中是恒定的)。如上述测量所示,TEXTRUNNER不仅在理论上具有可扩展性,而且在实践中也很快速。
3、实验仿真
3.1节中比较TEXTRUNNER和封闭IE系统在一组关系中的召回率和错误率,3.2节描述使用TEXTRUNNER提取更广泛的实体和关系的情况。
3.1 与传统IE的比较
评估Open IE的一种方法就是将其性能与最新的Web IE系统进行比较,对比对象选择的是KNOWITALL,这是一种无监督的IE系统,能够从Web上进行大规模提取。实验任务是从900W个网页语料库中提取实体。
由于 KNOWITALL是一个封闭的IE系统,需要预先确定一组关系。随机从语料库中的选择10种关系,每一种关系在语料库中至少可以在1000个句子中找到,并手动过滤掉过于模糊的关系(如:“includes”),具体关系如下:
表1显示了两个系统中十种关系的平均错误率和正确提取的总数。TEXTRUNNER的平均错误率比KNOWITALL低33%,但其发现的正确提取资料几乎相同。探究原因,TEXTRUNNER的提升很大程度上可以归因于其能更好地识别相对于关系正确的论点。
两个系统的大部分错误均来自于名词短语的分析:名词参数被截断或添加了stray词。如果没有为系统指定诸如公司名称、人名或书题等参数的预期类型,则很难准确地找到提取边界。对于authorOf关系尤其如此,其中许多反映书名的参数都被截断了,使得TEXTRUNNER的错误率为32%,而KNOWITALL为47%。排除了这个错误后,TEXTRUNNER的平均错误率为10%,KNOWITALL的错误率为16%。
即使是只提取10种类型的关系,TEXTRUNNER的效率优势仍然是显而易见的。是在900W页语料库上运行时,TEXTRUNNER的分布式提取过程总耗时为85个CPU小时,可以执行一次在语料库上对所有关系的提取;KNOWITALL则会分析语料库中所有可能符合其关系规则的句子,平均每个关系需要6.3个小时。在KNOWITALL从14个预先指定的关系中提取数据的时间内,TEXTRUNNER从相同的语料库中发现了更多数量级的关系。
除了采样的10种关系外,两系统还存在根本的不同。标准的IE系统只能根据用户事先给予的关系进行操作,并且仅适用于数量相对较少的关系。而Open IE无需预先知道这些关系,并且可以一次提取所有关系的信息。
3.2 抽取实体的全局统计
在给定的900W个页面的语料库中包含1.33亿个句子,TEXTRUNNER以平均每句2.2个元组的比率自动提取了6050万个元组。
Open IE的输出自然会引出以下几个问题:找到的元组中有多少个是带有合理论点的实际关系?这些元组的哪个子集是正确的?这些元组中有多少个是不同的,相反,相同或同义的有多少?由于元组集合的大小和多样性,回答这些问题就变得很有挑战性。为回答上面的问题,接下来进行了一系列的估算和近似计算。
首先,将分析限制在TEXTRUNNER提取的高概率元组的子集中。具体来说,参与评估的元组要满足以下条件:1)TEXTRUNNER为该元组分配的概率至少为0.8;2)元组的关系至少在语料库中的10个不同句子中出现;3)按支持句子的数量来算,元组的关系不会出现在关系排名的前0.1%(因为这些关系很普遍,以至于几乎是没有意义的,例如(NP1,has,NP2))。过滤后的集合由1180万个元组组成,包含278085个不同的关系字符串。这个过滤后的集合是将本节中描述的所有测量中使用的集合。
估计实体的准确性。
从过滤后的集合中随机选择400个元组作为样本。接下来将根据手工标记的样本推断测量。本文的三位作者检查了元组来表征TEXTRUNNER提取的数据。每位评估人员首先判断该关系是否格式正确。如果存在许多对实体X和Y且(X,r,Y)是X和Y之间的一个关系,则认为关系r是格式规范的。例如:(FCI, specializes in, software development)包含格式良好的关系,而(demands, of securing, border)则不是。如果发现一个元组具有良好的关系,则将判断该论点是否适合该关系。如果X和Y是可以形成关系(X,r,Y)的实体“类型”,则认为X和Y是关系r格式正确的论点。论点不正确元组的一个例子是(29,dropped,instruments)。
进一步将满足这些条件的元组分类为具体的和抽象的,具体是指元组的实体是基于特定实体的,如:(Tesla,invented, coil transformer);抽象元组是未指定的,如:(Einstein,derived, theory),或指代其他地方但暗含一般类的属性的实体,如:(executive,hired by, company)。
最后,根据每个抽取的具体元组或抽象元组是否与提取该元组的句子的真实值一致,来判断该元组为真还是为假。下图总结了对提取元组的分析。
TEXTRUNNER发现有780万个实体,它们均具有良好的关系和论点,概率至少为0.8.根据人工审查,有80.4%被认为是正确的。在给定一个关系中,平均14%的元组是具体实体(88.1%的准确性),86%是抽象实体(77.2%的准确率)。具体实体可能对于信息抽取或问答系统很有用,而抽象断言对于本体学习和其他应用程序很有用。当然,在任何特定的应用程序中,只有一小部分的元组是有意义的。
预估不同实体的个数。
在由TEXTRUNNER提取的数百万个元组中,有多少个反映的是不同的陈述,而不是对现有陈述的重新表述喃?为了回答这个问题,需要能够检测一个关系何时与另一个关系同义,以及何时一个实体被多个名称引用。在那些无监督且领域独立的上下文中,具有大量不同类型的关系实体,要回答这两个问题都是非常困难的。因此在本文的测量中,仅能解决关系同义的问题,也就意味着以下报告的测量是粗略近似的。
为了评估TEXTRUNNER发现不同关系的数量,本文进一步合并了仅在开头、结尾结点、辅助动词或停用词(例如that、who、which)上不同的关系。例如:将“are consistent with”与“which is consistent with”合并。此外还合并了因为主动或被动语态而不同的关系,例如:invented与was invented by合并。这个步骤将唯一关系的数量减少到合并前的91%。
经过上述的合并后仍然存在一些问题:这些关系字符串有多少是同义的?因为TEXTRUNNER发现的许多关系都有多种含义,因此要回答这个问题是十分困难的。例如developed关系,可以是一个人与一个发明间的关系,也可以是一个人一种疾病间的关系。除非对一个或两个自变量执行特定于领域的类型检查,否则是很难找到两个短语在所有意义上都真正同义的不同关系。如果每一个论点是科学家的名字,那么developed就与invented和created同义,并且与patented紧密相关。如果没有这种参数类型的检查,这些挑选出来的关系将是重复的,但是又完全不同的元组集。
对于人来璾,在元组级别上评估相似性是比较容易的,因为在这种情况下基于关系的实体形成的上下文是存在的。为了估计TEXTRUNNER提取的相似实体的数量,从过滤后的1130万个元组开始。对于每个元组,发现形式为的具体元组簇,其中
,即元组中实体可以匹配但关系字符不匹配。结果发现只有三分之一的元组属于这样的“同义簇”。
接下来,随机选择100个同义簇并请本文的一位作者确定每个簇中存在多少个不同的实体。例如,下面的4个元组组成的簇中描述了Bletchley
Park和Station X之间的2个不同的关系,如下所示:
总的来说,我们发现样本中大约四分之一的元组是其他元组重新制定的,这些元组包含在过滤后的1130万个元组中的某些地方。根据先前的测量,三分之二的具体实体元组不属于同义簇,根据计算得到,由TEXTRUNNER发现的元组中约92%表达了不同的断言。如前所述,这是对不同实体数量的高估,因此还无法考虑多个实体名称的影响,这也将是以后工作的主题。
4、相关工作
传统的“封闭式”IE的工作在第1节中已经说过了。最近尝试进行大规模提取的工作[Pasca et al,2006]表明对该问题的兴趣在与日俱增。
今年,Sekine[Sekine,2006]提出了“按需信息提取”的范例,该范例旨在消除将IE系统应用于新主题所涉及的定制化。使用无监督学习方法,系统会根据用户指定的主题自动创建模式并执行提取。
同样在今年,Shinyama和Sekine [Shinyama和Sekine,2006]描述了一种“不受限制的关系发现”方法,该方法是独立于我们的工作而开发的,并在28,000条新闻专线文章中进行了测试。这项工作包含了避免关系特定性的重要思想,但是不能扩展到Web,如下所述。
给定一组文档,该系统首先对整个文章集进行聚类,然后将语料库划分为文章集,这些文章集被认为可以讨论相似的主题。在每个群集中,将计算命名实体识别、共指解析和深度语言解析结构,然后将其应用于自动识别实体集之间的关系。如果将这种“繁琐的”语言机制应用到Web上,将会出现问题。
Shinyama和Sekine的系统使用成对矢量空间聚类,最初需要的工作量,其中D是文档数。然后,将分配给簇的每个文档进行语言处理,从而可能导致传输给另一组作为输入文档。对于大型文档收集而言,这比之前介绍的TEXTRUNNER的O(D + TlogT)运行时代价要昂贵得多。
通过收集28,000条新闻专线文章,Shinyama和Sekine能够发现101种关系。尽管很难测量TEXTRUNNER在其9,000,000个网页语料库上发现的确切关系数量,但比101至少大两个或三个数量级。
5、结论
本文介绍了在Web上的Open IE,这是一种无监督的抽取范式,它避免了特定于关系的抽取,而倾向于通过语料库上的单遍抽取,在此过程中可以自动发现并有效存储感兴趣的关系。与传统的IE系统会因命名每个新关系而反复增加语料库分析的成本不同,Open IE的一次性关系发现程序允许用户以交互速度命名和探索关系。
本文还介绍了TEXTRUNNER(一个完全实现的Open IE系统),并展示了其从900万个网页语料库中提取大量高质量信息的能力。我们已经证明,TEXTRUNNER能够与最新的KNOWITALL(最先进的Web IE系统)在召回率上相匹配,同时实现更高的精度。
将来,我们计划集成可扩展的方法来检测同义词和解决TEXTRUNNER中多次提及的实体。该系统还将受益于学习实体类型的能力,这常常是携带在关系中。这将使系统能够区分关系的不同含义,并更好地定位实体边界。最后,我们计划将TEXTRUNNER的元组统一输出为基于图的结构,从而实现复杂的关系查询。