Estimation of Renyi Entropy and Mutual Information Based on Generalized Nearest-Neighbor Graphs

By Dávid Pál, Barnab'as P'oczos, Csaba Szepesvari. 2010

171 citations recorded by the source corpus.

We present simple and computationally efficient nonparametric estimators of Renyi entropy and mutual information based on an i.i.d. sample drawn from an unknown, absolutely continuous distribution over ℝd. The estimators are calculated as the sum of p-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.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Signal Processing

Citations in the corpus

Nonparametric Divergence Estimation with Applications to Machine Learning on Distributions (2011, methodology): “Recently, Póczos et al. (2010), Pál et al. (2010) proposed a method for consistent Rényi information estimation, but this estimator also uses one sample only and cannot be used for estimating divergences.”
REGO: Rank-based Estimation of Renyi Information using Euclidean Graph Optimization (2010, background): “Motivated by his work Pál et al. (2010) proved the theorem for a more general class of k-NN graphs including GR(k), and applicable for any α ∈ (0, 1).”
On the Kozachenko-Leonenko entropy estimator (2016, background): “Let us finally mention the paper of Pál, Póczos and Szepesvári [18]: they study other notions of entropy, work in dimension d ≥ 1, use estimators based on nearest neighbors and give some bounds on their rates of convergence.”
Recovering Best Statistical Guarantees via the Empirical Divergence-Based Distributionally Robust Optimization (2016, methodology): “Unless one assumes a parametric framework, calibrating the ball radius requires nonparametric divergence estimation, which involves challenging statistical analyses on bandwidth tuning and loss of estimation eﬃciency (e.g., Moon and Hero (2014), Nguyen et al. (2007), P´al et al. (2010)).”
A Robust-Equitable Measure for Feature Ranking and Selection (2017, background): “Pál et al. (2010) also considered similar Hölder condition when they studied the convergence of k-nearest-neighbor (KNN) based MI estimator.”
Flow of Renyi information in deep neural networks (2016, methodology): “[6] proposed an estimator using k-nearest-neighbor graphs with a high probability bounds on the estimation error.”
An Entropy Search Portfolio for Bayesian Optimization (2014, methodology): “The method was motivated by similar information-theoretic ideas as ESP and is based on a different measure of uncertainty, namely the R ´ enyi α -divergence [24].”
Empirical estimation of entropy functionals with confidence (2010, background): “These include consistent estimators based on entropic graphs [19, 36], gap estimators [43], nearest neighbor distances [17, 26, 29, 45], kernel density plug-in estimators [1, 11, 3, 18, 4, 16], Edgeworth approximations [21], convex risk minimization [35] and orthogonal projections [25].”
On the Estimation of α-Divergences (2011, methodology): “Recently, Póczos et al. (2010); Pál et al. (2010) proposed a method for consistent Rényi information estimation, but this estimator also uses one sample only and cannot be used for estimating divergences.”
Breaking the Bandwidth Barrier: Geometrical Adaptive Entropy Estimation (2016, background): “As noted in [18], such an assumption is common in the literature on consistency of k-NN estimators, where it has been implicitly assumed in existing analyses of entropy estimators including [9, 5, 12, 27], without explicitly stating that such assumptions are being made.”
Demystifying fixed k-nearest neighbor information estimators (2016, background): “[38] Dávid Pál, Barnabás Póczos, and Csaba Szepesvári.”
On the Estimation of alpha-Divergences (2011, unknown): “The closest existing work most relevant to the topic of this paper is the work of Wang et al. (2009a), who provided an estimator for the α → 1 limit case only, i.”