【论文笔记】Preemptive Information Extraction using Unrestricted Relation Discovery

文章目录

1. 1. 核心思想
2. 2. 基本思想
3. 3. 增加基本模式
4. 4. 模型实现
   1. 4.1. 网络爬虫和Basic Clustering
   2. 4.2. Parsing 和 GLARFing
   3. 4.3. 命名体标注和共指解析
   4. 4.4. 基本模式生成
   5. 4.5. Metaclustering
5. 5. 实验与评估
   1. 5.1. 评估方法
   2. 5.2. 结果

2006 NAACL Preemptive Information Extraction using Unrestricted Relation Discovery
使用无限制关系发现的抢先信息提取

核心思想

作者正在尝试扩展信息提取（IE）系统的边界。 现有的IE系统需要大量时间和人力来适应新的情况。 抢先信息提取是尝试事先自动创建所有可行的IE系统，而无需人工干预。 于是提出了一种称为“无限制关系发现”的技术，该技术涵盖了文本中所有可能的关系，并将其显示为表格。 再提出了一个预审系统，该系统获得了相当不错的效果。

基本思想

主要方法使聚类。
在不受限制的关系发现中，发现过程（即创建新表）可以表述为聚类任务。 关键思想是将一组包含彼此之间具有相似关系的实体的文章聚集在一起，以便我们可以构造一个表，在其中将起相同作用的实体放置在同一列中。

假设有文章A和B，两篇文章都报道了飓风相关的新闻。文章A包含了两个实体，Katrina“和”New Orleans”，文章B包含了”Longwang“和”Taiwan”。这些实体通过命名体标注器识别出来。作者的目的是找出这些实体中的一种关系。基本模式是文本的一部分，它在句法上连接到一个实体。例如：”X is hit “ 或者 “Y’s residents.”

图1 展示了文章A中几个连接到实体”Katrina”和”New Orleans“的基本模式。
相似地，在图2中展示了实体”Katrina“和”Longwang”都有共同的基本模式”headed“。

在这个例子中，将两个实体连接起来。此外，”New Orleans“和”Taiwan”都共享一个共同的基本模式”was-hit”。现在，作者发现了两组实体可以在同时用来替换。这个意思就是这两组实体集合（”Katrina“-“New Orleans” 和 ”Longwang“-“Taiwan”）可以表示某个共同的关系：飓风的名字和发生的地点（a hurricane name and the place it affected）。 通过找到两篇文章之间的多个平行对应关系，可以估计它们之间关系的相似性。

通常，在聚类任务中，一个通过查找相似对来对项目进行分组。 找到一对具有相似关系的关节后，我们可以将它们置于同一簇中。 在这种情况下，通过将文章的基本模式用作功能来对文章进行聚类。 但是，每个基本模式仍连接到其实体，因此可以从中提取名称。 我们可以考虑一个基本模式来表示诸如其实体的“角色”之类的东西。 在此示例中，以“前进”为基本模式的实体为飓风，而以“遭受打击”为基本模式的实体为其受影响的地方。 通过使用基本模式，我们可以将实体对齐到表示关系中特定角色的相应列中。 在此示例中，我们创建了一个2乘2的表，其中每一列代表实体的角色，每一行代表不同的文章，如图2的底部所示。

这个表格可以通过找到另外一篇文章来进行扩展。这样，作者逐渐扩展了一个表，同时保留了它的列之间的关系。 在这个例子中，得到的表就是一个建立IE系统(它的任务是查找飓风名称和受影响的地方)。

但是，这些文章可能还包含其他内容，它们可能代表不同的关系。 例如，政府可能会寻求帮助，或者可能已经报告了一些人员伤亡。 为了获得这种关系，我们需要从文章中选择不同的实体。 现有的一些作品试图通过手动选择不同的实体对来提取某种类型的关系s (Brin, 1998; Ravichandran and Hovy, 2002). Hasegawa et al.(2004)试图通过选择实体类型来提取多个关系。 我们假设可以通过尝试预先选择的一组实体中的所有可能组合来找到这种关系。 一些组合可能代表飓风与政府的关系，而其他组合可能代表地点及其人员伤亡。 为了确保文章可以具有多个不同的关系，我们让每个文章都属于几个不同的类。

但是，在真实世界的环境下，如果只使用几种模式，有时候会得到令人失望的结果。比如，“(President) Bush flew to Texas” 和 “(Hurricane) Katrina flew to New Orleans”,两者都有共同的基本模式” flew to“，所以 “Bush” 和 “Katrina” 也许会被分进相同的列中。

