Formal Limitations on the Measurement of Mutual Information

INTRODUCTION

Mutual information has important applications to unsupervised learning. It underlies classical representation learning methods such as Brown clustering (Brown et al., 1992), INFOMAX (Bell and Sejnowski, 1995), and the information bottleneck method (Tishby et al., 1999). Maximizing mutual information is also central to recent works on unsupervised representation learning with neural networks (McAllester, 2018; Belghazi et al., 2018; Oord et al., 2018; Stratos, 2019; Hjelm et al., 2019).

Unfortunately, measuring mutual information from finite data is a notoriously difficult estimation problem. This difficulty has motivated researchers to consider more computationally amenable measurement methods that maximize a parameterized lower bound on mutual information. The hope is that the optimized value of the bound is close to the true value of mutual information and can serve as a good enough approximation. For instance, this is the approach advocated by Mutual Information Neural Estimator (MINE) (Belghazi et al., 2018) and contrastive predictive coding (CPC) (Oord et al., 2018).

Here we prove that serious statistical limitations are inherent to all methods of measuring 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 number of samples. Thus a meaningful high-confidence lower bound is infeasible when underlying mutual information is large (e.g., hundreds of bits).

Our result corrects, generalizes, and unifies past work on measuring mutual information. Unlike previous intractability results that are tied to specific estimators (Gao et al., 2015; Oord et al., 2018), our result is universal to all estimators. Hence we show that without making strong assumptions on the population distribution, such as the small support assumption in Valiant and Valiant (2011) and minimax bounds (Jiao et al., 2015), it is generally impossible to guarantee an accurate estimate of mutual information. Our results contradict a theorem in Belghazi et al. (2018) claiming a polynomial sample size convergence rate for a mutual information estimator and we point out an error in their proof.

While it is infeasible to give meaningful high-confidence lower bound guarantees for large mutual information, estimators lacking formal guarantees might still be useful in practice. To this end, we propose expressing mutual information as a difference of entropies and estimating the entropy terms by cross-entropy upper bounds. This difference-of-entropies (DoE) estimator gives neither an upper bound nor a lower bound guarantee on mutual information. Nevertheless, we give theoretical and empirical evidence that DoE can meaningfully estimate large mutual information from feasible samples.

We state our main result below. We write $(X,Y)$ to denote a pair of random variables with ranges $(\mathcal{X},\mathcal{Y})$. Unless otherwise specified, they can be discrete or continuous. For simplicity, all distributions are assumed to have full support.

Let $B$ be any mapping from $N$ samples of $(X,Y)$ to a real number with the following property: for any distribution $p_{XY}$ over $(X,Y)$, given $N$ iid samples $(x_{1},y_{1})\ldots(x_{N},y_{N})\sim p_{XY}$, with probability at least 0.99

where $I(X,Y;p_{XY})$ is the mutual information between $(X,Y)$ under $p_{XY}$. Now pick any distribution $q_{XY}$ over $(X,Y)$. Then given $N\geq 50$ iid samples $(x^{\prime}_{1},y^{\prime}_{1})\ldots(x^{\prime}_{N},y^{\prime}_{N})\sim q_{XY}$, with probability at least 0.96

In the rest of the paper, we build toward this result by proving statistical limitations on measuring lower bounds on Kullback-Leibler (KL) divergence and entropy. We derive several intermediate results, specifically:

We first consider the Donsker-Varadhan lower bound on KL divergence which underlies the approach in MINE. We give an intuitive explanation on why estimating the bound from samples is problematic. We show that the polynomial sample complexity result given by Belghazi et al. (2018) is incorrect.

We formally prove that any lower bound on KL divergence cannot be larger than $O(\ln N)$. This subsumes the Donsker-Varadhan bound as a special case.

We formally prove that any lower bound on entropy cannot be larger than $O(\ln N)$. Theorem 1.1 is a special case of this result.

