Motivated by applications to unsupervised learning, we consider the problem of measuring mutual information. Recent analysis has shown that naive kNN estimators of mutual information have serious statistical limitations motivating more refined methods. In this paper we prove that serious statistical limitations are inherent to any measurement method. More specifically, we show that any distribution-free high-confidence lower bound on mutual information cannot be larger than $O(\ln N)$ where $N$ is the size of the data sample. We also analyze the Donsker-Varadhan lower bound on KL divergence in particular and show that, when simple statistical considerations are taken into account, this bound can never produce a high-confidence value larger than $\ln N$. While large high-confidence lower bounds are impossible, in practice one can use estimators without formal guarantees. We suggest expressing mutual information as a difference of entropies and using cross entropy as an entropy estimator.  We observe that, although cross entropy is only an upper bound on entropy, cross-entropy estimates converge to the true cross entropy at the rate of $1/\sqrt{N}$. Motivated by maximal mutual information (MMI) predictive coding BID11 BID16 BID13 , we consider the problem of measuring mutual information. A classical approach to this problem is based on estimating entropies by computing the average log of the distance to the kth nearest neighbor in a sample BID7 . It has recently been shown that the classical kNN methods have serious statistical limitations and more refined kNN methods have been proposed BID5 . Here we establish serious statistical limitations on any method of estimating mutual information. More specifically, we show that any distribution-free high-confidence lower bound on mutual information cannot be larger than O(ln N ) where N is the size of the data sample.Prior to proving the general case, we consider the particular case of the Donsker-Varadhan lower bound on KL divergence BID3 BID1 . We observe that when simple statistical considerations are taken into account, this bound can never produce a highconfidence value larger than ln N . Similar comments apply to lower bounds based on contrastive estimation. The contrastive estimation lower bound given in BID13 does not establish mutual information of more than ln k where k is number of negative samples used in the contrastive choice.The difficulties arise in cases where the mutual information I(x, y) is large. Since I(x, y) = H(y ) − H(y|x) we are interested in cases where H(y ) is large and H(y|x) is small. For example consider the mutual information between an English sentence and its French translation. Sampling English and French independently will (almost) never yield two sentences where one is a plausible translation of the other. In this case the DV bound is meaningless and contrastive estimation is trivial. In this example we need a language model for estimating H(y) and a translation model for estimating H(y|x). Language models and translation models are both typically trained with crossentropy loss. Cross-entropy loss can be used as an (upper bound) estimate of entropy and we get an estimate of mutual information as a difference of cross-entropy estimates. Note that the upper-bound guarantee for the cross-entropy estimator yields neither an upper bound nor a lower bound guarantee for a difference of entropies. Similar observations apply to measuring the mutual information for pairs of nearby frames of video or pairs of sound waves for utterances of the same sentence.We are motivated by the problem of maximum mutual information predictive coding BID11 BID16 BID13 . One can formally define a version of MMI predictive coding by considering a population distribution on pairs (x, y) where we think of x as past raw sensory signals (images or sound waves) and y as a future sensory signal. We consider the problem of learning stochastic coding functions C x and C y so as to maximize the mutual information I(C x (x), C y (y)) while limiting the entropies H(C x (x)) and H(C y (y)). The intuition is that we want to learn representations C x (x) and C y (y) that preserve "signal" while removing "noise". Here signal is simply defined to be a low entropy representation that preserves mutual information with the future. Forms of MMI predictive coding have been independently introduced in BID11 under the name "information-theoretic cotraining" and in BID13 under the name "contrastive predictive coding". It is also possible to interpret the local version of DIM (DIM(L)) as a variant of MMI predictive coding.A closely related framework is the information bottleneck BID17 . Here one again assumes a population distribution on pairs (x, y). The objective is to learn a stochastic coding function C x so as to maximize I(C x (x), y) while minimizing I(C x (x), x). Here one does not ask for a coding function on y and one does not limit H(C x (x)).Another related framework is INFOMAX BID8 BID2 . Here we consider a population distribution on a single random variable x. The objective is to learn a stochastic coding function C x so as to maximize the mutual information I(x, C x (x)) subject to some constraint or additional objective .As mentioned above, in cases where I(C x (x), C y (y)) is large it seems best to train a model of the marginal distribution of P (C y ) and a model of the conditional distribution P (C y |C x ) where both models are trained with cross-entropy loss. Section 5 gives various high confidence upper bounds on cross-entropy loss for learned models. The main point is that, unlike lower bounds on entropy, high-confidence upper bounds on cross-entropy loss can be guaranteed to be close to the true cross entropy.Out theoretical analyses will assume discrete distributions. However, there is no loss of generality in this assumption. Rigorous treatments of probability (measure theory) treat integrals (either Riemann or Lebesgue) as limits of increasingly fine binnings. A continuous density can always be viewed as a limit of discrete distributions. Although our proofs are given for discrete case, all our formal limitations on the measurement of mutual information apply to continuous case as well. See BID9 for a discussion of continuous information theory. Additional comments on this point are given in section 4. Maximum mutual information (MMI) predictive coding seems well motivated as a method of unsupervised pretraining of representations that maintain semantic signal while dropping uninformative noise. However, the maximization of mutual information is a difficult training objective. We have given theoretical arguments that representing mutual information as a difference of entropies, and estimating those entropies by minimizing cross-entropy loss, is a more statistically justified approach than maximizing a lower bound on mutual information.Unfortunately cross-entropy upper bounds on entropy fail to provide either upper or lower bounds on mutual information -mutual information is a difference of entropies. We cannot rule out the possible existence of superintelligent models, models beyond current expressive power, that dramatically reduce cross-entropy loss. Lower bounds on entropy can be viewed as proofs of the non-existence of superintelligence. We should not surprised that such proofs are infeasible.
We give a theoretical analysis of the measurement and optimization of mutual information.
{"src": "scitldr-AIC_train", "paper_id": "BkedwoC5t7"}