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
Type
research article
Web of Science ID

WOS:001137613500001

Author(s)
Mokhtarian, Ehsan  
Salehkaleybar, Saber  
Ghassami, AmirEmad

Boston University

Kiyavash, Negar  
Date Issued

2023-12-01

Published in
Journal of Machine Learning Research
Volume

24

Issue

118

Start page

354

Subjects

experiment design

•

cyclic graphs

•

cyclic SCMs

•

causal structure learning

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
BAN  
FunderFunding(s)Grant NumberGrant URL

Swiss National Science Foundation under NCCR Automation

51NF40 180545

Available on Infoscience
September 12, 2024
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/195621.2
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