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:
- 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.
- 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.
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.
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