Monday, October 15, 2007

[Thinking cap questions on bayes networks]

0.1. Gi ven a 5 boolean random variables, how many different joint distributions can you write on them?
    If now I give the topology of a bayes network on these 5 variables, how many different joint distributions can you write?
 
 
 0.2. Given a bayes network on 5 nodes that has *no* edges (i.e., all nodes are disconnected), exactly many different conditional independence assertions does the network capture? (linear? polynomial or exponential?)
 
 
1. You have been given the topology of a bayes network, but haven't yet gotten the conditional probability tables
    (to be concrete, you may think of the pearl alarm-earth quake scenario bayes net).
    Your friend shows up and says he has the joint distribution all ready for you. You don't quite trust your
    friend and think he is making these numbers up. Is there any way you can prove that your friends' joint
    distribution is not correct?


2. Continuing bad friends, in the question above, suppose a second friend comes along and says that he can give you
   the conditional probabilities that you want to complete the specification of your bayes net. You ask him a CPT entry,
   and pat comes a response--some number between 0 and 1. This friend is well meaning, but you are worried that the
   numbers he is giving may lead to some sort of inconsistent joint probability distribution. Is your worry justified ( i.e., can your
   friend give you numbers that can lead to an inconsistency?)

  (To understand "inconsistency", consider someone who insists on giving you P(A), P(B), P(A&B) as well as P(AVB)  and they
wind up not satisfying the P(AVB)= P(A)+P(B) -P(A&B)
[or alternately, they insist on giving you P(A|B), P(B|A), P(A) and P(B), and the four numbers dont satisfy the bayes rule]

3. (mentioned in the class)
Your friend heard your claims that Bayes Nets can represent any possible conditional independence assertions exactly. He comes to you
and says he has four random variables, X, Y, W and Z, and only TWO conditional independence assertions:

X .ind. Y |  {W,Z}
W .ind. X  |  {X, Y}

He dares you to give him a bayes network topology on these four nodes that exactly represents these and only these conditional independencies.
Can you? (Note that you only need to look at 4 vertex directed graphs).
 
 
4. As foreshadowed in the class, the answer to 3 above is going to be "No". How serious an issue do you think this is? In particular, suppose your domain has exactly set A of conditional independencies. You have two bayes network configurations B1 and B2. The CIA(B1) is a superset of
A and CIA(B1) is a subset of A.   Clearly, neither B1 nor B2 exactly represent what you know about the domain. If you have to choose one to model the domain, what are the tradeoffs in choosing B1 vs. B2?
 
 
Rao
-------------
 

 

1 comment:

Ina said...

0.1 We would need 2^5 entries for the Joint distribution. But as we can have any value between 0 and 1 for any of them there could be infinite entries satisfying it?
0.2 X||Y|Z where X, Y, Z are subsets of variables gives us exponential different conditional Independence Assertions. Not sure of the exact value though as if we start with 2^5 * 2^5 * 2^5 ; it makes little sense to say that the same set is independent of itself given itself? Thus maybe we need to consider smaller sets for Y and Z as 2^5 * 2^4 * 2^3?
1. Yes, we can check if any of Independence property of the network does not hold for example:
P(MaryCalls|Alarm ) != P(MaryCalls| Alarm, Earthquake, Burglary) these probabilities can be calculated from the joint distribution and verified.
2. If the conditional properties for a particular case say Alarm add up to more than one you would have inconsistent joint probability distribution. I.e. if he says 0.5 for all his answers and you end up trying to fill the table for Alarm with all four entries as 0.5 then it cannot be allowed as the sum would have to be < 1.
4. In choosing B1 where CIA(B1) is superset, we have more conditional Independence i.e. the graph connections are sparse than the actual case. We can use that to simplify the problem.However B2 where CIA(B2) is a subset, has more restrictions, but we can't be sure that the added edges/connections benefit us to draw any other conclusions.
-Ina