科技

AI「王道」邏輯程式設計的復興?清華提出神經邏輯機,已入選ICLR

深度神經網路一直被人詬病的地方在於,缺少邏輯推理能力,它只是一種函式擬合方法。在這篇論文中,清華、Google和位元組跳動的研究者提出了一種名為神經邏輯機的模型,它可同時用於歸納學習與邏輯推理。它結合神經網路與邏輯程式設計(邏輯程式設計),讓神經網路也能用於邏輯推理。

這篇論文被接受為 ICLR 2019 的 Poster,它的評分為 6、5、7。正如評審該論文的領域主席所言,這篇論文提出了一個非常有意思的正向鏈模型,它利用了元層級的擴充套件,並以一種非常簡潔的方式降低了謂項引數,從而降低了複雜度。

論文連結:https://arxiv.org/abs/1904.11694演示地址:https://sites.google.com/view/neural-logic-machines在該論文的展示頁中,作者們也介紹了各種任務的效果,包括排序、最短路徑搜尋和積木世界等。其中所有智慧體都通過

強化學習

訓練,智慧體會根據當前狀態迭代地選擇動作,直到一個 Episode 結束。

下面我們簡要展示神經邏輯機(NLM)在最短路徑搜尋和積木世界上的表現。

1. 最短路徑搜尋

該任務會隨機生成一個無向圖,智慧體需要從開始節點一步步走到目標結點。例如如果我們將初始結點定義為 s、目標結點定義為 t,那麼 s 到 t 之間的距離為 d,d 是從區間 [1, 5] 中均勻取樣的。

結果是,智慧體能搜尋到正確的積木移動順序,並將初始狀態轉化為目標狀態。

什麼是「學習」解決不了的

機器學習已經成功應用在語音識別、遊戲等諸多領域,但聯結主義模型的系統性(systematicity)問題仍然存在爭議。

邏輯系統可以自然地處理語言理解和推理中的符號規則。歸納邏輯程式設計(ILP)從例子中學習邏輯規則。粗略地說,給定一組正負樣本,ILP 系統可以學習一組規則(帶有不確定性),其中包含所有正樣本,而不含負樣本。將符號和概率結合起來,可以很自然地解決許多高階認知能力(如系統性)帶來的問題。然而,由於組合規則(compositional rule)的搜尋空間巨大,ILP 很難擴充套件到小型規則集合之外。

為了更加具體地討論,該研究以經典的積木世界(blocks world)問題為例。如圖 1 所示,給定一堆積木,我們可以移動一塊積木 x 並將其放在另一塊積木 y 的上方或地上,前提是 x 可以移動並且 y 上可以放積木。我們將這種操作稱之為 Move(x, y)。如果一塊積木上沒有其他的積木,那麼這塊積木就是可以移動的,而且上面可以放其他積木。地上一直可以放積木,也就是說我們可以把所有積木都放在地上。給定積木世界的初始狀態之後,我們的目標就是通過一系列移動操作將其轉換為目標狀態。

圖 1:(左)積木世界圖示。給出原始和目標狀態,要求智慧體通過移動積木將原始狀態轉換為目標狀態。(右)本文用到的積木世界術語。

雖然積木世界問題乍看之下非常簡單,但構建學習系統來自動完成此任務存在四大挑戰:

學習系統應該恢復一套已經解除的規則(即那些統一應用於物件而不是與特定物件繫結的規則),並泛化到比訓練中積木數量更多的積木世界中。為了對此有一個直觀的認識,此處向不熟悉積木世界的讀者推薦陣列排序任務(如 Vinyals et al., 2015),在這個任務中,迴圈神經網路無法泛化至比訓練陣列稍長的陣列。學習系統應該處理高階關係資料和量詞(quantifier),但這超出了常見圖結構神經網路的範圍。例如,為了應用關係 r 的傳遞律(即 r(a, c) ← ∃b r(a, b) ∧ r(b, c)),我們需要同時檢查三個物件(a, b, c)。學習系統應該擴充套件規則的複雜性。現有的邏輯驅動方法(如傳統的 ILP 方法)計算複雜度為指數級,即需要學習的邏輯規則數量巨大。學習系統應該基於最小的學習先驗集恢復規則。相比之下,傳統的 ILP 方法通常需要手工編碼和針對特定任務的規則模板,來限制搜尋空間大小。為什麼結合邏輯程式設計的學習方法能 Work

在這篇論文中,研究者提出了一種名為神經邏輯機(Neural Logic Machines,NLM)的演算法,它可以解決上面學習方法解決不了的問題。簡而言之,NLM 提供了一種神經符號(neural-symbolic)架構,它以一階邏輯實現 Horn clauses (Horn, 1951)。NLM 的關鍵思想即

神經網路

可以高效地逼近邏輯運算,例如 AND 和 OR 等運算邏輯,且神經模組之間的連線可以實現邏輯量詞。

論文:NEURAL LOGIC MACHINES

