Muutke küpsiste eelistusi

Introduction to Lifted Probabilistic Inference [Pehme köide]

,
  • Formaat: Paperback / softback, 454 pages, kõrgus x laius: 229x178 mm
  • Sari: Neural Information Processing series
  • Ilmumisaeg: 17-Aug-2021
  • Kirjastus: MIT Press
  • ISBN-10: 0262542595
  • ISBN-13: 9780262542593
Teised raamatud teemal:
Introduction to Lifted Probabilistic InferenceSuurem pilt
  • Formaat: Paperback / softback, 454 pages, kõrgus x laius: 229x178 mm
  • Sari: Neural Information Processing series
  • Ilmumisaeg: 17-Aug-2021
  • Kirjastus: MIT Press
  • ISBN-10: 0262542595
  • ISBN-13: 9780262542593
Teised raamatud teemal:
Püsilink: https://www.kriso.ee/db/9780262542593.html
Märksõnad:
"The book presents an introduction to, and an authoritative guide, for anyone interested in the problem of probabilistic inference in the presence of symmetries/structured models"--

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.
List of Figures
xv
Contributors xxi
Preface xxiii
I OVERVIEW
1 Statistical Relational AI: Representation, Inference and Learning
3(12)
Guy Van den Broeck
Kristian Kersting
Sriraam Natarajan
David Poole
1.1 Representations
4(8)
1.1.1 First-order Logic and Logic Programs
5(1)
1.1.2 Probability and Graphical Models
6(2)
1.1.3 Relational Probabilistic Models
8(3)
1.1.4 Weighted First-order Model Counting
11(1)
1.1.5 Observations and Queries
11(1)
1.2 Inference
12(2)
1.3 Learning
14(1)
1.4 Book Details
14(1)
2 Modeling and Reasoning with Statistical Relational Representations
15(24)
Angelika Kimmig
David Poole
2.1 Preliminaries: First-order Logic
16(1)
2.2 Lifted Graphical Models and Probabilistic Logic Programs
17(11)
2.2.1 Parameterized Factors: Markov Logic Networks
17(4)
2.2.2 Probabilistic Logic Programs: ProbLog
21(5)
2.2.3 Inference Tasks
26(2)
2.3 Statistical Relational Representations
28(10)
2.3.1 Desirable Properties of Representation Languages
28(1)
2.3.2 Design Choices
29(9)
2.4 Conclusions
38(1)
3 Statistical Relational Learning
39(18)
Sriraam Natarajan
Jesse Davis
Kristian Kersting
Daniel Lowd
Pedro Domingos
Raymond Mooney
3.1 Introduction
39(1)
3.2 Statistical Relational Learning Models
40(1)
3.3 Parameter Learning of SRL models
41(1)
3.4 Markov Logic Networks
41(1)
3.5 Parameter and Structure Learning of Markov Logic Networks
42(3)
3.5.1 Parameter Learning
42(2)
3.5.2 Structure Learning
44(1)
3.6 Boosting-based Learning of SRL Models
45(2)
3.7 Deep Transfer Learning Using SRL Models
47(6)
3.7.1 TAMAR
48(1)
3.7.2 DTM
48(1)
3.7.3 TODTLER
49(2)
3.7.4 LTL
51(2)
3.8 Conclusion
53(4)
II EXACT INFERENCE
4 Lifted Variable Elimination
57(32)
Nima Taghipour
Daan Fierens
Jesse Davis
Hendrik Blockeel
Rodrigo de Salvo Braz
4.1 Introduction
57(1)
4.2 Lifted Variable Elimination by Example
58(8)
4.2.1 The Workshop Example
58(1)
4.2.2 Variable Elimination
59(3)
4.2.3 Lifted Inference: Exploiting Symmetries among Factors
62(1)
4.2.4 Lifted Inference: Exploiting Symmetries within Factors
62(2)
4.2.5 Splitting Overlapping Groups and Its Relation to Unification
64(2)
4.3 Representation
66(4)
4.3.1 A Constraint-based Representation Formalism
66(2)
4.3.2 Counting Formulas
68(2)
4.4 The GC-FOVE Algorithm: Outline
70(1)
4.5 GC-FOVE's Operators
71(18)
4.5.1 Lifted Multiplication
71(2)
4.5.2 Lifted Summing-out
73(3)
4.5.3 Counting Conversion
76(3)
4.5.4 Splitting and Shattering
79(3)
4.5.5 Expansion of Counting Formulas
82(3)
4.5.6 Count Normalization
85(1)
4.5.7 Grounding a Logvar
85(4)
5 Search-Based Exact Lifted Inference
89(24)
Seyed Mehran Kazemi
Guy Van den Broeck
David Poole
5.1 Background and Notation
90(4)
5.1.1 Random Variables, Independence, and Symmetry
90(1)
5.1.2 Finite-domain Function-free First-order Logic
91(1)
5.1.3 Log-linear Models
92(1)
5.1.4 Graphical Notation of Dependencies in Log-linear Models
93(1)
5.1.5 Markov Logic Networks
93(1)
5.1.6 From Normalization Constant to Probabilistic Inference
94(1)
5.2 Weighted Model Count
94(6)
5.2.1 Formal Definition
95(1)
5.2.2 Converting Inference into Calculating WMCs
96(1)
5.2.3 Efficiently Finding the WMC of a Theory
96(3)
5.2.4 Order of Applying Rules
99(1)
5.3 Lifting Search-Based Inference
100(13)
5.3.1 Weighted Model Counting for First-order Theories
101(2)
5.3.2 Converting Inference for Relational Models into Calculating WMCs of First-order Theories
103(1)
5.3.3 Efficiently Calculating the WMC of a First-order Theory
103(7)
5.3.4 Order of Applying Rules
110(1)
5.3.5 Bounding the Complexity of Lifted Inference
110(3)
6 Lifted Aggregation and Skolemization for Directed Models
113(34)
Wannes Meert
Jaesik Choi
Jacek Kisyriski
Hung Bui
Guy Van den Broeck
Adnan Darwiche
Rodrigo de Salvo Braz
David Poole
6.1 Introduction
113(1)
6.2 Lifted Aggregation in Directed First-order Probabilistic Models
114(13)
6.2.1 Parameterized Random Variables and Parametric Factors
114(2)
6.2.2 Aggregation in Directed First-order Probabilistic Models
116(2)
6.2.3 Existing Algorithm
118(1)
6.2.4 Incorporating Aggregation in C-FOVE
119(6)
6.2.5 Experiments
125(2)
6.3 Efficient Methods for Lifted Inference with Aggregation Parfactors
127(10)
6.3.1 Efficient Methods for AFM Problems
129(5)
6.3.2 Aggregation Factors with Multiple Atoms
134(1)
6.3.3 Efficient Lifted Belief Propagation with Aggregation Parfactors
135(1)
6.3.4 Error Analysis
135(1)
6.3.5 Experiments
136(1)
6.4 Lifted Aggregation through Skolemization for Weighted First-order Model Counting
137(7)
6.4.1 Normal Forms
137(1)
6.4.2 Skolemization for WFOMC
137(2)
6.4.3 Skolemization of Markov Logic Networks
139(2)
6.4.4 Skolemization of Probabilistic Logic Programs
141(2)
6.4.5 Negative Probabilities
143(1)
6.4.6 Experiments
144(1)
6.5 Conclusions
144(3)
7 First-order Knowledge Compilation
147(8)
Seyed Mehran Kazemi
Guy Van den Broeck
David Poole
7.1 Calculating WMC of Propositional Theories through Knowledge Compilation
148(1)
7.2 Knowledge Compilation for First-order Theories
149(3)
7.2.1 Compilation Example
151(1)
7.2.2 Pruning
151(1)
7.3 Why Compile to Low-level Programs?
152(3)
8 Domain Liftability
155(6)
Seyed Mehran Kazemi
Angelika Kimmig
Guy Van den Broeck
David Poole
8.1 Domain-liftable Classes
155(3)
8.1.1 Membership Checking
158(1)
8.2 Negative Results
158(3)
9 Tractability through Exchangeability: The Statistics of Lifting
161(20)
Mathias Niepert
Guy Van den Broeck
9.1 Introduction
161(1)
9.2 A Case Study: Markov Logic
162(2)
9.2.1 Markov Logic Networks Review
163(1)
9.2.2 Inference without Independence
163(1)
9.3 Finite Exchangeability
164(3)
9.3.1 Finite Partial Exchangeability
165(1)
9.3.2 Partial Exchangeability and Probabilistic Inference
166(1)
9.3.3 Markov Logic Case Study
166(1)
9.4 Exchangeable Decompositions
167(3)
9.4.1 Variable Decompositions
167(1)
9.4.2 Tractable Variable Decompositions
168(1)
9.4.3 Markov Logic Case Study
169(1)
9.5 Marginal and Conditional Exchangeability
170(3)
9.5.1 Marginal and Conditional Decomposition
170(2)
9.5.2 Markov Logic Case Study
172(1)
9.6 Discussion and Conclusion
173(8)
III APPROXIMATE INFERENCE
10 Lifted Markov Chain Monte Carlo
181(22)
Mathias Niepert
Guy Van den Broeck
10.1 Introduction
181(1)
10.2 Background
182(2)
10.2.1 Group Theory
182(1)
10.2.2 Finite Markov Chains
183(1)
10.2.3 Markov Chain Monte Carlo
183(1)
10.3 Symmetries of Probabilistic Models
184(2)
10.3.1 Graphical Model Symmetries
184(1)
10.3.2 Relational Model Symmetries
185(1)
10.4 Lifted MCMC for Symmetric Models
186(4)
10.4.1 Lumping
187(1)
10.4.2 Orbital Markov Chains
188(2)
10.5 Lifted MCMC for Asymmetric Models
190(3)
10.5.1 Mixing
190(1)
10.5.2 Metropohs-Hastings Chains
190(1)
10.5.3 Orbital Metropolis Chains
191(1)
10.5.4 Lifted Metropolis-Hastings
192(1)
10.6 Approximate Symmetries
193(2)
10.6.1 Relational Symmetrization
194(1)
10.6.2 Propositional Symmetrization
194(1)
10.6.3 From OSAs to Automorphisms
195(1)
10.7 Empirical Evaluation
195(1)
10.7.1 Symmetric Model Experiments
195(1)
10.8 Asymmetric Model Experiments
196(2)
10.9 Conclusions
198(1)
10.10 Acknowledgments
198(1)
10.11 Appendix: Proof of Theorem 10.3
198(5)
11 Lifted Message Passing for Probabilistic and Combinatorial Problems
203(56)
Kristian Kersting
Fabian Hadiji
Babak Ahmadi
Martin Mladenov
Sriraam Natarajan
11.1 Introduction
203(2)
11.2 Loopy Belief Propagation (LBP)
205(1)
11.3 Lifted Message Passing for Probabilistic Inference: Lifted (Loopy) BP
206(5)
11.3.1 Step 1 -- Compressing the Factor Graph
206(2)
11.3.2 Step 2 -- BP on the Compressed Factor Graph
208(3)
11.4 Lifted Message Passing for SAT Problems
211(16)
11.4.1 Lifted Satisfiability
212(2)
11.4.2 CNFs and Factor Graphs
214(2)
11.4.3 Belief Propagation for Satisfiability
216(1)
11.4.4 Decimation-based SAT Solving
216(1)
11.4.5 Lifted Warning Propagation
217(3)
11.4.6 Lifted Survey Propagation
220(3)
11.4.7 Lifted Decimation
223(1)
11.4.8 Experimental Evaluation
224(1)
11.4.9 Summary: Lifted Satisfiability
225(2)
11.5 Lifted Sequential Clamping for SAT Problems and Sampling
227(11)
11.5.1 Lifted Sequential Inference
228(5)
11.5.2 Experimental Evaluation
233(4)
11.5.3 Summary Lifted Sequential Clamping
237(1)
11.6 Lifted Message Passing for MAP via Likelihood Maximization
238(18)
11.6.1 Lifted Likelihood Maximization (LM)
239(3)
11.6.2 Bootstrapped Likelihood Maximization (LM)
242(1)
11.6.3 Bootstrapped Lifted Likelihood Maximization (LM)
243(6)
11.6.4 Experimental Evaluation
249(5)
11.6.5 Summary of Lifted Likelihood Maximization for MAP Inference
254(2)
11.7 Conclusions
256(3)
12 Lifted Generalized Belief Propagation: Relax, Compensate and Recover
259(22)
Guy Van den Broeck
Arthur Choi
Adnan Darwiche
12.1 Introduction
259(1)
12.2 RCR for Ground MLNs
260(3)
12.2.1 Ground Relaxation
261(1)
12.2.2 Ground Compensation
261(1)
12.2.3 Ground Recovery
262(1)
12.3 Lifted RCR
263(7)
12.3.1 First-order Relaxation
263(2)
12.3.2 First-order Compensation
265(3)
12.3.3 Count-Normalization
268(1)
12.3.4 The Compensation Scheme
269(1)
12.3.5 First-order Recovery
269(1)
12.4 Partitioning Equivalences
270(3)
12.4.1 Partitioning Atoms by Preemptive Shattering
270(1)
12.4.2 Partitioning Equivalences by Preemptive Shattering
271(1)
12.4.3 Dynamic Equivalence Partitioning
272(1)
12.5 Related and Future Work
273(2)
12.5.1 Relation to Propositional Algorithms
273(1)
12.5.2 Relation to Lifted Algorithms
274(1)
12.5.3 Opportunities for Equivalence Partitioning
274(1)
12.6 Experiments
275(5)
12.6.1 Implementation
275(1)
12.6.2 Results
276(4)
12.7 Conclusions
280(1)
13 Lift ability Theory of Variational Inference
281(36)
Martin Mladenov
Hung Bui
Kristian Kersting
13.1 Introduction
281(1)
13.2 Lifted Variational Inference
282(6)
13.2.1 Symmetry: Groups and Partitions
283(2)
13.2.2 Exponential Families and the Variational Principle
285(1)
13.2.3 Lifting the Variational Principle
286(2)
13.3 Exact Lifted Variational Inference: Automorphisms of F
288(7)
13.3.1 Automorphisms of Exponential Family
288(3)
13.3.2 Parameter Tying and Lifting Partitions
291(1)
13.3.3 Computing Automorphisms of F
292(1)
13.3.4 The Lifted Marginal Polytope
293(2)
13.4 Beyond Orbits of T: Approximate Lifted Variational Inference
295(10)
13.4.1 Approximate Variational Inference
296(1)
13.4.2 Equitable Partitions of the Exponential Family
297(2)
13.4.3 Equitable Partitions of Concave Energies
299(3)
13.4.4 Lifted Counting Numbers
302(2)
13.4.5 Computing Equitable Partitions of Exponential Families
304(1)
13.5 Unfolding Variational Inference Algorithms via Reparametrization
305(10)
13.5.1 The Lifted Approximate Variational Problem
306(2)
13.5.2 Energy Equivalence of Exponential Families
308(3)
13.5.3 Finding Partition-Equivalent Exponential Families
311(4)
13.6 Symmetries of Markov Logic Networks (MLNs)
315(1)
13.7 Conclusions
316(1)
14 Lifted Inference for Hybrid Relational Models
317(32)
Jaesik Choi
Kristian Kersting
Yuqiao Chen
14.1 Introduction
317(1)
14.2 Relational Continuous Models
318(9)
14.2.1 Inference Algorithms for RCMs
321(3)
14.2.2 Exact Lifted Inference with RCMs
324(1)
14.2.3 Conditions for Exact Lifted Inference
325(2)
14.3 Relational Kalman Filtering
327(10)
14.3.1 Model and Problem Definitions
328(4)
14.3.2 Lifted Relational Kalman Filter
332(3)
14.3.3 Algorithms and Computational Complexity
335(2)
14.4 Lifted Message Passing for Hybrid Relational Models
337(6)
14.4.1 Lifted Gaussian Belief Propagation
337(3)
14.4.2 Multi-evidence Lifting
340(1)
14.4.3 Sequential Multi-Evidence Lifting
341(2)
14.5 Approximate Lifted Inference for General RCMs
343(1)
14.6 Conclusions
344(5)
IV BEYOND PROBABILISTIC INFERENCE
15 Color Refinement and Its Applications
349(24)
Martin Grohe
Kristian Kersting
Martin Mladenov
Pascal Schweitzer
15.1 Introduction
349(4)
15.1.1 Applications
350(1)
15.1.2 Variants
351(1)
15.1.3 A Logical Characterization of Color Refinement
352(1)
15.2 Color Refinement in Quasilinear Time
353(2)
15.3 Application: Graph Isomorphism Testing
355(3)
15.4 The Weisfeiler-Leman Algorithm
358(2)
15.5 Fractional Isomorphism
360(6)
15.5.1 Color Refinement and Fractional Isomorphism of Matrices
364(2)
15.6 Application: Linear Programming
366(2)
15.7 Application: Weisfeiler-Leman Graph Kernels
368(2)
15.8 Conclusions
370(3)
16 Stochastic Planning and Lifted Inference
373(24)
Roni Khardon
Scott Sanner
16.1 Introduction
373(8)
16.1.1 Stochastic Planning and Inference
375(3)
16.1.2 Stochastic Planning and Generalized Lifted Inference
378(3)
16.2 Preliminaries
381(5)
16.2.1 Relational Expressions and Their Calculus of Operations
381(3)
16.2.2 Relational MDPs
384(2)
16.3 Symbolic Dynamic Programming
386(6)
16.4 Discussion and Related Work
392(3)
16.4.1 Deductive Lifted Stochastic Planning
392(2)
16.4.2 Inductive Lifted Stochastic Planning
394(1)
16.5 Conclusions
395(2)
Bibliography 397(28)
Index 425