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.
A conceptually straightforward way to estimate the differential entropy and mutual information is to use a kernel density estimator (KDE) @cite_59 @cite_60 @cite_19 @cite_64 @cite_34 @cite_41 : the densities @math are separately estimated from samples and the estimated densities are then used to calculate the entropy and mutual information via the resubstitution estimator. A typical approach to avoid overfitting is to conduct data splitting (DS): split the samples and use one part for KDE and the other for the resubstitution.
@cite_64 @cite_60 @cite_41 @cite_19 @cite_59 @cite_34
2109433950 2119420751 2951637626 2157510479
We develop a ldquoplug-inrdquo kernel estimator for the differential entropy that is consistent even if the kernel width tends to zero as quickly as 1 N, where N is the number of independent and identically distributed (i.i.d.) samples. Thus, accurate density estimates are not required for accurate kernel entropy estimates; in fact, it is a good idea when estimating entropy to sacrifice some accuracy in the quality of the corresponding density estimate. In the random sampling setting we estimate the entropy of a probability density distribution by the entropy of a kernel density estimator using the double exponential kernel. Under mild smoothness and moment conditions we show that the entropy of the kernel density estimator equals a sum of independent and identically distributed (i.i.d.) random variables plus a perturbation which is asymptotically negligible compared to the parametric rate n sup -1 2 . An essential part in the proof is obtained by exhibiting almost sure bounds for the Kullback-Leibler divergence between the kernel density estimator and its expected value. The basic technical tools are Doob's submartingale inequality and convexity (Jensen's inequality). We present simple and computationally efficient nonparametric estimators of R 'enyi entropy and mutual information based on an i.i.d. sample drawn from an unknown, absolutely continuous distribution over @math . The estimators are calculated as the sum of @math -th powers of the Euclidean lengths of the edges of the generalized nearest-neighbor' graph of the sample and the empirical copula of the sample respectively. For the first time, we prove the almost sure consistency of these estimators and upper bounds on their rates of convergence, the latter of which under the assumption that the density underlying the sample is Lipschitz continuous. Experiments demonstrate their usefulness in independent subspace analysis. We analyze the estimation of information theoretic measures of continuous random variables such as: differential entropy, mutual information or Kullback-Leibler divergence. The objective of this paper is two-fold. First, we prove that the information theoretic measure estimates using the k-nearest-neighbor density estimation with fixed k converge almost surely, even though the k-nearest-neighbor density estimation with fixed k does not converge to its true measure. Second, we show that the information theoretic measure estimates do not converge for k growing linearly with the number of samples. Nevertheless, these nonconvergent estimates can be used for solving the two-sample problem and assessing if two random variables are independent. We show that the two-sample and independence tests based on these nonconvergent estimates compare favorably with the maximum mean discrepancy test and the Hilbert Schmidt independence criterion.