從Bengio演講發散開來：探討邏輯推理與機器學習

機器之心分析師網絡

作者：仵冀穎

編輯：Joni

Bengio 認為，未來的深度神經網絡應當能夠實現 System2（邏輯分析系統），實現的是有意識的、有邏輯的、有規劃的、可推理以及可以語言表達的系統。本文所討論的 Logical Reasoning（邏輯推理）擬實現的就是 System2 中重點關注的有邏輯的（Logical）和可推理的（Reasoning）特點。

近年來，深度神經網絡的應用獲得了巨大的成功，也推動了人工智能的飛速發展。然而，深度神經網絡仍存在一些局限性。一般來說，深度神經網絡如何進行學習、使用何種算法實現的智能、基於哪些理論分析得出的相關結論並不會在網絡架構中有任何的顯式或符號表示。也就是說，深度神經網絡學習的算法隱式地存儲在成千上萬甚至是數百萬的權重中，這些通常是人類智能體無法破譯或驗證的。

Bengio 在 AAAI 2020 的演講報告中提出，人的認知系統包含兩個子系統：System1（直覺系統），實現的是快速、無意識、非語言的認知，這也是現有的深度神經網絡所實現的。他認為，未來的深度神經網絡應當能夠實現 System2（邏輯分析系統），實現的是有意識的、有邏輯的、有規劃的、可推理以及可以語言表達的系統。我們這篇文章中所討論的 Logical Reasoning（邏輯推理）擬實現的就是 System2 中重點關注的有邏輯的（Logical）和可推理的（Reasoning）特點。

本圖選自 Bengio 在 AAAI 2020 的演講報告

邏輯推理是一個非常寬泛的概念。實際上，我們所熟悉的字符識別、語音識別、圖像識別也可以看做是一種邏輯推理，這不過，這些邏輯推理是低層次的，已經能夠使用傳統的深度神經網絡所解決。我們在這篇文章中所討論的邏輯推理是更高層次的推理過程，即，即使是人來完成這個邏輯推理任務也是要進行一下思考的。

1. 什麼是邏輯？

1.1 邏輯的概念

首先，我們來回顧一下什麼是邏輯以及什麼是 AI/ML 中的邏輯。所謂邏輯，指的是符號化的、基於知識的、推理和其他類似的人工智能方法。基於邏輯的 AI 系統可以被認為是高級編程系統，可以很容易地以緊湊（compact）和可用的（usable）方式編碼人類知識。

最簡單的邏輯系統是命題邏輯（有時稱為零階邏輯）。在命題邏輯中，使用一些被稱為句子或公式的對象來編碼信息。這些對象代表着對世界的一些陳述。通常，可以使用一些基本語句作為這樣的對象。例如，使用「P，Q，R，S…」來表示基本語句，P 可能代表「正在下雨」，是一個原子（Atom）。

可以繼續將原子與邏輯連接詞如「and，or，if then」等組合形成更多的句子，稱為複合公式（Compound Formula）。

複合公式提供了一種有效的信息表示方法。那麼，我們如何利用這些複合公式從已有的信息推斷得到新的信息呢？一般可以通過推理（Reasoning）或推論（Inference）來做到這一點。命題邏輯配有一套稱為推理方法的方案。推理方法可以被認為是一個小程序，它以一組句子作為輸入，並輸出一個或多個句子。推論方法也可以被認為是一個小程序，它也以一組句子作為輸入，並輸出一個或多個句子。下圖展示了一種非常直接的推論方法，它接受表示「Q 和 R」的公式，並將公式 R 作為輸出。例如，如果輸入為「It is sunny, and It is warm」，則輸出將為「It is sunny」。

所有的邏輯都配備了一套與上述過程類似的推論方法。邏輯的這些原始內置方法的作用類似於編程語言中的標準庫。有了這些方法，就可以將它們組合起來以得到更複雜的方法。

從教學的角度來看，從命題邏輯出發進行介紹是一個很好的起點。但是，對於實際中具有大量對象的領域建模來說，使用命題邏輯是很難處理的。例如，假設我們要寫下數獨遊戲應該滿足的約束條件。對於每個數 k，每行 i 和列 j 都對應一個原子 A_ijk，它代表「行 i 和列 k 包含數字 k」。這樣，我們就可以在命題邏輯中快速寫出數獨的約束條件。例如，下圖中的句子說明數字 5 應該出現在第一行中。

同樣，我們也可以寫下其他數字的其他約束條件。在我們的約束條件下，總共有 9^3=729 個原子。每一個原子可以是真或假，即表徵總共 2 種可能的狀態（遠大於宇宙中物理原子的數量）。

一階邏輯通過引入原子來改進命題邏輯，這些原子可以接受域中對象的參數。在一階邏輯中將有一個原子來接受這些變量作為參數，而不是用一個原子 A_ijk 來表示 i、j 和 k 的每個組合。例如，A(1,3,5)表示第 1 行和第 3 列中有一個 5。下圖表示第 1 行中有一列的數字是 5。

一階邏輯是許多現代邏輯系統在研究和工業中應用的基礎。許多其他邏輯系統建立並擴展了一階邏輯（例如，二階邏輯、三階邏輯、高階邏輯和模態邏輯）。每一種邏輯都增加了一個新的維度或特性，以便更容易對世界的某些方面進行建模。例如，被稱為時態邏輯的邏輯被用來對時間和變化進行建模。

1.2 AI/ML 中的邏輯

1.2.1 科學中的自動發現

邏輯學最成功的應用之一是在科學領域中表示結構化的科學知識。2007 年，威爾士和英格蘭的一個小組創建了一個名為 Adam（自動發現和分析機器）的系統 [1]。Adam 可以自動形成科學假設，進行實驗來檢驗假設並記錄實驗結果。這是第一個自動系統，用來發現各類的科學信息。Adam 成功地應用於確定酵母中的一些基因。在這個系統中，假設、實驗結果和結論都以邏輯的形式表達出來。

