💻 computer science

Query Languages for Machine-Learning Models

本文探讨了将带有求和运算的一阶逻辑（FO(SUM)）及其递归扩展 IFP(SUM) 作为表示为加权图的神经网络的查询语言的应用，并提供了说明性示例，同时分析了它们的表达能力与计算复杂度。

原作者： Martin Grohe

发布于 2026-01-15

📖 1 分钟阅读☕ 轻松阅读

原作者： Martin Grohe

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下你拥有一个庞大且复杂的机器学习模型，比如一个神经网络。对于计算机科学家来说，这是一个“加权图”——由节点（神经元）和连接它们的线（边）组成的网络，每条线上都附带一个特定的数值（权重）。

这篇论文的作者 Martin Grohe 提出了一个简单但深刻的问题：我们如何向这些机器提问？

通常情况下，我们只是将数据输入神经网络并获得答案。但如果我们想问：“这个网络有多少条连接？”或者“如果我移除这根特定的导线，答案会改变吗？”或者“这个网络的输出曲线下的总面积是多少？”

为了回答这些问题，该论文提出了两种专门用于与这些加权机器进行交流的特殊“语言”（逻辑）。把这些语言想象成一种专门为神经网络设计的新型遥控器。

以下是这两种语言及其功能的拆解，使用了简单的类比：

1. 第一种语言：FO(SUM)

“计数与求和”遥控器

把 FO(SUM) 想象成一个非常聪明的计算器，它可以观察网络并执行两个主要任务：

观察周围： 它能够检查是否存在某种连接（比如询问：“节点 A 和节点 B 之间是否有导线？”）。
累加事物： 它有一个特殊的“求和（Sum）”按钮。它可以找到一组事物（比如网络中所有的三角形），并将它们的权重相加。

它的功能：

计数： 它可以准确告诉你网络中存在多少条边（导线）或多少个三角形。
寻找最优： 它可以找到网络中最“轻”或最“重”的三角形。
模拟简单网络： 如果神经网络很浅（深度不高），这种语言实际上可以计算出网络针对特定输入的输出。这就像是在模拟一段很短的多米诺骨牌链。
寻找“无用”导线： 它可以识别出哪些导线如果被移除，不会改变最终结果。

代价（局限性）：
FO(SUM) 就像是一个一次只能观察一个小范围邻里的观察者。它在处理深层网络时会感到吃力。如果神经网络有很多层（即一个非常长的多米诺骨牌链），这种语言就会迷失方向。因为它缺乏一种在深入过程中进行“循环”或“记忆”步骤的方法，所以它无法轻易计算极深网络的最终结果。

2. 第二种语言：IFP(SUM)

“递归式”遥控器

为了处理深层网络，我们需要一个更强大的工具。于是有了 IFP(SUM)。

你可以把它看作是带有“循环”按钮的第一种语言。在计算机术语中，这被称为“不动点（fixed-point）”算子。它允许这种语言表达：“持续进行这项计算，将上一步的结果作为下一步的输入，直到到达终点为止。”

它的功能：

处理任何深度： 因为它可以循环，所以它可以模拟神经网络的计算，无论其深度或复杂度如何。它可以追踪信号从第一个输入一直到最终输出的过程。
复杂的数学运算： 它可以执行评估网络函数所需的繁重计算工作。

代价（局限性）：
虽然 IFP(SUM) 功能强大，但它有一个速度限制。

“爆炸”问题： 如果你不小心，它计算出的数字可能会变得天文数字般巨大（比如不断地对一个数进行平方运算）。为了解决这个问题，论文引入了一个“安全”版本，称为 sIFP(SUM)，它可以防止数字增长过快，从而确保计算能在合理的时间内完成。
并非万能： 即便有了这个强大的遥控器，仍有一些问题是它无法回答的。例如，询问“是否存在任何输入能让这个网络的输出为非零值？”这类问题对于这种语言来说过于复杂，以至于它无法高效地解决，尽管人类理论上可以通过足够的时间来搞清楚。

大局观：“模型无关”的问题

论文还讨论了一种特殊的类型，叫做**“模型无关（Model-Agnostic）”**。

假设你有两个不同的神经网络，网络 A 和 网络 B。它们的构建方式不同（神经元数量不同、导线不同），但它们执行的任务完全相同（对于每个输入都会给出相同的答案）。

