Reasoning with probabilistic and deterministic graphical models
Subtitle: exact algorithms
By: Rina Dechter
Series: Synthesis lectures on artificial intelligence and machine learning -- #23; Synthesis lectures on artificial intelligence and machine learning -- #23.
Publisher: Morgan & Claypool Publishers
Published: 2013
Place of publication: San Rafael, California]
Language: eng
Number of pages: 177
ISBN-13: 9781627051989; 9781627051972
Subjects: Graphical modeling (Statistics); Bayesian statistical decision theory; Reasoning; Algorithms; Machine learning; COMPUTERS; General
Description: 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.
Notes: Includes bibliographical references (pages 167-176).
Table of contents: title: Preface
pagenum: xiii; label: 1
title: Introduction
pagenum: 1; label: 1.1
title: Probabilistic vs. Deterministic Models
pagenum: 1; label: 1.2
title: Directed vs. Undirected Models
pagenum: 4; label: 1.3
title: General Graphical Models
pagenum: 6; label: 1.4
title: Inference and Search-based Schemes
pagenum: 7; label: 1.5
title: Overview of the Book
pagenum: 8; label: 2
title: What are Graphical Models
pagenum: 9; label: 2.1
title: General Graphical Models
pagenum: 9; label: 2.2
title: The Graphs of Graphical Models
pagenum: 11; label: 2.2.1
title: Basic Definitions
pagenum: 11; label: 2.2.2
title: Types of Graphs
pagenum: 12; label: 2.3
title: Constraint Networks
pagenum: 14; label: 2.4
title: Cost Networks
pagenum: 17; label: 2.5
title: Probability Networks
pagenum: 19; label: 2.5.1
title: Bayesian Networks
pagenum: 20; label: 2.5.2
title: Markov Networks
pagenum: 22; label: 2.6
title: Mixed Networks
pagenum: 25; label: 2.7
title: Summary and Bibliographical Notes
pagenum: 27; label: 3
title: Inference: Bucket Elimination for Deterministic Networks
pagenum: 29; label: 3.1
title: Bucket-Elimination for Constraint Networks
pagenum: 31; label: 3.2
title: Bucket Elimination for Propositional CNFs
pagenum: 36; label: 3.3
title: Bucket Elimination for Linear Inequalities
pagenum: 40; label: 3.4
title: The Induced-Graph and Induced-Width
pagenum: 41; label: 3.4.1
title: Trees
pagenum: 42; label: 3.4.2
title: Finding Good Orderings
pagenum: 42; label: 3.5
title: Chordal Graphs
pagenum: 44; label: 3.6
title: Summary and Bibliography Notes
pagenum: 46; label: 4
title: Inference: Bucket Elimination for Probabilistic Networks
pagenum: 47; label: 4.1
title: Belief Updating and Probability of Evidence
pagenum: 47; label: 4.1.1
title: Deriving BE-bel
pagenum: 48; label: 4.1.2
title: Complexity of BE-bel
pagenum: 54; label: 4.1.3
title: The Impact of Observations
pagenum: 56; label: 4.2
title: Bucket Elimination for Optimization Tasks
pagenum: 60; label: 4.2.1
title: A Bucket Elimination Algorithm for MPE
pagenum: 60; label: 4.2.2
title: A Bucket Elimination Algorithm for MAP
pagenum: 63; label: 4.3
title: Bucket Elimination for Markov Networks
pagenum: 63; label: 4.4
title: Bucket Elimination for Cost Networks and Dynamic Programming
pagenum: 65; label: 4.5
title: Bucket Elimination for Mixed Networks
pagenum: 66; label: 4.6
title: The General Bucket Elimination
pagenum: 71; label: 4.7
title: Summary and Bibliographical Notes
pagenum: 71; label: 4.8
title: Appendix: Proofs
pagenum: 72; label: 5
title: Tree-Clustering Schemes
pagenum: 75; label: 5.1
title: Bucket-Tree Elimination
pagenum: 75; label: 5.1.1
title: Asynchronous Bucket-tree Propagation
pagenum: 81; label: 5.2
title: From Bucket Trees to Cluster Trees
pagenum: 83; label: 5.2.1
title: From Buckets to Clusters; The Short Route
pagenum: 83; label: 5.2.2
title: Acyclic Graphical Models
pagenum: 84; label: 5.2.3
title: Tree Decomposition and Cluster Tree Elimination
pagenum: 86; label: 5.2.4
title: Generating Tree Decompositions
pagenum: 89; label: 5.3
title: Properties of CTE for General Models
pagenum: 92; label: 5.3.1
title: Correctness of CTE
pagenum: 93; label: 5.3.2
title: Complexity of CTE
pagenum: 95; label: 5.4
title: Illustration of CTE for Specific Models
pagenum: 96; label: 5.4.1
title: Belief Updating and Probability of Evidence
pagenum: 96; label: 5.4.2
title: Constraint Networks
pagenum: 98; label: 5.4.3
title: Optimization
pagenum: 101; label: 5.5
title: Summary and Bibliographical Notes
pagenum: 102; label: 5.6
title: Appendix: Proofs
pagenum: 102; label: 6
title: AND/OR Search Spaces and Algorithms for Graphical Models
pagenum: 107; label: 6.1
title: AND/OR Search Trees
pagenum: 109; label: 6.1.1
title: Weights of OR-AND Arcs
pagenum: 112; label: 6.1.2
title: Pseudo Trees
pagenum: 114; label: 6.1.3
title: Properties of AND/OR Search Trees
pagenum: 115; label: 6.2
title: AND/OR Search Graphs
pagenum: 116; label: 6.2.1
title: Generating Compact AND/OR Search Spaces
pagenum: 118; label: 6.2.2
title: Building Context-Minimal AND/OR Search Graphs
pagenum: 118; label: 6.3
title: Finding Good Pseudo Trees
pagenum: 122; label: 6.3.1
title: Pseudo Trees Created from Induced Graphs
pagenum: 122; label: 6.3.2
title: Hypergraph Decompositions
pagenum: 124; label: 6.4
title: Value Functions of Reasoning Problems
pagenum: 124; label: 6.4.1
title: Searching and/or Tree (AOT) and and/or Graph (AOG)
pagenum: 128; label: 6.5
title: General AND-OR Search - AO(i)
pagenum: 130; label: 6.5.1
title: Complexity
pagenum: 131; label: 6.6
title: AND/OR Search Algorithms For Mixed Networks
pagenum: 133; label: 6.6.1
title: AND-OR-CPE Algorithm
pagenum: 135; label: 6.6.2
title: Constraint Propagation in AND-OR-CPE
pagenum: 137; label: 6.6.3
title: Good and Nogood Learning
pagenum: 139; label: 6.7
title: Summary and Bibliographical Notes
pagenum: 140; label: 6.8
title: Appendix: Proofs
pagenum: 141; label: 7
title: Combining Search and Inference: Trading Space for Time
pagenum: 143; label: 7.1
title: The Cutset-Conditioning Scheme
pagenum: 143; label: 7.1.1
title: Cutset-conditioning for Constraints
pagenum: 143; label: 7.1.2
title: General Cutset-conditioning
pagenum: 146; label: 7.1.3
title: Alternating Conditioning and Elimination
pagenum: 147; label: 7.2
title: The Super-Cluster Schemes
pagenum: 150; label: 7.3
title: Trading Time and Space with AND/OR Search
pagenum: 152; label: 7.3.1
title: AND/OR Cutset-Conditioning
pagenum: 152; label: 7.3.2
title: Algorithm Adaptive Caching (AOC(q))
pagenum: 154; label: 7.3.3
title: Relations Between AOC(q), AO-ALT-VEC(q) and AO-VEC(q)
pagenum: 157; label: 7.3.4
title: AOC(q) Compared with STCE(q)
pagenum: 161; label: 7.4
title: Summary and Bibliographical Notes
pagenum: 162; label: 7.5
title: Appendix: Proofs
pagenum: 163; label: 8
title: Conclusion
pagenum: 165; title: Bibliography
pagenum: 167; title: Author's Biography
pagenum: 177