Solutions

Bayesian Networks — Questions 1 & 2

Question 1 Solutions
1.1(a) Joint Distribution Factorization
Using the Bayesian network chain rule, each node is conditioned on its parents:

P (S, E, C, B, H, F, D) = P (S) · P (E) · P (C | S, E) · P (B | S, E)

· P (H | C, B) · P (F | H) · P (D | H)
Justification of each factor:

Node Parents Factor

S none P (S)
E none P (E)
C S, E P (C | S, E)
B S, E P (B | S, E)
H C, B P (H | C, B)
F H P (F | H)
D H P (D | H)

1.1(b) Numerical Joint Probability

P (S=T, E=F, C=T, B=T, H=T, F =T, D=T )
= P (S=T ) · P (E=F ) · P (C=T | S=T, E=F )
· P (B=T | S=T, E=F ) · P (H=T | C=T, B=T )
· P (F =T | H=T ) · P (D=T | H=T )

Factor Value Running product

P (S=T ) 0.3 0.3
× P (E=F ) 0.6 0.18
× P (C=T | S=T, E=F ) 0.8 0.144
× P (B=T | S=T, E=F ) 0.7 0.1008
× P (H=T | C=T, B=T ) 0.9 0.09072
× P (F =T | H=T ) 0.8 0.072576
× P (D=T | H=T ) 0.95 0.068947

P (S=T, E=F, C=T, B=T, H=T, F =T, D=T ) ≈ 0.068947

1
1.1(c) Student’s Factorization Claim
Claim: P (S) · P (E) · P (C, B | S, E) · P (H | C, B) · P (F, D | H)
Analysis of each grouped factor:
Factor 1: P (C, B | S, E) = P (C | S, E) · P (B | S, E)
C and B share the same parents S and E with no direct edge between them. Therefore
C ⊥ B | {S, E}, and the factorisation holds. ✓
Factor 2: P (F, D | H) = P (F | H) · P (D | H)
F and D are both children of H with no direct edge between them. The path
F ← H → D is a fork blocked by conditioning on H. Therefore F ⊥ D | H, and
the factorisation holds. ✓

Verdict: The student’s factorization is correct.

1.2 Conditional Independence and d-Separation

For each question: list all paths, classify intermediate nodes, determine blocked/active,
give verdict.

(a) Is S ⊥ E ?

Path Middle node Type Observed? Status

S→C←E C Collider No Blocked
S→B←E B Collider No Blocked

Both paths have an unobserved collider ⇒ both blocked.

S⊥E YES – Independent

(b) Is S ⊥ E | {H} ?

Path Key node Type Obs.? Status

S →C ←E C Collider No Blocked
S →B ←E B Collider No Blocked
S →C →H←B←E H Collider Yes fl
S →B →H←C←E H Collider Yes fl

Conditioning on H opens the collider at H, activating the last two paths.

S ̸⊥ E | {H} NO – Not Independent

Phenomenon: Explaining Away (Berkson’s Paradox). Observing H creates
dependence between its causes C and B, which in turn makes S and E dependent. If we

2
know the patient has heart disease and we learn they smoke heavily, this reduces the need
to explain H via exercise, making S and E negatively correlated given H.

(c) Is S ⊥ E | {C} ?

Path Key node Type Obs.? Status

S →C ←E C Collider Yes fl
S →B ←E B Collider No Blocked
S →C →H←B←E C Chain Yes Blocked
S →B →H←C←E C Collider Yes fl

Path 1 is active because C is a collider that is observed, which opens that path. Path
4 is also active for the same reason (C observed opens the collider end of that path).

S ̸⊥ E | {C} NO – Not Independent

Key difference from (b): In (b) conditioning on H (a descendant-collider) opened
paths. Here conditioning on C directly opens the collider S → C ← E. Both are collider
activation, but in (c) the collider is an ancestor node being observed, while in (b) it was
a descendant.

(d) Is F ⊥ D | {H} ?

Path Middle node Type Observed? Status

F ←H→D H Fork Yes Blocked

The only path goes through H which is a fork. Conditioning on a fork node blocks
the path.

F ⊥ D | {H} YES – Independent