模型无关型问题是指答案仅取决于网络所执行的“任务”，而不取决于它是“如何构建”的。
- 例子： “这个网络是否对所有输入都输出零？”（如果 A 和 B 执行相同的任务，那么这个结论对两者都成立）。
**非无关（模型相关）**型问题则取决于具体的布线。
- 例子： “这个网络有多少根导线？”（即使 A 和 B 执行相同的任务，网络 A 可能有 100 根导线，而网络 B 可能只有 50 根）。

意外的发现：
论文揭示了一个令人失望但重要的事实：

FO(SUM)（这种简单的语言）在询问通用网络的“模型无关”问题方面表现糟糕。它只能询问一些琐碎的事物（比如“网络是否为空？”）。除非网络非常浅，否则它无法判断网络是否“始终为零”。
IFP(SUM)（这种强大的语言）表现更好，但它也有极限。有些关于网络“做了什么”的问题极其复杂，以至于即使是这种强大的语言也无法高效地表达它们。

总结

这篇论文关于构建一套用于与神经网络对话的词典和语法。

FO(SUM) 是一个基础词典，擅长计数和简单的求和，但在处理深层网络时会迷失。
IFP(SUM) 是一个带有“循环”功能的词典，可以处理深层网络，但它有速度限制，且仍然无法回答所有关于网络行为的问题。

作者总结道，虽然我们在创建这些语言方面取得了进展，但关于我们究竟能通过“提问”让神经网络揭示多少其内部运作机制的奥秘，仍然存在许多未解之谜。

技术摘要：机器学习模型的查询语言

问题陈述

本文探讨了对机器学习（ML）模型（特别是神经网络）进行形式化分析与查询的挑战。神经网络本质上是“混合模型”，结合了离散结构（图拓扑）与连续数值组件（权重与偏置）。虽然有限模型理论已成功应用于分析关系数据库和离散计算问题，但标准逻辑缺乏处理描述加权结构（如神经网络）时所需的数值聚合与算术机制。

现有的机器学习分析方法通常依赖于固定的、通用的解释方法（例如针对特定输入的反事实解释），或将模型视为黑盒。作者主张采用一种根植于数据库理论和有限模型理论的视角，提出应将机器学习模型视为受灵活逻辑查询约束的数据结构。这使得研究局部组件功能性以及全局语义属性（例如鲁棒性、正确性或函数空间的积分）成为可能，而不必局限于特定的输入评估。

研究方法

本文研究了两种专为加权有限结构（具有有限全集且权重函数映射至扩展实数集 $\mathbb{R}_\perp$ 的结构）设计的逻辑：

FO(SUM)： 扩展了求和算子 ( $\sum$ ) 和条件项的一阶逻辑。该逻辑允许在结构内的可定义集合上进行权重聚合。
IFP(SUM)： 使用增量固定点算子对 FO(SUM) 进行递归扩展。这使得定义归纳过程成为可能，对于评估无界深度的神经网络至关重要。

研究方法包括：

神经网络的形式化： 将前馈神经网络（FNN）表示为具有特定词汇（ $\{wt, bias, \le_{in}, \le_{out}\}$ ）的有向无环加权图。
定义语义： 在加权结构上建立这些逻辑的语义，其中项（terms）求值为 $\mathbb{R}_\perp$ 中的值，而公式（formulas）求值为布尔值。
表达能力分析： 确定哪些 FNN 的属性（例如评估、计数参数、寻找无用边、计算积分）可以通过这些逻辑进行表达。
复杂度分析： 分析执行这些查询的计算复杂度，同时考虑统一电路复杂度类（如 $\mathsf{TC}^0$ ）和多项式时间（ $\mathsf{P}$ ）。
模型无关查询： 研究其结果仅取决于网络所计算的函数 ( $f^N$ ) 而非特定架构或权重的查询，从而区分“模型无关”与“完全模型无关”的属性。

核心贡献与结果

1. FO(SUM) 的表达能力

