A Complexity Map of Probabilistic Reasoning forNeurosymbolic Classification Techniques

神经符号分类技术的概率推理复杂性图谱

https://arxiv.org/pdf/2404.08404

摘要

神经符号人工智能（Neurosymbolic AI）是一个不断发展的研究领域，旨在将神经网络的学习能力与符号系统的推理能力相结合。其中，信息多标签分类是神经符号AI的一个子领域，研究如何利用先验知识来改进神经分类系统。近年来，基于概率推理的神经符号技术在信息分类中获得了广泛关注。然而，随着类别数量的增加，某些概率推理问题的难度可能会急剧增加，这取决于用于表示先验知识的语言。因此，评估这些技术的可扩展性时，概率推理的渐进复杂性至关重要。

在本文中，我们为四种概率推理问题开发了一个统一的形式化方法，并将已知的和新的可处理性结果整合到一个概率推理的复杂性地图中。我们基于这个复杂性地图，对几种技术的可扩展性领域进行了表征。我们希望这项工作能够帮助神经符号AI从业者更好地理解概率神经符号技术的可扩展性。

关键词：神经符号、概率推理、计算复杂性

1 引言

神经符号人工智能（NeSy AI）是一个不断发展的研究领域，旨在将神经网络的学习能力与符号系统的推理能力相结合。这种混合方式的具体形式取决于神经和符号组件如何相互作用。神经符号AI的一个重要子领域是信息机器学习，研究如何利用背景知识来改进神经系统。特别是，信息分类研究多标签分类任务，其中先验知识指定了哪些标签组合在语义上是有效的。

最近，一种特定的神经符号技术家族在文献中获得了广泛关注，它将神经网络的输出解释为输出变量上的独立概率，并利用概率推理来整合先验知识。为此，它们依赖于解决多个概率推理问题，例如计算命题理论被满足的概率（称为概率查询评估，PQE）或找到命题理论接受的最可能赋值（称为最可能解释，MPE）。

在这种情况下，概率推理的渐进复杂性对于评估这些技术在大规模分类任务上的可扩展性至关重要。特别是，我们希望了解当类别数量增加时，特定技术的复杂性将如何演变，因为多标签分类任务通常包含数千个类别（例如，ImageNet数据集包含1000个类别，当在WordNet层次结构中添加父类别时，最多可达1860个；Census Cars数据集包含2675个汽车类别；iNaturalist数据集包含5089个自然物种类别）。然而，该领域的大多数论文都关注性能指标，并使用复杂性问题尚未相关的玩具数据集（例如，[5]处理4×4网格中的简单路径、4个类别的偏好排序或像MNIST、Fashion-MNIST或Cifar-10这样的10个互斥类别的分类）。因此，计算复杂性问题很少在神经符号文献中被讨论。这可能导致对给定技术的计算限制产生误解。例如，[19]强调了现有神经符号技术在多数字MNIST加法任务上的可扩展性问题，并引入了一种近似方法来克服这些问题。随后，[20]表明，对任务的不同编码提供了一种线性时间（与数字数量成正比）的计算方案。我们相信，神经符号社区将从对概率推理的计算复杂性的系统研究中受益。我们希望这项工作能够填补这一空白。

概率推理的渐进复杂性取决于所处理问题的类型以及用于先验知识的表示语言。在本文中，我们绘制了一个概率推理的复杂性地图：我们为不同表示语言的多个概率推理问题提供了可处理性和不可处理性结果。特别是，我们专注于简洁语言，以保证神经符号技术在特定类型的先验知识上的可扩展性：层次化、基数化、简单路径和匹配约束。

最后，文献中大多数概率神经符号技术依赖于布尔电路片段（特别是分解否定范式DNNF或确定性分解否定范式d-DNNF）的知识编译来执行概率推理。我们讨论了这种方法的优势和局限性：特别是，我们表明DNNF及其片段并没有涵盖概率神经符号技术的全部可扩展性范围。

我们在第2节中介绍了图、知识表示语言、概率推理和神经符号技术的初步定义。我们在第3节中表征了概率神经符号技术可扩展性的条件。然后，我们在第4节中检查了知识编译的优势和局限性。最后，我们在第5节中分析了几种简洁语言的概率推理的渐进复杂性，这些语言代表了神经符号文献中常用的先验知识类型。我们的结果的完整证明可以在第6节中找到。我们在第7节中提到了相关工作，并在第8节中以可能的未来研究问题结束。

