Information estimators for weighted observations

Hideitsu Hino, Noboru Murata

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:

  1. 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.
  2. 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.
  3. 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.
Illustration of the quantile-based approach where weights of neighboring points are summed to reach a threshold.

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.
Application of weighted estimators to ensemble regression, showing the fit of multiple models to data points.

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

Abstract

The Shannon information content is a valuable numerical characteristic of probability distributions. The problem of estimating the information content from an observed dataset is very important in the fields of statistics, information theory, and machine learning. The contribution of the present paper is in proposing information estimators, and showing some of their applications. When the given data are associated with weights, each datum contributes differently to the empirical average of statistics. The proposed estimators can deal with this kind of weighted data. Similar to other conventional methods, the proposed information estimator contains a parameter to be tuned, and is computationally expensive. To overcome these problems, the proposed estimator is further modified so that it is more computationally efficient and has no tuning parameter. The proposed methods are also extended so as to estimate the cross-entropy, entropy, and Kullback–Leibler divergence. Simple numerical experiments show that the information estimators work properly. Then, the estimators are applied to two specific problems, distribution-preserving data compression, and weight optimization for ensemble regression.
BibTeX
@article{hino2013information,
  author = {Hideitsu Hino and Noboru Murata},
  title = {{Information estimators for weighted observations}},
  journal = {Neural Networks},
  year = {2013},
  doi = {10.1016/j.neunet.2013.06.005},
}
Figure