基于卷积树核的无指导中文实体关系抽取研究

黄晨,钱龙华,周国栋,朱巧明

(1.苏州大学计算机科学与技术学院,江苏苏州215006;2.张家港广播电视大学,江苏张家港215600)

1 引言

信息抽取(Information Extraction,IE)[1]的目的是从自由文本中找出用户感兴趣的事件、实体及其关系,并将这些信息以结构化的形式存储在数据库中,为情报分析和检测、自动文摘、文本分类等各种应用提供基础服务。在许多自然语言理解系统中,不但需要识别出文本中的实体(如地名、人名和机构名),而且还要根据上下文来确定这些实体之间所存在的关系,即实体关系抽取,简称关系抽取。一般来说,实体间的关系类型都是预先定义好的,例如文本短语“微软公司执行总裁”中“微软公司执行总裁”和“微软公司”分别为人物(PER)和组织(ORG)实体,两者之间又构成了雇佣关系(Org-Aff.Employment),即“微软公司执行总裁”受雇于“微软公司”。关系抽取不仅是信息抽取中的重要环节,而且在问答系统、知识获取和自然语言接口等应用中也非常重要。

随着近十几年关系抽取技术的不断发展,研究人员提出了众多不同的方法来实现关系抽取。根据它们对语料库的不同需求大致可分成指导性学习方法、弱指导学习方法和无指导学习方法等三大类。

指导性学习方法把关系抽取转换成一个分类问题,利用已标注的语料库训练一个分类器模型(如SVM、W INNOW),然后利用该模型来判别未标注实例的关系类型,代表工作有基于特征向量的方法[2-6]和基于核函数的方法[7-13]。目前指导性关系抽取虽然取得了最好的性能,但是它们需要大规模的人工标注语料库作为训练数据,因而通用性不强。弱指导性学习方法则从少量种子集开始,不断从未标注语料库中抽取出可靠性较高的关系实例来增强训练集,最终期望得到较好的抽取性能,如采用自举方法的DIPRE[14]和Snowball[15],采用协同训练的BootProject算法[16]和标注传播算法[17]。弱指导方法能极大地减少指导性学习方法对大规模标注语料的依赖,其主要问题是初始种子的选择比较困难,对最终的性能影响较大。而无指导学习方法不需要人工标注的语料库,也无需预先定义关系的种类。它通过直接对未标注语料库中的所有关系实例进行聚类,即将具有相似关系的实体对归在一类中,并对它们赋予某一标记。

无指导学习方法由于不需要人工标注的数据,因而可以节省大量的时间和人力。虽然存在着无法自动衡量其抽取性能的缺点,但无指导的学习方法为关系抽取指明了一个新的研究方向。目前的研究方法采用上下文词汇集合[18]或句法树[19]来表示关系实例,然后分别使用词汇相似度和句法树相似度来衡量关系实例之间的相似性,从而实现实体关系的抽取。另一方面,由于基于特征向量的方法很难找出新的有效的词汇、句法和语义等平面特征,因而树核函数特别是能有效捕获结构化特征的卷积树核函数[10-12]在指导性关系抽取中获得了广泛的应用,其抽取性能也不断提高。受卷积树核函数在指导性英文实体关系抽取中的积极作用所启发,本文提出了基于卷积树核函数的无指导中文实体关系抽取方法。其主要思想是首先使用简洁而有效的句法树—最短路径包含树来表示潜在的关系实例,然后再利用卷积树核函数来计算两个句法树之间的相似度,从而实现中文实体关系的抽取。由于卷积树核函数能有效捕获句法树的结构化信息,我们期待该方法能有效实现无指导的关系抽取。

本文的后续内容组织如下：第2节回顾中文实体关系抽取和无指导实体关系抽取方面的相关研究工作;第3节介绍我们所使用的方法;第4节给出实验数据,并进行结果分析;最后为总结全文和指明将来的工作方向。

2 相关工作

从理论上讲,英文实体关系抽取中的方法和原理都可以使用在中文实体关系抽取的研究中,但是,一方面由于中英文在语法结构上的诸多不同,另一方面,中文实体关系抽取研究的起步也较晚,因此其方法基本上都集中于指导性的统计机器学习方法,包括基于特征向量的方法和基于核函数的方法两大类。

