殷达作者

KDD 2019 | 如何从科研论文中挖掘算法的演变路线?

每年新的科研论文数量都在不断增长,这给想要快速了解学术领域主流信息的研究人员造成了很大的困扰。为了帮助研究人员克服这一难题,UCSB的学者在KDD2019发表了Mining Algorithm Roadmap in Scientific Publications,提出了能够自动生成学术路线图的算法,刻画不同算法之间的演进路线。

论文题目:Mining Algorithm Roadmap in Scientific Publications

论文作者:Hanwen Zha,Wenhu Chen,Keqian Li,Xifeng Yan

相关工作

在先前的工作中,从文档中抽取概念并构建树状结构是一种描述关系的高效方式。其中主要包含基于语义特征进行模式抽取的做法以及利用聚类间接建立层级结构的做法。然而这些关系的抽取往往局限于“A是B”这样的形态。

主要思路

本文主要聚焦于算法这一概念以及其缩写形态,目标是构建算法的演进路线。GAN算法相关的演变如下图所示。

对于路线图的刻画面临的最大的三个问题是:

  • “标签缺失:由于算法名词经常在发生演变,有标注的算法实体常常过时,而且新算法的出现频率又相对较低。因此无论是对于监督学习方法还是基于频率的弱监督学习方法,标签缺失都是一个巨大的挑战。

  • “实体歧义:算法名词本身可能有多种形态,使用缩写形态可以大大减轻困难,但同时会带来歧义。在缺少标注数据的前提下,传统的去歧算法很难发挥作用。

  • “算法关系:算法之间比较性质的描述,出现在论文的一条或多条语句中。传统无监督学习方法更多地关注在”A是B“关系的挖掘上,监督学习方法一部分聚焦于单条句子、另一部分则关注段落级别的通用关系,而非算法缩写之间的比较关系,这一方面又缺乏标注数据进行训练。

为了解决这些问题,本文的算法首先抽取缩写作为算法候选。然后从文本及表格中抽取比较关系及实体作为弱监督学习的训练数据。进而使用本文提出的Cross-sentence Attention NeTwork for cOmparative Relation(CANTOR)进行算法抽取,在构建演进图的过程中预测算法类型从而进行去歧处理。最后利用时间及频率信息连接演进图中的节点。

算法细节

在算法候选的抽取方面,论文采用缩写作为候选,一是因为缺乏标注数据,短语的低频性导致短语名词抽取不可靠;二是因为缩写在论文中被普遍使用,而且形式简单,可以使用正则表达式进行精准匹配,后续比较关系抽取的表格中也主要使用缩写。对于缩写的类型,可以用其周围的标志性词语(Signal Word)来判断,如下图所示。

在跨语句关系抽取方面,本文分成了单语句和多语句两个不同模块进行处理。对于单语句,论文使用了Piecewise CNN (PCNN);对于多语句,论文使用两套注意力机制自注意力及缩写注意力)。单语句和多语句模块得到的结果会通过加权的方式汇总在一起。

  • “语句每个词语的输入由词向量以及位置向量拼接而成。

  • “PCNN是一种CNN变形。对于输入的句子,将其分成三个片段,分别是第一个实体之前的片段、两个实体之间的片段和第二个实体之后的片段。三个片段用不同的Kernel分别做卷积以及Max-pooling,最后将三个分别处理过后的片段拼接起来,作为一个整体输入到最后的非线性层中。PCNN结构在短上下文关系抽取任务上有良好的表现效果。

  • “在注意力机制上,本文采用了Transformer的结构。类似BERT,论文引入了<CLS>和<SEP>两个token放在段落中作为结构标志。

  • “除此之外,本文还是用了字符级别的Character Embedding,为了应对有一些缩写在论文中出现频率过低的问题。

在实体类型的判别上,本文预设了一些类型,把它作为一个分类任务,放在上述的关系抽取过程中一起训练。具体来讲,是在注意力机制之后使用Softmax层进行预测。在损失函数上,由于一对实体,如算法之间的比较,应当具有同样的类型,因此额外加入KL散度。

关系抽取的数据采用了论文表格中的数据:同一列或同一行的实体为正例,同时再生成一系列负例。

在路线图的生成方面,由于先前生成的关系并无方向信息,在这里,作者使用算法出现的第一篇论文的时间作为算法的诞生时间,根据时间先后给定关系方向。如果年份相同,则按照出现频率大小给定方向。

实验

论文采用了NeurIPS/ACL/VLDB共12k篇论文。使用其中80%作为训练数据,20%作为测试数据。使用co-occurrence、词相似度等方法作为Baseline算法进行比较评估。由于生成的数据中,负例数量较多,所以无监督学习算法整体的准确率都较差。

案例分析

论文对三个数据集中的GAN/Word2Vec/MonetDB三个不同的算法进行了分析,得到了以下路线图。由于在本文的做法中,并未区分缩写的不同形态,诸如SteinGAN和SteinGan这样的不同形态在当前的路线图中同时出现了。

此外,在ACL的案例中,LSA-Wiki实际上是作为Word2vec的Baseline算法出现的,然而由于LSA-Wiki这个词在2015年才作为一个整体出现,因此被错分在了Word2vec之后。而且,一个名词的初次出现可能存在于当前数据集之外,意味着在当前数据集中的首次出现并不绝对代表这个名词的诞生。所幸公开的论文集,如Arxiv,的出现减轻了这个问题。

AMiner学术头条
AMiner学术头条

AMiner平台由清华大学计算机系研发,拥有我国完全自主知识产权。系统2006年上线,吸引了全球220个国家/地区800多万独立IP访问,数据下载量230万次,年度访问量1000万,成为学术搜索和社会网络挖掘研究的重要数据和实验平台。

https://www.aminer.cn/
专栏二维码
理论数据挖掘论文KDD 2019
1
相关数据
自注意力技术

自注意力(Self-attention),有时也称为内部注意力,它是一种涉及单序列不同位置的注意力机制,并能计算序列的表征。自注意力在多种任务中都有非常成功的应用,例如阅读理解、摘要概括、文字蕴含和语句表征等。自注意力这种在序列内部执行 Attention 的方法可以视为搜索序列内部的隐藏关系,这种内部关系对于翻译以及序列任务的性能非常重要。

损失函数技术

在数学优化,统计学,计量经济学,决策理论,机器学习和计算神经科学等领域,损失函数或成本函数是将一或多个变量的一个事件或值映射为可以直观地表示某种与之相关“成本”的实数的函数。

注意力机制技术

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

准确率技术

分类模型的正确预测所占的比例。在多类别分类中,准确率的定义为:正确的预测数/样本总数。 在二元分类中,准确率的定义为:(真正例数+真负例数)/样本总数

监督学习技术

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

聚类技术

将物理或抽象对象的集合分成由类似的对象组成的多个类的过程被称为聚类。由聚类所生成的簇是一组数据对象的集合,这些对象与同一个簇中的对象彼此相似,与其他簇中的对象相异。“物以类聚,人以群分”,在自然科学和社会科学中,存在着大量的分类问题。聚类分析又称群分析,它是研究(样品或指标)分类问题的一种统计分析方法。聚类分析起源于分类学,但是聚类不等于分类。聚类与分类的不同在于,聚类所要求划分的类是未知的。聚类分析内容非常丰富,有系统聚类法、有序样品聚类法、动态聚类法、模糊聚类法、图论聚类法、聚类预报法等。

推荐文章
暂无评论
暂无评论~