为神经组合优化策略提供可验证的反事实解释与压缩解释集
Constraint-Anchored Attribution: Feasibility-Certified Counterfactuals and Bonferroni-PAC Sufficient Subsets for Neural CO Policies
- 基于线性规划对偶分解约束族影响，实现决策归因
- 反事实结果通过约束满足问题模型认证，准确率显著高于梯度代理方法
- 用贝叶斯校正的霍夫丁检验生成简洁解释集，适合高可靠性场景
我们提出一种针对神经组合优化（CO）策略的归因方法：(i) 通过线性规划松弛对偶分解决策在约束族上的贡献；(ii) 利用组合可行性模型（实现为约束满足问题可行性判定模型）认证反事实结果；(iii) 沿贪婪排序使用贝叶斯校正的霍夫丁检验，界定帕累托充分解释集的最大规模。在三个组合优化问题和三个随机种子下，我们的LP锚定Λ归因在带容量限制的车辆路径问题（CVRPTW，n_cert=344）上匹配反事实信号达96.5%，在旅行商路线问题（Orienteering Problem，n_cert=281）上达77.2%，优于代理梯度法（75.0%和35.2%），差异显著（配对差值+0.215和+0.420；麦克内马尔精确p≤10⁻¹⁴）。在灵活作业车间调度问题的秩对齐情形中，两种后端在所有经由CSP认证的翻转（n_cert=59）上一致，验证了无增益预测。贝叶斯-帕累托充分解释集平均每步仅需5.0个节点（M=70，ε=δ=0.2，k_max=25）。参考实现见：https://github.com/sohaibafifi/neuro-co-cax
原文摘要 · Abstract (English)
We give an attribution method for neural combinatorial-optimisation (CO) policies that (i) decomposes a decision by constraint families via LP-relaxation duals, (ii) certifies counterfactuals through a combinatorial feasibility model (implemented as a CSP feasibility-decision model), and (iii) bounds the size of a PAC-sufficient explanation with a Bonferroni-corrected Hoeffding sufficient-subset test along a greedy ordering. Across three CO problems and three seeds, our LP-anchored $Λ$-attribution matches the CF-derived signal at 96.5% on CVRPTW (n_cert=344) and 77.2% on the Orienteering Problem (n_cert=281) vs 75.0% and 35.2% for proxy gradient (paired diffs +0.215 and +0.420; McNemar exact $p \le 10^{-14}$). In the rank-aligned regime of the Flexible Job-Shop Scheduling Problem, both backends agree on every CSP-certified flip (n_cert=59), confirming the no-gain prediction. Bonferroni-PAC subsets average 5.0 nodes per step ($M=70$, $\varepsilon=δ=0.2$, $k_{\max}=25$). Reference implementation: https://github.com/sohaibafifi/neuro-co-cax
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。