Estimating mutual information from i.i.d. samples drawn from an unknown joint density function is a basic statistical problem of broad interest with multitudinous applications. The most popular estimator is one proposed by Kraskov and St "ogbauer and Grassberger (KSG) in 2004, and is nonparametric and based on the distances of each sample to its @math nearest neighboring sample, where @math is a fixed small integer. Despite its widespread use (part of scientific software packages), theoretical properties of this estimator have been largely unexplored. In this paper we demonstrate that the estimator is consistent and also identify an upper bound on the rate of convergence of the bias as a function of number of samples. We argue that the superior performance benefits of the KSG estimator stems from a curious "correlation boosting" effect and build on this intuition to modify the KSG estimator in novel ways to construct a superior estimator. As a byproduct of our investigations, we obtain nearly tight rates of convergence of the @math error of the well known fixed @math nearest neighbor estimator of differential entropy by Kozachenko and Leonenko.
The basic estimation question studied in this paper takes a different hue depending on whether the underlying distribution is discrete or continuous. In the discrete setting, significant understanding of the minimax rate-optimal estimation of functionals, including entropy and mutual information, of an unknown probability mass function is attained via recent works @cite_5 @cite_48 @cite_39 @cite_45 @cite_13 . The continuous setting is significantly different, bringing to fore the interplay of geometry of the Euclidean space as well as the role of dimensionality of the domain in terms of estimating the information theoretic quantities; this setting is the focus of this paper. This fundamental question has been of longstanding interest in the theoretical statistics community where it is a canonical question of estimating a functional of the (unknown) density @cite_8 but also in the machine learning @cite_15 @cite_10 , information theory @cite_36 @cite_5 @cite_13 @cite_52 , and theoretical computer science @cite_39 @cite_43 @cite_7 communities. The popularity of mutual information and other information theoretic quantities comes from their wide use as basic features in several downstream applications @cite_28 @cite_9 @cite_4 @cite_57 .
@cite_4 @cite_7 @cite_8 @cite_36 @cite_48 @cite_10 @cite_28 @cite_9 @cite_52 @cite_39 @cite_57 @cite_43 @cite_45 @cite_5 @cite_15 @cite_13
2133027741 1989151402 2114771311 2127090196
These lecture notes highlight the mathematical and computational structure relating to the formulation of, and development of algorithms for, the Bayesian approach to inverse problems in differential equations. This approach is fundamental in the quantification of uncertainty within applications in volving the blending of mathematical models with data. The finite dimensional situation is described first, along with some motivational examples. Then the development of probability measures on separable Banach space is undertaken, using a random series over an infinite set of functions to construct draws; these probability measures are used as priors in the Bayesian approach to inverse problems. Regularity of draws from the priors is studied in the natural Sobolev or Besov spaces implied by the choice of functions in the random series construction, and the Kolmogorov continuity theorem is used to extend regularity considerations to the space of Holder continuous functions. Bayes’ theorem is de rived in this prior setting, and here interpreted as finding conditions under which the posterior is absolutely continuous with respect to the prior, and determining a formula for the Radon-Nikodym derivative in terms of the likelihood of the data. Having established the form of the posterior, we then describe various properties common to it in the infinite dimensional setting. These properties include well-posedness, approximation theory, and the existence of maximum a posteriori estimators. We then describe measure-preserving dynamics, again on the infinite dimensional space, including Markov chain-Monte C arlo and sequential Monte Carlo methods, and measure-preserving reversible stochastic differential equations. By formulating the theory and algorithms on the underlying infinite dimensional space, we obtain a framework suitable for rigorous analysis of the accuracy of reconstructions, of computational complexity, as well as naturally constructing algorithms which perform well under mesh refinement, since they are inherently well-defined in infinite dimensions. We propose a general methodology for the construction and analysis of essentially minimax estimators for a wide class of functionals of finite dimensional parameters, and elaborate on the case of discrete distributions, where the support size @math is unknown and may be comparable with or even much larger than the number of observations @math . We treat the respective regions where the functional is nonsmooth and smooth separately. In the nonsmooth regime, we apply an unbiased estimator for the best polynomial approximation of the functional whereas, in the smooth regime, we apply a bias-corrected version of the maximum likelihood estimator (MLE). We illustrate the merit of this approach by thoroughly analyzing the performance of the resulting schemes for estimating two important information measures: 1) the entropy @math and 2) @math . We obtain the minimax @math rates for estimating these functionals. In particular, we demonstrate that our estimator achieves the optimal sample complexity @math for entropy estimation. We also demonstrate that the sample complexity for estimating @math n S^ 1 S @math 1 , we show the minimax @math rate for estimating @math is @math for infinite support size, while the maximum @math rate for the MLE is @math . For all the above cases, the behavior of the minimax rate-optimal estimators with @math samples is essentially that of the MLE (plug-in rule) with @math samples, which we term “effective sample size enlargement.” We highlight the practical advantages of our schemes for the estimation of entropy and mutual information. We compare our performance with various existing approaches, and demonstrate that our approach reduces running time and boosts the accuracy. Moreover, we show that the minimax rate-optimal mutual information estimator yielded by our framework leads to significant performance boosts over the Chow–Liu algorithm in learning graphical models. The wide use of information measure estimation suggests that the insights and estimators obtained in this paper could be broadly applicable. We present some new results on the nonparametric estimation of entropy and mutual information. First, we use an exact local expansion of the entropy function to prove almost sure consistency and central limit theorems for three of the most commonly used discretized information estimators. The setup is related to Grenander's method of sieves and places no assumptions on the underlying probability measure generating the data. Second, we prove a converse to these consistency theorems, demonstrating that a misapplication of the most common estimation techniques leads to an arbitrarily poor estimate of the true information, even given unlimited data. This "inconsistency" theorem leads to an analytical approximation of the bias, valid in surprisingly small sample regimes and more accurate than the usual 1 N formula of Miller and Madow over a large region of parameter space. The two most practical implications of these results are negative: (1) information estimates in a certain data regime are likely contaminated by bias, even if "bias-corrected" estimators are used, and (2) confidence intervals calculated by standard techniques drastically underestimate the error of the most common estimation methods.Finally, we note a very useful connection between the bias of entropy estimators and a certain polynomial approximation problem. By casting bias calculation problems in this approximation theory framework, we obtain the best possible generalization of known asymptotic bias results. More interesting, this framework leads to an estimator with some nice properties: the estimator comes equipped with rigorous bounds on the maximum error over all possible underlying probability distributions, and this maximum error turns out to be surprisingly small. We demonstrate the application of this new estimator on both real and simulated data. We introduce a new approach to characterizing the unobserved portion of a distribution, which provides sublinear--sample estimators achieving arbitrarily small additive constant error for a class of properties that includes entropy and distribution support size. Additionally, we show new matching lower bounds. Together, this settles the longstanding question of the sample complexities of these estimation problems, up to constant factors. Our algorithm estimates these properties up to an arbitrarily small additive constant, using O(n log n) samples, where n is a bound on the support size, or in the case of estimating the support size, 1 n is a lower bound on the probability of any element of the domain. Previously, no explicit sublinear--sample algorithms for either of these problems were known. Our algorithm is also computationally extremely efficient, running in time linear in the number of samples used. In the second half of the paper, we provide a matching lower bound of Ω(n log n) samples for estimating entropy or distribution support size to within an additive constant. The previous lower-bounds on these sample complexities were n 2O(√log n). To show our lower bound, we prove two new and natural multivariate central limit theorems (CLTs); the first uses Stein's method to relate the sum of independent distributions to the multivariate Gaussian of corresponding mean and covariance, under the earthmover distance metric (also known as the Wasserstein metric). We leverage this central limit theorem to prove a stronger but more specific central limit theorem for "generalized multinomial" distributions---a large class of discrete distributions, parameterized by matrices, that represents sums of independent binomial or multinomial distributions, and describes many distributions encountered in computer science. Convergence here is in the strong sense of statistical distance, which immediately implies that any algorithm with input drawn from a generalized multinomial distribution behaves essentially as if the input were drawn from a discretized Gaussian with the same mean and covariance. Such tools in the multivariate setting are rare, and we hope this new tool will be of use to the community.