Bayesian Artificial Intelligence

Contents......Page 8
List of Figures......Page 18
List of Tables......Page 22
Preface......Page 24
About the Authors......Page 27
I. Probabilistic Reasoning......Page 28
1.1 Reasoning under uncertainty......Page 30
1.2 Uncertainty in AI......Page 31
1.3 Probability calculus......Page 32
1.3.1 Conditional probability theorems......Page 35
1.3.2 Variables......Page 36
1.4 Interpretations of probability......Page 37
1.5.1 Bayes' theorem......Page 39
1.5.2 Betting and odds......Page 41
1.5.3 Expected utility......Page 42
1.5.4 Dutch books......Page 43
1.12 Problems......Page 52
1.6 The goal of Bayesian AI......Page 48
1.8 Are Bayesian networks Bayesian?......Page 49
1.9 Summary......Page 50
1.11 Technical notes......Page 51
2.2 Bayesian network basics......Page 56
2.2.1 Nodes and values......Page 57
2.2.2 Structure......Page 58
2.2.3 Conditional probabilities......Page 59
2.3 Reasoning with Bayesian networks......Page 60
2.3.1 Types of reasoning......Page 61
2.3.2 Types of evidence......Page 62
2.3.3 Reasoning with numbers......Page 63
2.4.2 Pearl's network construction algorithm......Page 64
2.4.3 Compactness and node ordering......Page 65
2.4.4.1 Causal chains......Page 66
2.4.4.3 Common effects......Page 67
2.4.5 d-separation......Page 68
2.5.1 Earthquake......Page 70
2.5.3 Asia......Page 71
2.7 Bibliographic notes......Page 72
2.8 Problems......Page 77
3.1 Introduction......Page 82
3.2.1 Two node network......Page 83
3.2.2 Three node chain......Page 84
3.3 Exact inference in polytrees......Page 85
3.3.1 Kim and Pearl's message passing algorithm......Page 86
3.3.2 Message passing example......Page 89
3.4 Inference with uncertain evidence......Page 91
3.4.1 Using a virtual node......Page 92
3.4.3 Multiple virtual evidence......Page 94
3.5.1 Clustering methods......Page 96
3.5.2 Junction trees......Page 98
3.6 Approximate inference with stochastic simulation......Page 101
3.6.1 Logic sampling......Page 102
3.6.2 Likelihood weighting......Page 103
3.6.5 Assessing approximate inference algorithms......Page 105
3.7.2 Probability of evidence......Page 107
3.8.1 Observation vs. intervention......Page 108
3.8.2 Defining an intervention......Page 110
3.8.3 Categories of intervention......Page 111
3.8.4 Modeling effectiveness......Page 113
3.8.5 Representing interventions......Page 114
3.10 Bibliographic notes......Page 116
3.11 Problems......Page 118
4.2 Utilities......Page 124
4.3.1 Node types......Page 126
4.3.2 Football team example......Page 127
4.3.3 Evaluating decision networks......Page 128
4.3.4 Information links......Page 129
4.3.6 Types of actions......Page 131
4.4.1 Test-action combination......Page 133
4.4.2 Real estate investment example......Page 134
4.4.3 Evaluation using a decision tree model......Page 136
4.4.4 Value of information......Page 138
4.5 Dynamic Bayesian networks......Page 139
4.5.1 Nodes, structure and CPTs......Page 140
4.5.2 Reasoning......Page 142
4.5.3 Inference algorithms for DBNs......Page 144
4.6 Dynamic decision networks......Page 145
4.6.1 Mobile robot example......Page 146
4.7.1 OOBN basics......Page 147
4.7.2 OOBN inference......Page 149
4.7.3 OOBN examples......Page 150
4.7.4 "is-A" relationship: Class inheritance......Page 152
4.8 Summary......Page 153
4.10 Problems......Page 154
5.1 Introduction......Page 160
5.2.1 Types of reasoning......Page 161
5.2.2 Medical Applications......Page 162
5.2.3 Ecological and environmental applications......Page 165
5.2.4 Other applications......Page 167
5.3.1 Epidemiology models for cardiovascular heart disease......Page 172
5.3.2.1 Structure......Page 173
5.3.2.2 Parameters and discretization......Page 174
5.3.3.2 Parameters and discretization......Page 175
5.3.3.3 Points......Page 177
5.3.3.4 Target variables......Page 178
5.4 Goulburn Catchment Ecological Risk Assessment......Page 179
5.4.1 Background: Goulburn Catchment......Page 180
5.4.2 The Bayesian network......Page 181
5.4.2.2 Parameterization......Page 182
5.5.1 Five-card stud poker......Page 183
5.5.2.1 Structure......Page 185
5.5.2.4 Belief updating......Page 186
5.5.2.6 The utility node......Page 187
5.5.3 Betting with randomization......Page 188
5.5.5 Experimental evaluation......Page 189
5.6.1 The domain......Page 190
5.6.2.1 Nodes and values......Page 191
5.6.2.2 Structure and CPTs......Page 192
5.6.4 An extended sensor model......Page 194
5.7 A Nice Argument Generator (NAG)......Page 196
5.7.1 NAG architecture......Page 197
5.7.2 Example: An asteroid strike......Page 199
5.7.3 The psychology of inference......Page 200
5.7.4 Example: The asteroid strike continues......Page 201
5.7.5 The future of argumentation......Page 202
5.8 Summary......Page 203
5.9 Bibliographic notes......Page 204
5.10 Problems......Page 205
II. Learning Causal Models......Page 208
6.2.1 Parameterizing a binomial model......Page 212
6.2.1.1 The beta distribution......Page 213
6.2.2 Parameterizing a multinomial model......Page 215
6.3 Incomplete data......Page 217
6.3.1 The Bayesian solution......Page 218
6.3.2.1 Gibbs sampling......Page 219
6.3.2.2 Expectation maximization......Page 221
6.4 Learning local structure......Page 223
6.4.2 Noisy-or connections......Page 224
6.4.3 Classification trees and graphs......Page 225
6.4.4 Logit models......Page 227
6.6 Bibliographic notes......Page 228
6.8 Problems......Page 229
7.1 Introduction......Page 232
7.2 Naive Bayes models......Page 233
7.3 Semi-naive Bayes models......Page 235
7.4 Ensemble Bayes prediction......Page 236
7.5.1 Predictive accuracy......Page 238
7.5.2 Bias and variance......Page 240
7.5.3 ROC curves and AUC......Page 242
7.5.4 Calibration......Page 244
7.5.5 Expected value......Page 247
7.5.6 Proper scoring rules......Page 249
7.5.7 Information reward......Page 250
7.5.8 Bayesian information reward......Page 252
7.7 Bibliographic notes......Page 254
7.8 Technical notes......Page 255
7.9 Problems......Page 256
8.1 Introduction......Page 258
8.2 Path models......Page 260
8.2.1 Wright's first decomposition rule......Page 262
8.2.2 Parameterizing linear models......Page 265
8.2.3 Learning linear models is complex......Page 266
8.3 Constraint-based learners......Page 268
8.3.1 Markov equivalence......Page 271
8.3.2 PC algorithm......Page 274
8.3.3 Causal discovery versus regression......Page 276
8.6 Technical notes......Page 277
8.7 Problems......Page 279
9.1 Introduction......Page 282
9.2 Cooper and Herskovits's K2......Page 283
9.2.1 Learning variable order......Page 285
9.3 MDL causal discovery......Page 286
9.3.1 Lam and Bacchus's MDL code for causal models......Page 288
9.3.2 Suzuki's MDL code for causal discovery......Page 290
9.4 Metric pattern discovery......Page 291
9.5 CaMML: Causal discovery via MML......Page 292
9.5.1 An MML code for causal structures......Page 293
9.5.1.1 Totally ordered models (TOMs)......Page 294
9.5.2 An MML metric for linear models......Page 295
9.6.1 Genetic algorithm (GA) search......Page 296
9.6.2 Metropolis search......Page 297
9.6.3 Expert priors......Page 299
9.6.4 An MML metric for discrete models......Page 301
9.6.5 Learning hybrid models......Page 302
9.7.1 The causal Markov condition......Page 303
9.7.2 A lack of faith......Page 306
9.7.3 Learning in high-dimensional spaces......Page 311
9.8.1 Qualitative evaluation......Page 312
9.8.2 Quantitative evaluation......Page 313
9.8.3 Causal Kullback-Leibler (CKL)......Page 314
9.10 Bibliographic notes......Page 316
9.12 Problems......Page 317
III. Knowledge Engineering......Page 320
10.1.1 Bayesian network modeling tasks......Page 324
10.2.1 KEBN lifecycle model......Page 326
10.2.2 Prototyping and spiral KEBN......Page 327
10.2.3 Boneh's KEBN process......Page 329
10.2.5 Process management......Page 330
10.3 Stage 1: BN structure......Page 331
10.3.1 Nodes and values......Page 332
10.3.2 Common modeling mistakes: nodes and values......Page 334
10.3.3 Causal relationships......Page 338
10.3.4 Dependence and independence relationships......Page 339
10.3.5 Other relationships......Page 344
10.3.6 Controlling the number of arcs......Page 346
10.3.7 Combining discrete and continuous variables......Page 347
10.3.9 Common modeling mistakes: arcs......Page 348
10.3.10 Structure evaluation......Page 350
10.4 Stage 2: Probability parameters......Page 351
10.4.1 Parameter sources......Page 352
10.4.2 Probability elicitation for discrete variables......Page 354
10.4.4 Support for probability elicitation......Page 357
10.4.5 Local structure......Page 359
10.4.6 Case-based evaluation......Page 361
10.4.7 Validation methods......Page 362
10.4.8 Sensitivity analysis......Page 364
10.5 Stage 3: Decision structure......Page 368
10.6 Stage 4: Utilities (preferences)......Page 369
10.6.1 Sensitivity of decisions......Page 370
10.7 Modeling example: missing car......Page 374
10.8.1 Divide-and-conquer......Page 380
10.9 Adaptation......Page 381
10.9.1 Adapting parameters......Page 382
10.11 Bibliographic notes......Page 384
10.12 Problems......Page 385
11.2.1 The initial prototype......Page 388
11.2.3 Adaptation to Texas Hold'em, 2003......Page 390
11.2.4 Hybrid model, 2003......Page 392
11.2.7 KEBN aspects......Page 395
11.3 An intelligent tutoring system for decimal understanding......Page 396
11.3.1 The ITS domain......Page 397
11.3.2 ITS system architecture......Page 398
11.3.3 Expert elicitation......Page 400
11.3.4 Automated methods......Page 407
11.3.5 Field trial evaluation......Page 409
11.3.6 KEBN aspects......Page 410
11.4.1 Conceptual modeling......Page 411
11.4.2 The KEBN process used for parameterization......Page 412
11.4.3 Parameter estimation......Page 413
11.4.4 Quantitative evaluation......Page 416
11.4.5 Conclusions......Page 420
11.5.1 Learning CHD BNs......Page 421
11.5.2 The clinical support tool: TakeHeart II......Page 425
11.5.3 KEBN aspects......Page 429
11.6 Summary......Page 430
A. Notation......Page 432
B.1 Introduction......Page 436
B.2 History......Page 438
B.3 BN Software Package Survey......Page 439
Bibliography......Page 444