|

R177
M best solutions over Graphical Models

Natalia Flerova and Rina Dechter

Abstract
Bucket elimination is an algorithmic framework that generalizes dynamic programming to accommodate many problem-solving and reasoning tasks. In particular, it can be used for any combinatorial optimization task such as finding most probable configurations in a Bayesian network. In this paper we present a new algorithm elim-m-opt, extending bucket elimination for the task of finding m best solutions for an optimization task for any value of m. We formulate our algorithm using general notion of combination and marginalization operators and show that our approach is sound. We provide complexity analysis and compare it with related work. Potential extension to the mini-bucket framework and its impact on heuristic-search for m-best are discussed.

[pdf]