神经逻辑程序与神经网络 Neural logic programs and neural nets

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ᴺ¹ → 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ᴾ = A¹ᴾ ∪ … ∪ 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