对于基于特征向量的中文实体关系抽取而言,其关键问题仍然是如何选择有效的词汇、句法和语义等特征,如车万翔等[20]提取了实体的类型/小类、两个实体间的位置关系、两个实体前后的词汇等信息;董静等[21]进一步将关系实例划分为包含实体关系和非包含实体关系,并对非包含实体关系进一步加入了句法结构信息(如两个实体的祖先节点、实体之间的路径、依存动词及实体到依存动词的路径等);Li等[22]则进一步探索了实体间的结构关系(如包含关系、邻近关系和分隔关系等)对抽取性能的影响,同时采用基于字的一元或二元上下文特征以避免中文分词错误所产生的影响。

在基于核函数的中文实体关系抽取方法中,Che等[23](编辑距离核)和刘克彬等[24](字符串核)的核函数都是基于比较中文词串的相似度,并在比较过程中考虑了一定的词汇语义相似度。Huang等[25]初步探索了卷积树核函数和最短依存树核函数在中文实体关系抽取中的应用,但其性能极低(F指数约为30)。当然,这并不说明核方法本身存在问题,而只能说明在中文关系抽取中较难找到能合理和确切表示实体关系的结构化信息以及结构化信息的相似度计算方法。

在无指导关系抽取的研究方面,H asegawa等[18]首先识别出文本中的命名实体及其类型,当实体对的共现频率超过一定阈值时,把它们作为一个潜在的实体关系,并通过计算实体对之间的词汇相似度的方法进行聚类,然后给每个发现的实体关系赋予一个合适的类别名称。在1995年《纽约时报》语料上的测试表明,应用该方法发现公司实体对(COM-COM)之间的关系,F指数可达到75。不过,该方法不考虑出现次数少于30的命名实体对,因而湮灭了这些命名实体对之间潜在的关系。

Zhang等[19]通过计算包含实体对的句法树的相似度进行聚类,探讨了无指导学习方法在关系抽取中的应用。在同样的1995年《纽约时报》语料上,该方法能有效地发现高频和低频命名实体对之间的关系,相比 Hasegawa等[18]的实验结果,其F指数提高了5。但在无指导关系抽取中,聚类数目的确定和代表关系类别的词汇选择方面仍然存在着问题。

Chen等[26]在确定命名实体对之间关系的数量和特征集大小时,采用多次取样方法(Resamp le)通过反复的实验寻找目标函数的最优值,从而找到最自然的关系个数及其相对应的特征集,然后利用判别类型匹配方法(DCM)选择最重要的词汇特征作为某类关系的名称。在ACE语料库上的实验表明,该方法在PER-ORG、ORG-GPE和ORG-ORG实体对之间的关系抽取的准确率分别为41.3%、50.6%和42.4%,同Hasegawa等(2004)[18]的方法相比,性能有大幅度的提高。

在中文实体关系抽取方面,目前还没有采用无指导学习方法的相关研究工作。同时,由于卷积树核函数在英文实体关系抽取中取得了一定的成功,因此本文采用卷积树核函数的方法来实现无指导的中文实体关系抽取,其关键问题是如何选择合适的结构化信息来表示中文实体关系实例以及采用什么样的聚类方法,本文就这两方面展开研究。

3 基于卷积树核的无指导学习

基于树核函数的无指导实体关系抽取,第一步是如何表示关系实例的结构化信息和计算结构化信息之间的相似度;第二步是在关系实例的相似度基础之上,对实体对进行聚类,即将相似的实体对归为相同的簇(即实体关系类别),从而实现实体关系的抽取。

3.1 关系实例的结构化表示

Zhang等[10]最早研究了从包含两个实体的最小完全树(MCT)中抽取出5种结构化子树用于表示关系实例的方法,其中两个实体之间的最短路径包含树(SPT)取得了最好的性能。Zhou等[11]在SPT树的基础上动态扩充与谓词连接有关的上下文相关信息,产生了上下文相关的最短路径包含树(CS-SPT),抽取性能得到了进一步的提高。Qian等[12]则利用成分依存关系来决定最小完全树中的哪些成分对实体关系是有用的,从而形成一棵能有效捕获关系实例结构化信息的动态句法树(DSPT)。尽管这些结构化表达方式对指导性关系抽取的最终性能存在着一定的影响[12],但是考虑到我们要研究的主要问题是树核函数在无指导关系抽取中的有效性,为了处理的简化起见,我们采用比较方便但仍然有效的表达方式—最短路径包含树。

