Interactive demo · Probabilistic Machine Learning: Advanced Topics · Chapter 30

The PC algorithm and Markov equivalence

The PC algorithm removes an edge as soon as it finds a set that makes two variables conditionally independent, trying sets of size 0, 1, 2, …, then orients the v-structures and propagates. Even with infinite data it can only return the essential graph of the true DAG: the edges that Markov equivalence leaves reversible stay undirected. Compare the output with the true essential graph while you change the data.

True DAG

Independence test

Number of cases N

Test level α

Try these

Data are simulated from a linear Gaussian model on the true DAG (weights of both signs, unit noise); independence is tested by Fisher’s z test of the partial correlation, and the oracle uses d-separation in the true DAG, which is what infinitely many cases would give. The number of cases uses the first N rows of one fixed data set.

In the lecture notes