University of Illinois Urbana-Champaign

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

Wadhwa, Samir

Content Files
WADHWA-THESIS-2021.pdf

Permalink

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

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
Date of Ingest
2021-09-17T01:13:28Z
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

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois
Dissertations and Theses - Mechanical Science and Engineering