1.2.2 歸納程序設計

歸納程序設計的目標是學習給定一組輸入和輸出示例的計算機程序。歸納程序設計處理的是可以從這些例子中學習的生成系統。這種系統通常是用邏輯來表述的。最先進的歸納程序設計系統可以從幾個例子中學習複雜的遞歸程序。目前，歸納程序設計方法已經被用來學習數據清理和轉換程序任務[2]。

1.2.3 數學推理自動化

上面的數獨例子說明了一階邏輯比命題邏輯更具表現力。不過，我們能用它來模擬的東西有限制嗎？實際上，單是一階邏輯就相當強大，它強大到可以模擬幾乎所有的古典數學。在標準數學的概念下工作，使用一階邏輯可以陳述你想要證明的任何目標（一個猜想），並能讓機器自動檢查你的工作（數學證明）。這種方法就是直接使用數學的推理自動化。

1.2.4 計算機系統（包括機器學習系統）的驗證

在數學之外，以一階邏輯和類似系統為基礎的邏輯被用於驗證計算機系統。這種選擇被稱為正式驗證（Formal Verification）。在正式的驗證中，有一個計算機系統 S 和一個屬性 P，用戶必須用一種相對嚴格的方式來驗證這個屬性是有效的。例如，用於驗證硬件和軟件系統的工業強度系統 ACL2 (http://www.cs.utexas.edu/users/moore/acl2/)。

1.2.5 類似邏輯系統與機器學習模型

隨着越來越多的應用程序和領域使用機器學習模型，仍有一些場景需要使用類似邏輯系統和機器學習模型。例如，許多欺詐檢測系統使用一個或多個機器學習模型以及大量手工編制的規則，而這些規則是非常必要的。在欺詐檢測領域，這些規則可能會捕獲新的和不斷發展的欺詐模式，而針對這些模式可能並沒有足夠的數據來訓練得到新的模型[3]。

最近的一些研究着眼於將邏輯與深度學習系統進行結合，這也正是我們這篇文章所考慮的問題。我們將在下面的內容中選擇三篇關注於邏輯推理與深度神經網絡相結合的文章進行深入分析[5][6][7]。

2. 邏輯推理與深度學習（Logic Reasoning & DL）

2.1 Bridging Machine Learning and Logical Reasoning by Abductive Learning [5]

本文是南大周志華教授組發表在 NeurIPS 2019 中的一篇研究成果。感知（Perception）和推理（Reasoning）是兩種具有代表性的智能能力，它們在人類解決問題的過程中是無縫集成的。然而在人工智能領域，這兩種能力通常是分別通過機器學習和邏輯編程來實現的，因此，這兩類技術在人工智能的歷史上是分開發展的。本文提出的誘因性學習（Abductive Learning）旨在將兩類人工智能方法有機地統一起來，即機器學習模型學習從數據中感知原始邏輯事實，而邏輯推理方法則是引入符號領域知識並糾正錯誤感知的事實，以改進機器學習模型。此外，作者提出了一種新的方法來聯合優化機器學習模型和邏輯推理模型。作者證明，通過使用誘因性學習，機器可以從簡單的手寫方程圖像中同時學習識別數字和解決未知的數學運算。此外，所學習到的模型可以推廣到更長的方程組並適應不同的任務，這已經超出了現有的先進深度學習模型的能力。

2.1.1 誘因性學習

為了更自然地利用學習和推理，了解感知和推理在單個系統中如何相互影響是至關重要的，本文所引入的誘因性學習則是一種有效的聯合應用和分析的方法。誘因性學習是指根據背景知識有選擇地推斷出對觀察結果作出最佳解釋的特定事實和假設的過程，其中「觀察」主要是感官信息，「知識」通常是象徵性和結構性的。

人類使用誘因問題解決方法來解決問題的一個直觀例子是瑪雅象形文字的破譯，它反映了人類兩個顯著的智能能力：1）從象形文字中直觀地感知單個數字；2）基於數學和日曆的背景知識，象徵性地進行推理。圖 1 顯示了從帕倫克十字廟發現的瑪雅曆法，它從神話中的創世日期開始，接着是以長計數書寫的時間段，最後是由 Tzolk'in 和 Haab'日曆編碼的特定日期。

圖 1. 瑪雅曆法，其中彩色盒子和「？」對應於未知數字

圖 2 描繪了查爾斯 P. 鮑迪奇（Charles P. Bowditch）破解圖 1 的記錄。他首先確認了一些已知的數字，並確認第一和第六個象形文字是相同的。然後，Bowditch 嘗試用視覺上相似的數字代替那些未知的象形文字，如圖 2 中的「第 1 列」所示。同時，他根據自己的推測和瑪雅曆法中的背景知識計算出 Tzolk'in 和 Haab'的值，如圖 2 的「第 2 列」所示。最後，通過觀察其猜想與計算的一致性，得到了正確答案「1.18.5.4.0，1 Ahau 13 Mak」。這整個過程應用的就是誘因問題解決方法。

圖 2. 鮑迪奇對圖 1 的解讀（他把「Mak」寫為「Mac」）。垂直框中的數字是他對圖 1 中未知象形文字的猜測（第 1 列）。虛線黃色框根據其計算結果（第 2 欄）標記一致結果。

受誘因問題解決方法的啟發，本文提出了誘因性學習（Abductive Learning，ABL），一種連接機器學習和邏輯推理的新方法。在 ABL 中，機器學習模型負責將子符號數據解釋為原始邏輯事實，邏輯模型可以根據一些一階邏輯背景知識對解釋後的事實進行推理，以得到最終的輸出。這一過程中最主要的困難在於子符號模型和符號模型很難一起訓練。更具體地說：1）它不具備訓練機器學習模型的原始邏輯事實（如圖 1 中的正確數字）的任何基本真理；2）沒有準確的原始邏輯事實，推理模型很難推斷出正確的輸出或學習正確的邏輯理論。

本文提出的誘因學習（ABL）試圖通過邏輯誘因和一致性優化來解決這些挑戰。給定一個與最終輸出相關聯的訓練樣本，邏輯推理可以對缺失的信息（例如，示例中的候選原始事實，或能夠完成背景知識的邏輯子句）進行推測，以建立從樣本到最終輸出的一致性證明。然後，分別用導出的原始事實和邏輯子句訓練機器學習模型，並將其作為符號知識存儲。一致性優化被用來最大化推測與背景知識之間的一致性。為了解決這個高度複雜的問題，作者將其轉換為一個任務，即搜索函數，猜測可能錯誤的原始事實。

由於收集瑪雅象形文字數據是非常困難的，作者設計了一個類似的任務——「手寫方程解謎」用於實驗。該任務具體為學習圖像識別（感知）和數學運算計算方程（推理）。實驗結果表明，ABL 比最先進的深度學習模型具有更好的泛化能力，並且能夠以一種互利的方式利用機器學習和推理。作者在一個可視化 n 皇后任務上的實驗進一步證明，ABL 框架是非常靈活的，可以利用約束邏輯編程等經典符號 AI 系統來提高機器學習的性能。

2.1.2 方法簡介

誘因性學習的任務可以形式化的表示如下。誘因性學習的輸入由一組標記的關於目標概念 C 和領域知識庫 B 的訓練數據組成 D = {, . . . ,} 。目標概念 C 是在一組原始概念符號 P=之間的未知關係下定義的。其中每個 pk 都是 B 中定義的符號。ABL 的目標是輸出一個假設模型 H=p∪C：

p 是從特徵空間到原始符號的映射，即它是一個傳統機器學習的感知模型；

C 是一組用 B 定義目標概念 C 的一階邏輯子句，稱為知識模型。

假設模型應滿足：

(1)

其中，符號｜= 表示邏輯暗含（logical entailment）。從公式（1）可以看出，誘因性學習的主要挑戰是感知模型 p 和知識模型C 之間的相互依賴關係：1） 需要依賴於感知結果 p(x)來學習 C，p(x)為 x 中原始概念的集合。2） 為了得到 p，需要得到用於訓練的基本真值標籤 p(x)，p(x)可以從 B∪C 和 y 的邏輯推導出來。當機器學習模型訓練不足時，感知到的原始符號 p(x)極有可能不正確，因此作者將其命名為偽基元（pseudo-groundings）或偽標籤（pseudo-labels）。因此，基於公式（1）的 C 推理是不一致的，當知識模型C 不準確時，邏輯推導出的偽標籤 p(x)也可能出錯，從而影響了 p 的訓練，而無論哪種方式都會中斷學習過程。

ABL 試圖通過將機器學習與誘因性邏輯推理模塊相連接，並通過一致性優化將它們的內部機制融合起來，從而解決這些挑戰。ABL 的完整框架見圖 3。其中， 機器學習（Machine Learning）用於學習感知模型 p：給定一個輸入實例 x，p 可以預測偽標籤 p(x)作為 x 中可能的原始概念的真值。當偽標籤包含錯誤時，需要重新訓練感知模型，此時，所使用的標籤是邏輯誘因返回的修正後的偽標籤 r(x)。邏輯誘因（Logical abduction）是誘因推理的邏輯形式化表示。給定以一階邏輯子句形式表述的觀測事實和背景知識，邏輯推理將對觀測事實的可能性解釋擴展為基本假設。

圖 3. ABL 完整框架

邏輯程序（Logic Programming）中的一個聲明性框架將上述的過程形式化，稱為誘因性邏輯程序（Abductive Logic Programming，ALP）[8]。形式上，誘因性邏輯程序（abductive logic program）可以定義如下：

定義 1：誘因性邏輯程序是一個三元組 (B,A,IC)，其中 B 是背景知識，A 是一組可擴展謂詞，IC 是完整性約束。給定一些觀測事實 O，程序輸出為一組 A 的真值推理結果，如：

即，誘因性解釋 是一種假設：根據背景知識 B 和約束 IC 來解釋觀察 O 是如何成立的。考慮到公式（1），ABL 將關於最終概念的實例標籤作為觀測事實，並將假設模型 H=p∪C 作為推導內容。給定一個固定的C，ABL 可以根據 B 和 Y 推導出 p(x)；當感知模型 p 確定後，ALP 能夠根據 B∪p(x)∪Y 推導出知識模型C。

ABL 的目標是學習與背景知識和訓練實例相一致的假設。更具體地說，ABL 試圖在給定背景知識 B 的情況下，最大化外推假設 H 與訓練數據 D 之間的一致性：

關於 ABL 的優化過程本文不在詳述，感興趣的讀者可以閱讀作者原文。

2.1.3 手寫方程解譯任務

為了驗證所提出方法的有效性，作者設計了一個手寫方程解譯任務，如圖 4 所示，並應用 ABL 進行求解。解譯任務的方程由連續的字符圖片組成。方程由符號圖像（「0」、「1」、「+」和「=」）構成並用未知的運算規則生成，每個例子都有一個表示公式是否正確的標籤。機器的任務是從一組帶標籤的方程組中學習，並期望訓練後得到的模型能夠正確地預測未知的方程組。因此，這項任務需要使用圖 1 中所示出的感知和推理能力來完成。

圖 4. 手寫方程解譯難題：機器應同時學習識別符號並找出未知運算規則（本例中為「xnor」）

圖 5 給出了本文中 ABL 實現的架構，它使用卷積神經網絡（CNN）作為感知機器學習模型。CNN 以圖像像素作為輸入，期望輸出為圖像中的符號。符號輸出構成了偽標籤。邏輯推理部分是用 Prolog 語言實現的一個誘因性邏輯程序。在訓練之前，將以邏輯程序形式編寫的領域知識作為背景知識 B 提供給 ALP。在作者的實現中，B 只涉及方程的結構和位操作的遞歸定義。方程結構的背景知識是一組定句語法（Definite Clause Grammar，DCG）規則，DCG 遞歸地定義一個數字是「0」和「1」的序列，每個方程共享 X+Y=Z 的結構，儘管 X、Y 和 Z 的長度可能不同。位操作的知識是一種遞歸的邏輯程序，它反向計算 X+Y，即對 X 和 Y 從最後一位到第一位逐位運算。

圖 5. ABL 結構

註：請注意，計算運算的具體規則在 B 中沒有定義，即「0+0」、「0+1」和「1+1」的結果可以是「0」、「1」、「00」、「01」甚至「10」。缺失的計算規則形成知識模型 C，這一部分是需要從數據中學習得到的。

訓練開始後，CNN 將圖像解釋為偽標籤「0」、「1」、「+」和「=」構造的符號方程。因為 CNN 沒有經過訓練，所以感知到的符號通常是錯誤的。在這種情況下，ALP 不能根據領域知識導出任何與訓練數據一致的 C。為了導出一致性的 C，ABL 學習了啟發式函數δ來標記可能不正確的偽標籤。

當 CNN 收斂或算法滿足迭代極限後，所有 < x_i , y_i > 被關係特徵確定為二元特徵向量。對於每個輸入方程 x_i，其偽標籤將由所有的關係特徵來評估以產生二進制向量 u_i= [u_i1,...,u_iT]：

原始數據集 D={}可以轉換為新的數據集 D』={}，從中可以學習一個決策模型來處理子抽樣帶來的噪聲問題。

2.1.4 實驗分析

作者構造了兩個符號的圖像集來建立如圖 6 所示的方程。數字二進制加法（Digital Binary Additive，DBA）方程是用基準手寫字符數據集中的圖像創建的，而隨機符號二進制加法（Random Symbol Binary Additive，RBA）方程則是從 Omniglot 數據集中隨機選擇字符集構建的，並與 DBA 任務中的方程具有相同結構。為了評價實驗中各種對比方法的感知泛化能力，用於訓練方程和測試方程的生成圖像是不相交的。每一個方程都作為數字和運算符的原始圖像序列輸入。訓練和測試數據包含長度為 5 到 26 的方程。對於每個長度，它包含 300 個隨機生成的方程，總共 6600 個訓練樣本。

圖 6. 手寫方程解譯任務的數據實例

本文實驗中所使用的對比方法包括：

1）ABL，機器學習模型由兩層 CNN、一個兩層多層感知器（MLP）和一個 softmax 層組成，邏輯誘因將 50 個位操作的計算規則集作為關係特徵，決策模型為兩層 MLP。實驗中嘗試了兩種不同的設置：使用所有訓練數據的 ABL-all 和僅使用長度為 5-8 的訓練方程的 ABL-short。

2）可微神經計算機（Differentiable Neural Computer，DNC），這是一個與記憶有關的深層神經網絡。

3）Transformer 網絡，這是一個經過關注增強的深層神經網絡，已經被證實在許多自然語言處理任務中是有效的。

4）雙向長短期記憶網絡（Bidirectional Long Short-Term Memory Network，BiLSTM），這是目前應用最廣泛的序列數據學習的神經網絡。為了處理圖像輸入，BiLSTM、DNC 和 Transformer 網絡也使用與 ABLs 相同結構的 CNN 作為它們的輸入層。所有的神經網絡都是用一個從訓練數據中隨機抽取的驗證集來調整的。

除上述對比方法外，作者還進行了人類實驗（human）。40 名志願者被要求對從相同數據集中取樣的方程圖像進行分類。在參加測試之前，向各位志願者提供了有關位操作的領域知識作為提示，但是具體的計算規則並不可知。作者沒有使用與機器學習實驗完全相同的設置，而是給了志願者一個簡化版本，其中只有 5 個正方程和 5 個負方程，長度在 5-14 之間。

圖 7. DBA（左）和 RBA（右）任務的實驗結果

圖 7 中的實驗結果表明，在這兩個任務中，基於 ABL 的方法明顯優於其它進行比較的方法，並且 ABL 正確地學習了定義未知操作的符號規則。所有這些方法在 DBA 任務上的性能都比 RBA 好，這是因為 DBA 任務中的符號圖像更容易區分。ABL-all 和 ABL-short 的性能沒有顯著差異。隨着測試方程長度的增加，實驗中用於比較的其它方法的性能迅速退化到隨機猜測的準確度水平，而基於 ABL 的方法對未知數據的推導預測效果更好。一個有趣的結果是，人在這兩個任務上的表現非常接近而且都比 ABL 差。根據志願者的說法，他們並不需要區分不同的符號，在這種任務中人們非常容易出錯，而機器在檢查邏輯理論一致性方面是很擅長的。因此，應該更好的利用機器學習系統在邏輯推理方面的優勢。

2.1.5 文章小結

作為心理學中一種重要的認知模型，誘因已經引起人工智能領域的關注。現有的工作大多數是在符號域中將誘因性（Abduction）與歸納（Induction）結合起來。也有一些工作使用誘因性學習改進機器學習的效果，這些方法一般需要將邏輯背景知識調整為函數約束，或者在學習和推理過程中使用特別設計的算子來支持梯度下降，從而將邏輯推理簡化為不同的連續優化問題。

另一方面，ABL 利用邏輯推理和試錯搜索（Trial-and-Error Search），在不使用梯度的情況下將機器學習與原始的一階邏輯連接起來。ABL 繼承了一階邏輯推理的全部能力，例如，它有可能放棄不在背景知識中的新的一階邏輯理論。因此，可以直接向本文介紹的 ABL 框架中引入許多現有的符號人工智能技術。

最後，ABL 框架具有通用性和靈活性。例如，感知機器學習模型可以是一個預先訓練好的模型，而不必須是從頭開始學習的。機器學習的任務可以是半監督的，而不必須是完全沒有標籤的。邏輯推理可以包括二階邏輯子句，從而可能能夠實現遞歸從句和謂詞自動發明。作者希望其對誘因性學習的探索能夠推動構建統一的學習和推理框架。

2.2 SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver [6]

本文是 ICML 2019 中獲得最佳論文提名的一篇文章。由於上一篇文章《Bridging Machine Learning and Logical Reasoning by Abductive Learning》在 2018 年已經在 arXiv 上進行了發布，所以本文有參考引用並對比分析了與上一篇文章的不同。上一篇文章所介紹的方法是從現有的一組已知關係中創建一個模塊（邏輯誘因模塊），以便深層網絡能夠學習到這些關係的參數。因此，該方法需要植入變量之間關係的先驗信息。本文所提出的方法則是端到端學習這些關係及其相關參數，即，本文引入了一個可微（平滑）最大可滿足性（maximum satisfiability，MAXSAT）求解器，並將其直接集成到深度學習系統的迴路中，而不是作為一個單獨的分離模塊所考慮。該求解器基於快速坐標下降法來解決與 MAXSAT 問題相關的半定程序（semidefinite program，SDP）。具體見第一篇文章中的「圖 3. ABL 完整框架」。ABL 框架包括了兩個獨立的模塊「Machine Learning」和「Logical Abduction」。邏輯誘因性分析是一個與機器學習 ML 完全分離的單獨模塊。而在這篇文章中，作者考慮，不將邏輯推理和 ML/DL 完全分離開，而是將邏輯推理作為深度學習系統完整迴路中的一個部分，實現端到端的學習。

2.2.1 方法介紹

MAXSAT 問題是著名的可滿足性（satisfiability，SAT）問題的優化模擬，其目標是使滿足的子句數最大化。作者提出了一個可微的平滑的近似 MAXSAT 解算器，可以集成到目前的深度學習網絡體系結構中。該解算器使用快速坐標下降法來求解 MAXSAT 的 SDP 鬆弛。考慮一個包含 n 個變量和 m 子句的 MAXSAT 實例。令 v 表示問題變量的二進制賦值，v_i 是變量 i 的真值，定義 s_i，其中 s_ij 表述子句 j 中 v_i 的符號。MAXSAT 問題定義為：

（1）

為了形成（1）的半定鬆弛約束，作者首先將離散變量 v_i 鬆弛為相關的連續變量且滿足 ||v_i||=1，相對於某個「真值方向」v_T 滿足 ||v_T||=1。此外，定義一個對應於 v_T 的係數 s_T。MAXSAT 的 SDP 鬆弛為：

（2）

這個問題是 MIN-UNSAT 的一個低秩（但非凸）公式，它等價於 MAXSAT。可以將這個公式重寫為一個 SDP，並且已經由研究人員證明給定 k>sqrt(2n)的情況下，該式可以恢復最優 SDP 解。儘管它是非凸的，可以通過坐標下降來優化地解決公式（2）。特別是，依賴於 v_i 的客觀條件表示為：

其中 s_i 是 S 的第 i 列向量。根據 ||v_i||=1 的約束條件，最小化 v_i 的值以得到坐標下降更新：

這些更新可證明能夠收斂到 SDP(2)（即公式（2）對應的 SDP）的全局最優不動點。

使用 MAXSAT SDP 鬆弛和相關的坐標下降更新，作者創建了一個用於可滿足性求解的深度網絡層（SATNet）。令 I 表示已知賦值的 MAXSAT 變量的指數，O≡\I 對應於未知賦值的變量的指數。SATNet Layer 允許以概率或二進制的形式輸入 z_l∈[0,1]，l∈I，然後輸出未知變量 z_o∈[0,1]，o∈O 的賦值，這些未知變量具有類似的概率值或二進制值。令 Z_I 和 Z_O 分別表示全部的輸入和輸出任務。

通過 SDP(2)從輸入 Z_I 生成輸出 Z_O，SATNet Layer 的權重對應於 SDP 的低秩係數矩陣 S。完整的前向傳遞過程如圖 1 所示，具體的層初始化和前向傳遞的步驟描述見算法 1。

圖 1. MAXSAT 層的前向傳遞。該層將已知 MAXSAT 變量的離散或概率賦值作為輸入，通過權重 S 的 MAXSAT SDP 鬆弛輸出對未知變量賦值的猜測。

【層初始化】

初始化 SATNet 時，用戶必須指定該層可以表示的最大子句數 m。通常希望將 m 的值設置的較低，因為低秩結構可以防止出現過擬合的問題，從而提高泛化能力。考慮到這種低秩結構，用戶希望通過輔助變量在一定程度上提高層的表示能力。這裡的高級直覺來自於布爾滿足問題的合取範式（Conjunctive Normal Form，CNF）表示。向問題中添加額外的變量可以顯著減少描述該問題所需的 CNF 子句的數量。

最後，令 k=sqrt(2n)+1，n 除了輔助變量外還捕獲實際問題變量的數量。這也是本文的 MAXSAT 鬆弛公式（2）恢復其相關 SDP 的最優解所需的最小 k 值。

【放鬆層輸入】

首先將其輸入 Z_I 鬆弛成連續向量用於 SDP 公式（2）。也就是說，將每一層輸入 z_l，l∈I 鬆弛到一個相關的隨機單位向量 z_l，v_l∈R^k：

（4）

公式（4）滿足：

（5）

其中，(v_l)^rand 為隨機單位向量。

【通過 SDP 產生連續的輸出鬆弛】

給定連續輸入鬆弛 V_I，使用坐標下降更新公式（3）來計算連續輸出鬆弛 v_o。值得注意的是，坐標下降更新只計算輸出變量，也就是說，不計算其賦值作為層輸入的變量。

前向傳遞的坐標下降算法詳細說明在算法 2 中。該算法保留了計算 g_o 所需的Ω=VS^T 項，然後在每次內部迭代中通過秩 1 更新對其進行修改。因此，每次迭代的運行時間是 O(nmk)。

【生成離散或概率輸出】

給定坐標下降的鬆弛輸出 V_O，層通過閾值或隨機取整將這些輸出轉換為離散或概率變量賦值 Z_O。隨機化捨入的主要思想是，對於每一個 v_o，o∈O，可以從單位球面上取一個隨機超平面 r 並賦值。

（6）

給定正確的權值，這種隨機取整過程保證了某些 NP-hard 問題的最佳期望逼近比。在訓練期間，沒有明確地執行隨機取整。相反，v_o 和 v_T 在給定 r 的同一側的概率是：

（7）

在測試過程中，既可以以相同的方式輸出概率輸出，也可以通過閾值分割或隨機捨入輸出離散賦值。如果使用隨機化捨入，則執行多次捨入後將 z_o 設為使公式（1）中 MAXSAT 目標最大化的布爾解。

最後，作者討論了後向傳遞，即，通過 SATNet layer 獲得反向傳播更新，使其能夠集成到神經網絡中。基於層輸出給定網絡損失 l 的梯度δl/δZ_O，根據層輸入和每層權重δl/δS 計算梯度δl/δZ_I。由於顯式展開前向傳遞計算並存儲中間 Jacobians 在時間和內存方面效率低下，因此作者採用了高效的坐標下降算法推導出直接計算期望梯度的解析表達式。算法 1 總結了計算這些梯度計算的步驟。

【從概率輸出到連續鬆弛】

給定 δl/δZ_O，可以通過概率分配機制推導出 δl/δV_O：

（8）

【通過 SDP 的反向傳播】

得到 δl/δV_O 後，通過 SDP 推導出解 δl/δS：

（9）

【從鬆弛結果到原始輸入】

最後，使用梯度 δl/δV_I 通過輸入鬆弛過程推導梯度 δl/δZ_x：

（12）

（13）

2.2.2 實驗分析

在實驗部分，作者證明了 SATNet 可以集成到深度神經網絡架構中進行端到端的訓練。作者選擇了一個可視化數獨問題進行實驗：即，給定一個用 MNIST 數字構造的數獨板的圖像表示（而不是一個熱編碼或其他邏輯表示），深度神經網絡必須輸出與之相關聯的數獨問題的邏輯解。

圖 3 給出了一個輸入示例。使用經典的深度神經網絡體系架構無法解決這個問題，因為解決這個問題要求能在不將問題的邏輯結構硬編碼為中間邏輯層的前提下組合多個神經網絡層。本文的神經網絡使用了一個連接到 SATNet layer 的卷積網絡結構。具體來說，將一個用於數字分類的卷積層（使用 LeNet 架構）應用到數獨輸入的每個單元。然後，將該卷積層的每個單元概率輸出作為邏輯輸入輸入到 SATNet layer。這個 SATNet layer 採用與前面描述相同的架構和訓練參數。整個模型經過端到端的訓練以最小化交叉熵損失，並通過 Adam 進行優化，SATNet layer 的學習率為 2x10^(3)，卷積層的學習率為 10^(5)。

作者將本文的方法與結合了兩組卷積層的卷積神經網絡進行了比較，表 1 給出了實驗結果。將這些結果與 74.7% 的理論「最佳」測試精度結合起來，這解釋了特定的卷積結構的數獨數字分類準確率。假設板子上 81 個填充單元中平均有 36.2 個單元（如測試集中）和一個 MNIST 模型，測試準確率為 99.2%，期望一個完美的數獨解算器輸出正確解的時間為 74.7%。（=0.99236.2）。在 100 個周期中，本文模型在測試時能夠正確求解出 63.2% 的棋盤，達到理論「最佳」的 85%。本文方法在端到端求解可視化數獨板方面表現出很強的性能。另一方面，基線卷積網絡在 100 個周期的過程中對訓練損失的改善微乎其微。因此，本文的 SATNet 架構能夠直接從圖形輸入中進行端到端的「遊戲規則」學習，這種學習方式在以前的架構中是不可能的。

表 1. 9x 9 個數獨實驗的結果，將 SATNet 模型與一個普通的卷積神經網絡（ConvNet）以及一個接收二進制掩碼指示需要學習哪些位的網絡（ConvNetMask）進行比較。

2.2.3 文章小結

這項工作涵蓋了深度學習和邏輯推理的知識。目前，一些研究人員已經提出了許多「可微邏輯推理」系統，但大多數系統仍然需要預先手工參與確定的邏輯規則和真值基礎，因此這些方法在某種程度上限制了它們以真正的端到端方式進行處理的能力。本文將強大而通用的邏輯處理器（如 MAXSAT 解算器）封裝在一個可微框架內，該解算器可以應用在更大的深度學習框架內進行「隱式」邏輯推理。作者認為，SATNet 為整合符號推理和深度學習（人工智能的長期目標）邁出了一步。

3. 應用數據庫介紹

3.1 LogiQA: A Challenge Dataset for Machine Reading Comprehension with Logical Reasoning [7]

本文是 IJCAI 2020 中的一篇錄用文章，是由來自復旦大學和西湖大學的研究人員共同完成的，主要研究目的是構建一個用於測試邏輯推理能力的閱讀理解數據庫 LogiQA。與上一節介紹的模型方法不同，本文主要介紹的是應用於邏輯推理和機器學習任務的數據庫的構建，以及結合具體的 NLP 任務介紹將邏輯推理和機器學習方法相結合的作用和意義。

機器閱讀是測試自然語言理解能力的一項基本任務，它與人類認知有着密切的關係。機器閱讀可以廣泛應用於開放領域問答與信息檢索等後續任務中。隨着 NLP 深度學習的最新進展，閱讀理解研究也有了長足的發展，從能夠用簡單事實來回答的問題發展到需要通過多跳推理來整合不同證據的問題，以及對於人類閱讀理解都非常有難度的需要利用給定段落之外所涉及的常識來回答的問題。

邏輯推理是人類閱讀理解和問答的一個重要方面，也是早期人工智能的主要研究課題之一，然而目前涉及邏輯推理的 NLP 數據庫非常有限。圖 1 給出了一個需要通過邏輯推理才能完成的閱讀理解問題。P1 由一段事實和一個問題組成，這個問題要求被測者以事實為前提選擇一個有效的結論。為了選出正確的候選者，機器需要理解前提和候選者的答案。正確的答案可以通過絕對推理找到。

圖 1. LogiQA 示例，紅色對勾表示正確答案。

隨着深度學習技術的興起，在簡單的問答 QA（Question-Answer）任務中，算法模型展現出了良好的性能，此外，也提出了大量應用於機器閱讀的數據庫。在一個典型的 QA 任務設置中，將一篇文章和一個問題輸入系統，任務要求是從候選答案列表中選擇一個最合適的答案。P2 是一個更具挑戰性的問題，段落中只提供了一個前提和結論，需要在缺少一個前提的情況下選擇答案。問題涉及三類工人，包括 A 宿舍區工人、B 車間工人和紡織工人。被測試者可以通過繪製三組工人之間的邏輯關聯來找到答案。

回答本文所構建的 LogiQA 所涉及的閱讀理解問題需要同時具有自然語言理解（NLU）和邏輯推理能力。與簡單事實的問答相比，LogiQA 中段落和候選答案之間的詞彙重疊所起的作用相對較小。與常識性閱讀理解相比，LogiQA 的問題不太依賴外部知識，而是需要邏輯推理來解答。LogiQA 包含 8678 個段落問題對，每個問題有四個候選答案。相關數據來源於公開提供的閱讀理解邏輯試卷，這些試卷由領域專家設計，用於評估邏輯推理能力和測試參與者。問題的質量和主題覆蓋是可靠的。作者從原始數據集中手動選擇問題，過濾掉了涉及數字、圖表或數學計算量較大的問題，並確保邏輯推理類型的廣泛覆蓋，包括範疇推理、條件推理、析取推理和連詞推理等。

3.1.1 數據庫介紹

本文作者通過收集中國國家公務員考試公開試題中的邏輯理解題來構建 LogiQA，這個考試的目的是測試公務員的批判性思維和問題解決能力。作者收集了官方網站上發布的原始數據，得到了 13918 個段落問題選擇題。執行以下步驟來清理原始數據。首先，刪除所有不符合問題設置格式的實例，即如果候選選項的數量不是 4，則刪除該問題。其次，根據文本信息過濾掉所有包含圖像或表格的段落和問題。還刪除了所有包含關鍵字 「下劃線」和「排序句子」的問題，因為對於典型的機器閱讀器來說，很難重現下劃線和句子編號順序的場景。最後，作者刪除了所有重複的段落問題對。最終的結果數據集包含 8678 個段落問題對。由於原始數據集是用中文編寫的，因此作者還聘請了五名專業英語人士手動翻譯數據集。為了保證翻譯質量，又專門聘請了三名校對員。如果校對者認為翻譯存在問題，則將翻譯後的實例再次發送回翻譯人員進行修訂。作者同時發布了中文版的 LogiQA（中文 LogiQA），用於基於漢語推理的閱讀理解研究。

範疇推理（Categorical reasoning）：目的是推理一個特定的概念是否屬於一個特定的範疇。這種推理通常與量詞相關，如「all/everyone/any」、「no」和「some」等。

充分條件推理（Sufficient conditional reasoning）：假設推理的類型是基於 「如果 P，那麼 Q」形式的條件陳述，其中 P 是前因，Q 是後因。

析取推理（Disjunctive reasoning）：在這種推理中，前提是析取的，形式是「要麼。或者。」，只要一個前提成立，結論就成立。

合取推理（Conjunctive reasoning）：在這類推理中，前提是連詞，形式是「兩個。還有。」，只有當所有前提成立時，結論才成立。

如下，表 1 總結了 LogiQA 的詳細統計數據。

表 1. LogiQA 的統計數據

LogiQA 基準測試集由 867 個段落問題對組成。作者根據 Hurley 定義的邏輯推理的五種類型對實例進行人工分類[9]，包括範疇推理、充分條件推理、必要條件推理、析取推理和合取推理。這些推理屬於演繹推理，即給定一套前提條件，能夠得出明確的結論。因此，這種推理方法最適合於定量評價性能。圖 2 給出了 LogiQA 中推理類型的統計信息和代表性示例。

圖 2. LogiQA 中每種邏輯推理的例子（紅色對勾表示正確答案）

3.1.2 驗證的深度學習方法介紹

作者評估了典型的應用於閱讀理解任務的各類模型的性能，包括基於規則的方法、深度學習方法以及基於預先訓練的上下文嵌入的方法。此外，還對人類直接進行閱讀理解的完成情況進行了評估，並報告了最佳性能。

【基於規則的方法】

作者採用了兩種基於規則的方法，通過簡單的詞彙匹配給出答案。單詞匹配 [10] 是基於規則的基線方法，它選擇與給定段落問題對的單字格重疊程度最高的候選答案。滑動窗口 [11] 通過從給定段落問題對中的 n 個單詞中提取 TF-IDF 類型特徵來計算每個候選答案的匹配分數。

【深度學習方法】

深度學習方法通過文本匹配技術計算給定段落、問題和每個候選答案之間的相似度，從而找到閱讀理解的答案。例如，可以使用 LSTM 編碼和雙線性注意力函數計算段落問題對和候選答案之間的相似性。門控注意力閱讀器採用多跳結構，具有更細粒度的機制來匹配候選答案與段落問題對。協同匹配網絡通過對每段文本進行編碼並計算每對文本之間的匹配分數，進一步提升段落 - 問題對和段落 - 候選答案對的匹配效果。

【預訓練方法】

與深度學習方法不同，預訓練方法將段落、問題和每個候選答案視為一個連接句子，使用預先訓練的上下文嵌入模型對句子進行編碼以計算其得分。給出四個候選答案，將每個候選答案與段落和問題配對，然後構造四個連接句子，並選擇模型得分最高的一個作為答案。這一類方法包括 BERT、RoBERTa 等。

【人工方法】

本文研究團隊僱傭了三名研究生進行人工方法的評估，並給出了從測試集中隨機選取的 500 個樣本的平均分數。在計算最優性能時，如果其中一個學生給出了正確的答案，就認為人工方法針對這個問題能夠給出正確答案。

3.1.3 實驗分析

隨機分割數據集，將其中的 80% 用於訓練，10% 用於開發，其餘 10% 用於測試。表 2 給出了節 3.1.2 中所討論的模型的結果。人工方法的測試結果達到了 86.00%，最高的結果達到 95.00%，這說明對於人類測試者而言，LogiQA 的難度並不大。相比之下，其它所有算法模型的性能都比人類差得多，這表明這些方法在邏輯推理閱讀理解方面相對較弱。此外，中文數據集的結果與英文數據集的結果處於同一水平。

兩種基於規則的方法的準確率分別為 28.37% 和 22.51%，後者甚至低於隨機猜測的基線水平。這說明單靠詞彙匹配很難解決 LogiQA 中的這些問題。深度學習方法的準確率在 30% 左右，效果要優於隨機猜測的方法，但遠遠落後於人類的表現。一個可能的原因是這些方法都是經過端到端的訓練，結果發現基於注意力的文本匹配很難學習潛在的邏輯推理規則。預先訓練的模型具有一定的常識性和邏輯能力，與沒有上下文嵌入的方法相比，這種模型具有更好的性能。然而，RoBERTa 的最佳結果是 35.31%，仍然遠遠低於人類的表現。這表明預先訓練的模型中的知識對於邏輯推理來說是相當薄弱的。

表 2. LogiQA 的主要結果（準確率 %）

3.1.4 文章小結

本文提出了一個大型邏輯推理閱讀理解數據庫 LogiQA。除了測試機器閱讀的推理能力外，LogiQA 還可以作為重新審視在深度學習 NLP 時代長期追求的邏輯人工智能研究的基準水平。本文的實驗結果表明，最先進的機器閱讀器（各類算法、模型）仍然遠遠落後於人類的閱讀能力。本文所提出的數據集可以作為後續測試閱讀理解能力的測試基礎。

4. 小結

本文在回顧什麼是「邏輯」的基礎上，討論了構建有邏輯的（Logical）和可推理的（Reasoning）系統問題。其中，重點關注了兩篇邏輯推理與深度神經網絡相結合的文章。這兩篇文章的題目很類似，所做的工作也具有一定的延續性和對比性。第一篇文章是將誘因性學習作為一個模塊引入到經典的深度學習網絡架構中，第二篇文章則是引入了一個可微（平滑）最大可滿足性（MAXSAT）求解器，並將其直接集成到深度學習系統的迴路中，而不是作為一個單獨的模塊所考慮。

最後一篇文章重點是結合 NLP 中的閱讀理解任務構建了一個需要通過邏輯推理才能得到答案的 LogiQA 數據庫。在這篇文章中作者只是使用了經典的基於規則、深度學習和預訓練的方法進行實驗，且效果都不好，都遠低於人類直接進行閱讀理解的水平，經典深度學習方法的效果甚至低於預訓練的方法。但是作者並未對這種差距進行深入分析，尚無法判斷是否在 NLP 這一專門領域的邏輯推理任務中預訓練一定優於深度學習方法。

由我們分析的幾篇文章可以看出，很顯然，在強邏輯任務中機器還無法和人類相比擬。如何使深度學習 / 機器學習的方法或模型具備強大的推理能力，似乎仍然是一個懸而未決的問題。

參考文獻

[1] King, R.D., Rowland, J., Oliver, S.G., Young, M., Aubrey, W., Byrne, E., Liakata, M., Markham, M., Pir, P., Soldatova, L.N. and Sparkes, A., 2009. The Automation of Science. Science, 324(5923), pp.85–89.

[2] Raza, M. and Gulwani, S., 2017, February. Automated data extraction using predictive program synthesis. In Thirty-First AAAI Conference on Artificial Intelligence.

[3] https://stripe.com/radar/guide#rules-and-manual-reviews

[4] https://medium.com/abacus-ai/an-overview-of-logic-in-ai-and-machine-learning-2f41ccb2a335

[5] Bridging Machine Learning and Logical Reasoning by Abductive Learning, 2019, NeurIPS 2019, https://papers.nips.cc/paper/8548-bridging-machine-learning-and-logical-reasoning-by-abductive-learning.pdf

[6] SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver, ICML 2019, http://proceedings.mlr.press/v97/wang19e/wang19e.pdf

[7] Liu J , Cui L , Liu H , et al. LogiQA: A Challenge Dataset for Machine Reading Comprehension with Logical Reasoning[C]// Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence {IJCAI-PRICAI-20. 2020.

[8] A. C. Kakas, R. A. Kowalski, and F. Toni. Abductive logic programming. Journal of Logic Computation, 2(6):719–770, 1992.

[9] Patrick J. Hurley. A concise introduction to logic. Nelson Education, 2014.

[10] Wen-tau Yih, Ming-Wei Chang, C. Meek,and A. Pastusiak. Question answering using enhanced lexical semantic models. In ACL, 2013.

[11] M. Richardson, C.J.C. Burges, and E. Renshaw. MCTest: A challenge dataset for the opendomain machine comprehension of text. In EMNLP, 2013.

分析師介紹：

本文作者為仵冀穎，工學博士，畢業於北京交通大學，曾分別於香港中文大學和香港科技大學擔任助理研究員和研究助理，現從事電子政務領域信息化新技術研究工作。主要研究方向為模式識別、計算機視覺，愛好科研，希望能保持學習、不斷進步。