有界深度评估： FO(SUM) 可以表达有界深度 FNN 的评估。该逻辑可以通过求和来聚合加权输入，并利用条件项来模拟 ReLU 激活函数，从而递归地定义节点在固定深度 $d$ 内的值。
全局属性： 该逻辑可以定义全局属性，如权重的总数、“无用”边集合（移除后不改变输出的边），以及通过网络计算出的函数的积分（通过分片线性函数的柱状胞分解实现）。
在无界深度上的局限性： FO(SUM) 无法表达无界深度 FNN 的评估函数。该逻辑局限于局部属性；它无法模拟通用 FNN 评估所需的无界递归。
模型无关性的局限： 一个核心的否定结果（定理 3.14）指出，在所有 FNN 类上具有模型无关性（在计算相同函数的不同架构下保持不变）的任何 FO(SUM) 语句都必须是平凡的（即要么对所有情况皆为真，要么对所有情况皆为假）。因此，对于无界深度，非平凡的模型无关查询（如检查网络是否处处输出为零）无法通过 FO(SUM) 表达。
有界深度等价性： 然而，对于有界深度 FNN ( $N_d(m, 1)$ )，FO(SUM) 的能力惊人。定理 3.18 证明，任何在由实数扩展的有序域上可由一阶逻辑表达的查询 ( $FO(\mathbb{R}_{lin}, f)$ ) 也可以在 FO(SUM) 中表达。这是通过通过函数的柱状分解中的胞（cells）上的量化来模拟对实数的量化实现的。

2. IFP(SUM) 的表达能力

无界深度： IFP(SUM) 通过引入固定点算子克服了 FO(SUM) 的深度限制。它可以表达无界深度 FNN 的评估函数（示例 4.1）。
复杂度与标量片段： 虽然标准固定点逻辑在有序结构上可以捕捉多项式时间，但 IFP(SUM) 在加权结构上面临着复杂度障碍：项的大小可能会呈指数级增长（例如，重复平方）。为了解决这个问题，本文引入了标量片段 sIFP(SUM)，它限制了涉及内含符号（intensional symbols）的乘法和除法。
- 定理 4.5： 在有理加权结构上，sIFP(SUM) 的数据复杂度属于 P（多项式时间）。
表达能力极限： 尽管在 Blum-Shub-Smale 模型中捕捉了多项式时间，但 IFP(SUM)（及 sIFP(SUM)）无法表达所有多项式时间可计算的模型无关查询。定理 4.7 表明，在 $N(1, 1)$ 上存在一个多项式时间可判定的模型无关查询，即使在二进制权重下也无法通过 IFP(SUM) 表达。这种局限性源于该逻辑无法对数值进行任意计算（缺乏对数字的变量范围控制）。
简化 FNN： 本文引入了“简化 FNN”（通过类似于双模拟性的等价关系进行分解）。定理 4.8 表明，对于其简化形式具有有界位宽（bit-size）权重的 FNN，sIFP(SUM) 能够捕捉所有多项式时间可判定的模型无关查询。

3. 复杂度结果

FO(SUM)： 评估 FO(SUM) 表达式的数据复杂度属于 统一 $\mathsf{TC}^0$ （定理 3.9）。此类允许阈值门和迭代加法，足以支持所需的算术运算。
sIFP(SUM)： 其数据复杂度属于 P（定理 4.5）。

意义与主张

本文将其定位为一种“个人观点”，也是将有限模型理论应用于机器学习的基础性步骤。其主要意义在于：

形式化机器学习查询： 它提供了一个严谨的逻辑框架，用于查询神经网络的内部语义，从黑盒评估转向结构化与功能性分析。
桥接离散与连续： 它展示了如何将元有限模型理论（将有限模型理论扩展到混合结构）应用于自然表示为加权图的神经网络。
定义表达能力的边界： 研究结果划定了逻辑表达能力的清晰界限。值得注意的是，它强调了虽然有界深度网络可以通过 FO(SUM) 进行逻辑分析，但无界深度引入了需要递归（IFP）的复杂性，且在模型无关属性方面仍面临根本性的表达障碍。
复杂度洞察： 该工作将逻辑表达能力与计算复杂度联系起来，表明即使使用固定点算子，要捕捉所有多项式时间模型无关属性，也需要对权重的数值位宽进行限制。

作者总结道，尽管在 [22, 23] 中已取得了显著进展，但仍有许多开放性问题，特别是关于将结果扩展到任意输入维度、在不依赖复杂度假设的情况下提升有界深度假设，以及不同聚合算子之间的互定义性问题。本文并不声称解决了“可解释人工智能”问题，而是提供了一个用于定义和分析特定类型解释与验证的理论工具包。