PaperlayerView exact revision on arXiv

Source-linked AI summary

Causal Inference on Discrete Data using Additive Noise Models

Jonas Peters, Dominik Janzing, Bernhard Schölkopf

arXiv:0911.0280v1stat.ML

TL;DR

The paper addresses causal-direction inference for discrete variables, where continuous additive-noise methods do not directly apply and standard dependence-based approaches may leave directions indistinguishable. It extends additive noise models to discrete domains, proves generic directional identifiability, and develops an efficient finite-sample inference algorithm. The paper’s theory shows that reversible cases are rare, while the proposed method uses residual independence for regression and is reported to infer relationships between discrete variables.

  • Problem

    Causal discovery from observational joint distributions is difficult for discrete variables, while standard constraint-based methods cannot distinguish some directions and existing additive-noise methods primarily address continuous settings.

  • Method

    The paper defines integer and cyclic discrete additive noise models, prefers a direction with independent additive residuals when the reverse model is absent, and uses an efficient dependence-based regression heuristic.

  • Results

    Reversible additive noise models are very rare for generic choices, and the paper develops an efficient algorithm for inferring causal relationships between two discrete variables from finite data.

  • Takeaways & Limitations

    Generic directional identifiability provides a basis for using discrete additive-noise asymmetry to distinguish cause from effect.

  • Takeaways & Limitations

    The method can be inconclusive when no additive noise model exists in either direction, and its regression function class may exclude the true function because the range is restricted to finite values.

Abstract

from arXiv · show

Inferring the causal structure of a set of random variables from a finite sample of the joint distribution is an important problem in science. Recently, methods using additive noise models have been suggested to approach the case of continuous variables. In many situations, however, the variables of interest are discrete or even have only finitely many states. In this work we extend the notion of additive noise models to these cases. We prove that whenever the joint distribution $\prob^{(X,Y)}$ admits such a model in one direction, e.g. $Y=f(X)+N, N \independent X$, it does not admit the reversed model $X=g(Y)+\tilde N, \tilde N \independent Y$ as long as the model is chosen in a generic way. Based on these deliberations we propose an efficient new algorithm that is able to distinguish between cause and effect for a finite sample of discrete variables. In an extensive experimental study we show that this algorithm works both on synthetic and real data sets.

1 Introduction

The introduction frames causal direction inference as difficult without randomized experiments, especially when standard constraint-based methods cannot distinguish Markov-equivalent directions. It motivates extending additive noise models to discrete variables and using asymmetry between directions for efficient causal inference.

  • Motivation: Constraint-based causal discovery cannot distinguish X →Y from Y →X when both directions impose the same independences.It selects DAGs satisfying the Markov and faithfulness assumptions but leaves Markov-equivalent causal structures indistinguishable.
  • Related work: Prior additive-noise approaches found that generic nonlinear models can be identifiable in one direction, unlike the bivariate Gaussian case.Related work extended linear models to nonlinear functions and obtained generic non-reversibility.
  • Contribution: The paper extends additive noise models to integer-valued, cyclic, and finite categorical variables.The cyclic construction is also proposed for structureless categorical states by imposing an arbitrary cyclic structure.
  • Method: The method prefers the direction admitting an additive noise model when the reverse direction does not, interpreting that asymmetry as the causal direction.This uses Occam’s Razor as the decision principle.
  • Theory: Reversible additive-noise cases are expected to be very rare, supporting identifiability for generic choices of the model.The paper presents rarity of reversibility as the theoretical basis for drawing causal conclusions.
  • Algorithm: An efficient heuristic avoids testing every possible discrete regression function and is reported to work well in practice.The paper evaluates the approach experimentally on synthetic and real data in later sections.

2 Additive Noise Models for Discrete Variables

The paper defines discrete additive noise models over integer and cyclic domains and adopts directional asymmetry as its causal principle. It also specifies when the method declines to infer causality.

  • Causal principle: The causal inference principle identifies X as a cause of Y when Y has an additive noise model with respect to X but not vice versa.The principle is assumed throughout the article for discrete random variables.
  • Scope boundary: If neither direction admits an additive noise model, the method draws no causal conclusion and recommends trying other causal inference methods.This is an explicit scope boundary of the causal principle.
  • Integer model: For integer-valued variables, an additive noise model has the form Y=f(X)+N with N independent of X.The function maps integers to integers, and the noise is integer-valued.
  • Reversibility: A model is reversible when additive noise models exist in both directions.The reverse model uses a function from Y to X and independent reverse noise.
  • Cyclic model: Cyclic additive noise models interpret addition in periodic domains and are intended for variables with an appropriate cyclic structure.Examples include discretized wind direction, day of the year, and season; the cyclic model can also represent unordered categories after imposing a cycle.
  • Model comparison: In finite settings, cyclic constraints are more general than integer constraints because modularizing the noise can preserve independence even when the original noise is dependent.The distinction concerns the target domain and its noise, not whether the regressor is treated as cyclic.

