Probabilistic Graphical Models Principles and Techniques

Probabilistic Graphical Models Principles and Techniques

Daphne Koller

Nir Friedman

Press Cambridge, Massachusetts London, England

 As far as the laws of mathematics refer to reality, they are not certain, as far as they are certain, they do not refer to reality.Albert Einstein, When we try to pick out anything by itself we find that it is bound fast by a thousand invisible cords that cannot be broken, to everything in the universe. John Muir, I The actual science of logic is conversant at present only with things either certain, impossible, or entirely doubtful . .. Therefore the true logic fiJr this world is the calculus of probabilities, which takes account of the magnitude of the probability which is, or ought to be, in a reasonable mans mind. James Clerk Maxwell, The theory of probabilities is at bottom nothing but common sense reduced to calculus; it enables us to appreciate with exactness that which accurate minds feel with a sort of instinct for which ofttimes they are unable to account Pierre Simon Laplace, Misunderstanding of probability may be the greatest of all impediments to scientific literacy. Stephen Jay Gould

CONTENTS
 Cycles and Loops
Relevant Literature
Exercises
Representation
The Bayesian Network Representation
Exploiting Independence Properties
 Independent Random Variables
 The Conditional Parameterization
The Naive Bayes Model
Bayesian Networks
 The Student Example Revisited
 Basic Independencies in Bayesian Networks
 Graphs and Distributions
Independencies in Graphs
 D-separation
 Soundness and Completeness
 An Algorithm for d-Separation v
 I-Equivalence
From Distributions to Graphs
 Minimal I-Maps
 Perfect Maps
 Finding Perfect Maps *
Summary
Relevant Literature
Exercises
Undirected Graphical Models
The Misconception Example
Parameterization
 Factors -  Gibbs Distributions and Markov Networks
 Reduced Markov Networks
Markov Network Independencies
 Basic Independencies
 Independencies Revisited
 From Distributions to Graphs
Parameterization Revisited
 Finer-Grained Parameterization
 Overparameterization
Bayesian Networks and Markov Networks
 From Bayesian Networks to Markov Networks
 From Markov Networks to Bayesian Networks
Chordal Graphs
Partially Directed Models
 Conditional Random Fields
 Chain Graph Models *
Summary and Discussion
Relevant Literature
Exercises
Local Probabilistic Models
Tabular CPDs
Deterministic CPDs
 Representation
 Independencies
Context-Specific CPDs
 Representation
 Independencies
Independence of Causal Influence
 The Noisy-Or Model
 Generalized Linear Models
 The General Formulation
 Independencies
Continuous Variables
 Hybrid Models
Conditional Bayesian Networks
Summary
Relevant Literature
Exercises
Template-Based Representations
Introduction
Temporal Models
 Basic Assumptions
Dynamic Bayesian Networks
 State-Observation Models
Template Variables and Template Factors
Directed Probabilistic Models for Object-Relational Domains
 Plate Models
 Probabilistic Relational Models
Undirected Representation
Structural Uncertainty *
 Relational Uncertainty
 Object Uncertainty
Summary
Relevant Literature
Exercises
Gaussian Network Models
Multivariate Gaussians
 Basic Parameterization
 Operations on Gaussians
 Independencies in Gaussians
Gaussian Bayesian Networks
Gaussian Markov Random Fields
Summary
Relevant Literature
Exercises
The Exponential Family
Introduction
Exponential Families
 Linear Exponential Families
Factored Exponential Families
 Product Distributions
 Bayesian Networks
Entropy and Relative Entropy
 Entropy.
 Relative Entropy
Projections
 Comparison
 M-Projections
 I-Projections
Summary
Relevant Literature
Exercises
Inference
Exact Inference: Variable Elimination
Analysis of Complexity
 Analysis of Exact Inference
 Analysis of Approximate Inference
Variable Elimination: The Basic Ideas
Variable Elimination
 Basic Elimination
 Dealing with Evidence
Complexity and Graph Structure: Variable Elimination
 Simple Analysis
 Graph-Theoretic Analysis
 Finding Elimination Orderings *
Conditioning * .
 The Conditioning Algorithm
 Conditioning and Variable Elimination
 Graph-Theoretic Analysis
 Improved Conditioning
Inference with Structured CPDs *
 Independence of Causal Influence
 Context-Specific Independence
 Discussion I
Summary and Discussion
Relevant Literature
Exercises
Exact Inference: Clique Trees
Variable Elimination and Clique Trees
 Cluster Graphs
 Clique Trees
 Message Passing: Sum Product
 Variable Elimination in a Clique Tree
 Clique Tree Calibration
 A Calibrated Clique Tree as a Distribution
 Message Passing: Belief Update
 Message Passing with Division
 Equivalence of Sum-Product and Belief Update Messages
 Answering Queries
 Constructing a Clique Tree
 I Clique Trees from Variable Elimination
 Clique Trees from Chordal Graphs
 Summary
 Relevant Literature
 Exercises
