卢靖宇作者西安电子科技大学硕士学校自然语言处理研究方向

ACL 2018论文解读 | 基于排序思想的弱监督关系抽取选种与降噪算法

本期推荐的论文笔记来自 PaperWeekly 社区用户 @hawksilent本文创造性地将 Bootstrapping 关系提取中的自动选种任务,以及远程监督关系提取中的降噪任务看成是根据不同的排序标准进行排序的问题,提出了多种兼具自动选种和数据降噪功能的策略。

文章的贡献主要有以下几点:

1. 创造性的将关系提取中的自动选种和数据降噪任务转换成排序问题;

2. 提出多种既可用于 Bootstrapping 关系提取自动选种,又能用于远程监督关系提取降噪的策略;

3. 在收集自 Wikipedia 和 ClueWeb 的数据集上,通过实验证实提出的算法的实用性和先进性。

引言

最近阅读了 Ranking-Based Automatic Seed Selection and Noise Reduction for Weakly Supervised Relation Extraction 这篇文章,该工作来自于 Nara Institute of Science and Technology,发表在 ACL 2018。

这篇文章主要对弱监督关系提取中两个相关的任务展开研究:

  • Bootstrapping 关系提取Bootstrapping RE)的自动选种任务;

  • 远程监督关系提取(Distantly Supervise RE)的降噪任务。

文章受到 Web 结构挖掘中最具有权威性、使用最广泛的 Hypertext-induced topic search(HITS)算法,以及 K-means、潜在语义分析(LSA)、非负矩阵分解(NMF)等聚类中心选择算法的启发,提出一种能够从现有资源中选择初始化种子、并降低远程标注数据噪声的算法。

实验证明,该算法的性能要好于上述两个任务的基线系统。下面是我对这篇文章的阅读笔记。

问题引入

Bootstrapping RE 算法是机器学习中一种比较常用的弱监督学习方法。首先,利用一个称作“seeds”的小实例集合进行初始化,用以表示特定的语义关系;然后,通过在大规模语料库上迭代获取实例和模式,以发现与初始化种子相似的实例。该算法性能的主要制约因素在于语义漂移问题,而解决语义漂移问题的一种有效手段就是选择出高质量的“seeds”。 

Distantly Supervise 技术是一种用于构建大规模关系提取语料库的有效方法。然而,由于错误标注问题的存在,远程监督获取的语料常常包含噪声数据,这些噪声会对监督学习算法性能造成不良影响。因此,如何降低错误标注带来的数据噪声,就成为了远程监督技术的一个研究热点。

问题转化

表示目标关系的集合,每一种目标关系由一个三元组集合 Dr= {(e1, p, e2)} 来表示。其中,e1 和 e2 表示实体,实体对 (e1,e2) 被称为实例,p 表示连接两个实体的模式。例如,三元组 (Barack Obama, was born in, Honolulu),(BarackObama, Honolulu) 表示一个实例,“was born in”表示模式。 

结合上述概念文章将所研究的两个关系提取任务分别定义如下: 

Bootstrapping RE 的自动选种任务:以目标关系集合为输入,针对每一个,从由数据集中提取出的三元组集合 Dr 的实例中,选出能使 Bootstrapping RE 算法高效工作的种子。 

Distantly Supervised RE 的降噪任务:从由 DS 自动为每个关系生成的三元组集合 Dr 中,过滤出所包含的噪声三元组(错误标注三元组)。 

由以上两个任务的描述可以发现,无论是选种还是降噪都是从给定的集合中选出三元组。从排序的角度来看,这两个任务实质上拥有相似的目标。

因此,文章将这两个任务分别转换为:在给定三元组集合 Dr(可能包含噪声)的情况下,实例 (e1,e2 )的排序任务(选种)和三元组 (e1, p, e2 ) 的排序任务(降噪)。

在选种任务中,使用排名最高的 k 个实例作为 bootstrapping RE 的种子。同理,在降噪任务中,对于 DS 生成的三元组,使用其中排名最高的 k 个三元组来训练分类器(降噪任务中的 k 值可能远远小于选种任务中的 k 值)。

