1.1 Will Holmes arrive before lunch? . . . . . . . . . . . . . . . . . . . . . . . 11

1.2 Inheritance of eye colors . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.1 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.1.1 Paths and cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.1.2 Common structures . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.1.3 Clusters and cliques . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

3.1.1 Markov networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

3.1.2 Markov trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.1.3 Bayesian networks . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.2 Theory behind Markov networks . . . . . . . . . . . . . . . . . . . . . . . 24

3.2.1 Conditional independence . . . . . . . . . . . . . . . . . . . . . . . 24

3.2.2 Markov properties . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

4.2 Connectivity and information ow . . . . . . . . . . . . . . . . . . . . . . 30

4.2.1 Evidence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

4.2.2 Connections and propagation rules . . . . . . . . . . . . . . . . . 30

4.2.3 d-connection and d-separation . . . . . . . . . . . . . . . . . . . . 33

5.1 Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

5.1.1 Cluster trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

5.1.2 Junction trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

5.1.3 Decomposition of graphs and probability distributions . . . . . . 35

5.1.4 Potentials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

5.2 Transformation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

5.2.1 Moral graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

5.2.2 Triangulated graph . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

5.2.3 Junction tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

5.3 An example - The Year 2000 risk analysis . . . . . . . . . . . . . . . . . . 42

5.3.1 The Bayesian network model . . . . . . . . . . . . . . . . . . . . . 43

3

5.3.2 Moralization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

5.3.3 Triangulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

5.3.4 Building the junction tree . . . . . . . . . . . . . . . . . . . . . . . 45

5.4 Initializing the network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

5.4.1 Initializing the potentials . . . . . . . . . . . . . . . . . . . . . . . 46

5.4.2 Making the junction tree locally consistent . . . . . . . . . . . . . 47

5.4.3 Marginalizing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

5.5 The Year 2000 example continued . . . . . . . . . . . . . . . . . . . . . . . 50

5.5.1 Initializing the potentials . . . . . . . . . . . . . . . . . . . . . . . 50

5.5.2 Making the junction tree consistent . . . . . . . . . . . . . . . . . 52

5.5.3 Calculation the a priori distribution . . . . . . . . . . . . . . . . . 52

5.6 Evidence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

5.6.1 Evidence encoded as a likelihood . . . . . . . . . . . . . . . . . . . 54

5.6.2 Initialization with observations . . . . . . . . . . . . . . . . . . . . 54

5.6.3 Entering observations into the network . . . . . . . . . . . . . . . 55

5.7 The Year 2000 example continued . . . . . . . . . . . . . . . . . . . . . . . 55

5.7.1 Scenario I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

5.7.2 Scenario II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

5.7.3 Scenario III . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

5.7.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

6.1 What would have happened if we had not...? . . . . . . . . . . . . . . . . 58

6.1.1 The twin-model approach . . . . . . . . . . . . . . . . . . . . . . . 59

7.1 Further readings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

A.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

A.2 Multi-way arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

A.2.1 The vec-operator . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

A.2.2 Mapping between the indices in the multi-way array and the vecarray

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

A.2.3 Fast iteration along dimensions . . . . . . . . . . . . . . . . . . . . 66

A.2.4 Object oriented design of a multi-way array . . . . . . . . . . . . 67

A.3 Probability distributions and potentials . . . . . . . . . . . . . . . . . . . 67

A.3.1 Discrete probability distributions . . . . . . . . . . . . . . . . . . . 67

A.3.2 Discrete conditional probability distributions . . . . . . . . . . . . 68

A.3.3 Discrete potentials . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

A.3.4 Multiplication of potentials and probabilities . . . . . . . . . . . . 68

B.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

B.2 XML - Extensible Markup Language . . . . . . . . . . . . . . . . . . . . . 71

B.3 XBN - XML Belief Network File Format . . . . . . . . . . . . . . . . . . . 72

C.1 .Icy Roads. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

C.2 .Year2000. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77