On the Robustness of Most Probable Explanations
This addresses robustness in Bayesian networks for applications like diagnosis or decision-making, but it is incremental as it builds on existing MPE concepts.
The paper tackles the problem of determining how much a single parameter in a Bayesian network can change without altering the Most Probable Explanation (MPE), and presents a procedure that computes this for each parameter in O(n exp(w)) time, where n is the number of variables and w is the treewidth.
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.