图1显示了在短语“…将恐怖分子从监狱当中释放出来…”中实体“恐怖分子”(PER)和“监狱”(FAC)之间的关系实例的结构化表示形式。其中T1为最小完全树,T2为经过裁剪后的最短路径包含树,即在最小完全树中两个实体之间的最短路径(“E1—NP—VP—PP—NP—E2”)所包含的子树。

图1 关系实例的结构化信息表示(SPT)

3.2 树的相似度计算

在得到了关系实例的结构化信息之后,下一步要解决结构化信息之间的相似度计算问题。卷积核函数用离散对象的子结构来捕获它们之间的结构相似性,如句法树核函数、字符串核函数和图形核函数等。我们采用Co llins和Du ffy[27]的卷积树核函数(Convolution Tree Kernel,CTK)来计算两棵树之间的相似度,即通过计算它们之间的相同子树的数目来衡量它们之间的相似度,其公式为：

其中 N1和N 2分别为T1和 T2的节点集合,Δ(n1,n2)用来计算以n1和n2为根节点的两棵子树之间的相似度,它可以通过下列递归的方法得出：

1)如果和的产生式(采用上下文无关文法)不同,则 Δ(n1,n2)=0;否则转 2);

2)如果和是词性(POS)标记,则 Δ(n1,n2)=1×λ;否则转3);

3)递归计算下式：

其中#ch(n)是节点的子节点数目,ch(n,k)是节点的第k个子节点,而λ(0<λ<1)则是衰减因子,用来防止子树的相似度过度依赖于子树的大小。

由于卷积树核函数能有效捕获离散数据对象中的结构化信息,因而在信息抽取以及自然语言处理的其他领域中取得了广泛的应用,如语义角色标注和指代消解等。

3.3 关系实例的聚类

聚类[28]的目的是将一组对象划分成若干组或类别,即相似元素同组、相异元素不同组。本质上说,聚类是指根据样本之间的某种距离在无指导条件下的聚簇过程。聚类算法一般可分为两大类：层级聚类和非层级聚类。其中层次聚类的特点是每个节点都是其父类的一个子类,聚类结果通常可以表示成树图的形式;非层次聚类则类别结构简单,类别之间没有层次关系,非层次聚类中最典型的算法是K-means算法。不过,由于K-means算法中的数据必须表示成欧氏空间的特征向量,而本文采用树结构来表示关系实例,因此采用层次聚类算法比较适合,采用层次聚类的另一个好处是不用预先定义聚类的簇数量。

在层次聚类算法中需要用到两个聚类簇之间相似度的计算方法,由于一个簇中含有多个关系实例,因此可以选择下列三种簇相似度计算方法：

单连通：计算两个簇之间最相似样本之间的相似度;

全连通：计算两个簇之间最不相似样本之间的相似度;

平均连通：计算两个簇之间所有样本的平均相似度。

4 实验结果及分析

本节首先说明本文实验所使用的语料库及评测指标,然后再对实验结果进行分析和讨论。

4.1 实验设置

本文使用ACE RDC 2005中文标注语料库作为无指导关系抽取的实验数据。ACE RDC 2005语料库共包含633篇文档,其中BNEWS有238篇,NW IRE有298篇,WEBLOG有97篇。我们对这些文档进行了预处理,由于单句字数过多和句法错误等原因过滤掉了101篇,最终从中选取了532个文档,其中标注有关系的实体对(即关系正例)为7 630个,没有关系的实体对(即关系负例)为83 063个。ACE RDC 2005中文语料库的实体关系类型共有6个大类,36个小类。由于关系负例之间的结构差异很大,因此本文聚类的对象仅局限于关系正例。表1列出了各个关系大类实例数量的分布情况,从中可以看出其分布是不均匀的。

表1 ACE RDC 2005中文语料库关系实例统计信息