我们的贡献如下：首先，据我们所知，我们绘制了第一个包括计数、优化和枚举问题的概率推理复杂性地图。我们希望这项工作能够帮助神经符号AI从业者更好地理解概率神经符号技术的可扩展性。此外，我们将已知的简单路径和基数约束的PQE和MPE可处理性结果扩展到d-DNNF，并提供了高效的编译算法，这意味着EQE和ThreshEnum的可处理性。最后，我们表明匹配约束是MPE可处理的，但不能编译到DNNF：这表明将输入理论编译到DNNF、d-DNNF或其片段的主导趋势，并没有涵盖所有可处理性的情况。

2项准备工作

2.1图论

2.2 知识表示

知识表示语言有两个方面。语法定义了可以关于世界做出的可接受陈述。语义决定了陈述与状态之间的关系：它指定了在哪些状态下可以认为一个陈述为真或为假，或者反之，对于哪些陈述一个状态被认为是有效的。

布尔函数的知识表示语言来自不同的领域，并且通常是为了满足特定需求而设计的。例如，命题逻辑来自逻辑和SAT社区，布尔电路和决策图[21]来自知识表示和自动推理领域，而随机森林[22]、提升树[23]或二值化神经网络[24]来自机器学习领域。

为了提供一个统一的视角，我们提出了以下命题语言的定义，该定义受到了[25, 26]中工作的启发。

任何命题公式都可以通过按照标准优先级顺序读取公式，在线性时间内翻译成等价的布尔电路。因此，命题逻辑的常用片段（例如CNF、DNF等）可以翻译成布尔电路的片段。同样，决策图（如有序二进制决策图OBDD[28]）也对应于布尔电路的片段[29]。

基于图的语言
尽管它们通常不被视为命题语言，但通过将变量映射到图的元素，我们可以将布尔函数表示为满足特定属性的图的子结构集合。例如，我们利用这一点引入了SPath语言，它将变量映射到有向图的边，并表示形成图中完全简单路径的边的集合（更多细节见第5.3节），或者Match语言，它将变量映射到无向图的边，并表示形成图中匹配的边的集合（更多细节见第5.4节）。

基于图的理论的大小被视为其基础图的大小。与大多数传统命题语言不同，基于图的语言不是完备的（即它们不能表示任何布尔函数），而是专门用于某种特定类型的知识。然而，基于图的语言天然具有简洁性（即理论的大小与其变量数量呈多项式关系），因为图的大小最多是其节点或边数量的二次方。

2.3 概率推理
神经符号人工智能的一个挑战是弥合逻辑的离散性质与神经网络的连续性质之间的差距。概率推理可以通过允许我们对不确定的事实进行推理，为这两个领域之间提供接口。

推理
通常，当对随机变量的信念通过概率分布表达时，而新的信息以证据的形式（即变量的部分赋值）收集时，我们对两件事感兴趣：计算这种证据的概率，以及通过使用贝叶斯规则根据证据对分布进行条件化来更新我们的信念。概率推理允许我们在逻辑知识代替证据的情况下执行相同的操作。

执行这些操作或计算与条件分布相关的其他量构成了概率推理问题。我们在下面描述了几种概率推理问题，分为三种类型：计数问题、优化问题和枚举问题。表2列出了本文中用于推理问题的缩写列表。如第2.4节所示，解决这些问题构成了许多神经符号技术的核心。

枚举

将满足条件的状态按概率降序列出是一种称为排序枚举（RankedEnum）的枚举问题。一个与之密切相关的问题，我们称之为阈值枚举（ThreshEnum），它涉及列出概率高于给定阈值的满足状态集合。

2.4 概率神经符号技术

在有信息的分类（informed classification）的背景下，神经符号技术是一种将先验知识系统地整合到基于神经网络的分类系统中的方法。该领域的大多数论文假设神经模型的架构（例如，全连接的、卷积的、基于Transformer的等）主要取决于输入空间的模态（例如，图像、文本等），并开发了与模型无关的神经符号技术，这些技术在学习阶段、推理阶段或两者阶段整合先验知识，但将架构设计置于技术的范围之外。我们还考虑了用于共形分类（conformal classification）的神经符号技术，这些技术在非一致性度量（non-conformity measure）中以及在计算置信集（confidence set）时整合先验知识。

最近，概率神经符号技术（probabilistic neurosymbolic techniques）——一类利用概率推理将先验知识告知神经分类器的技术（见图3）——在文献中获得了显著的关注。我们在下面简要列举了文献中发现的主要概率神经符号技术。表3总结了每种技术所基于的概率推理问题。

3 可扩展性

如第2.4节所述，许多神经符号技术依赖于解决各种概率推理问题（即MPE、ThreshEnum、PQE或EQE）。因此，理解这些问题的计算复杂性对于评估这些技术在大规模分类任务中的可扩展性至关重要：ImageNet数据集[12]包含1,000个类别，当在WordNet层次结构[13]中添加父类别时，类别数可达1,860个；Census Cars数据集[14]包含2,675种汽车；iNaturalist数据集[15]包含5,089个自然物种类别。

