Information bottleneck method

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).
Let the compressed representation be given by random variable formula_1. The algorithm minimizes the following functional with respect to conditional distribution formula_2:
where formula_4 and formula_5 are the mutual information of formula_6 and formula_1, and of formula_1 and formula_9, respectively, and formula_10 is a Lagrange multiplier.
Information theory of deep learning.
Theory of Information Bottleneck is recently used to study Deep Neural Networks (DNN).
Consider formula_11 and formula_12 respectively as the input and output layers of a DNN, and let formula_13 be any hidden layer of the network. 
Shwartz-Ziv and Tishby proposed the information bottleneck that expresses the tradeoff between the mutual information measures formula_14 and formula_15. In this case, formula_14 and formula_17 respectively quantify the amount of information that the hidden layer contains about the input and the output.
They conjectured that the training process of a DNN consists of two separate phases; 1) an initial fitting phase in which formula_15 increases, and 2) a subsequent compression phase in which formula_14 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. Recently, Noshad et al. used a rate-optimal estimator of mutual information to explore this controversy, observing that the optimal hash-based estimator reveals the compression phenomenon in a wider range of networks with ReLu and maxpooling activations. 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.
Gaussian bottleneck.
The Gaussian bottleneck, namely, applying the information bottleneck approach to Gaussian variables, leads to solutions related to canonical correlation analysis. Assume formula_20 are jointly multivariate zero mean normal vectors with covariances formula_21 and formula_22 is a compressed version of formula_23 that must maintain a given value of mutual information with formula_24. It can be shown that the optimum formula_22 is a normal vector consisting of linear combinations of the elements of formula_26 where matrix formula_27 has orthogonal rows. 
The projection matrix formula_28 in fact contains formula_29 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
then the number formula_33 of active eigenvectors in the projection, or order of approximation, is given by
And we finally get
In which the weights are given by
where formula_37
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.
Since the bottleneck method is framed in probabilistic rather than statistical terms, the underlying probability density at the sample points formula_38must 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.
The arbitrarily increasing distance metric formula_39 between all sample pairs and distance matrix is formula_40 . Then transition probabilities between sample pairs formula_41 for some formula_42must be computed. Treating samples as states, and a normalised version of formula_43 as a Markov state transition probability matrix, the vector of probabilities of the 'states' after formula_44 steps, conditioned on the initial state formula_45, is formula_46. The equilibrium probability vector formula_47 given, in the usual way, by the dominant eigenvector of matrix formula_43 which is independent of the initialising vector formula_45. This Markov transition method establishes a probability at the sample points which is claimed to be proportional to the probabilities' densities there.
Other interpretations of the use of the eigenvalues of distance matrix formula_50 are discussed in Silverman's "Density Estimation for Statistics and Data Analysis".
Clusters.
In the following soft clustering example, the reference vector formula_51 contains sample categories and the joint probability formula_52 is assumed known. A soft cluster formula_53 is defined by its probability distribution over the data samples formula_54. 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 formula_57 between the formula_51 vectors generated by the sample data formula_59 and those generated by its reduced information proxy formula_60 is applied to assess the fidelity of the compressed vector with respect to the reference (or categorical) data formula_51 in accordance with the fundamental bottleneck equation. formula_62 is the Kullback–Leibler divergence between distributions formula_63
and formula_65 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
where the Bayes identities formula_67 are used.
Line 3: this line finds the marginal distribution of the clusters formula_60
This is a standard result.
Further inputs to the algorithm are the marginal sample distribution formula_70 which has already been determined by the dominant eigenvector of formula_43 and the matrix valued Kullback–Leibler divergence function
derived from the sample spacings and transition probabilities.
The matrix formula_73 can be initialized randomly or with a reasonable guess, while matrix formula_74 needs no prior values. Although the algorithm converges, multiple minima may exist that would need to be resolved.
Defining decision contours.
To categorize a new sample formula_75 external to the training set formula_76, the previous distance metric finds the transition probabilities between formula_75 and all samples in formula_78, formula_79 with formula_80 a normalization. Secondly apply the last two lines of the 3-line algorithm to get cluster and conditional category probabilities.
Finally
Parameter formula_83 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.
The following case examines clustering in a four quadrant multiplier with random inputs formula_84 and two categories of output, formula_85, generated by formula_86. This function has two spatially separated clusters for each category and so demonstrates that the method can handle such distributions.
20 samples are taken, uniformly distributed on the square formula_87 . The number of clusters used beyond the number of categories, two in this case, has little effect on performance and the results are shown for two clusters using parameters formula_88.
The distance function is formula_89 where formula_90 while the conditional distribution formula_91 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,
as a new sample formula_94is scanned over the square. Theoretically the contour should align with the formula_95 and formula_96 coordinates but for such small sample numbers they have instead followed the spurious clusterings of the sample points.
Neural network/fuzzy logic analogies.
This algorithm is somewhat analogous to a neural network with a single hidden layer. The internal nodes are represented by the clusters formula_97 and the first and second layers of network weights are the conditional probabilities formula_98 and formula_99 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 density distributions. Nonlinear functions are encapsulated in distance metric formula_100 (or "influence functions/radial basis functions") and transition probabilities instead of sigmoid functions.
The Blahut-Arimoto three-line algorithm converges rapidly, often in tens of iterations, and by varying formula_83, formula_102 and formula_39 and the cardinality of the clusters, various levels of focus on features can be achieved.
The statistical soft clustering definition formula_74 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