ACE RDC 2005语料库的原始形式是SGM L(Standard Generalized M ark-up Language)文件,即实体及其关系的标注信息是通过SGM L标记插入到文本中的。为了便于句法分析,我们首先将标注信息和纯文本分离开来,其中标注的实体及其关系实例存放到单独的标注文件中;然后对剩余的纯文本进行分句和分词,再将分词后的句子进行句法分析,从而得到每个句子的句法树;最后对每个句子中出现的所有实体进行两两配对,如果一个实体对存在关系,则它所对应的最短路径包含树及其相对应的关系类型加入到实验数据中。

本文所采用的基于卷积树核的相似度计算工具来自于SVMLight-TK①http：//dow nload.joachims.org/svm_ligh t/curren t/svm_ligh t.tar.gz.,其中的衰减因子λ采用默认值(即0.4)。不过,我们仅抽取其中与树的相似度计算相关的部分代码。聚类算法软件包采用东京大学的C/C++聚类库函数②http：//bonsai.im s.u-tokyo.ac.jp/ ～ mdehoon/software/cluster/cluster-1.46.tar.gz.,该软件包支持K-m eans聚类、层次聚类等功能。不过,由于它不直接支持采用树结构形式的数据实例,因此我们首先计算好关系实例两两之间的相似度,然后再把这些数值输入到聚类软件包中,并分别用三种簇相似度计算方法(单连通、完全连通和平均连通)进行层次聚类。

4.2 评测指标

对于无指导的关系抽取,一般采用与指导性关系抽取相类似的性能评测指标,如准确率(P recision)、召回率(Recall)和 F值(F-Score)等。与关系抽取不同的是,在关系聚类中,一个聚类簇内的关系实例的正确类别不是由它自身的关系类别所决定,而是由该簇的大多数实例的关系类别所决定。具体而言,假设经过聚类后得到N个簇(1,2,…,N),若某一簇中的大多数关系实例都属于表1中的某一类别,则该类别被认为是该簇的关系类别,最后,若两个簇的关系类别相同,则将他们合并为一个簇。

本实验评测指标与Hasegaw a[18]的指标基本相同,具体描述如下：

其中 Ncorrect为某一簇中被正确分类的实例数量,Nincor rect为该簇中被错误分类的实例数量,而Nkey为语料库中具有该簇类别的实例总数。由于相同类别的簇最终会被合并,因此聚类后的簇的数量总是不大于语料库中实际关系类别的数量。与Hasegawa等[18]方法不同的是,以上方法计算出的指标是针对某一类别的,对于最后的平均性能,我们采用对各类别进行加权平均的方法来获得Pavg与Ravg,然后再计算出Favg。

4.2 实验结果及分析

图2比较了聚类簇的数量对单连通聚类、全连通聚类和平均连通聚类关系抽取的性能影响。

图2 簇的数量对两种聚类算法的性能影响(F指数)

为了说明问题的方便,仅列出了相应的平均F指数。从图中可以看出,单连通聚类的性能与全连通聚类和平均连通聚类的性能相差较大,这是由于单连通聚类只考虑了两个簇之间最相似样本之间的相似值,随着簇内部样本数量的增加,这个度量值越来越偏离实际情况;同时,后两者的加权F平均值最高分别达到了58.8和60.1,这表明基于卷积树核的方法在无指导的中文实体关系抽取中是有效和可行的。针对全连通聚类和平均连通聚类,可以看出：

(1)随着聚类簇数量的增加,两种聚类算法的最终性能基本呈上升趋势。这是由于聚类的粒度越大(即簇数量越小),则不同类别的关系实例被聚类于同一簇中的概率也就越大,因而其总体性能也就越低。

(2)平均连通聚类在性能上要普遍优于全连通聚类(除了簇数量为18以外),不过随着簇数量的增加,两者的差距明显缩小直至基本相同。这是由于全连通聚类考虑的是两个簇之间最不相似样本之间的相似度,当簇数量较少时,每一簇内的实例数量较多,它们之间的差异也越大,全连通方法所得到的相似度误差也就越大;而平均连通聚类采用的是两个簇之间样本相似度的平均值,因此即使在簇数量较少时,也能在一定程度上较好地反映出簇之间的相似度。但是,当簇的数量增加时,每一簇内的实例数量变少,它们之间的差异也变小,因而即使是全连通方法也能较好地刻划簇之间的相似度,所以两者之间的性能差距接近。

