Adnan Darwiche
University of California, Los Angeles

Cambridge University Press 2009

First published in print format
ISBN-13 978-0-521-88438-9
ISBN-13 978-0-511-50728-1
© Adnan Darwiche 2009
2009

1 Introduction 1
1.1 Automated Reasoning 1
1.2 Degrees of Belief 4
1.3 Probabilistic Reasoning 6
1.4 Bayesian Networks 8
1.5 What Is Not Covered in This Book 12
2 Propositional Logic 13
2.1 Introduction 13
2.2 Syntax of Propositional Sentences 13
2.3 Semantics of Propositional Sentences 15
2.4 The Monotonicity of Logical Reasoning 18
2.5 Multivalued Variables 19
2.6 Variable Instantiations and Related Notations 20
2.7 Logical Forms 21
Bibliographic Remarks 24
2.8 Exercises 25
3 Probability Calculus 27
3.1 Introduction 27
3.2 Degrees of Belief 27
3.3 Updating Beliefs 30
3.4 Independence 34
3.5 Further Properties of Beliefs 37
3.6 Soft Evidence 39
3.7 Continuous Variables as Soft Evidence 46
Bibliographic Remarks 48
3.8 Exercises 49
4 Bayesian Networks 53
4.1 Introduction 53
4.2 Capturing Independence Graphically 53
4.3 Parameterizing the Independence Structure 56
4.4 Properties of Probabilistic Independence 58
4.5 A Graphical Test of Independence 63
4.6 More on DAGs and Independence 68
vBibliographic Remarks 71
4.7 Exercises 72
4.8 Proofs 75
5 Building Bayesian Networks 76
5.1 Introduction 76
5.2 Reasoning with Bayesian Networks 76
5.3 Modeling with Bayesian Networks 84
5.4 Dealing with Large CPTs 114
5.5 The Significance of Network Parameters 119
Bibliographic Remarks 121
5.6 Exercises 122
6 Inference by Variable Elimination 126
6.1 Introduction 126
6.2 The Process of Elimination 126
6.3 Factors 128
6.4 Elimination as a Basis for Inference 131
6.5 Computing Prior Marginals 133
6.6 Choosing an Elimination Order 135
6.7 Computing Posterior Marginals 138
6.8 Network Structure and Complexity 141
6.9 Query Structure and Complexity 143
6.10 Bucket Elimination 147
Bibliographic Remarks 148
6.11 Exercises 148
6.12 Proofs 151
7 Inference by Factor Elimination 152
7.1 Introduction 152
7.2 Factor Elimination 153
7.3 Elimination Trees 155
7.4 Separators and Clusters 157
7.5 A Message-Passing Formulation 159
7.6 The Jointree Connection 164
7.7 The Jointree Algorithm: A Classical View 166
Bibliographic Remarks 172
7.8 Exercises 173
7.9 Proofs 176
8 Inference by Conditioning 178
8.1 Introduction 178
8.2 Cutset Conditioning 178
8.3 Recursive Conditioning 181
8.4 Any-Space Inference 188
8.5 Decomposition Graphs 189
8.6 The Cache Allocation Problem 192
Bibliographic Remarks 196
8.7 Exercises 197
8.8 Proofs 198
9 Models for Graph Decomposition 202
9.1 Introduction 202
9.2 Moral Graphs 202
9.3 Elimination Orders 203
9.4 Jointrees 216
9.5 Dtrees 224
9.6 Triangulated Graphs 229
Bibliographic Remarks 231
9.7 Exercises 232
9.8 Lemmas 234
9.9 Proofs 236
10 Most Likely Instantiations 243
10.1 Introduction 243
10.2 Computing MPE Instantiations 244
10.3 Computing MAP Instantiations 258
Bibliographic Remarks 264
10.4 Exercises 265
10.5 Proofs 267
11 The Complexity of Probabilistic Inference 270
11.1 Introduction 270
11.2 Complexity Classes 271
11.3 Showing Hardness 272
11.4 Showing Membership 274
11.5 Complexity of MAP on Polytrees 275
11.6 Reducing Probability of Evidence to Weighted Model Counting 276
11.7 Reducing MPE to W-MAXSAT 280
Bibliographic Remarks 283
11.8 Exercises 283
11.9 Proofs 284
12 Compiling Bayesian Networks 287
12.1 Introduction 287
12.2 Circuit Semantics 289
12.3 Circuit Propagation 291
12.4 Circuit Compilation 300
Bibliographic Remarks 306
12.5 Exercises 306
12.6 Proofs 309
13 Inference with Local Structure 313
13.1 Introduction 313
13.2 The Impact of Local Structure on Inference Complexity 313
13.3 CNF Encodings with Local Structure
13.4 Conditioning with Local Structure 323
13.5 Elimination with Local Structure 326
Bibliographic Remarks 336
13.6 Exercises 337
14 Approximate Inference by Belief Propagation 340
14.1 Introduction 340
14.2 The Belief Propagation Algorithm 340
14.3 Iterative Belief Propagation 343
14.4 The Semantics of IBP 346
14.5 Generalized Belief Propagation 349
14.6 Joingraphs 350
14.7 Iterative Joingraph Propagation 352
14.8 Edge-Deletion Semantics of Belief Propagation 354
Bibliographic Remarks 364
14.9 Exercises 365
14.10 Proofs 370
15 Approximate Inference by Stochastic Sampling 378
15.1 Introduction 378
15.2 Simulating a Bayesian Network 378
15.3 Expectations 381
15.4 Direct Sampling 385
15.5 Estimating a Conditional Probability 392
15.6 Importance Sampling 393
15.7 Markov Chain Simulation 401
Bibliographic Remarks 407
15.8 Exercises 408
15.9 Proofs 411
16 Sensitivity Analysis 417
16.1 Introduction 417
16.2 Query Robustness 417
16.3 Query Control 427
Bibliographic Remarks 433
16.4 Exercises 434
16.5 Proofs 435
17 Learning: The Maximum Likelihood Approach 439
17.1 Introduction 439
17.2 Estimating Parameters from Complete Data 441
17.3 Estimating Parameters from Incomplete Data 444
17.4 Learning Network Structure 455
17.5 Searching for Network Structure 461
Bibliographic Remarks 466
17.6 Exercises 467
17.7 Proofs 470
18 Learning: The Bayesian Approach 477
18.1 Introduction 477
18.2 Meta-Networks 479
18.3 Learning with Discrete Parameter Sets 482
18.4 Learning with Continuous Parameter Sets 489
18.5 Learning Network Structure 498
Bibliographic Remarks 504
18.6 Exercises 505
18.7 Proofs 508
A Notation 515
B Concepts from Information Theory 517
C Fixed Point Iterative Methods 520
D Constrained Optimization 523
Bibliography 527
Index 541