On the finite sample complexity of causal discovery and the value of domain expertise

Wadhwa, Samir

Permalink

https://hdl.handle.net/2142/110577 Copy

Description

Title

On the finite sample complexity of causal discovery and the value of domain expertise

Author(s)

Wadhwa, Samir

Issue Date

2021-04-28

Director of Research (if dissertation) or Advisor (if thesis)

Dong, Roy

Committee Member(s)

Dullerud, Geir Eirik

Department of Study

Mechanical Sci & Engineering

Discipline

Mechanical Engineering

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

• causality
• discrete Bayesian networks
• conditional independence testing
• family-wise error rate

Abstract

Causal discovery methods seek to identify causal relations between random variables from purely observational data, as opposed to actively collected experimental data where an experimenter intervenes on a subset of correlates. One of the seminal works in this area is the Inferred Causation (IC) algorithm, which guarantees successful causal discovery under the assumption of a conditional independence (CI) oracle: an oracle that can states whether two random variables are conditionally independent given another set of random variables. Practical implementations of this algorithm incorporate statistical tests for conditional independence, in place of a CI oracle. In this thesis, we analyze the sample complexity of causal discovery algorithms without a CI oracle: given a certain level of confidence, how many data points are needed for a causal discovery algorithm to identify a causal structure? Furthermore, our methods allow us to quantify the value of domain expertise in terms of data samples. Finally, we demonstrate the accuracy of these sample rates with numerical examples, and quantify the benefits of three types of domain expertise: sparsity priors, known causal directions, and known conditional dependencies.

Graduation Semester

2021-05

Type of Resource

Thesis

Permalink

http://hdl.handle.net/2142/110577

Copyright and License Information

Copyright 2021 Samir Wadhwa

Owning Collections