但是这种类似的情况需要区分开，所以，为了解决这个问题，作者在聚类时添加了一个额外的规则。作者使用了词袋模型的方法来区分两篇文章：如果两篇文章之间基于单词的相似度太小，则不会将它们放到同一个类（即表格）中。 在此阶段，从相似性计算中排除名称，因为要链接有关相同类型事件而不是相同实例的文章。 另外，我们使用每种基本模式的频率来计算关系的相似性，因为几乎每篇文章中都会出现“ say”或“ have”之类的基本模式，依靠这种表达是危险的。

增加基本模式

在上述的假设中，作者假设能够从一篇文章中获取足够的基本模式。然而，从一篇文章中获取的模式数量通常不太够，因为与表达形式的变化相比，句子的数量很少。 因此，有两篇文章具有多种基本模式的共同之处是非常不可能的。

作者通过使用报告相同事件的一组可比较文章而不是单个文章来扩展获得基本模式的文章数量。 并将此文章集群称为“基本集群”。 使用基本群集代替单篇文章也有助于增加数据的冗余性，可以给重复的基本模式更多的信心。

注意，这里“basic cluster”的概念和上述用来构建表的簇不同。所以作者对此做了区分，用来建表的簇叫做“metacluster”，因为这是”basic clusters”的一个簇。一个”basic cluster”由一系列在相同时间内报道了相同事实的文章组成，而”metacluser”由同一时期包含了相同关系的事实组成。

作者试图通过同时查看多个新闻来源来增加一个基本集群中的文章数量。作者使用了一个向量空间模型在聚类算法中获取基本的cluster。这样，可以增加连接到每个实体的基本模式的数量。 此外，它还使给予实体权重。 我们使用簇（cluster）中出现的次数和它们在文章中的位置来计算它们的权重。 这些实体用于以后获取基本模式。

作者还使用了一个解析器和树正则化器来生成基本的模式。 基本模式的格式对性能至关重要。作者认为基本模式应该有些特定的情况，因为每个模式都应捕获具有相关上下文的实体。 但是同时，基本模式应该足够通用以减少数据稀疏性。 所以作者选择谓词参数结构作为此问题的自然解决方案。 与传统的构成树（constituent trees）相比，谓词-自变量结构是句子的高级表示形式，最近已被自然语言界广泛接受。 在本文中，我们使用了Meyers等人提出的称为GLARF的逻辑特征结构。 （2001a）。

一个GLARF转换器采用一个语法树作为输入，并增加了几个特征，GLARF结构如下图所示。

作者使用GLARF的两个原因：
(1) 与传统的成分分析器不同，GLARF具有规范化几种语言现象的能力，例如参与式构造和协调, 也就允许能够以统一的方式处理这种句法变化。
(2) 输出结构可以很容易地转换成表示每个单词之间关系的有向图，而不会丢失原始句子中的重要信息。
所以，相比于普通的组成数，GLARF能够更容易地抽取句法关系。

模型实现

从未标注文本中生成基本模式和发掘关系的过程如下图所示。

网络爬虫和Basic Clustering

首先，通过Web爬虫从网页上爬取多个领域的新闻文章，网络爬虫爬取文本数据的准确率达90%（也不知道作者怎么算出来的，这里就不细细研究。）。然后，对获得的文章应用了一种简单的聚类算法，以便找到一组谈论完全相同的新闻并形成基本聚类的文章。

先删除停用词，然后去除所有其他词，然后使用词袋模型计算两篇文章之间的相似度。在新闻文章当中，出现在开头的句子通常要比其他句子重要得多。因此，作者保留单词顺序以考虑每个句子的位置。首先，计算每篇文章中的单个词的词向量：

Vw(A)表示的是单词w在文章A的词向量。IDF(w)是单词w的逆文档率，POS(w,A)是一系列w在文章中的位置，然后计算两个向量的相似度（居然是余弦距离相似度…）：

作者花了一天的时间计算出文章中所有可能的对，选择相似度在0.65以上的对来构建basic cluster.

Parsing 和 GLARFing

得到一组基本聚类后，我们将它们传递给现有的统计解析器（Charniak，2000）和基于规则的树归一化器，以获取每篇文章中每个句子的GLARF结构。 GLARF转换器的当前实现使用解析器输出提供了大约75％的F-score。 有关GLARF表示及其转换的详细信息，请参见Meyers et al. (2001b)。

命名体标注和共指解析

在解析和GLARFing并行中，作者还为basic cluster中的每篇文章提供了NE标签和共引用解析。作者使用的是基于隐马尔可夫链的命名体标注器，其F-score是85%。这个命名体标注器生成了ACE-type的命名体，包括：PERSON,ORGANIZATION,GPE,LOCATION 和 FACILITY。在为每篇文章应用单个文档共引用解析之后，我们将同一基本集群中不同文章之间的实体连接起来，以获得具有简单字符串匹配的跨文档共引用实体。

