In Bayesian net with variable x={x1,...,xn}. Each random variable has at most P parent and Q child. For a given variable such Xi we want to determine the minimum number of observed variables that make Xi independent from another variable? (number of minimum variables)
This is an Entrance Exam Question that I took today. I am having trouble understanding why the answer is : P + PQ?
Hello Huimen,
here is a small example please go through this,
Bayesian Net Example
Consider the following Bayesian network:
Thus, the independence expressed in this Bayesian net are that
A and B are (absolutely) independent.
C is independent of B given A.
D is independent of C given A and B.
E is independent of A, B, and D given C.
Suppose that the net further records the following probabilities:
Prob(A=T) = 0.3
Prob(B=T) = 0.6
Prob(C=T|A=T) = 0.8
Prob(C=T|A=F) = 0.4
Prob(D=T|A=T,B=T) = 0.7
Prob(D=T|A=T,B=F) = 0.8
Prob(D=T|A=F,B=T) = 0.1
Prob(D=T|A=F,B=F) = 0.2
Prob(E=T|C=T) = 0.7
Prob(E=T|C=F) = 0.2
Some sample computations:
Prob(D=T)
P(D=T) =
P(D=T,A=T,B=T) + P(D=T,A=T,B=F) + P(D=T,A=F,B=T) + P(D=T,A=F,B=F) =
P(D=T|A=T,B=T) P(A=T,B=T) + P(D=T|A=T,B=F) P(A=T,B=F) +
P(D=T|A=F,B=T) P(A=F,B=T) + P(D=T|A=F,B=F) P(A=F,B=F) =
(since A and B are independent absolutely)
P(D=T|A=T,B=T) P(A=T) P(B=T) + P(D=T|A=T,B=F) P(A=T) P(B=F) +
P(D=T|A=F,B=T) P(A=F) P(B=T) + P(D=T|A=F,B=F) P(A=F) P(B=F) =
0.7*0.3*0.6 + 0.8*0.3*0.4 + 0.1*0.7*0.6 + 0.2*0.7*0.4 = 0.32
Prob(D=F,C=T)
P(D=F,C=T) =
P(D=F,C=T,A=T,B=T) + P(D=F,C=T,A=T,B=F) +
P(D=F,C=T,A=F,B=T) + P(D=F,C=T,A=F,B=F) =
P(D=F,C=T|A=T,B=T) P(A=T,B=T) + P(D=F,C=T|A=T,B=F) P(A=T,B=F) +
P(D=F,C=T|A=F,B=T) P(A=F,B=T) + P(D=F,C=T|A=F,B=F) P(A=F,B=F) =
(since C and D are independent given A and B)
P(D=F|A=T,B=T) P(C=T|A=T,B=T) P(A=T,B=T) + P(D=F|A=T,B=F) P(C=T|A=T,B=F) P(A=T,B=F) +
P(D=F|A=F,B=T) P(C=T|A=F,B=T) P(A=F,B=T) + P(D=F|A=F,B=F) P(C=T|A=F,B=F) P(A=F,B=F) =
(since C is independent of B given A and A and B are independent absolutely)
P(D=F|A=T,B=T) P(C=T|A=T) P(A=T) P(B=T) + P(D=F|A=T,B=F) P(C=T|A=T) P(A=T) P(B=F) + P(D=F|A=F,B=T) P(C=T|A=F) P(A=F) P(B=T) + P(D=F|A=F,B=F) P(C=T|A=F) P(A=F) P(B=F) =
0.3*0.8*0.3*0.6 + 0.2*0.8*0.3*0.4 + 0.9*0.4*0.7*0.6 + 0.8*0.4*0.7*0.4 = 0.3032
Prob(A=T|C=T)
P(A=T|C=T) = P(C=T|A=T)P(A=T) / P(C=T).
Now P(C=T) = P(C=T,A=T) + P(C=T,A=F) =
P(C=T|A=T)P(A=T) + P(C=T|A=F)P(A=F) =
0.8*0.3+ 0.4*0.7 = 0.52
So P(C=T|A=T)P(A=T) / P(C=T) = 0.8*0.3/0.52= 0.46.
Prob(A=T|D=F)
P(A=T|D=F) =
P(D=F|A=T) P(A=T)/P(D=F).
Now P(D=F) = 1-P(D=T) = 0.68 from the first question above.
P(D=F|A=T) = P(D=T,B=T|A=T) + P(D=F,B=F|A=T) =
P(D=F|B=T,A=T) P(B=T|A=T) + P(D=F|B=F,A=T) P(B=F|A=T) =
(since B is independent of A)
P(D=F|B=T,A=T) P(B=T) + P(D=F|B=F,A=T) P(B=F) = 0.3*0.6 + 0.2*0.4 = 0.26.
So P(A=T|D=F) = P(D=F|A=T) P(A=T)/P(D=F) = 0.26 * 0.3 / 0.68 = 0.115
Prob(A=T,D=T|B=F).
P(A=T,D=T|B=F) =
P(D=T|A=T,B=F) P(A=T|B=F) =
(since A and B are independent)
P(D=T|A=T,B=F) P(A=T) = 0.8*0.3 = 0.24.
Prob(C=T | A=F, E=T)
Prob(C=T | A=F, E=T) = (By Bayes' law)
Prob(E=T|C=T,A=F) * Prob(C=T|A=F) / Prob(E=T|A=F) = (since E is independent of A given C)
Prob(E=T|C=T) * Prob(C=T|A=F) / Prob(E=T|A=F).
Now Prob(E=T|A=F) = Prob(E=T,C=T|A=F) + Prob(E=T,C=F|A=F) =
Prob(E=T|C=T,A=F) Prob(C=T|A=F) + Prob(E=T|C=F,A=F) Prob(C=F|A=F) = (since E is independent of A given C)
Prob(E=T|C=T) * Prob(C=T|A=F) + Prob(E=T|C=F) * Prob(C=F|A=F).
So we have
Prob(C=T | A=F, E=T) =
Prob(E=T|C=T) * Prob(C=T|A=F) / (Prob(E=T|C=T) * Prob(C=T|A=F) + Prob(E=T|C=F) * Prob(C=F|A=F)) =
0.7*0.4 / (0.7 * 0.4 + 0.2 * 0.6) = 0.7
Hello, Nice Solution, thanks. Can you describe in term of P and Q ?
and another question, you say Consider the following Bayesian network:? there is not figure here..
- Badges
- Science topic
- Similar topics
- Medicine
- Physiology
- Biosignals
- Biomedical Signal Processing
- Statistical Learning