We motivate measuring mutual information as a difference of entropies, each of which measured by minimizing cross entropy. We empirically show that it outperforms existing variational lower bounds in synthetic experiments and produce realistic estimates of mutual information in real-world datasets.

ISSUES WITH THE DONSKER-VARADHAN LOWER BOUND

The Donsker-Varadhan (DV) lower bound on KL divergence is stated below. For completeness, a simple proof is given in the supplementary material.

The DV bound (2) computes the difference between the expected value of $f(x)$ under $p_{X}$ and the log of the expected value of the exponential of $f(x)$ under $q_{X}$. It can be easily estimated by sampling: given $x_{1}\ldots x_{N}\sim p_{X}$ and $x^{\prime}_{1}\ldots x^{\prime}_{N}\sim q_{X}$, we can compute the empirical estimate

An application of the DV bound is measuring KL divergence. Specifically, we estimate KL divergence by estimating the associated DV bound from samples:

The first inequality holds for all choices of $f$ by Theorem 2.1. We require that the second inequality holds with high probability (with respect to random sampling). We now show that this approach to measuring KL divergence is problematic.

A crucial observation is that the second term in the DV bound (2) involves an expectation of the exponential

This expression has the same form as the moment generating function used in analyzing large deviation probabilities. The utility of expectations of exponentials in large deviation theory is that such expressions can be dominated by extremely rare events (large deviations). The rare events dominating the expectation will never be observed by sampling from $q_{X}$.

To quantitatively analyze the risk of unseen outlier events, we will make use of the following simple lemma where we write $p_{X}(\Phi[x])$ for the probability over drawing $x$ from $p_{X}$ that the statement $\Phi[x]$ holds.

Given $N\geq 2$ samples from $p_{X}$ and a property $\Phi[x]$ such that $p_{X}(\Phi[x])\leq 1/N$, the probability that no sample $x$ satisfies $\Phi[x]$ is at least 1/4.

The probability that $\Phi[x]$ is unseen in the sample is at least $(1-1/N)^{N}$ which is at least $1/4$ for $N\geq 2$ and where $\lim_{N\rightarrow\infty}(1-1/N)^{N}=1/e$. ∎

We can use the outlier risk lemma to perform a quantitative risk analysis of the DV bound. Assume without loss of generality that $[0,F_{\max}]$ is the range of $f$ taken on $\mathcal{X}$. Let us consider the best case scenario in which the empirical estimate (3) is the largest. It is easy to see that the largest value is $F_{\max}$ and attained when

where $x_{1}\ldots x_{N}$ are samples from $p_{X}$ and $x^{\prime}_{1}\ldots x^{\prime}_{N}$ are samples from $q_{X}$. But by the outlier risk lemma, there is still at least a 1/4 probability that

Since we require that (3) is a high-confidence lower bound on the DV bound, it must account for the unseen outlier risk.We intentionally keep this argument informal to give intuition since the result on the DV bound will be subsumed by the general result in Theorem 3.1. In particular, we must have

2 Discussion of MINE

where $(x_{1},y_{1})\ldots(x_{N},y_{N})$ are drawn from $p_{XY}$ and $(x^{\prime}_{1},y^{\prime}_{1})\ldots(x^{\prime}_{N},y^{\prime}_{N})$ are drawn from $p_{X}\times p_{Y}$. This is an empirical estimate of the DV bound on

They claim that (4) yields a high-confidence accurate measurement of underlying mutual information with polynomial sample complexity under mild assumptions (Theorem 3 in their paper), which apparently contradicts our previous observation.

Upon inspection, we have found that their claim is wrong. In the appendix of the arXiv version v4, they make an incorrect application of the Hoeffding inequality in equation (46) from which they incorrectly derive equation (49). Hoeffding depends on the bounded range of the random variable: (49) is bounding the exponential of the variable. Thus their bound stated in Theorem 3 has an exponential dependence on the variable $M$.

STATISTICAL LIMITATIONS ON MEASURING LOWER BOUNDS ON KL DIVERGENCE

