Timezone: »

 
Poster
Minimum Cost Intervention Design for Causal Effect Identification
Sina Akbari · Jalal Etesami · Negar Kiyavash

Tue Jul 19 03:30 PM -- 05:30 PM (PDT) @ Hall E #604
in Poster Session 1 »

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.

Keywords: MISC: Causality

Author Information

Sina Akbari (École Polytechnique Fédérale de Lausanne (EPFL))

Computer science at EPFL, working on causal inference, mainly causal identification and bounds.

Jalal Etesami (EPFL)
Negar Kiyavash (École Polytechnique Fédérale de Lausanne)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors