Sorry, you need to enable JavaScript to visit this website.

facebooktwittermailshare

Scalable Mutual Information Estimation using Dependence Graphs

Abstract: 

The Mutual Information (MI) is an often used measure of dependency between two random variables utilized in informa- tion theory, statistics and machine learning. Recently several MI estimators have been proposed that can achieve paramet- ric MSE convergence rate. However, most of the previously proposed estimators have high computational complexity of at least O(N2). We propose a unified method for empirical non-parametric estimation of general MI function between random vectors in Rd based on N i.i.d. samples. The re- duced complexity MI estimator, called the ensemble depen- dency graph estimator (EDGE), combines randomized locality sensitive hashing (LSH), dependency graphs, and ensemble bias-reduction methods. We prove that EDGE achieves op- timal computational complexity O(N), and can achieve the optimal parametric MSE rate of O(1/N) if the density is d times differentiable. To the best of our knowledge EDGE is the first non-parametric MI estimator that can achieve paramet- ric MSE rates with linear time complexity. We illustrate the utility of EDGE for the analysis of the information plane (IP) in deep learning. Using EDGE we shed light on a controversy on whether or not the compression property of information bottleneck (IB) in fact holds for ReLu and other rectification functions in deep neural networks (DNN).

up
0 users have voted:

Paper Details

Authors:
Morteza Noshad, Yu Zeng, Alfred Hero
Submitted On:
8 May 2019 - 12:23pm
Short Link:
Type:
Presentation Slides
Event:
Presenter's Name:
Alfred Hero
Paper Code:
3844
Document Year:
2019
Cite

Document Files

Estimation, Mutual Information, Information Bottleneck, Deep Learning

(9)

Subscribe

[1] Morteza Noshad, Yu Zeng, Alfred Hero, "Scalable Mutual Information Estimation using Dependence Graphs", IEEE SigPort, 2019. [Online]. Available: http://sigport.org/4122. Accessed: Jul. 22, 2019.
@article{4122-19,
url = {http://sigport.org/4122},
author = {Morteza Noshad; Yu Zeng; Alfred Hero },
publisher = {IEEE SigPort},
title = {Scalable Mutual Information Estimation using Dependence Graphs},
year = {2019} }
TY - EJOUR
T1 - Scalable Mutual Information Estimation using Dependence Graphs
AU - Morteza Noshad; Yu Zeng; Alfred Hero
PY - 2019
PB - IEEE SigPort
UR - http://sigport.org/4122
ER -
Morteza Noshad, Yu Zeng, Alfred Hero. (2019). Scalable Mutual Information Estimation using Dependence Graphs. IEEE SigPort. http://sigport.org/4122
Morteza Noshad, Yu Zeng, Alfred Hero, 2019. Scalable Mutual Information Estimation using Dependence Graphs. Available at: http://sigport.org/4122.
Morteza Noshad, Yu Zeng, Alfred Hero. (2019). "Scalable Mutual Information Estimation using Dependence Graphs." Web.
1. Morteza Noshad, Yu Zeng, Alfred Hero. Scalable Mutual Information Estimation using Dependence Graphs [Internet]. IEEE SigPort; 2019. Available from : http://sigport.org/4122