Suppose you have 4 binary variables: a , b , c , and d . Consider the Bayesian n

Question

Suppose you have 4 binary variables: a, b, c, and d. Consider the Bayesian network structured as follows abcd. The network has the following parameters: P(a)=0.5, P(b|a)=0.4, P(b|¬a)=0.2, P(c|b)=0.3, P(c|¬b)=0.7 ,P(d|c)=0.4, P(d|¬c)=0.7.

1- Compute the probability of P(d). (hint: you need to marginalize out the probabilities of a, b, and, c)

2 - How many summations did you need to compute? Can you do better with a different ordering of summations?

3 - Suppose we have a Bayesian network with a similar structure but with n binary variables in a chain instead, i.e. x1x2x3…xn. What is the fewest number of sums needed to compute P(xn)?

4 - What is the worst-case number of sums needed to compute P(xn)?

Explanation / Answer

ANSWER1:

Say they take values 1 & 0 each. We want to compute

P(d) = a b c P(a, b, c, d)

=                     P (d=1 & c=1) or P (d=1 & c = 0) or

                      P (d=1 & b=1) or P (d=1 & b = 0) or

                        P (d=1 & a=1) or P (d=1 & a = 0)

This is based on the sum rule of probability. But in this case, there’s conditional dependence between (a, b), (b, c) and (c, d) hence we will create marginal probabilities of a, b and c first.

P(a=1) is given = 0.5

P(b=1) = P(b=1 & a = 1) + P(b=1 & a=0)

            = P(b=1 | a = 1).P(a=1) + P(b=1 | a = 0).(1-P(a=1))

            = 0.4*0.5 + 0.2*0.5

            = 0.2 + 0.1

            = 0.3

P(c=1) = P(c=1 & b=1) + P(c=1 & b=0)

            = P(c=1|b=1).P(b) + P(c=1|b=0).(1-P(b=1))

            = 0.3*0.3 + 0.7*0.7

            = 0.09 + 0.49

= 0.58

P(d=1) = P(d=1 & c = 1) + P(d=1 & c = 0)

            = P(d = 1|c = 1).P(c=1) + P(d = 1|c = 0).(1-P(c=1) )

            = 0.4*0.58 + 0.7*0.42

            = 0.232 + 0.294

            = 0.526

ANSWER2:

Number of summation required is: 3 In this case, I can't think of any other ordering of variables, especially since this is a directed graph with conditional dependence built in with each variable occurence. We can only remove terms from summation where there is no 'ancestry'

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.