Analysis of k-Nearest Neighbor Distances with Application to Entropy Estimation

Introduction

Estimating entropy and mutual information in a consistent manner is of importance in a number problems in machine learning. For example, entropy estimators have applications in goodness-of-fit testing (Goria et al., 2005), parameter estimation in semi-parametric models (Wolsztynski et al., 2005), studying fractal random walks (Alemany & Zanette, 1994), and texture classification (Hero et al., 2002a, b). Mutual information estimators have applications in feature selection (Peng & Dind, 2005), clustering (Aghagolzadeh et al., 2007), causality detection (Hlaváckova-Schindler et al., 2007), optimal experimental design (Lewi et al., 2007; Póczos & Lőrincz, 2009), fmri data processing (Chai et al., 2009), prediction of protein structures (Adami, 2004), and boosting and facial expression recognition (Shan et al., 2005). Both entropy estimators and mutual information estimators have been used for independent component and subspace analysis (Learned-Miller & Fisher, 2003; Szabó et al., 2007; Póczos & Lőrincz, 2005; Hulle, 2008), as well as for image registration (Kybic, 2006; Hero et al., 2002a, b). For further applications, see (Leonenko et al., 2008).

In this paper, we focus on the problem of estimating the Shannon entropy of a continuous random variable given samples from its distribution. All of our results extend to the estimation of mutual information, since the latter can be written as a sum of entropies. Specifically, for random variables $X$ and $Y$, $I(X;Y)=H(X)+H(Y)-H(X,Y)$. In our setting, we assume we are given $n$ IID samples from an unknown probability measure $P$. Under nonparametric assumptions (on the smoothness and tail behavior of $P$), our task is then to estimate the differential Shannon entropy of $P$.

Estimators of entropy and mutual information come in many forms (as reviewed in Section 2), but one common approach is based on statistics of $k$-nearest neighbor ($k$-NN) distances (i.e., the distance from a sample to its $k^{th}$ nearest neighbor amongst the samples, in some metric on the space). These nearest-neighbor estimates are largely based on initial work by Kozachenko & Leonenko (1987), who proposed an estimate for differential Shannon entropy and showed its weak consistency. Henceforth, we refer to this historic estimator as the ‘KL estimator’, after its discoverers. Although there has been much work on the problem of entropy estimation in the nearly three decades since the KL estimator was proposed, there are still major open questions about the finite-sample behavior of the KL estimator. The goal of this paper is to address some of these questions in the form of finite-sample bounds on the bias and variance of the estimator.

Specifically, our main contributions are the following:

We derive $O\left(\left(k/n\right)^{\beta/D}\right)$ bounds on the bias of the KL estimate, where $\beta$ is a measure of the smoothness (i.e., Hölder continuity) of the sampling density, $D$ is the intrinsic dimension of the support of the distribution, and $n$ is the sample size.

We derive $O\left(n^{-1}\right)$ bounds on the variance of the KL estimator.

We derive concentration inequalities for $k$-NN distances, as well as general bounds on expectations of $k$-NN distance statistics, with important special cases:

We give upper and lower bounds on the logarithms of $k$-NN distances. These are important for bounding the variance of the KL estimator, as well as $k$-NN estimators for divergences and mutual informations.

We present our results in the general setting of a set equipped with a metric, a base measure, a probability density, and an appropriate definition of dimension. This setting subsumes Euclidean spaces, in which $k$-NN methods have traditionally been analyzed, A recent exception in the context of classification, is Chaudhuri & Dasgupta (2014) which considers general metric spaces. but also includes, for instance, Riemannian manifolds, and perhaps other spaces of interest. We also strive to weaken some of the restrictive assumptions, such as compact support and boundedness of the density, on which most related work depends.

We anticipate that the some of the tools developed here may be used to derive error bounds for $k$-NN estimators of mutual information, divergences (Wang et al., 2009), their generalizations (e.g., Rényi and Tsallis quantities (Leonenko et al., 2008)), norms, and other functionals of probability densities. We leave such bounds to future work.

Section 2 discusses related work. Section 3 gives theoretical context and assumptions underlying our work. In Section 4, we prove concentration boundss for $k$-NN distances, and we use these in Section 5 to derive bounds on the expectations of $k$-NN distance statistics. Section 6 describes the KL estimator, for which we prove bounds on the bias and variance in Sections 7 and 8, respectively.

Related Work

