论文笔记7：Simple Algorithms for Complex Relation Extraction with Applications to Biomedical IE

论文笔记：Simple Algorithms for Complex Relation Extraction ·1234with Applications to Biomedical IE

提出将多元关系抽取转化为二元关系抽取，应用到的是一个句子，但作者提出扩展到跨句子抽取很容易。本文发表于2005年，属于早期论文。

一、论文要解决的问题

生物医学数据的快速发展，让利用计算机技术提取有用信息变得可能。论文提出，以往得研究点都是集中在特定领域的二元关系抽取 ，并且取得了不错得成绩。但是多元关系抽取研究还属于盲区，所以提出了一个简单的算法来抽取复杂关系，并将其定义为n-ary关系抽取。

二、问题提出的方法

2.1 一些定义：

定义模式(t1,t2,…,tn)$(t_1,t_2,\dots ,t_n)$ ，其中ti∈T$t_i\in T$ ，T$T$ 是实体类型。一个关系的实例就是一个实体(e1,…,en)$(e_1,\dots ,e_n)$ 集合，其中ei$e_i$的类型等于ti$t_i$或者ei=⊥$e_i=\perp$ ，⊥$\perp$ 表示实体集合的第i$i$th个元素缺失掉了。

2.2 复杂关系

第一步：将可能相关的实体对构建为一个图

定义一个图G = （V，E），其中V代表边，E代表节点，每条边E连接一个实体对(u,v)$(u,v)$。实体作为图的节点E，一对有关系的实体对之间的连线作为图的边V。

第二步：计算图中的最大团，作为候选复杂关系实例

定义G’ =（V’, E’）是图G的子图，其中V′∈V,E′=(u,v):u,v∈V′,(u,v)∈E$V^{\prime }\in V,E^{\prime }=(u,v):u,v\in V^{\prime },(u,v)\in E$。最大团是图G的子集，并且每一个节点之间都有边连接。

2.3 方法

• 首先将复杂关系因式分解为多个二元关系的集合。
• 然后使用标准的已经训练好的分类器来识别所有实体的实体对。
• 基于上面产生的实体对来构建图，复杂关系由这个图的最大团来决定。

2.4 举例

如上图所示，句子为”JohnandJaneareCEOsatInc.Corp.andBiz.Corp.respectively$JohnandJaneareCEOsatInc.Corp.andBiz.Corp.respectively$”

左边是所有的关系实例，右边是所有的二元关系。

二元关系的工作，不做详细介绍，可以看以前的论文。推荐几篇如下：

• 标准最大熵分类， Berger et al., 1996
• Zelenko et al. (2003)
• Miller et al. (2000)
• Roth and Yih (2004)
• McDonald et al. (2004a)

上图左边是由前面关系构成的图，右边是图中的团构成的元组。

2.4 重构复杂关系

将复杂关系转变为二元关系以后，如何重构复杂关系是一个难点。本文提出的方法如下：

前面构建的图为无向图，顶点为实体，边代表实体间的二元关系。

作者通过找到一个图中的最大团来重新构建复杂关系。这相当于让系统只返回二元分类器认为所涉及的所有实体都是成对相关的关系。

这里将产生另外一个问题，即团重叠，意思是会产生很多重复或者冲突的团。比如(John,CEO,Inc.Corp.)and(John,CEO,⊥)$(John,CEO,Inc.Corp.)and(John,CEO,\perp )$ 。这里作者解决这个问题的办法是，不返回所有的团，而是返回最大团，即某个团不是另外某个团的子集，这样能最大程度解决这个问题。

一个图产生的团是指数级的，但是有算法可以非常效率的找到最大团，此算法为Bron and Kerbosch(1973)， 这是一种分支限界算法，算法时间复杂度可以达到O(3^(n/3))。

最大团问题 中文博客参考https://www.cnblogs.com/zhj5chengfeng/p/3224092.html

2.5 概率团

前面的方法提出基于二元关系分类结果都是绝对正确的，但实际上不是，为了解决这个问题，为图的每条边设置一个权重，然后求一个团的所有权重的几何平均。

并且，设置一个阈值，文中定为0.5，大于这个值的才是合法的团，否则抛弃掉。

三、优点与缺点

3.1 优点

1. 将复杂关系分解为二元关系的主要优点是它允许使用标准分类算法来决定特定的实体对是否相关，而二元关系研究已经比较成熟
2. 简化了运算复杂度

3.2 缺点

1. 只使用了最简单的二元关系分类器进行测试
2. 没有在其他更多的数据集测试
3. 关系的参数数量必须提前确定（即必须提前知道有哪些关系模式）