Source-linked AI summary
Efficient Estimation of Mutual Information for Strongly Dependent Variables
Shuyang Gao, Greg Ver Steeg, Aram Galstyan
TL;DR
The paper addresses the difficulty of accurately estimating mutual information for strongly dependent variables with limited samples. It analyzes kNN-based estimators, attributes their failure to local-uniformity assumptions, and introduces a correction for local non-uniformity. The proposed estimator captures strong relationships with fewer samples and outperforms existing techniques on synthetic and real-world data.
Problem
Existing mutual-information estimators can require prohibitively many samples for strong dependence because accurate estimation is difficult with limited data.
Method
The paper introduces a nonparametric kNN mutual-information estimator that corrects for local non-uniformity in the joint distribution.
Results
The proposed estimator accurately measures strong relationships with significantly fewer samples and outperforms existing techniques on synthetic and real-world data.
Takeaways & Limitations
The estimator supports identifying and measuring strong nonlinear relationships when sample sizes are small.
Takeaways & Limitations
The analysis assumes absolutely continuous distributions, and strong dependence can make kNN-based estimation sample-intensive because local uniformity may fail.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper identifies a severe sample-complexity flaw in popular kNN-based mutual-information estimators and proposes a correction for local non-uniformity. Empirical results indicate that the new estimator measures strong relationships accurately with fewer samples.
- kNN-based estimators require exponentially many samples in the true mutual information for accurate estimation.This makes strong relationships harder to measure than weak dependence or independence.
- The flaw arises because existing estimators implicitly assume local uniformity, which can fail for sufficiently strong, nearly deterministic dependencies.
- The proposed kNN estimator relaxes local uniformity by introducing a correction term for local non-uniformity.
- For strong relationships, the proposed estimator accurately estimates mutual information with significantly fewer samples.
- Synthetic and real-world experiments show that the method outperforms existing techniques and accurately measures strong relationships using smaller sample sizes.
2 kNN-based Estimation of Entropic Measures
This section develops nonparametric mutual-information estimators from k-nearest-neighbor entropy estimates, including the KSG variant. The estimators use local neighborhoods in joint and marginal spaces, with neighborhood size controlled by k.
- Entropy Estimation: The naive kNN entropy estimator uses distances to the kth nearest neighbor and a digamma-function correction.
- Entropy Estimation: Under absolute continuity and positive integer k, the kNN entropy estimator is asymptotically unbiased.
- From Entropy to Mutual Information: The paper constructs mutual-information estimators from entropy estimators using the mutual-information identity.
- KSG Estimator: The KSG estimator matches marginal neighborhood length-scales to the joint-space k-nearest-neighbor distance and uses max-norm distance.
- KSG Estimator: The neighborhood parameter k trades local accuracy against estimator variance: smaller k may improve accuracy, whereas larger k reduces variance.
- KSG Estimator: KSG forms a max-norm rectangle around each point, then uses marginal point counts nxj instead of k for marginal entropy estimates.
- KSG Estimator: The presentation assumes absolutely continuous densities; technical concerns for this assumption are noted in related work.
- KSG Estimator: The max-norm rectangle is illustrated for k = 3 under a uniform distribution and k = 4 under a strongly correlated distribution.
3 Limitations of kNN-based MI Estimators
The paper shows that kNN-based mutual-information estimators can require exponentially many samples as true mutual information increases. This limitation arises because their local-uniformity approximation breaks down for strong dependencies.
- Theoretical limitation: For fixed dimensionality, accurate kNN-based MI estimation requires a sample size that increases exponentially with the true mutual information.Theorem 2 establishes this for the naive kNN estimator, and Theorem 3 establishes it for KSG.
- Practical implication: Strong relationships are harder to measure accurately than weak relationships with these estimators.The restriction is especially problematic when the goal is to find strong signals rather than merely distinguish independence.
- Practical implication: As a relationship approaches a functional dependence, mutual information and the required sample size both diverge.For X ∼ U(0, 1) and Y = X + ηU(0, 1), both quantities grow without bound as η approaches zero.
- Empirical comparison: Theoretical sample-size bounds are conservative but exhibit the same exponential growth rate as empirical lower bounds.Figure 2 compares the empirical lower bound with the theoretical bound from Theorem 3.
- Mechanism: The failure is attributed to approximating density as uniform inside each local kNN ball or KSG max-norm rectangle.Strong dependencies make the joint density more singular, violating this local-uniformity assumption.
4 Improved kNN-based Estimators
The paper proposes Local Nonuniformity Correction, a kNN-based approach that relaxes local uniformity by estimating a smaller local volume around each point. It is intended to improve MI estimation for strong relationships while retaining KSG when correction is unnecessary.
- Local Nonuniformity Correction: Local Nonuniformity Correction relaxes the local-uniformity assumption underlying kNN-based MI estimators.The method introduces a correction based on a subset of the neighborhood where density is treated as constant.
- Correction principle: The proposed correction improves estimates when density is highly non-uniform in a point’s k-nearest-neighbor region.The paper identifies strongly related variables as a setting where this condition occurs.
- KSG implementation: The concrete KSG modification uses localized PCA to find a smaller rotated rectangle covering each neighborhood.Its volume is used to estimate the locally occupied region rather than assuming the full axis-aligned max-norm rectangle is uniform.
- Limitation: The procedure can overcorrect genuinely uniform neighborhoods because PCA-aligned points may occupy a smaller sub-volume by chance.This creates an artificially large non-uniformity correction.
- Adaptive correction: A threshold α_k,d determines whether the local correction is applied or discarded for each point.When α_k,d is sufficiently small, the estimator reduces to the KSG estimator.
5 Experiments
Experiments on synthetic functional relationships and WHO data show that LNC generally estimates strong and synergistic dependencies more effectively than existing estimators, particularly with limited samples.
- 5.1 Experiments with synthetic data: LNC consistently outperforms KSG, GNN, MST, and EXP on synthetic functional relationships, especially at low noise.KSG and GNN become bounded by sample size in the low-noise regime, while LNC continues growing; MST overestimates MI at high noise, and EXP fails on most nonlinear relationships.
- 5.1 Experiments with synthetic data: Several orders of magnitude fewer samples are required for LNC than KSG on linear relationships in 2D and 5D and quadratic relationships in 2D.For the 5D linear relationship, KSG does not converge even at sample size 10^5, whereas LNC converges.
- 5.1 Experiments with synthetic data: LNC still converges faster than KSG for the 5D quadratic relationship, although its convergence is relatively slow.The slower convergence reflects LNC’s remaining assumption of local linearity, which requires more samples as nonlinearity increases.
- 5.2.2 Finding interesting triplets: On WHO data, LNC identifies synergistic triplets that KSG does not, with relatively high multi-information despite low pairwise mutual information.The analysis ranks triplets using SS = I(X : Y : Z)/max {I(X : Y), I(Y : Z), I(Z : X)} and selects those above a threshold.
- 5.2.2 Finding interesting triplets: One detected WHO relationship links population-related energy and electricity indicators to female cervical cancer cases through a synergistic relationship.The ratio of Total Energy Generation to Electricity Generation per Person essentially yields population size, which predicts the Number of Female Cervical Cancer cases.
- 5.2.2 Finding interesting triplets: A second WHO example associates cell-phone prevalence, female cervical cancer cases, and tuberculosis death rates through a strong synergistic interaction.The passage offers overall economic development and mobile technology in tuberculosis control as possible explanations for the observed association.
6 Related Work
Prior work compared MI estimators across sample sizes and noise levels, addressed boundary bias, and debated MI’s equitability relative to MIC.
- Khan et al. found KSG best for small samples and relatively low noise, while KDE performed better at higher noise intensities.
- Boundary-aware density estimators compensate kNN underestimation near support boundaries by extrapolating estimates from nearby interior points.
- Kinney and Atwal argued that MI is more equitable than MIC and linked MIC’s apparent superiority to flaws in MI estimation.
7 Conclusion
The conclusion frames MI as a general way to compare otherwise dissimilar relationships while emphasizing the sample burden of existing estimators. The proposed nonparametric estimator measures nonlinear relationship strength with small samples, supporting broader relationship discovery as data grows.
- Strong relationships require exponentially many samples for accurate estimation with some existing nonparametric MI techniques.
- MI provides a general basis for comparing the strength of otherwise dissimilar variables and relationships.
- The paper introduces a nonparametric MI estimator that measures nonlinear relationship strength even with small sample sizes.
A Proof of Theorem 2
The proof compares k-nearest-neighbor distances in the joint space with distances after projection into subdimensions, then derives an upper bound involving dimensional terms and a constant.
- For any sample point and subdimension, the joint-space k-nearest-neighbor distance is at least as large as the corresponding projected distance.
- The distance comparison is used to derive an upper bound for the naive kNN mutual information estimator.
- The resulting bound includes an O(d log d) term and a constant whose scaling is specified in the proof.
B Derivation of Eq. 17
The derivation starts from the naive kNN or KSG estimator, identifies the probability masses and neighborhood volumes it uses, and replaces the joint-space volume with a locally corrected volume.
- The naive kNN and KSG mutual information estimators are expressed through neighborhood-based quantities around each sample point.
- The estimator uses joint-space and projected-subspace neighborhood volumes together with their associated probability masses.
- Local nonuniform correction replaces the joint-space neighborhood volume with a corrected volume in the estimator.
- The derivation applies the monotonic decrease of ψ(k)−log(k) to obtain the final inequality.
C Empirical Evaluation for αk,d
The procedure empirically calibrates αk,d by comparing local-volume ratios under simulated uniform distributions. The resulting analysis shows how the threshold varies with k and dimension, while the broader tests evaluate estimators across noisy functional relationships.
- Threshold criterion: The threshold αk,d accepts local uniformity when the observed volume ratio V̄/V exceeds the empirically calibrated cutoff.Under uniformity, the cutoff is chosen so that rejecting the hypothesis occurs with small probability ε.
- Threshold trade-off: The threshold trades off false local-non-uniformity detections against statistical power for medium-strength relationships.A high α can overestimate mutual information, whereas a low α can reduce power for medium-strength relationships.
- Calibration procedure: The calibration samples k points from random uniform distributions on d-dimensional hyperrectangles and computes the enclosing volume after PCA rotation.The simulated distribution has volume V, while the enclosing rectilinear volume is denoted V̄.
- Empirical behavior: αk,d increases with k for fixed dimension, requiring V̄ to be closer to V before accepting local uniformity.This reflects the empirical distribution of V̄/V under uniform sampling.
- Empirical behavior: αk,d decreases as dimension d increases for fixed k, while V̄ becomes much smaller than V under uniform sampling.The result indicates stronger finite-sample volume shrinkage in higher dimensions.
- Estimator evaluation: The broader evaluation tests twenty-one functional relationships with varying noise intensities using 5,000 data points per relationship.The complete comparisons include LNC, KSG, GNN, MST, and EXP estimators; k is set to 5 for KSG, GNN, and LNC.