讓AI自行編寫程序：神經程序合成近期研究進展綜述

最新 02-11

作者：Neel Kant

讓計算機程序自動生成新的程序看起來是一個非常「人工智慧」的概念，事實上，它也是眾多 AI 研究者們努力的方向。2017 年以來，學界就出現了微軟的 RobustFill、Bloomberg 和英特爾的 AI Programmer、谷歌大腦的優先順序隊列訓練（PQT）等程序生成方法。近日，來自 UC Berkeley 的 Neel Kant 對於近期神經網路程序生成的發展進行了概述。

論文鏈接：https://arxiv.org/abs/1802.02353

作為一個總體領域，程序合成可以被定義為發展一個滿足一系列要求與限制的演算法。因為限制條件是被用來確定正確性的標準，所以限制條件是用來定義這個演算法的。這些條件可能包括了如速度，空間複雜性還有輸入輸出正確與否等等運行時間內性能。對於計算機科學系的學生來說，這個概念很熟悉，考試中會經常需要直接寫下三元快速排列的代碼或者填充不全一段演算法的代碼。

程序合成有很大的市場。成功的程序在未來可以操控現在人的工作：計算機編程。想像一個可以不用人來調試，重構，轉化及整合的世界。甚至可能會出現電腦程序本身不能直接解決問題，但可以提出編程問題並加以解決的世界。在數學和物理學科里，理論證明是需要人來根據已經存在的定理來產生新視角的例子。一個完整的程序合成系統可以跑一個程序來證明或推翻同樣的預測，然後這個任務可以被看成非常創新。當計算機視覺瞄準自動化一個生物複雜精細的感知系統，系統合成就是一個瞄準解決問題，邏輯和自動化它自己的領域。

這些非常強大的程序合成系統的應用使這一領域變得非常讓人著迷，但是它可能會花費幾十年的研究才能達到我們之前所展望的程度。相似的，深度學習已經得到了非常大的關注，而且已經被當成一種重要工具在每一種認知任務中被嘗試使用。這篇文章會總結一下這兩個領域最近的突破。我們可以看到，這裡成就及挑戰並存，我們應該謙虛的去追求我們的目標。

圖 1. 本論文的敘述結構。

摘要：近年來，深度學習在很多領域中取得了巨大成功，這使得研究者開始考慮智能系統是否能夠解決人類近期才開始考慮的問題：程序合成。這項挑戰與目標識別和語音翻譯不同，因為其抽象本質和對嚴謹性的高要求對人類來說都很困難。儘管神經程序合成技術距離解決該問題還很遙遠，或者與大多數現有方法相比也不具備太大競爭力，但是它發展很快，深入了解之後就會發現其具備巨大前景。本論文首先探討程序合成的問題陳述和挑戰。然後，我們回顧程序歸納模型的發展歷程，以及它們的成敗和再發展。最後，我們對比了程序合成的不同研究，並介紹了該領域未來可能有潛力的推薦研究方向。

2 神經程序歸納模型

研究者提出多種模型範式和架構來解決神經程序歸納中的多種挑戰。儘管模型傾向於共享使之易於分類的某些基本屬性，但它們在細節方面還有更複雜的結構。這種特殊性可用於解釋為什麼某些模型可以成功處理一項任務，而其他模型不行。這些細節還提示哪些屬性是通用的、哪些屬性可以高效解決神經程序歸納任務。

2.1 簡介：循環模型

循環神經網路（RNN）因其與序列數據的直觀匹配而獨樹一幟，它們還天然匹配編程任務，因為程序歸納中的輸入和輸出的規模是可變的。如果任務是程序合成，則輸出規模無法根據輸入來推斷，因此一種自然的計算方法就是一次生成一個輸出 token，輸出過程中不斷更新內部狀態。一些任務還可以建立在自然語言輸入之上，這樣多個 RNN 就可以一起工作。正如我們所見，一些模型使用外部存儲資源得到增強，這樣 RNN 就可以在不同的時間步發送請求。

2.2 卷積循環

一種非常成功的神經程序歸納模型是神經 GPU[15]，它是一種環路，但在每一個「時間步」中都涉及一個門控卷積運算。輸入數據首先嵌入到被稱為模型「內部狀態」的 3D 張量中，它是 RNN 的隱藏狀態的模擬。在時間步 t 上，模型的門控卷積運算通過卷積門控循環單元（Convolutional Gated Recurrent Unit，CGRU）運轉。這種機制與 GRU 幾乎相同，除了向量上的矩陣乘法被 3D 張量的卷積運算取代。

