神經引導演繹搜索：兩全其美的程序合成方法

摘要： 程序合成——自動生成滿足給定規範的程序——是AI領域的一個主要挑戰。它除了改變設計軟體的方法外，它還具有徹底創新任務自動化的潛力。

程序合成——自動生成滿足給定規範的程序——是AI領域的一個主要挑戰。它除了改變設計軟體的方法外，它還具有徹底創新任務自動化的潛力。沒有編程技能的終端用戶可以很容易地提供期望的程序行為的輸入—輸出實例。微軟Excel中的Flash Fill功能，是一個特別成功的技術應用，證明了一個單一的例子往往足以生成正確的程序。

圖1.Flash Fill僅僅從一個示例自動地完成一個字元串的轉換任務

設計程序合成系統是具有挑戰性的。你需要確保合成的程序滿足那些所提供的實例；還需要確保它的泛化性；程序必須在不可見的輸入上產生所期望的輸出。許多可能的程序與一個單獨的示例是一致的，挑選這個最通用的程序是一個重要的ML挑戰。最後，面向用戶的合成系統應該是運行快速的。

最高水平的程序合成研究遵循兩個主要方向中的一個：符號或神經。符號系統使用邏輯推理和一組指定域規則來搜索滿足所提供的示例的程序。它們被設計成通過構造產生一個令人滿意的程序。但是，設計這樣的規則要涉及巨大的工程努力，並且所得到的搜索過程可能是指數級的緩慢。

相對比來說，神經系統依賴於點對點的可微的和可訓練的網路來生成程序。雖然更容易執行和訓練，但是這樣的網路需要大量的數據來學習程序合成。因為數據通常是隨機生成的，神經系統經常不能獲取現實世界的模型，並且導致產生泛化很差的非自然程序。此外，神經網路的純統計特性不提供對合成的程序的任何正確性保證。

在第六屆國際學習表徵會議（ICLR）上，來自微軟研究的研究人員展示了神經引導演繹搜索（NGDS）的研究結果，它結合了兩種AI方法中最好的一個。它建立在由符號合成系統所採用的演繹搜索過程之上，但是是以神經引導來增強 ——一個預測每個分支決策的優先順序的模型，即從該分支產生的最佳程序的泛化評分。

如圖1中的任務。它最通用程序用來執行三個字元串的子表達式的級聯：第一個單詞的第一個字元，一個常量字元串「.」，以及最後一個單詞。

在搜索的過程中，一個合成系統首先決定在正確程序中的頂級操作符是否是一個級聯或是一個原始子表達式（子字元串或常量字元串）。如果它決定頂級操作符是級聯的，則系統進一步減少所提供的輸入——輸出實例到兩個級聯的子表達式的必要的輸入-輸出示例。這些邏輯決策在搜索過程中引入了分支，其中大部分產生滿足示例的程序，但不泛化到其它的輸入。這樣的分支可以通過使用神經引導來消除優先順序。

圖2.演繹搜索過程的一個片段，尋找滿足給定輸入輸出實例的最通用的程序。

在搜索樹中的每個分支點，將當前狀態注入一個神經模型，該模型預測可能從每個分支產生的最佳程序的質量（如綠色分布曲線；更高的形狀對應於更有希望的分支）。

重要的是，在搜索過程中的子問題是獨立的；我們可以推理一個滿意的子問題的程序，而不考慮它推導出的更大問題的的因素。這允許我們可以通過在搜索中記錄所有中間決策來產生大量的訓練數據。從385個字元串轉換任務中，我們生成超過400000個實際的訓練實例。

我們評估了神經引導演繹搜索（NGDS）在各種現實生活中的字元串轉換任務，並將其與最先進的程序合成系統進行比較：PROSE（純符號）、RobustFill（純神經）和DeepCoder（神經-符號混合）。雖然NGDS和散文被給了一個單一的輸入-輸出實例，但是我們提供了RobustFill和DeepCoder的額外實例，因為它們沒有明確地為程序泛化而設計。在我們的多個實驗中，NGDS在基線PROSE系統中獲得了67%的加速（一些任務的表現提高到了12倍），同時保持了任務完成的相同精度。這些基線方法不能保持相同的精度/性能平衡，或者一個不行，或者兩個都不行。

圖3. NGDS與基線方法的準確性和平均加速率：PROSE，DeepCoder 1-3個例子（DC 1-3），RobustFill 1-3個例子（RF 1-3）。

我們相信，程序合成的新進展可以通過神經和符號方法的結合來實現。邏輯推理和正確的程序泛化增強了神經系統的能力，結合了兩種人工智慧方法的優點。我們的神經導向演繹搜索研究代表了神經符號程序合成的開創性成就。我們期待著把它擴展到更具挑戰性的應用領域。

以上為譯文。

本文由阿里云云棲社區組織翻譯。

文章原標題《Neural-Guided Deductive Search: A best of both worlds approach to program synthesis》，譯者：Mags，審校：袁虎。

本文為雲棲社區原創內容，未經允許不得轉載。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！