Efficient computation of jointree bounds for systematic MAP search

摘要: The MAP (maximum a posteriori assignment) problem in Bayesian networks is the of finding most probable instantiation set variables given partial evidence for remaining variables. state-of-the-art exact solution method depth-first branch-and-bound search using dynamic variable ordering and jointree upper bound proposed by Park Darwiche [2003]. Since almost all time spent computing bounds, we introduce an efficient these bounds incrementally. We point out that, static ordering, it only necessary to compute relevant at each step, also possible cache potentials backtracking. computation typically produces joint configurations groups variables, our instantiates multiple instead single variable, order reduce number times that need be computed. Experiments show this approach leads orders magnitude reduction time.