Overview
This paper introduces two novel schemes for calculating upper bounds on the Constrained Most Probable Explanation (CMPE) task, a complex optimization problem in probabilistic graphical models. By leveraging Lagrangian relaxation and decomposition, the authors transform the difficult CMPE problem into more manageable sub-problems—either unconstrained MPE or Multi-Choice Knapsack Problems. This enables faster and more accurate heuristic solutions for applications like Explainable AI (XAI) and adversarial robustness.
What Problem Does This Paper Address?
In probabilistic graphical models (PGMs), the Most Probable Explanation (MPE) task asks: "What is the most likely state of all variables given some evidence?" While MPE is NP-hard in general, it is often solvable in practice for models with low treewidth.
However, many real-world applications require a constrained version of this task (CMPE). For example, in Explainable AI, you might want the most likely explanation that also satisfies a specific budget or decision constraint.
Adding this global constraint makes the problem significantly harder. It remains NP-hard even on "easy" models where standard MPE can be solved in linear time. Existing solvers like Mixed Integer Linear Programming (MILP) struggle because the global constraint is "dense"—it affects all variables simultaneously, breaking the local structure that solvers usually exploit to find efficient solutions.
Methods
The authors propose two main strategies to "relax" the problem and find upper bounds. Both methods utilize an i-bound parameter, which allows researchers to trade off computational complexity (memory and time) for the quality of the bound.
1. UB-MPE (Lagrangian Relaxation)
This approach moves the global constraint into the objective function using a Lagrange multiplier ($\lambda$). This transforms the CMPE task into a standard, unconstrained MPE task. The algorithm iteratively updates $\lambda$ using sub-gradient descent to find the tightest possible upper bound.
2. UB-KP (Lagrangian Decomposition)
This approach duplicates variables to "break" the dependencies in the graph. By relaxing the requirement that these duplicates must be equal, the problem decomposes into a Multi-Choice Knapsack Problem (MCKP). MCKPs are well-studied and can be solved efficiently using specialized algorithms like the Dyer-Zemel algorithm.
Datasets and Evaluation
The authors evaluated their methods across three distinct problem types:
- Tractable Models: Cutset networks learned from four high-dimensional datasets (AD, BBC, Book, and Reuters).
- Intractable Models: High-treewidth benchmarks from the UAI competitions, including Segmentation, Grids, Promedas (medical diagnosis), and Pedigree (genetic linkage).
- Adversarial Robustness: The MNIST handwritten digit dataset, where CMPE was used to find the minimal pixel changes needed to flip a classifier's decision.
Key Insights and Results
- The "Hardness" Gap: CMPE is fundamentally more difficult than MPE because the global constraint couples all variables, preventing the usual "divide and conquer" approach of variable elimination.
- Algorithm Complementarity: There is no one-size-fits-all solution. The UB-MPE approach is superior when the underlying model is tractable or when the user can afford a large i-bound (yielding nearly exact bounds very quickly on cutset networks). Conversely, the UB-KP approach yields better bounds when memory is strictly limited (small i-bound).
- Tighter Bounds on Intractable Models: For complex UAI benchmarks, the Join Graph (JG) and Knapsack (KP) versions provided significantly tighter upper bounds than simpler mini-bucket methods. On the "Grids" dataset, for instance, the bounds were often an order of magnitude tighter.
- Adversarial Attacks and XAI: The authors demonstrate that CMPE is a powerful tool for "Decision Preserving Explanations." By framing adversarial perturbations as a CMPE problem on MNIST, they successfully identified the most important pixels for changing a classifier's decision. Using a "grid model" for distance (which considers spatial pixel relationships) resulted in much smoother and more visually coherent adversarial examples than a simple univariate model.
Limitations and Future Work
- Model Restrictions: The current framework is designed for discrete variables and multi-linear classifiers (like PGMs or linear SVMs). It cannot be directly applied to non-linear models like deep neural networks without first creating linear or high-treewidth approximations.
- Convergence Speed: The UB-KP approach, while providing tight bounds at low memory, requires significantly more time to converge compared to UB-MPE.
- Future Directions: The authors suggest extending this work to handle multiple global constraints and exploring direct applications in non-linear models.
Summary updated