The information bottleneck method is a technique in information theory introduced by Naftali Tishby, Fernando C. Pereira, and William Bialek. 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".

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).

:

are the mutual information is a Lagrange multiplier.

Learning theory for deep learning

It has been mathematically proven that controlling information bottleneck is one way to control generalization error in deep learning. is the output of a hidden layer. This generalization bound scale with the degree of information bottleneck, unlike the other generalization bounds that scale with the number of parameters, VC dimension, Rademacher complexity, stability or robustness.

Phase transitions

Information theory of deep learning

Theory of Information Bottleneck is recently used to study Deep Neural Networks (DNN). decreases. Saxe et al. in countered the claim of Shwartz-Ziv and Tishby, stating that this compression phenomenon in DNNs is not comprehensive, and it depends on the particular activation function. In particular, they claimed that the compression does not happen with ReLu activation functions. Shwartz-Ziv and Tishby disputed these claims, arguing that Saxe et al. had not observed compression due to weak estimates of the mutual information. On the other hand, recently Goldfeld et al. have argued that the observed compression is a result of geometric, and not of information-theoretic phenomena, a view that has been shared also in.

Variational bottleneck

Gaussian bottleneck

The Gaussian bottleneck, namely, applying the information bottleneck approach to Gaussian variables, leads to solutions related to canonical correlation has orthogonal rows.

rows selected from the weighted left eigenvectors of the singular value decomposition of the matrix (generally asymmetric)

Define the singular value decomposition

and the critical values

of active eigenvectors in the projection, or order of approximation, is given by

And we finally get

In which the weights are given by

Applying the Gaussian information bottleneck to time series (processes), yields solutions related to optimal predictive coding. This procedure is formally equivalent to linear Slow Feature Analysis.

Optimal temporal structures in linear dynamic systems can be revealed in the so-called past-future information bottleneck, an application of the bottleneck method to non-Gaussian sampled data. The concept, as treated by Creutzig, Tishby et al., is not without complication as two independent phases make up in the exercise: firstly estimation of the unknown parent probability densities from which the data samples are drawn and secondly the use of these densities within the information theoretic framework of the bottleneck.

Density estimation

must be estimated. This is a well known problem with multiple solutions described by Silverman. In the present method, joint sample probabilities are found by use of a Markov transition matrix method and this has some mathematical synergy with the bottleneck method itself.

between all sample pairs and distance matrix. The equilibrium probability vector. This Markov transition method establishes a probability at the sample points which is claimed to be proportional to the probabilities' densities there.

are discussed in Silverman's Density Estimation for Statistics and Data Analysis.

Clusters

. Tishby et al. presented the following iterative set of equations to determine the clusters which are ultimately a generalization of the Blahut-Arimoto algorithm, developed in rate distortion theory. The application of this type of algorithm in neural networks appears to originate in entropy arguments arising in the application of Gibbs Distributions in deterministic annealing.

The function of each line of the iteration expands as

Line 1: This is a matrix valued set of conditional probabilities

The Kullback–Leibler divergence

is a scalar normalization. The weighting by the negative exponent of the distance means that prior cluster probabilities are downweighted in line 1 when the Kullback–Leibler divergence is large, thus successful clusters grow in probability while unsuccessful ones decay.

Line 2: Second matrix-valued set of conditional probabilities. By definition

are used.

Line 3: this line finds the marginal distribution

This is a standard result.

and the matrix valued Kullback–Leibler divergence function

derived from the sample spacings and transition probabilities.

needs no prior values. Although the algorithm converges, multiple minima may exist that would need to be resolved.

Defining decision contours

a normalization. Secondly apply the last two lines of the 3-line algorithm to get cluster and conditional category probabilities.

Finally

must be kept under close supervision since, as it is increased from zero, increasing numbers of features, in the category probability space, snap into focus at certain critical thresholds.

An example

. This function has two spatially separated clusters for each category and so demonstrates that the method can handle such distributions.

.

is a 2×20 matrix

and zero elsewhere.

The summation in line 2 incorporates only two values representing the training values of +1 or 1, but nevertheless works well. The figure shows the locations of the twenty samples with '0' representing Y = 1 and 'x' representing Y = 1. The contour at the unity likelihood ratio level is shown,

coordinates but for such small sample numbers they have instead followed the spurious clusterings of the sample points.

Neural network/fuzzy logic analogies

respectively. However, unlike a standard neural network, the algorithm relies entirely on probabilities as inputs rather than the sample values themselves, while internal and output values are all conditional probability (or influence functions/radial basis functions) and transition probabilities instead of sigmoid functions.

and the cardinality of the clusters, various levels of focus on features can be achieved.

has some overlap with the verbal fuzzy membership concept of fuzzy logic.

Extensions

An interesting extension is the case of information bottleneck with side information. Here information is maximized about one target variable and minimized about another, learning a representation that is informative about selected aspects of data. Formally

Bibliography

• P. Harremoës and N. Tishby "The Information Bottleneck Revisited or How to Choose a Good Distortion Measure". In proceedings of the International Symposium on Information Theory (ISIT) 2007

References