Here, we review previous work on the analysis of $k$-nearest neighbor statistics and their role in estimating information theoretic functionals, as well as other approaches to estimating information theoretic functionals.

In general contexts, only weak consistency of the KL estimator is known (Kozachenko & Leonenko, 1987). Biau & Devroye (2015) recently reviewed finite-sample results known for the KL estimator. They show (Theorem 7.1) that, if the density $p$ has compact support, then the variance of the KL estimator decays as $O(n^{-1})$. They also claim (Theorem 7.2) to bound the bias of the KL estimator by $O(n^{-\beta})$, under the assumptions that $p$ is $\beta$-Hölder continuous ($\beta\in(0,1]$), bounded away from , and supported on the interval . However, in their proof Biau & Devroye (2015) neglect the additional bias incurred at the boundaries of, where the density cannot simultaneously be bounded away from and continuous. In fact, because the KL estimator does not attempt to correct for boundary bias, for densities bounded away from , the estimator may suffer bias worse than $O(n^{-\beta})$.

The KL estimator is also important for its role in the mutual information estimator proposed by Kraskov et al. (2004), which we refer to as the KSG estimator. The KSG estimator expands the mutual information as a sum of entropies, which it estimates via the KL estimator with a particular random (i.e., data-dependent) choice of the nearest-neighbor parameter $k$. The KSG estimator is perhaps the most widely used estimator for the mutual information between continuous random variables, despite the fact that it currently appears to have no theoretical guarantees, even asymptotically. In fact, one of the few theoretical results, due to Gao et al. (2015b), concerning the KSG estimator is a negative result: when estimating the mutual information between strongly dependent variables, the KSG estimator tends to systematically underestimate mutual information, due to increased boundary bias. To alleviate this, Gao et al. (2015b) provide a heuristic correction based on using local PCA to estimate the support of the distribution. Gao et al. (2015a) provide and prove asymptotic unbiasedness of another estimator, based on local Gaussian density estimation, that directly adapts to the boundary. Nevertheless, the widespread use of the KSG estimator motivates study of its behavior. We hope that our analysis of the KL estimator, in terms of which the KSG estimator can be written, will lead to a better understanding of the latter.

2 Analysis of nearest-neighbor distance statistics

Evans (2008) derives a law of large numbers for $k$-NN statistics with uniformly bounded (central) kurtosis as the sample size $n\to\infty$. Although it is not obvious that the kurtosis of $\log$-$k$-NN distances is uniformly bounded (indeed, each $\log$-$k$-NN distance approaches $-\infty$ almost surely), we show in Section 8 that this is indeed the case, and we apply the results of Evans (2008) to bound the variance of the KL estimator.

3 Other Approaches to Estimating Information Theoretic Functionals

Quite recently, there has been much work on analyzing new estimators for entropy, mutual information, divergences, and other functionals of densities. Most of this work has been along one of three approaches. One series of papers (Liu et al., 2012; Singh & Poczos, 2014b, a) studied boundary-corrected plug-in approach based on under-smoothed kernel density estimation. This approach has strong finite sample guarantees, but requires prior knowledge of the support of the density and can necessitate computationally demanding numerical integration. A second approach (Krishnamurthy et al., 2014; Kandasamy et al., 2015) uses von Mises expansion to correct the bias of optimally smoothed density estimates. This approach shares the difficulties of the previous approach, but is statistically more efficient. Finally, a long line of work (Pérez-Cruz, 2008; Pál et al., 2010; Sricharan et al., 2012, 2010; Moon & Hero, 2014) has studied entropy estimation based on continuum limits of certain properties of graphs (including $k$-NN graphs, spanning trees, and other sample-based graphs).

Most of these estimators achieve rates of $O\left(n^{-\min\left\{\frac{2\beta}{\beta+D},1\right\}}\right)$ or $O\left(n^{-\min\left\{\frac{4\beta}{2\beta+D},1\right\}}\right)$. Only the von Mises approach of Krishnamurthy et al. (2014) is known to achieve the minimax rate for general $\beta$ and $D$, but due to its high computational demand ($O(2^{D}n^{3})$), the authors suggest the use of other statistically less efficient estimators for moderately sized datasets. In this paper, we prove that, for $\beta\in(0,2]$, the KL estimator converges at the rate $O\left(n^{-\min\left\{\frac{4\beta}{2\beta+D},1\right\}}\right)$. It is also worth noting the relative computational efficiency of the KL estimator ($O\left(Dn^{2}\right)$, or $O\left(2^{D}n\log n\right)$ using $k$-d trees for small $D$).

