Consistency Guarantees for Greedy Permutation-Based Causal Inference Algorithms
From MaRDI portal
Publication:6283072
DOI10.1093/BIOMET/ASAA104arXiv1702.03530WikidataQ130530797 ScholiaQ130530797MaRDI QIDQ6283072FDOQ6283072
Authors: Liam Solus, Yuhao Wang, Caroline Uhler 
Publication date: 12 February 2017
Abstract: Directed acyclic graphical models, or DAG models, are widely used to represent complex causal systems. Since the basic task of learning such a model from data is NP-hard, a standard approach is greedy search over the space of directed acyclic graphs or Markov equivalence classes of directed acyclic graphs. As the space of directed acyclic graphs on nodes and the associated space of Markov equivalence classes are both much larger than the space of permutations, it is desirable to consider permutation-based greedy searches. Here, we provide the first consistency guarantees, both uniform and high-dimensional, of a greedy permutation-based search. This search corresponds to a simplex-like algorithm operating over the edge-graph of a sub-polytope of the permutohedron, called a DAG associahedron. Every vertex in this polytope is associated with a directed acyclic graph, and hence with a collection of permutations that are consistent with the directed acyclic graph ordering. A walk is performed on the edges of the polytope maximizing the sparsity of the associated directed acyclic graphs. We show via simulated and real data that this permutation search is competitive with current approaches.
This page was built for publication: Consistency Guarantees for Greedy Permutation-Based Causal Inference Algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6283072)
