Constraint-based Causal Discovery: Conflict Resolution with Answer Set Programming

Antti Hyttinen California Institute of Technology, Frederick Eberhardt Caltech, Matti Järvisalo HIIT/University of Helsinki
Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, PMLR R12:27-36, 2014.

Abstract

Recent approaches to causal discovery based on Boolean satisfiability solvers have opened new opportunities to consider search spaces for causal models with both feedback cycles and unmeasured confounders. However, the available methods have so far not been able to provide a principled account of how to handle conflicting constraints that arise from statistical variability. Here we present a new approach that preserves the versatility of Boolean constraint solving and attains a high accuracy despite the presence of statistical errors. We develop a new logical encoding of (in)dependence constraints that is both well suited for the domain and allows for faster solving. We represent this encoding in Answer Set Programming (ASP), and apply a state-of-the-art ASP solver for the optimization task. Based on different theoretical motivations, we explore a variety of methods to handle statistical errors. Our approach currently scales to cyclic latent variable models with up to seven observed variables and outperforms the available constraint-based methods in accuracy.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR12-technology14a, title = {Constraint-based Causal Discovery: Conflict Resolution with Answer Set Programming}, author = {Technology, Antti Hyttinen California Institute of and Caltech, Frederick Eberhardt and Helsinki, Matti J{\"a}rvisalo HIIT/University of}, booktitle = {Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence}, pages = {27--36}, year = {2014}, editor = {Zhang, Nevin L. and Tian, Jin}, volume = {R12}, series = {Proceedings of Machine Learning Research}, month = {23--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r12/main/assets/technology14a/technology14a.pdf}, url = {https://proceedings.mlr.press/r12/technology14a.html}, abstract = {Recent approaches to causal discovery based on Boolean satisfiability solvers have opened new opportunities to consider search spaces for causal models with both feedback cycles and unmeasured confounders. However, the available methods have so far not been able to provide a principled account of how to handle conflicting constraints that arise from statistical variability. Here we present a new approach that preserves the versatility of Boolean constraint solving and attains a high accuracy despite the presence of statistical errors. We develop a new logical encoding of (in)dependence constraints that is both well suited for the domain and allows for faster solving. We represent this encoding in Answer Set Programming (ASP), and apply a state-of-the-art ASP solver for the optimization task. Based on different theoretical motivations, we explore a variety of methods to handle statistical errors. Our approach currently scales to cyclic latent variable models with up to seven observed variables and outperforms the available constraint-based methods in accuracy.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Constraint-based Causal Discovery: Conflict Resolution with Answer Set Programming %A Antti Hyttinen California Institute of Technology %A Frederick Eberhardt Caltech %A Matti Järvisalo HIIT/University of Helsinki %B Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2014 %E Nevin L. Zhang %E Jin Tian %F pmlr-vR12-technology14a %I PMLR %P 27--36 %U https://proceedings.mlr.press/r12/technology14a.html %V R12 %X Recent approaches to causal discovery based on Boolean satisfiability solvers have opened new opportunities to consider search spaces for causal models with both feedback cycles and unmeasured confounders. However, the available methods have so far not been able to provide a principled account of how to handle conflicting constraints that arise from statistical variability. Here we present a new approach that preserves the versatility of Boolean constraint solving and attains a high accuracy despite the presence of statistical errors. We develop a new logical encoding of (in)dependence constraints that is both well suited for the domain and allows for faster solving. We represent this encoding in Answer Set Programming (ASP), and apply a state-of-the-art ASP solver for the optimization task. Based on different theoretical motivations, we explore a variety of methods to handle statistical errors. Our approach currently scales to cyclic latent variable models with up to seven observed variables and outperforms the available constraint-based methods in accuracy. %Z Reissued by PMLR on 04 October 2026.
APA
Technology, A.H.C.I.o., Caltech, F.E. & Helsinki, M.J.H.o.. (2014). Constraint-based Causal Discovery: Conflict Resolution with Answer Set Programming. Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R12:27-36 Available from https://proceedings.mlr.press/r12/technology14a.html. Reissued by PMLR on 04 October 2026.

Related Material