Neural logic programs and neural nets

神經邏輯程序與神經網絡

https://arxiv.org/abs/2406.11888

摘要

神經符號集成（Neural-symbolic integration）旨在將連接主義的次符號方法與邏輯的符號方法結合起來，用于人工智能研究。在本文中，我們首先定義了（布爾）神經網絡的答案集語義（answer set semantics），然后從第一原理出發引入了一類神經邏輯程序，并證明了神經網絡與神經邏輯程序是等價的。

1. 引言

人工神經網絡受人類大腦的啟發（McCulloch & Pitts, 1943；Turing, 1948），在人工智能領域有諸多應用，例如模式識別（參見 Bishop, 2006）、通過反向傳播實現深度歸納學習（參見 Goodfellow 等人, 2016），以及 AlphaGo 在圍棋游戲中擊敗人類冠軍（Silver 等人, 2017），僅舉幾例。
神經網絡構成了所謂“連接主義”或“次符號”AI 方法的核心。支撐神經網絡的數學學科包括分析學、概率論和統計學。

另一方面，邏輯編程代表了符號化和邏輯化的（傳統的、經典的）AI 方法（Apt, 1990；Lloyd, 1987）。它起源于數理邏輯和自動推理，其主要數學工具是離散數學中的邏輯、代數和組合學。

這兩個世界——次符號世界和符號世界——各有其優勢和劣勢。邏輯形式系統可以被人類解釋，并具有明確的形式語義，而這是神經網絡所缺乏的。另一方面，連接主義系統具有顯著的抗噪性和學習能力，這在邏輯形式系統中通常是缺失的（一個值得注意的例外是歸納邏輯編程（Muggleton, 1991））。

因此，神經符號集成的目標是將符號與次符號世界結合起來（Valiant, 2008）（參見 d’Avila Garcez 等人, 2002, 2009, 2015；Raedt 等人, 2020）。盡管這一領域歷史較短，但其成果已相當顯著，并廣泛應用于生物信息學、控制工程、軟件驗證與適應、視覺智能、本體學習和計算機游戲等領域（Borges 等人, 2011；de Penning 等人, 2011；Hitzler 等人, 2005）。此外，它還與統計關系學習和概率邏輯學習密切相關（Raedt, 2008；Raedt 等人, 2008, 2020；Getoor & Taskar, 2007）。

本文的主要貢獻可概括如下：

(1) 首先，在第 §2 節中，我們通過定義神經網絡的“直接后果算子”和“Fitting 算子”（van Emden & Kowalski, 1976；Fitting, 2002），并應用近似不動點理論（Approximation Fixed Point Theory，簡稱 AFT）（Denecker 等人, 2000, 2004, 2012）——這是一種非單調推廣的著名 Knaster-Tarski 定理（Tarski, 1955）——為（布爾）神經網絡定義答案集語義（Gelfond & Lifschitz, 1991）（參見 Baral, 2003；Lifschitz, 2019；Brewka 等人, 2011；Eiter 等人, 2009）。據我們所知，本文首次認識到可以在（布爾）神經網絡上賦予這樣的語義（前提是能夠記住神經元的激活狀態）。

(2) 其次，在第 §3 節中，我們從第一原理出發引入“神經邏輯程序”，即由神經元構建的程序。我們定義了正程序的最小模型語義，并再次通過 AFT 定義任意程序的答案集語義；此外，我們按照 Faber-Leone-Pfeifer 歸約（Faber 等人, 2004, 2011）以通常的方式定義 FLP-答案集語義。

(3) 最后，在第 §4 節中，我們證明了神經網絡與神經邏輯程序是等價的。

從某種意義上說，我們的方法與著名的“核心方法”（core method）（H?lldobler & Kalinke, 1994；H?lldobler 等人, 1999）是相對的：核心方法是從一個命題邏輯程序出發，構造一個模擬該程序的神經網絡。核心方法是 d’Avila Garcez 等人（2009）所提出的基于模擬的神經符號集成工作的基礎。從更廣義的角度來看，本文是朝向神經符號集成方向邁出的又一步。

