融合定向自注意機制的代碼完成方法

虞慧群，黃家杰，范貴生，2，刁旭煬

1(華東理工大學 計算機科學與工程系，上海200237)

2(上海市計算機軟件評測重點實驗室，上海201112)

E-mail：yhq@ecust.edu.cn

1 引 言

隨著現代化軟件庫和工具的規模和復雜性不斷增長，集成開發環境(IDE)已成為現代軟件工程師的基本范例，因為IDE提供了一系列有用的服務來加速軟件開發，代碼完成已經成為IDE的基本特征.它基于上下文中的現有代碼建議下一個可能的代碼token.有效的代碼完成可以通過消除拼寫錯誤并從上下文中識別正確的參數來幫助軟件開發者減少一些不必要的錯誤，同時能夠快速開發軟件.

現有的代碼完成很大程度上依賴于編譯時類型信息來預測下一個token[1].因此，它適用于靜態類型的語言，如C++，Java.但是對于現在廣泛使用的動態類型語言(如JavaScript和Python)來說，由于缺少類型信息，這也就限制了現有的代碼完成對于動態類型語言的支持.

為了使動態類型能夠進行有效的代碼完成，有一些基于簡單的啟發式和專有術語頻率統計來進行代碼完成[2].但是，這種方法在完成代碼時僅檢查源代碼中的有限數量的元素.因此，這種方法的有效性可能無法很好地擴展到大型程序.

同時Hindle，White，Bielik[3-5]將編程語言視為自然語言，使用遞歸神經網絡(RNN)之類的神經語言模型可以捕獲順序分布和深度語義.然而，這些標準的神經語言模型受到所謂的隱藏狀態瓶頸的限制：關于當前序列的所有信息被壓縮成固定大小的矢量，這就使得RNN難以處理遠程依賴.

注意機制能夠解決遠程依賴的問題，與RNN結合能夠在大量NLP任務上實現最先進的性能[6].注意機制使用隱藏層來計算輸入序列中元素的分類分布，以反映其重要性權重.但是大多數注意機制的缺點是時間順序信息丟失.

Li等人結合LSTM和注意機制來進行代碼完成任務，此外還利用指針機制來解決OoV單詞問題，并取得了很好的效果[7].但是由于使用的是LSTM和注意機制同樣對于挖掘代碼的遠程依賴存在限制以及丟失了時間順序信息.

受到定向自注意網絡(Directional Self-Attention Network，DiSAN)[8]的啟發，考慮源代碼上下文中的遠程依賴和體現代碼結構的時間順序信息對于代碼完成任務的重要性.針對此，本文做出以下貢獻：

1)使用了一種定向自注意機制(Directional Self-Attention，DiSA)，捕捉AST表示的源代碼之間的時間順序信息進而學習源代碼的結構信息，以及代碼上下文的遠距離的依賴關系；

2)提出了挖掘代碼依賴之間的模型，更好地用于預測token的任務，學習從全局詞匯表或本地上下文中生成下一個單詞；

3)基于兩個基準數據集(JavaScript和Python)上來評估本文構建的模型.實驗結果表明，在預測token的準確率方面，分別在JavaScript數據集上提高了1%左右，在Python數據集上提高了8%左右，這顯示了本文提出的模型相比于現有技術的有效性和先進性.

2 相關工作

近年來有一些工作探討了統計學習和序列模型在代碼完成任務中的應用，例如n-gram模型[1，3]和概率語法[2，5，9].最近，神經網絡進行源代碼建模變得非常流行[10].

Bhoopchand使用RNN的稀疏指針機制，預測Python源代碼中的標識符[11].然而，它們的指針組件以Python源代碼中的標識符為目標，而不是本文工作中的包含標識符，類型，變量等的所有的語料.Subhasis探索基于學習的代碼推薦,基于神經網絡的學習技術使用機器學習來學習代碼的結構和模式[12]，并沒有編寫語法規則，試圖利用學習方法自動學習這些規則和模式.

