Introduction to Lifted Probabilistic Inference

Contents
List of Figures
Contributors
Preface
I OVERVIEW
1 Statistical Relational AI: Representation, Inference and Learning
1.1 Representations
1.1.1 First-order Logic and Logic Programs
1.1.2 Probability and Graphical Models
1.1.3 Relational Probabilistic Models
1.1.4 Weighted First-order Model Counting
1.1.5 Observations and Queries
1.2 Inference
1.3 Learning
1.4 Book Details
2 Modeling and Reasoning with Statistical Relational Representations
2.1 Preliminaries: First-order Logic
2.2 Lifted Graphical Models and Probabilistic Logic Programs
2.2.1 Parameterized Factors: Markov Logic Networks
2.2.2 Probabilistic Logic Programs: ProbLog
2.2.3 Inference Tasks
2.3 Statistical Relational Representations
2.3.1 Desirable Properties of Representation Languages
2.3.2 Design Choices
2.4 Conclusions
3 Statistical Relational Learning
3.1 Introduction
3.2 Statistical Relational Learning Models
3.3 Parameter Learning of SRL models
3.4 Markov Logic Networks
3.5 Parameter and Structure Learning of Markov Logic Networks
3.5.1 Parameter Learning
3.5.2 Structure Learning
3.6 Boosting-based Learning of SRL Models
3.7 Deep Transfer Learning Using SRL Models
3.7.1 TAMAR
3.7.2 DTM
3.7.3 TODTLER
3.7.4 LTL
3.8 Conclusion
II EXACT INFERENCE
4 Lifted Variable Elimination
4.1 Introduction
4.2 Lifted Variable Elimination by Example
4.2.1 The Workshop Example
4.2.2 Variable Elimination
4.2.3 Lifted Inference: Exploiting Symmetries among Factors
4.2.4 Lifted Inference: Exploiting Symmetries within Factors
4.2.5 Splitting Overlapping Groups and Its Relation to Unification
4.3 Representation
4.3.1 A Constraint-based Representation Formalism
4.3.2 Counting Formulas
4.4 The GC-FOVE Algorithm: Outline
4.5 GC-FOVE's Operators
4.5.1 Lifted Multiplication
4.5.2 Lifted Summing-out
4.5.3 Counting Conversion
4.5.4 Splitting and Shattering
4.5.5 Expansion of Counting Formulas
4.5.6 Count Normalization
4.5.7 Grounding a Logvar
5 Search-Based Exact Lifted Inference
5.1 Background and Notation
5.1.1 Random Variables, Independence, and Symmetry
5.1.2 Finite-domain Function-free First-order Logic
5.1.3 Log-linear Models
5.1.4 Graphical Notation of Dependencies in Log-linear Models
5.1.5 Markov Logic Networks
5.1.6 From Normalization Constant to Probabilistic Inference
5.2 Weighted Model Count
5.2.1 Formal Definition
5.2.2 Converting Inference into Calculating WMCs
5.2.3 Efficiently Finding the WMC of a Theory
5.2.4 Order of Applying Rules
5.3 Lifting Search-Based Inference
5.3.1 Weighted Model Counting for First-order Theories
5.3.2 Converting Inference for Relational Models into Calculating WMCs of First-order Theories
5.3.3 Efficiently Calculating the WMC of a First-order Theory
5.3.4 Order of Applying Rules
5.3.5 Bounding the Complexity of Lifted Inference
6 Lifted Aggregation and Skolemization for Directed Models
6.1 Introduction
6.2 Lifted Aggregation in Directed First-order Probabilistic Models
6.2.1 Parameterized Random Variables and Parametric Factors
6.2.2 Aggregation in Directed First-order Probabilistic Models
6.2.3 Existing Algorithm
6.2.4 Incorporating Aggregation in C-FOVE
6.2.5 Experiments
6.3 Efficient Methods for Lifted Inference with Aggregation Parfactors
6.3.1 Efficient Methods for AFM Problems
6.3.2 Aggregation Factors with Multiple Atoms
6.3.3 Efficient Lifted Belief Propagation with Aggregation Parfactors
6.3.4 Error Analysis
6.3.5 Experiments
6.4 Lifted Aggregation through Skolemization for Weighted First-order Model Counting
6.4.1 Normal Forms
6.4.2 Skolemization for WFOMC
6.4.3 Skolemization of Markov Logic Networks
6.4.4 Skolemization of Probabilistic Logic Programs
6.4.5 Negative Probabilities
6.4.6 Experiments
6.5 Conclusions
7 First-order Knowledge Compilation
7.1 Calculating WMC of Propositional Theories through Knowledge Compilation
7.2 Knowledge Compilation for First-order Theories
7.2.1 Compilation Example
7.2.2 Pruning
7.3 Why Compile to Low-level Programs?
8 Domain Liftability
8.1 Domain-liftable Classes
8.1.1 Membership Checking
8.2 Negative Results
9 Tractability through Exchangeability: The Statistics of Lifting
9.1 Introduction
9.2 A Case Study: Markov Logic
9.2.1 Markov Logic Networks Review
9.2.2 Inference without Independence
9.3 Finite Exchangeability
9.3.1 Finite Partial Exchangeability
9.3.2 Partial Exchangeability and Probabilistic Inference
9.3.3 Markov Logic Case Study
9.4 Exchangeable Decompositions
9.4.1 Variable Decompositions
9.4.2 Tractable Variable Decompositions
9.4.3 Markov Logic Case Study
9.5 Marginal and Conditional Exchangeability
9.5.1 Marginal and Conditional Decomposition
9.5.2 Markov Logic Case Study
9.6 Discussion and Conclusion
III APPROXIMATE INFERENCE
10 Lifted Markov Chain Monte Carlo
10.1 Introduction
10.2 Background
10.2.1 Group Theory
10.2.2 Finite Markov Chains
10.2.3 Markov Chain Monte Carlo
10.3 Symmetries of Probabilistic Models
10.3.1 Graphical Model Symmetries
10.3.2 Relational Model Symmetries
10.4 Lifted MCMC for Symmetric Models
10.4.1 Lumping
10.4.2 Orbital Markov Chains
10.5 Lifted MCMC for Asymmetric Models
10.5.1 Mixing
10.5.2 Metropolis-Hastings Chains
10.5.3 Orbital Metropolis Chains
10.5.4 Lifted Metropolis-Hastings
10.6 Approximate Symmetries
10.6.1 Relational Symmetrization
10.6.2 Propositional Symmetrization
10.6.3 From OSAs to Automorphisms
10.7 Empirical Evaluation
10.7.1 Symmetric Model Experiments
10.8 Asymmetric Model Experiments
10.9 Conclusions
10.10 Acknowledgments
10.11 Appendix: Proof of Theorem 10.3
11 Lifted Message Passing for Probabilistic and Combinatorial Problems
11.1 Introduction
11.2 Loopy Belief Propagation (LBP)
11.3 Lifted Message Passing for Probabilistic Inference: Lifted (Loopy) BP
11.3.1 Step 1 – Compressing the Factor Graph
11.3.2 Step 2 – BP on the Compressed Factor Graph
11.4 Lifted Message Passing for SAT Problems
11.4.1 Lifted Satisfiability
11.4.2 CNFs and Factor Graphs
11.4.3 Belief Propagation for Satisfiability
11.4.4 Decimation-based SAT Solving
11.4.5 Lifted Warning Propagation
11.4.6 Lifted Survey Propagation
11.4.7 Lifted Decimation
11.4.8 Experimental Evaluation
11.4.9 Summary: Lifted Satisfiability
11.5 Lifted Sequential Clamping for SAT Problems and Sampling
11.5.1 Lifted Sequential Inference
11.5.2 Experimental Evaluation
11.5.3 Summary Lifted Sequential Clamping
11.6 Lifted Message Passing for MAP via Likelihood Maximization
11.6.1 Lifted Likelihood Maximization (LM)
11.6.2 Bootstrapped Likelihood Maximization (LM)
11.6.3 Bootstrapped Lifted Likelihood Maximization (LM)
11.6.4 Experimental Evaluation
11.6.5 Summary of Lifted Likelihood Maximization for MAP Inference
11.7 Conclusions
12 Lifted Generalized Belief Propagation: Relax, Compensate and Recover
12.1 Introduction
12.2 RCR for Ground MLNs
12.2.1 Ground Relaxation
12.2.2 Ground Compensation
12.2.3 Ground Recovery
12.3 Lifted RCR
12.3.1 First-order Relaxation
12.3.2 First-order Compensation
12.3.3 Count-Normalization
12.3.4 The Compensation Scheme
12.3.5 First-order Recovery
12.4 Partitioning Equivalences
12.4.1 Partitioning Atoms by Preemptive Shattering
12.4.2 Partitioning Equivalences by Preemptive Shattering
12.4.3 Dynamic Equivalence Partitioning
12.5 Related and Future Work
12.5.1 Relation to Propositional Algorithms
12.5.2 Relation to Lifted Algorithms
12.5.3 Opportunities for Equivalence Partitioning
12.6 Experiments
12.6.1 Implementation
12.6.2 Results
12.7 Conclusions
13 Liftability Theory of Variational Inference
13.1 Introduction
13.2 Lifted Variational Inference
13.2.1 Symmetry: Groups and Partitions
13.2.2 Exponential Families and the Variational Principle
13.2.3 Lifting the Variational Principle
13.3 Exact Lifted Variational Inference: Automorphisms of F
13.3.1 Automorphisms of Exponential Family
13.3.2 Parameter Tying and Lifting Partitions
13.3.3 Computing Automorphisms of F
13.3.4 The Lifted Marginal Polytope
13.4 Beyond Orbits of F: Approximate Lifted Variational Inference
13.4.1 Approximate Variational Inference
13.4.2 Equitable Partitions of the Exponential Family
13.4.3 Equitable Partitions of Concave Energies
13.4.4 Lifted Counting Numbers
13.4.5 Computing Equitable Partitions of Exponential Families
13.5 Unfolding Variational Inference Algorithms via Reparametrization
13.5.1 The Lifted Approximate Variational Problem
13.5.2 Energy Equivalence of Exponential Families
13.5.3 Finding Partition-Equivalent Exponential Families
13.6 Symmetries of Markov Logic Networks (MLNs)
13.7 Conclusions
14 Lifted Inference for Hybrid Relational Models
14.1 Introduction
14.2 Relational Continuous Models
14.2.1 Inference Algorithms for RCMs
14.2.2 Exact Lifted Inference with RCMs
14.2.3 Conditions for Exact Lifted Inference
14.3 Relational Kalman Filtering
14.3.1 Model and Problem Definitions
14.3.2 Lifted Relational Kalman Filter
14.3.3 Algorithms and Computational Complexity
14.4 Lifted Message Passing for Hybrid Relational Models
14.4.1 Lifted Gaussian Belief Propagation
14.4.2 Multi-evidence Lifting
14.4.3 Sequential Multi-Evidence Lifting
14.5 Approximate Lifted Inference for General RCMs
14.6 Conclusions
IV BEYOND PROBABILISTIC INFERENCE
15 Color Refinement and Its Applications
15.1 Introduction
15.1.1 Applications
15.1.2 Variants
15.1.3 A Logical Characterization of Color Refinement
15.2 Color Refinement in Quasilinear Time
15.3 Application: Graph Isomorphism Testing
15.4 The Weisfeiler-Leman Algorithm
15.5 Fractional Isomorphism
15.5.1 Color Refinement and Fractional Isomorphism of Matrices
15.6 Application: Linear Programming
15.7 Application: Weisfeiler-Leman Graph Kernels
15.8 Conclusions
16 Stochastic Planning and Lifted Inference
16.1 Introduction
16.1.1 Stochastic Planning and Inference
16.1.2 Stochastic Planning and Generalized Lifted Inference
16.2 Preliminaries
16.2.1 Relational Expressions and Their Calculus of Operations
16.2.2 Relational MDPs
16.3 Symbolic Dynamic Programming
16.4 Discussion and Related Work
16.4.1 Deductive Lifted Stochastic Planning
16.4.2 Inductive Lifted Stochastic Planning
16.5 Conclusions
Bibliography
Index