自动选种和降噪算法

文章提出的算法受到了 Hypertext-induced topic search(HITS)算法,以及 K-means、潜在语义分析(LSA)、非负矩阵分解(NMF)等聚类中心选择算法的启发。

该算法根据具体的任务来决定是选择实例还是选择三元组:实例用于自动选种任务,三元组用于降噪任务。由于实例即为实体对,而实体对又包含在三元组中,因而可以通过实例和三元组之间的转换,灵活的将提出的方法分别应用到两个任务中。

基于K-means的算法

文章提出的基于 K-means 的算法具体描述如下:

1. 确定需要选择的实例/三元组的数目 k;

2. 运行 K-means 聚类算法将输入的三元组中的所有实例划分为 k 个簇,每个数据点通过其对应实体间的嵌入向量差来表示。例如,实例 I=(Barack Obama,Honolulu) 对应于 vec(I)=vec("Barack Obama")-vec("Honolulu");

3. 从每个簇中选出最接近质心的实例。

基于HITS的算法

Hypertext-induced topic search(HITS)算法又称为 hubs-and-authorities 算法,它是一种广泛用于对 web 页面排序的链接分析方法。

该算法的基本思想是:利用 Hub 页面(包含了很多指向 Authority 页面的链接的网页)和 Authority 页面(指与某个主题相关的高质量网页)构成的二部图,计算每个节点的枢纽度(hubness)得分,然后据此对网页内容的质量和网页链接的质量做出评价。 

对于第 2 节描述的两个任务,可通过实例 (e1,e2) 和模式 p 的共生矩阵 A 生成两者的二部图,进而即可利用 HITS 算法的思想计算两者的 hubness 得分。

文章提出的基于 HITS 思想的选种策略描述如下:

1. 确定要选择的三元组的数目 k;

2. 基于实例-模式的共生矩阵 A 构建实例和模式的二部图。下图所示为构建二部图的三种可能思路。思路一:将每一个实例/模式均作为图中的一个节点。思路二:将实例和模式分别作为边和节点。思路三:将实例和模式分别作为节点和边;

3. 对于思路一和思路三,仅保留 hubness 得分最高的 top k 个实例作为输出。对于思路二,选择与得分最高的模式相关联的 k 个实例作为输出。

基于HITS和K-means的方法

该方法将 HITS 算法和 K-means 算法组合使用。首先,基于实例和模式的二部图对这两者进行排序;然后,在标注数据集上运行 K-means 算法对实例进行聚类。之后,与常规思路不同,这里不选择距离质心最近的实例,而是选择每个簇中 HITS 算法 hubness 得分最高的实例。

基于LSA的算法

潜在语义分析(LSA)是一种被广泛应用的多维数据自动聚类方法,该方法利用奇异值分解(Singular value decomposition,SVD)算法构建实例-模式共生矩阵 A 的等价低秩矩阵。

所谓 SVD,是将矩阵

分解为三个矩阵的乘积:SVD 实例矩阵,奇异值对角矩阵,SVD模式矩阵:  

本文提出的基于 LSA 的选种策略具体描述如下:

1. 指定需要的三元组数目 k;

2. 利用 LSA 算法将实例-模式的共生矩阵 A 分解为矩阵 I、S、P。将 LSA 的维度设置为 K=k;

3. 将 LSA 看作软聚类的一种形式,其中 SVD 实例矩阵 I 的每一列对应一个簇。之后,从矩阵 I 的每一列选出绝对值最高的 k 个实例。

基于NMF的方法

非负矩阵分解(Non-negative matrix factorization,NMK)是另外一种用于近似非负矩阵分解的方法。非负矩阵可以近似表示为这两个因子的乘积: 

非负约束(non-negativity constraint)是 NMF 与 LSA 之间的主要区别。与基于 LSA 的方法类似,NMF 算法先将期望选择的实例数目设置为 K=k。之后,从矩阵 W 的每一列中选出值最大的 k 个实例。

