KDD 2019 | 如何從科研論文中挖掘演算法的演變路線？

• 2019 年 10 月 4 日
• 筆記

每年新的科研論文數量都在不斷增長，這給想要快速了解學術領域主流資訊的研究人員造成了很大的困擾。為了幫助研究人員克服這一難題，UCSB的學者在KDD2019發表了Mining Algorithm Roadmap in Scientific Publications，提出了能夠自動生成學術路線圖的演算法，刻畫不同演算法之間的演進路線。

論文題目：Mining Algorithm Roadmap in Scientific Publications

論文作者：Hanwen Zha,Wenhu Chen,Keqian Li,Xifeng Yan

1. 相關工作

在先前的工作中，從文檔中抽取概念並構建樹狀結構是一種描述關係的高效方式。其中主要包含基於語義特徵進行模式抽取的做法以及利用聚類間接建立層級結構的做法。然而這些關係的抽取往往局限於「A是B」這樣的形態。

2. 主要思路

本文主要聚焦於演算法這一概念以及其縮寫形態，目標是構建演算法的演進路線。GAN演算法相關的演變如下圖所示。

對於路線圖的刻畫面臨的最大的三個問題是：

• 「標籤缺失：由於演算法名詞經常在發生演變，有標註的演算法實體常常過時，而且新演算法的出現頻率又相對較低。因此無論是對於監督學習方法還是基於頻率的弱監督學習方法，標籤缺失都是一個巨大的挑戰。
• 「實體歧義：演算法名詞本身可能有多種形態，使用縮寫形態可以大大減輕困難，但同時會帶來歧義。在缺少標註數據的前提下，傳統的去歧演算法很難發揮作用。
• 「演算法關係：演算法之間比較性質的描述，出現在論文的一條或多條語句中。傳統無監督學習方法更多地關注在」A是B「關係的挖掘上，監督學習方法一部分聚焦於單條句子、另一部分則關注段落級別的通用關係，而非演算法縮寫之間的比較關係，這一方面又缺乏標註數據進行訓練。

為了解決這些問題，本文的演算法首先抽取縮寫作為演算法候選。然後從文本及表格中抽取比較關係及實體作為弱監督學習的訓練數據。進而使用本文提出的Cross-sentence Attention NeTwork for cOmparative Relation（CANTOR）進行演算法抽取，在構建演進圖的過程中預測演算法類型從而進行去歧處理。最後利用時間及頻率資訊連接演進圖中的節點。

3. 演算法細節

在演算法候選的抽取方面，論文採用縮寫作為候選，一是因為缺乏標註數據，短語的低頻性導致短語名詞抽取不可靠；二是因為縮寫在論文中被普遍使用，而且形式簡單，可以使用正則表達式進行精準匹配，後續比較關係抽取的表格中也主要使用縮寫。對於縮寫的類型，可以用其周圍的標誌性詞語（Signal Word）來判斷，如下圖所示。

在跨語句關係抽取方面，本文分成了單語句和多語句兩個不同模組進行處理。對於單語句，論文使用了Piecewise CNN （PCNN）；對於多語句，論文使用兩套注意力機制（自注意力及縮寫注意力）。單語句和多語句模組得到的結果會通過加權的方式匯總在一起。

• 「語句每個詞語的輸入由詞向量以及位置向量拼接而成。
• 「PCNN是一種CNN變形。對於輸入的句子，將其分成三個片段，分別是第一個實體之前的片段、兩個實體之間的片段和第二個實體之後的片段。三個片段用不同的Kernel分別做卷積以及Max-pooling，最後將三個分別處理過後的片段拼接起來，作為一個整體輸入到最後的非線性層中。PCNN結構在短上下文關係抽取任務上有良好的表現效果。
• 「在注意力機制上，本文採用了Transformer的結構。類似BERT，論文引入了<CLS>和<SEP>兩個token放在段落中作為結構標誌。
• 「除此之外，本文還是用了字元級別的Character Embedding，為了應對有一些縮寫在論文中出現頻率過低的問題。

在實體類型的判別上，本文預設了一些類型，把它作為一個分類任務，放在上述的關係抽取過程中一起訓練。具體來講，是在注意力機制之後使用Softmax層進行預測。在損失函數上，由於一對實體，如演算法之間的比較，應當具有同樣的類型，因此額外加入KL散度。

關係抽取的數據採用了論文表格中的數據：同一列或同一行的實體為正例，同時再生成一系列負例。

在路線圖的生成方面，由於先前生成的關係並無方向資訊，在這裡，作者使用演算法出現的第一篇論文的時間作為演算法的誕生時間，根據時間先後給定關係方向。如果年份相同，則按照出現頻率大小給定方向。

4. 實驗

論文採用了NeurIPS/ACL/VLDB共12k篇論文。使用其中80%作為訓練數據，20%作為測試數據。使用co-occurrence、詞相似度等方法作為Baseline演算法進行比較評估。由於生成的數據中，負例數量較多，所以無監督學習演算法整體的準確率都較差。

5. 案例分析

論文對三個數據集中的GAN/Word2Vec/MonetDB三個不同的演算法進行了分析，得到了以下路線圖。由於在本文的做法中，並未區分縮寫的不同形態，諸如SteinGAN和SteinGan這樣的不同形態在當前的路線圖中同時出現了。

此外，在ACL的案例中，LSA-Wiki實際上是作為Word2vec的Baseline演算法出現的，然而由於LSA-Wiki這個詞在2015年才作為一個整體出現，因此被錯分在了Word2vec之後。而且，一個名詞的初次出現可能存在於當前數據集之外，意味著在當前數據集中的首次出現並不絕對代表這個名詞的誕生。所幸公開的論文集，如Arxiv，的出現減輕了這個問題。