Reasoning with Probabilistic and Deterministic Graphical Models: Exact Algorithms

✍ Scribed by Rina Dechter

• Publisher: Springer
• Year: 2019
• Tongue: English
• Leaves: 200
• Series: Synthesis Lectures on Artificial Intelligence and Machine Learning
• Edition: 2
• Category: Library

✦ Synopsis

Graphical models (e.g., Bayesian and constraint networks, influence diagrams, and Markov decision processes) have become a central paradigm for knowledge representation and reasoning in both artificial intelligence and computer science in general. These models are used to perform many reasoning tasks, such as scheduling, planning and learning, diagnosis and prediction, design, hardware and software verification, and bioinformatics. These problems can be stated as the formal tasks of constraint satisfaction and satisfiability, combinatorial optimization, and probabilistic inference. It is well known that the tasks are computationally hard, but research during the past three decades has yielded a variety of principles and techniques that significantly advanced the state of the art.

This book provides comprehensive coverage of the primary exact algorithms for reasoning with such models. The main feature exploited by the algorithms is the model's graph. We present inference-based, message-passing schemes (e.g., variable-elimination) and search-based, conditioning schemes (e.g., cycle-cutset conditioning and AND/OR search). Each class possesses distinguished characteristics and in particular has different time vs. space behavior. We emphasize the dependence of both schemes on few graph parameters such as the treewidth, cycle-cutset, and (the pseudo-tree) height. The new edition includes the notion of influence diagrams, which focus on sequential decision making under uncertainty. We believe the principles outlined in the book would serve well in moving forward to approximation and anytime-based schemes. The target audience of this book is researchers and students in the artificial intelligence and machine learning area, and beyond.

✦ Table of Contents

Cover
Copyright page
Title page
Contents
Preface
Introduction
Probabilistic vs. Deterministic Models
Directed vs. Undirected Models
General Graphical Models
Inference and Search-Based Schemes
Overview of the Book
Defining Graphical Models
General Graphical Models
The Graphs of Graphical Models
Basic Definitions
Types of Graphs
Constraint Networks
Cost Networks
Probability Networks
Bayesian Networks
Markov Networks
Influence Diagrams
Mixed Networks
Summary and Bibliographical Notes
Inference: Bucket Elimination for Deterministic Networks
Bucket Elimination for Constraint Networks
Bucket Elimination for Propositional CNFs
Bucket Elimination for Linear Inequalities
The Induced-Graph and Induced-Width
Trees
Finding Good Orderings
Chordal Graphs
Summary and Bibliography Notes
Inference: Bucket Elimination for Probabilistic Networks
Belief Updating and Probability of Evidence
Deriving BE-bel
Complexity of BE-bel
The Impact of Observations
Bucket Elimination for Optimization Tasks
A Bucket Elimination Algorithm for mpe
A Bucket Elimination Algorithm for map
Bucket Elimination for Markov Networks
Bucket Elimination for Influence Diagrams
Bucket Elimination for Cost Networks and Dynamic Programming
Bucket Elimination for Mixed Networks
The General Bucket Elimination
Summary and Bibliographical Notes
Appendix: Proofs
Tree-Clustering Schemes
Bucket-Tree Elimination
Asynchronous Bucket-Tree Propagation
From Bucket Trees to Cluster Trees
From Buckets to Clusters – the Short Route
Acyclic Graphical Models
Tree Decomposition and Cluster Tree Elimination
Generating Tree Decompositions
Properties of CTE for General Models
Correctness of CTE
Complexity of CTE
Illustration of CTE for Specific Models
Belief Updating and Probability of Evidence
Constraint Networks
Optimization
Summary and Bibliographical Notes
Appendix: Proofs
AND/OR Search Spaces for Graphical Models
AND/OR Search Trees
Weights of OR-AND Arcs
Pseudo Trees
Properties of AND/OR Search Trees
AND/OR Search Graphs
Generating Compact AND/OR Search Spaces
Building Context-Minimal AND/OR Search Graphs
Size of AND/OR Graph
Finding Good Pseudo-Trees
Pseudo Trees Created from Induced-Graphs
Hypergraph Decompositions
Value Functions of Reasoning Problems
Searching and/or Tree (AOT) and and/or Graph (AOG)
General AND-OR Search – AO(i)
Complexity
AND/OR Search Algorithms For Mixed Networks
AND-OR-cpe Algorithm
Constraint Propagation in AND-OR-cpe
Good and Nogood Learning
Summary and Bibliographical Notes
Appendix: Proofs
Combining Search and Inference: Trading Space for Time
The Cutset-Conditioning Scheme
Cutset-Conditioning for Constraints
General Cutset-Conditioning
Alternating Conditioning and Elimination
The Super-Cluster Schemes
Trading Time and Space with AND/OR Search
AND/OR Cutset-Conditioning
Algorithm Adaptive Caching (AOC(q))
Relations Between AOC(q), AO-ALT-VEC(q) and AO-VEC(q)
AOC(q) Compared with STCE(q)
Summary and Bibliographical Notes
Appendix: Proofs
Conclusion
Bibliography
Author's Biography