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. Conferences, Workshops, Symposiums, and Seminars
  4. Minimum Cost Intervention Design for Causal Effect Identification
 
conference paper not in proceedings

Minimum Cost Intervention Design for Causal Effect Identification

Akbari, Sina  
•
Etesami, Jalal  
•
Kiyavash, Negar  
2022
International Conference on Machine Learning 2022

Pearl's do calculus is a complete axiomatic approach to learn the identifiable causal effects from observational data. When such an effect is not identifiable, it is necessary to perform a collection of often costly interventions in the system to learn the causal effect. In this work, we consider the problem of designing the collection of interventions with the minimum cost to identify the desired effect. First, we prove that this problem is NP-hard, and subsequently propose an algorithm that can either find the optimal solution or a logarithmic-factor approximation of it. This is done by establishing a connection between our problem and the minimum hitting set problem. Additionally, we propose several polynomial-time heuristic algorithms to tackle the computational complexity of the problem. Although these algorithms could potentially stumble on sub-optimal solutions, our simulations show that they achieve small regrets on random graphs. 32 pages, 10 figures, ICML2022

  • Files
  • Details
  • Metrics
Type
conference paper not in proceedings
DOI
10.48550/arxiv.2205.02232
Author(s)
Akbari, Sina  
Etesami, Jalal  
Kiyavash, Negar  
Date Issued

2022

Publisher

PMLR

Total of pages

258-289

Subjects

NP-hard

•

Causal Identification

•

Experimental Design

•

Minimum-cost

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
BAN  
Event nameEvent place
International Conference on Machine Learning 2022

Baltimore, USA

Available on Infoscience
March 9, 2023
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/195628
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