3 Identifiability

The paper characterizes when discrete additive-noise models are reversible and shows that reversibility is confined to highly restricted, generally non-generic distributions. These results support causal-direction inference by preferring the direction with an additive-noise model when the reverse direction is unavailable.

  • Identifiability scope: The intersection of distributions admitting forward and backward additive-noise models is very small; outside it, the method identifies the correct direction with enough data.If the data-generating process lies in the intersection, the method returns “I do not know” rather than a wrong direction.
  • Finite-support variables: For finite-support variables, a forward model can fail to reverse because conditional reverse-noise supports have unequal sizes at different values of Y.The example contrasts a one-point support at Y = 0 with a three-point support at Y = 4, violating reverse-noise independence.
  • Finite-support variables: Reversibility in the finite-support case is characterized by a disjoint decomposition whose component supports, probabilities, and shifted noise supports satisfy restrictive alignment conditions.The characterization includes shifted component sets, shifted and scaled component distributions, and disjoint translated noise supports.
  • Infinite-support variables: For infinite support with compact noise, reversibility has the same decomposition characterization under a condition limiting infinitely large constant regions of f.With noise supported on all integers, reversibility instead imposes parameter dependencies: knowing f, the noise distribution, and sufficiently many tail probabilities determines the remaining probabilities.
  • Non-identifiable cases: Several non-identifiable cases remain, including constant functions, uniform noise, and bijective affine functions with uniform X; these motivate non-uniformity and non-degeneracy assumptions.The paper states a conjecture that, under these exclusions, a non-constant forward model is not reversible, while proving a slightly weaker generic result.
  • Cyclic variables: Under cyclic constraints, divisibility of support sizes is necessary for a backward model, and a backward model introduces at least one additional equality constraint.Specifically, #supp Y must divide #supp X · #supp N; otherwise reversal is impossible.

4 Practical Method for Causal Inference

The method infers the causal direction by comparing additive-noise regressions in both directions and preferring the direction with independent residuals. It uses dependence minimization for discrete regression and an iterative heuristic to make the otherwise intractable search practical.

  • It prefers the direction admitting an additive noise model in only one direction, following Occam’s Razor.
  • The method regresses Y on X and X on Y, then compares whether each direction yields residuals independent of its regressor.It distinguishes causal directions, bad model fits, and cases where both directions remain possible.
  • Because discrete regression need not use regularization but may require searching many functions, the paper proposes an efficient iterative heuristic.It initializes each function value using the most frequent corresponding Y and updates values separately to reduce residual dependence.
  • The regression objective is a dependence measure DM between residuals and the regressor rather than a conventional prediction loss.This directly targets the independence condition required by additive noise models.
  • The heuristic evaluates candidate functions on observed X values and restricts possible outputs to a finite range between the observed minimum and maximum Y.Sparse observations can exclude the true function value, although the resulting few incorrect residuals may have little effect on independence.
  • Independence is tested with Pearson’s χ2 test, using its p-value or test statistic as the dependence measure when the p-value is too small.

5 Experiments

Experiments on synthetic and real data support generic identifiability and show that the algorithm usually recovers the true causal direction. The proposed regression procedure remains efficient where exhaustive function search is infeasible, while near-non-identifiable cases expose a test-level trade-off.

  • Synthetic experiments: The algorithm identifies the true causal direction in almost all simulated data sets, with non-identifiable cases confined to the theoretical counterexamples.For Data Set 1a, residual-dependence mistakes occurred in 4.8% of remaining cases, matching α = 5%.
  • Synthetic experiments: For models close to non-identifiability, the algorithm identifies the correct direction when r ≠ 0, while r = 0 is non-identifiable.At α = 5%, indecisiveness is roughly test-level for |r| ≥ 0.15.
  • Synthetic experiments: Decreasing α reduces indecisive cases but can increase wrongly accepted backward models.This illustrates the trade-off in selecting the independence-test level near non-identifiability.
  • Computational efficiency: 104 ± 33 functions were checked for N1 with i = 9, versus approximately 1.1 · 10^10 total functions and 2.0 · 10^6 empirically supported functions.The proposed method found the true function while avoiding an intractable exhaustive search.
  • Synthetic experiments: The algorithm detects the true direction in almost all unequal-support synthetic cases, except when the model is non-identifiable.This experiment tests whether different support sizes create directional bias.
  • Real data: On the abalone data, the method identified all three sex-to-size directions correctly under integer constraints and rejected the reverse cyclic models.The reported forward p-values were 0.17, 0.19, and 0.05.

