已經(jīng)有不少使用神經(jīng)網(wǎng)絡(luò)生成程序的研究，但目前的工作基本上都基于嚴(yán)格的語(yǔ)義（semantic）限制。Rice大學(xué)的研究人員Vijayaraghavan Murali等將在ICLR 2018上做口頭報(bào)告，介紹他們的新研究，基于不確定的語(yǔ)法(syntactic)條件生成類似Java的強(qiáng)類型程序。

AML

對(duì)于程序生成而言，Java還是有些復(fù)雜。因此研究人員對(duì)Java做了一些簡(jiǎn)化，設(shè)計(jì)了一門新的語(yǔ)言AML。AML刻畫了Java類語(yǔ)言的API使用的精髓。

AML使用有限的API數(shù)據(jù)類型的集合，類型同樣是由API方法名稱（包括constructor）指定的有限集合。方法a的類型簽名用(τ1, ..., τk) -> τ0表示。

AML語(yǔ)法

其中，c表示變量，x、x1……表示變量，let用于變量綁定。

訓(xùn)練數(shù)據(jù)

訓(xùn)練數(shù)據(jù)為標(biāo)注過(guò)的程序：

{(X1, Prog1), (X2, Prog2), ...

其中，Prog1、Prog2……為AML程序。X1、X2為標(biāo)簽。訓(xùn)練之后，模型將根據(jù)標(biāo)簽生成程序，因此標(biāo)簽應(yīng)當(dāng)包含關(guān)于代碼的信息。

具體是哪些信息呢？

首先，AML主要是基于API調(diào)用設(shè)計(jì)的語(yǔ)言，因此API調(diào)用是重要的信息。

其次，AML脫胎于Java這一靜態(tài)類型語(yǔ)言，因此類型也是重要的信息。

理論上，給定關(guān)鍵的API調(diào)用和類型，就可以生成程序。但實(shí)際上模型還沒(méi)有這么智能，有時(shí)還需要一些額外的信息，一些關(guān)鍵詞。

因此，標(biāo)簽共分3類：

X調(diào)用

X類型

X關(guān)鍵詞

其中，關(guān)鍵詞主要是根據(jù)類型和調(diào)用方法的命名CamelCase切分所得。例如，readLine會(huì)被切分為2個(gè)關(guān)鍵詞read和line。

草圖

如前一節(jié)所述，訓(xùn)練數(shù)據(jù)為標(biāo)簽（X）和AML程序（Prog）。然而，研究人員并沒(méi)有直接學(xué)習(xí)標(biāo)簽和程序間的關(guān)系。因?yàn)椋绦虬恍┑蛯拥男畔ⅲ@些信息其實(shí)無(wú)關(guān)緊要，并不需要學(xué)習(xí)。比如，具體的變量命名，替換一下，并不會(huì)影響程序的語(yǔ)義（λ演算中的α-等價(jià)）。因此，需要將程序再轉(zhuǎn)換一下，轉(zhuǎn)換成某種刻畫程序的高層結(jié)構(gòu)和形狀（控制結(jié)構(gòu)、API調(diào)用順序、參數(shù)類型、返回值類型）的表示。基于這一思路，研究人員將程序中的一些低層信息（變量命名、基本操作）抽象掉，從而將程序轉(zhuǎn)化為草圖（Sketch），并基于標(biāo)簽學(xué)習(xí)草圖上的概率分布。之后，再使用組合方法將草圖具體化為類型安全的AML程序（通過(guò)類型引導(dǎo)的隨機(jī)搜索過(guò)程）。

Prog、X、Y的貝葉斯網(wǎng)絡(luò)

其中，Yi= α（Progi），Y（草圖）的語(yǔ)法如下：

可以看到，草圖的語(yǔ)法和AML的語(yǔ)法類似，抽象掉了其中的變量名稱（x、x1等），保留了控制結(jié)構(gòu)、類型信息和API調(diào)用。

對(duì)比草圖的語(yǔ)法和AML的語(yǔ)法，α函數(shù)（從程序中抽象出草圖的操作）的定義也就不言自明了：

