程式合成——自動生成滿足給定規範的程式——是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，審校：袁虎。 文章為簡譯，更為詳細的内容，請檢視 原文 。