OREGON STATE UNIVERSITY

You are here

k-nearest neighbor estimation of entropies with confidence

Titlek-nearest neighbor estimation of entropies with confidence
Publication TypeConference Paper
Year of Publication2011
AuthorsSricharan, K., R. Raich, and A. O. Hero, III
Conference Name2011 IEEE International Symposium on Information Theory - ISIT
Pagination1205 - 1209
Date Published08/2011
PublisherIEEE
Conference LocationSt. Petersburg, Russia
ISBN Number978-1-4577-0596-0
Keywordscentral limit theorem, confidence intervals, entropy estimation, k-NN density estimation, plug-in estimation
Abstract

We analyze a k-nearest neighbor (k-NN) class of plug-in estimators for estimating Shannon entropy and Rényi entropy. Based on the statistical properties of k-NN balls, we derive explicit rates for the bias and variance of these plug-in estimators in terms of the sample size, the dimension of the samples and the underlying probability distribution. In addition, we establish a central limit theorem for the plug-in estimator that allows us to specify confidence intervals on the entropy functionals. As an application, we use our theory in anomaly detection problems to specify thresholds for achieving desired false alarm rates.

DOI10.1109/ISIT.2011.6033726