Structural property: Common-cause screening off. H is the common cause of
both F and D. Once H is known, F and D carry no additional information about each
other.

3
1.3(a) P (H=T | D=T ) via Bayes Theorem
P (D=T | H=T ) · P (H=T )
P (H=T | D=T ) =
P (D=T )
Step 1 — Compute P (H=T ).
First compute the joint marginals over C and B (they share parents S, E, so they are
not marginally independent):
X
P (C, B) = P (C | s, e) P (B | s, e) P (s) P (e)
s,e

C B P (C, B)
T T 0.7×0.6×0.12 + 0.8×0.7×0.18 + 0.2×0.1×0.28 + 0.4×0.3×0.42 = 0.2072
T F 0.7×0.4×0.12 + 0.8×0.3×0.18 + 0.2×0.9×0.28 + 0.4×0.7×0.42 = 0.2448
F T 0.3×0.6×0.12 + 0.2×0.7×0.18 + 0.8×0.1×0.28 + 0.6×0.3×0.42 = 0.1448
F F 0.3×0.4×0.12 + 0.2×0.3×0.18 + 0.8×0.9×0.28 + 0.6×0.7×0.42 = 0.4032

X
P (H=T ) = P (H=T | c, b) P (c, b) = 0.9(0.2072)+0.7(0.2448)+0.6(0.1448)+0.1(0.4032)
c,b

= 0.1865 + 0.1714 + 0.0869 + 0.0403 = 0.4851

P (H=F ) = 1 − 0.4851 = 0.5149
Step 2 — Compute P (D=T ) by the law of total probability.

P (D=T ) = P (D=T | H=T ) P (H=T ) + P (D=T | H=F ) P (H=F )

= 0.95 × 0.4851 + 0.08 × 0.5149 = 0.4608 + 0.0412 = 0.5020
Step 3 — Apply Bayes Theorem.
0.95 × 0.4851 0.4608
P (H=T | D=T ) = =
0.5020 0.5020

P (H=T | D=T ) ≈ 0.9179

1.3(b) P (H=T | D=T, F =T )

Because F ⊥ D | H (shown in 1.2d), the likelihood of both observations factors:

P (D=T, F =T | H) = P (D=T | H) · P (F =T | H)
Applying Bayes:

P (D=T | H=T ) P (F =T | H=T ) P (H=T )

P (H=T | D=T, F =T ) =
P (D=T, F =T )
Numerator:
0.95 × 0.8 × 0.4851 = 0.3685

4
 Denominator:

P (D=T, F =T ) = (0.95)(0.8)(0.4851) + (0.08)(0.1)(0.5149) = 0.3685 + 0.00412 = 0.37262

0.3685
P (H=T | D=T, F =T ) = ≈ 0.9889
0.37262
Why D and F are dependent marginally but independent given H:
Marginally, the path D ← H → F is a fork at H which is unobserved, so the path is
active and D and F are dependent (they share the common cause H). Once H is observed,
the fork is blocked by conditioning, making D and F conditionally independent.

1.3(c) Evidence Accumulation

Evidence P (H=T )
None 0.4851
D=T 0.9179
D=T, F =T 0.9889

Interpretation: Each additional piece of evidence updates our belief via Bayes theo-
rem. The positive test D=T alone raises the probability of heart disease from 0.49 to 0.92
(a very informative test, P (D=T | H=T ) = 0.95). Adding the independent symptom
F =T pushes the posterior to 0.99, because F provides a second, conditionally indepen-
dent channel of evidence about H. This illustrates Bayesian belief updating: evidence
compounds multiplicatively when the observations are conditionally independent given
the hypothesis.

1.4 Variable Elimination: P (H | S=T, D=T )

Elimination ordering: E, C, B, F

(a) Active factors after evidence S=T , D=T

Factor Expression Scope

ϕE P (E) {E}
ϕC P (C | S=T, E) {E, C}
ϕB P (B | S=T, E) {E, B}
ϕH P (H | C, B) {C, B, H}
ϕF P (F | H) {F, H}
ϕD P (D=T | H) {H}

5
(b) Elimination steps
Step 1 — Eliminate E Factors involving E: ϕE (E), ϕC (E, C), ϕB (E, B)
X
f1 (C, B) = P (E) · P (C | S=T, E) · P (B | S=T, E)
E

