Active causal structure learning with advice

2023/05/31 by Choo, Davin, Gouleakis, Themis, Bhattacharyya, Arnab · 4 citations
#Artificial Intelligence (cs.AI) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.2305.19588

Abstract

We introduce the problem of active causal structure learning with advice. In the typical well-studied setting, the learning algorithm is given the essential graph for the observational distribution and is asked to recover the underlying causal directed acyclic graph (DAG) G^* while minimizing the number of interventions made. In our setting, we are additionally given side information about G^* as advice, e.g. a DAG G purported to be G^*. We ask whether the learning algorithm can benefit from the advice when it is close to being correct, while still having worst-case guarantees even when the advice is arbitrarily bad. Our work is in the same space as the growing body of research on algorithms with predictions. When the advice is a DAG G, we design an adaptive search algorithm to recover G^* whose intervention cost is at most O(max\1, log ψ\) times the cost for verifying G^*; here, ψ is a distance measure between G and G^* that is upper bounded by the number of variables n, and is exactly 0 when G=G^*. Our approximation factor matches the state-of-the-art for the advice-less setting.

Cited by

• Product distribution learning with imperfect advice
• Linear Causal Discovery with Interventional Constraints
• Optimizing Health Coverage in Ethiopia: A Learning-augmented Approach and Persistent Proportionality Under an Online Budget
• Approximate Proportionality in Online Fair Division

Related

• Active Structure Learning of Causal DAGs via Directed Clique Tree
• Interventional Experiment Design for Causal Structure Learning
• Learning Causal Graphs with Small Interventions
• Structure Learning for Directed Trees
• Adaptivity Complexity for Causal Graph Discovery