2. 神經網絡

在本節中，我們首先回顧（布爾）神經網絡，其形式例如在 d’Avila Garcez 等人（2002, §3）中有所呈現（與之有一個重要區別：我們在此假設神經元在激活后保持激活狀態）。我們將神經元的功能簡化為：根據其輸入的加權和以及給定的閾值，計算出一個布爾輸出。接著，我們定義了正網絡的最小模型語義（§2.2），并定義了任意網絡的答案集語義（§2.3），這部分內容似乎是原創的。

在接下來的內容中，我們用 R 表示實數集，用 R? 表示正實數集，令 R?∞ := R ∪ {?∞} ，并用 B = {0, 1}表示布爾值集合。我們用 |X| 表示集合 X 的基數。定義空和為:∑?∈? a? := ?∞。

3 設 f : L → L 是定義在格 L = (L, ≤) 上的一個函數，若某個元素 a ∈ L 滿足 f(a) ≤ a ，則稱 a 是函數 f 的一個前不動點 （prefixed point）；當且僅當 f(a) = a 時，我們稱 a 是 f 的一個不動點 （fixed point）。

2.1 神經元與神經網絡

設 A 是一個神經元的集合，其中每個神經元 a ∈ A 由其閾值 θ(a) ∈ R?∞ 所確定。

一個在 A 上的（神經）網絡 N 是一個有限的加權有向圖，其頂點是來自 A 的神經元，邊的形式為 a ??→??? b ，其中權重 w?b ∈ R 。如果 w?b ≠ 0 ，我們稱神經元 a 和 b 是連接的 （connected）；如果 w?b = 0 ，我們稱它們是斷開的 （disconnected）。一個網絡稱為正網絡 （positive），當且僅當它只包含正權重。當神經元 a ∈ A 出現在網絡 N 中時，我們寫作 a ∈ N 。對于神經網絡 N 中的神經元 a ∈ N，我們定義其體部 （body）為：

一個事實 （fact）是指其體部為空且沒有權重的神經元，對于給定的事實 a ，我們總是假設 θ(a) = ?∞；而如果 a 不是事實，則我們假設 θ(a) ≠ ?∞ 。我們將網絡 N 中的事實記作 facts(N) 。這些事實將表示輸入信號。

一個 普通網絡 （ordinary net）是一個網絡 N ，滿足對所有 a ∈ N ，有 θ(a) = |bN(a)| ，并且對所有 b ∈ bN(a) ，有 wba = 1 。直觀上，在一個普通網絡 N 中，一個神經元 a “激發”（fires）當且僅當其體部中的每一個神經元 bN(a) 都“激發”。

2.2 正網絡的最小模型語義

一個解釋 （interpretation）是 A 的任意子集，我們將 A 上所有解釋的集合記作 I? 。我們可以將每個解釋 I 解釋為一個函數 I : A → B ，使得 I(a) = 1 當且僅當 a ∈ I 。

在文獻中（例如 d’Avila Garcez 等人, 2009, §3），神經網絡的功能是相對于某個時間點 t 給出的，通常來說，在時間點 t 神經元 a 被激活意味著它在時間點 t + 1 是非激活的，除非存在從 a 到自身的遞歸連接。在本文中，我們采取一種不同的方法：我們假設一旦神經元 a 被激活，它將保持激活狀態；或者換一種解釋方式，我們認為系統會記住 a 曾被激活過。這種方法允許網絡達到穩定的狀態配置，我們將這些穩定狀態與穩定模型（或答案集模型）相對應。這將使我們在第 §4 節能夠證明神經網絡與邏輯程序是等價的。

定義 1 . 對于每一個解釋 I ，定義網絡 N 的（直接后果）算子如下：

這意味著，一個沒有事實（即沒有輸入信號）的正網絡總是具有空的最小模型。

定義神經網絡的直接后果算子以及正網絡的最小模型的概念似乎是新的。

2.3 任意網絡的答案集語義

