CISPA
Browse
cispa_all_2915.pdf (425.43 kB)

Approximating Algorithmic Conditional Independence for Discrete Data

Download (425.43 kB)
conference contribution
posted on 2023-11-29, 18:10 authored by Alexander Marx, Jilles VreekenJilles Vreeken
Testing for conditional independence is a core part of constraint-based causal discovery. It is mainly used to find associations, but can in special cases also be applied to infer causal arrows. We specifically focus on discrete data. Although commonly used tests are perfect in theory, due to data sparsity they often fail to reject independence in practice—especially when conditioning on multiple variables. We propose a new conditional independence test based on the notion of algorithmic independence. To instantiate this ideal formulation in practice, we use stochastic complexity. We show that our proposed test SCI is an asymptotically unbiased estimator for conditional mutual information (CMI) as well as L2 consistent. Further, we show that SCI can be reformulated to find a sensible threshold for CMI that works well given only limited data. Empirical evaluation shows that SCI has a lower type II error than commonly used tests, which leads to a higher recall when we use it in causal discovery algorithms; without compromising the precision.

History

Preferred Citation

Alexander Marx and Jilles Vreeken. Approximating Algorithmic Conditional Independence for Discrete Data. In: National Conference of the American Association for Artificial Intelligence (AAAI). 2019.

Primary Research Area

  • Empirical and Behavioral Security

Name of Conference

National Conference of the American Association for Artificial Intelligence (AAAI)

Legacy Posted Date

2019-06-07

Open Access Type

  • Unknown

BibTeX

@inproceedings{cispa_all_2915, title = "Approximating Algorithmic Conditional Independence for Discrete Data", author = "Marx, Alexander and Vreeken, Jilles", booktitle="{National Conference of the American Association for Artificial Intelligence (AAAI)}", year="2019", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC