選自 arXiv

作者：Rasmus Berg Palm、Ulrich Paquet、Ole Winther

機器之心編譯

參與：李詩萌、王淑婷

本文引入循環關系網絡來解決步驟相互依賴的關系推理任務，舉個栗子，數獨任務。以往的傳統深度學習方法雖然也能解決，卻總是會出現一些問題。本文提出的 RNN 模型解決了 96.6% 的最難數獨，而且與其它方法相比結果最佳。

人類智能的核心組成部分是對目標及其相互作用進行抽象推理的能力 [Spelke 等人，1995，Spelke 和 Kinzler，2007]。舉個例子，假設要解數獨問題。數獨盤面中有 81 個格，按 9*9 的方式排列，要用數字 1～9 填滿這些格子，每個數字在每行、每列以及每一個 3*3 的非重疊格中都只能出現一次，有些數字已經給定為 1。要解數獨，就得用方法推理出盤面上的格子以及它們在許多步驟中的相互作用關系。有人試著將數字放進格子中，并觀察它會對其它格子產生怎樣的影響，迭代地解決這一問題。

將這種方式與傳統的深度學習方法（如多層感知器（MLP）或多層卷積神經網絡（CNN））進行對比來解決問題。上述架構將整個數獨盤作為輸入，在一次正向傳遞過程中輸出了完整的解決方案，但在這個過程中它們忽視了目標之間存在的歸納偏置，以及它們是以一致的方式互相作用的。當面對需要推理基本關系的問題時，這些模型會出現問題也就不足為奇了 [Lake 等人，2016，Santoro 等人，2017]。

Santoro 等人的關系網絡 [2017] 是用簡單模塊推理目標及其相互作用的重要第一步，但它的局限性在于只能進行單個關系運算，而在數據集上評估時最多需要三個推理步驟（令人驚訝的是，如文中所示，這一問題可通過單個關系推理步驟解決）。除了關系網絡，在人工智能和機器學習領域還有關于邏輯和推理方面的文獻，我們將在第 5 節中討論。

為了實現在多個步驟中有條理地推理目標及其相互作用的能力，本文引入了一個復合函數，循環關系網絡。它是端到端可微分學習系統中多步關系推理的模塊化組件。它將歸納偏置編碼為：1）存在于這個世界的目標；2）可以通過屬性充分描述；3）屬性可以隨時間的變化而改變；4）目標之間會互相影響；5）在給定屬性的情況下，目標對彼此的影響不變。

從 Santoro 等人 [2017] 的研究中得出的重要見解是將關系推理函數分解成兩個組件或「模塊」：一個感知前端（其任務是識別原始輸入中的目標，并將其表示為向量）和一個關系推理模塊（使用這些表征來推理目標及其相互作用）。這兩個模塊都是用端到端的方法聯合訓練的。用計算機科學中的術語來說，關系推理模塊實現了一個接口：它在有向邊和節點的圖上進行操作，其中節點由實值向量表示，并且是可微分的。本文主要開發該接口的關系推理方面。

我們評估的一些任務也可以通過在符號級別上操作的手工算法高效、完美地解決。例如，可以用約束傳播和搜索 [Norvig，2006] 或舞蹈鏈 [Kuth，2000] 的方法在零點幾秒內解決 9*9 的數獨問題。從各個方面看這些符號算法都很優越，只有一點除外：它們不符合接口，因為它們不可微也不適用于實值向量描述。因此它們不能用于具有深度學習感知前端和端到端學習的組合模型中。

繼 Santoro 等人 [2017] 后，我們用「關系推理」一詞來表示以目標和交互為中心的問題解決方法。盡管「關系推理」與「關系邏輯」或「一階邏輯」這種其他科學分支的術語相似，但這并不意味著直接的并行。

本文認為多步關系推理是深度學習架構中一項極具挑戰的任務。我們開發了循環關系推理模塊，它即這篇文章的主要貢獻。我們在三個不同的數據集上進行多步關系推理，證實了這是一個強大的架構，它在 bAbI 和數獨游戲上都實現了當前最佳的結果。

論文：Recurrent Relational Networks

論文鏈接：https://arxiv.org/pdf/1711.08028.pdf

摘要：本文關注的是學習解決需要一系列相互依賴步驟的關系推理任務，比如回答關于目標之間關系的復雜問題，或者是解決在解決方案中小元素相互約束的問題。我們引入了循環關系網絡，這是一個在目標的圖表征上運行的通用模塊。正如 Santoro 等人 [2017] 所做的關于關系網絡的概括，該網絡可以增強任何能夠進行多步關系推理的神經網絡模型。我們用循環關系網絡在 bAbI 文本問答數據集上實現了當前最佳結果，連續解決了 20/20 的任務。從關系推理的角度看，bAbI 并不是特別具有挑戰性，因此我們引入了 Pretty-CLEVR 數據集，這是一個用于關系推理的新診斷數據集。在 Pretty-CLEVR 的建立過程中，我們可以通過改變問題來控制獲得答案所需的關系推理步驟數量。最后，我們展示了循環關系網絡是如何從監督訓練數據中學會解決數獨問題的，這是一項極具挑戰的任務，需要 64 個以上的關系推理步驟。我們解決了 96.6% 最難的數獨問題，而在所有可比較的方法中該方法實現了當前最佳的結果。

循環關系網絡