(3)当簇的数量达到36时,两种聚类算法均取得较好的性能,而当簇数量再进一步增加时,聚类性能变化不大,甚至略微减少。一种合理的解释是由于ACE RDC 2005语料库将6个关系大类进一步划分为36个关系子类,因而簇数量为36时最能体现关系实例的自然簇结构。当簇的数量再进一步增加时,一个小类中的实例或许被强行聚类到不同的簇中,但这并不能提高聚类的性能。这在另一方面也说明在ACE RDC 2005语料库中的关系类别定义还是相当合理的。

图3 簇的数量对各大类关系识别的性能影响(平均连通聚类)

图3比较了在平均连通聚类中簇的数量对各个关系大类聚类性能的影响,仍然采用F指数来衡量。从图中可以看出,其变化趋势与平均性能变化趋势基本一致。特别地,Physical,Part-w hole和ORG-A ffiliation等三个关系类别的聚类性能较好,其在簇数量为36时的F指数分别达到了 59.0、69.6和65.9,这主要是由于这三个大类的关系实例数量较多并且其内部结构一致性较好的原因。

由于目前还没有相关的无指导中文实体关系抽取系统,因此我们在表2中比较了无指导关系抽取和下列两种方法之间的性能差别：

◦基准(Baseline)方法：基于特征向量的中文实体关系聚类,采用Zhou等[4]的方法从文本中抽取出词汇、实体、重叠、语块等特征构成特征向量,然后计算特征向量之间的相似度,再以此为基础进行单连通、平均连通和全连通等层次聚类。实验表明,当采用全连通聚类方法、簇的数量为36时,聚类性能F值取得最高值56.7;

◦指导性关系分类方法：在所有关系正例上进行关系分类的 5倍交叉验证。首先将实例集(7 630个实例)分成大小相同的5份,每次取4份作为训练集,用基于树核的分类器SVMLight-TK训练出一个模型,然后在剩余一份上进行测试,计算出关系分类的一次性能,最后取5次实验的平均值。

从表2中可以看出,相对于基于特征向量的方法而言,基于卷积树核的无指导关系分类取得了一定的进步,F值提高了约3点,这主要是由于难于获得有效的平面特征来表示中文实体关系实例,而卷积树核能有效地捕获实体关系的结构化特征,同时也说明基于树核的层次聚类方法对于无指导中文关系抽取具有一定的有效性。不过,同指导性关系抽取相比差距仍很大,F值低约17点。由于关系抽取在自然语言处理领域是一个相当困难的问题,特别是对于中文实体关系,与英文实体关系抽取相比,指导性抽取方法尚且还不能取得令人满意的结果,因此今后仍需进一步提高指导性中文实体关系抽取的性能。

表2 中文ACE 2005关系抽取性能比较

5 结论

本文提出了一种基于卷积树核的无指导中文实体关系抽取方法,以最短路径包含树来表示关系实例的结构化信息,采用卷积树核函数来计算结构化信息之间的相似度,然后使用单连通、全连通和平均连通三种分层聚类算法来实现无指导的中文实体关系抽取。在ACE RDC 2005中文语料库上的实体关系聚类实验表明,聚类簇的数量对各关系大类乃至整个关系抽取的性能具有很大的影响。特别地,当聚类簇数量为预定义的关系小类数量时,全连通聚类和平均连通聚类的F加权平均值取得了较高值,分别达到了58.8和60.1,这些结果表明基于卷积树核的方法在无指导的中文实体关系抽取中能有效捕获关系实例的自然簇结构,在一定程度上是行之有效的。

我们下一步的工作是对未标注的中文语料库进行实体关系聚类,并进行聚类簇的标记,即给每一个簇赋予一个合理的关系名称,同时对不可靠的簇进行修剪,进一步提高无指导中文实体关系抽取的实用性。

[1] 李保利,陈玉忠,俞士汶.信息提取研究综述[J].计算机工程与应用,2003,39(10)：1-5.

[2] Kambhatla N.Combining lexical,syntactic and semantic featuresw ith Maximum Entropy mode ls for extracting relations[C]//ACL-2004(Poster)：178-181.

[3] Zhao S B and G rishman R.Ex tracting relations w ith integrated information using kernel-basedmethods[C]//ACL-2005：419-426.