Inference as Optimization
 Introduction
 Exact Inference Revisited *
 The Energy Functional
 _ . Optimizing the Energy Functional
 Exact Inference as Optimization
 Fixed-Point Characterization
 Inference as Optimization
 Propagation-Based Approximation
 . A Simple Example
 Cluster-Graph Belief Propagation
 Properties of Cluster-Graph Belief Propagation
 Analyzing Convergence * _ -
 Constructing Cluster Graphs
________________________________________
Page
. Variational Analysis
 Other Entropy Approximations *
 Discussion
Propagation with Approximate Messages *
 Factorized Messages
 Approximate Message Computation
 Inference with Approximate Messages
 Expectation Propagation
 Variational Analysis
 Discussion
Structured Variational Approximations
 The Mean Field Approximation v
 Structured Approximations
 Local Variational Methods *
Summary and Discussion
Relevant Literature
Exercises
Particle-Based Approximate Inference
Forward Sampling
 Sampling from a Bayesian Network -
 Analysis of Error
 Conditional Probability Queries
Likelihood Weighting and Importance Sampling
 Likelihood Weighting: Intuition
 . Importance Sampling
 Importance Sampling for Bayesian Networks
 Importance Sampling Revisited
Markov Chain Monte Carlo Methods
 Gibbs Sampling Algorithm
 Markov Chains
 Gibbs Sampling Revisited
 A Broader Class of Markov Chains *
 Using a Markov Chain
Collapsed Particles
 Collapsed Likelihood Weighting *
 Collapsed MCMC
Deterministic Search Methods *
Summary
Relevant Literature
Exercises
MAP Inference
Overview
 Computational Complexity
 Overview of Solution Methods
Variable Elimination for (Marginal) MAP
 Max-Product Variable Elimination
 Finding the Most Probable Assignment
 Variable Elimination for Marginal MAP *
Max-Product in Clique Trees
 Computing -Max-Marginas
 Message Passing as Reparameterization
 Decoding Max-Marginals
Max-Product Belief Propagation in Loopy Cluster Graphs
 Standard Max-Product Message Passing
 Max-Product BP with Counting Numbers *
 Discussion
MAP as a Linear Optimization Problem *
 The Integer Program Formulation
 Linear Programming Relaxation
 Low-Temperature Limits
Using Graph Cuts for MAP
 Inference Using Graph Cuts
 Nonbinary Variables .
Local Search Algorithms * .
Summary
Relevant Literature
Exercises
Inference in Hybrid Networks
Introduction
 Challenges
 Discretization
 Overview
Variable Elimination in GaussianNetworks
 Canonical Forms
 Sum-Product =Algorithms
 Gaussian Belief Propagation
Hybrid Networks .
 The Difficulties
 Factor Operations for Hybrid Gaussian Networks
 EP for CLG Networks =
 An Exact CLG Algorithm *
Nonlinear Dependencies
I . Linearization
 Expectation Propagation with Gaussian Approximation
Particle-Based Approximation Methods
 Sampling in Continuous Spaces
 Forward Sampling in Bayesian Networlcs
MCMC Methods
 Collapsed Particles
 Nonparametric Message-Passing
Summary and Discussion
Relevant Literature
Exercises
 Inference in Temporal Models
Inference Tasks
Exact Inference
 Filtering in State-Observation Models
Filtering as Clique Tree Propagation
 Clique Tree Inference in DBNs
 Entanglement
Approximate Inference
 Key Ideas
 Factored Belief State Methods
 Particle Filtering
 Deterministic Search Techniques
Hybrid DBNs
 Continuous Models
 Hybrid Models
Summary
Relevant Literature
Exercises
III Learning
 Learning Graphical Models: Overview
Motivation
Goals of Learning
 Density Estimation
 Specific Prediction Tasks
 Knowledge Discovery
Learning as Optimization
 Empirical Risk and Overfitting
 Discriminative versus Generative Training
Learning Tasks
 Model Constraints
 Data Observability
 Taxonomy of Learning Tasks
Relevant Literature
 Parameter Estimation
Maximum Likelihood Estimation
 The Thumbtack Example
 The Maximum Likelihood Principle
 MLE for Bayesian Networks
 A Simple Example
 Global Likelihood Decomposition
 Table-CPDs
 Gaussian Bayesian Networks *
 Maximum Likelihood Estimation as M-Projection *
 Bayesian Parameter Estimation
 The Thumbtack Example Revisited
 Priors and Posteriors
 Bayesian Parameter Estimation in Bayesian Networks
 Parameter Independence and Global Decomposition
 Local Decomposition
 Priors for Bayesian Network Learning
 MAP Estimation *
 Learning Models with Shared Parameters
 Global Parameter Sharing
 Local Parameter Sharing
 Bayesian Inference with Shared Parameters
 Hierarchical Priors *
 Generalization Analysis *
 Asymptotic Analysis
 PAC-Bounds
 Summary
 Relevant Literature
 Exercises