RNN之類的深度學習技術已經在語言建模任務中實現了最先進的結果[13].Nguyen等人使用DNN來構建語言模型，設計了一個上下文合并方法，用于源代碼的句法和類型注釋，進行源代碼分析[14].

特別地，Li等人結合LSTM和Attention機制來進行代碼完成任務，而且利用指針機制解決OoV單詞問題，并取得了很好的效果[7].然而LSTM存在限制使得其不能有效的挖掘遠距離的依賴關系，同時注意機制存在時間順序丟失的問題.定向注意機制提出用于解決自然語言處理中的LSTM的遠距離依賴關系問題，并取得非常好的效果[8].代碼之間的時間順序信息以及代碼之間的依賴信息對于代碼完成任務來說是非常有用的，本文使用定向自注意機制來挖掘代碼之間的依賴關系和時間順序信息，促進智能化代碼開發的進一步發展.

3 自注意機制

3.1 自注意定義

注意機制計算來自兩個來源的元素之間注意分數[15，16].給定源序列x=[x1,x2,…,xn]的標記嵌入和查詢q的向量表示，注意通過兼容性函數計算f(xi,q)計算xi和q之間的注意權重，反映了xi和q之間的依賴關系，進而轉化成源x對q的重要性依賴的概率.轉換成如下公式：

(1)

p(z|x,q)=softmax(a)

(2)

f(xi,q)=wTσ(W(1)xi+W(2)q)

(3)

(4)

自注意力是注意機制的一個特例.它用來自源輸入本身的令牌嵌入xj替換q.它通過計算每對令牌xj和xj之間的注意力來關聯單個序列在不同位置的元素.它對于遠程和本地依賴都非常具有表現力和靈活性.

3.2 定向自注意機制

Shen等人提出一種多維自注意[8]，探索來自相同源x的xi和xj之間的依賴關系，并為每個元素生成上下文感知編碼.

f(xi,q)=WTσ(W(1)xi+W(2)q+b(1))+b

(5)

其中f(xi,q)∈Rde是一個長度與xi相同的向量，所有權重矩陣W,W(1),W(2)∈Rde×de.

f(xi,xj)=WTσ(W(1)xi+W(2)xj+b(1))+b

(6)

然后，計算每個特征k∈[de]的所有n個標記的分類分布p(zk|x,q).

(7)

來自x的所有元素的自注意的輸出是s=[s1,s2,…,sn]∈Rde×n.

定向自注意機制(DiSA)在自注意塊中使用探索依賴性和時間順序的“Mask”形成多維自注意塊，以及用于組合注意塊的輸出和輸入的融合門，其結構如圖1所示.

圖1 定向自注意機制結構圖

將多維自注意應用于輸入，并為輸入序列中的所有元素生成上下文感知矢量表示.將位置掩碼應用于方程自注意輸出的上下文感知矢量，使注意力機制產生了方向性.

f(xi,xj)=c·tanh([W(1)xi+W(2)xj+b(1)]/c)+Mij1

(8)

通過掩碼容易地編碼諸如時間順序和依賴性解析的先前結構知識，并且在生成的編碼中進行探索.

為了自注意，使用掩碼將時間順序信息編碼到注意輸出中.使用兩個掩模，即前掩模Mfw和后掩模Mbw，

(9)

(10)

在前向掩碼Mfw中，后一個元素j只關注早期元素i，反之亦然.

給定輸入序列x和掩碼M，根據方程(8)計算f(x)，并遵循多維自注意的標準過程來計算每個j∈[n]的概率矩陣Pj.s中的每個輸出sj的計算方法如公式(7)所示.

DiSA的最終輸出u∈Rde×n是通過組合Mask的多維自注意塊的輸出s和輸入x來獲得的.這產生了每個元素/令牌的時間順序編碼和上下文感知矢量表示.

4 基于定向自注意機制的方法與模型

本節首先介紹了如何將源代碼程序轉換成AST抽象語法樹的形式，根據抽象語法樹遍歷形成節點序列，再進行模型構建.如圖2所示，使用AST的終端節點和非終端節點的序列來進行下一個終端或非終端的預測，并構建模型.

圖2 模型架構

