Abstract
Finding the $m$ best solutions in graphical models is a critical task for applications where the single optimal solution may be unreliable due to noise or model incompleteness. This paper extends classic heuristic search paradigms—specifically A and Depth-First Branch and Bound—to this task. We provide the first formal proof that $m$-A maintains the desirable properties of standard A*, including soundness, completeness, and optimal efficiency. Furthermore, we adapt these algorithms to AND/OR search spaces to exploit conditional independence. Empirical evaluations across six diverse benchmarks demonstrate that these search-based methods are competitive with and often superior to existing iterative and dynamic programming approaches.
Introduction
In combinatorial optimization, the goal is typically to find the single "best" solution (e.g., the most likely explanation in a Bayesian network). However, in real-world applications such as genetic linkage analysis or medical diagnosis, the underlying data may be noisy or incomplete, making the single optimal solution unreliable. Finding the top $m$ solutions allows human experts to evaluate multiple plausible results or helps in approximating complex summation tasks. While algorithms for this "$m$-best" task existed, they often relied on redundant iterative schemes or memory-intensive inference methods. This paper provides a rigorous foundation for using heuristic search to find $m$ solutions efficiently.
Graphical Models and Search Spaces
Graphical models represent joint distributions or cost functions by exploiting local dependencies. The structure of the model, captured by its primal graph and induced width, dictates the complexity of inference.
To improve efficiency, search can be conducted over AND/OR search spaces, which decompose the problem into independent subproblems based on a pseudo tree. This reduction changes the search space size from exponential in the number of variables to exponential in the graph's induced width.
Proposed Methods
The authors introduce and analyze several algorithms:
- $m$-A*: An extension of the A* algorithm that continues until $m$ solutions are found. It allows a node to be expanded up to $m$ times to account for different paths.
- $m$-BB: A depth-first branch and bound variant that maintains a sorted list of the $m$ best solutions found so far, using the cost of the $m$-th best solution as a pruning bound.
- AND/OR Search Adaptation: These algorithms are adapted to AND/OR spaces to exploit conditional independence. At "AND" nodes, the algorithm must merge sets of $m$ partial solutions from independent subproblems.
- Mini-Bucket Heuristics: For problems where exact heuristics are too expensive, mini-bucket elimination provides lower bounds to guide the search.
Key Insights and Results
A significant theoretical contribution is the proof that $m$-A inherits the optimal efficiency of standard A. This means no other search algorithm using the same heuristic can find the $m$ best solutions by expanding fewer nodes (given a consistent heuristic).
Empirically, the algorithms were evaluated on six benchmarks, including genetic pedigrees, medical diagnostic systems (Promedas), and protein side-chain prediction. Key findings include:
- Worst-Case Champion: The hybrid BE+$m$-BF algorithm (Bucket Elimination followed by $m$-A*) has the best worst-case time complexity among known $m$-best algorithms.
- Memory vs. Robustness: While $m$-A* is generally faster, $m$-BB is far more robust for memory-intensive, high-width problems.
- Scalability: The runtime of these schemes scaled much better with $m$ than theoretical worst-case analysis suggested, making them practical for $m$ values up to 100 or more.
Conclusion and Future Work
Search-based methods provide a robust framework for the $m$-best task in graphical models. Future research will address the "merging bottleneck" at AND nodes and the development of more memory-efficient AND/OR best-first search variants.
Summary updated