Structure Learning in Bayesian Networks
 Introduction -
 Problem Definition
 Overview of Methods
 Constraint-Based Approaches
 General Framework
 Independence Tests
 Structure Scores
 Likelihood Scores
 Bayesian Score
 Marginal Likelihood for a Single Variable
 Bayesian Score for Bayesian Networks
 Understanding the Bayesian Score
 Priors
 Score Equivalence *
 Structure Search
 Learning Tree-Structured Networks

 Known Order
 General Graphs
 Learning with Equivalence Classes *
Bayesian Model Averaging *
 Basic Theory
 Model Averaging Given an Order
 The General Case
Learning Models with Additional Structure
 Learning with Local Structure
 Learning Template Models
Summary and Discussion
Relevant Literature
Exercises
 Partially Observed Data
Foundations
 Likelihood of Data and Observation Models
 Decoupling of Observation Mechanism
 The Likelihood Function
 Identifiability
Parameter Estimation
 Gradient Ascent
 Expectation Maximization (EM)
 Comparison: Gradient Ascent versus EM
 Approximate Inference *
Bayesian Learning with Incomplete Data *
 Overview
 MCMC Sampling
 Variational Bayesian Learning
Structure Learning
 Scoring Structures
 Structure Search
 I Structural EM
Learning Models with Hidden Variables
 Information Content of Hidden Variables
 Determining the Cardinality
 Introducing Hidden Variables
Summary
Relevant Literature
Exercises
 Learning Undirected Models
Overview
 The Likelihood Function
 An Example
 Form of the Likelihood Function
 Properties of the Likelihood Function
Maximum (Conditional) Likelihood Parameter Estimation
 Maximum Likelihood Estimation
 Conditionally Trained Models
 Learning with Missing Data
 Maximum Entropy and Maximum Likelihood *
Parameter Priors and Regularization
 Local Priors
 Global Priors
Learning with Approximate Inference
 Belief Propagation
 MAP-Based Learning *
Alternative Objectives
 Pseudolikelihood and Its Generalizations
 Contrastive Optimization Criteria
Structure Learning
 Structure Learning Using Independence Tests
 Score-Based Learning: Hypothesis Spaces
 Objective Functions
 Optimization Task _
 Evaluating Changes to the Model
Summary
Relevant Literature
 Exercises
IV Actions and Decisions
 Causality
Motivation and Overview ,
 Conditioning and Intervention
 Correlation and Causation
Causal Models
Structural Causal Identifiability
 Query Simplification Rules
 Iterated Query Simplification
Mechanisms and Response Variables *
Partial Identifiability in Functional Causal Models *
Counterfactual Queries *
 Twinned Networks
 Bounds on Counterfactual Queries
Learning Causal Models
 Learning Causal Models without Confounding Factors
 Learning from Interventional Data
Dealing with Latent Variables *
 Learning Functional Causal Models *
Summary
Relevant Literature
Exercises
Utilities and Decisions
Foundations: Maximizing Expected Utility
 Decision Making Under Uncertainty
 Theoretical Justification *
Utility Curves
 Utility of Money
 Attitudes TowardRisk
 Rationality
Utility Elicitation
 Utility Elicitation Procedures
 Utility of Human Life
Utilities of Complex Outcomes
 Preference and Utility Independence, *
 Additive Independence Properties
Summary
Relevant Literature
Exercises
Structured Decision Problems
Decision Trees
 Representation
 Backward Induction Algorithm
Influence Diagrams
 Basic Representation
 Decision Rules
 Time and Recall
 Semantics and Optimality Criterion
Backward Induction in Influence Diagrams
 Decision Trees for Influence Diagrams
 Sum-Max-Sum Rule
Computing Expected Utilities
 Simple Variable Elimination
 Multiple Utility Variables: Simple Approaches
 Generalized Variable Elimination *
Optimization in Influence Diagrams
 Optimizing a Single Decision Rule
 Iterated Optimization Algorithm
 Strategic Relevance and Global Optimality *
Ignoring Irrelevant Information *
 Value of Information
 Single Observations
 Multiple Observations
 Summary
 Relevant Literature
 Exercises
 Epilogue
A Background Material
A Information Theory
All Compression and Entropy
A Conditional Entropy and Information
A Relative Entropy and Distances Between Distributions
A. Convergence Bounds
A. Central Limit Theorem
A Convergence Bounds
A Algorithms and Algorithmic Complexity
A Basic Graph Algorithms
A Analysis of Algorithmic Complexity
A Dynamic Programming
A Complexity Theory
AA Combinatorial Optimization and Search
A Optimization Problems
A Local Search
A Branch and Bound Search
A Continuous Optimization
A Characterizing Optima of a Continuous Function
A. Gradient Ascent Methods
A. Constrained Optimization
A. Convex Duality
Bibliography
Notation Index
Qubject Index