Inference Schemes for M Best Solutions for Soft CSPs

Emma Rollon, Natalia Flerova and Rina Dechter

The paper present a formalization of the m-best task within the unifying framework of semirings. As a consequence, known inference algorithms are defined and their correctness and completeness for the m-best task are immediately implied. We also describe and analyze a Bucket Elimination algorithm for solving the m-best task, elim-m-opt, presented in an earlier workshop1 and introduce an extension to the mini-bucket framework, yielding a collection of bounds for each of the m-best solutions. Some empirical demonstration of the algorithms and their potential for approximations are provided.