重要的是，這裡有一個「更新」和「重置」門，可用於保存長期記憶信息，就像 LSTM 一樣。CGRU 的輸出與輸入的形態總是相同的。在時間步 t+1 上，神經 GPI 使用的是與 CGRU（t）相同的 CGRU 操作，所以既有卷積也有循環。重點在於，對於某些輸入規模 n，神經 GPU 只簡單地應用了 n 次 CGRU 操作。在這些運算之後，模型的內部狀態被解碼以生成程序輸出。如果模型在小 n 上能成功運行，則我們希望它在更大的問題規模上通過重複迭代運算也能有效。

卷積循環是一個聰明的想法，但神經 GPU 在實現上會有一些困難。在時間步 t 上，有關問題在所有時間步 1、2……t-1 的信息都會存儲在內部狀態中，並且我們無法分別觀察之前的內部狀態。這意味著模型的內部信息包含了處理下一時間步的所有必要信息。

2.3 注意力和指針網路

上一節討論的問題可以用注意力機制解決。注意力機制很有用，它可以令解碼器沒有任何瓶頸的情況下訪問每個編碼器狀態的信息。文獻 [7] 中的神經機器翻譯技術在構成輸出時採用這種機制獨立地處理每個輸入標記。然而，更廣義地說，注意力分布可以看成生成非負的歸一化分布，例如標準的概率分布。在編碼器-解碼器範式中，這意味著解碼器可以選擇性地訪問編碼器狀態，並選擇其中最有用的進行處理。在程序歸納和合成中，注意力還可以用於放寬離散運算，例如選擇。

圖 3. 來自輸入字典的關於目標指針的可視化表徵。

指針網路（Pointer Networks，Ptr-Nets）[9] 可能是對注意力機制的最直接的非平凡應用，其將注意力機制的 RNN 應用到了神經程序合成中。Ptr-Nets 中涉及的運算總結如下：

按序饋送輸入到模型中，作為編碼器。編碼器的隱藏狀態 e_1 . . . e_k 被全部記錄。

一旦輸入完成，模型將按序對生成注意力分布，其中 d_t 是當前的解碼器隱藏狀態。這些分布在訓練過程中作為軟選擇，並且所有分布都可以用於損失函數和梯度下降中。

重要的是，Ptr-Nets 可以求解比訓練時使用的輸入規模更大的問題。這是泛化能力的直接標誌，但很容易推出，隨著輸入規模量級的增加，模型的性能將大幅降低。這歸咎於神經程序歸納模型的存在癥結。雖然這些模型可以歸納和訓練時使用的輸入規模相當的程序，但幾乎不能保證其泛化到更大規模程序以及極端情況的性能。

2.4 注意力結合記憶機制

神經圖靈機（Neural Turing Machine，NTM）[4] 引入了用外部記憶增強神經網路的概念。實際上，此時神經網路將作為一個控制器，執行記憶的讀取和寫入命令，而不是用其自身的參數作為記憶的主體。外部記憶的用矩陣 M∈ R^m×n 表示：

基於內容求解：對一個讀取的向量 v∈ R^n，返回結果 u∈ R^m，其中 u 表示每個內存槽內容和讀取向量的相似度。

基於定位求解：讀取/寫入向量 v∈ R^m 表示被讀取/寫入的關於記憶索引的注意力分布。

圖 4. 通過基於內容求解的注意力步驟以獲得讀取輸出 w_t。控制器（LSTM）的輸出是完全可微的。

這兩個機制非常簡單優雅。在每個時間步上，NTM 採用輸入並生成讀取和寫入的命令，將 RNN 控制器的輸出與記憶進行交互。然而，對比 Ptr-Nets，該論文中展示的結果是非常初級的，特別是在問題規模方面。而任務本身對於演算法也不複雜。儘管更加靈活，且表達力更強，但是 NTM 的訓練難度要高得多。

Graves 等人採用了 NTM 的思想，進一步提出了可微神經計算機（Differentiable Neural Computer，DNC）[14]。DNC 可以用多個讀寫頭訓練，並有額外關於它的記憶的數據。它有兩種特別性質：

時間連接（Temporal Linkages）：關於記憶寫入順序的相關信息。它能允許控制器推理數據之間的關係，因為時間連接在演算法中是很常用的。

內存利用（Memory Usage）：關於記憶的索引是否包含有用信息的信息。理論上，它應該能通知和簡化控制器對讀取和寫入的選擇。

