AAAI Publications, Twenty-First International Joint Conference on Artificial Intelligence

Font Size: 
Variable and Value Ordering for MPE Search
Sajjad Ahmed Siddiqi, Jinbo Huang

Last modified: 2009-06-26


In Bayesian networks, a most probable explanation (MPE) is a most likely instantiation of all network variables given a piece of evidence. Solving (the decision version of) an MPE query is NP-hard. Recent work proposed a branch-and-bound search algorithm that finds exact solutions to MPE queries, where bounds are computed on a relaxed network obtained by a technique known as node splitting. In this work we study the impact of variable and value ordering on such a search algorithm. We study several heuristics based on the entropies of variables and on the notion of  nogoods, and propose a new meta-heuristic that combines their strengths. Experiments indicate that search efficiency is significantly improved, allowing many hard problems to be solved for the first time.


Bayesian Networks, Probabilistic Reasoning, Approximate Compilation, Exact Inference

Full Text: PDF