Probabilistic Graphical Models: Principles and Techniques (Adaptive Computation and Machine Learning) (Adaptive Computation and Machine Learning Series) [Hardcover]

Stanford professor, Daphne Koller, and her co-author, Professor Nir Friedman, employed graphical models to motivate thoroughgoing explorations of representation, inference and learning in both Bayesian networks and Markov networks. They do their own bidding at the book's web page, [...], by giving readers a panoramic view of the book in an introductory chapter and a Table of Contents. On the same page, there is a link to an extensive Errata file which lists all the known errors and corrections made in subsequent printings of the book - all the corrections had been incorporated into the copy I have. The authors painstakingly provided necessary background materials from both probability theory and graph theory in the second chapter. Furthermore, in an Appendix, more tutorials are offered on information theory, algorithms and combinatorial optimization. This book is an authoritative extension of Professor Judea Pearl's seminal work on developing the Bayesian Networks framework for causal reasoning and decision making under uncertainty. Before this book was published, I sent an e-mail to Professor Koller requesting some clarification of her paper on object-oriented Bayesian networks; she was most generous in writing an elaborate reply with deliberate speed.

I purchased this book as a text for the Stanford online course in PGM, which as of this writing is at least six weeks late in starting. While waiting for the course, I've tried to struggle through the first chapters on my own, with zero success. After wading through about the first third of the book, and skimming the rest, I must say that if I had to implement a program using PGM to solve some problem, I wouldn't have the foggiest idea how to even begin.

This book may well be a good reference for someone who already has a deep background in machine learning & artificial intelligence, but it emphatically is not of any use to the novice in the field(1). It contains many proofs of theorems, numerous long-winded "explanations" (most of which I don't understand), some algorithms set out in an obfuscated format(2) that I thought had died out about the time I got my BS, but (as far as I've been able to discover) not one line of actual code, nor any implementation, even of the simple "Hello, World" sort.

(1) For background, I have a couple of decades of programming experience, most of it in numerical modelling and parallel applications.

(2) A LaTeX cheat sheet for the symbols used would be a useful addition to future editions of the text.

(Shortened, since it was even more obnoxiously long). Note that each chapter ends with Summary, Relevant Literature and Exercises.

