Apr 8

3:30 pm

## A Unified Approach to Representing the Structure of Markov Equivalence Classes

### Thomas Richardson

Seminar

Carnegie Mellon University - Department of Philosophy

A great deal of research has focused upon the relationship between conditional independencies and the 'structure' of a statistical model. (Kiiveri & Speed; Cox & Wermuth; Andersson, Madigan & Perlman; Lauritzen et al.; Pearl et al.; Spirtes et al.; among others.)

The Global Directed Markov condition is central to much of this work; it associates a set of conditional independence relations with a directed acyclic graph (DAG) which naturally represents the structure of the model. A wide range of (parametric and non-parametric) statistical models can be represented using this formalism, including recursive linear structural equation models with independent errors, regression models, factor analytic models, path models, bayes nets. Given a set of conditional independencies there may be many different directed acyclic graphs which will entail these independencies under the Global Directed Markov condition; any two graphs entailing the same conditional independencies are said to be Markov Equivalent. Verma & Pearl, and independently, Frydenberg, characterized the features that all Markov equivalent DAGs have in common.

The work I shall be presenting here considers a number of extensions of the DAG framework: (i) the conditional independence structure of DAG models under marginalization, e.g. where there are latent variables or correlated errors, (ii) the conditional independence structure of DAG models under conditionalization on an unmeasured variable, which may be used to study selection bias, (iii) sets of conditional independencies entailed by the Global Directed Markov condition applied to directed cyclic graphs, which may be used to represent conditional independencies in non-recursive structural equation models.

I will describe a graphical object, which I call a Partial Ancestral Graph (PAG), for representing features common to all of the models in a given Markov equivalence class. PAGs may be used to represent information about Markov equivalence classes for any one of the families of models, (i)-(iii) described above. There exist polynomial (in the number of vertices) time algorithms for constructing the PAG given a model. Further, there are algorithms for constructing a PAG given only an oracle for deciding conditional independencies; these algorithms are polynomial (in the number of vertices) time for sparse graphs.