Computed values:

f1 (C=T, B=T ) = 0.4(0.7)(0.6) + 0.6(0.8)(0.7) = 0.168 + 0.336 = 0.5040

f1 (C=T, B=F ) = 0.4(0.7)(0.4) + 0.6(0.8)(0.3) = 0.112 + 0.144 = 0.2560
f1 (C=F, B=T ) = 0.4(0.3)(0.6) + 0.6(0.2)(0.7) = 0.072 + 0.084 = 0.1560
f1 (C=F, B=F ) = 0.4(0.3)(0.4) + 0.6(0.2)(0.3) = 0.048 + 0.036 = 0.0840
Scope of f1 : {C, B}

Step 2 — Eliminate C Factors involving C: f1 (C, B), ϕH (C, B, H)

X
f2 (B, H) = f1 (C, B) · P (H | C, B)
C

f2 (B=T, H=T ) = 0.5040(0.9) + 0.1560(0.6) = 0.4536 + 0.0936 = 0.5472

f2 (B=T, H=F ) = 0.5040(0.1) + 0.1560(0.4) = 0.0504 + 0.0624 = 0.1128
f2 (B=F, H=T ) = 0.2560(0.7) + 0.0840(0.1) = 0.1792 + 0.0084 = 0.1876
f2 (B=F, H=F ) = 0.2560(0.3) + 0.0840(0.9) = 0.0768 + 0.0756 = 0.1524
Scope of f2 : {B, H}

Step 3 — Eliminate B Factors involving B: f2 (B, H)

X
f3 (H) = f2 (B, H)
B

f3 (H=T ) = 0.5472 + 0.1876 = 0.7348

f3 (H=F ) = 0.1128 + 0.1524 = 0.2652
Scope of f3 : {H}

Step 4 — Eliminate F Factor involving F : ϕF (F, H) = P (F | H)

F is unobserved; summing over all values of F :
X
P (F | H) = 1 ∀ H
F

This yields a scalar 1 which drops out of the computation.

No new factor is created.

6
(c) Final unnormalized expression and normalization
P̃ (H | S=T, D=T ) ∝ f3 (H) · P (D=T | H)

H f3 (H) P (D=T | H) Unnormalized

T 0.7348 0.95 0.7348 × 0.95 = 0.6981
F 0.2652 0.08 0.2652 × 0.08 = 0.0212
Sum 0.7193

Normalized:

0.6981
P (H=T | S=T, D=T ) = ≈ 0.9705
0.7193
0.0212
P (H=F | S=T, D=T ) = ≈ 0.0295
0.7193

(d) Treewidth under order E, C, B, F, S

Step Eliminate Neighbours at elimination Clique (size)

1 E {S, C, B} — add C-B if absent {E, S, C, B} (4)
2 C {S, B, H} — add S-H, B-H {C, S, B, H} (4)
3 B {S, H} {B, S, H} (3)
4 F {H} {F, H} (2)
5 S {H} {S, H} (2)

Largest clique formed = 4 variables.

Treewidth = 4 − 1 = 3

7
Question 2 Solutions
2.1(a) Is N ⊥ W | {A, S, D} ?
Path Key Type Obs.? Status
node(s)
W →A→N A Chain Yes Blocked
W →D→N D Chain Yes Blocked
W →S→D→N S (chain) Chain Yes Blocked
W →A→N ←D←W (same path) — — (not a new
path)
W →D→N ←R←M N Collider No Blocked
W →A→N ←R←M A (chain), Chain Yes (A) Blocked
N (collider)

Every path from W to N is blocked by a chain node in {A, S, D}.

N ⊥ W | {A, S, D} YES – Independent

2.1(b) Is E ⊥ M ?
We look for any undirected path between E and M in the moral/undirected skeleton.
M connects only via the edge M → R → N . Any path from E to M must pass
through N .
Path: E → A → N ← R ← M

Path Key node Type Observed? Status

E→A→N ←R←M N Collider No Blocked

N is a collider on this path and is not observed, so the path is blocked. No other path
between E and M exists.

E⊥M YES – Independent

2.2 Conditional Independence of Nodes given {A, D, N }

