🤖 machine learning

Constraint-Anchored Attribution: Feasibility-Certified Counterfactuals and Bonferroni-PAC Sufficient Subsets for Neural CO Policies

本文提出了一种面向神经组合优化策略的约束锚定归因方法，该方法通过线性规划松弛对偶分解决策、利用组合可行性模型验证反事实，并借助邦费罗尼校正的 PAC 检验界定充分解释的规模，从而在多个问题领域中展现出显著高于代理梯度的准确性。

原作者： Sohaib Lafifi

发布于 2026-05-26

📖 1 分钟阅读☕ 轻松阅读

原作者： Sohaib Lafifi

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

想象一下，你拥有一个超级智能的机器人调度员，它负责规划配送路线或安排工厂作业。它极其擅长本职工作，常常胜过人类专家。但它是一个“黑箱”：当你问它“为什么先把卡车派到这家？”时，它只会回答“因为我的数学计算如此”。

本文介绍了一种打开这个黑箱的新方法，称为约束锚定归因（Constraint-Anchored Attribution, CAX）。可以把它想象成一个翻译器，将机器人复杂的数学运算转化为关于规则的故事，而不仅仅是数字。

以下是本文如何用三大工具来解释该系统：

1. “规则手册”翻译器（Λ-归因）

通常，当我们试图解释人工智能时，我们会关注单个输入（例如“到某家的距离”或“包裹的重量”）。本文认为，这就像把建筑物倒塌归咎于某一块砖，而实际上真正出问题的是地基或屋顶。

在这类问题中，决策是由规则族驱动的（例如：“不要超过卡车的载重”、“不要在下午 5 点后到达”、“不要行驶过远”）。

旧方法：审视每一个数字，猜测哪条规则起了作用。它经常出错，因为某些数字看起来更“响亮”（拥有更多数据），即使它们并非决策的真正原因。
新方法（CAX）：它查看“影子价格”（这是一个数学术语，指某条规则对解的挤压程度）。它会问：“目前哪一族规则受到的压力最大？”
结果：它能正确识别出决策是由“时间窗口”规则驱动的，而不仅仅是“距离”规则，即使距离数据量巨大。

2. “假如”现实核查（可行性认证反事实）

解释人工智能的一种常见方式是问：“做一点什么小改变会让机器人做出不同的选择？”

旧方法的问题：它们可能会建议：“如果包裹重 -50 公斤，机器人就会去别处。”这不可能！你不可能有负重量。这些“反事实”在数学上是成立的，但在物理上是荒谬的。
CAX 的解决方案：本文使用“可行性证书”。在接受任何解释之前，它会进行严格测试（就像安全检查员一样），确保“假如”的情景在现实世界中是真正可能的。
类比：想象你问：“你为什么走桥？”旧版 AI 会说：“因为如果你走隧道，你会撞车。”而 CAX AI 会说：“因为如果你走隧道，你会撞车，而且隧道实际上是开放且可通行的。”它过滤掉了不可能的情景。

3. “最小证据”测试（Bonferroni-PAC 子集）

有时，我们想知道：“机器人做出这个决策所需的最少信息量是多少？”

方法：本文使用一种统计技巧（Bonferroni 校正）来找出一个小节点组（例如路线上的几个特定房屋），如果你仅知道关于它们的信息，机器人仍会做出完全相同的选择。
结果：它证明机器人不需要查看整张地图；它只需要查看一个微小的、特定的 5 个地点的集群，就能有 95% 的把握做出其决策。这使得解释简短且聚焦。

大考：它奏效了吗？

作者在三个不同的问题上测试了该方法：

配送路线（CVRPTW）：具有时间窗口和载重限制的卡车。
奖品收集（OP）：在耗尽燃油前访问尽可能多的高价值地点。
工厂调度（FJSP）：将作业分配给不同的机器。

发现：

在配送路线上：旧方法（查看原始数字）的正确率仅为75%。新的 CAX 方法正确率达到了97%。它成功捕捉到了旧方法遗漏的“时间窗口”规则。
在奖品收集上：旧方法的正确率仅为35%。CAX 跃升至77%。
在工厂调度上：两种方法完全一致（100%）。这证实了该理论：当数据与规则完美对齐时，旧方法有效；但当它们变得混乱时，只有 CAX 能得出正确答案。

nutshell（一句话总结）

本文提供了一种解释复杂机器人决策的方法，通过：

按规则（而不仅仅是数字）对原因进行分组。
检查“假如”的故事在物理上是否可行。
找出证明决策所需的最小事实集。

它将令人困惑的数学输出转化为清晰、可信的关于机器人为何做出该选择的故事，确保解释基于游戏的实际规则，而不仅仅是统计噪声。

技术摘要：面向神经组合优化策略的约束锚定归因

问题陈述

用于组合优化（CO）的神经策略在解决路由和调度问题方面日益有效，但其决策过程仍然不透明。标准的可解释人工智能（XAI）方法，如基于梯度的特征归因（例如积分梯度 Integrated Gradients、DeepLIFT），在 CO 领域失效，因为它们作用于特征层面而非约束层面。CO 问题由约束族（例如容量、时间窗、优先关系）定义，这些约束通常跨越多个不同秩的特征张量。因此，即使高秩特征张量并不代表驱动决策的绑定约束，它们也可能累积过多的梯度质量，导致归因错位。