GED

如前所述，模型將基于草圖進(jìn)行學(xué)習(xí)：

上式表明，最終我們需要計(jì)算：

為了計(jì)算上式，研究人員提出了高斯編碼-解碼器（Gaussian Encoder-Decoder）（簡(jiǎn)稱GED）模型，引入了一個(gè)潛向量Z，以隨機(jī)連接標(biāo)簽和草圖：

下面我們以編碼X調(diào)用為例，說(shuō)明編碼器具體是如何工作的。

首先，將X調(diào)用的每個(gè)元素X調(diào)用,i轉(zhuǎn)換成one-hot向量表示，記為X'調(diào)用,i。然后，通過(guò)下式編碼X'調(diào)用,i

XCalls,i即X調(diào)用,i

其中，h為神經(jīng)隱藏單元的數(shù)量，Wh∈ R|調(diào)用| x h、bh∈ Rh、Wd∈ Rh x d、bd∈ Rd為網(wǎng)絡(luò)的權(quán)重和偏置，可通過(guò)訓(xùn)練學(xué)習(xí)。

基于f，可以計(jì)算P(X | Z,θ)

也就是說(shuō)，X編碼后的值從以Z為中心的高維正態(tài)分布取樣。

P(X | Z,θ)的計(jì)算需要編碼，P(Y | Z,θ)的計(jì)算與之相反，需要解碼。

草圖Y可以看成一個(gè)樹形結(jié)構(gòu)。

研究人員采用了自頂向下的搜索方法，從樹形的頂端，一路往下，遞歸地計(jì)算輸出分布yi。“一路往下”的“路”，研究人員稱為生產(chǎn)路徑（production path）。生產(chǎn)路徑定義為有序?qū)Φ男蛄?(v1, e1), (v2, e2), ..., (vk, ek)>，其中，vi為草圖中的節(jié)點(diǎn)（即語(yǔ)法中的項(xiàng)），ei為連接vi與vi+1的邊的類型。具體而言，邊包括兩種類型：sibling（兄弟姊妹，上圖中的實(shí)線）和child（子女，上圖中的虛線）。

比如，上圖中有4條生產(chǎn)路徑：

(try,c), (FR.new(String),s), (BR.new(FR),s), (while,c), (BR.readLine(),c), (skip,·)

(try,c), (FR.new(String),s), (BR.new(FR),s), (while,s), (BR.close(),·)

(try,s), (catch,c), (FNFException,c), (T.printStackTrace(),·)

(try,s), (catch,s), (catch,c), (IOException,c), (T.printStackTrace(),·)

其中，·表示路徑的終結(jié)。另外，為了簡(jiǎn)明，以上路徑均省略了(root,c)，用s和c表示sibling和child，并縮寫了部分類名。

給定Z和某條生產(chǎn)路徑上的序列Yi= <(v1,e1), ..., (vi,ei)>，為了簡(jiǎn)化計(jì)算，假定路徑中的下一個(gè)節(jié)點(diǎn)僅僅取決于Z和Yi，從而解碼器只需使用單個(gè)推理步驟即可計(jì)算概率P(vi+1| Yi,Z)。具體而言，解碼器使用了兩個(gè)循環(huán)神經(jīng)網(wǎng)絡(luò)，一個(gè)用于c邊，一個(gè)用于s邊。

其中，v'i為vi轉(zhuǎn)換成的one-hot向量。h為解碼器的隱藏單元數(shù)目，|G|為解碼器的輸出詞匯。Whe、bhe為解碼器的隱藏狀態(tài)權(quán)重和偏置矩陣，Wve、bve為輸入權(quán)重和偏置矩陣，Wye、bye為輸出權(quán)重和偏置矩陣（e為邊的類型）。Wl和bl是“提升”權(quán)重和偏置，將d維向量Z提升到解碼器的高維隱藏空間h。

可視化

