Loading [MathJax]/jax/output/CommonHTML/jax.js
Skip to yearly menu bar Skip to main content


Poster

Active causal structure learning with advice

Davin Choo · Themis Gouleakis · Arnab Bhattacharyya

Exhibit Hall 1 #329
[ ]
[ PDF [ Poster

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.

Chat is not available.