MAP Search in Bayesian Networks Using Joint Bounds

Contents

Maximum a Posteriori assignment (MAP) is the problem of finding the most probable instantiation of a set of variables in a Bayesian network given partial evidence for the remaining variables. The state-of-the-art exact solution method is branch-and-bound search using a jointree upper bound proposed by Park and Darwiche (2003). In this approach, almost all of the search time is due to computation of the bounds. We start with the observation that the bound computation typically produces what we call joint bounds, i.e., bounds for joint configurations of groups of variables. Based on this observation, we show how to improve search efficiency by instantiating multiple variables at each step of the search, instead of a single variable, which reduces the number of times an upper bound needs to be computed. We demonstrate the effectiveness of this approach in solving a range of benchmark Bayesian networks.