2

From here:

An I-map is said to be perfect if $I(G)=I(p)$. Given a distribution $p$, it is not always possible to find a DAG $G$ such that $I(G)=I(p)$. Consider a joint distribution over four random variables such that $X_A \perp X_C|X_B,X_D$ and $X_B \perp X_D|X_A,X_C$ are the only conditional independence relations. One can verify that there is no four vertex DAG that implies only these conditional independence assumptions.

I am also aware that not even Markov networks are perfect maps for all probability distributions and so can't represent all conditional independencies. Why is this? I thought the whole point of probabilistic graphical models was to represent a joint distribution as efficiently as possible? If that is not possible, then how this problem overcome?

mhdadk
  • 4,940

1 Answers1

1

You can represent the joint distribution, no problem. The problem is that you cannot explicitly represent all the conditional independencies. The example given can be represented as a directed graph, but not as a directed acyclic graph.

You can work out the probability of $X_A$, and then get the probabilities $P(X_B | X_A)$ and $P(X_D | X_A)$, and then $P(X_C | X_B, X_D)$. This gives you a directed graph that contains a cycle. There is no way to represent this accurately without a cycle.

Robby the Belgian
  • 654
  • So then why do we use DAGs? Why not use directed cyclic graphs instead? – mhdadk Sep 26 '20 at 15:24
  • DAGs are a lot more computationally efficient. For each pair of variables, there is only 1 possible path leading from one to the other through conditional dependencies. So, when given the value of 1 variable, inference on the other is much easier in a DAG. Once you start talking about thousands or millions of variables, that's really the only way to do it -- the joint table would be much too large. – Robby the Belgian Sep 26 '20 at 15:55