Probabilistic Inference for Dynamic and Relational Models

Within the field of Artificial Intelligence, there is a lot of interest in combining probability and expressive representations for dealing with complex relational and dynamic domains. A common approach to reason with these representations is to rely on existing techniques for propositional models and thus requires to first ground the underlying model into a propositional representation. This strategy comes at a cost, however, as capturing the semantics of the original representation might lead to a combinatorial explosion and quickly renders inference intractable. This dissertation investigates how weighted model counting and knowledge compilation can be used to directly perform inference on the original representation. This thesis has three main contributions. First, we propose an exact probabilistic inference algorithm for propositional dynamic domains. Our approach allows to exploit different types of structures by compiling the transition model into an efficient circuit representation. Second, we propose an anytime probabilistic inference algorithm for relational domains. An efficient circuit representation is compiled in an incremental way and, at any time in the process, hard bounds on the inferred probabilities can be computed. Third, we deal with relational dynamic domains by combining principles from the first and second contribution. In addition, our approach exploits the given observations to further scale-up inference. The techniques presented in this dissertation are evaluated empirically on various real-world domains and applications such as biological and social network analysis, web-page classification, electronic circuit diagnosis and game playing. They outperform state-of-the-art approaches on these problems with respect to time, space and quality of results.status: publishe