一個可能包含負權重的任意神經網絡的直接后果算子 可能是非單調的 ，這意味著它的最小不動點可能不存在。近似不動點理論 （Approximation Fixed Point Theory，簡稱 AFT）（Denecker 等人，2000，2004，2012；Fitting，2002）正是為了處理這類非單調算子而設計的，它可以被視為將經典的 Knaster-Tarski 定理 從單調格算子推廣到非單調格算子的情形。

在本節中，我們使用 AFT 來定義神經網絡的答案集語義，這似乎是原創性的。我們通過按照標準流程來定義答案集：即基于三值 Fitting 算子（Definition 5）來進行定義。

2.4 無環網絡

一個網絡是無環的 （acyclic），當且僅當它不包含由非零權重邊構成的環路。請注意，一個無環網絡 N中的神經元可以被劃分為若干層（layers），其中每一層的神經元只接收來自更低層級神經元的輸入邊。

一個 n 層前饋網絡 （n-layer feed-forward net），或稱 n-net ，是一個無環網絡
N = N? ∪ … ∪ N? （不交并），其中 N? 包含第 i 層的神經元（1 ≤ i ≤ n）；我們將 N? 稱為輸入層 ，將 N?稱為輸出層 。回想一下，我們假設所有輸入層神經元 a ∈ N? 的閾值 θ(a) = 0 ，因為它們的體部 bN(a) 是空的，這意味著每個 a ∈ N? 都是一個事實（參見 §2.1）。

每一個 n-net N = N? ∪ … ∪ N? 都計算一個（布爾）函數 f? : I?1 → I?? ，
（注意：I 可能僅包含來自輸入層 N? 的神經元，而 f?(I) 僅包含來自輸出層 N? 的神經元），其定義為：

3. 神經邏輯程序

在本節中，我們將神經邏輯程序定義為由神經元構建而成的程序。

3.1 語法

設 A 是一個有限的神經元集合。一個在 A 上的（神經邏輯）程序是由有限條形如以下形式的（神經）規則組成的集合：

其中，a?, ..., a? ∈ A 是神經元，且w = (w????, ..., w????) ∈ R? ，滿足對所有 1 ≤ i ≤ k ，有 w???? ≠ 0 ，這些是權重。形式為 (3) 的規則被稱為正規則 （positive），當且僅當所有的權重 w?, ..., w? ≥ 0 都是正數；一個程序被稱為正程序 （positive program），當且僅當它僅由正規則組成。

為了方便起見，對于形式為 (3) 的一條規則 r ，我們定義：

如果對于每一個規則頭最多只有一條對應的規則，則稱該程序是極簡主義的 （minimalist）。

我們定義程序 P 的依賴圖 （dependency graph）為：dep(P) := (A?, E?) ，其中 A? 是出現在程序 P 中的所有神經元，在 E? 中存在一條邊 a ??→??? b 當且僅當存在一條規則：

請注意，程序的依賴圖本質上就是一個神經網絡 （net）！
一個程序是無環的 （acyclic），當且僅當它的依賴圖是無環的。
類似于無環網絡，出現在一個無環程序 P 中的神經元集合 A? 可以被劃分為若干層：
A? = A1? ∪ … ∪ A?? （不交并），使得對于每一條規則 r ∈ P ，如果 h(r) ∈ A?? ，那么對每一個 b ∈ b(r) ，都有 b ∈ A???? ，其中 1 ≤ k ≤ i ? 1。一個 n-程序 （n-program）是一個可以被劃分為 n 層的無環程序。

一個普通規則 （ordinary rule）是指形式為 (3) 的規則，其中權重 w = (1, ..., 1) ∈ R? ，并且 θ(a?) = k ，我們可以簡單地將其寫作：

一個普通程序 （ordinary program）僅由普通規則組成。

3.2 答案集語義

我們現在定義神經邏輯程序的語義。與神經網絡一樣，程序的一個解釋 （interpretation）是 A 的任意子集。

