Quiz 2: CS 726, Spring 2025

Prof. Sunita Sarawagi

22𝑛𝑑 January, 2025

The quiz will last for 20 minutes.

Answer the following questions:

(a) Which of the following CIs would hold for all Probability distributions for which the above Bayesian Network
is a correct representation?
i. 𝐷⟂
⟂ 𝐸 ∣ 𝐴, 𝐵
ii. 𝐴⟂
⟂𝐶∣𝐷
iii. 𝐴⟂
⟂𝐹 ∣𝐶
iv. 𝐴⟂
⟂𝐵∣𝐶
v. 𝐴⟂
⟂𝐵∣𝐹
Solution: (iii) only. i) D-C-E is not blocked. ii). A-C is not blocked, iii) all paths blocked by C, iv) C is the collider
node, v) F is a descendant of the collider node [2 mark]
(b) Without the BN available, what would be the number of free parameters required to specify the joint distribu-
tion of A, B, C, D using the standard representation?

Solution: 34 − 1 = 80. One parameter to represent probability corresponding to each of the 34 possible values
of (𝐴, 𝐵, 𝐶, 𝐷) tuple (since each RV can take 3 values). -1 is due to the constraint that the sum of all probabilities
should be equal to 1.
[1 mark]
(c) Suppose 𝐀, 𝐁, 𝐂, 𝐃, 𝐄 are independent of each other, what would be the number of free parameters sufficient
to completely specify the joint distribution of 𝐀, 𝐁, 𝐂, 𝐃, 𝐄 using the standard representation?

Solution: 2 ∗ 5 = 10. Two parameters to represent probability distribution of each R.V. (say, probability of
RV X being equal to 0, -1. Probability of RV X being equal to 1 is fixed due to the constraint that the P(X=1) +
P(X=0) + P(X=-1) = 1). There are 5 R.V.s in total, so, required number = 2*5 [1 mark]
 (d) With the BN available, what would be the number of free parameters required to specify the joint distribution
of 𝐀, 𝐁, 𝐂, 𝐃, 𝐄, 𝐅 using the standard representation?

Solution: 52
Given the Bayesian Network (BN) structure, the joint distribution of the variables A, B, C, D, E, F can be factorized
as:
𝑃(𝐴, 𝐵, 𝐶, 𝐷, 𝐸, 𝐹 ) = 𝑃(𝐴) ⋅ 𝑃(𝐵) ⋅ 𝑃(𝐶|𝐴, 𝐵) ⋅ 𝑃(𝐷|𝐶) ⋅ 𝑃(𝐸|𝐶) ⋅ 𝑃(𝐹 |𝐷, 𝐸)
Now, let’s calculate the number of free parameters required for each factor:
1. 𝑃(𝐴): This is the marginal probability of 𝐴. Since 𝐴 is ternary, we only need to specify two parameters
(𝑃(𝐴 = −1), 𝑃(𝐴 = 0)).
Number of parameters for 𝑃(𝐴) = 2

2. 𝑃(𝐵): This is the marginal probability of 𝐵, and it is similar to 𝑃(𝐴).

Number of parameters for 𝑃(𝐵) = 2

3. 𝑃(𝐶|𝐴, 𝐵): We need 2 parameters (say, 𝑃(𝐶 = −1|𝐴 = 0, 𝐵 = 0), 𝑃(𝐶 = 0|𝐴 = 0, 𝐵 = 0). The third probability
mass, 𝑃(𝐶 = 1|𝐴 = 0, 𝐵 = 0) will automatically fixed due to sum of probabilities, given 𝐴 = 0 and 𝐵 = 0, being
equal to 1) for 𝐶 for each combination of values of 𝐴 and 𝐵. There are 9 combinations of values of 𝐴 and 𝐵,
so:
Number of parameters for 𝑃(𝐶|𝐴, 𝐵) = 2 × 3 × 3 = 18
4. 𝑃(𝐷|𝐶): We need 2 parameters (same logic as above) to specify the distribution 𝑃(𝐷|𝐶) for each given value
of C. For example, two parameters to specify 𝑃(𝐷|𝐶 = 0). Since, there can be 3 given values of C ({−1, 0, 1}),

Number of parameters for 𝑃(𝐷|𝐶) = 2 × 3 = 6

5. 𝑃(𝐸|𝐶): Like 𝑃(𝐷|𝐶), we need 2 parameters for each value of 𝐶.

Number of parameters for 𝑃(𝐸|𝐶) = 2 × 3 = 6

6. 𝑃(𝐹 |𝐷, 𝐸): By the same logic as 𝑃(𝐶|𝐴, 𝐵),

