An Introduction to Lifted Probabilistic Inference

Recent advances in the area of lifted inference, which exploits the structure inherent in relational probabilistic models.

Statistical relational AI (StaRAI) studies the integration of reasoning under uncertainty with reasoning about individuals and relations. The representations used are often called relational probabilistic models. Lifted inference is about how to exploit the structure inherent in relational probabilistic models, either in the way they are expressed or by extracting structure from observations. This book covers recent significant advances in the area of lifted inference, providing a unifying introduction to this very active field.

After providing necessary background on probabilistic graphical models, relational probabilistic models, and learning inside these models, the book turns to lifted inference, first covering exact inference and then approximate inference. In addition, the book considers the theory of liftability and acting in relational domains, which allows the connection of learning and reasoning in relational domains.

Guy Van den Broeck is Associate Professor of Computer Science at the University of California, Los Angeles. Kristian Kersting is Professor in the Computer Science Department and the Centre for Cognitive Science at Technische Universität Darmstadt. Sriraam Natarajan is Professor and the Director of the Center for Machine Learning in the Department of Computer Science at University of Texas at Dallas. David Poole is Professor in the Department of Computer Science at the University of British Columbia.

List of Figures
Contributors
Preface
I OVERVIEW
1 Statistical Relational AI: Representation, Inference and Learning
2 Modeling and Reasoning with Statistical Relational Representation
3 Statistical Relational Learning
II EXACT INFERENCE
4 Lifted Variable Elimination
5 Search-Based Exact Lifted Inference
6 Lifted Aggregation and Skolemization for Directed Models
7 First-Order Knowledge Compilation
8 Domain Liftability
9 Tractability through Exchangeability: The Statistics of Lifting
III APPROXIMATE INFERENCE
10 Lifted Markov Chain Monte Carlo
11 Lifted Message Passing for Probabilistic and Combinatorial Problems
12 Lifted Generalized Belief Propagation: Relax, Compensate and Recover
13 Liftability Theory of Variational Inference
14 Lifted Inference for Hybrid Relational Models
IV BEYOND PROBABILISTIC INFERENCE
15 Color Refinement and Its Applications
16 Stochastic Planning and Lifted Inference
Bibliography
Index