4.1 構建AST抽象語法樹

無論是動態類型還是靜態類型，任何編程語言都有明確的上下文無關語法(CFG)，可用于將源代碼解析為抽象語法樹(AST).而且AST可以很容易地轉換回源代碼.并且以AST形式處理程序是軟件工程(SE)中的典型實踐[7，17，18].因此在實驗的語料庫中，參考Raychev，Liu，Li等人的AST編碼操作[2，7]，將每個源程序都以抽象語法樹(AST)的形式表示.

在AST中，每個非葉節點對應于CFG指定結構信息中的非終端.例如圖3顯示了一個示例Python程序及其相應的AST.在Python中，非終端可以是body，For，Call等.每個葉節點對應于CFG中的終端，終端有無限的可能性，它們可以是變量名，字符串或數字等等.

將程序的AST信息編碼為圖3的格式，可以看到每個程序對應的AST節點包含兩個屬性：節點的類型和值.

對于每個葉節點，“：”用作類型和值類型之間的分隔符.對于每個非葉節點，對其附加一個特殊的EMPTY標記作為其值.例如，圖3中的AST節點NamaLoad：n，其中NameLoad表示該節點的類型，n是節點的值.類型編碼程序結構，例如body，for，If等.在實驗所用的的語料庫中，類型的數量相對較少(只有數百種)，值可以是任何程序標識符，文字，程序操作符等.

圖3 Python源代碼轉換成抽象語法樹(AST)

將程序表示為AST而不是純文本能夠預測程序的結構，即每個AST節點的類型.通過這種方式，成功預測下一個AST節點不僅可以完成下一個令牌，還可以完成整個代碼塊.這種結構使得能夠在不同粒度級別上更靈活地完成代碼.

給定部分AST作為輸入，將下一個非終端預測的輸入視為長度為K的序列，即(N1,T1),(N2,T2),……,(Nk,Tk).這里，對于每個i，Ni是非終端，并且Ti是Ni的終端值.對于每個非終端節點Ni，不僅編碼其種類，而且編碼非終端是否具有至少一個非終端子節點.在這樣做時，可以從輸入序列重建原始AST.將序列中的每個元素(例如，(Ni,Ti))稱為標記.如上所述，沒有值的非終端被認為具有EMPTY值.

該輸入序列(N1,T1),(N2,T2),……,(Nk,Tk)是所有問題的唯一輸入.在整個討論的其余部分中，將對Nk和Tk都使用embed編碼，并且非終端和終端的詞匯集是分開的.

4.2 源代碼上下文的依賴關系和時間順序挖掘

本文中使用3.2節中提出的自注意機制公式(6)來挖掘源代碼輸入序列的(N1,T1),(N2,T2),……,(Nk,Tk)的每一個單詞對之間的自注意機制的注意的分數f(xi,xj)，通過這個注意分數來展示出源代碼上下文中的代碼與代碼之間的注意力的權重，也就顯示出源代碼上下文中的代碼之間的依賴關系.

通過使用3.3節中的定向的自注意機制公式(8)將源代碼之間的時間順序與之前源代碼依賴關系結合起來，挖掘出源代碼的時間順序信息，進而挖掘出程序代碼的結構信息，同時挖掘出上下文之間的遠程依賴關系.這里挖掘時間順序信息是挖掘出源代碼前向時間順序信息及其依賴關系ubw∈Rde×k和后向的時間順序信息及其依賴關系ubw∈Rde×k.

最后將前向自注意輸出與后向自注意輸出進行結合uc∈R2de×k，通過對uc使用softmax進行輸出的預測概率.

(11)

5 實驗結果與分析

5.1 數據集

本文在兩個基準數據集(1)http：//plml.ethz.ch上評估了不同的方法：JavaScript(JS)和Python(PY)，它們總結在表1中.從GitHub收集，兩個數據集都是公開可用的并用于以前的工作[2，5，7]，兩個數據集都包含150，000個程序文件，這些文件以相應的AST格式存儲，其中前100，000個用于訓練，剩下的50，000個用于測試.在深度優先遍歷中序列化每個AST之后，生成多個用于訓練和評估的查詢，每個AST節點一個，通過從序列中刪除節點(加上右邊的所有節點)，然后嘗試預測節點.

