彩雲科技提出結合組合子抽象的神經編程器-解釋器，提升通用性和可學習性

選自OpenReview

作者：Da Xiao、Jo-Yu Liao、Xingyuan Yuan

機器之心編譯

參與：李舒陽、劉曉坤

近日，ICLR 2018 接收論文公布，國內人工智慧公司彩雲科技的一篇論文被此大會接收。在此論文中，作者們通過引入組合子抽象的方法，可以建立一種新的架構 CNPI，使得核心控制器需要解釋的程序顯著減少且程序複雜度顯著降低，從而克服神經編程器-解釋器（NPI）在通用性和可學習性存在局限性的問題。

論文：IMPROVING THE UNIVERSALITY AND LEARNABILITY OF NEURAL PROGRAMMER-INTERPRETERS WITH COMBINATOR ABSTRACTION

論文地址：https://openreview.net/pdf?id=rJlMAAeC-

摘要：為了克服神經編程器-解釋器（NPI）在通用性和可學習性方面的局限，本文提出在神經編程中引入組合子抽象（combinator abstraction）方法，並為此提出了 NPI 的一種新架構——組合神經編程器-解釋器（CNPI）。有了組合子抽象，CNPI 的核心控制器需要解釋的程序顯著減少且程序複雜度顯著降低，同時在核心控制器與其他組件的協同作用下，CNPI 仍然可以表示和解釋任意複雜度的程序。本文提出用四個組合子來表徵最常見的四種編程模式。由於組合子數量有限，形式簡單，並且減少了核心控制器的解釋工作量，我們可以構造出一個 CNPI，使之適用於所有可「組合子化」（即可用組合子描述）的程序，這樣足以解決大多數演算法任務。此外，通過恰當地設計課程，可能直接用策略梯度增強學習來訓練 CNPI，無需提供程序執行軌跡。

1 引言

教機器學程序是個有挑戰的任務。研究者提出了很多模型，例如神經圖靈機（Graves et al., 2014）、可微分神經計算機（Graves et al., 2016）、神經 GPU（Kaiser & Sutskever, 2015）、神經編程器（Neelakantan et al., 2015）、神經隨機存取機（Kurach et al., 2015），還有神經編程器-解釋器（Reed & de Freitas, 2016）。這些模型通常含有可微分存取的存儲組件。大多數模型以程序輸入-輸出對作為訓練數據，訓練後的神經網路可以成為特定的目標程序，模仿一種特定的圖靈機。

這些模型中的一個特例是神經編程器-解釋器（NPI）（Reed & de Freitas, 2016）及其支持遞歸的擴展形式（Cai et al., 2017，在該論文中被稱為 RNPI）。NPI 包含三個組件：一個核心控制器，通常由遞歸神經網路（RNN）實現；一個程序存儲器，用於存儲已學得程序的嵌入向量；還有多個特定域編碼器，讓單個 NPI 在多種環境中均可運行。核心控制器不學習任何特定的程序，而是學習解釋任何一個用向量表示的程序，即模仿一個通用圖靈機。核心控制器（即解釋器）與已學得程序的存儲器（即編程器）相結合，使 NPI 能夠通過合子程序來學習新的程序，其架構更靈活也更具可組合性。然而，NPI 在理論和實際應用方面依然存在一些局限。

NPI 模型之所以可能適用於多任務學習、遷移學習和終身學習，是因為研究者假設 NPI 理論上具有通用性，即能夠表達和解釋任何程序。由於 NPI 僅靠核心控制器來解釋程序，通用性意味著一個固定的核能夠解釋潛在的大量程序。想要持續地學習新程序並復用已學得的程序，一個普適且固定的核至關重要，因為一旦核的權重改變，學習了新程序就可能沒法解釋學過的舊程序了。儘管最早提出 NPI 的論文（Reed & de Freitas, 2016）實驗顯示單個共享的核可以解釋 21 個程序，涵蓋五種任務，並且訓練過的固定核 NPI 還可以學習一個簡單的新程序 MAX，但尚不清楚普適的 NPI 是否存在、究竟能夠多普適。具體而言，考慮到所有可能的程序是個無限集，能夠被一個固定核解釋的程序子集並沒有被顯式定義。就算存在普適的 NPI，用 Cai et al. (2017) 論文中提出的驗證方法也很難保證其通用性，因為需要驗證無窮個程序。

