Information bottleneck method

The information bottleneck method is a technique in information theory introduced by Naftali Tishby, Fernando C. Pereira, and William Bialek.^[1] It is designed for finding the best tradeoff between accuracy and complexity (compression) when summarizing (e.g. clustering) a random variable X, given a joint probability distribution p(X,Y) between X and an observed relevant variable Y - and self-described as providing "a surprisingly rich framework for discussing a variety of problems in signal processing and learning".^[1]

Applications include distributional clustering and dimension reduction, and more recently it has been suggested as a theoretical foundation for deep learning. It generalized the classical notion of minimal sufficient statistics from parametric statistics to arbitrary distributions, not necessarily of exponential form. It does so by relaxing the sufficiency condition to capture some fraction of the mutual information with the relevant variable Y.

The information bottleneck can also be viewed as a rate distortion problem, with a distortion function that measures how well Y is predicted from a compressed representation T compared to its direct prediction from X. This interpretation provides a general iterative algorithm for solving the information bottleneck trade-off and calculating the information curve from the distribution p(X,Y).

Let the compressed representation be given by random variable ${\displaystyle T}$. The algorithm minimizes the following functional with respect to conditional distribution ${\displaystyle p(t|x)}$:

${\displaystyle \inf _{p(t|x)}\,\,{\Big (}I(X;T)-\beta I(T;Y){\Big )},}$

where ${\displaystyle I(X;T)}$ and ${\displaystyle I(T;Y)}$ are the mutual information of ${\displaystyle X}$ and ${\displaystyle T}$, and of ${\displaystyle T}$ and ${\displaystyle Y}$, respectively, and ${\displaystyle \beta }$ is a Lagrange multiplier.