text: 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.
  @cite_33: Estimating divergences in a consistent way is of great importance in many machine learning tasks. Although this is a fundamental problem in nonparametric statistics, to the best of our knowledge there has been no finite sample exponential inequality convergence bound derived for any divergence estimators. The main contribution of our work is to provide such a bound for an estimator of R 'enyi- @math divergence for a smooth H "older class of densities on the @math -dimensional unit cube @math . We also illustrate our theoretical results with a numerical experiment.
  @cite_60: For a multivariate density f with respect to Lebesgue measure μ, the estimation of MathType!MTEF!2!1!+- feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXafv3ySLgzGmvETj2BSbqefm0B1jxALjhiov2D aebbfv3ySLgzGueE0jxyaibaiiYdd9qrFfea0dXdf9vqai-hEir8Ve ea0de9qq-hbrpepeea0db9q8as0-LqLs-Jirpepeea0-as0Fb9pgea 0lrP0xe9Fve9Fve9qapdbaqaaeGacaGaaiaabeqaamaabaabcaGcba Waa8qaaeaacaWGkbGaaiikaiaadAgacaGGPaGaamOzaiaadsgacqaH 8oqBaSqabeqaniabgUIiYdaaaa!4404! [ J(f)fd ], and in particular MathType!MTEF!2!1!+- feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXafv3ySLgzGmvETj2BSbqefm0B1jxALjhiov2D aebbfv3ySLgzGueE0jxyaibaiiYdd9qrFfea0dXdf9vqai-hEir8Ve ea0de9qq-hbrpepeea0db9q8as0-LqLs-Jirpepeea0-as0Fb9pgea 0lrP0xe9Fve9Fve9qapdbaqaaeGacaGaaiaabeqaamaabaabcaGcba Waa8qaaeaacaWGMbWaaWbaaSqabeaacaaIYaaaaOGaamizaiabeY7a TbWcbeqab0Gaey4kIipaaaa!41E4! [ f^2 d ] and MathType!MTEF!2!1!+- feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXafv3ySLgzGmvETj2BSbqefm0B1jxALjhiov2D aebbfv3ySLgzGueE0jxyaibaiiYdd9qrFfea0dXdf9vqai-hEir8Ve ea0de9qq-hbrpepeea0db9q8as0-LqLs-Jirpepeea0-as0Fb9pgea 0lrP0xe9Fve9Fve9qapdbaqaaeGacaGaaiaabeqaamaabaabcaGcba Waa8qaaeaacaWGMbGaciiBaiaac+gacaGGNbGaamOzaiaadsgacqaH 8oqBaSqabeqaniabgUIiYdaaaa!44AC! [ f fd ], is studied. These two particular functionals are important in a number of contexts. Asymptotic bias and variance terms are obtained for the estimators MathType!MTEF!2!1!+- feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXafv3ySLgzGmvETj2BSbqefm0B1jxALjhiov2D aebbfv3ySLgzGueE0jxyaibaiiYdd9qrFfea0dXdf9vqai-hEir8Ve ea0de9qq-hbrpepeea0db9q8as0-LqLs-Jirpepeea0-as0Fb9pgea 0lrP0xe9Fve9Fve9qapdbaqaaeGacaGaaiaabeqaamaabaabcaGcba WaaybyaeqaleqabaGaey4jIKnaneaacaWGjbaaaOGaeyypa0Zaa8qa aeaacaWGkbGaaiikamaawagabeWcbeqaaiabgEIizdqdbaGaamOzaa aakiaacMcacaWGKbGaamOramaaBaaaleaacaWGobaabeaaaeqabeqd cqGHRiI8aaaa!4994! [ I ^ = J( f ^ )dF_N ] and MathType!MTEF!2!1!+- feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXafv3ySLgzGmvETj2BSbqefm0B1jxALjhiov2D aebbfv3ySLgzGueE0jxyaibaiiYdd9qrFfea0dXdf9vqai-hEir8Ve ea0de9qq-hbrpepeea0db9q8as0-LqLs-Jirpepeea0-as0Fb9pgea 0lrP0xe9Fve9Fve9qapdbaqaaeGacaGaaiaabeqaamaabaabcaGcba WaaybyaeqaleqabaGaeSipIOdaneaacaWGjbaaaOGaeyypa0Zaa8qa aeaacaWGkbGaaiikamaawagabeWcbeqaaiabgEIizdqdbaGaamOzaa aakiaacMcadaGfGbqabSqabeaacqGHNis2a0qaaiaadAgaaaGccaWG KbGaeqiVd0galeqabeqdcqGHRiI8aaaa!4C40! [ I ^ = J( f ^ ) f ^ d ], where MathType!MTEF!2!1!+- feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXafv3ySLgzGmvETj2BSbqefm0B1jxALjhiov2D aebbfv3ySLgzGueE0jxyaibaiiYdd9qrFfea0dXdf9vqai-hEir8Ve ea0de9qq-hbrpepeea0db9q8as0-LqLs-Jirpepeea0-as0Fb9pgea 0lrP0xe9Fve9Fve9qapdbaqaaeGacaGaaiaabeqaamaabaabcaGcba WaaybyaeqaleqabaGaey4jIKnaneaacaWGMbaaaaaa!3E9C! [ f ^ ] is a kernel density estimate of f and F n is the empirical distribution function based on the random sample X 1 ,..., X n from f. For the two functionalsmentioned above, a first order bias term for I can be made zero by appropriate choices of non-unimodal kernels. Suggestions for the choice of bandwidth are given; for MathType!MTEF!2!1!+- feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn hiov2DGi1BTfMBaeXafv3ySLgzGmvETj2BSbqefm0B1jxALjhiov2D aebbfv3ySLgzGueE0jxyaibaiiYdd9qrFfea0dXdf9vqai-hEir8Ve ea0de9qq-hbrpepeea0db9q8as0-LqLs-Jirpepeea0-as0Fb9pgea 0lrP0xe9Fve9Fve9qapdbaqaaeGacaGaaiaabeqaamaabaabcaGcba WaaybyaeqaleqabaGaey4jIKnaneaacaWGjbaaaOGaeyypa0Zaa8qa aeaadaGfGbqabSqabeaacqGHNis2a0qaaiaadAgaaaGccaWGKbGaam OramaaBaaaleaacaWGobaabeaaaeqabeqdcqGHRiI8aaaa!476C! [ I ^ = f ^ dF_N ], a study of optimal bandwidth is possible.
  @cite_55: We prove a new exponential concentration inequality for a plug-in estimator of the Shannon mutual information. Previous results on mutual information estimation only bounded expected error. The advantage of having the exponential inequality is that, combined with the union bound, we can guarantee accurate estimators of the mutual information for many pairs of random variables simultaneously. As an application, we show how to use such a result to optimally estimate the density function and graph of a distribution which is Markov to a forest graph.
  @cite_0: We propose and analyse estimators for statistical functionals of one or more distributions under nonparametric assumptions. Our estimators are derived from the von Mises expansion and are based on the theory of influence functions, which appear in the semiparametric statistics literature. We show that estimators based either on data-splitting or a leave-one-out technique enjoy fast rates of convergence and other favorable theoretical properties. We apply this framework to derive estimators for several popular information theoretic quantities, and via empirical evaluation, show the advantage of this approach over existing estimators.
  @cite_63: We consider nonparametric estimation of L2, Renyi-α and Tsallis-α divergences between continuous distributions. Our approach is to construct estimators for particular integral functionals of two densities and translate them into divergence estimators. For the integral functionals, our estimators are based on corrections of a preliminary plug-in estimator. We show that these estimators achieve the parametric convergence rate of n-1 2 when the densities' smoothness, s, are both at least d 4 where d is the dimension. We also derive minimax lower bounds for this problem which confirm that s > d 4 is necessary to achieve the n-1 2 rate of convergence. We validate our theoretical guarantees with a number of simulations.
  @cite_66: We analyze a plug-in estimator for a large class of integral functionals of one or more continuous probability densities. This class includes important families of entropy, divergence, mutual information, and their conditional versions. For densities on the d-dimensional unit cube [0,1]d that lie in a β-Holder smoothness class, we prove our estimator converges at the rate O(n-β β+d). Furthermore, we prove the estimator is exponentially concentrated about its mean, whereas most previous related results have proven only expected error bounds on estimators.
summary: In some cases, the parametric rate of convergence of @math of @math error is achieved: of particular interest is the result of @cite_60 where the parametric rate is achieved for differential entropy estimation via KDE of density followed by the resubstitution estimator when the dimension is no more than 6. Numerical evidence suggests the hypothesis that the lower bounds derived in Theorem below could perhaps be improved when the dimension is more than 4 and estimators constrained to only use fixed @math -NN distances. Under certain very strong conditions on the density class (that are relevant in certain applications on graphical model selection @cite_55 ), exponential rate of convergence can be demonstrated @cite_66 @cite_33 . Recent works @cite_63 @cite_0 have studied the performance of the leave-one-out (LOO) approach where all but the sample of resubstitution are used for KDE, involving techniques such as von Mises expansion methods.