Efficient Estimation of Mutual Information for Strongly Dependent Variables

2014/11/07 by Shuyang Gao, Gao, Shuyang, Greg Ver Steeg +3 · 16 citations
Computer Science · Physics and Astronomy · #Bayesian Methods and Mixture Models #Bayesian Modeling and Causal Inference #Complex Network Analysis Techniques #Data Analysis #FOS: Computer and information sciences #FOS: Physical sciences #Information Theory (cs.IT) #Machine Learning (stat.ML) #Statistics and Probability (physics.data-an)

paper · pdf · doi:10.48550/arxiv.1411.2003

openalex publication_date 2014/11/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We demonstrate that a popular class of nonparametric mutual information (MI) estimators based on k-nearest-neighbor graphs requires number of samples that scales exponentially with the true MI. Consequently, accurate estimation of MI between two strongly dependent variables is possible only for prohibitively large sample size. This important yet overlooked shortcoming of the existing estimators is due to their implicit reliance on local uniformity of the underlying joint distribution. We introduce a new estimator that is robust to local non-uniformity, works well with limited data, and is able to capture relationship strengths over many orders of magnitude. We demonstrate the superior performance of the proposed estimator on both synthetic and real-world data.

Cited by

• Nonparametric Estimation of Joint Entropy via Partitioned Sample-Spacing
• Analysis of k-Nearest Neighbor Distances with Application to Entropy Estimation
• Understanding Convolutional Neural Networks with Information Theory: An Initial Exploration
• TELL-TALE: Task Efficient LLMs with Task Aware Layer Elimination
• Measuring Data Quality for Project Lighthouse
• MMG: Mutual Information Estimation via the MMSE Gap in Diffusion
• NMINE: Normalized Mutual Information Neural Estimation
• Mutual Information Gradient Estimation for Representation Learning
• Formal Limitations on the Measurement of Mutual Information
• Model-Augmented Estimation of Conditional Mutual Information for Feature Selection
• ML-PWS: Estimating the Mutual Information Between Experimental Time Series Using Neural Networks
• DEMI: Discriminative Estimator of Mutual Information
• Nonparanormal Information Estimation
• Ensemble Estimation of Distributional Functionals via k-Nearest Neighbors
• Understanding the Limitations of Variational Mutual Information Estimators
• Modeling Psychotherapy Dialogues with Kernelized Hashcode Representations: A Nonparametric Information-Theoretic Approach

Related

• Estimating Mutual Information by Local Gaussian Approximation
• A Bayesian Nonparametric Estimation of Mutual Information
• Scalable Mutual Information Estimation using Dependence Graphs
• Beyond Normal: On the Evaluation of Mutual Information Estimators
• Nonparanormal Information Estimation