大多数神经符号技术是使用通用知识表示语言定义的（例如，命题逻辑、布尔电路、线性规划等）。尽管使用一种完备语言来定义涵盖整个知识范围的技术是合理的，但它也错误地给人一种印象，即该技术会在整个知识范围内良好扩展，而事实并非如此，原因有两个：可处理性和简洁性。

首先，对于上述大多数通用语言，所有概率推理问题都是不可处理的：不存在多项式时间算法（相对于输入理论的大小）能够解决这些问题（除非P=NP）。幸运的是，这些语言中有一些完备的片段提供了MPE、ThreshEnum、PQE或EQE的可处理性，同时保持了完备性（见第4节）。不幸的是，这还不够，因为这些可处理的语言往往不够简洁。

事实上，尽管一种完备语言可以表示任何布尔函数，但它无法简洁地表示（即理论的大小与变量数量呈多项式关系）。这意味着表示布尔函数的最小理论的大小通常会随着变量数量呈指数增长。由于推理算法至少需要读取理论来进行计算，因此它无法在整个知识范围内扩展。这也意味着所有简洁语言本质上都是专门化的。需要注意的是，基于图的语言是天然简洁的：图的大小由其边数或顶点数（与变量集一一对应）多项式地界定。因此，在本文中，我们经常使用基于图的语言来表示完备语言的简洁片段。

这些观察结果导致了以下对可扩展性的定义。

定义3：我们说一种神经符号技术在给定的命题语言上是可扩展的，当且仅当该语言满足两个标准：

-简洁性：语言中的理论必须具有多项式大小（相对于其变量数量）。

-可处理性：该技术依赖的概率推理问题必须能够在理论大小的多项式时间内解决（对于计数和优化问题），或者在理论和输出的联合大小的多项式时间内解决（对于枚举问题）。

注释2：根据定义，神经符号技术无法在一种完备语言（这种语言无法做到简洁）上实现可扩展性，而只能在专门化的语言上实现可扩展性。此外，我们只关注了枚举问题的时间复杂度，但对于某些算法来说，空间复杂度可能会成为主要的限制因素。

4 知识编译

知识编译既有理论意义，也有实际意义。首先，如上所述，它简化了可处理性的证明，因为许多可处理性结果可以通过单一的高效编译属性推导出来。从实际角度来看，可以通过将编译算法与目标语言的算法组合，获得源语言的算法。此外，它使得尽可能多的计算可以在离线编译阶段完成，从而加速在线执行阶段所需的剩余计算（见第7节的编译复杂性）。这在概率神经符号技术的背景下特别有趣，其中先验知识被一次性离线编译为目标语言，并在在线阶段多次使用（每次学习步骤或测试样本一次）。此外，由于基于DNNF和d-DNNF的MPE、PQE和EQE算法在计算过程中严格遵循电路的结构，它们可以很容易地并行化以利用GPU的计算能力。最后，知识编译提供了一个超越渐近复杂性的实际复杂性度量：对于源语言（例如CNF）中的给定理论，编译后理论的大小决定了针对该特定理论的概率推理问题的计算时间，无论源语言是否可处理。

知识编译也有一些局限性，特别是在概率推理的背景下。首先，到目前为止识别出的两种主要目标语言（即DNNF和d-DNNF）在概率推理问题的可处理性方面并未涵盖全部范围：我们在第5.4节中通过匹配约束的案例展示了这一点，表明DNNF在MPE可处理性方面的局限性。此外，由于大多数现有的知识编译算法直接编译为d-DNNF（或其片段）[42–45]，它们无法利用DNNF和d-DNNF之间的简洁性差距，因此也无法利用MPE和PQE之间的复杂性差距。最后，由于算法在计算过程中遵循电路的结构，这意味着计算图无法适应推理问题中使用的特定概率，就像组合求解器为了加速计算所做的那样。实际上，组合求解器因此可能比依赖于布尔电路知识编译的算法更快。

5 复杂性图谱

在本节中，我们考察了几种简洁语言的可处理性。我们使用在第2.2节中定义的标准命题语言，并在本节中贯穿使用表1中的缩写。如前所述，识别一种可处理语言的典型标准是证明它可以被编译为具有有界树宽的CNF。然而，神经符号文献中常见的大多数类型的先验知识并不满足这一标准。因此，在本节中，我们分析了无界树宽的简洁语言的可处理性。

此外，计数问题通常比优化问题要困难得多[46]。因此，自然会寻找那些MPE可处理且PQE仍然为#P难的简洁语言。这些语言在概率神经符号技术的背景下具有重要意义，因为一些技术在这种语言上仍然可以扩展（例如，推理时的语义条件化），而其他技术则不能（例如，语义条件化和语义正则化）。