6 Conclusions and Future Work

The paper concludes that discrete additive noise models are generically identifiable and can support causal inference from finite data. It also identifies independence testing, broader variable types, and broader empirical validation as open boundaries.

  • Conclusions: The paper proves generic identifiability of the direction of a discrete additive noise model and develops an efficient finite-data causal-inference algorithm.The method targets cause-effect inference between two discrete random variables.
  • Limitations: Because χ2 fails for small data sizes, replacing the independence test may improve algorithm performance.This is presented as a limitation and possible improvement for finite samples.
  • Future work: Extending the method to more than two variables may require regularization, while identifiability for one discrete and one continuous variable remains to be shown.The paper describes both extensions as directions for future work.
  • Future work: More real-world testing and broader principles for causal identification are needed to support or challenge additive noise models as a general causal-inference principle.The authors frame the work as a step toward understanding differences between cause and effect.

A Proof of Theorem 2

The proof characterizes how conditional supports and translated noise supports constrain a reversible discrete additive noise model. It constructs aligned support sets and uses independence to establish the required distributional relationships.

  • Support decomposition: Conditional supports ˜C_i are either equal or disjoint, and f is constant on each support set.These sets are the smallest subsets of supp X carrying probability one conditional on each y_i.
  • Support decomposition: The proof selects disjoint sets C_0, …, C_l on which f is constant and shows that the translated sets c_k + supp N are pairwise different.The values c_k = f(C_k) are pairwise distinct.
  • Reversibility construction: When a backward model also holds, each C_i is a translated version of C_0, namely C_i = C_0 + d_i.The translation is defined through d_i = g(c_i) − g(c_0).
  • Reversibility construction: The constructed reverse noise has a conditional distribution independent of y because membership in C_i is translation-invariant across the relevant support sets.For supported h, the conditional probability is determined by the same joint-probability expression and does not depend on y.

B Proof of Theorem 3

The proof of Theorem 3 assumes simultaneous forward and backward additive noise models and derives increasingly constrained support and probability relations. These relations ultimately contradict the existence of a valid distribution with the required support behavior.

  • Support structure: The proof normalizes the noise supports to nonnegative values with positive mass at zero and uses the compact support of N to show conditional supports C_y are finite shifted copies.The freedom to choose an additive constant is used in this normalization.
  • Support structure: An iterative construction decomposes supp X into support blocks whose extrema shift across conditional distributions.The construction selects successive points ˆx_i and compares maxima and minima of the associated level sets.
  • Support propagation: A finite box of joint-support positions determines subsequent conditional supports under the assumed reversible structure.The argument propagates known positive-support locations to later values of Y.
  • Contradiction: The same probability-scaling relation must hold in the opposite direction, but no infinite-support distribution for X can satisfy it.This contradiction rules out the assumed reversible configuration in the theorem’s setting.
  • Integer-support case: For full integer noise support, comparing joint probabilities across two Y values identifies the shift d and permits iterative recovery of all P(X = x).The sign of d determines which neighboring joint probabilities are used.

C Proof of Theorem 5

The proof analyzes reversibility in three structural cases and shows that reversible additive-noise models require strong distributional constraints. It derives parameter constraints for non-injective cases and uniformity in the bijective case.

  • Case 1: f and g are bijective: In the bijective case, reversibility with bijective f and g implies that both X and Y are uniformly distributed.The proof uses bijectivity of g to construct a predecessor t_y and then shows q(y)=q(t_y) for every y.
  • Case 2: g is not injective: For non-injective g, the proof defines a mapping h on Im(y0−f) and analyzes its cycles to count equality constraints on n.Cyclic and non-cyclic structures impose different numbers of independent constraints.
  • Case 2: g is not injective: If h has only cycles, Imf−#cycles+1 parameters of n are fixed; otherwise Imf−#cycles parameters are fixed.These counts arise from the equality constraints induced by iterating h and the normalization condition.
  • Case 2: g is not injective: At least max(⌈1/2·Imf⌉, 2) parameters of n are fixed in all cases.Thus reversibility is restricted to distributions satisfying multiple parameter constraints.
  • Case 3: f is not injective: If h has only cycles, Im(g−g)−#cycles+1 parameters of p are fixed; otherwise Im(g−g)−#cycles parameters are fixed.If x1−x0 does not divide m, there are no cycles and Im(g−g) parameters of p are determined.
  • Case 3: f is not injective: At least max(⌈1/2·Im(g−g)⌉, 2) parameters of p are fixed in all cases.The proof also notes that the three cases suffice because injective f and g imply equal state-space sizes and bijectivity.
Loading 0911.0280v1…