nucleation

LIT-1172: Nonnegative Decomposition of Multivariate Information

2 min read

Properties8
StatusActive — read in full 2026-10-17 (NOTE-936); worth reading as the source of the partial information decomposition the record already leans on through Williams and Beer (2011), Varley and Hoel, the ΦID review and the Shannon-invariants paper: the redundancy lattice of antichains, the Möbius inversion that turns any redundancy function into nonnegative-by-construction atoms once that function is monotone on the lattice, and the I_min redundancy measure. Read it knowing that the lattice and the inversion are general while every number is I_min's, that I_min credits independent sources with redundancy whenever they reduce surprise about the same outcomes (Harder, Salge and Polani, LIT-1168), and that it is an unrefereed arXiv preprint. Filed as THEORY-706.
Tagsinformation-theory, complex-systems
Extended byLIT-1168 — A Bivariate Measure of Redundant Information, LIT-1176 — Generalized Measures of Information Transfer, LIT-1201 — Measuring multivariate redundant information with pointwise common change in surprisal, LIT-1203 — Intersection Information Based on Common Randomness, LIT-1204 — Quantifying synergistic mutual information
Compared againstLIT-1162 — Quantifying unique information, LIT-1201 — Measuring multivariate redundant information with pointwise common change in surprisal, LIT-1203 — Intersection Information Based on Common Randomness, LIT-1204 — Quantifying synergistic mutual information
RivalsLIT-1162 — Quantifying unique information
Corrected byLIT-1168 — A Bivariate Measure of Redundant Information
Cited as “paper” byNOTE-936 — Williams and Beer — Nonnegative decomposition of multivariate information
Cited as “source” byTHEORY-706 — Any redundancy function defined on the lattice of antichains of sources, ordered so that a collection precedes another when every source of the latter contains one of the former, has a Möbius inverse that decomposes the information a set of sources gives about a target into partial-information atoms summing to every subset's mutual information; for the I_min redundancy, the expected minimum specific information over sources, every atom is nonnegative, and interaction information is a signed mixture of atoms, synergy minus redundancy for three variables

Graph View

Paul L. Williams and Randall D. Beer (2010), “Nonnegative Decomposition of Multivariate Information”, arXiv preprint — ARXIV-1004.2515

Key takeaways

From the reading, NOTE-936.

  • I_min (Eq. 3). Redundancy is the expected minimum, over sources, of the specific information I(S = s; A) = D_KL(p(a|s) ‖ p(a)) about each outcome s. It is nonnegative, at most each source’s mutual information, and equal to it for one source.
  • The lattice (Eqs. 4–5). Collections of sources with no source a superset of another (antichains), ordered by α ≼ β iff every B ∈ β contains some A ∈ α. There are 4 nodes for two sources, 18 for three, 166 for four: the Dedekind numbers.
  • The atoms (Eqs. 6–8). Π is the Möbius inverse of I_min on the lattice. Theorem 5 proves every atom nonnegative for I_min. The inversion itself works for any redundancy function; nonnegativity has to be shown for each.
  • Interaction information (Eqs. 14–15). For three variables it is synergy minus redundancy. For four it is a signed sum of atoms, with one atom counted twice, so pure synergy (3-parity) and pure redundancy (three copies) both score +1 bit.
  • Scope. No estimator, no data, no application. The lattice grows super-exponentially; for nine variables it has more than 5 × 10²² nodes.

Standing in the record

Filed on 2026-10-17 because the record used its decomposition in at least six documents without holding it, and read the same day. Filed as THEORY-706. The lattice and the inversion are what THEORY-712’s two-term split and THEORY-568’s redundancy-free invariants rest on. I_min itself is what THEORY-581’s numbers rest on. Harder, Salge and Polani (LIT-1168) show I_min gives 1 bit of redundancy to two independent bits copied into the target. It carries no instruction for machine-learning practice.

Backlinks