基本模式生成

在获得每个句子的GLARF结构和一组实体被标记并相互连接的文档后，合并两个输出，并创建一个庞大的GLARF结构网络，其节点跨不同的句子/文章相互连接。 现在可以为每个实体生成基本模式。 首先，我们计算一个basic cluster中每个交叉文档实体E的权重如下：

其中 e ∈E，是一篇文章中的一个实体，mentions(e)是提及实体e的文档数目，firstent(e)是实体e在句子中首次出现的次数。C在这个公式中是一个常数值。为了降低组合的复杂性，仅从每个basic cluster中选取五个权重最高的实体来生成基本模式。 我们观察到这五个实体可以涵盖基本群中报告的主要关系。

然后，从GLARF框架中获取基本模式。 只使用每篇文章的前十句来获得基本的模式，因为最重要的事实通常写在新闻文章的前几句中。下图展示了通过”Katrina hit Louisiana’s coast.”来获取基本模式。

阴影节点“Katrina”和“Louisiana”是每个基本模式的实体。 从每个实体节点中走一条GLARF节点的路径，直到它到达任何预测节点：名词、动词或形容词。从节点”hit”和”coast”在例子中是谓词，可以得到三条独一无二的路径：”Louisiana+T-POS:coast（Louisiana’s coast）”，”Katrina+SBJ:hit（Katrina hit something）”和”Katrina+SBJ:hit-OBJ:coast（Katrina hit some coast）”。

为了增加模式的特异性，通过添加立即连接到谓词节点的节点来生成额外的基本模式（从上述的例子中从”Katrina”节点生成了”hit-coast”和”hit”）。

请注意，在GLARF结构中，即使我们提取图形的单路径，每个参数的类型（例如主题或对象）也保留在边缘中。现在，移除”Katrina”和”Louisiana”的实体而换成他们的命名体标注器获得的参数化的模式：”GPE+T-POS: coast（Louisiana’s coast）”,”PER+SBJ:hit（Katrina hit something）”,以及 “PER+SBJ:hit-OBJ:coast”。

Metaclustering

最后，执行 metaclustering 来生成表。首先计算基于basic cluster中两两的相似度。
XA和XB分别是来自basic cluster的cA和cB的跨文档实体的集合。 检查了来自两个基本集群的所有可能的关系映射（多个实体的并行映射），并发现其相似性得分超过特定阈值的所有映射。 词语相似度（cA，cB）是两个聚类的词袋相似度。 作为加权函数，我们使用了ICF：

然后，对所有可能的basic cluster对的相似性进行排序，并尝试通过首先选择连接最紧密的对来构建metacluster。 请注意，在此过程中，可以将一个basic cluster分配给几个不同的metacluster。 当在已经分配给metacluster的两个basic cluster之间找到链接时，我们尝试将其放入其所属的所有现有metacluster群中。 但是，仅当basic cluster可以填充该表中的所有列时，我们才允许添加该群集。 换句话说，前两个basic cluster（即初始的两行表）确定其列，因此定义了该表的关系。

实验与评估

作者使用了12家主要在美国出版的报纸。收集了他们的文章超过两个月（从2005年9月21日-2005年11月27日）。获取了 643767 个基本模式和7990个单独的类型。然后坐着使用了metaclustering应用到 basic cluster中，得到了302个metaclusters(tables)。

然后，移去重复的行，仅取出具有3行或更多行的表。 最终，我们有101张表。 表2显示了作者使用的商品和类的总数。

评估方法

我们对获得的表进行了如下评估。 对于表中的每一行，我们添加了用于提取关系的源文章的摘要。 然后，对于每个表，评估者将查看每一行及其源文章，并尝试提出一个解释其各列之间关系的句子。 描述应尽可能具体。 如果至少有一半的行可以满足预算，则该表被视为“一致”。 对于每个一致的表，评估者使用变量名（$ 1，$ 2，…）记下句子以引用其列。 最后，我们计算了一致表的数量。 我们还计算了每个表中可以容纳多少行。

（人工评估？应该是

结果

我们评估了48个随机选择的表。 在这些表中，我们发现有36个表是一致的。 我们还计算了适合每个描述的行总数，如表3所示。

表4显示了所选表的描述。

最大的一致性表是关于飓风的（表5）。

尽管我们无法精确衡量每个表的召回率，但我们还是尝试通过将飓风表与手动创建的表进行比较来估算召回率（表6）。 我们在9个飓风中发现了6个。在3个飓风名称中，尽管我们的NE标签程序并未将飓风名称与人名区分开，但大多数这些飓风名称都自动进行了歧义消除。 表7显示了第二大表（大约是官方的提名）。