Breaking the Bandwidth Barrier: Geometrical Adaptive Entropy Estimation

Weihao Gao, Sewoong Oh, Pramod Viswanath

Research output: Contribution to journalArticle

Abstract

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 k -NN distances with a finite k , 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 universal; 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 both the kernel and NN estimators. The corresponding theoretical contribution relating the asymptotic geometry of nearest neighbors to order statistics is of independent mathematical interest.

Original languageEnglish (US)
Pages (from-to)3313-3330
Number of pages18
JournalIEEE Transactions on Information Theory
Volume64
Issue number5
DOIs
StatePublished - May 2018

Fingerprint

entropy
Entropy
Bandwidth
trend
Byproducts
statistics
Statistics
mathematics
Geometry
science
performance

Keywords

  • Information theory
  • density estimation robust algorithm
  • information entropy
  • mutual information
  • nearest neighbor methods

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Cite this

Breaking the Bandwidth Barrier : Geometrical Adaptive Entropy Estimation. / Gao, Weihao; Oh, Sewoong; Viswanath, Pramod.

In: IEEE Transactions on Information Theory, Vol. 64, No. 5, 05.2018, p. 3313-3330.

Research output: Contribution to journalArticle

@article{ac9f7b1e907b495ea3298d8f9a977ee9,
title = "Breaking the Bandwidth Barrier: Geometrical Adaptive Entropy Estimation",
abstract = "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 k -NN distances with a finite k , 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 universal; 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 both the kernel and NN estimators. The corresponding theoretical contribution relating the asymptotic geometry of nearest neighbors to order statistics is of independent mathematical interest.",
keywords = "Information theory, density estimation robust algorithm, information entropy, mutual information, nearest neighbor methods",
author = "Weihao Gao and Sewoong Oh and Pramod Viswanath",
year = "2018",
month = "5",
doi = "10.1109/TIT.2018.2810313",
language = "English (US)",
volume = "64",
pages = "3313--3330",
journal = "IEEE Transactions on Information Theory",
issn = "0018-9448",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "5",

}

TY - JOUR

T1 - Breaking the Bandwidth Barrier

T2 - Geometrical Adaptive Entropy Estimation

AU - Gao, Weihao

AU - Oh, Sewoong

AU - Viswanath, Pramod

PY - 2018/5

Y1 - 2018/5

N2 - 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 k -NN distances with a finite k , 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 universal; 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 both the kernel and NN estimators. The corresponding theoretical contribution relating the asymptotic geometry of nearest neighbors to order statistics is of independent mathematical interest.

AB - 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 k -NN distances with a finite k , 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 universal; 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 both the kernel and NN estimators. The corresponding theoretical contribution relating the asymptotic geometry of nearest neighbors to order statistics is of independent mathematical interest.

KW - Information theory

KW - density estimation robust algorithm

KW - information entropy

KW - mutual information

KW - nearest neighbor methods

UR - http://www.scopus.com/inward/record.url?scp=85043369477&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85043369477&partnerID=8YFLogxK

U2 - 10.1109/TIT.2018.2810313

DO - 10.1109/TIT.2018.2810313

M3 - Article

AN - SCOPUS:85043369477

VL - 64

SP - 3313

EP - 3330

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 5

ER -