我們以解決數獨問題這種大家都很熟悉的事物為例來討論循環關系網絡。有一個簡單的策略，如果在某個數獨格子里填了「7」，那么在同一行、同一列以及對應的 3*3 格子中就可以安全地刪去「7」這個選項。在信息傳遞框架中，這個格子需要向同一行、同一列以及對應 3*3 格子中的其它格子傳遞信息，告訴它們它的值是「7」，不要再接受「7」了。在一個迭代 t 中，這些信息是同時、并行地在所有格子之間發送的。然后每一個格子 i 就要思考所有的輸入信息，并將其內部狀態??更新為??i。更新狀態后每一個格子都要向外發送新的信息，然后重復這個過程。

在圖上傳遞信息：循環關系網絡要學習在圖上傳遞信息。就數獨游戲而言，圖有 i ∈ {1, 2, ..., 81} 個節點，每個節點表示數獨盤中的一個格子。每個節點都有一個輸入特征向量 和與數獨盤中同一行、同一列以及同一 3*3 格子中所有節點相連的邊。圖是關系推理模塊的輸入，向量??一般是感知前端的輸出，例如卷積神經網絡。繼續以數獨游戲為例，每一個 ?都對初始的格子內容（空的或給定數字）以及格子中行和列的位置進行了編碼。

在每個步驟 t 中，每個節點都有隱藏狀態向量 ，將這個向量初始化為特征，使?。在每一步 t 中，每個節點會給它的相鄰節點發送信息。我們通過以下方式定義在第 t 步時從節點 i 發送到節點 j 的信息?：

其中信息函數 f 是多層感知機，它使得網絡能夠了解要發送的信息類型，我們在實驗中使用了具有線性輸出的 MLP。由于節點要考慮所有輸入的信息，我們用以下方式對其進行求和：

式中 N（j）是所有和節點 j 相連的節點。就數獨游戲而言，N（j）包含所有與 j 相同的行、列、3*3 格子的節點。在我們的實驗中，因為在（1）中的信息是線性的，這有點類似于信念傳播中如何對對數幾率求和 [Murphy 等人，1999]。

循環節點更新：最后我們要通過以下方式更新節點隱藏狀態，

式中的節點函數 g 是另一個學習過的神經網絡。對先前節點隱藏狀態??的依賴使得網絡能夠迭代地尋找解決方案，而不是每一步都從頭開始。像這樣在每一步都輸入特征向量?，就能將節點函數的注意力集中于來自其它節點的信息，而不是試圖記住輸入。

監督訓練：上述用于發送信息和更新節點狀態的等式定義了循環關系網絡的核心。為了以有監督的方式訓練一個求解數獨的循環關系網絡，我們在圖中每個節點的數字 1～9 上引入了輸出概率分布。節點 i 在第 t 步的輸出概率??由下式給出：

式中 r 是將節點隱藏狀態映射到輸出概率的 MLP，例如用 softmax 非線性。在給定目標數字 y = {y_1, y_2, ..., y_81} 的情況下，第 t 步的損失是交叉熵項的和，每個節點的交叉熵項如下：，式中?是 o_i 的第 y_i 個組件。等式（1）到（4）在圖 1 中闡釋。

圖 1：在全連接圖上有 3 個節點的循環關系網絡。綠色高亮表示的是節點的隱藏狀態 ?，紅色高亮表示的是輸入 ，藍色高亮表示的是輸出 。虛線表示循環連接。下標表示節點索引，上標表示 t 步。通過兩步展開的同一圖形請參閱補充材料。

收斂性信息的傳遞：本文提出模型的顯著特征是我們在每一步都最小化了輸出和目標分布之間的交叉熵。

測試時我們只考慮了最后一步的輸出概率，但訓練時每一步都有損失是有益的。因為目標數字 y_i?是在步驟上是恒定的，所以它鼓勵網絡學習收斂信息傳遞算法。其次，它有助于解決梯度消失問題。

Variation：如果邊是未知的，可以將圖視為全連接的。在這種情況中，網絡需要學習哪些目標是彼此相互作用的。如果邊有屬性?，等式 1 中的信息函數可以修改為

。如果想要整個圖而不是每個節點的輸出，可以將等式 4 中的輸出修改為單個輸出，即。也可以根據需要相應地修改損失。

實驗

表 1：bAbI 的結果。用 10，000 個訓練樣本在所有 20 個任務上進行聯合訓練。用星號標記的條目是我們自己的實驗，其它結果都來自于各自的論文。

圖 2：2（a）是 Pretty-CLEVR 診斷數據集中的兩個樣本。每個樣本都有 128 個相關問題，這表現出了不同等級的關系推理難度。對于最頂層的樣本，用箭頭表示的問題的解決方案是：「綠色，跳 3 次」，也就是「加號」。2（b）對應的是從 8 個可能的輸出中隨機挑選一個（形狀和顏色取決于輸入）。RRN 經過了四個步驟的訓練，但因為它在每一步都進行了預測，因此我們可以評估每一步的表現。括號中標出了步數。

圖 3：訓練后的網絡如何解決部分數獨問題的示例。清晰起見，僅顯示了完整 9*9 數獨盤的最頂行。

表 2：求解數獨的方法比較。只比較了可微的方法。用星號標記的條目是我們的實驗，其它都來自于各自的論文。

本文為機器之心編譯，轉載請聯系原作者獲得授權。

?------------------------------------------------

加入機器之心（全職記者 / 實習生）：hr@jiqizhixin.com

投稿或尋求報道：content@jiqizhixin.com

廣告 & 商務合作：bd@jiqizhixin.com

總結

以上是生活随笔為你收集整理的NeurIPS 2018 | 如何用循环关系网络机智地解决数独类关系推理任务？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。