[4] Zhou G D,Su J,Zhang Jand Zhang M.Exp loring various know ledge in re lation ex traction[C]//ACL-2005：427-434.

[5] Jiang J and ZhaiC X.A Systematic Exploration of the Feature Space for Relation Extraction[C]//NAACLH LT-2007：113-120.

[6] 奚斌 ,钱龙华 ,周国栋 ,等.语言学组合特征在语义关系抽取中的应用[J].中文信息学报,2008,22(3)：44-49,63.

[7] Zelenko D,Aone C and Richardella A.Kernel-based methods for relation extraction[J].Journal of Machine Learning Research,2003,3(Feb)：1083-1106.

[8] Cu lotta A and Sorensen J.Dependency tree kernels for relation ex trac tion[C]//ACL-2004：423-429.

[9] Bunescu R and Mooney R J.A shortest path dependency kernel for relation extraction[C]//H LT-EMNLP-2005：724-731.

[10] Zhang M,Zhang J,Su Jand Zhou G D.A Composite Kernel to Ex tract Relations betw een Entities w ith both Flat and Structured Features[C]//COLINGACL-2006：825-832.

[11] Zhou G D,Zhang M,Ji D H,Zhu Q M.Tree Kernel-based Relation Ex traction w ith Context-Sensitive Structured Parse T ree In formation[C]//EMNLPCoNLL-2007：728-736.

[12] Qian L H,Zhou G D,Zhu QM,Qian PD.Exploiting constituent dependencies for tree kernel-based semantic re lation extraction[C]//COLING-2008：697-704.

[13] 庄成龙 ,钱龙华 ,周国栋.基于树核函数的实体语义关系抽取方法研究[J].中文信息学报,2009,23(1)：4-8,34.

[14] Brin S.Extracting patterns and relations from the World W ide Web[C]//Proceedings of WebDBWorkshop at 6th International Conference on Extending Database Technology(EDBT'98),1998.

[15] Agichtein E and G ravano L.Snow ball：Ex tracting Relations from Large Plain-Tex t Co llec tions[C]//Proceedings of the fifth ACM conference on Digital libraries,2000.

[16] Zhang Z.W eak ly supervised relation classification for Information Extraction[C]//CIKM-2004：581-588.

[17] Chen JX,Ji D H and Tan C L.Relation Extraction using Label Propagation Based Sem i supervised Learning[C]//COLING-ACL-2006：126-139.

[18] H asegawa T,Sekine S and Grishman R.Discovering Relations among Named Entities from Large Corpora[C]//ACL-2004：415-422.

[19] Zhang M,Sun J,Wang D M,eta l.Discovering Relations betw een Named Entities from a Large Raw Corpus Using T ree Sim ilarity-base Clustering[C]//IJCNLP-2005：378-389.

[20] 车万翔,刘挺,李生.实体关系自动抽取[J].中文信息学报,2005,19(2)：1-6.

[21] 董静,等.中文实体关系抽取中的特征选择研究[J].中文信息学报,2007,21(4)：80-85,91.

[22] LiW J,Zhang P,Wei F R,H ou Y X and Lu Q.A Novel Feature-based A pp roach to Chinese Entity Relation Extraction[C]//ACL-2008(short paper)：89-92.

[23] Che W X,et a l..Im proved-Edit-Distance Kernel for Chinese Relation Ex trac tion[C]//IJCNLP,2005：132-137.

[24] 刘克彬,等.基于核函数中文关系自动抽取系统的实现[J].计算机研究与发展,2007,44(8)：1406-1411.

[25] H uang R H,Sun L,Feng Y Y.Study of Kernel-Based Methods for Chinese Relation Extraction[C]//LNCS(Lecture Notes in Computer Science),2008(4993)：598-604.

[26] Chen J X,Ji D H,Tan C L,et a l.Unsupervised Feature Selection for Relation Extraction[C]//CIKM-2007：411-418.

[27] Collins M and Duffy N.Convolution Kernels for Natural Language[C]//N IPS-2001：625-632.

[28] Christopher D.Manning,H inrich Schtze.Foundations of Statistical Natural Language Processing[M].Beijing：Pub lishing House of Electronics Industry,2005.