Breaking the Bandwidth Barrier: Geometrical Adaptive Entropy Estimation

By Weihao Gao, Sewoong Oh, Pramod Viswanath. 2016

33 citations recorded by the source corpus.

Estimators of information theoretic measures, such as entropy and mutual information, are a basic workhorse for many downstream applications in modern data science. State-of-the-art approaches have been either geometric [nearest neighbor (NN)-based] or kernel-based (with a globally chosen bandwidth). In this paper, we combine both these approaches to design new estimators of entropy and mutual information that outperform the state-of-the-art methods. Our estimator uses local bandwidth choices of <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-NN distances with a finite <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>, independent of the sample size. Such a local and data dependent choice ameliorates boundary bias and improves performance in practice, but the bandwidth is vanishing at a fast rate, leading to a non-vanishing bias. We show that the asymptotic bias of the proposed estimator is <italic>universal</italic>; it is independent of the underlying distribution. Hence, it can be precomputed and subtracted from the estimate. As a byproduct, we obtain a unified way of obtaining <italic>both</italic> the kernel and NN estimators. The corresponding theoretical contribution relating the asymptotic geometry of nearest neighbors to order statistics is of independent mathematical interest.

Subfields: Artificial Intelligence, Statistics and Probability

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 Statistics and Probability

Citations in the corpus

Estimating Mutual Information for Discrete-Continuous Mixtures (2017, methodology): “Further, recent works [14, 16] involving a combination of kernel density estimators and k-NN methods have been proposed to further improve the KSG estimator.”
The Nearest Neighbor Information Estimator is Adaptively Near Minimax Rate-Optimal (2017, background): “In the literature, a large collection of work assume that the density is uniformly bounded away from zero [23, 29, 57, 30, 53], while others put various assumptions quantifying on average how close the density is to zero [25, 40, 56, 14, 20, 52, 11].”
Decomposition of Uncertainty for Active Learning and Reliable Reinforcement Learning in Stochastic Systems (2017, methodology): “The quantity in equation (7) can be approximating using standard entropy estimators, e.g. nearest-neighbor methods [Kozachenko and Leonenko, 1987, Kraskov et al., 2004, Gao et al., 2016].”
Uncertainty Decomposition in Bayesian Neural Networks with Latent Variables (2017, methodology): “The quantity in equation (7) can be approximating using standard entropy estimators, e.g. nearest-neighbor methods (Kozachenko & Leonenko, 1987; Kraskov et al., 2004; Gao et al., 2016).”
Decomposition of Uncertainty in Bayesian Deep Learning for Efficient and Risk-sensitive Learning (2017, background): “(5) can be approximated using standard entropy estimators, e.g. nearest-neighbor methods (Kozachenko & Leonenko, 1987; Kraskov et al., 2004; Gao et al., 2016).”