Abstract
This paper introduces a novel suite of non-parametric estimators designed to calculate Shannon information content, entropy, and KL divergence for datasets where observations are associated with weights. By transitioning from traditional $k$-nearest neighbor counts to a "quantile-based" approach, the authors provide robust tools for high-dimensional data analysis, distribution-preserving compression, and ensemble learning. These estimators, particularly the Mean Quantile Information Estimator (MQIE), offer improved stability and parameter-free operation compared to existing methods.
Introduction
In information theory, the Shannon information content ($-\log f(x)$) is a fundamental metric used to describe the "surprise" of a data point relative to a probability distribution. While standard tools like Kernel Density Estimation (KDE) and $k$-Nearest Neighbors ($k$-NN) are widely used to estimate this from raw data, they typically assume that every observation is equally significant.
However, real-world data is frequently weighted to correct for selection bias, represent model importance in ensembles, or summarize large datasets into compressed versions. Standard $k$-NN lacks a trivial mechanism to incorporate these weights. This research fills that gap by redefining information estimation through the lens of cumulative weight quantiles.
Methodology: From Counts to Quantiles
The authors propose three primary estimators that move beyond discrete neighbor counts:
- Quantile Information Estimator (QIE): Instead of identifying the $k$-th nearest neighbor, this estimator identifies the point where the cumulative sum of weights reaches a threshold $\alpha$. This allows the estimator to naturally handle varying weights within the geometry of the data space.
- Fixed Radius Quantile Information Estimator (RQIE): To optimize computational costs, this version uses a fixed radius $R$ and sums the weights of all points within that ball, effectively acting as a weighted version of a hard-window KDE.
- Mean Quantile Information Estimator (MQIE): The most sophisticated contribution, MQIE marginalizes over all possible values of $\alpha$. This creates a parameter-free estimator that is significantly more stable and exhibits lower variance than the basic QIE.
Experimental Validation
The researchers validated these methods using a combination of synthetic and real-world benchmarks:
- Artificial Data: 1D and 20D Gaussian distributions were used to test bias and variance in high-dimensional spaces.
- Classification (IDA Datasets): 13 standard datasets (e.g., Banana, Titanic) were used to test distribution-preserving data compression.
- Regression Tasks: Real-world sets like Boston Housing and Airquality were used to evaluate weighted ensemble learning.
Key Insights and Results
The core "aha moment" of the paper is that while "the 5th neighbor" is a discrete count that ignores weights, "the point at the 5% weight quantile" is a continuous concept that integrates importance weights seamlessly.
Stability and Performance
In high-dimensional spaces (e.g., 20D Gaussian tests), the QIE and MQIE significantly outperformed traditional KDE. KDE often struggles with bandwidth selection as dimensions increase, whereas quantile-based methods adapt more gracefully to local data structures. Furthermore, the MQIE showed the lowest standard deviation among all tested estimators, making it highly reliable for optimization tasks.
Practical Applications
The authors demonstrated the utility of these estimators in two key areas:
- Data Compression: By using the KL divergence estimator to optimize weights for "codebook vectors," the authors improved $k$-NN classification accuracy across most IDA datasets compared to simple frequency-based weighting.
- Ensemble Regression: By optimizing the weights of a "Bagging" ensemble to minimize average information content, the authors significantly reduced prediction variance, leading to more reliable models.
Limitations and Future Directions
While the MQIE is highly stable, it introduces a consistent bias because it averages over all $\alpha \in [0, 1]$, including large values where the assumption of "local" density may fail. Future work may involve using a non-uniform weight function $w(\alpha)$ within the MQIE to prioritize smaller, more local quantiles to reduce this bias. Additionally, the authors suggest applying these estimators to change-point detection in time series, where weighting recent events more heavily is crucial.
Summary updated