On the Robustness of Most Probable Explanations
Hei Chan, Adnan Darwiche
Abstract:
In Bayesian networks, a Most Probable Explanation (MPE) is a complete variable instantiation with a highest probability given the current evidence. In this paper, we discuss the problem of finding robustness conditions of the MPE under single parameter changes. Specifically, we ask the question: How much change in a single network parameter can we afford to apply while keeping the MPE unchanged? We will describe a procedure, which is the first of its kind, that computes this answer for each parameter in the Bayesian network variable in time O(n exp(w)), where n is the number of network variables and w is its treewidth.
Keywords:
Pages: 6371
PS Link:
PDF Link: /papers/06/p63chan.pdf
BibTex:
@INPROCEEDINGS{Chan06,
AUTHOR = "Hei Chan
and Adnan Darwiche",
TITLE = "On the Robustness of Most Probable Explanations",
BOOKTITLE = "Proceedings of the TwentySecond Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI06)",
PUBLISHER = "AUAI Press",
ADDRESS = "Arlington, Virginia",
YEAR = "2006",
PAGES = "6371"
}

