Software Science (SwS) Research Publications


2017 2013 2012 2011 2010 2009 2008

Reports

J. Kwisthout. Two new notions of abduction in Bayesian networks. Technical report: ICIS-R10005, November, Radboud University Nijmegen, 2010.

Most Probable Explanation and (Partial) MAP are well-known problems in Bayesian networks that correspond to Bayesian or probabilistic inference of the most probable explanation of observed phenomena, given full or partial evidence. These problems have been studied extensively, both from a knowledge-engineering starting point (see [15] for an overview) as well as a complexity-theoretic point of view (see [13] for an overview). Algorithms, both exact and approximate, are studied in e.g. [21, 25, 19, 28]. In this paper, we introduce two new notions of abduction-like problems in Bayesian networks, motivated from cognitive science, namely the problem of fi nding the most simple and the most informative explanation for a set of variables, given evidence. We de fine and motivate these problems, show that these problems are computationally intractable in general, but become tractable when some particular constraints are met.

[ PDF ] [ Bibtex ]

J. Kwisthout. Most Probable Explanations in Bayesian Networks: complexity and tractability. Technical report: ICIS-R10001, March, Radboud University Nijmegen, 2010.

An overview is given of definitions and complexity results of a number of variants of the problem of probabilistic inference to the most probable explanation of a set of hypotheses given observed phenomana.

[ PDF ] [ Bibtex ]