摘要:該研究提出了一種神經-符號架構——神經邏輯機(NLM),該架構可用於歸納學習和邏輯推理。NLM 利用神經網路(作為函式逼近器)和邏輯程式設計(作為符號處理器),處理具備不同屬性、關係、邏輯聯結詞(logic connective)和量詞的物件。在小規模任務(如對短陣列排序)上進行訓練後,NLM 可以恢復一些已經被取消的規則,並泛化至大規模任務中(比如對較長陣列進行排序)。實驗證明,NLM 可在大量任務中獲取完美的泛化效果,包括對家族樹和通用圖進行關係推理的任務、決策任務(包括陣列排序、尋找最短路徑、積木世界)等。大多數任務對於神經網路或歸納邏輯程式設計自身是很難完成的。

神經邏輯機(NLM)

NLM 是邏輯機在封閉世界假定下的神經網路實現。給出一組基於 object(前提)的謂項,NLM 序列地應用一階規則(first-order rule)得出結論,如某個 object 的屬性。舉例來說,在積木世界任務中,基於 object u 的前提 IsGround(u) 和 Clear(u),NLM 可以推斷出 u 是否可移動。

NLM 內部使用張量表示邏輯謂項(logic predicates)。基於這種張量表徵,規則可以通過神經運算元實現,且規則能應用於前提張量並生成歸結張量。這樣的神經運算元是概率性的,並能通過各種命令(即使用不同元數在謂項上進行操作)處理關係型資料。

下圖 2 展示了 NLM 整體的多層、多組架構。NLM 的層級深度為 D(水平向),每一層有 B+1 個計算單元(垂直向)。這些單元會在謂項的張量表徵上進行操作,且謂項的元數(arity)在 [0, B] 之間。NLM 將謂項(前提)的張量作為輸入,並執行一層層的計算,且把輸出張量作為歸結。

圖 2:神經邏輯機(NLM)的整體架構。在前向傳播中,NLM 將 object 屬性和關係作為輸入,並執行序列的邏輯演繹,最後輸出歸結屬性或 object 間的關係。

對於運算的具體內容,如下圖 3 所示,如果層級 i 有的組為 2(二元謂項),那麼模組從組內計算開始。它首先會收集垂直連續組(一元、二元和三元)的輸出,該輸出是從前一層 i-1 得到的,它們的張量形狀見下圖 3。

圖 3:NLM 中的計算模組,以第 i 層的二元謂項為例。其中 C 的上下標分別表示組與層級,C 表示不同組與層級下的輸出謂項數。[·] 表示張量形狀。

實驗

研究者在大量任務上對 NLM 進行了實驗,包括關係推理、決策等。此外,研究者還證明使用小規模例項訓練的 NLM 可以泛化到大規模例項上。在實驗中,Softmax-Cross-Entropy 損失用於監督學習任務,REINFORCE (Williams, 1992) 用於強化學習任務。

研究者使用 Memory Networks (MemNN) (Sukhbaatar et al., 2015) 和 Differentiable Inductive Logic Programming (∂ILP) (Evans & Grefenstette, 2018) 分別作為聯結主義和符號主義的基線模型。

家族樹推理和圖推理

家族樹是歸納邏輯程式設計的基準,在該任務中,向機器提供包含 m 個成員的家族樹。該家族樹由以下關係(謂項)表示:IsSon、IsDaughter、IsFather 和 IsMother。該任務的目標是推斷出家族成員的其他屬性或他們之間的關係。研究者還進一步將家族樹擴充套件至通用圖。

實驗結果見表 1。

表 1:在家族樹和圖推理任務中,MemNN、∂ILP 和 NLM 的對比,其中 m 表示家族樹或圖的規模。∂ILP 和 NLM 的效能均優於神經基線模型,在測試集上達到了 100% 的準確率。注意:N/A 標記表示 ∂ILP 無法在 2-OutDegree 中擴充套件。

積木世界、排序和尋找最短路徑

研究者在經典的積木世界問題(見圖 1)上測試了 NLM 的決策效能,他們將 NLM 模型擴充套件至強化學習的

馬爾科夫決策

過程(MDP)中。此外,研究者還在演算法任務上測試了 NLM 的能力,如排序演算法和路徑演算法。

NLM 在積木世界、排序和尋找最短路徑任務上的效能如下所示:

表 2:在積木世界、整數排序和尋找最短路徑任務中,MemNN 和 NLM 的效能對比。

其中 m 表示積木世界環境中的積木數、排序環境中的陣列規模,或者尋找最短路徑環境中的圖數量。兩個模型都在 m ≤ 12 的情況下訓練,在 m = 10 或 50 的情況下測試。效能評估指標有兩個,由/分隔,二者分別是:測試中完成任務的概率、完成任務時智慧體使用的平均步數。MemNN 無法在最大 m × 4 步數下完成積木世界任務。

Reference:科技日報

看更多!請加入我們的粉絲團

轉載請附文章網址

不可錯過的話題