CS262A Learning and Reasoning with Bayesian Network

Table of contents

1. CS262A Learning and Reasoning with Bayesian Network

---

CS262A Learning and Reasoning with Bayesian Network

• Preface
• 1 Introduction
  • 1.1 Automated Reasoning
  • 1.2 Degrees of Belief
  • 1.3 Probabilistic Reasoning
  • 1.4 Bayesian Networks
  • 1.5 What Is Not Covered in This Book
• 2 Propositional Logic
  • 2.1 Introduction
  • 2.2 Syntax of Propositional Sentences
  • 2.3 Semantics of Propositional Sentences
  • 2.4 The Monotonicity of Logical Reasoning
  • 2.5 Multivalued Variables
  • 2.6 Variable Instantiations and Related Notations
  • 2.7 Logical Forms
  • Bibliographic Remarks
  • 2.8 Exercises
• 3 Probability Calculus
  • 3.1 Introduction
  • 3.2 Degrees of Belief
  • 3.3 Updating Beliefs
  • 3.4 Independence
  • 3.5 Further Properties of Beliefs
  • 3.6 Soft Evidence
  • 3.7 Continuous Variables as Soft Evidence
  • Bibliographic Remarks
  • 3.8 Exercises
• 4 Bayesian Networks
  • 4.1 Introduction
  • 4.2 Capturing Independence Graphically
  • 4.3 Parameterizing the Independence Structure
  • 4.4 Properties of Probabilistic Independence
  • 4.5 A Graphical Test of Independence
  • 4.6 More on DAGs and Independence
• 4 Bayesian Networks (continued)
  • 4.7 Exercises
  • 4.8 Proofs
• 5 Building Bayesian Networks
  • 5.1 Introduction
  • 5.2 Reasoning with Bayesian Networks
  • 5.3 Modeling with Bayesian Networks
  • 5.4 Dealing with Large CPTs
  • 5.5 The Significance of Network Parameters
  • Bibliographic Remarks
  • 5.6 Exercises
• 6 Inference by Variable Elimination
  • 6.1 Introduction
  • 6.2 The Process of Elimination
  • 6.3 Factors
  • 6.4 Elimination as a Basis for Inference
  • 6.5 Computing Prior Marginals
  • 6.6 Choosing an Elimination Order
  • 6.7 Computing Posterior Marginals
  • 6.8 Network Structure and Complexity
  • 6.9 Query Structure and Complexity
  • 6.10 Bucket Elimination
  • Bibliographic Remarks
  • 6.11 Exercises
  • 6.12 Proofs
• 7 Inference by Factor Elimination
  • 7.1 Introduction
  • 7.2 Factor Elimination
  • 7.3 Elimination Trees
  • 7.4 Separators and Clusters
  • 7.5 A Message-Passing Formulation
  • 7.6 The Jointree Connection
  • 7.7 The Jointree Algorithm: A Classical View
  • Bibliographic Remarks
  • 7.8 Exercises
  • 7.9 Proofs
• 8 Inference by Conditioning
  • 8.1 Introduction
  • 8.2 Cutset Conditioning
  • 8.3 Recursive Conditioning
  • 8.4 Any-Space Inference
  • 8.5 Decomposition Graphs
  • 8.6 The Cache Allocation Problem
  • Bibliographic Remarks
• 8 Inference by Conditioning (continued)
  • 8.7 Exercises
  • 8.8 Proofs
• 9 Models for Graph Decomposition
  • 9.1 Introduction
  • 9.2 Moral Graphs
  • 9.3 Elimination Orders
  • 9.4 Jointrees
  • 9.5 Dtrees
  • 9.6 Triangulated Graphs
  • Bibliographic Remarks
  • 9.7 Exercises
  • 9.8 Lemmas
  • 9.9 Proofs
• 10 Most Likely Instantiations
  • 10.1 Introduction
  • 10.2 Computing MPE Instantiations
  • 10.3 Computing MAP Instantiations
  • Bibliographic Remarks
  • 10.4 Exercises
  • 10.5 Proofs
• 11 The Complexity of Probabilistic Inference
  • 11.1 Introduction
  • 11.2 Complexity Classes
  • 11.3 Showing Hardness
  • 11.4 Showing Membership
  • 11.5 Complexity of MAP on Polytrees
  • 11.6 Reducing Probability of Evidence to Weighted Model Counting
  • 11.7 Reducing MPE to W-MAXSAT
  • Bibliographic Remarks
  • 11.8 Exercises
  • 11.9 Proofs
• 12 Compiling Bayesian Networks
  • 12.1 Introduction
  • 12.2 Circuit Semantics
  • 12.3 Circuit Propagation
  • 12.4 Circuit Compilation
  • Bibliographic Remarks
  • 12.5 Exercises
  • 12.6 Proofs
• 13 Inference with Local Structure
  • 13.1 Introduction
  • 13.2 The Impact of Local Structure on Inference Complexity
  • 13.3 CNF Encodings with Local Structure
• 13 Inference with Local Structure (continued)
  • 13.4 Conditioning with Local Structure
  • 13.5 Elimination with Local Structure
  • Bibliographic Remarks
  • 13.6 Exercises
• 14 Approximate Inference by Belief Propagation
  • 14.1 Introduction
  • 14.2 The Belief Propagation Algorithm
  • 14.3 Iterative Belief Propagation
  • 14.4 The Semantics of IBP
  • 14.5 Generalized Belief Propagation
  • 14.6 Joingraphs
  • 14.7 Iterative Joingraph Propagation
  • 14.8 Edge-Deletion Semantics of Belief Propagation
  • Bibliographic Remarks
  • 14.9 Exercises
  • 14.10 Proofs
• 15 Approximate Inference by Stochastic Sampling
  • 15.1 Introduction
  • 15.2 Simulating a Bayesian Network
  • 15.3 Expectations
  • 15.4 Direct Sampling
  • 15.5 Estimating a Conditional Probability
  • 15.6 Importance Sampling
  • 15.7 Markov Chain Simulation
  • Bibliographic Remarks
  • 15.8 Exercises
  • 15.9 Proofs
• 16 Sensitivity Analysis
  • 16.1 Introduction
  • 16.2 Query Robustness
  • 16.3 Query Control
  • Bibliographic Remarks
  • 16.4 Exercises
  • 16.5 Proofs
• 17 Learning: The Maximum Likelihood Approach
  • 17.1 Introduction
  • 17.2 Estimating Parameters from Complete Data
  • 17.3 Estimating Parameters from Incomplete Data
  • 17.4 Learning Network Structure
  • 17.5 Searching for Network Structure
  • Bibliographic Remarks
  • 17.6 Exercises
  • 17.7 Proofs
• 18 Learning: The Bayesian Approach
  • 18.1 Introduction
  • 18.2 Meta-Networks
  • 18.3 Learning with Discrete Parameter Sets
  • 18.4 Learning with Continuous Parameter Sets
  • 18.5 Learning Network Structure
  • Bibliographic Remarks
  • 18.6 Exercises
  • 18.7 Proofs
• Appendices
  • A Notation
  • B Concepts from Information Theory
  • C Fixed Point Iterative Methods
  • D Constrained Optimization
• Bibliography
• Index