1
$\begingroup$

I am currently studying Bayesian Reasoning and Machine Learning by David Barber, the 4th chapter exercise 4.7 (p 80). The exercise is the following:

Consider the following belief network: enter image description here

  1. Write down a Markov Network of $p(x_1,x_2,x_3)$
  2. Is your Markov Network a perfect map of $p(x_1,x_2,x_3)$?

I have done 1. It was simple - just sum over $h_1$ and $h_1$ and then $x_1,x_2,x_3$ are coupled and my solution is the same as in the solution manual. I didn't know how to do (2) so I looked at the solution manual and didn't quite understand their answer:

This is not a perfect map since in $p(x_1,x_2,x_3)$ we have $x_1 \perp\kern-5pt\perp x_3 | \emptyset$, which is violated by the Markov Network representation.

I don't fully understand 2 things:

  1. What exactly would be a perfect map in this situation? (an example of a perfect map would be great) Is a perfect map a distribution which has the same independence assumptions?

  2. Isn't the independence $x_1 \perp\kern-5pt\perp x_2 | \emptyset$ also violated?

$\endgroup$

1 Answer 1

1
+50
$\begingroup$

Your first question:
The definition of a perfect map is given on page 77:

A graph G which is both an I-map and a D-map for P is called a perfect map.

So, a graph $G$ is a perfect map of a probability distribution $P$ if

  1. every separation (see Definitions 4.5 and 4.6 on page 68) in the graph $G$ is also a conditional independence relation in $P$, and
  2. every conditional independence relation in $P$ is a separation in the graph $G$.

The decisive point here is, that perfect maps do not always exist. There are distributions $P$ that don't admit a perfect map. And this marginalization of the graph of exercise 4.7 is an example. And here is why:

You have already figured out that there must be an edge between all three nodes $x_1, x_2$ and $x_3$. This is because if we condition on $x_3$, then $x_1$ and $x_2$ are still dependent, and it is clear that an undirected graph that is supposed to describe this must have an edge between $x_1$ and $x_2$. Similar arguments show the necessity of the edges between $x_2$ and $x_3$ and between $x_3$ and $x_1$ (for this last case, note that $x_2$ is a collider). I.e., the fully connected graph is the only candidate we have left. But unfortunately, since $x_2$ is a collider, we have $x_1 \perp\kern-5pt\perp x_3 | \emptyset$. But in our fully connected graph, $x_1$ and $x_3$ are not separated, thus there is no perfect map.

Your second question:
The independence $x_1 \perp\kern-5pt\perp x_2 | \emptyset$ does not hold. The nodes $x_1, x_2$ are dependent because of the path $x_1\leftarrow h_1 \to x_2$.

In general, this example shows that it is easy to create distributions without perfect maps from those with perfect maps by applying some smart marginalizations.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.