圖 5. DNC 圖示 [14]，注意 b 中有多個讀向量（read vector），d 中描述了一些聯結。

DNC 仍然使用 RNN 控制器作為其主核心，使用基於注意力的定址技術。但是，和 NTM 類似，與更簡單的模型如 Pointer Nets 相比，DNC 似乎更難執行高效訓練。

2.5 內存和預定義基元

之前的所有模型從設計上看都是聯結主義。現在，我們將嘗試兩個模型：神經編程器 [17] 和 Neural RAM [16]，僅使用明確定義的數據變換。具體來說，控制器不向內存發送直接可讀／寫的指令，而是對數據執行一種可能的一元／二元運算，如基本算術（如加、乘）、邏輯運算符（如相等比較、小於）和聚合運算符（最小、最大）。這兩種模型可以能夠運行的時間步可多於僅描述問題的必要時間步數。這使得模型能夠組合這些基本運算，創建複雜程序。

具體來說，典型的組件有：

RNN 控制器：使用來自（a）控制器外部和／或（b）存儲單元的序列輸入，自動以嵌入格式出現。

習得的函數可以在（a）可執行的預定義運算和（b）可執行運算的數據上生成注意力分布。

可讀寫數據的存儲單元。這還可以作為指定輸出位置（Neural RAM）。

兩種模型存在一些有趣的差異。神經編程器設計為使用自然語言輸入。當然，它們通過 RNN 控制器變成向量化的嵌入格式，但是該模型仍然需要學習英語的語義。類似地，神經編程器具備使之在存儲上執行資料庫類型運算的模塊，該模型可從資料庫中返回多個元素。從這個層面上看，神經編程器是為了成為一個自動問答系統，學習回答問題所需的潛在程序。因此，解決方案可能是綜合的，但是比問題中存在表徵的情況需要的步驟要少一些。

圖 6：神經編程器原理圖 [17]。輸入是表徵序列，需要多個時間步來運行。

而 Neural RAM 專門創建高度綜合的程序。由於該模型的 14 個預定義模塊都是原子性的，因此這些程序可以使用數百個時間步來完成。

好消息是與 NTM 和 DNC 相比，Neural RAM 可創建連貫的程序，可運行更多的時間步。這可能是因為運算並不模糊，即使使用變化比重的注意力來選擇運算。當使用誤差反向傳播進行監督時，該模型理論上知道其中一個基元運算是正確的，無需僅依賴於寫入的存儲（NTM、DNC 的情況）。該模型還可以選擇何時使用 sigmoid 的末尾單元終止程序，何時超出閾值，何時完全停止模型。需要注意的是，與 NTM 相比，任務本身沒有那麼複雜，Neural RAM 甚至無法嘗試 DNC 比較擅長的圖形問題。

2.6 函數層級（Function Hierarchy）

在某些情況下，監督信號會非常弱，因此訓練數據很容易過擬合。神經編程解釋器（Neural Programmer-Interpreter，NPI）[19] 試圖通過增加模型的複雜度和監督強度解決這些問題。其中非常重要的進步是令函數在新的堆棧幀中靈活調用子函數。這可以在新的幀中通過將 RNN 控制器的隱藏狀態重置為零，將給定嵌入程序、參數和環境作為輸入來實現。

這些堆棧幀可以終止，並通過一個 Sigmoid 末端控制返回調用幀（caller frame），和 Neural RAM 一樣。但子函數結束時，調用子函數之前的控制器隱藏狀態會被儲存起來。當頂層函數結束時，整個模型將結束執行。

圖 7. NPI [19] 便條簽（左）和執行堆棧軌跡（右）。注意：事實上最低級別的指令是 ACT，這裡為讀者說明下。

核心概念是 NPI 可以抽象和更高階地控制該程序。當新的函數和參數被調用時，它可以被表達成一個嵌入格式的向量。這個嵌入格式的向量通過聯合在一起的參數嵌入、整體環境和通知子函數未來調用的語境構建而成。

3 歸納任務上的模型性能分析

這部分介紹了四個難度遞增的例子。難度來自於所需的控制流級別、目標程序運行時複雜度（如果存在一個人造程序），和訓練數據的可用性。

3.1 算術

我們可以比較一下 Neural GPU、NPI 與 NPL，這些模型已經用加法任務測試過了，並且在同樣的問題大小環境下完美地進行小數加法。這些模型也實現了函數層級，因此它們的泛化性能更加可靠。