[NIPS2018]Library Learning for Neurally-Guided Bayesian Program Induction

• • 1. 摘要
  • 2. 問題定義
  • 3. 方法介紹
  • • 3.1. 分層貝葉斯架構
    • 3.2. Explore階段：尋找程式集合Fx
    • 3.3. Compile階段: 學習識别模型q
    • 3.4. Compress階段: 學習生成模型 (DSL)
  • 4. 實驗結果

作者：Kevin Ellis，Lucas Morales，Mathias Sablé-Meyer，Armando Solar-Lezama，Joshua B. Tenenbaum。（MIT）

1. 摘要

一般的程式歸納方法需要手工定義一個DSL（domain-specific language），用來限制程式的搜尋空間并預定義一些程式的先驗知識。而該文則提出了一種稱之為EC2的方法，可以在訓練用來搜尋程式的神經網絡時，進一步的學習新的函數并添加到DSL中（library of program components），然後在更新後的DSL中重新搜尋程式。

2. 問題定義

該文提出的方法是在訓練用以搜尋程式的神經網絡時，不斷更新并豐富DSL。上面是文章中舉出的可以使用該方法的三個場景。三個例子分别為清單處理List Processing，文本編輯和符号回歸，前兩個輸入為一些輸入輸出對，通過輸入輸出對有監督的學習出一個正确的程式，最後一個為輸入圖像，在提前限制的有理函數中利用神經網絡搜尋程式。

3. 方法介紹

EC2（ECC, Explore/Compress/Compile）。

Explore階段，給定任務（如幾百個例子），按照目前的DSL和神經網絡搜尋符合條件的程式。

Compress階段，通過對上一步得到的程式分析得到一些規則，并将其變為可調用的代碼段，增加到DSL中。

Compile階段，通過新的DSL和代碼訓練神經網絡，提高網絡搜尋的結果。

3.1. 分層貝葉斯架構

分層貝葉斯架構Hierarchical Bayesian Framing。

考慮一個輸入任務的集合X，定義似然模型P[x|p]，其中p是一個程式，該模型可以了解為程式p在任務x的評分（x∈X）。同時從程式p中推理DSL，記為D。D和實值權重矢量θ共同定義(D, θ)為程式的生成模型。此時，任務的目标變成了求給定X下的(D, θ)的最大後驗機率。公式如下：

但是，由于程式p屬于一個無窮集合，是以上式實際不可計算。實際中，可以定義一個有限的程式p集合frontier（Fx），隻在Fx上求解。通過最大化下面的式子來近似得到最大後驗機率。

Explore: 最大化Fx，即，固定(D, θ)，尋找新的程式p加入Fx集合使得上式最大。

Compress:最大化DSL，固定Fx，對上式的 θ 求積分得到D，然後再更新 θ。

搜尋新的程式時，由于程式的搜尋空間太大，采用訓練一個神經識别模型q來搜尋程式p，q(p|x) ≈ P[p|x, D, θ] ∝ P[x|p]P[p|D, θ]。

Compile: 訓練q使得P[x|p]P[p|D, θ]最大。樣本p可以取自Explore階段找到程式和從DSL中采樣得到。

三個步驟之間的互相關系如上圖所示。1）兩個虛線為Explore階段，根據目前的DSL和識别模型q尋找新的程式p。2）得到程式p後進行Compress階段，求解DSL。3）根據程式p和新的DSL采樣可以再次訓練識别模型q。

3.2. Explore階段：尋找程式集合Fx

從DSL中直接通過枚舉的方式尋找程式p，如果p滿足P[x|p] > 0，則加入Fx。具體DSL形式可以用λ演算表達式來表示。定義DSL如下：

(D, θ)：D是λ演算表達式的集合，θ是長度為|D|+1的向量，分别對應D中每個表達式和一個常量的出現機率。這樣定義DSL後，就得到了一個程式的分布，P[p|D, θ]，然後就可以從中枚舉程式了。

3.3. Compile階段: 學習識别模型q

訓練一個識别模型q的目的是分攤（amortize）搜尋程式時的代價。在先驗(D, θ)下，對每個任務預測一個使得P[x|p]機率最大的程式p。具體網絡可以參考DeepCoder。

3.4. Compress階段: 學習生成模型 (DSL)

通過加入新的λ表達式産生新的DSL，直到下式不再增加。新的λ表達式來自Fx中的程式的片段。

總的算法流程如下圖：

4. 實驗結果

略

論文連結：https://papers.nips.cc/paper/8006-learning-libraries-of-subroutines-for-neurallyguided-bayesian-program-induction