Searching through Markov equivalent directed acyclic graphs with the DECS algorithm

Thumbnail Image
Massie, Marie-Angelique
Journal Title
Journal ISSN
Volume Title
University of Guelph

Model selection in graphical Markov models has been a challenging problem. The number of possible directed acyclic graphs (DAGs) grows super-exponentially as the number of variables increases and many of these DAGs encode the same conditional independence relations. Searching through DAG equivalence classes reduces the search space, hence making the search more efficient. The DAG equivalence class search (DECS) algorithm extends to DAG equivalence classes a search over undirected graph for the most simple graph consistent with the data. I provide a graphical criterion for the submodel relation for graphs with four or fewer nodes. I also provide insights into the graphical criterion needed for the submodel relations for graphs over more than four nodes. I use this criterion in the DECS algorithm to move across DAG equivalence classes. Finally. I also demonstrate the DECS algorithm on both real and simulated data sets.

Markov models, Graphical, Acyclic graphs, DECS algorithm, Conditional independence relations