實際應用時，Reed & de Freitas (2016) 的 NPI 模型需要強監督訓練，也就是以程序的示例執行軌跡為訓練數據。獲取這種形式的訓練數據，其成本往往高於獲取程序輸入-輸出示例。相比之下，弱監督訓練才是充分發揮 NPI 潛力的理想選擇。

為了克服 NPI 的上述局限，本文提出將組合子抽象方法引入 NPI 模型，並為此設計了必要的組件和機制來增強原有的 NPI 架構。新架構被稱為組合神經編程器-解釋器（CNPI）。組合子，即高階函數，是函數式編程中一種重要的抽象技巧，本文借用組合子的概念來表示不同程序共有的一些編程模式。

2 組合子抽象概述

2.1 綜述 NPI 及其局限

本節將概述 Reed & de Freitas (2016) 和 Cai et al. (2017) 論文中的 NPI 架構，分析架構的局限，這也是本文提出組合子抽象的動機。NPI 模型包含三個具有學習能力的組件：一個與任務無關的核心控制器、一個程序存儲器，以及讓 NPI 適用於多種環境的多個特定域編碼器。核心控制器是一個長短期記憶（LSTM）網路（Hochreiter & Schmidhuber, 1997），作為各個程序之間的路由。在每個時間步上，核心控制器可以選擇以特定的參數調用其他程序，也可以終止調用當前程序。當程序返回後，控制權將返給主調程序，即主調程序的 LSTM 隱藏單元和程序嵌入向量彈出程序調用棧，從中斷處繼續執行主調函數。

NPI 的推理過程如下（詳見論文 Reed & de Freitas (2016) 第 3.1 節和演算法 1）。在時間步 t 上，編碼器 f_enc 接收環境觀測量 e_t 和參數 a_t，輸出狀態 s_t。核心 LSTM 網路 f_lstm 接收狀態 s_t、程序嵌入向量 p_t∈ R^P 和上一個隱狀態 h_t-1，從而更新自身的隱狀態 h_t。根據最頂層 LSTM 的隱狀態，多個解碼器可產生如下輸出：返回概率 r_t、下一個程序的鍵嵌入向量 k_t+1，以及下一個程序的參數 a_t+1。通過對比鍵嵌入向量 k_t+1 與鍵存儲器 M_key 中的每一行，可得到下一個程序的 ID。於是，從存儲了 N 個程序的程序存儲器 M_prog 中可以獲取下一個程序的嵌入向量：

以上描述的 NPI 架構有兩個局限。第一，由上式可知，程序存儲器中保存著已學得的全部 N 個程序，在每個時間步上，核心控制器都要從這 N 個程序里選擇一個調用。隨著數量 N 增大到成百上千，讓單個核心控制器正確解釋程序會變得越來越困難。更難的是，核心控制器在學習新程序的同時，還不能忘記已學得的舊程序。第二，不同名稱、不同功能的程序往往有一些共同的潛在編程模式。以 Reed & de Freitas (2016) 和 Cai et al. (2017) 論文中的兩個程序為例（見圖 1）：ADD1 程序執行多位數十進位加法，BSTEP 程序執行冒泡排序中的一次冒泡。這裡採用 Cai et al. (2017) 論文中的遞歸形式。兩個程序的循環模式非常相似，然而核心控制器需要分別學習這兩個程序，無法利用他們共有的模式來提高學習效率。於是，以普適為目標的核心控制器需要學習無窮個程序。由於存在以上兩個局限，我們認為即使可以構造普適的 NPI，挑戰也非常大。

圖 1：傳統 NPI 與引入組合子抽象的 CNPI

2.2 本文的組合子抽象方法

為了克服 NPI 的局限，本文提出在 NPI 架構中引入組合子抽象。函數式編程中，作為有力的抽象手段，組合子是一種特殊高階函數，可以增強編程語言的表達力。本文將組合子概念引入到神經編程中，使之成為提升 NPI 通用性的關鍵角色。

