Automated explanation generation in graphical models

Explanation generation is an important and useful problem in automated reasoning. This thesis deals with the theoretical and practical issues involved in computing explanations in graphical models. Specifically, it deals with the problem of generating the Maximum a Posteriori Hypothesis (MAP), and a specialization of MAP known as the Most Probable Explanation (MPE). From a theoretical viewpoint, we analyze the complexity of producing explanations. For some classes it turns out to be very difficult. This hardness remains, even for classes of very simple models for which other inference tasks are tractable. Thus algorithms capable of producing good (though sometimes suboptimal) solutions efficiently are important. We give novel algorithms for approximating both MAP and MPE. While they provide no guarantee on the solution quality, in practice the performance seems to be quite good, and outperforms other previous algorithms. While approximations are useful, it is sometimes important to produce the optimal solution. We present a new MAP algorithm that is typically many orders of magnitude more efficient than previous techniques, and is the first algorithm capable of generating exact solutions for large real world models. We also introduce new theoretical and algorithmic results, which form the core of some of the approximation methods, but also have wider application. Specifically, we show how to extract additional information from jointree algorithms (the main class of algorithms for probabilistic inference), allowing them to directly answer more queries. We also introduce a novel jointree algorithm that improves the efficiency of computing such queries.