DeepMind新研究：可微歸納邏輯編程，融匯神經網路與邏輯編程之長（下）
來源：DeepMind
編譯：weakish
隨著深度學習的興起，神經網路的尺寸也伴隨著表達力的提升而提升。隨著神經網路複雜度的增加，過擬合問題也變得越來越普遍。雖然正則化可以緩解過擬合問題，但解決過擬合問題最常用的方法還是使用大量訓練數據，希望足夠多的訓練數據的分布可以逼近測試數據的分布。然而，大量數據並不總是那麼容易得到。相比神經網路，歸納邏輯編程可以說是極度數據高效了。然而，歸納邏輯編程對雜訊和標註錯誤的數據極為敏感，也無法應用於非符號領域的問題，因此，歸納邏輯編程適用的領域比神經網路要狹窄得多。DeepMind的研究科學家Richard Evans和Edward Grefenstette提出了可微歸納邏輯編程?ILP，結合了神經網路和歸納邏輯編程的優勢。
在上篇中，我們介紹了?ILP如何將歸納推理問題轉化為可滿足性問題，以及?ILP在標準ILP任務上的表現。在這篇文章中，我們將介紹?ILP的可微架構，以及?ILP對錯誤標註數據的魯棒性和如何應用?ILP到非符號數據。除此以外，我們還將討論?ILP與相關工作的異同，以及?ILP的缺陷及改進空間。
模型架構
上篇提到研究人員所採取的模型採用的是自頂向下方法，也就是根據語言生成程序，然後在正例和反例上進行測試。因此，給定一個ILP問題(L, B, P, N)，一個程序模板Π，模型將基於L、B、Π生成一組子句，然後測試正例和反例。
那麼，從機器學習的視角而言，這個模型很像是一個二元分類器，學習基礎原子a的真值（為真時屬於正例，為假時屬於反例）。
然後，為了便於使用隨機梯度下降之類的方法進行訓練，研究人員將二元分類器的輸出從離散的布爾值改成了[0, 1]實數區間。同理，研究人員將上篇中提到的表明程序實際使用的子句的離散的布爾值變數改成了連續的權重子句的概率分布（不妨用W表示）。相應地，模型學習的也是基礎原子a的條件概率（不妨用λ表示）。
由此，研究人員構建了一個可微的模型：
相應地，正例和反例可以表示為標註過的原子數據集：
損失函數為分類問題常用的交叉熵：
前面我們提到了模型要學習條件概率：
那麼，這個概率具體是如何計算的呢？
研究人員使用了4個輔助函數進行計算：
用圖形表示更容易理解：
上圖中，綠框中的函數為可微函數，實線表示可微路徑，虛線表示不可微路徑。我們看到，雖然和為不可微函數，但是從子句權重到最終的損失函數，模型是處處可微的。也就是說，訓練模型以自動得到權重的過程，都是可微的。
以上我們概覽了整個模型的架構，下面我們詳細解釋下權重是如何表示的。
規則權重
W為由矩陣組成的權重集合，每個矩陣對應於一個內涵謂詞p ∈ Pi，即(cl(τp1), cl(τp2,k))。不同的矩陣的大小通常不一樣，因為不同的規則模板生成的子句集合的大小不同。
Wp[j,k]表示系統有多麼相信子句對(Cp1,j, Cp2,k)是定義內涵謂詞p的正確方式。
研究人員使用softmax將權重矩陣Wp[j,k]轉換為概率分布：
相應地，Wp*[j,k]表示(Cp1,j, Cp2,k)為定義內涵謂詞p的正確方式的概率。
正向鏈
?ILP的核心是給定子句c，可以自動生成其正向鏈函數Fc.
下面我們結合一個例子，解釋如何生成（計算）這個正向鏈函數Fc.
給定P = ，C = ，將C中的元素代入P，通過排列組合，我們可以得到對應的基礎原子集合G：
假定子句c為：
我們可以定義一個集合Xc=nk=1，表示滿足子句c的所有基礎原子對的集合。
比如，k=9時，xk為(1,5)和(2,7)，換言之：
在我們的例子中，X為：
最終我們將通過基礎原子生成子句，因此再將X分成X1和X2，分別對應基礎原子對中的第一個原子和第二個原子。
然後，將其拼裝起來：
Y1= gather2(a, X1)
將上式中的X1替換為X2，可以得到Y2的定義。
其中，gather2的定義為：
gather2(x,y)[i,j] = x[y[i,j]]
然後，模糊合取（fuzzy conjunction）Y1和Y2：
Z = Y1⊙ Y2
Fc(a)選取Z中模糊真值的最大值，即Fc(a) = a",其中a"[k] = max(Z[k,:])
回到先前的例子，下表顯示了Fc(a)的值：
上面的模糊合取，研究人員使用了像素級乘積（element-wise product）。事實上，有很多表示模糊合取的方式。為了保證高度的概括性，模糊合取運算需要滿足t-norm：
滿足t-norm的運算有：
研究人員選取乘積 t-norm的原因是，當損失函數反向傳播至子句權重時，梯度均勻地在Y1和Y2間流動。而使用Godel t-norm時，若Y1> Y2，沒有梯度信息傳遞給Y1。類似地，使用Lukasiewic t-norm時，若Y1+ Y2< 1，Y1和Y2均收不到梯度信息。
推理
將前向鏈函數分別應用於子句集合Cp1,j和Cp2,k，並取元素級最大值（element-wise max）：
Gpj,k(a) = x
其中，
x[i] = max(Fp1,j(a)[i],Fp2,k(a)[i])
然後我們可以定義t時步推斷後的結果為：
ctp,j,k= Gpj,k(at)
t=0時的初始值a為背景公理：
ctp,j,k的加權平均（基於softmax）為：
由此，可以定義兩個時步間的關係，即基於當前推斷計算下一步推斷：
其中，famalgamate的定義，研究人員首先嘗試直接使用最大值函數：
famalgamate(x,y) = max(x,y)
但研究人員發現，這一定義在訓練時會影響梯度流程，因此研究人員最後使用了概率和（probabilistic sum）：
內存佔用
?ILP屬於內存密集模型。
atp,j,k和ctp,j,k佔用了大量的內存。它們共需存儲如下數目的浮點數：
中間向量Y1、Y2和Z的計算也需要大量內存：
之所以佔用這麼多內存，主要原因是模型為每對規則模板分配了權重矩陣(cl(τp1), cl(τp2,k))。看起來，這麼做引入了不必要的複雜性，完全可以為單獨的規則模板分配權重，而不用存儲這麼多的規則模板組合對應的權重。這樣，模型大大簡化了，內存佔用也大大下降了。
事實上，研究人員起初就是這麼做的。為每個模板生成的字句cl(τ)分配了一個權重矩陣。相應地：
然而，研究人員發現，在較困難的任務中，這一簡化模型無法擺脫局部極小值。
簡化模型的問題在於，如果有兩個規則模板定義了相同的內涵謂詞，組合這兩條規則時，會損失信息。這會影響系統學習涉及多子句的程序。
實現細節
框架
兩位研究人員均來自Google DeepMind，順理成章地使用TensorFlow實現了模型。
超參數
研究人員首先使用網格搜索查找一些「合理的」超參數。「合理」的含義是，可以基於至少5%的隨機初始化的權重解決10個特定的問題。研究人員嘗試了一些優化演算法：隨機梯度下降、Adam、AdaDelta、RMSProp，也嘗試了不同的學習率。權重基於均值為0、標準差在0到2之間（均值為固定值，標準差為超參數）的正態分布隨機初始化。每個超參數配置，研究人員在10個特定問題上測試了20次，每次使用不同的隨機數種子。
研究人員發現RMSProp和Adam都能給出合理的結果。當學習率處於0.5到0.01之間時，RMSProp都能成功。
最終，研究人員選定了如下超參數配置：RMSProp，學習率0.5，初始權重取樣自N(0, 1)的正態分布。
試驗方法
基於上述超參數，研究人員訓練了6000步。在訓練中，使用了多個(B, P, N)三元組。在訓練的每一步中，模型首先從其中一個三元組取樣，接著從P ∪ N中取樣一個mini-batch。提供不同的三元組，幫助系統正確地正確地進行概括。
注意，取樣mini-batch時，並沒有使用整個正例、反例集合，而是在每一步隨機選取一個子集，從子集中取樣mini-batch。這給過程增加了隨機性，有助於避免陷入局部極小值。
消融測試
研究人員在三類任務上試驗了?ILP：
其中，標註ILP問題上的測試結果，我們已經在上篇介紹過了。
此外，為了驗證?ILP的有效性，研究人員還進行了一系列消融測試：
錯誤標註問題
研究人員在訓練數據（正例、反例）中摻雜了錯誤標註的信息，以考驗?ILP對抗雜訊的能力。
p為錯誤標註的信息比例
從上表我們可以看到，在有10%的錯誤標註信息的情況下，?ILP仍然為6個任務中的5個找到了正確解答。在一些任務中，即使錯誤標註率高達20%或30%，?ILP仍能找到正確解答。
從上表我們還可以看到，隨著錯誤標註比例的升高，?ILP的表現平穩地下降。這和傳統的ILP系統大不相同。在傳統的ILP系統中，單個錯誤標註的訓練樣本就足以讓測試誤差劇烈升高。從下圖能更清楚地看到這一點。
下圖顯示了隨著錯誤標註比例的升高，規則的熵值變化的情況。softmax後的規則權重，表示子句的概率分布。該概率分布的熵值衡量了所學規則的模糊程度。注意，在某些情形下，錯誤標註比例升高的一定程度後，熵值反而下降了。這是因為，有時候，當數據全部都錯誤標註的時候，相比有一半數據錯誤標註的情況，反而更容易找到清晰的規則。例如，假設我們學習自然數上的even（偶數）謂詞，然後將所有正例和反例對調，那我們將學習到odd（奇數）謂詞的規則，這條錯誤的規則的熵值為零。
處理模糊數據
在上篇中，我們介紹了一個自然數上even（偶數）/odd（奇數）謂詞的例子。現在，我們討論一個類似的例子，只不過接受的輸入不再是符號（數字），而是像素圖像（MNIST數據集中的圖像）。
和上篇的例子一樣，背景知識仍然是基本的算術（只不過為了簡化這個例子，這裡只考慮0-5的情形）：
這一任務的語言模板為：
我們看到，這個語言模板和原本的語言模版類似，不同之處主要為：
?ILP找到的一個解答為：
其中，第一條規則的意思是「當前圖像表示數值X，且X滿足pred1時，target謂詞為真」。
當然，為了處理像素圖像，需要對?ILP進行一些改造。研究人員在?ILP的架構中加入了一個在MNIST上預訓練過的卷積神經網路。像素圖像傳入預訓練過的卷積神經網路，通過softmax將卷積神經網路的輸出轉化為原子的概率分布。例如，假設圖像表示數字「2」，最終得到的概率分布可能是：
加入卷積神經網路後，整個網路架構如下圖所示：
上面的網路架構仍有改進的空間：
相關研究
相比prolog的模式聲明（mode declaration），和metagol的元規則（meta rules），?ILP的規則目標的限制要少得多。
為了克服傳統ILP的缺陷，Garcez等在2015年嘗試基於神經網路框架實現ILP系統，但是這一工作只在有限的概念驗證性的例子上起效，未能成功應用於實際問題。
深度學習社區也嘗試將ILP生成的符號程序表示改為隱式的基於網路權重分布的圖靈機之類的底層計算模型。有不少工作基於這一思路，經此改造的ILP能夠應對雜訊和模糊數據。然而，和傳統ILP不同，由於生成的計算模型過於底層，因此難以查探，不具可讀性，而且概括性也很差，當測試數據包含很多訓練數據中未見的新數據時，模型的表現劇烈下降。例如，假設訓練數據長度為10，測試數據長度為20，這樣的模型可能表現不錯。但如果測試數據長度為100，模型的表現就急劇下降。
當然，也有一些工作採用了和?ILP相近的思路。
Holldoble等在1999年證明，對任何特定類型的邏輯程序，存在一個循環神經網路，能夠以任意所需精度逼近原邏輯程序。然而，這一工作僅僅是理論上的證明，並沒有給出為具體程序構建循環神經網路的方法。（「Approximating the Semantics of Logic Programs by Recurrent Neural Networks」）
基於以上工作，Bader等在1999年給出了構造方法。（「Connectionist Model Generation: A First-Order Approach」）
該方法和?ILP的不同點為：
Serafini和Garcez在2016年提出了「實邏輯」，將一階邏輯中的布爾值替換為[0, 1]之間的實數值。這一做法與?ILP類似。不過，如上篇所屬，?ILP能生成一階邏輯無法表達的問題的解答。當然，「實邏輯」不像?ILP一樣限定了確定性Datalog子句。（「Logic Tensor Networks: Deep Learning and Logical Reasoning from Data and Knowledge」）
Bader、Garcez、Hitzler在2005年使用fibred神經網路表示邏輯程序。fibred神經網路可以表示遞歸程序，甚至互遞歸程序。然而，這一系統無法表示自由變數。（「Computing First-Order Logic Programs by Fibring Artificial Neural Networks」）
Kersting等在2006年改進了隱馬爾科夫模型（HMM），提出了邏輯隱馬爾科夫模型（LOHMM），該模型可以編碼一階表示。和?ILP類似，LOHMM基於條件概率，可以應對雜訊問題。和?ILP不同，LOHMM基於原子序列進行學習，LOHMM的規則體只包含一個原子。（「Logical Hidden Markov Models」）
De Raedt和Kersting在2008年提出了一個非常概括的ILP形式化表示，基於覆蓋（cover）關係（?ILP的蘊涵關係屬於覆蓋關係中的一種）。不過，?ILP可以學習遞歸子句，而這一系統無法學習遞歸子句。（「Probabilistic Inductive Logic Programming」）
Guillame-Bert、Broda、Garcez在2010年發表的論文「First-order Logic Learning in Artificial Neural Networks」使用了和?ILP在很多方面相似的方法：同樣限定確定性子句，使用神經網路架構實現正向鏈。和?ILP不同，他們的方法沒有Datalog限制（可以使用函數符號），然而，只能學習單個子句，也不支持遞歸子句。
Fran ?ca、Zaverucha、Garcez在2014年提出的CILP++系統沒有?ILP的內存佔用問題，但無法學習遞歸子句。總體而言，CILP++的設計方向與?ILP不同，CILP++致力於學習更多數據，而?ILP致力於學習更複雜的程序。（「Fast Relational Learning Using Bottom Clause Propositionalization with Artificial Neural Networks」）
Rockt ?aschel和Riede在2016年提出了基於反向鏈的可微神經網路架構（?ILP基於正向鏈）。另外，該系統的規則模板比?ILP的限制更多。和?ILP類似，該系統同樣限定了Datalog子句。（「Learning Knowledge Base Inference with Neural Theorem Provers」）
Rockt ?aschel和Riede在2016年提出了基於反向鏈的可微神經網路架構（?ILP基於正向鏈）。另外，該系統的規則模板比?ILP的限制更多。和?ILP類似，該系統同樣限定了Datalog子句。（「Learning Knowledge Base Inference with Neural Theorem Provers」）
Yang等在2016年提出了正向鏈的可微實現，和?ILP不同，該實現學習單獨子句，也不支持遞歸子句。（「A Differentiable Approach to Inductive Logic Programming」）
Eisner等在2004年提出了用於自然語言處理系統的Dyna語言，一個聲明式一階語言。和?ILP類似，Dyna基於正向鏈推理計算概率。（「Dyna: A Declarative Language for Implementing Dynamic Programs」）
缺陷和改進空間
如前所述，?ILP的缺陷主要是內存密集。這限制了?ILP應用於大量數據，也難以應對需要三元以上謂詞才能求解的問題。
目前?ILP需要規則模板才能生成程序。研究人員嘗試過使用暴力搜索法避免手工構造規則模板，然而，這牽涉大量運算。研究人員計劃在以後使用更巧妙、更節省算力的解決方案。
另外，「處理模糊數據」一節已經提過，應用於模糊數據的?ILP，可以改進的方面有：卷積神經網路與整個系統一起訓練，根據手頭的問題決定模糊數據的學習程度。
※女神搭配指南！秋冬新款V領毛衣裙針織衫
※如果可以選爸爸，那我一定選陳小春
TAG:全球大搜羅 |