Compression-Based Information Decomposition for Continuous Data

When a prediction depends on several inputs, such as two sensors, two image regions, or two groups of neurons, we often want to know how the information is split among them. Some information is available from either input alone (redundancy). Some is available from only one input (unique information). Some appears only when the inputs are seen together, as in XOR (synergy). Partial information decomposition (PID) is the formal tool for this split. On real continuous data it breaks down in three places. Its estimators degrade as dimension grows. Mutual information becomes infinite for deterministic networks, so activations must be crudely quantized to 2 or 3 bits. Its continuous estimators can return negative "misinformation."

We propose to replace the Shannon quantities inside PID with the code lengths of a 1-nearest-neighbor compression code. A 1-nearest-neighbor classifier labels a new point by copying the label of the closest stored point. The question we ask of each input is: how many bits does it take to transmit the labels if the receiver already sees this input and decodes by nearest neighbor? Kolmogorov complexity is the length of the shortest program that outputs an object. It is the ideal version of this question, but it is uncomputable. Nearest-neighbor sample compression is a computable stand-in, and its size and running time are provably governed by the doubling dimension of the data. The doubling dimension is a measure of intrinsic geometric size: how many half-radius balls are needed to cover any ball. It does not depend on the ambient number of coordinates. The result is an information decomposition that stays finite on deterministic data, whose cost scales with intrinsic rather than ambient dimension, and whose synergy term has a concrete geometric meaning.

Core Claim

Define $L(S)$ as the shortest two-part code for the training labels $Y$ when the receiver sees only the source subset $S$ and decodes with 1-nearest-neighbor under that source's metric. The code first sends a condensed prototype set and its labels. It then sends the indices of the remaining points that the prototypes misclassify. The minimum is taken over the scale $\gamma$ of the net used to pick prototypes:

$$L(S) = \min_{\gamma}\Big[\, |P_\gamma(S)|\,(\log_2 n + \log_2 |\mathcal{Y}|) \;+\; \log_2 \tbinom{n}{e_\gamma(S)} \,\Big],$$

Here $n$ is the sample size, $P_\gamma(S)$ is a $\gamma$-net (a set of points at least $\gamma$ apart that covers everything within $\gamma$) chosen under the metric of $S$, and $e_\gamma(S)$ is the number of points it misclassifies. The information $S$ carries about $Y$ is its compression gain $G(S) = L(\varnothing) - L(S)$, where $L(\varnothing)$ is the cost of sending the labels with no side information.

The new ingredient is an operational redundancy. Let $L_\cap$ be the length of the shortest prototype code that decodes correctly both for a receiver who sees only $X_1$ and for one who sees only $X_2$. Define $R = L(\varnothing) - L_\cap$. Because one code must serve both receivers, $R \le \min(G_1, G_2)$. The bound is tight only when the same prototypes carry the label structure under both metrics. Requiring the two receivers to share prototypes is what separates this from the minimum-mutual-information shortcut.

The remaining atoms then follow from the usual PID bookkeeping:

$$U_1 = G(X_1) - R,\quad U_2 = G(X_2) - R,\quad \mathrm{Syn} = G(X_1,X_2) - G(X_1) - G(X_2) + R.$$

All quantities are finite for deterministic data. Each prototype set has size at most $(1/\gamma)^{\mathrm{ddim}+1}$ and can be built in time $2^{O(\mathrm{ddim})} n \log(1/\gamma)$ (Near-optimal sample compression for nearest neighbors). We therefore expect estimation error and cost to track the doubling dimension of each source, not its ambient dimension.

We are explicit about what this is and is not. It is algorithmic information relative to the nearest-neighbor code class, in the minimum description length (MDL) sense. It is not true Kolmogorov information. Differences of computable upper bounds on Kolmogorov complexity carry no guarantee in general (Hutter on why ideal induction is not executable). The claim is empirical and comparative: this class-relative decomposition recovers known ground-truth atoms, and it is better behaved than current continuous PID estimators.

Relation to Prior Work

Work that supplies the method. Gottlieb, Kontorovich and Nisnevitch build $\gamma$-net condensing for 1-nearest-neighbor with size and time bounds in the doubling dimension. They treat compression as a single-source Occam bound on generalization. We instead compare compression across source subsets. The same group's Non-uniform packings extends packing bounds to points with individual radii. We use it to bound the size of shared prototype sets, where a point may need different separation under the two metrics.

Work that motivates the gap. Two papers show that current PID estimation is the bottleneck.

  • Ehrlich et al.'s continuous PID defines redundancy through "shared exclusions" and estimates it with a k-nearest-neighbor estimator. It can produce negative unique information, and it names scaling as an open problem. Our atoms are also built from nearest-neighbor geometry, but they are code lengths, not density ratios.
  • Ehrlich et al.'s Representational Complexity measures how many neurons are needed, on average, to decode task information. It must quantize activations to 2–3 bits and coarse-grain neurons. It reports that complexity falls from about 2.5 to 1.2–1.5 during training, and that local intrinsic dimension does not track this trend. We test whether our measure recovers that trend without quantization.

Work that frames simplicity. Valle Pérez et al. use Lempel-Ziv complexity as the Kolmogorov proxy for a whole learned function. Bridging Kolmogorov Complexity and Deep Learning optimizes a variational description length over weights. Neither decomposes complexity across input sources.

Work that constrains the geometric claim. Li & Long show that sample complexity depends on the doubling dimension of the hypothesis class, but only in the realizable setting. Our exception term is a crude agnostic extension, and we do not claim a theorem for it.