实验

数据集与设置

文章使用了一个局整关系的标注数据集做为种子选择的来源。该数据集提取自 Wikipedia 和 ClueWeb。这里,所谓的局整关系并不是指某一种具体的关系,而是指一种类型的关系集合,如下表所示。

表中显示出了局整关系集中 8 种子关系出现的频率。数据集中 8 种子关系共有 5727 个标注实例。文章通过使用 Precision@N 来衡量提出的模型性能,其中取 N=50。实验中 k 的值在区间 [5,50] 内以 5 为步长逐步递增,对于每个选种方法给出其 P@50 的值。 

在降噪任务中,文章使用由 (Riedel et al., 2010) 开发的训练集和测试集,该数据集是通过将 Freebase 关系与纽约时报语料库对齐而生成的,包含53 种关系类型。在使用提出的方法从数据集中滤除噪声三元组之后,文章使用过滤后的数据对两种卷积神经网络模型(CNN)进行了训练:一种是 (Zeng et al., 2014) 提出的 CNN 模型,一种是 (Zeng et al., 2015) 提出的 PCNN 模型。 

表中显示出了局整关系集中 8 种子关系出现的频率。数据集中 8 种子关系共有 5727 个标注实例。文章通过使用 Precision@N 来衡量提出的模型性能,其中取 N=50。实验中 k 的值在区间 [5,50] 内以 5 为步长逐步递增,对于每个选种方法给出其 P@50 的值。 

在降噪任务中,文章使用由 (Riedel et al., 2010) 开发的训练集和测试集,该数据集是通过将 Freebase 关系与纽约时报语料库对齐而生成的,包含 53 种关系类型。在使用提出的方法从数据集中滤除噪声三元组之后,文章使用过滤后的数据对两种卷积神经网络模型(CNN)进行了训练:一种是 (Zeng et al., 2014) 提出的 CNN 模型,一种是 (Zeng et al., 2015) 提出的 PCNN 模型。

自动选种算法性能

选种算法的实验结果如下表所示。对于基于 HITS 的算法和基于 HITS+K-means 的算法,文章给出了相应的 P@50(分别采用 3.2 节介绍的三种构图思路),实验中使用随机种子选择做为对比基线。

观察实验结果发现,随机选种性能最差,为 0.75;基于 HITS 的策略、基于 LSA 的策略和基于 NMF 的策略,三种算法性能相当,都超过了基线算法;对于基于 HITS 的策略,三种不同的构图思路中,思路一和思路三性能提升明显,思路二性能虽有提升但效果明显低于其他两种策略;将 HITS 策略(构图思路分别采用思路一和思路三)与 K-means 算法结合得到的性能在提出的算法中最佳。

HITS 策略中思路二效果不佳的原因在于:一个模式可能含有歧义,因而链接到该模式的实例可能并不与其匹配,这说明依靠实例选种要好于依靠模式选种。

降噪算法性能

在降噪实验中,文章分别采用基于 HITS、LSA 和 NMF 的算法,下表为各算法对于 CNN 和 PCNN 模型带来的性能提升。表中最右边一列为集成算法的性能,该方法结合基于 HITS 和基于 LSA 的策略,其中,一半的三元组来自基于 HITS 的算法,另一半三元组来自基于 LSA 的算法。

观察实验结果发现,基于 HITS 的策略表现最为稳定,对于四种模型都能提升其性能;基于 LSA 的策略,与注意力机制(无论模型是 CNN 还是 PCNN)结合使用时性能提升明显,但与多实例学习算法结合使用则效果变差,甚至还要低于原始模型;基于 NMF 的策略,对于 PCNN 模型(无论采用多实例学习还是注意力机制)能带来明显的性能提升,但对于 CNN 模型性能改善不明显;将基于 HITS 的策略和基于 LSA 的策略集成使用,则对于四种模型不但表现稳定,且性能提升效果也十分明显。

总结

