English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the problem of learning the causal relationships between a set ofobserved variables in the presence of latents, while minimizing the cost ofinterventions on the observed variables. We assume access to an undirectedgraph $G$ on the observed variables whose edges represent either all directcausal relationships or, less restrictively, a superset of causal relationships(identified, e.g., via conditional independence tests or a domain expert). Ourgoal is to recover the directions of all causal or ancestral relations in $G$,via a minimum cost set of interventions. It is known that constructing an exactminimum cost intervention set for an arbitrary graph $G$ is NP-hard. We furtherargue that, conditioned on the hardness of approximate graph coloring, nopolynomial time algorithm can achieve an approximation factor better than$\Theta(\log n)$, where $n$ is the number of observed variables in $G$. Toovercome this limitation, we introduce a bi-criteria approximation goal thatlets us recover the directions of all but $\epsilon n^2$ edges in $G$, for somespecified error parameter $\epsilon > 0$. Under this relaxed goal, we givepolynomial time algorithms that achieve intervention cost within a smallconstant factor of the optimal. Our algorithms combine work on efficientintervention design and the design of low-cost separating set systems, withideas from the literature on graph property testing.

Intervention Efficient Algorithms for Approximate Learning of Causal Graphs