Demystifying Fixed κ-Nearest Neighbor Information Estimators

Weihao Gao, Sewoong Oh, Pramod Viswanath

Research output: Contribution to journalArticle

Abstract

Estimating mutual information from independent identically distributed samples drawn from an unknown joint density function is a basic statistical problem of broad interest with multitudinous applications. The most popular estimator is the one proposed by Kraskov, Stögbauer, and Grassberger (KSG) in 2004 and is nonparametric and based on the distances of each sample to its kth nearest neighboring sample, where k is a fixed small integer. Despite of its widespread use (part of scientific software packages), theoretical properties of this estimator have been largely unexplored. In this paper, we demonstrate that the estimator is consistent and also identify an upper bound on the rate of convergence of the ℓ2 error as a function of a number of samples. We argue that the performance benefits of the KSG estimator stems from a curious 'correlation boosting' effect and build on this intuition to modify the KSG estimator in novel ways to construct a superior estimator. As a by-product of our investigations, we obtain nearly tight rates of convergence of the ℓ2 error of the well-known fixed k -nearest neighbor estimator of differential entropy by Kozachenko and Leonenko.

Original languageEnglish (US)
Pages (from-to)5629-5661
Number of pages33
JournalIEEE Transactions on Information Theory
Volume64
Issue number8
DOIs
StatePublished - Aug 2018

Fingerprint

Software packages
Probability density function
Byproducts
Entropy
intuition
entropy
performance
software

Keywords

  • Information theory
  • information entropy
  • mutual information
  • nearest neighbor methods

ASJC Scopus subject areas

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

Cite this

Demystifying Fixed κ-Nearest Neighbor Information Estimators. / Gao, Weihao; Oh, Sewoong; Viswanath, Pramod.

In: IEEE Transactions on Information Theory, Vol. 64, No. 8, 08.2018, p. 5629-5661.

Research output: Contribution to journalArticle

@article{f1665b6d92a34c4c8d4c79fb645ade60,
title = "Demystifying Fixed κ-Nearest Neighbor Information Estimators",
abstract = "Estimating mutual information from independent identically distributed samples drawn from an unknown joint density function is a basic statistical problem of broad interest with multitudinous applications. The most popular estimator is the one proposed by Kraskov, St{\"o}gbauer, and Grassberger (KSG) in 2004 and is nonparametric and based on the distances of each sample to its kth nearest neighboring sample, where k is a fixed small integer. Despite of its widespread use (part of scientific software packages), theoretical properties of this estimator have been largely unexplored. In this paper, we demonstrate that the estimator is consistent and also identify an upper bound on the rate of convergence of the ℓ2 error as a function of a number of samples. We argue that the performance benefits of the KSG estimator stems from a curious 'correlation boosting' effect and build on this intuition to modify the KSG estimator in novel ways to construct a superior estimator. As a by-product of our investigations, we obtain nearly tight rates of convergence of the ℓ2 error of the well-known fixed k -nearest neighbor estimator of differential entropy by Kozachenko and Leonenko.",
keywords = "Information theory, information entropy, mutual information, nearest neighbor methods",
author = "Weihao Gao and Sewoong Oh and Pramod Viswanath",
year = "2018",
month = "8",
doi = "10.1109/TIT.2018.2807481",
language = "English (US)",
volume = "64",
pages = "5629--5661",
journal = "IEEE Transactions on Information Theory",
issn = "0018-9448",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "8",

}

TY - JOUR

T1 - Demystifying Fixed κ-Nearest Neighbor Information Estimators

AU - Gao, Weihao

AU - Oh, Sewoong

AU - Viswanath, Pramod

PY - 2018/8

Y1 - 2018/8

N2 - Estimating mutual information from independent identically distributed samples drawn from an unknown joint density function is a basic statistical problem of broad interest with multitudinous applications. The most popular estimator is the one proposed by Kraskov, Stögbauer, and Grassberger (KSG) in 2004 and is nonparametric and based on the distances of each sample to its kth nearest neighboring sample, where k is a fixed small integer. Despite of its widespread use (part of scientific software packages), theoretical properties of this estimator have been largely unexplored. In this paper, we demonstrate that the estimator is consistent and also identify an upper bound on the rate of convergence of the ℓ2 error as a function of a number of samples. We argue that the performance benefits of the KSG estimator stems from a curious 'correlation boosting' effect and build on this intuition to modify the KSG estimator in novel ways to construct a superior estimator. As a by-product of our investigations, we obtain nearly tight rates of convergence of the ℓ2 error of the well-known fixed k -nearest neighbor estimator of differential entropy by Kozachenko and Leonenko.

AB - Estimating mutual information from independent identically distributed samples drawn from an unknown joint density function is a basic statistical problem of broad interest with multitudinous applications. The most popular estimator is the one proposed by Kraskov, Stögbauer, and Grassberger (KSG) in 2004 and is nonparametric and based on the distances of each sample to its kth nearest neighboring sample, where k is a fixed small integer. Despite of its widespread use (part of scientific software packages), theoretical properties of this estimator have been largely unexplored. In this paper, we demonstrate that the estimator is consistent and also identify an upper bound on the rate of convergence of the ℓ2 error as a function of a number of samples. We argue that the performance benefits of the KSG estimator stems from a curious 'correlation boosting' effect and build on this intuition to modify the KSG estimator in novel ways to construct a superior estimator. As a by-product of our investigations, we obtain nearly tight rates of convergence of the ℓ2 error of the well-known fixed k -nearest neighbor estimator of differential entropy by Kozachenko and Leonenko.

KW - Information theory

KW - information entropy

KW - mutual information

KW - nearest neighbor methods

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

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

U2 - 10.1109/TIT.2018.2807481

DO - 10.1109/TIT.2018.2807481

M3 - Article

AN - SCOPUS:85042198807

VL - 64

SP - 5629

EP - 5661

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 8

ER -