逻辑、优化与人工智能

# 逻辑、优化与人工智能 来源：https://arxiv.org/html/2607.15532 11institutetext:卡内基梅隆大学,11email:jh38@andrew\.cmu\.edu

## 1 引言

逻辑与优化自人工智能（AI）诞生之初便发挥了核心作用。最早的AI程序（1956年）——逻辑理论家NewSim56 (https://arxiv.org/html/2607.15532#bib.bib107)，证明了逻辑与数学中的定理，包括罗素与怀特海德著名著作《数学原理》中的多个定理。次年，开创性的AI系统“通用问题求解器”NewShaSim59 (https://arxiv.org/html/2607.15532#bib.bib106)以类似于逻辑编程的方式应用了手段-目的分析。至于优化，机器学习和人工神经网络的问世立刻引出了调整参数以拟合训练数据的问题。这一优化问题至今仍是机器学习中核心且富有挑战的要素。

逻辑与优化不仅在AI中各自有用，它们结合在一起时更能带来巨大价值。二者共同为基于规则的AI提供了一种理想的实现路径。虽然联结主义机器学习取得了令人瞩目的成果，但它日益暴露出透明度问题，而对可复现性、可解释性、可信赖性和公平性而言，透明度至关重要BurHub21 (https://arxiv.org/html/2607.15532#bib.bib29);Hai20 (https://arxiv.org/html/2607.15532#bib.bib60);Wal21 (https://arxiv.org/html/2607.15532#bib.bib127);ZhoChe18 (https://arxiv.org/html/2607.15532#bib.bib135)。基于规则的AI则为透明度提供了一种自然的解决方案，因为它允许将知识显式编码为规则，从而从中推断出相关信息，并允许基于规则的生产系统推导出决策。

虽然神经网络提供了一种有用的认知模型，但基于规则的框架长期以来一直是另一种可选模型。例如，受AI先驱艾伦·纽厄尔启发的著名ACT-R框架，将智能体的执行功能置于一个基于规则的生产系统之中AndBotByrDouLebQin04 (https://arxiv.org/html/2607.15532#bib.bib7);LebAnd93 (https://arxiv.org/html/2607.15532#bib.bib89);New94 (https://arxiv.org/html/2607.15532#bib.bib105)。逻辑与优化在基于规则的环境中是天作之合。逻辑为表述规则及推导其结论提供了显而易见的框架，甚至可用于伦理评估KimHooDon21 (https://arxiv.org/html/2607.15532#bib.bib83)。而优化则作为一种强大的方法，用于计算逻辑推理以及对AI中使用的各种逻辑进行概念阐释。优化求解器——尤其是线性和整数规划求解器——不仅能推导出结论，还能提供推导过程的追溯，从而增强了基于规则AI天然具备的透明度。这些求解器多年来也取得了巨大进步。例如，一项研究指出，整数规划求解器在1989至2024年间将求解时间减少了五百万倍，这还不包括因硬件提速带来的改进Sol24 (https://arxiv.org/html/2607.15532#bib.bib121)。更为根本的是，我们将看到优化与逻辑推理实际上是同一基本问题的特例。

本文呈现了逻辑-优化合作的一些范例，这些合作与机器学习同步发展，并值得持续关注——尤其是在当今优化技术先进且重视透明度的背景下。我们首先讨论概率逻辑，它具有线性规划形式，可用现代列生成方法求解。我们还描述了各种扩展，包括贝叶斯逻辑（将概率逻辑与贝叶斯网络结合，并利用非线性规划）。我们也考察了信念逻辑，包括Dempster-Shafer理论及其变体，它们具有易于求解的线性规划形式。接着，我们讨论两种在AI中得到应用的非标准逻辑：缺省逻辑（非单调推理的一种）和多值逻辑。两者都受益于整数规划模型。

至此，我们转向从有噪声的数据中推断逻辑公式本身（而非仅推导其推论）。我们描述了一种布尔回归形式，它可通过整数规划进行校准，并能衡量统计显著性。然后，我们深入探讨上述逻辑与优化之间的根本联系，指出两者本质上都提出了一个投影问题。我们展示了如何将一种近期发展出的优化方法——基于逻辑的Benders分解——应用于表示为二叉决策图的知识库，从而解决该问题。

接下来，我们具体阐述三种优化方法可以提供追溯的方式，这些追溯有望增强AI的透明度。其一是经典的线性规划灵敏度分析，另外两种是基于推理和基于BDD的整数规划后最优性分析。随后，我们将缺省逻辑、基于逻辑的Benders分解与后最优性分析相结合，以说明优化在模理论答案集编程中的核心作用。最后，我们提出一些可能的未来研究方向。

全文重点在于传达基本思想及其动机，而非提供完整的技术描述。具体细节可在所引参考文献中找到，这些文献涵盖了本文讨论的方法及后续进展。

## 2 概率逻辑

尽管乔治·布尔最广为人知的是他在命题逻辑方面的工作，但他认为概率逻辑Boo1854 (https://arxiv.org/html/2607.15532#bib.bib22)才是自己最重要的贡献。它确实展现了惊人的原创性。尽管被遗忘了超过一个世纪，但它对今天的人工智能项目高度相关。它允许我们确定：当只有某些概率已知的命题时，可以以多大的置信度从中得出推论。HailperinHai76 (https://arxiv.org/html/2607.15532#bib.bib61)在1976年指出，布尔的概率逻辑可以建模为线性规划问题。在Hailperin的工作十年后，Nilsson在AI文献中独立发表了类似的模型Nil86 (https://arxiv.org/html/2607.15532#bib.bib109)。他的论文引发了一系列后续贡献，其中许多在ChaHoo99 (https://arxiv.org/html/2607.15532#bib.bib31);HanJau00 (https://arxiv.org/html/2607.15532#bib.bib62);KliPar11 (https://arxiv.org/html/2607.15532#bib.bib86)中有综述。

我们首先描述布尔的概率逻辑及其线性规划模型。我们将展示列生成这一著名技术如何处理模型中指数级数量的变量。然后，我们在不牺牲线性性的前提下引入二阶概率。条件独立性假设会引入非线性约束，但我们指出如何通过利用贝叶斯网络的结构来一定程度上缓解由此带来的计算挑战。

### 2.1 基本模型

概率逻辑最好通过一个例子来解释ChaHoo99 (https://arxiv.org/html/2607.15532#bib.bib31)。假设三个逻辑命题的概率给定如下：

Pr\(x1\)=0.9                              (1)
Pr\(x1⊃x2\)=0.8                           (2)
Pr\(x2⊃x3\)=0.7                           (3)

我们还给定条件概率

Pr\(x1|x2,x3\)=Pr\(x1,x2,x3\)Pr\(x2,x3\)=0.8                                      (4)

注意，Pr\(x1⊃x2\)不是条件概率Pr\(x2|x1\)，而是实质蕴含x1⊃x2的概率，等价于¬x1∨x2。我们希望确定能够以多大的概率推断x3。布尔观察到，我们无法推导出x3的精确概率，但可以推导出它的概率位于某个区间内。

在概率逻辑中，x=\(x1,x2,x3\)的每种真值赋值都被视为一个“可能世界”（0和1分别对应假和真）。每个可能世界x都有一个初始未知的概率px。例如，p000是\(x1,x2,x3\)=\(0,0,0\)的世界的概率，类似地有p001,...,p111。于是，命题x1的概率0.9对应于p100+p101+p110+p111（因为x1在这些可能世界中为真），命题x1⊃x2和x2⊃x3同理。

概率赋值 (1)–(3) 可以写作线性方程：

p100+p101+p110+p111=0.9                   (5)
p000+p001+p010+p011+p110+p111=0.8        (6)
p000+p001+p011+p100+p101+p111=0.7        (7)

条件概率赋值 (4) 可以线性化为：

Pr\(x1,x2,x3\)=0.8 Pr\(x2,x3\)

因此写作：

p111−0.8\(p011+p111\)=0                  (8)

现在我们可以推导x3的概率的可能取值范围，它等于：

p001+p011+p101+p111                      (9)

x3概率的严格上界是 (9) 在约束 (5)–(8) 以及归一化和非负性约束下的最大值：

p000+p001+p010+p011+p100+p101+p110+p111=1   (10)
p000,...,p111≥0                          (11)

这是一个线性规划问题，最大值为0.7。x3概率的严格下界是 (9) 在这些约束下的最小值，为0.5。因此x3的概率必须位于区间 [0.5, 0.7] 内。由于约束定义的可行集是凸的，该区间内的每一个概率都与赋值 (5)–(8) 一致。

一般地，概率推理问题是：

min/max { c⊺p | Ap=π, Bp=0, 1⊺p=1, p≥0 }            (12)

其中约束 Ap=π 指定范畴概率，Bp=0 指定条件概率，而1=\(1,1,...,1\)。如果 (12) 没有可行解，则概率赋值不可满足。

示例问题在这种形式下为：

min/max { [0 1 0 1 0 1 0 1]p | 
\[00001111 11110011 11011101\]p = \[0.9 0.8 0.7\]
\[0 0 0 -0.8 0 0 0 0.2\]p = 0
\[1 1 1 1 1 1 1 1\]p = 1, p ≥ 0 }          (13)

其中p=\(p000,...,p111\)。如有需要，可以在 (12) 中指定概率范围而非点值，同时保持问题的线性结构。

### 2.2 列生成

问题 (12) 的一个困难在于它包含 2^n 个变量，其中 n 是原子命题 xi 的个数。有人可能认为这使问题在计算上难以处理，Nilsson 在Nil93 (https://arxiv.org/html/2607.15532#bib.bib110)中也有类似暗示。然而，优化领域熟知的求解技术——列生成，正是为这种情况设计的。它允许我们通过单纯形法求解问题，同时只生成矩阵 A 和 B 中一小部分列，从而只使用 p 中一小部分变量。列生成可以很容易地应用于概率逻辑，如Bru88 (https://arxiv.org/html/2607.15532#bib.bib27);GeoKavPap88 (https://arxiv.org/html/2607.15532#bib.bib54);Hoo88a (https://arxiv.org/html/2607.15532#bib.bib64);JauHanAra91 (https://arxiv.org/html/2607.15532#bib.bib75);KavPap90 (https://arxiv.org/html/2607.15532#bib.bib82)中最初观察到的。

它从 (12) 的一个限制版本开始，其中 A 和 B 只包含少量列。它将对偶变量 u、v 和 α 分别与约束 Ap=π、Bp=0 和 1⊺p=1 相关联。这些对偶变量在单纯形法过程中计算得出，用于计算每个变量 pj 的简约成本：

cj − u⊺Aj − v⊺Bj − α                        (14)

其中 (cj, Aj, Bj, 1) 是 (c⊺, A, B, 1⊺) 中对应于 pj 的列。假设我们正在求解最小化问题，单纯形法的每次迭代会选择一个新的列 (cj, Aj, Bj, 1)，其简约成本为负，将其纳入问题（如果求解最大化问题，则需要正的简约成本）。如果不存在这样的列，则已找到最优解，此时 (c⊺, A, B, 1⊺) 中很可能只有一小部分列被选中。

寻找具有负简约成本的 pj 的问题——即定价问题——可以通过在所有列 j 上最小化 (14) 来求解。定价问题的性质最好通过例子来说明。(c⊺, A, B, 1⊺) 的一列可以表示为