Lecture 9: Markov Equivalence and Structure Learning

In theory structure learning algorithms are quite clear, but in practice they are quite complicated. They are not used super often in practice for several reason, we will discuss in this lecture.

Objectives:

  • When are two Bayesian networks statistically equivalent?
    • After structure learning, may end up with many equivalent structures that are compatible with the data.
  • What's the concept of faithfulness to a probability solution?
  • How can a Bayesian network structure be derived from data?

Faithfulness assumption

So far we assumed networks are designed by a human expert. But there is no strong theory how a network should look like; this field suffers from a lack of theory; and we require a lot of knowledge to come up with a network.

Question: Can we derive networks automatically without prior knowledge?

A structure learning problem has

  • input: probability distribution P
    • In practice, we have a dataset instead of direct access to a probability distribution
  • output: a Bayesian network G such that P is consistent with G.

Consistency is fully determined by conditional independence: P is consistent with G iff every conditional independence implied by G holds in P.

Because consistency needs the conditional independence implications rather than the OG probability distribution, this allows a rephrasing of the input:

Consistency: the graph cannot be "contradicted" by the data.

  • input: list of conditional independence statements holding in probability distribution P
  • output: a Bayesian network G such that P is consistent with G.

In practice, we need to infer the conditional independence statements from data.

Really study the formulation of consistency! We have to avoid independences that are not given in the data. Otherwise we could satisfy this by just always outputting an empty graph.

If input X _ | | _ Y | M (found from the data, not the model!), then e.g. X M Y is not a valid solution, because it implies independences other than the input.

Possible solutions:

X <- M -> Y

X -> M -> Y

X <- M <- Y

Logic question: how could you change a solution such that we find another solution?

Removing an arrow produces a new conditional independence statement, which is not allowed. So we cannot remove arrows.

Can we add arrows instead? However, complete graphs are also accepted; since they do not make any claims, they are consistent by definition.

This means that in total we have 2^3 - 2 (amount of possible cycles) possible consistent network configurations.

So we see the problem: we have too many consistent graphs that are trivially consistent by connecting too much. We need to solve this.

Trivial consistency and model complexity

Faithfulness: we have a lot of graphs that fullfil the input conditional independencies.

Apply Occam's Razor: prefer the simplest DAG. One way to define simple is by just picking the solution with the fewest edges.

(So also less parameters to fit; less change of "overfitting")

Concept of faithfulness

A BN network G is faithful to prob. distribution P when G implies exactly the set of conditional independences that hold in P (instead of a subset). Using consistency only, it's OK to only imply a subset of the independences in P.

This is a heuristic to apply Occam's razor.

But we should not assume that only faithful networks are interesting; and the "true" causal diagram behind the generation of P does not need to be faithful to P.

N.B. Faithfulness is symmetric, unlike consistency.

Markov Equivalent

Consider X -> M -> Y, X <- M <- Y both imply only one conditional independence, X ind. Y | M.

This means they are statistically equivalent, i.e. consistent with exactly the same probability distributions. Such networks are called Markov equivalent.

We may end up with some Markov equivalent networks, so then we still need domain expertise to decide on the best network (e.g. check if arrows go again the direction of time).

Markov Equivalence Classes

The set of all markov equivalent networks is a Markov equivalent class of some BN G.

daggity has equivalentDAGs( g ) command.

Definitions

Skeleton of G is undirected version of the same graph g.

V-structure in G is set of three variables such that U -> V <- W is an induced subgraph of G.

N.b. implies that we do not have U -> W or U <- W; so V-structure is not the same as a collider.

V-structures imply the direction of the edges is "locked", because changing one will disrupt the V structure and change the Markov equivalence class.

That is, any separating set between U and W must not include V. If we switch any edge direction, V has to be in the separating set to make U and W independent.

Markov equivalence iff

  • G and H have same skeleton
  • G and H have the same v-structures

This will almost certainly be in the exam.

Graph Patterns and CPDAGs

If we make a mixed graph in which only the edges that are part of v-structures are drawn directed and the others undirected, then we have a graph pattern.

Some edges will change the v-structure when they change direction; so here we know their direction. If we fill in all these edges we get a CPDAG (completed partially directed acyclic graph).

These are intended to be representations of equivalence classes, but they are not that easy to read.

CPDAGs are suitable representations for faithful graphs.

Bringing it together: faithful structure learning problem

Input: conditional independences holding in prob. distribution P

Output: a CPDAG G such that P is faithful to all DAGs represented by G.

The IC algorithm

The inferred causation algorithm has two steps.

  1. Infer skeleton
    • Start with a graph with no edges
    • For each variable pair X, Y search for a set Z(XY) such that either a) X ind. Y | Z(XY) is in the input list or b)is a consequence from the implications in the input list.
    • If such a set does not exist, add an undirected edge between X and Y; i.e. we have not found a possibility to make them independent, but we do not necessarily know the direction of the arrow.
    • N.B. you will re-use Z(XY) for step 2
  2. Infer v-structure
    • For each X and Y that is not linked, we check whether it has a v-structure through any neighbour W. If it has a v-structure, this would mean that W is not in separating set Z(XY), so add arrows pointing to W, X->W<-Y.
    • N.B. in the other case, we leave the arrows undirected; because we have multiple equivalence classes.
  3. Orient edges in the graph pattern where possible to create a CPDAG.

It's a simple procedure, but its complexity is terrible because it requires inspection of all subsets of variables (exponential time). So pretty unusable for any non-trivial network.

PC algorithm

Structure learning is NP-hard, but we can do better than the default IC algorithm by not starting with an empty but with a complete graph (I guess with undirected edges).

In IC we add an edge when Z(XY) does not exist. Here we take the opposite approach: when any Z(X,Y) exists for which X ind. Y | Z(X,Y), then remove the edge between X and Y. Which makes sense; otherwise they would be dependent in any case.

Rest stays the same as for IC.

This is more efficient for several reasons. We can start looking for small sets Z(X, Y). We first start with an empty Z(X, Y), i.e. which variables are unconditionally independent? We can check this with a simple correlation test and using a cutoff, e.g. 0.05 correlation.

This already limits the amount of subsets we have to check tremendously!

Learning algorithms are the main focus of bnlearn.

?pc.stable

give them dataset as input;

Important insight: these structure learning algorithms still rely on conditional independence testing.

This also means that it suffers from the same issues as we encountered before (e.g. chi-squared being unstable when conditioning upon too many things).