More specifically, let $B(p_{X},S,\delta)$ be any real-valued function of a distribution $p_{X}$, a multiset $S$, and a confidence parameter $\delta$ such that, for any $p_{X}$, $q_{X}$ and $\delta$, with probability at least $1-\delta$ over a draw of $S$ from $q_{X}^{N}$ we have

For any such bound, and for $N\geq 2$, for any $q_{X}$, with probability at least $1-4\delta$ over the draw of $S$ from $q_{X}^{N}$ we have

The premise is that $B$ yields a high-confidence lower bound for any distribution. Thus we have

This result has immediate implications on measuring mutual information which is a special case of KL divergence (5). A direct application of Theorem 3.1 gives the following: in the setting in which we have perfect knowledge of $p_{XY}$ but can only sample from $p_{X}$ and $p_{Y}$ (i.e., we cannot compute marginals) and measure a lower bound on $I(X,Y;p_{XY})$ from $N$ samples, we cannot guarantee that the bound is larger than $\ln N$. However, this setting is arguably awkward. In the next section, we make a more natural argument by considering entropy.

STATISTICAL LIMITATIONS ON MEASURING LOWER BOUNDS ON ENTROPY

Recall that mutual information can be formulated as a difference of entropies

where $H(X;p_{X})$ is the entropy of $X$ under $p_{X}$ and $H(X|Y;p_{XY})$ is the conditional entropy of $X$ given $Y$ under $p_{XY}$. Entropy is nonnegative for discrete variables: in this case we have

It states that the mutual information between $X$ and $Y$ cannot be larger than information content of $X$ alone. Thus a lower bound on mutual information implies a lower bound on entropy. We will show that any distribution-free high-confidence lower bound on entropy requires a sample size exponential in the size of the bound.

The above argument seems problematic for the case of continuous densities as differential entropy can be negative. However, for the continuous case we have

where $C$ and $C^{\prime}$ range over all maps from the underlying continuous space to discrete sets (all binnings of the continuous space). A proof is given in the supplementary material. Hence an $O(\ln N)$ upper bound on the measurement of mutual information for the discrete case applies to the continuous case as well. We assume the discrete case in this section without loss of generality.

The type of a multiset $S$, denoted ${\cal T}(S)$, is a function on positive integers such that

That is, ${\cal T}(S)(i)$ is the number of elements of $S$ that occur $i$ times in $S$.

The type ${\cal T}(S)$ contains all information relevant to estimating the actual probability of the items of a given count and of estimating the entropy of the underlying distribution. The problem of estimating distributions and entropies from sample types has been investigated by various authors (McAllester and Schapire, 2000; Orlitsky et al., 2003; Orlitsky and Suresh, 2015; Arora et al., 2018). Here we give the following negative result on lower bounding the entropy of a distribution by sampling.

Let $B$ be any distribution-free high-confidence lower bound on $H(X;p_{X})$ computed from a type ${\cal T}(S)$ with $S\sim p_{X}^{N}$.

More specifically, let $B({\cal T},\delta)$ be any real-valued function of a type ${\cal T}$ and a confidence parameter $\delta$ such that for any $p_{X}$, with probability at least $1-\delta$ over a draw of $S$ from $p_{X}^{N}$, we have

For any such bound, and for $N\geq 50$ and $k\geq 2$, for any $p_{X}$, with probability at least $1-\delta-1.01/k$ over the draw of $S$ from $p_{X}^{N}$ we have

For a type ${\cal T}$ let $\Pr_{S\sim P^{N}}({\cal T})$ denote the probability over drawing $S\sim P^{N}$ that ${\cal T}(S)={\cal T}$. We now have

Using $1-z\geq e^{-1.01z}$ for $z\leq 1/100$ we have the following birthday paradox calculation.

Applying the union bound to (9) and (11) gives

By a derivation similar to that of (11) we get

TOWARD ACCURATE MEASUREMENT OF MUTUAL INFORMATION