定義 6 . 普通程序的語義定義如下，類似于普通的命題 Horn 邏輯程序，歸納地定義為：

• 對于一個神經元 a ∈ A ，有 I |= a 當且僅當 a ∈ I ；

• 對于一個神經元集合 B ? A ，有 I |= B 當且僅當 B ? I ；

• 對于一個形式為 (4) 的普通規則 r ，有 I |= r 當且僅當 I |= b(r) 蘊含 I |= h(r) ；

• 對于一個普通程序 P ，有 I |= P 當且僅當對每個 r ∈ P 都有 I |= r 。

定義 7 . 我們歸納地定義神經邏輯程序的語義如下：

• 對于一個神經元 a ∈ A ，有 I |= a 當且僅當 a ∈ I 。

• 對于一個形式為 (3) 的規則 r ，我們定義：

  
  

• 對于一個神經邏輯程序 P ，我們定義 I |= P 當且僅當對每個規則 r ∈ P 都有 I |= r ，此時我們稱 I 為程序 P 的一個 模型 （model）。

定義 8 . 對于每一個解釋 I ，定義程序 P 的（直接后果）算子（(immediate consequence) operator）（van Emden & Kowalski, 1976）如下：

請注意，該算子與神經網絡在 (1) 中定義的直接后果算子 具有相似性，這將在第 §4 節中起到關鍵作用。如果程序 P 是普通程序，則我們得到的就是 van Emden 和 Kowalski（1976）所提出的普通直接后果算子。

例 9 . 考慮如下程序：

例如，假設 w = 0 且 θ(b) > 0 ，則程序 P 的最小模型是 {a} ，這與我們通過令 w = 1 且 θ(b) = 1 所得到的普通程序的最小模型 {a, b} 不同。

事實 10 . 一個解釋 I 是程序 P 的模型，當且僅當 I 是算子 T? 的前不動點（prefixed point）。

一個解釋 I 是程序 P 的支持模型 （supported model），當且僅當 I 是算子 T? 的不動點（fixed point）。
當一個程序與其對應的神經網絡具有相同的支持模型時，我們稱該程序與該網絡是支持模型等價（supported model equivalent）的。

與神經網絡類似，正程序 P 的算子是單調的，因此它存在一個最小不動點。根據事實 10，這個最小不動點就是 P 的一個模型，稱為 P 的最小模型 。

程序 P 與神經網絡 N 是蘊含等價 （subsumption equivalent）的，當且僅當 T? = T? （Maher, 1988）。
此外，一個正程序與其對應的神經網絡是最小模型等價 的，當且僅當它們的最小模型一致。

同樣地，對于非正程序來說，其對應的算子可能是非單調的 ，這意味著它的最小不動點可能不存在。

我們可以像定義任意神經網絡的答案集語義一樣，來定義任意神經邏輯程序的答案集語義：
我們定義算子 Φ? 和 Φ?? ，并規定 I 是程序 P 的答案集當且僅當 I = Φ??(I) 。
請注意，這種構造方法是通過 Fitting 算子來定義程序的答案集語義的標準流程（參見 Fitting, 2002；Denecker 等人, 2012）。
當且僅當一個程序與其對應的神經網絡具有相同的答案集時，我們稱該程序與該網絡是等價 的。

與神經網絡不同的是，我們可以使用Faber-Leone-Pfeifer 歸約 （reduct）直接定義神經邏輯程序的答案集語義（Faber 等人, 2004, 2011），其定義如下：
對每一個程序 P 和解釋 I ，歸約后的程序 P^I 定義為：

我們現在可以說：I 是程序 P 的一個 FLP-答案集 （FLP-answer set）當且僅當 I 是 P? 的一個 ?-極小模型 （即關于集合包含關系 ? 是極小的模型）。

請注意，我們無法以一種合理的方式定義神經網絡的歸約（reduct），因為對于網絡來說并沒有“規則”的概念，這意味著神經網絡不存在 FLP-答案集的概念。

4. 等價性

我們現在可以證明本文的主要結果。

