- Information bottleneck method
The information bottleneck method is a technique introduced by Tishby et al  for finding the best tradeoff between
accuracyand complexity (compression) when summarizing (e.g. clustering) a random variableX, given a joint probability distributionbetween X and an observed relevant variable Y. Other applications include distributional clustering, and dimension reduction. In a well defined sense it generalized the classical notion of minimal sufficient statisticsfrom 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 compressed variable is and the algorithm minimises the following quantity
where are the mutual informations between and respectively.
= Gaussian Information Bottleneck  =
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 correlation. Assume are jointly multivariate zero mean normal vectors with covariances and is a compressed version of which must maintain a given value of mutual information with . It can be shown that the optimum is a normal vector consisting of linear combinations of the elements of where matrix has orthogonal rows. The projection matrix in fact contains rows selected from the weighted left eigenvectors of the singular value decomposition of the following matrix (generally asymmetric)
Define the singular value decomposition
and the critical values
then the number of active eigenvectors in the projection, or order of approximation, is given by
And we finally get
In which the weights are given by
= Data Clustering using the Information Bottleneck =
This application of the bottleneck method to non-Gaussian sampled data is described in  by Tishby et. el. The concept, as treated there, is not without complication as there are two independent phases 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.
Since the bottleneck method is framed in probabilistic rather than statistical terms, we first need to estimate the underlying probability density at the sample points . This is a well known problem with a number of solutions described by Silverman in  . In the present method, joint probabilities of the samples are found by use of a Markov transition matrix method and this has some mathematical synergy with the bottleneck method itself.
Define an arbitrarily increasing distance metric between all sample pairs and
distance matrix. Then compute transition probabilities between sample pairs for some . Treating samples as states, and a normalised version of as a Markov state transition probability matrix, the vector of probabilities of the ‘states’ after steps, conditioned on the initial state , is . We are here interested only in the equilibrium probability vector given, in the usual way, by the dominant eigenvector of matrix which is independent of the initialising vector . 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 are discussed in  .
In the following soft clustering example, the reference vector contains sample categories and the joint probability is assumed known. A soft cluster is defined by its probability distribution over the data samples . In  Tishby et al present 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 application of Gibbs Distributions in deterministic annealing  .
The function of each line of the iteration is expanded as follows.
Line 1: This is a matrix valued set of conditional probabilities
The Kullback Leibler distance between the vectors generated by the sample data and those generated by its reduced information proxy is applied to assess the fidelity of the compressed vector with respect to the reference (or categorical) data in accordance with the fundamental bottleneck equation. is the Kullback Leibler distance between distributions
and 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 Liebler distance is large, thus successful clusters grow in probability while unsuccessful ones decay.
Line 2: This is a second matrix-valued set of conditional probabilities
The steps in deriving this are as follows. We have, by definition
where the Bayes identities are used.
Line 3: this line finds the marginal distribution of the clusters
This is also a standard result.
Further inputs to the algorithm are the marginal sample distribution which has already been determined by the dominant eigenvector of and the matrix valued Kullback Leibler distance function
derived from the sample spacings and transition probabilities.
The matrix can be initialised randomly or as a reasonable guess, while matrix needs no prior values. Although the algorithm is converging, multiple minima may exist which need some action to resolve. Further details, including hard clustering methods, are found in  .
Defining Decision Contours
To categorize a new sample external to the training set , apply the previous distance metric to find the transition probabilities between and all samples in , with a normalisation. Secondly apply the last two lines of the 3-line algorithm to get cluster, and conditional category probabilities.
Finally we have
Parameter 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.
The following case examines clustering in a four quadrant multiplier with random inputs and two categories of output, , generated by . This function has the property that there are two spatially separated clusters for each category and so it demonstrates that the method can handle such distributions.
20 samples are taken, uniformly distributed on the square . 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 .
The distance function is where while the conditional distribution is a 2x20 matrix
and zero elsewhere.
The summation in line 2 is only incorporates two values representing the training values of +1 or -1 but nevertheless seems to work quite well. Five iterations of the equations were used. 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 is scanned over the square. Theoretically the contour should align with the and coordinates but for such small sample numbers they have instead followed the spurious clusterings of the sample points.
Neural Network/Fuzzy Logic Analogies
There is some analogy between this algorithm and a neural network with a single hidden layer. The internal nodes are represented by the clusters and the first and second layers of network weights are the conditional probabilities and respectively. However, unlike a standard neural network, the present 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 (or "influence functions/radial basis functions") and transition probabilities instead of sigmoid functions.The Blahut-Arimoto three-line algorithm is seen to converge rapidly, often in tens of iterations, and by varying , and and the cardinality of the clusters, various levels of focus on data features can be achieved.
The statistical soft clustering definition has some overlap with the verbal fuzzy membership concept of fuzzy logic.
 N. Tishby, F.C. Pereira, and W. Bialek: [http://www.cs.huji.ac.il/labs/learning/Papers/allerton.pdf “The Information Bottleneck method”. The 37th annual Allerton Conference on Communication, Control, and Computing, Sep 1999: pp. 368-377]
 G. Chechik, A Globerson, N. Tishby and Y. Weiss: [http://www.jmlr.org/papers/volume6/chechik05a/chechik05a.pdf “Information Bottleneck for Gaussian Variables”. Journal of Machine Learning Research 6, Jan 2005, pp. 165-188]
 N Tishby, N Slonim: “Data clustering by Markovian Relaxation and the Information Bottleneck Method”, Neural Information Processing Systems (NIPS) 2000, pp. 640-646
 B.W. Silverman: “Density Estimation for Statistical Data Analysis”, Chapman and Hall, 1986.
 N. Slonim, N. Tishby: "Document Clustering using Word Clusters via the Information Bottleneck Method", SIGIR 2000, pp. 208-215
 Y. Weiss: "Segmentation using eigenvectors: a unifying view", Proceedings IEEE International Conference on Computer Vision 1999, pp. 975-982
 D. J. Miller, A. V. Rao, K. Rose, A. Gersho: "An Information-theoretic Learning Algorithm for Neural Network Classification". NIPS 1995: pp. 591-597
 P. Harremoes and N. Tishby [http://www.cs.huji.ac.il/labs/learning/Papers/flaske2.pdf "The Information Bottleneck Revisited or How to Choose a Good Distortion Measure". In proceedings of the International Symposium on Information Theory (ISIT) 2007]
* [http://citeseer.ist.psu.edu/tishby99information.html Paper by N. Tishby, et. al]
Wikimedia Foundation. 2010.
Look at other dictionaries:
List of information theory topics — This is a list of information theory topics, by Wikipedia page.*A Mathematical Theory of Communication *algorithmic information theory *arithmetic encoding *channel capacity *Communication Theory of Secrecy Systems *conditional entropy… … Wikipedia
Computers and Information Systems — ▪ 2009 Introduction Smartphone: The New Computer. The market for the smartphone in reality a handheld computer for Web browsing, e mail, music, and video that was integrated with a cellular telephone continued to grow in 2008. According to… … Universalium
List of statistics topics — Please add any Wikipedia articles related to statistics that are not already on this list.The Related changes link in the margin of this page (below search) leads to a list of the most recent changes to the articles listed below. To see the most… … Wikipedia
List of mathematics articles (I) — NOTOC Ia IA automorphism ICER Icosagon Icosahedral 120 cell Icosahedral prism Icosahedral symmetry Icosahedron Icosian Calculus Icosian game Icosidodecadodecahedron Icosidodecahedron Icositetrachoric honeycomb Icositruncated dodecadodecahedron… … Wikipedia
List of mathematics-based methods — This is a list of mathematics based methods, by Wikipedia page.See also list of graphical methods.*Adams method (differential equations) *Akra Bazzi method (asymptotic analysis) *Condorcet method (voting systems) *Coombs method (voting systems)… … Wikipedia
Word-sense disambiguation — Disambiguation redirects here. For other uses, see Disambiguation (disambiguation). In computational linguistics, word sense disambiguation (WSD) is an open problem of natural language processing, which governs the process of identifying which… … Wikipedia
Augmentative and alternative communication — An AAC user indicates a series of numbers on an eye gaze communication board in order to convey a word. Augmentative an … Wikipedia
computer — computerlike, adj. /keuhm pyooh teuhr/, n. 1. Also called processor. an electronic device designed to accept data, perform prescribed mathematical and logical operations at high speed, and display the results of these operations. Cf. analog… … Universalium
Travelling salesman problem — The travelling salesman problem (TSP) is an NP hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find a shortest… … Wikipedia
Mathematics and Physical Sciences — ▪ 2003 Introduction Mathematics Mathematics in 2002 was marked by two discoveries in number theory. The first may have practical implications; the second satisfied a 150 year old curiosity. Computer scientist Manindra Agrawal of the… … Universalium