Innovation Representation of Stochastic Processes With Application to Causal Inference

Amichai Painsky, Saharon Rosset, Meir FederIEEE Trans. Information Theory 2018 · DOI · arXiv

Introduction

Analyzing real-world stochastic processes is inherently challenging due to serial correlation; the state of a system at time $t$ is typically dependent on its state at $t-1$. To simplify these complexities, researchers seek an "innovation representation." This framework describes a process as a sequence of independent, memoryless inputs (innovations) $Y_k$ that, when passed through a deterministic function, reconstruct the observed process $X_k$. While this is well-understood for linear Gaussian systems via the Gram-Schmidt process, extending it to non-Gaussian or discrete data requires new mathematical tools.

Continuous and Discrete Representations

The approach to finding these representations varies significantly based on the data type:

Continuous Variables

For continuous data, the authors utilize a "Posterior Matching" scheme. By mapping the cumulative distribution function (CDF) of the current state—conditioned on its history—to a uniform distribution, they generate a sequence of independent variables. This method ensures a unique, invertible representation, provided the transformations are monotonically increasing.

Discrete Lossy Case

In scenarios where the output alphabet is restricted, a perfect independent representation may be impossible without information loss. Here, the objective shifts to Mutual Information Maximization. For binary first-order Markov processes, the authors derived a closed-form decision rule to determine the optimal distribution of the innovation process.

The relationship between mutual information $I(X;Y)$ and the innovation distribution parameter $\beta$ in a binary Markov process.

Discrete Lossless Case

When information must be preserved perfectly, the task becomes a Minimum Entropy Coupling problem. This is computationally difficult (NP-hard), leading the authors to propose two primary solutions:

  1. Greedy Algorithm: An iterative approach designed to "squeeze" the distribution into the lowest possible entropy.
  2. Mixed Integer Linear Programming (MILP): An optimization framework used to establish a lower bound on achievable entropy, serving as a benchmark for algorithmic performance.
Visualizing different coupling configurations for discrete variables to minimize entropy while maintaining independence.

Applications in Causal Inference and Resource Design

Causal Inference

A central insight of this work is the link between causality and simplicity. In the framework of entropic causal inference, if $X$ causes $Y$, then $Y$ can be represented as a function of $X$ and some independent noise $E$. The "true" causal direction is identified as the one where this noise $E$ possesses the minimum entropy. This paper provides the rigorous mathematical foundation required to identify that minimum.

The IKEA Problem

The authors also introduce the "IKEA Problem," a resource allocation challenge solved using Mixed Integer Quadratic Programming (MIQP). The goal is to design a single, low-entropy storage unit capable of accommodating multiple different customer distribution types without mixing items, effectively treating physical storage as an innovation representation problem.

Conclusion

This research establishes a comprehensive framework for representing complex stochastic processes through independent innovations. By providing closed-form solutions for binary cases and robust algorithmic bounds for discrete ones, it offers a powerful toolkit for causal discovery and optimal system design. Future work may extend these sequential representations to batch processing, potentially offering new insights into Independent Component Analysis (ICA).

Summary updated

BibTeX
@article{painsky2018innovation,
  author = {Amichai Painsky and Saharon Rosset and Meir Feder},
  title = {{Innovation Representation of Stochastic Processes With Application to Causal Inference}},
  journal = {IEEE Trans. Information Theory},
  year = {2018},
  doi = {10.1109/tit.2019.2927530},
}
Figure