Empirical estimation of entropy functionals with confidence

Kumar Sricharan, Raviv Raich, Alfred O. HeroarXiv 2010 · DOI · arXiv

Abstract

This paper introduces a class of k-nearest neighbor ($k$-NN) estimators called bipartite plug-in (BPI) estimators for estimating integrals of non-linear functions of a probability density, such as Shannon entropy and Rényi entropy. The density is assumed to be smooth, have bounded support, and be uniformly bounded from below on this set. Unlike previous $k$-NN estimators of non-linear density functionals, the proposed estimator uses data-splitting and boundary correction to achieve lower mean square error. Specifically, we assume that $T$ i.i.d. samples ${X}_i \in \mathbb{R}^d$ from the density are split into two pieces of cardinality $M$ and $N$ respectively, with $M$ samples used for computing a k-nearest-neighbor density estimate and the remaining $N$ samples used for empirical estimation of the integral of the density functional. By studying the statistical properties of k-NN balls, explicit rates for the bias and variance of the BPI estimator are derived in terms of the sample size, the dimension of the samples and the underlying probability distribution. Based on these results, it is possible to specify optimal choice of tuning parameters $M/T$, $k$ for maximizing the rate of decrease of the mean square error (MSE). The resultant optimized BPI estimator converges faster and achieves lower mean squared error than previous $k$-NN entropy estimators. In addition, a central limit theorem is established for the BPI estimator that allows us to specify tight asymptotic confidence intervals.

Introduction

Estimating entropy—the measure of uncertainty or information content in a dataset—is a cornerstone of machine learning, signal processing, and statistics. However, accurate estimation for high-dimensional, multivariate data is notoriously difficult. Standard approaches often rely on $k$-nearest neighbor ($k$-NN) density estimates, which suffer from significant bias near the boundaries of the data's support. Furthermore, most existing estimators lack a proven Central Limit Theorem (CLT), making it impossible to construct reliable confidence intervals for the estimates.

This paper introduces the Bipartite Plug-In (BPI) estimator, a novel framework for estimating non-linear density functionals like Shannon and Rényi entropy. By employing a data-splitting strategy and an adaptive boundary correction mechanism, the BPI estimator achieves faster convergence rates and provides the theoretical foundation for asymptotic confidence intervals.

Methodology

The core innovation of the BPI framework lies in its two-stage approach designed to minimize bias and simplify statistical analysis.

Data Splitting

The total available samples ($T$) are partitioned into two independent sets of size $M$ and $N$. The first set ($M$) is used to construct the $k$-NN density estimates, while the second set ($N$) serves as the "plug-in" points for empirical integration. This bipartite structure decouples the statistical dependencies inherent in standard $k$-NN estimators, facilitating the derivation of a Central Limit Theorem.

Adaptive Boundary Correction

$k$-NN density estimates are typically biased near the edges of a dataset's support because the neighborhood balls are truncated by the boundary. The BPI estimator addresses this by identifying boundary points and applying a correction.

Identification of boundary points and pairs in a 2D sample set.

As shown in Figure 1, the algorithm identifies boundary points based on the local geometry of $k$-NN distances. For these points, the estimator performs a correction by extrapolating density information from nearby interior neighbors.

Bipartite data splitting and boundary neighborhood correction.

Figure 2 illustrates the bipartite split and the resulting neighborhood corrections. The "corrected boundary neighborhoods" (black circles) adjust for the truncation seen in the "original k-NN boundary neighborhoods" (red circles), effectively reducing bias without requiring prior knowledge of the boundary's shape.

Results

The authors validated the BPI estimator through both theoretical analysis and empirical simulations using synthetic distributions (e.g., 2D Beta distributions) and real-world network data.

Faster Convergence and Lower Error

The BPI estimator achieves a Mean Squared Error (MSE) convergence rate of $O(((log T)^6/T)^{4/d})$, which is significantly faster than the $O(T^{-2/d})$ rate observed in previous $k$-NN estimators. In head-to-head comparisons against established methods like the Leonenko and Baryshnikov estimators, the BPI method consistently demonstrated lower MSE across various sample sizes and distributions.

Confidence Intervals and Anomaly Detection

By establishing a CLT, the authors successfully constructed 95% coverage intervals that closely match empirical results, typically within 12%. This capability was applied to real-world Abilene network traffic data for anomaly detection. By tracking changes in the intrinsic dimension of the traffic via entropy estimation, the BPI estimator effectively identified unusual activity peaks corresponding to network anomalies.

Conclusion

The Bipartite Plug-In estimator represents a significant advancement in information-theoretic estimation. By solving the boundary bias problem and providing a path to rigorous confidence intervals, it offers a more robust tool for high-dimensional data analysis. Future work may extend this framework to other measures such as $f$-divergence and mutual information.

Summary updated

Abstract

This paper introduces a class of k-nearest neighbor ($k$-NN) estimators called bipartite plug-in (BPI) estimators for estimating integrals of non-linear functions of a probability density, such as Shannon entropy and Rényi entropy. The density is assumed to be smooth, have bounded support, and be uniformly bounded from below on this set. Unlike previous $k$-NN estimators of non-linear density functionals, the proposed estimator uses data-splitting and boundary correction to achieve lower mean square error. Specifically, we assume that $T$ i.i.d. samples ${X}_i \in \mathbb{R}^d$ from the density are split into two pieces of cardinality $M$ and $N$ respectively, with $M$ samples used for computing a k-nearest-neighbor density estimate and the remaining $N$ samples used for empirical estimation of the integral of the density functional. By studying the statistical properties of k-NN balls, explicit rates for the bias and variance of the BPI estimator are derived in terms of the sample size, the dimension of the samples and the underlying probability distribution. Based on these results, it is possible to specify optimal choice of tuning parameters $M/T$, $k$ for maximizing the rate of decrease of the mean square error (MSE). The resultant optimized BPI estimator converges faster and achieves lower mean squared error than previous $k$-NN entropy estimators. In addition, a central limit theorem is established for the BPI estimator that allows us to specify tight asymptotic confidence intervals.
BibTeX
@misc{sricharan2010empirical,
  author = {Kumar Sricharan and Raviv Raich and Alfred O. Hero},
  title = {{Empirical estimation of entropy functionals with confidence}},
  year = {2010},
  eprint = {1012.4188},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1012.4188},
}
Figure