文章创造性地将关系提取中的自动选种和数据降噪这两个重要任务转换为排序问题。然后,借鉴 HITS、K-means、LSA 和 NMF 等传统算法策略,按照对实例-模式三元组排序的思路,构建出了兼具自动选种和数据降噪功能的算法。实验结果显示,文章提出的算法能够有效完成自动选种和数据降噪任务,并且其性能同基线算法相比也有较大提升。

这篇文章的启发作用在于:对于关系提取中的不同子任务通过问题转换归结为本质相同的同一问题,而后借鉴已有的成熟算法设计出可以通用的解决策略。这种思路上的开拓创新能否应用于其他 NLP 任务,是一个值得思考和探索的方向。

参考文献

[1] Sebastian Riedel, Limin Yao, and Andrew McCallum. 2010. Modeling relations and their mentions without labeled text. In Proceedings of the 2010 Joint European Conference on Machine Learning and Principles of Knowledge Discovery in Databases (ECML PKDD), pages 148–163. Springer. 

[2] Daojian Zeng, Kang Liu, Siwei Lai, Guangyou Zhou, and Jun Zhao. 2014. Relation classification via convolutional deep neural network. In Proceedings of COLING 2014, the 25th International Conference on Computational Linguistics: Technical Papers, pages 2335–2344. Dublin City University and Association for Computational Linguistics. 

[3] Daojian Zeng, Kang Liu, Yubo Chen, and Jun Zhao.2015. Distant supervision for relation extraction via piecewise convolutional neural networks. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 1753–1762. Association for Computational Linguistics.

PaperWeekly
PaperWeekly

推荐、解读、讨论和报道人工智能前沿论文成果的学术平台。

理论CNN非负矩阵分解监督学习潜在语义分析关系提取Bootstrapping论文ACL 2018
2
相关数据
安德鲁·麦卡勒姆人物

Andrew McCallum是马萨诸塞州阿默斯特大学计算机科学系的教授兼研究员。他的主要专业是机器学习,自然语言处理,信息提取,信息整合和社交网络分析。

机器学习技术

机器学习是人工智能的一个分支,是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论,机器学习与推断统计学联系尤为密切,也被称为统计学习理论。算法设计方面,机器学习理论关注可以实现的,行之有效的学习算法。

关系提取技术

关系抽取任务需要检测和分类一组工件中的语义关系提及,通常来自文本或XML文档。该任务与信息提取(IE)的任务非常相似,但是IE另外需要去除重复关系(消歧),并且通常指的是提取许多不同的关系。

奇异值分解技术

类似于特征分解将矩阵分解成特征向量和特征值,奇异值分解(singular value decomposition, SVD)将矩阵分解为奇异向量(singular vector)和奇异值(singular value)。通过分解矩阵,我们可以发现矩阵表示成数组元素时不明显的函数性质。而相比较特征分解,奇异值分解有着更为广泛的应用,这是因为每个实数矩阵都有一个奇异值分解,但未必都有特征分解。例如,非方阵型矩阵没有特征分解,这时只能使用奇异值分解。

注意力机制技术

我们可以粗略地把神经注意机制类比成一个可以专注于输入内容的某一子集(或特征)的神经网络. 注意力机制最早是由 DeepMind 为图像分类提出的,这让「神经网络在执行预测任务时可以更多关注输入中的相关部分,更少关注不相关的部分」。当解码器生成一个用于构成目标句子的词时,源句子中仅有少部分是相关的;因此,可以应用一个基于内容的注意力机制来根据源句子动态地生成一个(加权的)语境向量(context vector), 然后网络会根据这个语境向量而不是某个固定长度的向量来预测词。

非负矩阵分解技术

潜在语义分析技术