Boundedness of the density: For all of the above approaches, theoretical finite-sample results known so far assume that the sampling density is lower and upper bounded by positive constants. This also excludes most distributions with unbounded support, and hence, many distributions of practical relevance. A distinctive feature of our results is that they hold for a variety of densities that approach and $\infty$ on their domain, which may be unbounded. Our bias bounds apply, for example, to densities that decay exponentially, such as Gaussian distributions. To our knowledge, the only previous results that apply to unbounded densities are those of Tsybakov & van der Meulen (1996), who show $\sqrt{n}$-consistency of a truncated modification of the KL estimate for a class of functions with exponentially decaying tails. In fact, components of our analysis are inspired by Tsybakov & van der Meulen (1996), and some of our assumptions are closely related. Their analysis only applies to the case $\beta=2$ and $D=1$, for which our results also imply $\sqrt{n}$-consistency, so our results can be seen in some respects as a generalization of this work.

Setup and Assumptions

In previous work on $k$-NN statistics (Evans et al., 2002; Biau & Devroye, 2015) and estimation of information theoretic functionals (Sricharan et al., 2010; Krishnamurthy et al., 2014; Singh & Poczos, 2014b; Moon & Hero, 2014), it has been common to make the assumption that the sampling distribution has full dimension with constant $\gamma_{*}$ and $\gamma^{*}$ (or, equivalently, that the density is lower and upper bounded by positive constants). This excludes distributions with densities approaching or $\infty$ on their domain, and hence also densities with unbounded support. By letting $\gamma_{*}$ and $\gamma^{*}$ be functions, our results extend to unbounded densities that instead satisfy certain tail bounds.

In order to ensure that entropy is well defined, we assume that $P$ is a probability measure absolutely continuous with respect to $\mu$, and that its probability density function $p:\mathcal{X}\to[0,\infty)$ satisfies See (Baccetti & Visser, 2013) for discussion of sufficient conditions for $H(p)<\infty$.

Finally, we assume we have $n+1$ samples $X,X_{1},...,X_{n}$ drawn IID from $P$. We would like to use these samples to estimate the entropy $H(p)$ as defined in Equation (1).

Our analysis and methods relate to the $k$-nearest neighbor distance $\varepsilon_{k}(x)$, defined for any $x\in\mathcal{X}$ by $\varepsilon_{k}(x)=d(x,X_{i})$, where $X_{i}$ is the $k^{th}$-nearest neighbor of $x$ in the set $\{X_{1},...,X_{n}\}$. Note that, since the definition of dimension used precludes the existence of atoms (i.e., for all $x\in\mathcal{X}$, $p(x)=\mu(\{x\})=0$), $\varepsilon_{k}(x)>0$, $\mu$-almost everywhere. This is important, since we will study $\log\varepsilon_{k}(x)$.

Concentration of k𝑘k-NN Distances

We begin with a consequence of the multiplicative Chernoff bound, asserting a sort of concentration of the distance of any point in $\mathcal{X}$ from its $k^{th}$-nearest neighbor in $\{X_{1},\dots,X_{n}\}$. Since the results of this section are concerned with fixed $x\in\mathcal{X}$, for notational simplicity, we suppress the dependence of $\gamma_{*}$ and $\gamma^{*}$ on $x$.

and, if $r\in\left[0,\min\left\{\left(\frac{k}{\gamma^{*}n}\right)^{1/D},\rho\right\}\right]$, then

Bounds on Expectations of KNN Statistics

Here, we use the concentration bounds of Section 4 to bound expectations of functions of $k$-nearest neighbor distances. Specifically, we give a simple formula for deriving bounds that applies to many functions of interest, including logarithms and (positive and negative) moments. As in the previous section, the results apply to a fixed $x\in\mathcal{X}$, and we continue to suppress the dependence of $\gamma_{*}$ and $\gamma^{*}$ on $x$.

($f_{+}(x)=\max\{0,f(x)\}$ and $f_{-}(x)=-\min\{0,f(x)\}$ denote the positive and negative parts of $f$, respectively).

which permits, for example, Gaussian distributions. It should be noted that the constant $C_{T}$ depends only on the metric measure space, the distribution $P$, and the function $f$, and, in particular, not on $k$.