表1 實驗數據集分析

Table 1 DataSet analysis

JSPYTraining Queries10.7×1076.2×107Test Queries5.3×1073.0×107Type Vocabulary95330Value Vocabulary2.6×1063.4×107

JS和PY中節點類型的數量最初為44和181.通過添加其有關子節點和兄弟節點的信息，將數字分別增加到95和330.如表1所示，兩個數據集中的節點值的數量太大而不能直接應用神經語言模型，因此僅在每個訓練集中選擇K個最頻繁的值來構建全局詞匯表，其中K是自由參數.并且添加了三個特殊值：UNK用于表示詞匯外值，EOF表示每個程序的結束，和EMPTY表示AST中非葉節點的值.

5.2 實驗設置

實驗設置為了與Li[7]等人的實驗具有相當的可比較性，在本問的模型參數設置中，隱藏單元大小設置為1500.為了訓練模型，使用交叉熵損失函數和mini-batch SGD與Adam優化器[19].將初始學習率設置為0.001，并在每個時期后乘以0.6來衰減它.將漸變的范數設置為5以防止漸變爆炸.批量大小為64，將模型訓練8輪.每個實驗運行三次，并計算平均結果.

將每個程序劃分為由50個連續AST節點組成的段，如果未滿，則最后一段用EOF填充.所有其他變量使用[-0.05，0.05]上的均勻分布隨機初始化.使用準確度作為實驗的評估度量，即正確預測的下一個節點類型/值的比例.

預處理和訓練細節由于每個AST節點由一個類型和一個值組成，要對節點進行編碼并將其輸入到DiSA，分別為每種類型(300維)和值(1200維)訓練嵌入向量，然后將兩個嵌入連接成一個向量.由于兩個數據集中類型的數量相對較少，因此在預測下一個AST節點類型時沒有未知單詞問題.

對于每個數據集，將訓練集中具有K個最頻繁的節點值的AST節點值構建全局詞匯表，并將訓練集和測試集中的所有詞典外節點值標記為OoV值.對于詞匯表內的值，將它們標記為全局詞匯表中的相應ID.在訓練期間，每當訓練查詢的基本事實是UNK時，將該查詢的損失函數設置為零，以便模型不學習預測UNK.在訓練和評估中，目標值為UNK的所有預測都被視為錯誤的預測，即降低整體準確性.

5.3 實驗結果與討論

對于每個實驗，本文運行以下模型進行比較，沒有任何注意或指針機制的標準LSTM網絡；配備了注意機制LSTM網絡；結合了注意力LSTM和指針網絡的混合網絡；以及本文提出的使用定向自注意機制的模型；

5.3.1不同的K時預測終端節點值的準確度

本文首先評估定向自注意模型在不同的頻繁的K個節點值對于預測下一個AST節點值，并與Li等人提出的指針網絡解決OoV單詞問題[7]進行比較.對于兩個數據集中的每一個，通過將節點值的全局詞匯量K改變為1K，10K和50K來創建三個特定數據集，從而導致不同的詞匯外(OoV)率.在每個特定數據集上運行上述模型，表2列出了相應的統計數據和實驗結果.

表2 不同的K時預測下一終端節點值的準確度

Table 2 Accuracy on next value prediction with different vocabulary sizes

Vocabulary SizeJS_1KJS_10KJS_50KPY_1KPY_10KPY_50KOoV Rate20%11%7%24%16%11%LSTM69.9%75.8%78.6%63.6%66.3%67.3%Attentional LSTM71.7%78.1%80.6%64.9%68.4%69.8%Pointer Mixture LSTM73.2%78.9%81.0%66.4%68.9%70.1%DiSA(Ours)72.8%79.5%82.5%69.6%74.6%76.7%