2 Foundations 15
2.1 Probability Theory 15
2.2 Graphs 34
I Representation 43
3 The Bayesian Network Representation 45
3.1 Exploiting Independence Properties 45
3.2 Bayesian Networks 51
3.3 Independencies in Graphs 68
3.4 From Distributions to Graphs 78
4 Undirected Graphical Models 103
4.1 The Misconception Example 103
4.2 Parameterization 106
4.3 Markov Network Independencies 114
4.4 Parameterization Revisited 122
4.5 Bayesian Networks and Markov Networks 134
4.6 Partially Directed Models 142
5 Local Probabilistic Models 157
5.1 Tabular CPDs 157
5.2 Deterministic CPDs 158
5.3 Context-Specific CPDs 162
5.4 Independence of Causal Influence 175
5.5 Continuous Variables 185
5.6 Conditional Bayesian Networks 191
6 Template-Based Representations 199
6.1 Introduction 199
6.2 Temporal Models 200
6.3 Template Variables and Template Factors 212
6.4 Directed Probabilistic Models for Object-Relational Domains 216
6.5 Undirected Representation 228
6.6 Structural Uncertainty 232
7 Gaussian Network Models 247
7.1 Multivariate Gaussians 247
7.2 Gaussian Bayesian Networks 251
7.3 Gaussian Markov Random Fields 254
8 The Exponential Family 261
8.1 Introduction 261
8.2 Exponential Families 261
8.3 Factored Exponential Families 266
8.4 Entropy and Relative Entropy 269
8.5 Projections 273
II Inference 285
9 Exact Inference: Variable Elimination 287
9.1 Analysis of Complexity 288
9.2 Variable Elimination: The Basic Ideas 292
9.3 Variable Elimination 296
9.4 Complexity and Graph Structure: Variable Elimination 306
9.5 Conditioning 315
9.6 Inference with Structured CPDs 325
10 Exact Inference: Clique Trees 345
10.1 Variable Elimination and Clique Trees 345
10.2 Message Passing: Sum Product 348
10.3 Message Passing: Belief Update 364
10.4 Constructing a Clique Tree 372
11 Inference as Optimization 381
11.1 Introduction 381
11.2 Exact Inference as Optimization 386
11.3 Propagation-Based Approximation 391
11.4 Propagation with Approximate Messages 430
11.5 Structured Variational Approximations 448
12 Particle-Based Approximate Inference 487
12.1 Forward Sampling 488
12.2 Likelihood Weighting and Importance Sampling 492
12.3 Markov Chain Monte Carlo Methods 505
12.4 Collapsed Particles 526
12.5 Deterministic Search Methods 536
13 MAP Inference 551
13.1 Overview 551
13.2 Variable Elimination for (Marginal) MAP 554
13.3 Max-Product in Clique Trees 562
13.4 Max-Product Belief Propagation in Loopy Cluster Graphs 567
13.5 MAP as a Linear Optimization Problem 577
13.6 Using Graph Cuts for MAP 588
13.7 Local Search Algorithms 595
14 Inference in Hybrid Networks 605
14.1 Introduction 605
14.2 Variable Elimination in Gaussian Networks 608
14.3 Hybrid Networks 615
14.4 Nonlinear Dependencies 630
14.5 Particle-Based Approximation Methods 642
15 Inference in Temporal Models 651
15.1 Inference Tasks 652
15.2 Exact Inference 653
15.3 Approximate Inference 660
15.4 Hybrid DBNs 675
III Learning 695
16 Learning Graphical Models: Overview 697
16.1 Motivation 697
16.2 Goals of Learning 698
16.3 Learning as Optimization 702
16.4 Learning Tasks 711
17 Parameter Estimation 717
17.1 Maximum Likelihood Estimation 717
17.2 MLE for Bayesian Networks 722
17.3 Bayesian Parameter Estimation 733
17.4 Bayesian Parameter Estimation in Bayesian Networks 741
17.5 Learning Models with Shared Parameters 754
17.6 Generalization Analysis 769
18 Structure Learning in Bayesian Networks 783
18.1 Introduction 783
18.2 Constraint-Based Approaches 786
18.3 Structure Scores 790
18.4 Structure Search 807
18.5 Bayesian Model Averaging 824
18.6 Learning Models with Additional Structure 832
19 Partially Observed Data 849
19.1 Foundations 849
19.2 Parameter Estimation 862
19.3 Bayesian Learning with Incomplete Data 897
19.4 Structure Learning 908
19.5 Learning Models with Hidden Variables 925
20 Learning Undirected Models 943
20.1 Overview 943
20.2 The Likelihood Function 944
20.3 Maximum (Conditional) Likelihood Parameter Estimation 949
20.4 Parameter Priors and Regularization 958
20.5 Learning with Approximate Inference 961
20.6 Alternative Objectives 969
20.7 Structure Learning 978
IV Actions and Decisions 1007
21 Causality 1009
21.1 Motivation and Overview 1009
21.2 Causal Models 1014
21.3 Structural Causal Identifiability 1017
21.4 Mechanisms and Response Variables 1026
21.5 Partial Identifiability in Functional Causal Models 1031
21.6 Counterfactual Queries 1034
21.7 Learning Causal Models 1039
22 Utilities and Decisions 1057
22.1 Foundations: Maximizing Expected Utility 1057
22.2 Utility Curves 1062
22.3 Utility Elicitation 1066
22.4 Utilities of Complex Outcomes 1069
23 Structured Decision Problems 1083
23.1 Decision Trees 1083
23.2 Influence Diagrams 1086
23.3 Backward Induction in Influence Diagrams 1093
23.4 Computing Expected Utilities 1098
23.5 Optimization in Influence Diagrams 1105
23.6 Ignoring Irrelevant Information 1117
23.7 Value of Information 1119
A Background Material 1135
A.1 Information Theory 1135
A.2 Convergence Bounds 1141
A.3 Algorithms and Algorithmic Complexity 1144
A.4 Combinatorial Optimization and Search 1152
A.5 Continuous Optimization 1159