研究人員可視化了32維潛向量空間的聚類。研究人員從測(cè)試數(shù)據(jù)中得到標(biāo)簽X，然后從P(Z | X)取樣潛向量Z，進(jìn)而從P(Y | Z)取樣草圖Y。接著使用t-SNE降維Z到2維，然后基于Y中的API使用標(biāo)注每個(gè)點(diǎn)。下圖顯示了這一2維空間，每個(gè)標(biāo)簽對(duì)應(yīng)不同的顏色。

從上圖我們可以很明顯地看到，模型很好地根據(jù)API的不同學(xué)習(xí)了潛空間的聚類。

定量測(cè)試

研究人員基于1500個(gè)Android應(yīng)用（收集自網(wǎng)絡(luò)），進(jìn)行了測(cè)試。研究人員使用JADX反編譯這1500個(gè)Android應(yīng)用安裝文件（APK）到1億行源代碼，并從中提取出了15萬(wàn)Java方法。隨后，研究人員將這15萬(wàn)Java方法轉(zhuǎn)換成了AML程序。然后，從AML程序中提取出草圖Y和X調(diào)用、X類型、X關(guān)鍵詞，供模型訓(xùn)練。其中，分別隨機(jī)選擇了1萬(wàn)個(gè)AML程序，作為驗(yàn)證集和測(cè)試集。

理論上來(lái)說(shuō)，驗(yàn)證生成程序的正確性需要驗(yàn)證程序的所有輸入對(duì)應(yīng)的輸出符合預(yù)期。然而，這是一個(gè)不可判定問(wèn)題。因此，研究人員轉(zhuǎn)而使用一些間接的標(biāo)準(zhǔn)進(jìn)行衡量。

期望AST

API調(diào)用順序的相似程度（具體而言，研究人員使用了平均最小Jaccard距離）

API調(diào)用方法的相似程度（同樣基于平均最小Jaccard距離）

語(yǔ)句數(shù)目

控制結(jié)構(gòu)數(shù)目（例如，分支、循環(huán)、try-catch）數(shù)

上面5張表格中，“Input Label Observability”（輸入標(biāo)簽可觀察性）表示測(cè)試數(shù)據(jù)提供的輸入標(biāo)簽（API調(diào)用、類型、關(guān)鍵詞）的信息比例。研究人員試驗(yàn)了75%、50%、25%的可觀察性，相應(yīng)的中位數(shù)分別為9、6、2。這樣，研究人員可以評(píng)估給定少量關(guān)于代碼的信息時(shí)，模型的預(yù)測(cè)能力。

下表顯示了在50%可觀察性下，模型在未見(jiàn)數(shù)據(jù)上的表現(xiàn)。

以上6個(gè)表格中，“Model”（模型）一列中，GED為研究人員所用的模型，GSNN（高斯隨機(jī)神經(jīng)網(wǎng)絡(luò)）為當(dāng)前最先進(jìn)的條件生成式模型（Sohn等在2015年提出）。為了驗(yàn)證草圖學(xué)習(xí)的有效性，研究人員進(jìn)行了消融測(cè)試。帶-Sk后綴的為基于草圖學(xué)習(xí)的模型，帶-AML后綴的為直接基于程序進(jìn)行學(xué)習(xí)的模型。

測(cè)試結(jié)果表明，研究人員提出的模型GED-Sk表現(xiàn)最優(yōu)，超過(guò)了當(dāng)前的最先進(jìn)模型GSNN。另外，GSNN-Sk的表現(xiàn)也不錯(cuò)，而直接基于程序進(jìn)行學(xué)習(xí)的模型表現(xiàn)很糟糕。這說(shuō)明草圖學(xué)習(xí)是條件程序生成的關(guān)鍵。

定性測(cè)試

除了定量測(cè)試之外，研究人員也進(jìn)行了定性測(cè)試。

文件讀寫

研究人員希望Bayou能生成一個(gè)寫入文件的程序。想想看，如果你希望指示Bayou生成寫入文件的程序，你會(huì)給出怎么樣的提示呢？最低限度的提示，應(yīng)該是兩個(gè)關(guān)鍵詞，write、file，或者，甚至僅僅是一個(gè)類型FileWriter。Bayou還沒(méi)有這么智能，但它的表現(xiàn)已經(jīng)相當(dāng)搶眼了。研究人員給Bayou的輸入僅僅是一個(gè)類型和一個(gè)關(guān)鍵詞，幾乎就是最低限度的信息了：

