Research map / Learning theory and algorithms / Combinatorial and search optimization
Novel Upper Bounds for the Constrained Most Probable Explanation Task
Tahrima Rahman, Sara Rouhani, Vibhav Giridhar Gogate
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MPE-based bound (MB) instead of MCKP-based bound (KP) on tractable cutset networks | MB · Cutset networks (AD q20) | upper bound: -3307.8 -> -3308.3 | Improved |
| Use MB instead of KP on cutset network Reuters | MB · Reuters q50 | upper bound: -1431.6 -> -1443.5 | Improved |
| Use KP/JG instead of MB/MM on high-treewidth UAI networks at i-bound 2 | KP · Segmentation q20 | upper bound: -381.7 -> -459.9 | Improved |
| Use KP/JG instead of MB on Grids at i-bound 2 | KP · Grids q20 | upper bound: 1370.4 -> 821.4 | Improved |
| Use KP/JG instead of MB/MM on UAI networks | KP and JG · UAI networks | computation time: 1 -> 430 | Hurt |
| Increase i-bound from 2 to 10 (ablation) | MB · Segmentation q20 | upper bound: -381.7 -> -452.7 | Improved |
| Increase i-bound from 2 to 10 (ablation) | MM · Grids q20 | upper bound: 1040.8 -> 824.1 | Improved |
| Increase i-bound from 2 to 10 (ablation) | KP · Segmentation q20 | upper bound: -459.9 -> -460.0 | No clear effect |
| Use MM instead of MB at same i-bound | MM · Grids q20 iB=2 | upper bound: 1370.4 -> 1040.8 | Improved |
| Increase i-bound from 2 to 4 on MNIST grid model (ablation) | MB · MNIST grid model | average upper bound: 291.42 -> 290.79 | Improved |
| Use JG instead of MB on MNIST grid model | JG · MNIST grid model | average upper bound: 291.42 -> 290.11 | Improved |
| Use grid distance model instead of univariate distance model | Grid model · MNIST adversarial | perturbation smoothness | Improved |
Closest papers by meaning
- A Novel Approach for Constrained Optimization in Graphical Models (NeurIPS 2020 · similarity 0.87)
- A Neural Network Approach for Efficiently Answering Most Probable Explanation Queries in Probabilistic Models (NeurIPS 2024 · similarity 0.86)
- Computing Probabilistic Explanations for ML Models: Fixed-Parameter Algorithms (AAAI 2026 · similarity 0.85)
- Learning to Condition: A Neural Heuristic for Scalable MPE Inference (NeurIPS 2025 · similarity 0.85)
- Sequential Probability Assignment with Contexts: Minimax Regret, Contextual Shtarkov Sums, and Contextual Normalized Maximum Likelihood (NeurIPS 2024 · similarity 0.83)
- Decomposing Constraint Networks for Calculating c-Representations (AAAI 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
