《Learn to Represent Programs with Graphs》閱讀筆記

05-02

論文地址: https://arxiv.org/abs/1711.00740

來源: ICLR 2018

代碼：https://github.com/Microsoft/gated-graph-neural-network-samples.

關於源代碼的學習任務近期已經有研究，但是大多數工作都試圖傳遞自然語言方法，並且沒有利用代碼已知語法提供的獨特經驗。在這項工作中，將介紹如何從源代碼構建圖，以及如何使用 GGNN (Gated Graph Neural Networks）訓練。提出兩個評測任務：預測變數名（VARNAMING），以及判斷變數是否被正確使用（VARMISUSE）。

上圖顯示了模型在一個流行的開源項目中檢測到的一個錯誤片段。具體來說，應該在黃色突出顯示的插槽中使用變數first，而不是 clazz。

GGNN

1.圖定義為 $G = (V,E,X)$ ， $V$ 是節點集合， $X$ 是節點特徵， $E = (E_1,...,E_K)$ 為邊的集合，K 是邊的個數。

2.每個節點的狀態向量 $h^{(v)}$ 初始化為 $x^{(v)},xin X$ ， $x^{(v)}in R^D$ 。

3.每個節點向相鄰的節點發送類型為k個的消息(message)， $m^{(v)}_k = f_k(h^{(v)})$ , $f$ 可以使任意函數，在本文中為線性函數。

4.根據結點接收到的消息，更新結點狀態向量。接收到的消息為 $ilde{m}^{(v)}_k = g({m^{(v)}_k|(u,v)in E})$ ,本文中 $g$ 為所有的頂點求和。頂點的狀態向量更新為

$h^{(v)} = GRU( ilde{m}^{(v)} , h^{(v)})$ ,GRU 為 gated recurrent unit。

5.由上述等式定義的過程被重複固定數量的時間步長。再使用上一個時間步的狀態向量作為節點表示。

Program Graphs

將程序源代碼表示為圖形，並使用不同的邊緣類型來建模不同標註之間的句法和語義關係。程序圖的骨幹是程序的抽象語法樹（AST）（abstract syntax tree），由語法節點（對應於編程語言的語法中的非終結符）和語法標記（對應於終端）組成

為了通過程序捕獲控制流和數據流，作者添加了附加的邊，連接不同的用法以及對應於變數的句法標註的更新

利用變數類型信息。添加變數的類型信息，定義一個embedding函數 $r( au)$ ， $au$ 為已知類型，不可知的類型定義為UNKTYPE。對於多繼承得到的類型，該類型定義為所有父類的集合 $au^*$ ，embedding定義為最大值。

在預測變數名任務中，將對於程序中的變數 $v$ ，將圖中所有對應的結點用<SLOT> token代替

圖中的結點初始化為[token embedding, type embedding]。
運行GGNN，得到所有<SLOT>結點的狀態向量的平均值。
將上一步得到的平均值輸入一層的GRU中，得到目標對象的變數名序列。

在判斷變數是否正確使用任務中，需要對圖進行修改。

計算context representation $c(t)$ 。程序中的某處(t)變數 $v$ 添加結點 $v_{<SLOT>}$ ，為這個結點添加除LastUse, LastWrite, LastLexicalUse, GuardedBy之外的邊。 $c(t)=h^{(v_{<SLOT>})}$
計算usage representation $u(t,v)$ 。其中 $v$ 是 $t$ 處的候選變數，根據候選變數和程序其他結點的關係添加LastUse, LastWrite and LastLexicalUse邊。 $u(t, v)=h^{(v_{t,v})}$
最後， $t$ 處正確的變數為 $argmax_v W[c(t), u(t,v)]$ ， $W$ 是一個線性層。

Evalution

dataset 從GitHub上的開源C＃項目收集了VARMISUSE任務的數據集。濾掉了不太容易成功編譯的項目。

Baselines 對於 VARMISUSE 是兩個基於RNN的雙向基線。對於 VARNAMING 區別是將LOC替換為AVGLBL，AVGLBL是使用每個變數用法的4個左右上下文標註的對數雙線性模型。

在包含290萬行真實源代碼的大型數據集上評估作者的模型，顯示作者的最佳模型在VARNAMING任務上達到32.9％的準確度，在VARMISUSE任務上達到85.5％的準確率，從而擊敗基線。

Discussion & Conclusions

雖然源代碼在其他學科（如編程語言研究）中有很好的理解和研究，但它是深度學習的一個相對較新的領域。與文本或知覺數據相比，它提供了新的角度，因為它的（本地）語義是明確定義的，並且可以使用眾所周知的高效程序分析來提取豐富的附加信息。另一方面，整合這些豐富的結構化信息帶來了一個有趣的挑戰。因為它需要概率地提煉類型系統中包含的標準信息，我們認為它是學習源代碼含義的核心挑戰的第一個嘗試。