Our main contribution is a set of fundamental statistical limitations on measuring a lower bound on mutual information implied by the difficulty of measuring a lower bound on KL divergence (Theorem 3.1) or entropy (Theorem 4.1). But it is natural to ask: then how can we achieve an accurate measurement of mutual information? As a complementary piece of contribution, in this section we explore a new estimator for mutual information that, while lacking formal guarantees, does not suffer from the same limitations.

Since mutual information can be expressed as a difference of entropies (7), the problem of measuring mutual information can be reduced to the problem of measuring entropies. More specifically, we write mutual information as

where we use the fact that the entropy $H(X;p_{X})$ is upper bounded by the cross entropy between $p_{X}$ and $q_{X}$, denoted $H(p_{X},q_{X})$, for all distributions $q_{X}$ (similarly for the conditional entropy $H(X|Y;p_{XY})$). They are equal iff $q_{X}=p_{X}$ and we have

Note that the upper-bound guarantee for the cross-entropy estimator (15) yields neither an upper bound nor a lower bound guarantee for a difference of entropies (14). However, we give theoretical evidence below that, unlike lower bound estimators, upper bound cross-entropy estimators can meaningfully estimate large entropies from feasible samples.

The statistical limitations on distribution-free high-confidence lower bounds on entropy do not arise for cross-entropy upper bounds. For upper bounds we can show that naive sample estimates of the cross-entropy loss produce meaningful (large entropy) results. The empirical cross-entropy loss computed on samples $x_{1}\ldots x_{N}$ from a population distribution $p_{X}$ is

where $q_{X}$ is viewed as a model of $p_{X}$. We can bound the true loss of $q_{X}$ by ensuring a minimum probability $e^{-F_{\max}}$ where $F_{\max}$ is then the maximum possible log loss in the cross-entropy objective.In language modeling a loss bound exists for any model that ultimately backs off to a uniform distribution on characters. Given a loss bound of $F_{\max}$, $\widehat{H}^{N}(p_{X},q_{X})$ is just the standard sample mean estimator of an expectation of a bounded variable. In this case we have the following standard confidence interval derived from the Chernoff bound.

For any population distribution $p_{X}$, and model distribution $q_{X}$ with $-\ln q_{X}(x)$ bounded to the interval $[0,F_{\max}]$, with probability at least $1-\delta$ over the draw of $x_{1}\ldots x_{N}\sim p_{X}$ we have

Thus unlike high-confidence distribution-free lower bounds, high-confidence distribution-free upper bounds on entropy can approach the true cross entropy at the modest sample rate of $1/\sqrt{N}$ even when the true cross entropy is large.It is also possible to give PAC-Bayesian bounds on $H(p_{X},q_{X}^{\theta})$ as functions of the parameters $\theta$ of $q_{X}$. See the supplementary material for details.

2 Experiments

We present experiments with the proposed difference-of-entropies (DoE) estimator to gain a better understanding of its empirical behavior. First, we compare DoE with existing lower-bound estimators in a standard synthetic setting based on correlated Gaussians. Next, we apply DoE on the task of measuring mutual information between related articles and translation pairs and show an evidence of large mutual information.

In the following, DoE computes an empirical estimate of (14) by taking iid samples $(x_{1},y_{1})\ldots(x_{N},y_{N})$ from $p_{XY}$ and computing

where each minimization corresponds to fitting a probabilistic model on the samples with the cross-entropy loss.

Table 1 shows mutual information estimates given by these estimators. All estimators are trained for 3,000 steps where at every step they use $N=128$ samples drawn from $p_{XY}$ to update their weights. We tune the hyperparameters of each estimator (e.g., learning rate, number of hidden units, initialization strategies, estimator-specific hyperparameters such as the mixing weights in NWJ+CPC and MINE) to minimize $\left|I(X,Y)-\hat{m}\right|$ where $\hat{m}$ is the final estimate. Thus the results assume an oracle that gives an optimal configuration. All details can be found in the code: https://github.com/karlstratos/doe.

