Hybrid Top-Down Global Causal Discovery with Local Search for Linear and Nonlinear Additive Noise Models
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929672956149760 |
|---|---|
| author | Hiremath, Sujai Maasch, Jacqueline R. M. A. Gao, Mengxiao Ghosal, Promit Gan, Kyra |
| author_facet | Hiremath, Sujai Maasch, Jacqueline R. M. A. Gao, Mengxiao Ghosal, Promit Gan, Kyra |
| contents | Learning the unique directed acyclic graph corresponding to an unknown causal model is a challenging task. Methods based on functional causal models can identify a unique graph, but either suffer from the curse of dimensionality or impose strong parametric assumptions. To address these challenges, we propose a novel hybrid approach for global causal discovery in observational data that leverages local causal substructures. We first present a topological sorting algorithm that leverages ancestral relationships in linear structural causal models to establish a compact top-down hierarchical ordering, encoding more causal information than linear orderings produced by existing methods. We demonstrate that this approach generalizes to nonlinear settings with arbitrary noise. We then introduce a nonparametric constraint-based algorithm that prunes spurious edges by searching for local conditioning sets, achieving greater accuracy than current methods. We provide theoretical guarantees for correctness and worst-case polynomial time complexities, with empirical validation on synthetic data. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_14496 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Hybrid Top-Down Global Causal Discovery with Local Search for Linear and Nonlinear Additive Noise Models Hiremath, Sujai Maasch, Jacqueline R. M. A. Gao, Mengxiao Ghosal, Promit Gan, Kyra Machine Learning Learning the unique directed acyclic graph corresponding to an unknown causal model is a challenging task. Methods based on functional causal models can identify a unique graph, but either suffer from the curse of dimensionality or impose strong parametric assumptions. To address these challenges, we propose a novel hybrid approach for global causal discovery in observational data that leverages local causal substructures. We first present a topological sorting algorithm that leverages ancestral relationships in linear structural causal models to establish a compact top-down hierarchical ordering, encoding more causal information than linear orderings produced by existing methods. We demonstrate that this approach generalizes to nonlinear settings with arbitrary noise. We then introduce a nonparametric constraint-based algorithm that prunes spurious edges by searching for local conditioning sets, achieving greater accuracy than current methods. We provide theoretical guarantees for correctness and worst-case polynomial time complexities, with empirical validation on synthetic data. |
| title | Hybrid Top-Down Global Causal Discovery with Local Search for Linear and Nonlinear Additive Noise Models |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2405.14496 |