SAT-based causal discovery under weaker assumptions

Zhalama, Jiji ZHANG, Frederick EBERHARDT, Wolfgang MAYER

Research output: Book Chapters | Papers in Conference ProceedingsConference paper (refereed)Researchpeer-review

2 Citations (Scopus)

Abstract

Using the flexibility of recently developed methods for causal discovery based on Boolean satisfiability (SAT) solvers, we encode a variety of assumptions that weaken the Faithfulness assumption. The encoding results in a number of SAT-based algorithms whose asymptotic correctness relies on weaker conditions than are standardly assumed. This implementation of a whole set of assumptions in the same platform enables us to systematically explore the effect of weakening the Faithfulness assumption on causal discovery. An important effect, suggested by simulation results, is that adopting weaker assumptions greatly alleviates the problem of conflicting constraints and substantially shortens solving time. As a result, SAT-based causal discovery is potentially more scalable under weaker assumptions.

Original languageEnglish
Title of host publicationProceedings of the 33rd Conference on Uncertainty in Artificial Intelligence (UAI)
PublisherAssociation for Uncertainty in Artificial Intelligence (AUAI)
Publication statusPublished - 1 Jan 2017
Event33rd Conference on Uncertainty in Artificial Intelligence, UAI 2017 - Sydney, Australia
Duration: 11 Aug 201715 Aug 2017

Conference

Conference33rd Conference on Uncertainty in Artificial Intelligence, UAI 2017
Abbreviated titleUAI 2017
CountryAustralia
CitySydney
Period11/08/1715/08/17

Cite this

Zhalama, ZHANG, J., EBERHARDT, F., & MAYER, W. (2017). SAT-based causal discovery under weaker assumptions. In Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence (UAI) [234] Association for Uncertainty in Artificial Intelligence (AUAI).
Zhalama, ; ZHANG, Jiji ; EBERHARDT, Frederick ; MAYER, Wolfgang. / SAT-based causal discovery under weaker assumptions. Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence (UAI). Association for Uncertainty in Artificial Intelligence (AUAI), 2017.
@inproceedings{77d30c54530e4bc8b4539894daf8d3e7,
title = "SAT-based causal discovery under weaker assumptions",
abstract = "Using the flexibility of recently developed methods for causal discovery based on Boolean satisfiability (SAT) solvers, we encode a variety of assumptions that weaken the Faithfulness assumption. The encoding results in a number of SAT-based algorithms whose asymptotic correctness relies on weaker conditions than are standardly assumed. This implementation of a whole set of assumptions in the same platform enables us to systematically explore the effect of weakening the Faithfulness assumption on causal discovery. An important effect, suggested by simulation results, is that adopting weaker assumptions greatly alleviates the problem of conflicting constraints and substantially shortens solving time. As a result, SAT-based causal discovery is potentially more scalable under weaker assumptions.",
author = "Zhalama and Jiji ZHANG and Frederick EBERHARDT and Wolfgang MAYER",
year = "2017",
month = "1",
day = "1",
language = "English",
booktitle = "Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence (UAI)",
publisher = "Association for Uncertainty in Artificial Intelligence (AUAI)",

}

Zhalama, , ZHANG, J, EBERHARDT, F & MAYER, W 2017, SAT-based causal discovery under weaker assumptions. in Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence (UAI)., 234, Association for Uncertainty in Artificial Intelligence (AUAI), 33rd Conference on Uncertainty in Artificial Intelligence, UAI 2017, Sydney, Australia, 11/08/17.

SAT-based causal discovery under weaker assumptions. / Zhalama, ; ZHANG, Jiji; EBERHARDT, Frederick; MAYER, Wolfgang.

Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence (UAI). Association for Uncertainty in Artificial Intelligence (AUAI), 2017. 234.

Research output: Book Chapters | Papers in Conference ProceedingsConference paper (refereed)Researchpeer-review

TY - GEN

T1 - SAT-based causal discovery under weaker assumptions

AU - Zhalama,

AU - ZHANG, Jiji

AU - EBERHARDT, Frederick

AU - MAYER, Wolfgang

PY - 2017/1/1

Y1 - 2017/1/1

N2 - Using the flexibility of recently developed methods for causal discovery based on Boolean satisfiability (SAT) solvers, we encode a variety of assumptions that weaken the Faithfulness assumption. The encoding results in a number of SAT-based algorithms whose asymptotic correctness relies on weaker conditions than are standardly assumed. This implementation of a whole set of assumptions in the same platform enables us to systematically explore the effect of weakening the Faithfulness assumption on causal discovery. An important effect, suggested by simulation results, is that adopting weaker assumptions greatly alleviates the problem of conflicting constraints and substantially shortens solving time. As a result, SAT-based causal discovery is potentially more scalable under weaker assumptions.

AB - Using the flexibility of recently developed methods for causal discovery based on Boolean satisfiability (SAT) solvers, we encode a variety of assumptions that weaken the Faithfulness assumption. The encoding results in a number of SAT-based algorithms whose asymptotic correctness relies on weaker conditions than are standardly assumed. This implementation of a whole set of assumptions in the same platform enables us to systematically explore the effect of weakening the Faithfulness assumption on causal discovery. An important effect, suggested by simulation results, is that adopting weaker assumptions greatly alleviates the problem of conflicting constraints and substantially shortens solving time. As a result, SAT-based causal discovery is potentially more scalable under weaker assumptions.

UR - http://auai.org/uai2017/proceedings/papers/234.pdf

UR - http://commons.ln.edu.hk/sw_master/6104

M3 - Conference paper (refereed)

BT - Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence (UAI)

PB - Association for Uncertainty in Artificial Intelligence (AUAI)

ER -

Zhalama , ZHANG J, EBERHARDT F, MAYER W. SAT-based causal discovery under weaker assumptions. In Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence (UAI). Association for Uncertainty in Artificial Intelligence (AUAI). 2017. 234