It is clear that (1) DoE obtains the most accurate estimates whether $I(X,Y)>\ln N$ or $I(X,Y)\leq\ln N$, (2) DoE is the only estimator that achieves accurate estimates when underlying mutual information is large, and (3) either Gaussian or logistic parameterization of DoE yields accurate estimates. Furthermore, Table 1 does not show the fact that DV, MINE, and NWJ are highly unstable (especially in the large mutual information setting). In particular, while it seems that they can achieve estimates much larger than $\ln N$, it is not representative of their general performance which is fraught with numerical overflow/underflow problems leading to completely off estimates. Poole et al. (2019) discuss the large variance of these estimators. In contrast, DoE is based on the standard cross-entropy loss and very stable.

Figure 2 shows a plot of the best training session for each estimator. DoE is a clear outlier as the only accurate estimator of mutual information. Unlike lower-bound estimators, DoE can approach $I(X,Y)$ from above or below.

2.2 Mutual Information Between Articles and Translations

We consider two datasets for the choice of $(X,Y)$:

Related news article pairs extracted from the Who-Did-What dataset (Onishi et al., 2016)

English-German translation pairs extracted from the IWSLT 2014 dataset

We expect that mutual information is large in either setting: a random article (sentence) has large entropy, but given a related article (translation) the uncertainty is drastically reduced. We use a standard LSTM language model for $q_{X}$ and a standard attention-based translation model for $q_{X|Y}$. More details of the experiments can be found in the supplementary material.

Table 2 shows the estimates of mutual information on the test portion of data. We use log base 2 to accommodate the bit interpretation of entropies (rather than nats). We see that mutual information is estimated to be over 120 bits on related article pairs and 54 bits on translation pairs. Mutual information is estimated to be close to zero for shuffled pairs: this shows that the estimator can also handle small mutual information.

RELATED WORK

We make a few additional remarks on related work to better contextualize our work. In the continuous setting, a classical approach to estimating mutual information is based on computing the average log of the distance to the $k$-th nearest neighbor in samples (Kraskov et al., 2004). Gao et al. (2015) show that this estimator suffers exponential sample complexity and propose more refined nearest-neighbor methods (Gao et al., 2015). In contrast, we establish that serious statistical limitations are inherent to the measurement of mutual information no matter what estimator is used.

There is a line of work that develops efficient estimators for entropy by assuming distributions with very small support—distributions with support smaller than the sample size. Valiant and Valiant (2011) show that it is possible to achieve an optimal sample rate of $O(n/\ln n)$ where $n$ is the support size. Past work on analyzing minimax bounds likewise assume small support (Jiao et al., 2015; Han et al., 2015; Kandasamy et al., 2015). In this case, the entropy of the distribution cannot be larger than the log of the number of samples. This is in agreement with, but does not imply, our results. We are interested in the large entropy setting, such as a distribution over all possible images or articles. We cannot have the number of samples equal to the number of possible images or articles.

As discussed in depth in Section 2, we are motivated by the approach in MINE which measures the DV bound to estimate and maximize mutual information (Belghazi et al., 2018). CPC is another notable example that illustrates the statistical limitations of measuring mutual information (Oord et al., 2018). CPC maximizes a lower bound on mutual information through noise contrastive estimation: it is shown that this lower bound cannot be larger than $\ln k$ where $k$ is number of negative samples used in the contrastive choice. Complementary to our work, a recent work by Poole et al. (2019) investigates tradeoffs between bias and variance in estimating variational bounds on mutual information.

There is a class of representation learning methods such as Brown clustering (Brown et al., 1992) and the information bottleneck method (Tishby et al., 1999) that maximize a lower bound on mutual information given by the data processing inequality (DPI). In these methods, we learn “coding” functions $(C,C^{\prime})$ by optimizing the objective

where the inequality is by the DPI. Information theoretic co-training (McAllester, 2018) considers a similar lower bound and has been shown to be useful for label induction in speech and text (Stratos, 2019). Measuring these lower bounds is subject to the same limitations presented in this paper.

