學界 | MIT與微軟聯合論文提出深度API編程器: 可通過API調用合成新程序

機器之心編譯

參與：吳攀

讓機器學會自動編程一直以來都是人工智能研究界所追求的一個重要目標，甚至被一些人認為是實現真正通用的人工智能的關鍵。在這方麵的研究也一直是層出不窮，比如《深度 | 機器的自我進化：走向自主編程的人工智能（附提交 ICLR 2017 的自動編程論文）》和《學界 | 劍橋與微軟提交 ICLR 2017 論文提出 DeepCoder：組合其它程序代碼生成新程序》。近日，麻省理工學院和微軟研究院的研究者又發布了一篇相關論文，提出了一種可以學習使用 API 編程的方法——深度 API 編程器。機器之心對該論文的部分內容進行了編譯介紹，其中重點介紹了該方法的概述部分，更多詳情請點擊文末「閱讀原文」查閱原論文。

我們提出了 DAPIP（Deep API Programmer/深度 API 編程器），這是一個可以根據示例編程（Programming-By-Example）的係統，其可以學習使用 API 來編寫執行數據轉換任務的程序。我們設計了一種領域特定語言（DSL：domain-specific language），允許 API 輸出和常量字符串的任意拚接（concatenation）。該 DSL 由三個 API 係列組成：基於正則表達式的 API、查找 API 和轉換 API。然後我們提出了一種全新的神經合成算法（neural synthesis algorithm）來在該 DSL 中搜索與一個給定的示例集一致的程序。該搜索算法使用了最近引入的神經架構來編碼「輸入-輸出示例（input-output examples）」和建模在該 DSL 中的程序搜索。我們的研究表明：在合成基準和真實世界基準上，該合成算法在程序合成上的表現都優於基線方法。

1 引言

總體而言，這篇論文的主要貢獻有：

我們設計了一個表達式 DSL，其帶有可以編碼句法和語義數據轉換任務的 API。

我們使用神經架構在該 DSL 中自動學習了一個用於合成程序的的合成算法。

我們在 238 個真實世界 FlashFill 基準和數千個合成基準上評估了我們的係統 DAPIP。

2 目標示例

示例 1：一個 Excel 用戶想要將一些名字轉換成如圖 1 所示的形式。因為一些輸入樣本有可選的中間名，所以該用戶難以找到一個可以用於執行該任務的宏。

圖 1：縮寫名字的 FlashFill 任務示例。該用戶提供了前兩個輸出，然後學習到的程序自動生成了下麵加粗的兩項

DAPIP 為這個任務學習到了以下程序：

Concat(GetFirstChar(v), ConstStr(「. 00), GetLastWord(v))

這個學習到的程序使用了屬於正則表達式 API 的 GetFirstChar 和 GetLastWord API，其可以基於正則表達式來提取輸入字符串中的子字符串。

3 方法概述

現在，我們給出我們的學習在一個 DSL 中合成與示例集一致的程序的端到端係統的概述。我們的係統的訓練階段如圖 4 所示，測試階段如圖 3 所示。我們首先設計了一個允許使用常量字符串組成嵌套 API 調用的 DSL。在設計這個 DSL 之前，我們研究了大量真實的字符串轉換任務，以使得其有足夠的能力編碼這些任務。在訓練階段，我們使用了一個程序采樣器（program sampler）來統一從該 DSL 中采樣大量程序。對於其中每一個程序，我們都使用了一種基於規則的方法來為其構建了 5 個輸入字符串，以滿足該程序的先決條件。我們通過在這些輸入字符串上執行程序來獲取輸出字符串。

圖 3：給定一組輸入-輸出示例，使用訓練好的 R3NN 模型來從該 DSL 中采樣程序；即使是在推理的用例中，節點也會以一種獨特的離散方式擴展

圖 4：基於輸入-輸出示例，訓練該 R3NN 網絡來學習 DSL 擴展之上的分布；擴展（expansion）按一種由條件分布確定的特定順序執行。

在訓練階段，每個被采樣的程序與其對應的輸入-輸出樣本被用於訓練該 R3NN 模型，這是一個可以根據示例學習該 DSL 中的擴展之上的分布的神經架構。這些示例的編碼使用了另一種被稱為交叉相關編碼器（cross-correlational encoder）的神經架構，其可以產生一個固定維度的向量。該 R3NN 係統將這個輸入-輸出調節向量（input-output conditioning vector）、該 DSL 和其訓練程序作為輸入，並被訓練用於預測在該 DSL 擴展的集合上的一個條件分布。接下來的擴展是從這個條件分布上采樣的，這會導致形成部分樹（partial tree），然後重複該流程；你可以在對應的圖中看到潛在的指數級節點增長。

然後這個訓練好的 R3NN 模型可以在給定一組示例的情況下在該 DSL 中合成程序。這個訓練好的模型的輸入是那個輸入-輸出調節向量，然後在該 DSL 擴展的集合上生成一個分布，該擴展很有可能是構建想要的程序所需的擴展。然後該分布會被采樣，以在該 DSL 中導出程序，其中擴展的階數是由該分布確定的，如對應的圖中所示，而且該係統會返回首個與該輸入-輸出示例一致的程序。

4 領域特定語言（DSL）

這個用於基於 API 的字符串轉換的領域特定語言的句法如圖 5 所示。該語言的頂級結構是 Concat 函數，其返回其參數子字符串 fi 的拚接（concatenation）。子字符串表達式 f 可以是一個常量字符串 s、輸入字符串 v 或一個以 f 作為參數的 API 函數的結果。該 Concat 算子允許使用常量字符串來組成 API 調用。該 DSL 由 3 種 API 組成：正則表達式 API R、查找 API L 和轉換 API T。

圖 5：用於 API 組成的 DSL 的句法

5 用於搜索的神經架構

這種在 DSL 中程序上基於輸入-輸出示例的神經搜索使用了 [Parisotto et al., 2016] 中介紹的模型。首先，其輸入-輸出示例被編碼成了一個固定長度的特征向量，其目標是在輸入和輸出字符串之間獲取共享的模式。然後這種示例表征會被傳遞給程序樹（program tree）上的一個基於神經樹（neural tree）的生成模型，該模型被稱為 R3NN，可以用來生成所需的隱藏程序。我們提供了對這兩種架構的高層麵的概述。