Research Program

Theory. The first theoretical task is to prove sanity properties of the decomposition:

  • $R$ is symmetric.
  • $R \le \min(G_1, G_2)$.
  • Copying a source makes $R = G_1$.
  • An independent extra source leaves the atoms unchanged up to code-length slack.
  • On XOR-type targets the marginal gains are near zero while the joint gain is large, so synergy dominates.

The second task is the geometric statement. If each source has doubling dimension $d_i$ and the target has margin $\gamma$, every atom can be computed in time $2^{O(\max d_i)} n \log(1/\gamma)$. Its finite-sample fluctuation is then controlled by $d_i$, independent of the ambient dimension. Synergy has a concrete reading here: the joint metric admits a large margin, but the marginal metrics admit essentially none.

Software. We will build an estimator that runs on two or three source groups. We will not attempt the full multivariate lattice; whole modalities or neuron groups serve as sources. We will release it alongside the analytic test cases.

Baselines

Naive reference point. Plain Shannon mutual information estimated with k-nearest-neighbor methods on each source and on the joint, combined into interaction information (joint minus marginals). This is the cheapest summary a practitioner would compute. It cannot report redundancy and synergy separately, because it gives only their difference. We count our method as better if it identifies cases where this difference is near zero but both redundancy and synergy are large. A mixed XOR-plus-copy system is the test case.

Strongest existing continuous decomposition. The shared-exclusion k-nearest-neighbor PID estimator of Ehrlich et al.. It is the only continuous, assumption-light competitor in the file. It will be run on identical samples. Its neighbor count will be tuned over the same grid size as our $\gamma$ grid, with the same random seeds. Lacuna has no reported result for the estimation accuracy of this estimator on any benchmark, so the comparison is made on our own ground-truth systems.

Strongest existing measure for neural representations. Quantized discrete PID and Representational Complexity from Ehrlich et al.. Its reported figure is $C$ falling from about 2.5 to 1.2–1.5 on MNIST and CIFAR-10. It will be rerun at the same 2- and 3-bit quantization on the same networks and checkpoints. Beating it means matching its monotone trend across layers and epochs, and its shuffled-label train/test gap, without quantization. It also means agreeing better with ground truth where we plant known redundant and synergistic units.

Ablation of the key ingredient. We replace the shared-prototype redundancy $R$ with $\min(G_1, G_2)$, an MDL analogue of minimum-mutual-information redundancy. If this ablation matches the full method everywhere, the shared-code idea adds nothing.

Compressor ablation. We replace the nearest-neighbor code with Lempel-Ziv compression of labels ordered along each source. This is the proxy used by Valle Pérez et al.. It tests whether the metric structure of the code matters.

Why not just…?

Why not just compare the accuracy of classifiers trained on each source and on both? This is the most serious threat. Our measure is itself built from a classifier, a code-counted 1-nearest-neighbor. Accuracy differences ignore model size, so a flexible network can memorize from either source and report redundancy that is not there. Our code charges for every stored prototype, and in the shuffled-label experiments of Ehrlich et al. memorization is exactly what separates train from test. We will run the accuracy-difference baseline using gradient-boosted trees and small networks on every synthetic system. If it recovers the ground-truth atoms equally well, including under label noise and small $n$, we will report that the code-length accounting is unnecessary.

Why not just quantize and use discrete PID? Quantization is what current neural-representation work does. Its results depend on the bit width, and coarse-graining only gives a lower bound on complexity. We will report how the quantized atoms shift between 2 and 3 bits, and compare that shift with the stability of our estimates across $\gamma$.

Why not just use local intrinsic dimension or random projection first? Ehrlich et al. already found that local intrinsic dimension fails to track representational simplification. Projection reduces dimension but does not split information among sources. We use doubling dimension only to explain and bound cost, not as the measure itself.

Proposed Experiments

Synthetic ground truth. Targets are copy, unique, AND, XOR and k-bit parity built from noisy continuous inputs. Each source is embedded into ambient dimension $D$ from 2 to 1000 by random nonlinear maps that fix its doubling dimension. We also use the affine systems with Cauchy and Poisson noise, which have closed-form PID (Analytically deriving PID for affine systems).

  • Metric: absolute error of each atom against ground truth, plotted against $n$ and $D$.
  • Decisive check: our error should stay flat in $D$ at fixed intrinsic dimension, while the shared-exclusion estimator degrades. If our error also grows with $D$, the geometric claim fails.

Synergy and sample complexity. At matched joint doubling dimension, we vary the synergy fraction of the target. We then measure the number of samples a 1-nearest-neighbor learner and a small network need to reach a fixed test error. This tests the prediction of Gap 5: synergy, not global dimension alone, sets sample cost.

Real tabular data. We use the Covertype and Skin Segmentation splits from Gottlieb et al., where condensing reached 3.4% and 4.78% of the original sample size. Features are split into two groups. We then plant redundancy by duplicating a noisy copy of one group, and check that $R$ rises by the planted amount while synergy stays put.

Neural representations. We use multilayer networks on MNIST and CIFAR-10, with pairs of neuron groups as sources. We track layer-wise and epoch-wise atoms and the shuffled-label train/test gap against quantized Representational Complexity.

Multimodal pilot. On MM-Fi features, we test whether a helper modality's unique atom predicts the accuracy loss when that modality is dropped. CST reports that transmitting no more than 14.18% of helper features suffices. A large measured unique-plus-synergy share for a helper would contradict that figure, which gives an external consistency check.