Direct Estimation of Density Functionals Using a Polynomial Basis

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

Abstract

Estimating information-theoretic quantities like Kullback-Leibler (KL) divergence or Bayes error bounds is a fundamental challenge in signal processing and machine learning. Traditional methods often rely on error-prone probability density estimation or restrictive parametric assumptions. This paper introduces a general framework for the direct estimation of density functionals by decomposing them into a data-driven polynomial basis derived from $k$-nearest neighbor ($k$-NN) graphs. We demonstrate that the local composition of $k$-NN neighborhoods converges to Bernstein basis polynomials as sample sizes increase. By employing convex optimization with regularization, the proposed estimator achieves high accuracy in high-dimensional spaces and robustness against non-Gaussian distributions, significantly outperforming traditional plug-in and parametric methods.

Introduction

In many machine learning applications, we require precise estimates of density functionals—quantities that depend on the underlying probability distributions of data. Examples include the Bayes Error Rate (BER), which defines the theoretical limit of classification performance, and various divergence measures.

Historically, two main approaches have dominated this space. Parametric methods assume a specific model (e.g., Gaussian), leading to significant bias if the model is misspecified. Conversely, non-parametric "plug-in" methods estimate probability density functions (PDFs) first and then integrate. However, PDF estimation suffers from the "curse of dimensionality," requiring exponentially more data as the feature space grows. This paper addresses these challenges by proposing a direct estimator that bypasses explicit PDF estimation, providing a general-purpose and robust solution for high-dimensional data.

Methodology: The Bernstein Connection

The core innovation lies in the realization that density functionals can be expressed as integrals of a "posterior mapping function" $g(\eta)$, where $\eta$ represents the posterior probability of a class. The authors utilize $k$-NN statistics to create a natural coordinate system for these distributions.

For a given dataset, the method examines the $k$-nearest neighbors of each point and calculates the fraction of neighborhoods containing exactly $r$ points from a specific class. This statistic, denoted as $\rho_{r,k,N}$, serves as the foundation for the estimator. A key theoretical contribution of this work is the proof that as the sample size $N \to \infty$, this $k$-NN statistic converges to the Bernstein basis polynomials.

Figure 2: The $k$-NN statistic $\rho_{r,k}$ converges to the Bernstein basis polynomials as the sample size $N$ increases, providing a robust data-driven basis for functional estimation.

To translate this theoretical connection into a practical estimator, the authors use convex optimization to find the optimal weights for the basis functions. Because standard Bernstein weights can lead to high variance in finite datasets, the authors introduce a regularization term ($\lambda$). This term penalizes large oscillating coefficients, stabilizing the estimator.

Figure 4: Mean Squared Error (MSE) vs. $k$ for different estimation strategies. The convex optimization approach with regularization (yellow) prevents the instability and large errors seen in the unregularized convex method (red) while maintaining better performance than the standard Bernstein approach (blue).

Furthermore, a "density-weighted fitting" approach is proposed. This refinement uses the data to identify regions where the posterior distribution is most dense, allowing the optimizer to prioritize accuracy where data is most abundant, further improving performance on finite samples.

Experimental Results

The framework was evaluated using synthetic multivariate datasets, including multivariate Gaussians and uniform hypercubes, across various dimensions (up to 8D).

  • Accuracy and Bias: In experiments with non-Gaussian data, the proposed method significantly outperformed parametric estimators. While parametric models suffered from massive asymptotic bias due to incorrect distributional assumptions, the direct basis-expansion method remained accurate.
  • Comparison to Plug-ins: The direct estimator achieved lower Mean Squared Error (MSE) than traditional $k$-NN plug-in estimators, particularly as the sample size increased.
  • Bayes Error Bounds: On 8-dimensional Gaussian benchmark datasets, the "Convex Bound" produced by this method was notably tighter than classical bounds. For instance, in a dataset with a 10% actual error, the Convex Bound estimated 14.17%, whereas the widely used Bhattacharyya bound was much looser at 21.74%.

Discussion and Conclusion

While the proposed method offers significant advantages, it introduces some computational overhead. The "density-weighted" version requires an $O(k^3)$ optimization step for each new dataset. Additionally, while regularization reduces sensitivity to the choice of $k$, selecting the optimal $k$ relative to the sample size $N$ still relies on heuristics.

Future research directions include exploring orthogonal versions of the Bernstein basis. Such an approach could simplify the weight-solving process and potentially accelerate convergence rates, further enhancing the utility of direct density functional estimation in complex, high-dimensional machine learning tasks.

Summary updated

BibTeX
@article{wisler2018direct,
  author = {Alan Wisler and Visar Berisha and Andreas Spanias and Alfred O. Hero III},
  title = {{Direct Estimation of Density Functionals Using a Polynomial Basis}},
  journal = {IEEE Trans. Signal Process.},
  year = {2018},
  doi = {10.1109/tsp.2017.2775587},
}
Figure