NeurIPS 2018｜如何用循環關係網路解決數獨類關係推理任務？

選自 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：求解數獨的方法比較。只比較了可微的方法。用星號標記的條目是我們的實驗，其它都來自於各自的論文。

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