← Back to papers
2007 JMLR JMLR 2007

Estimating High-Dimensional Directed Acyclic Graphs with the PC-Algorithm

Abstract

We consider the PC-algorithm (Spirtes et al., 2000) for estimating the skeleton and equivalence class of a very high-dimensional directed acyclic graph (DAG) with corresponding Gaussian distribution. The PC-algorithm is computationally feasible and often very fast for sparse problems with many nodes (variables), and it has the attractive property to automatically achieve high computational efficiency as a function of sparseness of the true underlying DAG. We prove uniform consistency of the algorithm for very high-dimensional, sparse DAGs where the number of nodes is allowed to quickly grow with sample size n, as fast as O(na) for any 0 < a < ∞. The sparseness assumption is rather minimal requiring only that the neighborhoods in the DAG are of lower order than sample size n. We also demonstrate the PC-algorithm for simulated data. [abs] [ pdf ][ bib ] © JMLR 2007. (edit, beta)

🌉 Interdisciplinary Bridge — Knowledge & Reasoning and Machine Learning
📈 Trend Setter — Causal Inference
🧭 Keyword Pioneer — high-dimensional datum
🐣 Hot Topic Early Bird — graphical model
🐝 Cross-Pollinator — Artificial Intelligence, Computer Science, Computer Vision, Data Science & Analytics, Deep Learning, Healthcare & Medicine, Interdisciplinary, Knowledge & Reasoning, Machine Learning, Mathematics & Optimization, Natural Language Processing, Reinforcement Learning

Authors

Markus Kalisch , Peter Bühlmann

Topics

Machine Learning > Core Methods > Representation Learning Knowledge & Reasoning > Reasoning > Causal Inference Machine Learning > Core Methods > Graphical Models

Keywords

structure learning causal discovery graphical model high-dimensional datum directed acyclic graph pc algorithm
Download PDF

Related papers

Statistical Consistency of Kernel Canonical Correlation Analysis 2007
A Probabilistic Analysis of EM for Mixtures of Separated, Spherical Gaussians 2007
Large Margin Semi-supervised Learning 2007
Refinable Kernels 2007
Building Blocks for Variational Bayesian Learning of Latent Variable Models 2007