On the Robustness of Most Probable Explanations

By Hei Chan, Adnan Darwiche. 2006

62 citations recorded by the source corpus.

In Bayesian networks, a Most Probable Explanation (MPE) is a complete variable instantiation with the 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 all parameters in the Bayesian network in time O(n exp(w)), where n is the number of network variables and w is its treewidth.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Explanation in Human-AI Systems: A Literature Meta-Review, Synopsis of Key Ideas and Publications, and Bibliography for Explainable AI (2019, neutral): “(Chajewska and Halpern, 1997; Chan and Darwiche, 2012; Chang, Gerrish, Wang, Boyd-Graber, and Blei, 2009; Doyle et al., 2003; Druzdzel, 1990, 1996a, 1996b; Druzdzel and Henrion, 1990; Eaves Jr and Shafto, 2016; Fox, Glasspool, Grecu, Modgil, South, and Patkar, 2007; Freuder, Likitvivatanavong, and…”
PAC-Bayesian Collective Stability (2014, background): “Chan and Darwiche (2006), Wainwright (2006) and Honorio (2011) analyzed the sensitivity of probabilistic graphical models to changes in parameters.”
Stability and Generalization in Structured Prediction (2016, methodology): “…probabilistic inference, sensitivity analysis has been used to determine the maximum amount one can perturb the model parameters (or evidence) such that the likelihood of a query stays within a given tolerance, or such that the most likely assignment does not change (Chan and Darwiche, 2005, 2006).”