现有的特定于 CO 的解释器通常依赖于违反问题可行性的无约束反事实（例如负需求或反转的时间窗），或者针对静态代理模型而非神经策略的自回归解码过程。目前缺乏能够按约束族分解神经 CO 决策并提供形式化可行性保证的方法。

方法论：约束锚定归因（CAX）

本文提出了 CAX，这是一个包含三个原语的框架，将神经解释与底层优化结构联系起来：

1. $\Lambda$ -归因

该方法按约束族而非单个特征分解策略的决策梯度。对于步骤 $t$ 的决策 $a_t$ ，对约束族 $c_k$ 的归因计算如下：
$\Lambda_k(t) = \lambda^*_k(x) \cdot \sum_{i \in F(c_k)} \sum_j |\nabla_{x^{(i)}_j} \log \pi_\theta(a_t | s_t) \cdot x^{(i)}_j|$
其中， $\lambda^*_k$ 表示问题线性规划（LP）松弛中的拉格朗日乘子（对偶值），按族聚合。这种缩放确保归因反映约束的“绑定压力”。该框架支持三种后端来估计 $\lambda^*$ ：

LP：来自 LP 松弛的对偶值。
Subgrad：在松弛子问题上的拉格朗日子梯度上升。
Proxy：均匀加权（ $\lambda_k=1$ ），等同于约束划分的梯度 $\times$ 特征。

2. 邦费罗尼-PAC 充分子集

为了确定维持策略 argmax 决策所需的最小节点集，该方法调整了 Koriche 等人针对 CO 解码器的方法。它寻找最小的子集 $S$ ，使得策略在 Gaussian 扰动下保持其决策的概率至少为 $1-\epsilon$ 。

贪婪算法遍历归因排序，寻找最小的 $k$ ，使得经验保留率超过 $1-\epsilon$ 。
为了控制跨自适应查询（最多 $k_{max}$ ）的族错误率，对 Hoeffding 界应用邦费罗尼校正。这产生了一个样本量 $M_{bonf}$ ，保证沿贪婪排序具有 $(1-\delta)$ -PAC 界。

3. CSP 认证反事实（CF）

与最小化扰动范数但无可行性保证的标准 Wachter 式反事实不同，CAX 强制执行组合可行性证书。

过程：采样器生成扰动以翻转 argmax 决策。候选者首先经过算术检查（例如字段边界）。
认证：最佳候选者针对约束规划（CP）可行性决策模型（通过 CP-SAT 实现）进行验证。
裁决信号：在 CSP 认证的翻转扰动中携带最大 $L_1$ 质量的族，作为策略局部敏感性的真实信号。该信号对扰动范数（ $L_1, L_2, L_\infty$ ）和维度归一化具有不变性。

主要贡献

约束级分解：CAX 是首个利用 LP 松弛对偶值按约束族分解神经 CO 策略决策的方法，纠正了特征级归因固有的排名错位问题。
可行性认证反事实：它引入了一种反事实生成过程，通过 CSP 可行性决策模型严格遵循问题约束，使其区别于无约束的 XAI 方法。
PAC 充分子集：它提供了针对神经 CO 策略的充分解释子集大小的邦费罗尼校正、Hoeffding 控制界。
实证裁决：该框架利用 CF 导出的信号验证归因后端，证明当特征秩与绑定约束错位时，LP 对偶值能挽救归因精度。

实验结果

该框架在三个不同的 CO 问题上进行了评估：带时间窗的带容量车辆路径问题（CVRPTW）、定向问题（OP）和柔性作业车间调度问题（FJSP）。

与 CF 信号的一致性：
- CVRPTW：LP 锚定的 $\Lambda$ -归因在 96.5% 的案例中与 CF 导出的信号匹配（ $n_{cert}=344$ ），显著优于代理梯度（75.0%）。差异（+0.215）具有统计学显著性（McNemar $p \le 10^{-14}$ ）。
- OP：LP 锚定归因实现了 77.2% 的一致性（ $n_{cert}=281$ ），而代理为 35.2%（差异 +0.420， $p \le 10^{-14}$ ）。
- FJSP：在这个“秩对齐”机制中，高质量张量与绑定族匹配，LP 和代理后端在所有 59 个认证翻转中均实现了 100% 的一致性，证实了理论预测：当秩对齐时，LP 对偶值不提供额外信息。
可行性率：CSP 认证的反事实保持了高可行性。仅算术过滤就通过了 100% 的获胜者，而匹配的无约束基线仅通过了 19.3% 的候选者。
PAC 子集：在 CVRPTW 上，邦费罗尼校正的 PAC 子集平均每个步骤为 5.0 个节点（ $M=70, \epsilon=\delta=0.2$ ）。

意义与主张

本文主张 CAX 提供了一种严谨的、基于约束的神经 CO 策略解释方法。其主要意义在于证明：仅当特征张量秩与绑定约束族错位时，LP 对偶值才是准确归因所必需的。 当它们对齐时，较简单的方法就足够了；当它们错位时，特征级方法会失效，而 LP 锚定方法能恢复正确的约束级信号。

该框架的范围适度：它仅需一个可行性模型（此处实现为 CSP），并作为事后分析工具运行。它不声称解决完整的子集格优化问题（精确的 PAC 最优子集仍然是一个未解决的问题），但通过贪婪排序提供了一个保守的、认证的界。这项工作通过使用 CSP 认证的反事实作为裁决信号，建立了评估 CO 中 XAI 的新基准，超越了启发式特征重要性，转向基于约束的有效性。