Exponential concentration for mutual information estimation with application to forests

Han Liu; John Lafferty; Larry Wasserman

Exponential concentration for mutual information estimation with application to forests

Han Liu, John Lafferty, Larry Wasserman

Operations Research & Financial Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

20 Scopus citations

Abstract

We prove a new exponential concentration inequality for a plug-in estimator of the Shannon mutual information. Previous results on mutual information estimation only bounded expected error. The advantage of having the exponential inequality is that, combined with the union bound, we can guarantee accurate estimators of the mutual information for many pairs of random variables simultaneously. As an application, we show how to use such a result to optimally estimate the density function and graph of a distribution which is Markov to a forest graph.

Original language	English (US)
Title of host publication	Advances in Neural Information Processing Systems 25
Subtitle of host publication	26th Annual Conference on Neural Information Processing Systems 2012, NIPS 2012
Pages	2537-2545
Number of pages	9
State	Published - 2012
Event	26th Annual Conference on Neural Information Processing Systems 2012, NIPS 2012 - Lake Tahoe, NV, United States Duration: Dec 3 2012 → Dec 6 2012

Publication series

Name	Advances in Neural Information Processing Systems
Volume	4
ISSN (Print)	1049-5258

Other

Other	26th Annual Conference on Neural Information Processing Systems 2012, NIPS 2012
Country/Territory	United States
City	Lake Tahoe, NV
Period	12/3/12 → 12/6/12

All Science Journal Classification (ASJC) codes

Computer Networks and Communications
Information Systems
Signal Processing

Cite this

@inproceedings{2fa6bb14e6884b6195dc2bac841e7f3b,

title = "Exponential concentration for mutual information estimation with application to forests",

abstract = "We prove a new exponential concentration inequality for a plug-in estimator of the Shannon mutual information. Previous results on mutual information estimation only bounded expected error. The advantage of having the exponential inequality is that, combined with the union bound, we can guarantee accurate estimators of the mutual information for many pairs of random variables simultaneously. As an application, we show how to use such a result to optimally estimate the density function and graph of a distribution which is Markov to a forest graph.",

author = "Han Liu and John Lafferty and Larry Wasserman",

year = "2012",

language = "English (US)",

isbn = "9781627480031",

series = "Advances in Neural Information Processing Systems",

pages = "2537--2545",

booktitle = "Advances in Neural Information Processing Systems 25",

note = "26th Annual Conference on Neural Information Processing Systems 2012, NIPS 2012 ; Conference date: 03-12-2012 Through 06-12-2012",

}

Liu, H, Lafferty, J & Wasserman, L 2012, Exponential concentration for mutual information estimation with application to forests. in Advances in Neural Information Processing Systems 25: 26th Annual Conference on Neural Information Processing Systems 2012, NIPS 2012. Advances in Neural Information Processing Systems, vol. 4, pp. 2537-2545, 26th Annual Conference on Neural Information Processing Systems 2012, NIPS 2012, Lake Tahoe, NV, United States, 12/3/12.

Exponential concentration for mutual information estimation with application to forests. / Liu, Han; Lafferty, John; Wasserman, Larry.
Advances in Neural Information Processing Systems 25: 26th Annual Conference on Neural Information Processing Systems 2012, NIPS 2012. 2012. p. 2537-2545 (Advances in Neural Information Processing Systems; Vol. 4).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Exponential concentration for mutual information estimation with application to forests

AU - Liu, Han

AU - Lafferty, John

AU - Wasserman, Larry

PY - 2012

Y1 - 2012

N2 - We prove a new exponential concentration inequality for a plug-in estimator of the Shannon mutual information. Previous results on mutual information estimation only bounded expected error. The advantage of having the exponential inequality is that, combined with the union bound, we can guarantee accurate estimators of the mutual information for many pairs of random variables simultaneously. As an application, we show how to use such a result to optimally estimate the density function and graph of a distribution which is Markov to a forest graph.

AB - We prove a new exponential concentration inequality for a plug-in estimator of the Shannon mutual information. Previous results on mutual information estimation only bounded expected error. The advantage of having the exponential inequality is that, combined with the union bound, we can guarantee accurate estimators of the mutual information for many pairs of random variables simultaneously. As an application, we show how to use such a result to optimally estimate the density function and graph of a distribution which is Markov to a forest graph.

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

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

M3 - Conference contribution

AN - SCOPUS:84877734502

SN - 9781627480031

T3 - Advances in Neural Information Processing Systems

SP - 2537

EP - 2545

BT - Advances in Neural Information Processing Systems 25

T2 - 26th Annual Conference on Neural Information Processing Systems 2012, NIPS 2012

Y2 - 3 December 2012 through 6 December 2012

ER -

Exponential concentration for mutual information estimation with application to forests

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this