CONCLUSIONS

Maximizing mutual information is well motivated as a method of unsupervised pretraining of representations that maintain semantic signal while dropping uninformative noise. However, measuring and maximizing mutual information from finite data is a difficult training objective. In this paper, we have shown serious statistical limitations inherent to measuring lower bounds on various information theoretic measures including KL divergence, entropy, and mutual information. We have also 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.

Appendix A PROOF OF THEOREM 2.1

For any distribution $r_{X}$ over $X$, we can write

which is a valid distribution over $X$. Plugging this into the lower bound in (18), we have

By (18), the supremum of (19) over the choice of $f$ is precisely the KL divergence between $p_{X}$ and $q_{X}$. It can be easily verified that an optimal $f$ is given by

Appendix B MUTUAL INFORMATION AS THE SUPREMUM OVER BINNINGS

where $(I_{\epsilon},J_{\epsilon})$ denote the indices $(i,j)$ such that $x\in C_{i,\epsilon}$ and $y\in C_{j,\epsilon}$ for $(x,y)\sim p_{XY}$.

This proof immediately generalizes to higher dimensions where the mutual information can be expressed as a Riemann integral. We believe that this statement remains true for arbitrary measures on product spaces where the mutual information is finite. However the proof for this extremely general case appears to be nontrivial.

Appendix C PAC-BAYESIAN BOUNDS

The PAC-Bayesian bounds apply to “broad basin” losses and loss estimates such as the following:

Under mild smoothness conditions on $q_{X}^{\theta}(x)$ as a function of $\theta$ we have

An $L_{2}$ PAC-Bayesian generalization bound (McAllester, 2013) gives that for any parameterized class of models and any bounded notion of loss, and any $\lambda>1/2$ and $\sigma>0$, with probability at least $1-\delta$ over the draw of $S$ from $p_{X}^{N}$ we have the following simultaneously for all parameter vectors $\theta$.

It is instructive to set $\lambda=5$ in which case the bound becomes.

While this bound is linear in $1/N$, and tighter in practice than square root bounds, note that there is a small residual gap when holding $\lambda$ fixed at 5 while taking $N\rightarrow\infty$. In practice the regularization parameter $\lambda$ can be tuned on holdout data. One point worth noting is the form of the dependence of the regularization coefficient on $F_{\max}$, $N$ and the basin parameter $\sigma$.

It is also worth noting that the bound can be given in terms of “distance traveled” in parameter space from an initial (random) parameter setting $\theta_{0}$.

Evidence is presented in Dziugaite and Roy (2017) that the distance traveled bounds are tighter in practice than traditional $L_{2}$ generalization bounds.

Appendix D EXPERIMENT DETAILS

We take pairs from the Who-Did-What dataset (Onishi et al., 2016). The pairs in this dataset were constructed by drawing articles from the LDC Gigaword newswire corpus. A first article is drawn at random and then a list of candidate second articles is drawn using the first sentence of the first article as an information retrieval query. A second article is selected from the candidates using criteria described in Onishi et al. (2016), the most significant of which is that the second article must have occurred within a two week time interval of the first. The training statistics of this dataset after preprocessing is given in Table 3.

Our translation pairs consists of English-German sentence pairs extracted from the IWSLT 2014 dataset. The training statistics of this dataset after preprocessing is given in Table 4.

We train an LSTM encoder-decoder model where the decoder doubles as both the decoder of a translation model and a language model. The decoder is a left-to-right 2-layer LSTM in which a single word embedding matrix is used for both input embeddings and the softmax predictions. When this model is trained as a language model on PTB using standard hyperparameter values it achieves test perplexity of 72.26. The encoder is a separate left-to-right 2-layer LSTM using the same word embeddings as the decoder. We use the input-feeding attention archietecture of Luong et al. (2015).

in nats which translates to $120.34$ bits. For translation pairs, we obtain

in nats which translates to $54.72$ bits.