Chernoff bottleneck optimizes compressed hypotheses for accurate decisions
Mutual Information Constrained Chernoff Bottleneck
Information TheoryMachine Learning
Summary
Many systems need to summarize data before making decisions, but the ways they usually do this don’t always minimize mistakes effectively. This paper studies a new way to compress information that directly relates to minimizing error when guessing between two options. The authors developed a method that finds the best compressed summary to keep error rates low while limiting how much information is kept. Tests show their method keeps most of the accuracy even when compressing data a lot, such as in topic detection from text.
What this means in practice
- •For machine learning engineers: Improve compressed representations for classifiers to retain high accuracy with reduced data size.
- •For data compression developers: Design encoders that optimize error rates in binary decision tasks under strict data rate limits.
Tested on one dataset.
Authors
Dier Tang, Guangyue Han
Abstract
The classical information bottleneck (IB) measures the relevance of a representation $U$ of $X$ to a target $Y$ by $I(U;Y)$, which does not directly characterize the error of downstream decisions. For a binary hypothesis $Y$ inferred from many separately encoded observations, the optimal error exponent is the Chernoff information between the two conditional distributions of $U$ given $Y$. We study the mutual information constrained Chernoff bottleneck, which seeks an encoder that maximizes this Chernoff information subject to a rate constraint $I(U;X) \leq R$. We show that its optimal value $C(R)$ increases strictly up to $R = H(V)$, where $V$ merges the symbols of $X$ with equal likelihood ratio, remains at the uncompressed exponent beyond, and, unlike the IB curve, need not be concave. We further show that $k+1$ outputs suffice to attain $C(R)$, where $k$ is the cardinality of $V$. We propose an alternating algorithm that updates the encoder via a generalized Blahut--Arimoto algorithm and the Chernoff parameter $s$ via a nonlinear equation, and prove that its iterates remain feasible, with nondecreasing and convergent Chernoff information. Numerical experiments confirm the theory, and on real topic-detection data from the 20 Newsgroups corpus, compressing each word to only $17\%$ of its entropy retains $90\%$ of the error exponent and nearly the accuracy of the uncompressed classifier.