I'm studying the PC algorithm for learning the structure of a Bayesian Network.

One of the steps refers to performing several rounds of conditional independence tests of increasing order, zero, first, second...

What does the order refer to?


Jeremy's own answer is correct, but I would like to add some details, and why the order matters at all.

The SGS Algorithm

Suppose there is a set of variables $\mathcal{P}$ from which we wish to construct a conditional independence network. This is a network of connections between variables which, given their relationship with all other variables, still have a non-zero partial correlation.

The SGS algorithm (named after the authors)$^\dagger$ does so by starting from a dense network and then pruning edges by running a series of tests for conditional independence $X \perp \!\!\!\! \perp Y \; | \; \mathbf{Z}$, for all choices of $X, Y, \mathbf{Z} \subseteq \mathcal{P}$. Note that $\boldsymbol{Z}$ could be a set of multiple variables, since relationships like:

conditional independence network

still imply conditional independence of $X$ and $Y$. Any two variables for which a path is found that explains away their dependence are conditionally independent and have their edge removed. The result is then a (sparse) graph of direct relationships only.

The problem with the SGS algorihtm is that as the number of variables in $p$ grows, the number of conceivable tests does too, very rapidly. In fact, pruning edges by testing all possible paths is NP-hard.

The PC Algorithm

The PC algorithm (named after a subset of the same authors)$^\ddagger$ is an improvement of the SGS algorithm with the same assumptions and resulting graph. It works by ordering the tests hierarchically, and pruning along the way:

  • The $0^\text{th}$ order tests for direct independence $X \perp \!\!\!\! \perp Y$;
  • The $1^\text{st}$ order tests for independence conditional on a single third variable $X \perp \!\!\!\! \perp Y \; | \; Z$;
  • The $2^\text{nd}$ order tests for independence conditional on two variables $X \perp \!\!\!\! \perp Y \; | \; Z_1, Z_2$
  • $\dots$
  • The $(p-2)^\text{th}$ order tests condition on all remaining variables: $X \perp \!\!\!\! \perp Y \; | \; Z_1, Z_2, \dots, Z_{p-2}$

The order matters because there exist fewer low order tests than high order tests. Any elimination in the lower orders will speed up the higher orders by reducing the number of remaining paths.

The justification for this approach is that the existence of any path that 'explains away' the dependence between $X$ and $Y$ is sufficient to conclude their conditional independence. In addition, if $X \perp \!\!\!\! \perp Y$, there is no reason to seek such a path.

In the worst case scenario (the true graph is dense), the algorithm still evaluates all possible paths. However, we are usually interested in a presumed sparse true graph, for which the time complexity tends to polynomial. The sparser the underlying graph, the greater the benefit of ordering the tests.

$\dagger$: Spirtes, Peter & Glymour, Clark & Scheines, Richard. (1993). Causation, Prediction, and Search. 10.1007/978-1-4612-2748-9.

$\ddagger$: Spirtes, Peter & Glymour, Clark & Scheines, Richard. (2000). Causation, Prediction, and Search, 2nd Edition.

| cite | improve this answer | |

From further study of the algorithm, I'm going to make an educated guess, it the hope that someone can confirm or correct!!!

The order refers to the number of variables that are conditioned on.

  • Zero order: Test for A and B independent
  • First order: Test for A and B independent given C
  • Second order: Test for A and B independent given C and D
  • etc...
| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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