Information bottleneck method

The information bottleneck method is a technique for finding the best trade-off between accuracy and compression when summarizing (e.g. clustering) a random variable X when given a joint probability distribution between X and an observed variable Y.

The compressed variable is $T\,$ and the algorithm minimises the following quantity

${\underset {p(t|x)}{\min }}\,\,I(X;T)-\beta I(T;Y)$

where $I(X;T)\,\,I(T;Y)$ are the mutual informations between $X,T\,$ and $T;Y\,$ respectively.

Gaussian Information Bottleneck [1]

A relatively simple application of the information bottleneck is to Gaussian variates and this has some semblance to a least squares reduced rank or canonical approximation. Assume $X,Y\,$ are jointly multivariate zero mean normal vectors and $T\,$ is a compressed version of $X\,$ which must maintain a given value of mutual information with $Y\,$. It can be shown that the optimum $T\,$ is a normal vector consisting of orthogonal linear combinations of the elements of $X:T=AX\,$.

The projection matrix $A\,$ contains $M\,$ rows selected from the weighted left eigenvectors of the singular value decomposition of the following matrix (generally asymmetric)

$\Omega =\Sigma _{X|Y}\Sigma _{XX}^{-1}=I-\Sigma _{XY}\Sigma _{YY}^{-1}\Sigma _{XY}^{T}\Sigma _{XX}^{-1}$

Define the singular value decomposition

$\Omega =U\Lambda V^{T}\,$ with $\lambda _{1}\leq \lambda _{2}\cdots \lambda _{N}\,$

and the critical values

$\beta _{i}^{C}{\underset {\lambda _{i}<1}{=}}(1-\lambda _{i})^{-1}$.

then the number $M\,$ of active eigenvectors in the projection, or order of approximation, is given by

$\beta _{M-1}^{C}<\beta \leq \beta _{M}^{C}$ 

And we finally get

$A=[w_{1}U_{1},\dots ,w_{M}U_{M}]^{T}$

In which the weights are given by

$w_{i}={\sqrt {(\beta (1-\lambda _{i})/\lambda _{i}r_{i}}}$

where $r_{i}=U_{i}^{T}\Sigma _{xx}U_{i}$ .

[1] G. Chechik, A Globerson, N. Tishby and Y. Weiss: “ Information Bottleneck for Gaussian Variables”. Journal of Machine Learning Research 6, Jan 2005, pp. 165-188

See also

• Information theory

External links

• Paper by N. Tishby, et. al