What exactly would be a perfect map in this situation? Is a perfect map a distribution which has the same independence assumptions?

Question

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:

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?

Answer 1

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.