A data-driven basis for direct estimation of functionals of distributions

Alan Wisler, Visar Berisha, Andreas Spanias, Alfred O. Hero Iii

Introduction

Calculating density functionals—such as Kullback-Leibler (KL) divergence, Hellinger distance, or the Bayes Error Rate (BER)—is a fundamental task in statistical signal processing and machine learning. Traditional approaches typically rely on parametric assumptions, which fail under model mismatch, or non-parametric "plug-in" estimators that estimate probability density functions (PDFs) before integration. The latter approach is notoriously susceptible to the "curse of dimensionality," where estimation accuracy degrades rapidly as the number of features increases.

This paper introduces a general framework for estimating smooth functionals of two distributions directly from data samples. By bypassing explicit PDF estimation, the proposed method offers a more robust and scalable alternative for high-dimensional data analysis.

The Data-Driven Polynomial Basis

The core innovation of this work is the construction of a "data-driven" polynomial basis using $k$-nearest neighbor ($k$-NN) statistics. The authors demonstrate that the proportion of neighborhoods containing a specific number of points from a given class converges to a Bernstein basis polynomial as the sample size $N$ grows.

Illustration of k-nearest neighbor neighborhoods for different values of k.

As shown in Figure 1, the local neighborhood structure around a sample point $\mathbf{x}^*$ captures essential information about the underlying distributions. By leveraging these $k$-NN counts, any continuous functional can be approximated as a linear combination of these basis functions. This transforms a complex integration problem into a weight-fitting task.

Optimization and Weight Fitting

To determine the optimal weights ($w_r$) for the basis expansion, the authors propose two optimization routines:

  1. Uniform Optimization: This approach assumes the posterior likelihood is uniformly distributed, allowing for pre-calculated weights.
  2. Density-Weighted Optimization: This more advanced method uses the data to estimate the density of the posterior likelihood, focusing accuracy on the most populated regions of the feature space.

To ensure numerical stability and prevent the weights from becoming overly sensitive to noise—a common pitfall in polynomial fitting—the authors incorporate a regularization term into their convex optimization framework.

Key Insights and Results

The most significant theoretical contribution is the realization that $k$-NN neighborhood counts are physical realizations of Bernstein polynomials. This bridge between graph-based statistics and classical approximation theory allows for the creation of estimators that maintain stability in high dimensions.

Empirical evaluations on synthetic datasets, including multivariate Gaussians and non-Gaussian distributions, confirm the method's effectiveness. In divergence estimation tasks, the proposed approach significantly outperformed standard $k$-NN plug-in estimators, which often exhibit high bias.

Mean Squared Error as a function of k for different estimation methods, highlighting the impact of regularization.

As illustrated in Figure 3, the selection of the neighborhood size $k$ involves a trade-off. While larger $k$ values can reduce approximation error, they may increase estimation error in finite samples. The figure also highlights the critical role of regularization; without it, the "Convex" estimator exhibits high instability (large MSE spikes), whereas the regularized version remains stable and competitive with the Bernstein-based approach.

Conclusion

This framework provides a versatile tool for direct functional estimation. By using $k$-NN statistics to build a polynomial basis, it avoids the pitfalls of high-dimensional PDF estimation. While the density-weighted optimization adds computational complexity, the resulting gains in accuracy and the ability to produce tight empirical bounds on quantities like the Bayes Error Rate make it a powerful addition to the statistical toolkit. Future work may explore orthogonal versions of the Bernstein basis to further enhance numerical stability and simplify the optimization process.

Summary updated

BibTeX
@article{wisler2018data,
  author = {Alan Wisler and Visar Berisha and Andreas Spanias and Alfred O. Hero III},
  title = {{A data-driven basis for direct estimation of functionals of distributions}},
  journal = {IEEE Trans. Signal Process.},
  year = {2018},
  doi = {10.1109/tsp.2017.2775587},
}
Figure