Variable and Value Ordering for MPE Search
Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. Pages 1964-1968.
Abstract
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.Sajjad Ahmed Siddiqi, Jinbo Huang
@inproceedings{ijcai2009p324,
title = {Variable and Value Ordering for MPE Search},
author = {Siddiqi, Sajjad Ahmed and Huang, Jinbo},
booktitle = {Proceedings of the Twenty-First International Joint Conference on
Artificial Intelligence, {IJCAI-09}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Hiroaki Kitano},
pages = {1964--1968},
year = {2009},
url = {https://ijcai.org/proceedings/2009/324},
}
TY - CPAPER TI - Variable and Value Ordering for MPE Search AU - Siddiqi, Sajjad Ahmed AU - Huang, Jinbo T2 - Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, IJCAI-09 PB - International Joint Conferences on Artificial Intelligence PY - 2009 SP - 1964 EP - 1968 UR - https://ijcai.org/proceedings/2009/324 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