Number of parameters for 𝑃(𝐹 |𝐷, 𝐸) = 2 × 3 × 3 = 18

The total number of free parameters required to specify the joint distribution is the sum of the free parameters
for each factor:
Total = 2 + 2 + 18 + 6 + 6 + 18 = 52
[2 mark]

2. (One or more options correct) Let us have an arbitrary set of (conditional) independence relationships among N vari-
ables that is associated with a joint probability distribution. Which of the following is/are true?
(a) It is always possible to draw a “correct” BN Representation of the distribution.
(b) It is always possible to find a BN Representation that perfectly maps this set (perfectly maps = preserves all the
(conditional) independence relationships, it neither removes nor adds any)
(c) There exists a unique minimal BN representation which is correct
(d) Two different BNs cannot have same set of Global-CIs.
Solution: (a)
(a) Use any ordering of the nodes, the algorithm for creating a minimal, correct BN for the set of conditional
independences, will trivially give a correct BN for the probability distribution (Note: There is subtlety in the
notion of what is a ”correct” BN as mentioned in the slides. A Bayesian Network is ”correct” (or ”can represent
a set of conditional independences 𝐼 (𝑃)”) when the set of conditional independences associated with the graph,
𝐼 (𝐺) (i.e. the set of conditional independences asserted by the BN) is a subset if 𝐼 (𝑃) (conditional independences
of a probability distribution))
𝐼 (𝐺) ⊆ 𝐼 (𝑃)
(b) Say, there are two independent RV A and B, the following BN is “correct” but is not “perfect” - because the
BN does not assert that 𝐴 and 𝐵 are independent.

Perfect BN means (same notation as in the previous option)

𝐼 (𝐺) = 𝐼 (𝑃)

(c) This is false, because the minimal representation depends on the ordering of the nodes while running the
algorithm for getting minimal, correct BN. Note the difference between “minimal” and “minimum” BN. “Minimal”
means one cannot get a “correct” BN by taking a subset of edges of the minimal BN.
(d) Consider the trivial example below:

Figure 1: BN 1

Figure 2: BN 2

The set of conditional independences asserted by both BN = 𝜙 [2 mark]

Which of the following graphs can represent a minimal, correct Bayesian network formed by running the algorithm
discussed in class for constructing such networks, for some ordering of the random variables?
(Hint: Infer the first two nodes in the ordering from the given options and verify if the remaining edges are correct
according to the algorithm)

(a) (b)

(c) (d)

Solution:
(a) Taking the order 𝐴, 𝐵, 𝐶, 𝐷 gives the BN in option (a)
(b) Only possible orderings could be 𝐷, 𝐵, 𝐴, 𝐶 or 𝐷, 𝐵, 𝐶, 𝐴, none of which give the given graph
(c) Taking the order 𝐶, 𝐴, 𝐵, 𝐷 gives the BN in option (c)
(d) Only possible orderings could be 𝐵, 𝐷, 𝐴, 𝐶, but this ordering does not give the BN in option (d) when the algorithm
is run. [2 mark]
 4. Consider 4 binary random variables taking values in 0,1. Their joint probability distribution can be represented by the
following Bayesian Network, and the given conditional probabilities.

𝑃(𝐴 = 0) = 0.4,
𝑃(𝐵 = 0|𝐴 = 1) = 0.5, 𝑃(𝐵 = 0|𝐴 = 0) = 0.4,
𝑃(𝐶 = 0|𝐴 = 1) = 0.4, 𝑃(𝐶 = 0|𝐴 = 0) = 0.5
𝑃(𝐷 = 0|𝐵 = 0, 𝐶 = 0) = 0.4, 𝑃(𝐷 = 0|𝐵 = 0, 𝐶 = 1) = 0.6, 𝑃(𝐷 = 0|𝐵 = 1, 𝐶 = 0) = 0.3, 𝑃(𝐷 = 0|𝐵 = 1, 𝐶 = 1) = 0.7
• What is value of 𝑃(𝐷 = 0|𝐴 = 1, 𝐵 = 1, 𝐶 = 0)? Solution: 0.3 𝑃(𝐷|𝐴, 𝐵, 𝐶) = 𝑃(𝐷|𝐵, 𝐶) [1 mark]

• What is value of 𝑃(𝐴 = 0, 𝐵 = 1, 𝐶 = 0, 𝐷 = 1)? Solution: 0.084 𝑃(𝐴, 𝐵, 𝐶, 𝐷) = 𝑃(𝐴)𝑃(𝐵|𝐴)𝑃(𝐶|𝐴)𝑃(𝐷|𝐵, 𝐶)