Source-linked AI summary
Two Optimal Strategies for Active Learning of Causal Models from Interventional Data
Alain Hauser, Peter Bühlmann
TL;DR
Observational data alone leaves causal DAGs identifiable only up to Markov equivalence, and intervention targets affect how much identifiability improves. The paper proposes two target-selection strategies and proves a minimum-target guarantee; simulations compare them with random and existing approaches under oracle and finite-sample settings.
Problem
Observational data alone generally identifies a causal DAG only up to Markov equivalence, leaving arrow directions unresolved without additional model assumptions.
Source: §1 · p. 1Method
The paper proposes OptSingle to maximize orientable edges with single-vertex interventions and OptUnb to find arbitrary-size targets that reduce the clique number of unoriented edges.
Source: §4 · p. 6, §4.1 · p. 6, §4.2 · p. 8Results
In the oracle case, both algorithms reached full identifiability significantly faster than random interventions, while OptUnb used slightly more total intervened variables than random; with reasonably large samples, the approach outperformed He and Geng (2008).
Source: §6 · pp. 12–13Takeaways & Limitations
Iteratively applying OptUnb yields a minimum set of intervention targets that guarantees full identifiability and proves Eberhardt’s (2008) conjecture about the sufficient and worst-case necessary number of interventions.
Source: §6 · p. 12OptUnb does not generally produce an intervention target of minimal size, and the described heuristic improvements do not guarantee one.
Source: §4.3 · p. 9
Abstract
from arXiv · showhide
From observational data alone, a causal DAG is only identifiable up to Markov equivalence. Interventional data generally improves identifiability; however, the gain of an intervention strongly depends on the intervention target, that is, the intervened variables. We present active learning (that is, optimal experimental design) strategies calculating optimal interventions for two different learning goals. The first one is a greedy approach using single-vertex interventions that maximizes the number of edges that can be oriented after each intervention. The second one yields in polynomial time a minimum set of targets of arbitrary size that guarantees full identifiability. This second approach proves a conjecture of Eberhardt (2008) indicating the number of unbounded intervention targets which is sufficient and in the worst case necessary for full identifiability. In a simulation study, we compare our two active learning approaches to random interventions and an existing approach, and analyze the influence of estimation errors on the overall performance of active learning.
1 Introduction
Observational data generally leaves causal arrow directions unresolved, while interventions can improve identifiability. The paper develops and proves active-learning strategies for choosing interventions, then evaluates them in simulations with and without estimation errors.
1 Introduction
- Observational data alone generally identifies a causal DAG only up to Markov equivalence, leaving arrow directions unresolved without additional model assumptions.Interventions perturb variables by forcing them to values irrespective of their original causal parents.Source: §1 · p. 1
- The paper extends earlier algorithms with correctness proofs and simulation comparisons, including analyses with and without estimation errors.Its comparisons include competing methods and examine whether separating observational-class estimation from orientation decisions affects errors.Source: §1 · pp. 1–2
- The strategies target sequential improvement of identifiability, unlike classical active learning that sequentially optimizes estimation accuracy.The paper considers both single-vertex interventions and unbounded-size targets for full identifiability.Source: §1 · p. 2
2 Model
The paper represents causal models with DAGs and formalizes how intervention targets change the data-generating graph and the remaining equivalence class. It then specifies two greedy strategies for choosing interventions.
2 Model
- A causal model pairs a DAG on p variables with an observational density that factorizes according to each variable’s parent set.The DAG encodes the Markov property of the density.Source: §2 · p. 2
2.1 Causal Calculus
- An intervention target identifies variables forced to independent random values, and the corresponding intervention graph removes arrows pointing into those variables.A family of targets records the distinct interventions used; each vertex must be left unintervened in at least one target.Source: §2.1 · p. 2
- I-essential graphs represent intervention-specific Markov equivalence classes: directed edges are invariant across the class, while undirected edges can differ in orientation.The paper assumes each vertex is left unintervened by at least one target, preserving at least the observational level of identifiability.Source: §2.1 · p. 3
2.2 Active Learning
- OptSingle chooses a single vertex to maximize orientable edges, whereas the arbitrary-size-target strategy maximally reduces the largest clique of undirected edges.Efficient implementations optimize these objectives without enumerating all DAGs in the represented equivalence class.Source: §2.2 · p. 4
3 Graph Theoretic Background
The graph-theoretic background supplies the structures and ordering and coloring results used by the intervention algorithms, especially OptUnb.
Graph definitions
- Graphs encode variables as vertices and causal relationships as directed or undirected edges; the skeleton removes arrow directions, while v-structures and parent sets describe local structure.A DAG is directed and acyclic; chain graphs also allow undirected edges but contain no directed cycle.Source: §3 · p. 4
- Chordal graphs have a chord in every cycle of length at least four, and their clique number is the size of their largest clique.For chain graphs, the clique number is the maximum clique number among chain components.Source: §3 · p. 4
Orderings
- Perfect elimination orderings orient chordal chain components into DAG representatives without introducing absent v-structures.LexBFS generates a perfect elimination ordering on a chordal graph in linear time.Source: §3 · p. 5
Coloring
- Greedy coloring along a perfect elimination ordering gives an optimal coloring of a chordal graph, a property used by OptUnb.In general, the chromatic number is bounded below by the clique number and above by maximum degree plus one.Source: §3 · p. 5
4 Optimal Intervention Targets
The algorithms exploit essential-graph structure to select interventions for two distinct objectives: maximizing immediate edge orientation or reducing the clique number. OptUnb gives a sharp sufficient and worst-case-necessary target count, while the methods differ in complexity and target-size guarantees.
4 Optimal Intervention Targets
- I-essential graphs have chordal chain components, allowing optimal intervention searches to focus on individual components.Edge orientations across different chain components do not restrict one another.Source: §4 · p. 6
4.1 Single-vertex Interventions
- For an I-essential graph, OptSingle(G) = ∅ when G has no undirected edge; otherwise, it is a single vertex solving Equation 1, whose maximum is computable without enumerating representative DAGs in D(G).Source: §4.1 · p. 6
4.2 Interventions at Targets of Arbitrary Size
- ⌈log2(ω(G))⌉ intervention targets are sufficient and, in the worst case, necessary for full identifiability.The bound follows because an I-essential graph has one representative DAG exactly when its clique number is 1.Source: §4.2 · p. 7
- OptUnb constructs such targets by coloring chain components and encoding each vertex’s color in binary to separate neighboring vertices.The resulting targets make every edge orientable.Source: §4.2 · p. 8
4.3 Discussion
- OptUnb runs in linear time, whereas OptSingle is polynomial for bounded-degree graphs and worst-case exponential otherwise.The OptSingle complexity depends on the largest clique in the I-essential graph.Source: §4.3 · p. 9
- The algorithms optimize different objectives: OptUnb need not maximize identifiability after each intervention, and OptSingle need not minimize the number of single-vertex interventions to full identification.Source: §4.3 · p. 9
- For one essential graph, some representatives can be fully identified in two OptSingle steps, while the illustrated representative takes three.For the latter, the algorithm proposes vertices 5, 2, and 3.Source: §4.3 · p. 9
- OptUnb does not generally minimize the number of vertices in a target, even when alternative targets have the same effect on edge orientations.In the Figure 4 example, {4, 5} and {2, 5} are alternatives to the selected targets.Source: §4.3 · p. 9
5 Experimental evaluation
The simulations compare active intervention strategies under oracle and finite-sample conditions, measuring how quickly they identify DAGs and how closely estimated graphs match the truth. Optimal strategies improve on random targeting in the oracle case, while finite-sample results depend on estimation accuracy and sample size.
5 Experimental evaluation
- The study evaluated Algorithms 2 and 3 on 4,000 randomly generated Gaussian causal models with p ∈ {10, 20, 30, 40}.For each p, it generated 1,000 DAGs with expected degree 3; sample sizes ranged from 50 to 5,000 per intervention target.Source: §5 · p. 9, §5.1 · p. 10
5.1 Methods and Models
- The oracle setting compared OptSingle and OptUnb with random-target strategies and MaxNb, while the sample setting also tested GIES and He and Geng (2008) using estimated graphs.For the latter approach, observational estimation used PC or GES, followed by intervention-based edge orientation tests.Source: §5.1 · pp. 9–10
- In the sample setting, interventions were added to an estimated observational essential graph, and additional observational data were drawn if estimation produced a fully oriented but incorrect DAG.Source: §5.1 · p. 10
- Performance was assessed by intervention steps to correct reconstruction and by SHD, which counts skeleton false positives, skeleton false negatives, and wrongly oriented edges.Intervention steps were counted as targets or intervened variables, with survival functions estimated using Kaplan-Meier.Source: §5.1 · p. 10
5.2 Results
- In the oracle case, OptUnb needed fewer intervention targets, while OptSingle significantly improved on RandAdv and performed indistinguishably from MaxNb at the 5% significance level.When counting intervened variables rather than targets, OptUnb was slightly worse than RandAdv; OptSingle’s gain over RandAdv was smaller than RandAdv’s gain over Rand.Source: §5.2 · p. 10, Figure 5 · p. 11
- In finite-sample active learning on estimated interventional essential graphs, combining OptSingle or OptUnb with GIES significantly outperformed He and Geng (2008), while performance differences between algorithms shrank.For n = 500 data points per intervention from models with p = 30, He and Geng (2008) was almost indistinguishable from GIES with randomly chosen intervention targets.Source: §5.2 · p. 10
- At n = 5000 per intervention, the oracle-case hierarchy remained visible for GIES through about seven steps, but RandAdv, OptSingle, and OptUnb did not differ significantly at n = 500.Source: §5.2 · p. 12
- For p = 30, SHD results depended strongly on sample size: at n = 50 random targeting matched optimal targeting with GIES, while at n = 5000 OptSingle and OptUnb surpassed random competitors.He and Geng (2008) performed markedly worse at all sample sizes.Source: §5.2 · p. 12, Figure 7 · p. 12
6 Conclusion
The paper presents OptSingle for selecting single-variable interventions and OptUnb for arbitrary-size targets, proving that iterative OptUnb gives a minimum target set for full identifiability. Simulations show faster oracle-case identification than random interventions, but finite-sample performance depends on estimation error and sample size.
6 Conclusion
- OptUnb iteratively yields a minimum set of arbitrary-size intervention targets guaranteeing full identifiability, proving Eberhardt’s (2008) conjecture on the sufficient and worst-case necessary number of interventions.Source: §6 · p. 12
- In the oracle case, both algorithms reached full identifiability significantly faster than random interventions, but OptUnb was slightly worse when counting total intervened variables.The comparison illustrates that sequential single-variable interventions can yield more identifiability than intervening on those variables simultaneously.Source: §6 · p. 12
- When sample size was around the number of variables per intervention, estimation errors dominated limited identifiability.Source: §6 · p. 12
- With reasonably large finite samples, the proposed approach outperformed He and Geng (2008) by using an estimation algorithm operating on observational and interventional data together.Source: §6 · pp. 12–13
A Proofs
The proofs establish the graph criteria used for interventional essential graphs and justify the paper’s single-vertex and full-identifiability strategies. They bound the remaining unoriented edges for a constructed intervention target and show a matching worst-case lower bound.
A Proofs
- An interventional essential graph is characterized by chain-graph structure, chordal chain components, forbidden-configuration exclusions, and strong protection of every directed edge.The characterization includes the absence of an induced a-b-c subgraph and of an undirected edge split by an intervention target.Source: A Proofs · p. 13
- Equivalent DAGs with the same skeleton and v-structures retain the same intervention-DAG skeletons when their orientations incident to the intervened vertex agree.This establishes the skeleton comparison needed for the proof of Lemma 2.Source: A Proofs · p. 14
- OptSingle evaluates each vertex intervention by counting the unoriented edges remaining after orienting its chain component, then selects the vertex with the best score.The proof relates admissible neighbor sets to cliques and constructs an ordering that realizes a maximizing DAG extension.Source: A Proofs · p. 14
- A coloring-based target bounds the unorientable clique size by ⌈ω(G)/2⌉, and a maximum-clique construction establishes this bound as necessary in the worst case.The construction is also used to prove the correctness of Algorithm 3.Source: A Proofs · pp. 14–15