定理 11 . 每個神經網絡都與某個極簡主義神經邏輯程序是蘊含等價 （subsumption equivalent）的。

備注 12 . 注意，在定理 11 的證明中構造的神經邏輯程序 P? 是極簡主義的 （minimalist），即它對每一個規則頭最多只包含一條規則。此外，如果網絡 N 是無環的，則程序 P? 也是無環的。

推論 13 . 每個神經網絡都與某個極簡主義神經邏輯程序是支持模型等價 （supported model equivalent）的。

推論 14 . 每個正神經網絡都與某個正的極簡主義神經邏輯程序是最小模型等價 （least model equivalent）的。

定理 15. 每個普通神經網絡都與某個普通極簡主義神經邏輯程序是 蘊含等價 （subsumption equivalent）的。

證明 . 如定理 11 的證明中所定義的極簡主義程序 P? 與如下普通程序是等價的：

證明 . 給定一個 n-net（n 層前饋網絡）N ，在定理 11 的證明中構造的程序 P? 是一個與 N 等價的 n-程序 。證畢。 □

5. 未來工作

在本文中，神經元是布爾型 的，即它們的輸出是從集合 {0, 1} 中取值的布爾值，這一點對于將其翻譯為神經邏輯程序至關重要。如果我們允許神經元具有實數值（或任何其他半環中的值），那么我們需要將它們翻譯為加權神經邏輯程序 （weighted neural logic programs），其中語義也應定義在實數域（或該半環）中（參見 Droste & Gastin, 2007；Stüber & Vogler, 2008；Cohen 等人, 2011）。這是非常重要的，因為像反向傳播這樣的學習策略只能在非布爾環境中運行。

這引出了我們下一步的研究方向：在神經邏輯程序的框架下解釋諸如反向傳播等知名的學習策略，并分析直接后果算子 在學習過程中的作用。

HEX 程序 （Eiter 等人, 2005）通過在答案集程序中引入外部原子 （external atoms），可以用于實現神經邏輯程序：每個神經元可以用一個外部原子來表示，前提是 HEX 程序被推廣為允許外部原子出現在規則頭中（這仍是尚未解決的問題）。

可以說最引人入勝的一個未來研究方向是將本文的概念和結果從命題級 提升到一階神經邏輯程序 。這需要回答一個根本性問題：“什么是‘一階神經元’？”這個問題與神經符號集成的核心問題——變量綁定（variable binding）密切相關（參見 Smolensky, 1990；Sun, 1994；Browne & Sun, 1999；Feldmann, 2013；另見 Bader 等人, 2008）。這一研究方向將與最近提出的神經隨機邏輯程序 （neural stochastic logic programs）相關聯（Manhaeve 等人, 2021；Winters 等人, 2022），它通過引入神經謂詞擴展了概率邏輯程序。

最后，引入并研究神經邏輯程序的順序組合 （sequential composition）（Anti?, 2024, 2023c）對于程序的組合與分解來說似乎是基礎性的：因為它提供了神經邏輯程序的代數結構，從而也為神經網絡提供了代數結構，可用于定義神經邏輯程序之間的“類比比例”（analogical proportions），形式如：“P 對于 Q 就如同 R 對于 S”，進而定義神經網絡之間的類比比例。

更有趣的是形如 P : R :: M : N 的“混合比例”，其中 P、R 是普通程序，而 M、N 是表示神經網絡的神經程序，最終為我們提供了一個純邏輯程序與神經網絡之間的代數聯系，這種聯系表現為滿足P : R :: F(P) : F(R)的比例函子 （proportional functors）F （Anti?, 2023b）。

6. 結論

在本文中，我們定義了正（布爾）神經網絡的最小模型語義 ，以及任意（布爾）神經網絡的答案集語義。隨后，我們從第一原理出發定義了一類神經邏輯程序 ，并證明了神經網絡與神經邏輯程序是等價的 。從更廣泛的意義上講，本文是朝向神經符號集成 方向邁出的又一步。

原文鏈接： https://arxiv.org/abs/2406.11888