Two New Notions of Abduction in Bayesian Networks
Johan Kwisthout · Radboud Repository (Radboud University) · 2010
Most Probable Explanation and (Partial) MAP are well-known problems in Bayesian networks that cor respond 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 knowledgeengineering starting point (see [10] for an overview) as well as a complexity-theoretic point of view (see [9] for an overview).Algorithms, both exact and approximate, are studied in e.g.[14,17,12,20].In this paper, we introduce two new notions of abduction-like problems in Bayesian networks, motivated from cognitive science, namely the problem of finding the most simple and the most informative explanation for a set of variables, given evidence.We define and motivate these problems, show that these problems are computationally intractable in general, but become tractable when some particular constraints are met.