We test every node not in the conditioning set {A, D, N } against M .
The only path out of M is M → R → N . Conditioning on N opens the collider at
N (since N is a collider between its three parents A, D, R). This means paths can flow
through N .
However, once through N every onward path to E, W , or S must pass through A or
D, both of which are in the conditioning set and act as chain-blockers.
Check each node:

8
 Node Best path from M Verdict
R M → R — direct edge, R not in evidence Dependent
E M → R → N ← A ← E: N observed Independent
(opens collider), then A observed (chain
blocked)
W M → R → N ← A ← W : N opens, A Independent
blocks
M → R → N ← D ← W : N opens, D Independent
blocks
S M → R → N ← D ← S: N opens, D Independent
blocks

Nodes independent of M | {A, D, N } = {E, W, S}

2.3(a) Variable Elimination

P (N | E=Long, W =Positive, D=Drinking, R=Poor)
Full joint factorization:

P (E) P (W ) P (M ) P (A | E, W ) P (S | W ) P (D | W, S) P (R | M ) P (N | A, D, R)

Active factors after fixing evidence E=e, W =w, D=d, R=r:

Factor Expression Scope

ϕA P (A | E=e, W =w) {A}
ϕS P (S | W =w) {S}
ϕD P (D=d | W =w, S) {S}
ϕM P (M ) {M }
ϕR P (R=r | M ) {M }
ϕN P (N | A, D=d, R=r) {N, A}

Step 1 — Eliminate M Factors: ϕM (M ), ϕR (M )

X
f1 = P (M ) · P (R=Poor | M ) −→ scalar
M

Scope of f1 : {} (scalar constant)

Step 2 — Eliminate S Factors: ϕS (S), ϕD (S)

Note: S does not appear in ϕN (since D and R are already fixed as evidence), so S is
eliminated independently.
X
f2 = P (S | W =w) · P (D=d | W =w, S) −→ scalar
S

Scope of f2 : {} (scalar constant)

9
Step 3 — Eliminate A Factors: ϕA (A), ϕN (N, A)
X
f3 (N ) = P (A | E=e, W =w) · P (N | A, D=d, R=r)
A

Scope of f3 : {N }

Final result
P (N | E, W, D, R) ∝ f1 · f2 · f3 (N )
Since f1 and f2 are scalars, they cancel in normalization:

X
P (A | E=e, W =w) P (N | A, D=d, R=r)
f3 (N ) A
P (N | E, W, D, R) = X = XX
f3 (n) P (A | E=e, W =w) P (N | A, D=d, R=r)
n N A

2.3(b) Treewidth under order M, S, A

Step 1 — Moralize the DAG
Before variable elimination can be applied to find the treewidth of a directed Bayesian
network, the graph must first be moralized: for every node with more than one parent,
add an undirected edge between every pair of those parents (“marry the co-parents”),
then drop all edge directions.
Co-parent marriages required:

Node Parents Edges added

A {E, W } E–W
D {W, S} W –S (already exists)
N {A, D, R} A–D, A–R, D–R

Moralized graph adjacency (undirected):

Node Neighbours
E A, W
W A, D, E, S
M R
A D, E, N, R, W
S D, W
D A, N, R, S, W
R A, D, M, N
N A, D, R

10
Step 2 — Variable Elimination on the Moralized Graph
At each step: form a clique over the node and all its current neighbours, add any missing
fill edges between those neighbours, then remove the node.

Step Eliminate Neighbours & fill edges added Clique (size)

1 M Neighbours: {R}. {M, R} (2)

No fill edges needed.
2 S Neighbours: {W, D}. {S, W, D} (3)
W –D already exists in moralized
graph.
No new fill edges needed.
3 A Neighbours: {D, E, N, R, W }. {A, D, E, N, R, W } (6)
Add fill edges between all pairs:
D–E, E–R, E–N , R–W , W –N .
(D–R, D–N , D–W , R–N already
exist.)

The crucial point is that A’s neighbours in the moralized graph include D and R (due
to the co-parent marriages at N ), not just E, W , and N as the directed graph alone
would suggest. This pulls all five neighbours into a single clique of size 6.
Largest clique formed = 6 variables.

Treewidth = 6 − 1 = 5

11