Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. A Unified Experiment Design Approach for Cyclic and Acyclic Causal Models
 
research article

A Unified Experiment Design Approach for Cyclic and Acyclic Causal Models

Mokhtarian, Ehsan  
•
Salehkaleybar, Saber  
•
Ghassami, AmirEmad
Show more
December 1, 2023
Journal of Machine Learning Research

We study experiment design for unique identification of the causal graph of a system where the graph may contain cycles. The presence of cycles in the structure introduces major challenges for experiment design as, unlike acyclic graphs, learning the skeleton of causal graphs with cycles may not be possible from merely the observational distribution. Furthermore, intervening on a variable in such graphs does not necessarily lead to orienting all the edges incident to it. In this paper, we propose an experiment design approach that can learn both cyclic and acyclic graphs and hence, unifies the task of experiment design for both types of graphs. We provide a lower bound on the number of experiments required to guarantee the unique identification of the causal graph in the worst case, showing that the proposed approach is order-optimal in terms of the number of experiments up to an additive logarithmic term. Moreover, we extend our result to the setting where the size of each experiment is bounded by a constant. For this case, we show that our approach is optimal in terms of the size of the largest experiment required for uniquely identifying the causal graph in the worst case.

  • Files
  • Details
  • Versions
  • Metrics
Loading...
Thumbnail Image
Name

22-1425-2.pdf

Type

Main Document

Version

Published version

Access type

openaccess

License Condition

CC BY

Size

600.53 KB

Format

Adobe PDF

Checksum (MD5)

f545498f4a2982cfe637aa0577f9ff94

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés