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_38: 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.
  @cite_37: Local likelihood was introduced by Tibshirani and Hastie as a method of smoothing by local polynomials in non-Gaussian regression models. In this paper an extension of these methods to density estimation is discussed, and comparison with other methods of density estimation presented. The local likelihood method has particularly strong advantages over kernel methods when estimating tails of densities and in multivariate settings. Suppose constraints are incorporated in a simple manner. Asymptotic properties of the estimate are discussed. A method for computing the estimate is outlined.
  @cite_14: 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.
  @cite_26: This paper develops a nonparametric density estimator with parametric overtones. Suppose f(x, θ) is some family of densities, indexed by a vector of parameters θ. We define a local kernel-smoothed likelihood function which, for each x, can be used to estimate the best local parametric approximant to the true density. This leads to a new density estimator of the form f(x, o(x)), thus inserting the best local parameter estimate for each new value of x. When the bandwidth used is large, this amounts to ordinary full likelihood parametric density estimation, while for moderate and small bandwidths the method is essentially nonparametric, using only local properties of data and the model. Alternative ways more general than via the local likelihood are also described. The methods can be seen as ways of nonparametrically smoothing the parameter within a parametric class. Properties of this new semiparametric estimator are investigated. Our preferred version has approximately the same variance as the ordinary kernel method but potentially a smaller bias. The new method is seen to perform better than the traditional kernel method in a broad nonparametric vicinity of the parametric model employed, while at the same time being capable of not losing much in precision to full likelihood methods when the model is correct. Other versions of the method are approximately equivalent to using particular higher order kernels in a semiparametric framework. The methodology we develop can be seen as the density estimation parallel to local likelihood and local weighted least squares theory in nonparametric regression.
  @cite_15: We demonstrate that a popular class of nonparametric mutual information (MI) estimators based on k-nearest-neighbor graphs requires number of samples that scales exponentially with the true MI. Consequently, accurate estimation of MI between two strongly dependent variables is possible only for prohibitively large sample size. This important yet overlooked shortcoming of the existing estimators is due to their implicit reliance on local uniformity of the underlying joint distribution. We introduce a new estimator that is robust to local non-uniformity, works well with limited data, and is able to capture relationship strengths over many orders of magnitude. We demonstrate the superior performance of the proposed estimator on both synthetic and real-world data.
  @cite_54: 
  @cite_53: We describe an interesting application of the principle of local learning to density estimation. Locally weighted fitting of a Gaussian with a regularized full covariance matrix yields a density estimator which displays improved behavior in the case where much of the probability mass is concentrated along a low dimensional manifold. While the proposed estimator is not guaranteed to integrate to 1 with a finite sample size, we prove asymptotic convergence to the true density. Experimental results illustrating the advantages of this estimator over classic non-parametric estimators are presented. Nous decrivons une application du principe d'apprentissage local a l'estimation de densite. Le lissage pondere localement d'une gaussienne utilisant une matrice de covariance pleine et regularisee conduit a un estimateur de densite ayant un comportement ameliore lorsque la masse de probabilite est concentree le long d'une variete de basse dimension. Meme si l'estimateur propose n'est pas garanti d'integrer a 1 sur un ensemble de donnees fini, nous prouvons la convergence asymptotique de la vraie densite. Les resultats experimentaux illustrant les avantages de cet estimateur sur les estimateurs non parametriques classiques sont presentes.
  @cite_65: We develop the general, multivariate case of the Edgeworth approximation of differential entropy and show that it can be more accurate than the nearest-neighbor method in the multivariate case and that it scales better with sample size. Furthermore, we introduce mutual information estimation as an application.
  @cite_3: Nearest neighbor (k-NN) graphs are widely used in machine learning and data mining applications, and our aim is to better understand what they reveal about the cluster structure of the unknown underlying distribution of points. Moreover, is it possible to identify spurious structures that might arise due to sampling variability? Our first contribution is a statistical analysis that reveals how certain subgraphs of a k-NN graph form a consistent estimator of the cluster tree of the underlying distribution of points. Our second and perhaps most important contribution is the following finite sample guarantee. We carefully work out the tradeoff between aggressive and conservative pruning and are able to guarantee the removal of all spurious cluster structures at all levels of the tree while at the same time guaranteeing the recovery of salient clusters. This is the first such finite sample result in the context of clustering.
  @cite_56: 
  @cite_24: We present two related contributions of independent interest: (1) high-probability finite sample rates for k-NN density estimation, and (2) practical mode estimators - based on k-NN - which attain minimax-optimal rates under surprisingly general distributional conditions.
  @cite_2: We develop and analyze M-estimation methods for divergence functionals and the likelihood ratios of two probability distributions. Our method is based on a nonasymptotic variational characterization of f -divergences, which allows the problem of estimating divergences to be tackled via convex empirical risk optimization. The resulting estimators are simple to implement, requiring only the solution of standard convex programs. We present an analysis of consistency and convergence for these estimators. Given conditions only on the ratios of densities, we show that our estimators can achieve optimal minimax rates for the likelihood ratio and the divergence functionals in certain regimes. We derive an efficient optimization algorithm for computing our estimates, and illustrate their convergence behavior and practical viability by simulations.
  @cite_47: 
  @cite_58: We consider estimation of functionals of a probability density of the elements of a sample. We discuss a class of statistics based on spacings of increasing order and show that these statistics are almost surely consistent. Special attention is paid to entropy estimation. In particular we derive asymptotic normality in that case. It turns out that the entropy estimator is efficient under certain conditions on the unknown density.
  @cite_25: Abstract : The discrimination problem (two population case) may be defined as follows: e random variable Z, of observed value z, is distributed over some space (say, p-dimensional) either according to distribution F, or according to distribution G. The problem is to decide, on the basis of z, which of the two distributions Z has.
  @cite_12: Motivated by a broad range of potential applications in topological and geometric inference, we introduce a weighted version of the k-nearest neighbor density estimate. Various pointwise consistency results of this estimate are established. We present a general central limit theorem under the lightest possible conditions. In addition, a strong approximation result is obtained and the choice of the optimal set of weights is discussed. In particular, the classical k-nearest neighbor estimate is not optimal in a sense described in the manuscript. The proposed method has been implemented to recover level sets in both simulated and real-life data.
  @cite_11: Estimating mutual information (MI) from samples is a fundamental problem in statistics, machine learning, and data analysis. Recently it was shown that a popular class of non-parametric MI estimators perform very poorly for strongly dependent variables and have sample complexity that scales exponentially with the true MI. This undesired behavior was attributed to the reliance of those estimators on local uniformity of the underlying (and unknown) probability density function. Here we present a novel semi-parametric estimator of mutual information, where at each sample point, densities are locally approximated by a Gaussians distribution. We demonstrate that the estimator is asymptotically unbiased. We also show that the proposed estimator has a superior performance compared to several baselines, and is able to accurately measure relationship strengths over many orders of magnitude.
summary: Alternative methods involve estimation of the entropies using spacings @cite_54 @cite_58 , the Edgeworth expansion @cite_65 , and convex optimization @cite_2 . Among the @math -NN methods, there are two variants: either @math is chosen to grow with the sample size @math or @math is fixed. There is a large literature on the former, where the classical result is the possibility of consistent estimation of the density from @math -NN distances @cite_47 @cite_25 , including recent sharper consistency characterizations @cite_12 @cite_3 . Several works have applied this basic insight towards the estimation of the specific case of information theoretic quantities @cite_24 @cite_53 and extensions to generalized NN graphs @cite_14 . For fixed @math -NN methods, apart from the works referred to in the main text, detailed experimental comparisons are in @cite_38 and local Gaussian approaches studied in @cite_15 @cite_11 @cite_56 bringing together local likelihood density estimation methods @cite_37 @cite_26 with @math -NN driven choices of kernel bandwidth.