潜在语义分析(LSA)是自然语言处理中的一种技术,特别是在分布式语义学中。传统的语义学通常研究字、词的含义以及词与词之间的关系,如同义,近义,反义等等。潜在语义分析探讨的是隐藏在字词背后的某种关系,这种关系不是以词典上的定义为基础,而是以字词的使用环境作为最基本的参考。这种思想来自于心理语言学家。他们认为,世界上数以百计的语言都应该有一种共同的简单的机制,使得任何人只要是在某种特定的语言环境下长大都能掌握那种语言。在这种思想的指导下,人们找到了一种简单的数学模型,这种模型的输入是由任何一种语言书写的文献构成的文库,输出是该语言的字、词的一种数学表达(向量)。字、词之间的关系乃至任何文章片断之间的含义的比较就由这种向量之间的运算产生。值接近1代表相似的单词,而值接近0代表非常不相似的单词。这项技术在信息检索中,被称作潜在语义索引(LSI)。

卷积神经网络技术

卷积神经网路(Convolutional Neural Network, CNN)是一种前馈神经网络,它的人工神经元可以响应一部分覆盖范围内的周围单元,对于大型图像处理有出色表现。卷积神经网路由一个或多个卷积层和顶端的全连通层(对应经典的神经网路)组成,同时也包括关联权重和池化层(pooling layer)。这一结构使得卷积神经网路能够利用输入数据的二维结构。与其他深度学习结构相比,卷积神经网路在图像和语音识别方面能够给出更好的结果。这一模型也可以使用反向传播算法进行训练。相比较其他深度、前馈神经网路,卷积神经网路需要考量的参数更少,使之成为一种颇具吸引力的深度学习结构。 卷积网络是一种专门用于处理具有已知的、网格状拓扑的数据的神经网络。例如时间序列数据,它可以被认为是以一定时间间隔采样的一维网格,又如图像数据,其可以被认为是二维像素网格。

监督学习技术

监督式学习(Supervised learning),是机器学习中的一个方法,可以由标记好的训练集中学到或建立一个模式(函数 / learning model),并依此模式推测新的实例。训练集是由一系列的训练范例组成,每个训练范例则由输入对象(通常是向量)和预期输出所组成。函数的输出可以是一个连续的值(称为回归分析),或是预测一个分类标签(称作分类)。

语料库技术

语料库一词在语言学上意指大量的文本,通常经过整理,具有既定格式与标记;事实上,语料库英文 "text corpus" 的涵意即为"body of text"。

噪音技术

噪音是一个随机误差或观测变量的方差。在拟合数据的过程中,我们常见的公式$y=f(x)+\epsilon$中$\epsilon$即为噪音。 数据通常包含噪音,错误,例外或不确定性,或者不完整。 错误和噪音可能会混淆数据挖掘过程,从而导致错误模式的衍生。去除噪音是数据挖掘(data mining)或知识发现(Knowledge Discovery in Database,KDD)的一个重要步骤。

链接分析技术

这是一种网络理论中用于评估节点之间关系(连接)的数据分析技术,属于网络计量学(Webometrics)范畴。网络中的节点可以包括多种类型的对象及其组合,如组织、人员和事务。链接分析已被用于调查犯罪活动(欺诈侦查、反恐和情报)、计算机安全分析、搜索引擎优化、市场研究、医学研究和艺术等领域。链接分析中最基础且重要的两类算法是PageRank算法与HITS算法。除此之外,其他常见算法还包括SALSA、PHITS、贝叶斯和Reputation等几类。而上述每一类算法都各自衍生出一些变种算法,从而形成了链接分析的算法体系。

自助(抽样)法技术

在统计学中,自助法(Bootstrap Method,Bootstrapping或自助抽样法)是一种从给定训练集中有放回的均匀抽样,也就是说,每当选中一个样本,它等可能地被再次选中并被再次添加到训练集中。自助法由Bradley Efron于1979年在《Annals of Statistics》上发表。当样本来自总体,能以正态分布来描述,其抽样分布(Sampling Distribution)为正态分布(The Normal Distribution);但当样本来自的总体无法以正态分布来描述,则以渐进分析法、自助法等来分析。采用随机可置换抽样(random sampling with replacement)。对于小数据集,自助法效果很好。

暂无评论
暂无评论~