When does the ID algorithm fail?

Ilya ShpitserarXiv 2023 · DOI · arXiv

Abstract

The ID algorithm is a cornerstone of causal inference, providing a sound and complete method for identifying causal effects from observational data. However, the "hedge criterion"—a graphical shorthand for identification failure—contained a subtle logical error. This paper corrects this error, demonstrating that the identifiability of a complex intervention does not necessarily imply the identifiability of its sub-interventions. We present three equivalent characterizations of identification failure based on nested Markov factorizations and the fixing operator.

Introduction

In the world of causal inference, the ID algorithm is a bit of a legend. Developed in the mid-2000s, it provided a "sound and complete" answer to a fundamental question: Given a causal graph and some observational data, can we mathematically identify the effect of an intervention, such as a new drug or a policy change?

If the ID algorithm says "yes," it provides a formula to calculate the effect. If it says "no," it is because the effect is truly unidentifiable due to hidden confounding. However, a popular graphical shorthand for these failures—known as the "hedge criterion"—turned out to be slightly off. In this work, Ilya Shpitser revisits the original framework to provide a necessary correction and a more robust understanding of causal failure.

The Identification Problem

The core challenge in causal inference is identification: moving from a "do-expression" (representing an active intervention) to a "probability expression" (representing observed data). In 2006, Shpitser and Pearl introduced the "hedge" structure—a specific pattern of directed and bidirected edges in a graph—as the definitive signal that an effect is unidentifiable. They originally claimed that if a query contains a hedge for any sub-intervention, the entire query is unidentifiable.

It turns out this is not strictly true. A scenario can exist where a specific intervention is identifiable even if a "simpler" version of that intervention is not. This paper addresses this logical gap, providing counterexamples to the old rule and establishing a new, correct set of criteria.

Methodology: ADMGs and the Fixing Operator

The paper utilizes Graphical Causal Models, specifically Acyclic Directed Mixed Graphs (ADMGs). These graphs use directed arrows for causation and bidirected arrows to represent hidden common causes (latent confounders).

The author relies on the fixing operator ($\phi$), a mathematical tool used to systematically simplify a graph. If one can "fix" (remove) all variables not of interest without encountering structural obstacles, the effect is identifiable. This operator defines:

  • Intrinsic Sets: Sets of variables reachable through a valid sequence of fixing operations.
  • Reachable Closures: The smallest set of variables surrounding a query that is itself fixable.

Correcting the Hedge Criterion

The most striking insight is the refutation of the old "Corollary 3." Shpitser demonstrates a graph where $p(Y | do(a_1, a_2))$ is identifiable, but $p(Y | do(a_2))$ is not. Under the previous rule, the failure of the simpler query should have "poisoned" the more complex one. This paper proves that is not the case.

Causal graphs illustrating various identification scenarios, including hedges and latent confounding.

The paper provides Proposition 1, which lists three equivalent ways to determine if the ID algorithm will fail:

  1. A hedge exists specifically for the query at hand.
  2. A specific component of the graph (a "district") is not intrinsic.
  3. A district is not equal to its own reachable closure.

Results and Implications

The primary result is the formalization of when the ID algorithm fails. While the algorithm itself remains sound and complete, our graphical understanding of its limits is now more precise. The paper concludes that the ID algorithm succeeds if and only if every "district" (a group of variables connected by hidden confounders) in the relevant part of the graph is an intrinsic set. If the algorithm cannot fix a variable because it has both a directed path and a bidirected path to another node, a "hedge" has been identified, and identification is impossible.

Furthermore, the paper links the ID algorithm to the "nested Markov property." This suggests that the formulas produced by the ID algorithm are fundamental pieces of a deeper statistical structure that accounts for hidden variables.

Limitations and Future Work

This theoretical work assumes the causal graph is known a priori. In practice, "causal discovery"—learning the graph from data—remains a significant challenge. Additionally, this work focuses on identification (theoretical possibility) rather than estimation (practical calculation with finite data). Future directions include the "proximal ID algorithm" and other modern extensions that handle complex scenarios involving proxy variables, suggesting that the "fixing" framework remains central to the field's evolution.

Summary updated

Abstract

The ID algorithm solves the problem of identification of interventional distributions of the form p(Y | do(a)) in graphical causal models, and has been formulated in a number of ways [12, 9, 6]. The ID algorithm is sound (outputs the correct functional of the observed data distribution whenever p(Y | do(a)) is identified in the causal model represented by the input graph), and complete (explicitly flags as a failure any input p(Y | do(a)) whenever this distribution is not identified in the causal model represented by the input graph). The reference [9] provides a result, the so called "hedge criterion" (Corollary 3), which aims to give a graphical characterization of situations when the ID algorithm fails to identify its input in terms of a structure in the input graph called the hedge. While the ID algorithm is, indeed, a sound and complete algorithm, and the hedge structure does arise whenever the input distribution is not identified, Corollary 3 presented in [9] is incorrect as stated. In this note, I outline the modern presentation of the ID algorithm, discuss a simple counterexample to Corollary 3, and provide a number of graphical characterizations of the ID algorithm failing to identify its input distribution.
BibTeX
@misc{shpitser2023when,
  author = {Ilya Shpitser},
  title = {{When does the ID algorithm fail?}},
  year = {2023},
  eprint = {2307.03750},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2307.03750},
}
Figure