Minimum Cost Intervention Design for Causal Effect Identification

Sina Akbari, Jalal Etesami, Negar Kiyavash
Proceedings of the 39th International Conference on Machine Learning, PMLR 162:258-289, 2022.

Abstract

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 prob-em is NP-complete, 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v162-akbari22a, title = {Minimum Cost Intervention Design for Causal Effect Identification}, author = {Akbari, Sina and Etesami, Jalal and Kiyavash, Negar}, booktitle = {Proceedings of the 39th International Conference on Machine Learning}, pages = {258--289}, year = {2022}, editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan}, volume = {162}, series = {Proceedings of Machine Learning Research}, month = {17--23 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v162/akbari22a/akbari22a.pdf}, url = {https://proceedings.mlr.press/v162/akbari22a.html}, abstract = {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 prob-em is NP-complete, 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.} }
Endnote
%0 Conference Paper %T Minimum Cost Intervention Design for Causal Effect Identification %A Sina Akbari %A Jalal Etesami %A Negar Kiyavash %B Proceedings of the 39th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2022 %E Kamalika Chaudhuri %E Stefanie Jegelka %E Le Song %E Csaba Szepesvari %E Gang Niu %E Sivan Sabato %F pmlr-v162-akbari22a %I PMLR %P 258--289 %U https://proceedings.mlr.press/v162/akbari22a.html %V 162 %X 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 prob-em is NP-complete, 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.
APA
Akbari, S., Etesami, J. & Kiyavash, N.. (2022). Minimum Cost Intervention Design for Causal Effect Identification. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:258-289 Available from https://proceedings.mlr.press/v162/akbari22a.html.

Related Material