Source-linked AI summary
The deterministic information bottleneck
DJ Strouse, David J Schwab
TL;DR
Lossy compression must preserve relevant information while discarding other features. This paper introduces the deterministic information bottleneck, replacing mutual-information compression with entropy-based representation constraints, and finds that it yields hard clustering with comparable IB performance, superior DIB performance, and 2-5x greater computational efficiency in synthetic experiments.
Problem
Lossy compression and clustering require deciding which features are relevant, while the IB measures compression through mutual information rather than representational entropy.
Method
The paper replaces the IB compression measure I(X; T) with H(T) and derives a family of objectives interpolating between the IB and DIB.
Results
The DIB performs nearly identically to the IB under the IB cost, far better under its own cost, and with 2-5x greater computational efficiency in synthetic experiments.
Takeaways & Limitations
The DIB provides a deterministic, hard-clustering alternative to the IB for compression and clustering.
Takeaways & Limitations
The DIB name is imperfect because other deterministic IB limits exist and the method's deterministic solution was a result rather than its goal.
Abstract
from arXiv · showhide
Lossy compression and clustering fundamentally involve a decision about what features are relevant and which are not. The information bottleneck method (IB) by Tishby, Pereira, and Bialek formalized this notion as an information-theoretic optimization problem and proposed an optimal tradeoff between throwing away as many bits as possible, and selectively keeping those that are most important. In the IB, compression is measure my mutual information. Here, we introduce an alternative formulation that replaces mutual information with entropy, which we call the deterministic information bottleneck (DIB), that we argue better captures this notion of compression. As suggested by its name, the solution to the DIB problem turns out to be a deterministic encoder, or hard clustering, as opposed to the stochastic encoder, or soft clustering, that is optimal under the IB. We compare the IB and DIB on synthetic data, showing that the IB and DIB perform similarly in terms of the IB cost function, but that the DIB significantly outperforms the IB in terms of the DIB cost function. We also empirically find that the DIB offers a considerable gain in computational efficiency over the IB, over a range of convergence parameters. Our derivation of the DIB also suggests a method for continuously interpolating between the soft clustering of the IB and the hard clustering of the DIB.
1 Introduction
Lossy compression requires deciding which features to preserve as relevant and which to discard. The information bottleneck formalizes this as trading compression against retaining information useful for predicting a variable of interest.
- Lossy compression preserves features judged essential while discarding others, whether in images, memory, or data clusters.
- Compression can be framed using X as the signal, T as its compressed representation, and Y as the variable of interest.
- A good compression algorithm trades off compressing a signal against selectively retaining bits that help predict another signal.
- The information bottleneck formalized this tradeoff as an information-theoretic optimization problem with an iterative soft-clustering algorithm.
- The proposed deterministic information bottleneck replaces IB compression I(X; T) with H(T), emphasizing representation constraints rather than communication.
2 The original information bottleneck (IB)
The original information bottleneck optimizes a stochastic encoder under a Markov constraint, balancing compression against relevance. Its iterative updates converge to a local optimum and trace a compression–relevance tradeoff as β varies.
- The IB seeks an encoding distribution q(t|x) from p(x,y), subject to the Markov constraint T ↔ X ↔ Y.
- The IB cost function balances compression I(X; T) against relevance through a non-negative parameter β.
- Mutual information measures the reduction in uncertainty about one variable when observing another and does not assume a particular relationship form.
- The formal solution maps x to t when p(y|x) and q(y|t) have small Kullback–Leibler divergence.
- The iterative IB approach provably converges to a local optimum, although not necessarily a global one.
- The encoder family traces compression against relevance as β varies, with small β favoring compression over prediction.
3 The deterministic information bottleneck
The DIB replaces the IB’s mutual-information compression measure with entropy, emphasizing representational cost and yielding deterministic encodings. A generalized α-family makes the problem tractable and connects the IB and DIB as limiting cases.
- Motivation: The DIB measures compression with H(T) rather than I(X; T), emphasizing the representation’s cost instead of communication cost.This choice is motivated by source coding and redundancy reduction, including minimizing H(T) in neuroscience.
- Cost functions: The DIB cost function removes the IB’s relative encouragement of stochasticity and consequently produces a deterministic encoding function.The IB decomposition I(X; T) = H(T) − H(T | X) exposes H(T | X) as the noise entropy associated with stochastic mappings.
- Generalized formulation: Because direct variational calculus does not yield an explicit q(t | x) term for the DIB, the derivation introduces an α-indexed family whose limiting cases include the IB and DIB.The DIB solution is defined as the α → 0 limit of the generalized solution qα(t | x), while the IB is recovered at α = 1.
- Caveat: The paper notes that q_DIB need not equal the exact solution of L_DIB because the solution of a limit need not equal the limit of the solution.This is presented as a subtlety in identifying the limiting encoder with the DIB optimization solution.
- Deterministic solution: As α → 0, q(t | x) collapses to a delta function at the t maximizing log q(t) − βD_KL[p(y | x) | q(y | t)].The resulting deterministic assignment balances reuse of populated clusters against retaining information about Y, with β controlling compression versus prediction.
- Optimization: The DIB is solved iteratively, but unused clusters cannot re-enter later iterations, so the representation cardinality should be chosen conservatively large.The algorithm can be viewed as clamping the IB assignment at every step, rather than clamping only after running IB to convergence.
4 Comparison of IB and DIB
On synthetic joint distributions, IB and DIB solutions can look similar under the IB objective but differ sharply under the DIB objective. DIB also converges faster in the tested settings, although the speedup depends on convergence conditions.
- IB and DIB solutions perform similarly in the IB plane but differ drastically in the DIB plane.
- The IB can increase representation entropy beyond H(X), effectively decompressing data under the DIB measure.This occurs because mutual information can be minimized by mappings that distribute each X uniformly across T, even when H(T) is large.
- At small β, DIB outperforms IB most clearly in the DIB plane; their solutions converge there as β increases.
- Careful IB initialization reduces but does not eliminate DIB’s advantage, while some single-cluster initializations skip lower-I(Y; T) solutions.
- DIB remained approximately 2–5x faster than IB across all tested convergence tolerances.The speedup was generally more pronounced at lower ctol values, while absolute fit times depend on hardware.
5 Related work
DIB differs from earlier hard-clustering approaches by deriving deterministic encoders top-down from a modified compression objective rather than designing a greedy hard-clustering procedure.
- AIB and DIB: AIB is a bottom-up greedy method that repeatedly merges clusters to maximize gains in relevant information.
- AIB and DIB: DIB is derived top-down by replacing the IB compression measure to match source-coding compression, with hard clustering emerging as a result.
- Deterministic encoders: Unlike the original IB’s deterministic limit at β →∞, DIB provides a family of deterministic encoders with varying compression levels.
6 Discussion
The DIB is presented as an alternative to the IB that yields non-trivial deterministic clustering, performs strongly on synthetic data, and is computationally more efficient. The discussion identifies real-world validation and naming as important qualifications.
- The DIB provides a non-trivial deterministic version of the IB for compression and clustering.
- On synthetic data, DIB performs nearly identically to IB under the IB cost function but far better under the DIB cost function.
- 2-5x better computational efficiency was observed for DIB than IB in the reported experiments.
- Comparisons on real-world datasets, including hierarchical topic-modeling data, remain important for testing whether DIB advantages hold.
- The paper notes that DIB is an imperfect name because other deterministic IB limits exist and determinism was a result rather than the original goal.
8 Appendix: derivation of generalized IB solution
The appendix derives a generalized IB solution under a Markov constraint by reformulating terms as KL divergences and solving for the encoding distribution. It then specializes the result to the IB and DIB solutions.
- The generalized IB problem is formulated from p(x, y) subject to the Markov constraint T ↔ X ↔ Y.
- A Lagrange multiplier term explicitly enforces normalization of q(t|x).
- The Markov constraint supplies factorizations and corresponding derivatives used to differentiate the cost with respect to the encoding distribution.
- The derivation rewrites the β-dependent terms using KL divergence before solving for q(t|x).
- The resulting generalized solution is specialized into separate IB and DIB solutions.