We can apply Theorem 7 to several functions $f$ of interest. Here, we demonstrate the cases $f(x)=\log x$ and $f(x)=x^{\alpha}$ for certain $\alpha$, as we will use these bounds when analyzing the KL estimator.

(where $\Gamma(s,x):=\int_{x}^{\infty}t^{s-1}e^{-t}\,dt$ denotes the upper incomplete Gamma function, and we used the bound $\Gamma(s,x)\leq x^{s-1}e^{-x}$), and (4) gives

for $C_{1}=\frac{\gamma^{*}e^{k\gamma_{*}/\gamma^{*}}}{Dk\gamma_{*}}$. For $\alpha>0$, $f(x)=x^{\alpha}$, (3) gives

where $C_{2}=1+2\frac{\alpha}{D}$. For any $\alpha\in[-Dk\gamma_{*}/\gamma^{*},0]$, when $f(x)=-x^{\alpha}$, (4) gives

where $C_{3}=1+\frac{\alpha\gamma^{*}e^{k\gamma_{*}/\gamma^{*}}}{Dk\gamma_{*}+\alpha\gamma^{*}}$.

The KL Estimator for Entropy

Recall that, for a random variable $X$ sampled from a probability density $p$ with respect to a base measure $\mu$, the Shannon entropy is defined as

As discussed in Section 1, many applications call for estimate of $H(X)$ given $n$ IID samples $X_{1},\dots,X_{n}\sim p$. For a positive integer $k$, the KL estimator is typically written as

where, for any $x\in\mathcal{X}$, $\varepsilon>0$,

denotes the local average of $p$ in a ball of radius $\varepsilon$ around $x$. Since $p_{\varepsilon}$ is a smoothed approximation of $p$ (with smoothness increasing with $\varepsilon$), the KL estimate can be intuitively thought of as a plug-in estimator for $H(X)$, using a density estimate with an adaptive smoothing parameter.

In the next two sections, we utilize the bounds derived in Section 5 to bound the bias and variance of the KL estimator. We note that, for densities in the $\beta$-Hölder smoothness class ($\beta\in(0,2]$), our results imply a mean-squared error of $O(n^{-2\beta/D})$ when $\beta<D/2$ and $O(n^{-1})$ when $\beta\geq D/2$.

Bias Bound

In this section, we prove bounds on the bias of the KL estimator, first in a relatively general setting, and then, as a corollary, in a more specific but better understood setting.

where $C_{B}=(1+c_{D})C_{2}C_{\beta}\Gamma_{B}$.

where $C_{H}=(1+c_{D})C_{2}\Gamma\frac{LD}{D+\beta}$.

Variance Bound

If the terms $\log\varepsilon_{k}(X_{i})$ were independent, a Bernstein inequality, together with the moment bound (13) would imply a sub-Gaussian concentration bound on the KL estimator about its expectation. This may follow from one of several more refined concentration results relaxing the independence assumption that have been proposed.

2 Bound on the Variance of the KL Estimate

Bounds on the variance of the KL estimator now follow from the law of large numbers in Evans (2008) (itself an application of the Efron-Stein inequality to $k$-NN statistics).

Bounds on the Mean Squared Error

The bias and variance bounds (Theorems 10 and 18) imply a bound on the mean squared error of the KL estimator:

is $\beta$-Hölder continuous with $\beta\in(0,2]$.

vanishes on $\partial\mathcal{X}$. If $\beta>1$, then also suppose $\|\nabla p\|_{2}$ vanishes on $\partial\mathcal{X}$.

[TODO: Other assumptions.] satisfies the assumptions of Theorems 10 and 18. Then,

If we let $k$ scale as $k\asymp n^{\max\left\{0,\frac{2\beta-D}{2\beta+D}\right\}}$ this gives an overall convergence rate of

Conclusions and Future Work

This paper derives finite sample bounds on the bias and variance of the KL estimator under general conditions, including for certain classes of unbounded distributions. As intermediate results, we proved concentration inequalities for $k$-NN distances and bounds on the expectations of statistics of $k$-NN distances. We hope these results and methods may lead to convergence rates for the widely used KSG mutual information estimator, or to generalize convergence rates for other estimators of entropy and related functionals to unbounded distributions.

Acknowledgements

This material is based upon work supported by a National Science Foundation Graduate Research Fellowship to the first author under Grant No. DGE-1252522.

References