Pushing Forward Marginal MAP with Best-First Search

Radu Marinescu, Rina Dechter, Alexander T. IhlerIJCAI 2015 · OpenReview

Introduction

Marginal MAP (MMAP) is a notoriously difficult task in probabilistic graphical models, categorized as $NP^{PP}$-complete. Unlike standard MAP, which seeks the most likely configuration for all variables, or Marginalization, which sums them out, MMAP does both: it identifies the most likely assignment for a subset of "MAP variables" while summing out the remaining "sum variables."

The primary computational bottleneck in MMAP is that evaluating even a single candidate assignment for the MAP variables requires solving a complete summation problem to determine the marginal likelihood. Most existing solvers rely on Depth-First Branch and Bound (DFBnB), which often wastes significant resources evaluating mediocre assignments before finding a strong enough solution to enable effective pruning.

Methodology

This paper proposes a shift from traditional depth-first search to Best-First Search (BFS) strategies to explore the space of MAP assignments. By expanding nodes in order of their heuristic promise, BFS theoretically minimizes the number of nodes visited. The authors introduce two primary algorithms:

  1. AOBF-MMAP: A best-first search algorithm operating on an AND/OR search tree. This structure exploits the conditional independence of the graphical model to decompose the problem into smaller, independent sub-problems.
  2. RBFAOO-MMAP: A "Recursive Best-First" variant designed to address the memory limitations of standard BFS. It uses a local threshold control mechanism to operate within limited memory while retaining the efficiency of best-first exploration.
The primal graph (a) and its corresponding pseudo tree (b) illustrate how graphical models are decomposed to exploit conditional independence during search.

Both algorithms utilize Weighted Mini-Bucket (WMB) heuristics to guide the search. These heuristics provide an upper bound on the optimal value, allowing the search to focus on the most promising regions of the state space.

Experimental Setup

The algorithms were evaluated using benchmarks from the PASCAL2 Inference Challenge, including binary grid networks, medical diagnosis systems (Promedas), genetic linkage analysis (Pedigree), protein interaction models, and image segmentation tasks (Segbin). The researchers tested both structured "easy" instances and "hard" instances where MAP variables were selected randomly to challenge the solvers.

Results and Key Insights

The study reveals that BFS is uniquely suited for MMAP because it minimizes the number of "frontier" nodes—the points where the search transitions from MAP variables to Sum variables. Since these transitions represent the most expensive operations, BFS's mathematical guarantee to expand the minimum number of these nodes leads to significant efficiency gains.

Performance comparison on the or_chain_4.fg instance showing that RBFAOO-MMAP performs significantly fewer conditional likelihood evaluations than depth-first AOBB, especially at lower i-bounds.

Key findings include:

  • Orders of Magnitude Speedup: In many "hard" instances, RBFAOO-MMAP was 2 to 3 orders of magnitude faster than the state-of-the-art depth-first AOBB.
  • Heuristic Resilience: Best-first search maintains a massive performance lead even when heuristics are "weak" (computed with low memory/low $i$-bounds), making it more robust for complex problems where high-quality heuristics are too expensive to compute.
  • Solving the Unsolvable: The best-first approaches successfully solved several problem instances that were completely beyond the reach of previous methods within the standard one-hour time limit.

Conclusion and Future Work

While best-first search significantly optimizes the search for MAP variables, the summation sub-problems remain a bottleneck for graphs with high induced width. Future research directions include extending these algorithms into "anytime" solvers—which can provide increasingly better solutions if interrupted—and exploring the use of bounded approximations for summation sub-tasks to further accelerate the search process.

Summary updated

BibTeX
@inproceedings{marinescu2015pushing,
  author = {Radu Marinescu and Rina Dechter and Alexander T. Ihler},
  title = {{Pushing Forward Marginal MAP with Best-First Search}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
  url = {https://openreview.net/forum?id=BkWxEXfu-S},
}
Figure