我们关于简洁语言可处理性的结果展示在图4所示的复杂性图谱中。随后，表4将图4与表??结合起来，后者总结了每种神经符号技术所依赖的概率推理问题，以确定哪些概率神经符号技术可以根据所考虑的任务类型（由其对应的简洁表示语言表征）实现可扩展性。

5.1 层次约束

层次约束在人工智能中无处不在，因为我们习惯于将概念组织成分类体系，以至于层次分类（即输出类别集以层次结构组织的分类任务）本身就是一个研究领域。

除了MPE，单调2-CNF上的ThreshEnum、PQE和EQE可以归约为负2-CNF（CNF的子片段，其中子句包含2个负文字）上的等价问题，而负2-CNF可以高效地编译为使用排除边的Hex理论。

Hex语言的另一个有趣的子片段，我们称之为排他层次结构（Exclusive-Hierarchical），由以下理论组成：一对变量是互斥的（即这两个变量之间存在一条排除边）当且仅当它们没有共同的后代（即无法通过层次边从这两个变量都到达某个顶点）。注意，排除边完全由层次边决定。因此，排他层次结构可以用与层次结构（H）相同的语法表示，但语义不同。在本节的其余部分，我们将使用这种表示方法。**树形排他层次结构（TreeExclusive-Hierarchical）**语言由排他层次结构理论 组成，其中 G 是一棵树。

命题4：树形排他层次结构是MPE、ThreshEnum、PQE和EQE可处理的。

简单路径约束在有信息的分类任务中（见示例5）或其他神经符号人工智能领域（例如，基于路线的强化学习[54]）经常遇到。

示例5（Warcraft最短路径）：Warcraft最短路径数据集使用从《Warcraft II》瓦片集中随机生成的地形图的图像。地图构建在一个12×12的有向网格上（每个顶点都连接到其所有邻居），网格的每个顶点对应瓦片集中的一个瓦片。每个瓦片是一个RGB图像，描绘了一种具有固定旅行成本的特定地形。对于每张地图，标签编码了从左上角到右下角的最短s-t路径，路径的权重是路径上所有地形（即网格顶点）的旅行成本之和。地形成本用于生成数据集，但在训练或推理过程中并未提供。该数据集已在文献中多次用于构建有信息的分类任务，以评估神经符号技术[6, 8, 33, 52]：关于任务的先验知识告诉我们，有效的标签必须对应于网格中的简单路径。

许多研究工作探讨了在无向图中简单路径约束的概率推理以及知识编译[55–57]。在本节中，我们分析了有向图中简单路径约束的概率推理的复杂性。特别是，我们表明图的无环性在概率推理的可处理性中起着关键作用。

命题7：SPath在MPE、ThreshEnum、PQE和EQE方面是不可处理的。

有趣的是，ThreshEnum可以归约为RankedEnum（只需按概率降序枚举状态，并在第一个超出概率阈值的状态处停止），这意味着Match是ThreshEnum可处理的。

最后，已知计算图的匹配数量是#P难的[51]。因此，由于MC可以归约为PQE和EQE，Match是PQE和EQE不可处理的。

8 结论

本文研究了基于概率推理的神经符号技术的可扩展性。在引入命题知识表示和概率推理的统一框架后，我们识别了若干神经符号技术所依赖的关键概率推理问题（即MPE、ThreshEnum、PQE和EQE）。我们通过将知识编译到d-DNNF，展示了对于有信息分类中流行的知识类型所代表的几种简洁语言的可处理性结果。然而，我们也指出了这种方法的局限性，特别是它无法利用优化/枚举问题（MPE/ThreshEnum）与计数问题（PQE/EQE）之间的复杂性差距。我们将已知结果和我们的新结果整合为第一张包含计数、优化和枚举问题的概率推理复杂性图谱。我们希望这项工作能够帮助神经符号人工智能从业者更好地了解概率神经符号技术的可扩展性。

我们未来的研究方向包括完善这张复杂性图谱，加入：其他表示语言、其他（概率）推理问题（例如边际MPE和PQE查询）、对复杂性差距的更深入理解以及对枚举问题空间复杂性的刻画。我们还希望探索概率推理的编译复杂性类和计数问题的近似算法：特别是，我们希望识别哪些表示语言属于Comp-P或Comp-#P，以及哪些语言为PQE和EQE提供了完全多项式时间近似方案（FPTAS）。最后，对概率神经符号技术的计算时间进行实际研究将是非常有意义的，以了解这些理论结果在实践中关于其可扩展性领域的信息性。

https://arxiv.org/pdf/2404.08404