如表 2所示，在每個特定數據集中，vanilla LSTM實現了最低精度，而注意力LSTM提高了vanilla LSTM的性能，指針混合網絡實現了高精度，同時本文的定向自注意機制模型在5個實驗上實現了最高精度.此外，還可以看到，通過增加JS或PY數據集中的詞匯量大小，OoV率降低，并且由于更多可用信息，不同模型的一般準確度增加.

在JS數據集中K設置為1K時，可以看到此時的OoV Rate在此時比較高，此時本文使用的模型預測的準確率要比混合指針網絡預測的準確率低0.4%，同時在PY數據集上同樣的K值并且OoV Rate更加高時本文提出的模型的預測準確率要比混合指針網絡的效果要高3.2%左右，可以猜測混合指針網絡并沒有很好的挖掘到代碼的長程依賴和時間順序信息，同時可以注意到自注意機制的性能提升，并且增益是最大的，性能增益歸因于當前代碼段的時間順序信息以及代碼之間的依賴關系.

從這部分實驗結果說明，在沒有充分挖掘到代碼段的時間順序信息和代碼之間的依賴關系，考慮OoV單詞對于預測效果是沒有太大幫助的.從實驗結果看出本文提出基于定向自注意機制的模型對于下一節點值的預測的準確度都保持在最高準確率，說明相比較配備了Attention機制的LSTM的混合指針網絡來說，本文提出的基于定向自注意機制的網絡模型能夠非常有效的挖掘到代碼之間的依賴關系和代碼段的時間順序信息進而挖掘代碼段的結構信息，并且時間順序信息所反映出的結構信息和代碼之間的依賴關系對于下一個結點值的預測來說是非常有幫助的.

5.3.2 有效性比較

由于已經有先前在兩個基準數據集上進行代碼完成的研究，為了驗證提出的方法的有效性，需要與現有技術進行比較.特別是，Liu等人在JS數據集上使用標準LSTM[6].Raychev等基于概率語法構建了代碼的概率模型[2]，以及Li 等提出并使用結合Attention機制的LSTM并結合指針網絡的混合網絡，并在兩個數據集上實現了最先進的代碼完成精度[7].

具體來說，分別對整個AST中的每一個AST節點類型(TYPE)預測和該結點對應的節點值(VALUE)預測進行實驗.將值詞匯量大小設置為50K，以使結果與當前先進的結果相當.結果如表3所示.

表3 有效性比較

Table 3 Comparisonofthe effectiveness

MethodsJSTYPEVALUEPYTYPEVALUELSTM88.1%78.6%79.3%67.3%Att-LSTM 88.6%80.6%80.6%69.8%PM-LSTM-81.0%-70.1%P-Model 83.9%82.9%76.3%69.2%DiSA(Ours)89.2%82.5%88.4%76.7%

表3顯示了本文所提方法與相關方法的實驗效果對比.Pointer Mixture LSTM僅在兩個數據集上預測下一個值.對于下一個類型預測，其仍然使用的是具有Attention機制的LSTM，而本文提出的基于定向自注意機制的模型同時預測了下一個節點的類型和值，并且在兩個數據集上實現了最高精度，顯著提高了兩個數據集的最佳記錄.對于JS數據集的下一個值預測，本文提出的模型實現了與Probalilistic Model[2]相當的性能，這是一個基于特定領域語法的概率模型，但是在下一個類型預測，本文提出的模型顯著提高了預測精度.并且，本文提出的模型的結果優于當前比較先進的幾個模型提出的結果.在PY數據集上，本文提出的模型用于下一個類型預測和下一個值預測的效果均要優于先前的最佳記錄，顯著提高了預測精度.因此，可以得出結論，本文提出的基于定向自注意力機制網絡對于代碼完成是有效的，在四個任務中實現了三個最先進的性能.

6 結 論

在本文中，將定向自注意機制應用于代碼完成任務，并開發一種關注程序AST的時間順序信息的注意機制.為了處理代碼完成中的節點值的預測，本文提出了一種使用定向自注意機制的網絡，它有效挖掘代碼段當前上下文的時間順序信息，以及源代碼上下文的代碼之間的依賴關系.實驗結果表明了本文方法的有效性.