Cover image for Bayesian networks and decision graphs
Title:
Bayesian networks and decision graphs
Personal Author:
Series:
Information science and statistics
Edition:
2nd ed.
Publication Information:
Berlin : Springer, 2007
Physical Description:
xvi, 447 p. : ill. ; 24 cm.
ISBN:
9780387682815
Added Author:

Available:*

Library
Item Barcode
Call Number
Material Type
Item Category 1
Status
Searching...
30000010177443 QA279.5 J46 2007 Open Access Book Book
Searching...

On Order

Summary

Summary

This is a brand new edition of an essential work on Bayesian networks and decision graphs. It is an introduction to probabilistic graphical models including Bayesian networks and influence diagrams. The reader is guided through the two types of frameworks with examples and exercises, which also give instruction on how to build these models. Structured in two parts, the first section focuses on probabilistic graphical models, while the second part deals with decision graphs, and in addition to the frameworks described in the previous edition, it also introduces Markov decision process and partially ordered decision problems.


Author Notes

Thomas is an associate professor at the department of computer science at Aalbory University, Denmark.


Table of Contents

Prefacep. V
1 Prerequisites on Probability Theoryp. 1
1.1 Two Perspectives on Probability Theoryp. 1
1.2 Fundamentals of Probability Theoryp. 2
1.2.1 Conditional Probabilitiesp. 4
1.2.2 Probability Calculusp. 5
1.2.3 Conditional Independencep. 6
1.3 Probability Calculus for Variablesp. 7
1.3.1 Calculations with Probability Tables: An Examplep. 11
1.4 An Algebra of Potentialsp. 13
1.5 Random Variablesp. 15
1.5.1 Continuous Distributionsp. 15
1.6 Exercisesp. 16
Part I Probabilistic Graphical Models
2 Causal and Bayesian Networksp. 23
2.1 Reasoning Under Uncertaintyp. 23
2.1.1 Car Start Problemp. 23
2.1.2 A Causal Perspective on the Car Start Problemp. 24
2.2 Causal Networks and d-Separationp. 26
2.2.1 d-separationp. 30
2.3 Bayesian Networksp. 32
2.3.1 Definition of Bayesian Networksp. 32
2.3.2 The Chain Rule for Bayesian Networksp. 35
2.3.3 Inserting Evidencep. 39
2.3.4 Calculating Probabilities in Practicep. 41
2.4 Graphical Models - Formal Languages for Model Specificationp. 42
2.5 Summaryp. 44
2.6 Bibliographical Notesp. 45
2.7 Exercisesp. 45
3 Building Modelsp. 51
3.1 Catching the Structurep. 51
3.1.1 Milk Testp. 52
3.1.2 Cold or Angina?p. 54
3.1.3 Inseminationp. 55
3.1.4 A Simplified Poker Gamep. 57
3.1.5 Naive Bayes Modelsp. 58
3.1.6 Causalityp. 60
3.2 Determining the Conditional Probabilitiesp. 60
3.2.1 Milk Testp. 60
3.2.2 Stud Farmp. 62
3.2.3 Poker Gamep. 66
3.2.4 Transmission of Symbol Stringsp. 68
3.2.5 Cold or Angina?p. 71
3.2.6 Why Causal Networks?p. 72
3.3 Modeling Methodsp. 73
3.3.1 Undirected Relationsp. 73
3.3.2 Noisy-Orp. 75
3.3.3 Divorcingp. 78
3.3.4 Noisy Functional Dependencep. 80
3.3.5 Expert Disagreementsp. 81
3.3.6 Object-Oriented Bayesian Networksp. 84
3.3.7 Dynamic Bayesian Networksp. 91
3.3.8 How to Deal with Continuous Variablesp. 93
3.3.9 Interventionsp. 96
3.4 Special Featuresp. 97
3.4.1 Joint Probability Tablesp. 98
3.4.2 Most-Probable Explanationp. 98
3.4.3 Data Conflictp. 98
3.4.4 Sensitivity Analysisp. 99
3.5 Summaryp. 100
3.6 Bibliographical Notesp. 101
3.7 Exercisesp. 102
4 Belief Updating in Bayesian Networksp. 109
4.1 Introductory Examplesp. 109
4.1.1 A Single Marginalp. 110
4.1.2 Different Evidence Scenariosp. 111
4.1.3 All Marginalsp. 114
4.2 Graph-Theoretic Representationp. 115
4.2.1 Task and Notationp. 115
4.2.2 Domain Graphsp. 116
4.3 Triangulated Graphs and Join Treesp. 119
4.3.1 Join Treesp. 122
4.4 Propagation in Junction Treesp. 124
4.4.1 Lazy Propagation in Junction Treesp. 127
4.5 Exploiting the Information Scenariop. 130
4.5.1 Barren Nodesp. 130
4.5.2 d-Separationp. 131
4.6 Nontriangulated Domain Graphsp. 132
4.6.1 Triangulation of Graphsp. 134
4.6.2 Triangulation of Dynamic Bayesian Networksp. 137
4.7 Exact Propagation with Bounded Spacep. 140
4.7.1 Recursive Conditioningp. 140
4.8 Stochastic Simulation in Bayesian Networksp. 145
4.8.1 Probabilistic Logic Samplingp. 146
4.8.2 Likelihood Weightingp. 148
4.8.3 Gibbs Samplingp. 150
4.9 Loopy Belief Propagationp. 152
4.10 Summaryp. 154
4.11 Bibliographical Notesp. 156
4.12 Exercisesp. 157
5 Analysis Tools for Bayesian Networksp. 167
5.1 IEJ Treesp. 168
5.2 Joint Probabilities and A-Saturated Junction Treesp. 169
5.2.1 A-Saturated Junction Treesp. 169
5.3 Configuration of Maximal Probabilityp. 171
5.4 Axioms for Propagation in Junction Treesp. 173
5.5 Data Conflictp. 174
5.5.1 Inseminationp. 175
5.5.2 The Conflict Measure confp. 175
5.5.3 Conflict or Rare Casep. 176
5.5.4 Tracing of Conflictsp. 177
5.5.5 Other Approaches to Conflict Detectionp. 179
5.6 SE Analysisp. 179
5.6.1 Example and Definitionsp. 179
5.6.2 h-Saturated Junction Trees and SE Analysisp. 182
5.7 Sensitivity to Parametersp. 184
5.7.1 One-Way Sensitivity Analysisp. 187
5.7.2 Two-Way Sensitivity Analysisp. 188
5.8 Summaryp. 188
5.9 Bibliographical Notesp. 190
5.10 Exercisesp. 191
6 Parameter Estimationp. 196
6.1 Complete Datap. 195
6.1.1 Maximum Likelihood Estimationp. 196
6.1.2 Bayesian Estimationp. 197
6.2 Incomplete Datap. 200
6.2.1 Approximate Parameter Estimation: The EM Algorithmp. 201
6.2.2 Why We Cannot Perform Exact Parameter Estimationp. 207
6.3 Adaptationp. 207
6.3.1 Fractional Updatingp. 210
6.3.2 Fadingp. 211
6.3.3 Specification of an Initial Sample Sizep. 212
6.3.4 Example: Strings of Symbolsp. 213
6.3.5 Adaptation to Structurep. 214
6.3.6 Fractional Updating as an Approximationp. 215
6.4 Tuningp. 218
6.4.1 Examplep. 220
6.4.2 Determining grad dist(x, y) as a Function of tp. 222
6.5 Summaryp. 223
6.6 Bibliographical Notesp. 225
6.7 Exercisesp. 226
7 Learning the Structure of Bayesian Networksp. 229
7.1 Constraint-Based Learning Methodsp. 230
7.1.1 From Skeleton to DAGp. 231
7.1.2 From Independence Tests to Skeletonp. 234
7.1.3 Examplep. 235
7.1.4 Constraint-Based Learning on Data Setsp. 237
7.2 Ockham's Razorp. 240
7.3 Score-Based Learningp. 241
7.3.1 Score Functionsp. 242
7.3.2 Search Proceduresp. 245
7.3.3 Chow-Liu Treesp. 250
7.3.4 Bayesian Score Functionsp. 253
7.4 Summaryp. 258
7.5 Bibliographical Notesp. 260
7.6 Exercisesp. 261
8 Bayesian Networks as Classifiersp. 265
8.1 Naive Bayes Classifiersp. 266
8.2 Evaluation of Classifiersp. 268
8.3 Extensions of Naive Bayes Classifiersp. 270
8.4 Classification Treesp. 272
8.5 Summaryp. 274
8.6 Bibliographical Notesp. 275
8.7 Exercisesp. 276
Part II Decision Graphs
9 Graphical Languages for Specification of Decision Problemsp. 279
9.1 One-Shot Decision Problemsp. 280
9.1.1 Fold or Call?p. 281
9.1.2 Mildewp. 282
9.1.3 One Decision in Generalp. 283
9.2 Utilitiesp. 284
9.2.1 Instrumental Rationalityp. 287
9.3 Decision Treesp. 290
9.3.1 A Couple of Examplesp. 293
9.3.2 Coalesced Decision Treesp. 295
9.3.3 Solving Decision Treesp. 296
9.4 Influence Diagramsp. 302
9.4.1 Extended Poker Modelp. 302
9.4.2 Definition of Influence Diagramsp. 305
9.4.3 Repetitive Decision Problemsp. 308
9.5 Asymmetric Decision Problemsp. 310
9.5.1 Different Sources of Asymmetryp. 314
9.5.2 Unconstrained Influence Diagramsp. 316
9.5.3 Sequential Influence Diagramsp. 322
9.6 Decision Problems with Unbounded Time Horizonsp. 324
9.6.1 Markov Decision Processesp. 324
9.6.2 Partially Observable Markov Decision Processesp. 330
9.7 Summaryp. 332
9.8 Bibliographical Notesp. 337
9.9 Exercisesp. 337
10 Solution Methods for Decision Graphsp. 343
10.1 Solutions to Influence Diagramsp. 343
10.1.1 The Chain Rule for Influence Diagramsp. 345
10.1.2 Strategies and Expected Utilitiesp. 346
10.1.3 An Examplep. 352
10.2 Variable Eliminationp. 353
10.2.1 Strong Junction Treesp. 355
10.2.2 Required Pastp. 358
10.2.3 Policy Networksp. 360
10.3 Node Removal and Arc Reversalp. 362
10.3.1 Node Removalp. 362
10.3.2 Arc Reversalp. 363
10.3.3 An Examplep. 365
10.4 Solutions to Unconstrained Influence Diagramsp. 367
10.4.1 Minimizing the S-DAGp. 367
10.4.2 Determining Policies and Step Functionsp. 371
10.5 Decision Problems Without a Temporal Ordering: Troubleshootingp. 373
10.5.1 Action Sequencesp. 373
10.5.2 A Greedy Approachp. 375
10.5.3 Call Servicep. 378
10.5.4 Questionsp. 378
10.6 Solutions to Decision Problems with Unbounded Time Horizonp. 380
10.6.1 A Basic Solutionp. 380
10.6.2 Value Iterationp. 381
10.6.3 Policy Iterationp. 385
10.6.4 Solving Partially Observable Markov Decision Processesp. 388
10.7 Limited Memory Influence Diagramsp. 392
10.8 Summaryp. 395
10.9 Bibliographical Notesp. 400
10.10 Exercisesp. 401
11 Methods for Analyzing Decision Problemsp. 407
11.1 Value of Informationp. 407
11.1.1 Test for Infected Milk?p. 407
11.1.2 Myopic Hypothesis-Driven Data Requestp. 409
11.1.3 Non-Utility-Based Value Functionsp. 411
11.2 Finding the Relevant Past and Future of a Decision Problemp. 413
11.2.1 Identifying the Required Pastp. 415
11.3 Sensitivity Analysisp. 420
11.3.1 Examplep. 421
11.3.2 One-Way Sensitivity Analysis in Generalp. 423
11.4 Summaryp. 426
11.5 Bibliographical Notesp. 427
11.6 Exercisesp. 427
List of Notationp. 429
Referencesp. 431
Indexp. 441