Learning to Condition: A Neural Heuristic for Scalable MPE Inference¶

会议: NeurIPS 2025
arXiv: 2509.25217
代码: 无
领域: 概率推理 / 图模型
关键词: MPE推理, 概率图模型, 神经启发式, 条件化, 分支定界

一句话总结¶

提出 Learning to Condition (L2C)，通过训练注意力网络从求解器搜索轨迹中学习变量-值对的"最优性"与"简化性"双重评分，用于指导概率图模型中 MPE 推理的条件化决策，在高树宽模型上大幅缩减搜索空间且维持或提升解质量。

研究背景与动机¶

领域现状：Most Probable Explanation (MPE) 推理是概率图模型（PGM）中的核心任务，目标是在给定证据下找到未观测变量的最可能赋值。经典精确方法如 AND/OR 搜索、整数线性规划（ILP）虽能保证最优，但对高树宽模型计算成本极高。近似方法则牺牲解质量。

现有痛点：条件化（Conditioning）——即固定部分变量的值来降低推理复杂度——是加速推理的经典策略（如 cutset conditioning、递归条件化），但其效果高度依赖于变量选择和赋值顺序。现有方法要么依赖手工启发式（如最大度数），要么依靠计算昂贵的 full strong branching 进行逐步前瞻。

核心矛盾：哪些变量应被固定、固定为什么值、以什么顺序？固定错误变量会不可逆地排除最优解，不固定则丧失计算加速。理想情况需要同时满足"安全性"（保留最优解）和"有效性"（大幅降低求解开销），但这两个目标往往矛盾。

本文目标 (1) 如何自动学习哪些变量-值对同时满足最优性保持和推理简化？(2) 如何将这种学习策略集成到现有精确求解器中？

切入角度：L2C 观察到"解的歧义性"调节条件化风险——若某变量在所有最优解中取同一值，则固定它很安全但也最危险（估错则致命）；若变量值分布更均匀，则条件化风险更低。模型通过大量训练自适应学习这种权衡。

核心 idea：用神经网络从求解器搜索轨迹中学习变量-值对的双重评分（最优性 + 简化性），替代手工启发式指导条件化决策。

方法详解¶

整体框架¶

L2C 的 pipeline 分为两阶段：(1) 离线数据生成与训练——通过调用 oracle 求解器获取最优解和求解统计信息，构造监督数据集，训练注意力网络；(2) 在线推理——训练好的网络对所有变量-值对打分，通过贪心或束搜索选择高分赋值进行条件化，然后将简化后的问题交给精确求解器。

关键设计¶

可扩展的数据生成管道:
- 功能：从求解器搜索轨迹中提取训练信号
- 核心思路：对每个 PGM 实例，随机采样全赋值并划分查询集和证据集，调用 oracle 求解 MPE 获得最优解。然后对查询集中随机选取的 \(c_{max}\) 个变量，逐一固定并重新求解，记录运行时间、搜索节点数等统计量。最优解提供"最优性"标签（变量-值对是否在解中），求解统计量经 softmax 归一化后提供"简化性"排名标签
- 设计动机：避免枚举所有 MPE 解（不可行），通过采样 \(c_{max}\) 个变量控制计算开销，同时收集足够的监督信号
注意力双头架构:
- 功能：对每个变量-值对输出最优性分数和简化性分数
- 核心思路：每个变量-值对通过嵌入表获得向量表示，未观测变量的嵌入作为 query 通过多头注意力机制与证据变量嵌入交互，捕获变量间关联。上下文化嵌入经共享编码器后分别输入两个 MLP 头——最优性头（sigmoid）估计赋值出现在最优解中的概率，简化性头（softmax）估计赋值对推理简化的相对效用
- 设计动机：双头设计解耦了"保留最优解"和"降低求解开销"两个目标；注意力机制实现置换不变性和任意证据-查询分区的泛化
多任务损失与推理策略:
- 功能：联合优化两个目标并提供灵活的推理时集成方式
- 核心思路：总损失 \(\mathcal{L} = \lambda_{opt} \cdot \mathcal{L}_{opt} + \lambda_{rank} \cdot \mathcal{L}_{rank}\)，其中最优性用二元交叉熵，简化性用 list-ranking 交叉熵。推理时提供三种策略：贪心条件化（迭代选最优赋值）、束搜索（维护 \(W\) 条候选序列）、NN 引导 B&B（直接作为分支和节点选择启发式）
- 设计动机：排名损失比绝对值预测更鲁棒；多策略满足不同延迟/质量需求

实验关键数据¶

主实验¶

在 14 个高树宽二值 PGM（90~1444 变量）上评估，12 种配置（4个条件化深度 × 3个时间预算）。

方法	胜过无条件化 Oracle 的配置数	说明
L2C-Rank	几乎全部 12 配置	最一致
L2C-Opt	多数配置	仅用最优性头
Full Strong Branching	少数配置	偶尔改善
Graph heuristic	极少配置	最弱

消融实验（AOBB oracle，节点减少 vs 解质量）¶

条件化深度	L2C-Rank LL gap	L2C-Rank 节点减少	基线 LL gap
5%	≈0	40-60%	显著偏离
15%	≈0	60-80%	较大偏离
25%	≈0	70-90%	大幅退化

关键发现¶

L2C-Rank 在几乎所有配置下帮助 SCIP 找到更优解，且随条件化深度增加优势更显著
配合 AOBB 时，L2C 大幅减少搜索节点同时维持近最优解质量，基线方法质量快速退化
作为 B&B 分支/节点选择启发式，L2C 同样显著优于 SCIP 默认策略（热力图以绿色为主）

亮点与洞察¶

双任务评分设计非常巧妙：将条件化决策分解为正交的"最优性保持"和"推理简化"两个维度，比单一启发式更精细地权衡安全性与效率。这种思路可迁移到任何需要在质量和效率间做 trade-off 的搜索问题
learn-from-solver-traces 范式可复用：把求解器当 oracle 生成训练数据的策略可推广到 SAT、调度等组合优化问题
即插即用的集成方式：既可作为前处理简化问题，也可嵌入 B&B 内部引导搜索，灵活性很强

局限与展望¶

数据生成阶段需调用 oracle 求解器多次，对百万级变量模型可能不可行
仅验证了二值变量 PGM，多值变量泛化能力未测试
求解器信号仅用了运行时间和节点数，更丰富的信号（如 LP 边界变化、branch-and-cut 决策）可能进一步提升
每个 PGM 单独训练模型，跨图模型家族的迁移学习能力未探索

评分¶

新颖性: ⭐⭐⭐⭐ 双头评分 + 从求解器轨迹学习的范式有原创性
实验充分度: ⭐⭐⭐⭐ 14 个 PGM + 两种 oracle + 多种集成方式的系统评估
写作质量: ⭐⭐⭐⭐ 技术描述清晰，算法伪码完整
价值: ⭐⭐⭐⭐ 在高树宽 PGM 推理场景有实用价值，learn-from-solver 范式可推广