Introduction
Estimating entropy and mutual information (MI) from finite samples is a cornerstone of modern data science, underpinning tasks from feature selection to representation learning. However, traditional estimators often struggle with the "bandwidth barrier." Non-parametric $k$-nearest neighbor ($k$-NN) methods, while adaptive to local density, suffer from significant bias when data resides on low-dimensional manifolds or near boundaries. Conversely, Kernel Density Estimation (KDE) requires a delicate balance in choosing a global bandwidth; too large a bandwidth oversmooths the density, while too small a bandwidth introduces excessive noise.
This paper introduces the $k$-LNN estimator, a novel framework that "breaks" this barrier by combining the local adaptivity of $k$-NN with the structural modeling of local likelihood density estimation. By mathematically accounting for the resulting bias, the authors provide a simple correction method that significantly outperforms state-of-the-art estimators.
Methods: Local Likelihood and Universal Bias
The $k$-LNN estimator leverages Local Likelihood Density Estimation (LLDE). Instead of simple point counting, it fits a local polynomial of degree $p$ to the log-density of the data within a neighborhood defined by the $k$-th nearest neighbor.
Key innovations include:
- Closed-form Solutions: For $p \leq 2$, the authors derive efficient, closed-form expressions using Gaussian kernels, avoiding the need for iterative numerical optimization.
- Universal Bias Correction: A major theoretical contribution is the proof that for a fixed $k$, the asymptotic bias of the local estimator depends only on $k$ and the dimension $d$, and is independent of the underlying data distribution. This allows for a simple, precomputed bias-correction constant ($B_{k,d}$).
- Geometric Adaptation: By using a quadratic fit ($p=2$), the estimator accounts for local curvature and orientation, effectively correcting for the "boundary bias" that plagues standard $k$-NN methods.
Experimental Evaluation
The performance of the $k$-LNN estimator was rigorously tested against synthetic datasets where ground truth entropy and MI are known, including jointly Gaussian variables with varying correlations, mixtures of Gaussians, and high-dimensional manifolds.
Key Results
- Robustness to Correlation: As variables become highly correlated ($r \to 1$), data collapses toward lower-dimensional structures. While traditional estimators like Kozachenko-Leonenko (KL) see errors spike by orders of magnitude, the $p=2$ $k$-LNN estimator remains stable and accurate.
- Sample Efficiency: The proposed method demonstrates superior convergence rates. In high-dimensional tests, it reaches lower error levels with significantly fewer samples than traditional KDE or $k$-NN approaches.
- Superior Accuracy: Across diverse multi-modal and non-linear distributions, the degree-2 $k$-LNN estimator consistently achieved lower Mean Squared Error (MSE) than state-of-the-art baselines.
Conclusion and Future Work
The $k$-LNN estimator provides a powerful, computationally efficient tool for information-theoretic estimation. By mathematically accounting for the bias introduced by local bandwidths, it bridges the gap between geometric and kernel-based methods.
While highly effective, future research could further explore optimal selection strategies for $k$ and provide a formal theoretical treatment of convergence rates on embedded manifolds. Despite the increased local computation required for quadratic fitting, the gains in accuracy and sample efficiency make $k$-LNN a compelling choice for high-dimensional data analysis.
Summary updated