組合子定義為一個「程序模板」，形參作為要填的空，可以是要調用的子程序。用另一個稱為應用子（applier）的程序來包裹組合子，即可表示實際的程序。當執行組合子的時候，應用子調用組合子，將實參傳遞給組合子。組合子的實參可以是一組實際的程序，也可以是包裹結構的程序（即應用子），這樣就能反覆組合，構造出越來越複雜的程序了。與原始 NPI 相似的是，核心控制器對組合子的解釋取決於一個輕量級的特定域編碼器的輸出。這個編碼器我們稱為探測子（detector），也由應用子動態地提供。圖 1 為引入組合子抽象的 NPI 新架構。

在 CNPI 架構中，組合子是唯一需要被核心控制器解釋的程序類型。由於限定了組合子只能調用傳遞給它的參數（程序），在每個時間步上可調用程序的選擇範圍就從不斷增加的 N 個縮減到常數 K 個，K 是組合子可調用參數的最大數量（本文模型中 ≤ 9）。同時，與無限個潛在程序相比，有用的組合子數量有限而且通常很少。本文構造的組合子集合僅包含四個，用於表徵最常見的四種編程模式。我們將證明，一個相當小的核與其他組件協同作用，就足以構造出普適的 CNPI。

3 CNPI 模型

3.1 組合子和組合程序

本文提出用四個組合子來表徵演算法任務中最常見的四種編程模式：順序模式、條件模式、線性遞歸和樹形遞歸（即多重遞歸）。四個組合子的偽代碼見圖 2。

圖 2：組合子集合的偽代碼

圖 3：BSTEP（氣泡排序）寫成組合程序的示例。其中 NOP 是特殊的的元動作（ACT），不進行任何操作。

3.2 CNPI 架構及演算法

表 1：CNPI 與 NPI、RNPI 的定性比較

5 實驗

5.1 監督學習結果

圖 5：可調用參數的數量 K=4 時，對應組合子集合包含 57 個組合子。用三種模型分別學習整個集合，模型 LSTM 單元數與預測精度的關係。

表 3：單個固定核學習新程序/組合子並記憶舊程序/組合子的準確率。用新程序/組合子訓練，RNPI 和 CNPI 取得的最高準確率分別為 100% 和 97.7%。

5.2 增強學習的課程

表 4：用增強學習訓練 CNPI 執行排序任務的課程設計。要學習的程序（包括探測子）顯示為加粗藍色字。為輔助學習排序任務，課程中增加了幾個動作（ACT）：OUT_x 是將指針 x 處的元素寫入 P3 指向的位置，並讓 P3 所指位置向前移動一步；CLEAR_x 是將指針 x 處的元素置為 -1；OUTCLEAR_x 是將指針 x 處的元素輸出，然後置為 -1。這裡的排序任務並非在原位操作，而是將每個回合找到的最大元素寫入 P3 指向的另一個數組中。

5.3 增強學習結果

表 5：採用不同的採樣方法及課程時，增強學習訓練 CNPI 核的成功率。

表 6：增強學習訓練 CNPI、RNPI 模型，完成簡單版任務和最終版任務的成功率。

表 7：採用兩類探測子、有無瞬態條件時，學習組合子 linrec（線性遞歸）的成功率比較。

6 結論

通過在函數式編程中結合組合子抽象，本文提出的 CNPI 首次解決了 NPI 提升通用性和可學習性的問題。分析和實驗結果表明 CNPI 對於所有「可組合子化」的程序都是通用的，並且無論用強監督還是弱監督都可以訓練。研究者認為這個方法足夠通用，除了解決演算法任務之外，還存在潛在的應用。其中一個可能的應用場景是用強化學習訓練智能體以服從指令和進行泛化（例如, Oh et al. (2017), Andreas et al. (2017), Denil et al. (2017)）。自然語言中包含了「高階」詞，例如「然後」、「兩次」等，這些詞在語言表達中很重要，但普通的序列到序列模型（Lake & Baroni, 2017）可能很難理解其意義。通過將這類詞表示成組合子，並將智能體結合類似 CNPI 的組件，就有可能構造出性能更強的智能體，不僅可以根據簡明的指令做出更複雜、更結構化的行為，而且由於抽象程度的提升，泛化性能也會提升。此類探索將在未來的研究中進行。

本文為機器之心編譯，轉載請聯繫本公眾號獲得授權。

------------------------------------------------

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