你和「懂AI」之間，只差了一篇論文
很多讀者給芯君後臺留言，說看多了相對簡單的AI科普和AI方法論，想看點有深度、有厚度、有眼界……以及重口味的專業論文。
為此，在多位AI領域的專家學者的幫助下，我們解讀翻譯了一組頂會論文。每一篇論文翻譯校對完成，芯君和編輯部的老師們都會一起笑到崩潰，當然有的論文我們看得抱頭痛哭。
同學們現在看不看得懂沒關係，但芯君敢保證，你終有一天會因此愛上一個AI的新世界。
讀芯術讀者論文交流群，請加小編微信號：zhizhizhuji。等你。
這是讀芯術解讀的第61篇論文
AAAI 2017 Machine Learning Applications
神經網絡示例編程
Neural Programming by Example
北京航空航天大學
Beihang University
【摘要】示例編程(PBE)的目標是自動推斷電腦程式，從簡單的輸入和輸出中完成某個任務。在本文中，我們提出了一種基於深度神經網絡DNN(Deep Neural Networks)的神經網絡示例編程(NPBE)，該模型可以從輸入輸出的字符串中學習，並能誘導解決字符串處理問題的程序。我們的NPBE模型有四個基於神經網絡的組件：一個字符串編碼器、一個輸入輸出分析器、一個程序生成器和一個符號選擇器。我們在電子製表軟體系統中通過訓練它端到端地解決一些常見的字符串處理問題的處理來展示NPBE的有效性。結果表明，該模型能有效地誘導字符串操作程序。我們的工作是向教授DNN生成電腦程式的一步。
1 引言
示例編程(Programmingby Example，PBE，也稱為通過演示進行編程，或歸納合成)(Lieberman2001; Cypher and Halbert 1993; Gulwani 2011)給機器提供了推理和生成新程序的能力，而不需要大量的人力監督。在PBE系統中，用戶(通常是非專業的程式設計師)提供了一個含有他們想要執行的任務的輸入輸出示例的機器，該機器能自動為完成任務推理一個程序。PBE的概念已經成功應用於電子製表軟體系統，如MicrosoftExcel (Gulwani et al. 2015)、計算機輔助教育(Gulwani2014)和數據提取系統(Le和Gulwani 2014)。
例如，如果用戶提供以下輸入和輸出示例：
john@example.coim john
james@company.com james
PBE系統應該理解用戶想從電子郵件地址提取用戶名。它會自動地合成一個程序Select(Split(x，@)，0)，其中x是輸入字符串，拆分Split是根據分隔符拆分一個字符串，選擇Select是從字符串數組中選擇一個子字符串。如果有一個新的電子郵件地址jacob@test.com，這個程序將輸出字符串jacob。
Lau等(2003)應用版本空間代數來尋找可能的程序。最近的PBE方法(Gulwani 2011)主要採用搜索技術來查找滿足輸入輸出示例的預定義函數的組合(如字符串拆分和連接)。這些方法創建了一個有向無環圖(DAG)，並搜索可以從給定輸入狀態生成輸出字符串的函數序列。這些方法可以有效地生成複雜的字符串處理程序，但需要複雜的程序合成算法的設計。
在本文中，我們提出了一種基於DNN的示例編程方法。我們訓練神經網絡使其能自動從輸入輸出的例子中推斷程序。在過去的幾年裡，DNN的研究在計算機視覺(Krizhevsky,Sutskever,Hinton2012)、語音識別(Mohamed,Dahl, Hinton 2012)，自然語言處理(UNKbert et al. 2011)和APIlearning(Gu et al. 2016)等多種領域取得了顯著的成果。最近，研究人員已經探索了應用DNN解決編程和計算相關問題的可行性(Neelakantan, Le, and Sutskever 2015; Reedand de Freitas 2015; Graves, Wayne, and Danihelka 2014; Kurach, Andrychowicz,and Sutskever 2015)。我們的工作是基於類似的想法，即應用DNN來推斷和執行電腦程式。不同於現有的工作，我們將目標對準PBE問題，並對輸入、輸出和程序三元組的神經網絡PBE模型進行訓練。
我們的方法，稱為NPBE(NeuralProgramming by Example，它教DNN為字符串操作編寫一組預定義的原子操作。給定一個輸入輸出字符串對，NPBE模型被訓練成合成一個程序——一系列函數和相應的參數，將輸入字符串轉換為輸出字符串。這個程序是由原子函數生成的，一個函數可以使用以前一個函數的執行結果。因此，該模型能夠僅使用幾個預定義的操作組成複雜的程序。
我們已經在大量的輸入輸出字符串上為45個字符串操作任務對NPBE進行了大量的實驗評估，結果令人鼓舞。我們發現我們的模型可以泛化超越訓練輸入/輸出字符串和訓練參數設置。我們的工作是將DNN應用於編程問題的早期嘗試之一。
2 相關工作
Reed等人(2015)開發了一種名為神經網絡編程解釋器的框架，通過神經網絡來誘導和執行程序。他們的方法把程序當作嵌入，使用神經網絡來生成程序執行的函數和參數。他們的模型接受了執行跟蹤的訓練，並且可以在許多不同的場景中使用。然而，他們的模型不能直接應用於PBE的問題，因為他們的模型的輸入是由任務編碼的環境，而我們的工作是致力於PBE，而且我們的模型的輸入是輸入-輸出的例子。
神經網絡程式設計師(Neelakantan,Le, and Sutskever 2015)是一種神經網絡，可以通過幾個步驟來調用一組操作來增強。它被訓練用於輸出程序執行的結果，而我們的模型被訓練成輸出由符號表示的程序。NeuralEnquirer (Yin et al. 2015)是一個完全神經網絡的端到端微分模型，能夠建模和執行表查詢相關程序。在數據表上使用神經網絡，神經網絡詢問器的執行是「柔和」的，而我們的工作並不適用於輸入輸出字符串的軟執行。Bosnjak等(2016)提出了一種用於語言等的抽象機器的神經網絡實現。它可以從輸入輸出數據的訓練中學習程序的行為。然而，它需要程序草圖作為輸入。
我們的模型也與使用遞歸神經網絡解決編程和計算相關問題的工作有關。Graveset al .(2014)開發了一種神經網絡圖靈機，它能夠通過外部存儲器學習和執行簡單的程序。Zarembaet al .(2015)使用執行跟蹤來訓練遞歸神經網絡學習簡單的算法。Linget al .(2016)開發了一種從自然語言和結構化規範中生成程序代碼的模型。指針網絡PointerNetworks (Vinyals, Fortunato, Jaitly 2015)使用一個關注的遞歸模型來解決複雜的算法問題。
有一些機器學習方法用於解決PBE問題。Lau等(2003)應用版本空間代數，有效地搜索可能的程序。根據輸入輸出對，遺傳編程(Banzhafet al. 1998)可以從候選群體中演化出有用的程序。Liang等(2010)提出了一種採用分層貝葉斯方法在給定的例子中來學習簡單程序的方法。Melon等(2013)使用機器學習，通過學習與文本特徵相關的權重來加速搜索可能的程序。他們的方法需要精心設計的特性來減少搜索空間，而我們的方法則減少了搜索空間，並通過DNN的學習表示避免了特徵工程。
3 NPBE模型
問題聲明：讓S表示字符串的集合。對於輸入字符串x∈S和輸出字符串y∈S，我們的模型是引入一個函數f∈SS，所以y=f(x)。我們的模型的輸入是輸入輸出對z:=(x,y)∈S2，我們希望得到正確的函數f，使得當用戶輸入另一個字符串∈S,我們可以生成所需的輸出，而不需要用戶顯式指定函數。
圖1 NPBE總體架構
本文提出的NPBE模型(圖1)由四個模塊組成：
程序生成器將運行幾個步驟，每個步驟都可以訪問先前步驟的輸出，從而使模型能夠僅使用一些預定義的原子函數來組成強大的程序。而傳統的深度學習模型試圖對給定的x生成輸出y，並最終擬合出函數f使得y=f(x)，我們的模型直接學習生成函數f，並擬合出高階函數g使得f = g(x,y)且f滿足y = f(x)。
3.1 字符串編碼器
給定一個由一系列字符{i1, i2，…iL}組成的字符串，字符串編碼器輸出一個字符串嵌入和一個字符嵌入列表。首先，通過隨機初始化和可訓練的嵌入矩陣，將序列中的每個字符ik映射到8維原始嵌入e(ik)。為了更好地呈現和處理一個字符，每個字符的上下文都與字符的原始嵌入相融合，以構建字符嵌入。讓l(ik)表示字符ik的左上下文和r(ik)作為ik的右上下文。l(ik)和r(ik)分別用式(1)和式(2)計算得到l(0)= r(L + 1)=[0]c。在我們的實施中，fl和fr是LSTM(Hochreiter和Schmid - huber 1997)的更新函數。
每個字符的字符嵌入是字符ik和e(ik)的左/右上下文的組合，如式(3)所示，其中[•;•]表示向量的連接，max是點集最大池element-wisemax-pooling。We和be是構建全字符嵌入的參數矩陣和矢量。
Ck將會被程序生成器的注意力機制所使用。
我們還需要一個可以總結整個字符串的表示，這樣我們就可以從輸入和輸出字符串的字符串嵌入中誘導轉換。我們使用多層雙向LSTM(Graves和schmidthuber 2005)來概況Ck。每一層的前向和後向LSTM的輸出被連接並成為下一層的前向和後向LSTM的輸入。將前向和後向LSTM的前幾層的最後一個隱藏狀態進行合併，通過一個最後的全連接層產生字符串嵌入s∈RS。輸入和輸出字符串的處理是分開但同享同一個神經網絡架構和參數，因此對輸入和輸出字符分別生成cI,1,……,cI,L, sI和co,1,……co,L, so。
3.2 輸入/輸出分析器輸入/輸出分析器將輸入和輸出字符串嵌入到轉換嵌入中，從而描述輸入和輸出字符串之間的關係。令t∈RT表示這個變換嵌入。sI∈RS，sO∈RS分別是輸入和輸出字符串嵌入。輸入/輸出分析器可以表示為式(4)，在我們的實現中，fIO只是一個具有激活函數tanh的2層全連通神經網絡。
3.3 程序生成器Program Generator圖2 程序生成器的圖表
程序生成器(圖2)是NPBE的核心。它會一步一步地生成幾個函數和相應的參數「嵌入」。在t時刻函數的嵌入計算方程為(5)，這是一個完全連接的神經網絡，它採取t時刻的變換嵌入和程序生成器的執行歷史ht-1∈RH(h0=t)作為輸入。同樣，在t時刻的函數的參數嵌入由式子(6)計算。然而，函數的參數通常非常複雜，很難準確預測。所以注意力機制(類似於一個用於神經機器翻譯模型(Bahdanau,Cho,Bengio2014))應用於在輸入和輸出字符串上用注意力去完善的原始參數嵌入ar,t。這是在式(7)中總結出來的。最後，函數嵌入ft，完善的參數嵌入at，以及之前的歷史嵌入ht-1，都被嵌入到如式(8)所示的新歷史嵌入。Wh和bh分別是參數矩陣和生成的新歷史向量。
函數ffunc和fargs可以是多層完全連接的神經網絡，在我們的實驗中，我們只使用一層神經網絡。式(7)中的函數fatt是通過對輸入和輸出字符串按照如下處理來實現的：
W1，W2，vI和W3，W4，vo分別是處理輸入和輸出字符串的參數。請注意，用於輸入和輸出字符串的注意力架構是相同的，但有不同的參數。最終的參數嵌入是通過將注意力集成在輸入、輸出和嵌入的原始參數之上生成的：
Watt和batt是組合的參數。
3.4 符號選擇器
符號選擇器使用函數嵌入ft和由程序生成器生成的參數嵌入at來選擇合適的函數和該函數的相應參數。由式(16)產生在P原子函數之上的概率分布αfunc,t∈[0,1]p，其中Uf∈RP*F是存儲原子函數表示的矩陣。由RNN(Choet al. 2014)解碼的參數嵌入at(表示參數的摘要)是根據之前的輸出和式子（17）中的at來表示。st,0,…,st,i-1是LSTM的隱藏狀態，其中st,0=[0]H。這樣，參數序列由RNN生成。第i個參數在t時刻在Q可能的參數αarg,i,t∈[0,1]Q的概率分布是用式(18)產生的，其中Ua∈RQ*A是存儲可能參數的表示的矩陣。
3.5 訓練我們使用輸入輸出字符串對{Хi,Уi}以及作為函數序列和相應參數的程序來對NPBE端到端進行訓練。每個程序可以將Х轉換為Уi，其中i表示第i個訓練樣本。對於每個輸入輸出對我們可以生成一個T個函數的序列，而且每個函數都有一個參數列表a∈AM，其中A是一組可能的參數，M是一個函數可以取的最大的參數個數。在我們的執行中，T=5, M=5。
訓練是在給定{Хi,Уi}情況下，由直接最大化正確程序的log似然可能指導的：
其中θ是我們模型的參數。將隨機高斯噪聲(Neelakantanet al. 2015)注入到轉換嵌入和參數嵌入中，以提高NPBE的泛化能力和穩定性。
4 實驗
4.1 實驗設置
NPBE模型需要誘導一個程序，該程序由一個僅基於一個輸入輸出字符串對的函數序列組成。在本節中，我們將描述對NPBE模型的評估。在我們的實驗中，我們定義了7個基本的字符串操作函數和1個空函數作為原子函數(表1)。為了簡單起見，每個程序最多可以由5個函數組成。我們定義了一組常量符號(表2)，我們的模型可以從中選擇參數。常量符號包括整數和分隔符。Select函數使用整數作為字符串數組的索引。負整數用於從尾部訪問數組元素。整數符號的設計支持訪問最多7個元素的數組。分隔符被拆分Split和連接Join使用，以拆分字符串或通過分隔符連接字符串數組。我們還定義了一些特殊的符號。例如，符號x表示輸入字符串、ol、o2、o3和o4分別表示第一、第二、第三和第四個操作的輸出。NoArg符號表示當前位置沒有預期的參數。請注意，儘管在我們的實驗中，我們對程序中的函數和參數提供了一些約束，但是我們的模型可以很容易地擴展以支持新的函數和參數。
表1 原子函數
表2 我們模型的常量符號
為了獲得培訓數據，我們首先根據45個預定義的任務在不同層次的複雜性上生成程序。任務是按特定順序排列的函數序列，但是每個函數的參數不是固定的。定義任務的原因是我們希望我們的模型生成的程序是語法正確和有意義的。45項任務範圍從簡單的任務，如輸入到某個常量字符串的連接，到更複雜的任務，包括拆分、連接、選擇、ToUpper和連接函數等。例如，拆分split和加入join的任務是先將輸入字符串拆分為分隔符，然後使用另一個分隔符加入和拆分字符串數組。程序源自這個任務可是Join(Split(x,/」),「:」)，它將輸入字符串x根據分隔符「/」分離，然後將生成的子字符串使用分隔符「：」組合。完成一個任務的平均函數數是3.5個。
對於所有的任務，我們總共產生了大約69000個訓練程序。我們為每個程序Pi生成一個隨機的輸入字符串Xi，它應該是一個有效的程序Pi的輸入。接下來,我們在Xi上，通過實際運行Python程序實現以應用程式Pi，得到輸出字符串Yi。我們將Xi和Yi最長限定為62個字符。之後，我們使用{Xi, Yi}作為輸入數據，輸入到我們的模型，而Pi作為訓練目標。這個程序產生的方式是，如果有多個程序可以導致相同的Xi，那麼只選擇一個特定的程序。因此，對模型的預測希望的程序是沒有歧義的。給定程序Pi，輸入字符串Xi總是隨機動態生成以減少過擬合。表3為模型提供了一些具體的輸入輸出示例。
表3 用於NPBE的輸入輸出對例子。對應的程序（從上到下）分別是：1）Concatenate(「Hello 」, Select(Split(x, 「@」), 0), 「, have fun!」)；2）Concatenate (ToUpper(Select(Split(x, 「/」),1)), 「-」, Select(Split(x, 「/」), 0))；3)Select (Split (Select (Split (x, 「/」), -1), 「.」), 0). 注意，GetConstString是一個佔位符，第一個被評估為「Hello」，第二個被評估為「，havefun!」
為了訓練NPBE，我們選擇了RMSProp(Tieleman和Hinton 2012)作為優化器，並將最小批mini - batch大小設置為200。我們將變換嵌入t和歷史嵌入的維數h設為256，將函數嵌入f設為16，並且將參數嵌入a設為64。實際的訓練過程依賴於一個自適應的課程 (Reed和de Freitas 2015)，其中一個特定任務的訓練頻率與測試的錯誤率成正比。每10個時期，我們估計預測誤差。我們使用具有足夠溫度的softmax來採樣每項任務的頻率，這些任務將在接下來的10個周期進行。因此，具有較高錯誤率的任務將比在接下來的10個時代中錯誤率低的任務更頻繁地被取樣。
NPBE的評估是為了回答以下研究問題：
4.1.1 研究問題1: 在生成程序中NPBE的精確度是什麼？在這個研究問題中，我們使用隨機生成的輸入輸出字符串來評估NPBE生成程序的準確性。例如，給定一個隨機輸入輸出對：25/11/16和25:11:16 (沒有出現在訓練數據)，我們想測試是否還能生成正確的程序Join(Split(x,「/」),「:」)。要回答這個研究問題，我們為每個任務生成隨機輸入輸出字符串1000次，並應用訓練的NPBE模型。由NPBE產生的程序只有當模型正確預測所有五個功能(如果不到五個，則填充上NoFunc符號)和所有的參數函數(也填充上NoArg符號)是才被認為正確的(因此總共5+ 5 * 5 = 30個位置)。我們還將我們的模型與RNN編碼器-解碼器模型(Cho et al. 2014)進行了比較，該模型使用LSTM和LSTM注意力機制進行了實現，所有的參數都與我們的模型相似。
4.1.2 研究問題2: NPBE能用之前看不到的參數生成程序嗎？在這個研究問題中，我們測試了NPBE的泛化能力。我們使用參數設置沒有出現在訓練集中的程序來評估我們的模型。例如，如果程序Join(Split(x,「/」),「:」)出現在訓練集中，我們想知道是否NPBE還可以用於沒有出現在訓練集中的Join(Split(x,「@」),「-」)。為了回答這個研究問題，我們設計一個包括大約19000個前所未有參數的程序測試集。這個實驗是在19個有複雜的參數組合的任務中進行的(對於簡單的任務，很少可以選擇參數，所以我們跳過它們)。
4.2 實驗結果研究問題1: 在生成程序中NPBE的精確度是什麼？
表4給出了NPBE預測程序的評價結果。NPBE取得的Top1的平均精度為74.1%，這意味著在測試中74.1%的輸入輸出對，NPBE能夠成功地生成相應的程序。我們發現模型預測錯誤最有可能發生在Select的整數參數上，因為神經網絡不擅長計數。因此，我們也讓模型在嘗試預測Select的整數參數時給出3或5個預測。Top3和Top5的平均精度結果分別為85.8%和91.0%，這意味著在測試中85.8%和91.0%的輸入輸出對，NPBE分別在前3和前5的結果中成功返回相應的程序。結果表明，NPBE模型可以為大多數任務生成正確的程序。
表4 生成程序的結果
作為一個例子，給定輸入字符串「17/apr/2016」和輸出字符串「APR-17」，我們的模型需要誘導一個由Split，Select，Case Change，Concatenate組成的程序。對於這個任務，我們的模型在35.8%的案例中給出了完全正確的程序。如果我們允許模型對Select的整數參數給出3個或5個預測，那麼精確度將提高到73.2%或94.0%。
LSTM和具有注意力機制的LSTM(即LSTM-a)的結果也見表4。請注意，LSTM和LSTM-a的Top1、Top3和Top5精度幾乎相同，因此只報告了Top1的準確性。我們發現，普通的編碼器解碼器模型可以解決最簡單的任務，但不能解決更複雜的任務。結果表明，NPBE顯著優於普通的編碼器解碼器模型。
研究問題2: NPBE能用之前看不到的參數生成程序嗎？
我們測試了NPBE對具有看不見參數設置的程序的泛化能力。表5給出了平均Top5精度結果。結果表明，對於可見和不可見的參數設置，我們的模型實現的精度沒有太大的差異。例如，Split任務，Join首先將一個輸入字符串分隔符(如「/」)，然後用其他分隔符(如「:」)連接生成的子字符串。這個任務在訓練集上達到了93.6%的準確率。對於不同的參數(例如，先用「@」將輸入字符串拆分，然後再由「-」來連接產生的子字符串)，在訓練集中不存在，NPBE仍然可以得到93.9%的準確率。結果表明，NPBE可以推廣到不可見的程序參數，而不需要對特定的參數組合進行過度擬合。
表5 具有可見參數和不可見程序參數的結果
4.3 討論和未來工作
NPBE背後的意圖是使模型能夠自動地從輸入輸出字符串中學習相關的特性，並利用所學的特性來歸納出正確的程序。本文的目的不是直接與現有的PBE系統競爭。相反，我們證明DNN的使用可以識別字符串轉換中的特性，並且可以通過輸入輸出對學習精確的程序。
目前，NPBE不能推廣到完全看不見的(如分割、加入、連接)，從來沒有出現在訓練集的任務。在未來的工作中，我們將努力構建模型，真正「理解」原子函數的含義，從而能歸納到看不見的任務。
5 結論
在本文中，我們提出了基於DNN的實例編程(PBE)模型。NPBE可以通過推理出函數的組成和相應的參數來誘導基於簡單輸入輸出對的字符串操作程序。我們已經證明，利用DNN的新方法可以成功地應用於實例系統的編程。我們的工作也探索了在深度學習中學習高階函數的方法，是向DNN傳授電腦程式的一步。
論文下載連結:
https://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14482/13948
留言 點讚 發個朋友圈
我們一起探討AI落地的最後一公裡
推薦文章閱讀
長按識別二維碼可添加關注
讀芯君愛你