X類型= {FileWriter}

X調(diào)用= {write}

X關(guān)鍵詞= {}

Bayou生成了如下的程序（選取自top-5）：

BufferedWriter bw;

FileWriter fw;

try {

fw = newFileWriter($String, $boolean);

bw = newBufferedWriter(fw);

bw.write($String);

bw.newLine();

bw.flush();

bw.close();

} catch (IOException _e) {

}

注意，盡管輸入只提供了FileWriter類型，程序使用了BufferedWriter，因?yàn)樵贘ava中，文件讀寫經(jīng)常基于buffer。Bayou自行學(xué)習(xí)到了這一點(diǎn)。另外，Bayou也正確地在關(guān)閉文件前清空了buffer。

Android對(duì)話框

研究人員希望生成一個(gè)程序，設(shè)定Android對(duì)話框的標(biāo)題和信息。這次研究人員給定的輸入已經(jīng)到了最低限度：

X類型= {}

X調(diào)用= {}

X關(guān)鍵詞= {android, dialog, set, title, message}

生成的程序如下：

Builder builder2;

Builder builder1;

AlertDialog alertDialog;

Builder builder4;

Builder builder3;

builder1 = newBuilder($Context);

builder2 = builder1.setTitle($String);

builder3 = builder2.setMessage($String);

builder4 = builder3.setNeutralButton($String,

$OnClickListener);

alertDialog = builder4.show();

雖然輸入信息中沒(méi)有指定，Bayou很智能地使用了幫助類AlertDialog.Builder。另外，Bayou還額外給對(duì)話框加上了一個(gè)按鈕，這是因?yàn)锽ayou學(xué)習(xí)到Android對(duì)話框經(jīng)常配備一個(gè)按鈕（通常用于關(guān)閉對(duì)話框）。

預(yù)覽拍攝

最后一個(gè)例子是生成預(yù)覽拍攝效果的程序。這次給定的輸入可以說(shuō)是極簡(jiǎn)了：

X類型= {}

X調(diào)用= {startPreview}

X關(guān)鍵詞= {}

Bayou生成的程序：

Parameters parameters;

parameters = $Camera.getParameters();

parameters.setPreviewSize($int, $int);

parameters.setRecordingHint($boolean);

$Camera.setParameters(parameters);

$Camera.startPreview();

這個(gè)例子充分體現(xiàn)了Bayou的智能之處。首先，Bayou自動(dòng)識(shí)別出startPreview屬于camera API。其次，Bayou在開始預(yù)覽前，首先獲取了相機(jī)參數(shù)，然后設(shè)定了預(yù)覽顯示尺寸。這正是Android camera API文檔的推薦做法！

實(shí)現(xiàn)細(xì)節(jié)

研究人員將整個(gè)系統(tǒng)命名為Bayou，該系統(tǒng)由兩部分組成，基于TensorFlow構(gòu)建的GED，以及基于Eclipse IDE構(gòu)建的草圖抽象和組合具體化。

研究人員基于網(wǎng)格搜索進(jìn)行交叉驗(yàn)證，選擇表現(xiàn)最優(yōu)的模型。

超參數(shù)設(shè)定如下：

編碼器：調(diào)用64單元、類型32單元、關(guān)鍵詞64單元。

解碼器：128單元。

32維潛向量空間。

mini-batch尺寸：50。

Adam優(yōu)化，學(xué)習(xí)率0.0006。

epoch：50。

整個(gè)模型的訓(xùn)練大約需要10小時(shí)（AWS p2.xlarge、K80、12G Ram）

結(jié)語(yǔ)

這是首個(gè)使用神經(jīng)網(wǎng)絡(luò)基于不確定的條件生成程序的研究。未來(lái)的IDE可能基于類似的模型提供極為智能的代碼補(bǔ)全。