Statistical Estimation of the Kullback–Leibler Divergence

Alexander Bulinski, Denis DimitrovMDPI (MDPI AG) 2021 · DOI

TL;DR

This paper introduces and analyzes new statistical estimators for the Kullback-Leibler (KL) divergence between two probability distributions in high-dimensional spaces (Rd). The key contribution is proving that these estimators are asymptotically unbiased and L²-consistent under very general conditions, without requiring densities to be smooth or have bounded support. This is a significant step towards reliable KL divergence estimation in complex, real-world scenarios.

What Problem Does This Paper Address?

The Kullback-Leibler (KL) divergence is a fundamental measure in information theory and statistics, quantifying how one probability distribution differs from another. It has wide applications in machine learning, statistics, and signal processing. However, accurately estimating the KL divergence from data, especially in high-dimensional spaces (Rd) and when the underlying probability distributions are not well-behaved (e.g., not smooth or with unbounded support), is a challenging problem. Existing methods often rely on strong assumptions that limit their applicability. This paper aims to develop and rigorously analyze estimators that overcome these limitations, providing robust tools for KL divergence estimation.

Methods

The authors propose novel estimators for the KL divergence based on k-nearest neighbor (k-NN) statistics. Instead of using the standard nearest neighbor, they employ k-nearest neighbors from two independent samples of observations from the two distributions. The estimators are constructed using specific functionals involving these k-NN distances. The core of the paper lies in the theoretical analysis, where they establish asymptotic unbiasedness and L²-consistency of these estimators. This involves developing new techniques to bound certain functions and leveraging properties of regularly varying functions and convexity. They also extend their results to mixture models, including mixtures of Gaussian distributions.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and does not present empirical evaluations on specific datasets.

Key Insights and Ideas

  • Generalizability of k-NN for KL Divergence: The paper demonstrates that extending the nearest neighbor concept to k-nearest neighbors (k-NN) for KL divergence estimation is effective and can be rigorously analyzed.
  • Mild Conditions for Consistency: A major breakthrough is proving the asymptotic unbiasedness and L²-consistency of the proposed estimators under very weak conditions on the probability densities. This includes densities with unbounded support and without requiring smoothness.
  • Novel Functional Analysis: The authors introduce and utilize new functionals (e.g., $K_{p,q}(v, N, t)$, $Q_{p,q}(\epsilon, R)$, $T_{p,q}(\epsilon, R)$) and analytical tools to bound the behavior of the estimators, which are crucial for proving their theoretical properties.
  • Connection to Shannon Entropy: The work builds upon and extends previous research on Shannon entropy estimation, showing how similar k-NN-based approaches can be adapted for KL divergence.
  • Applicability to Gaussian Mixtures: The theoretical results are shown to hold for mixtures of Gaussian distributions, a common and important class of probability distributions.

Key Results

  • Asymptotic Unbiasedness: Theorem 1 establishes that the proposed KL divergence estimators are asymptotically unbiased, meaning their expected value converges to the true KL divergence as the sample sizes increase. This holds under mild conditions on the densities.
  • L²-Consistency: Theorem 2 proves that the estimators are L²-consistent, meaning the mean squared error of the estimators converges to zero as sample sizes increase. This is a stronger form of convergence than unbiasedness.
  • General Conditions: The proofs rely on conditions related to the finiteness of certain integral functionals involving the densities, which are more general than those typically required in prior work.
  • Gaussian Case: Corollary 5 explicitly shows that the results apply to KL divergence estimation between two Gaussian random vectors, providing a concrete example of the theory's applicability.

Limitations and Future Work

  • Theoretical Focus: The paper is primarily theoretical, focusing on proving asymptotic properties. It does not include empirical evaluations or comparisons with existing estimators on real datasets.
  • Choice of k and Parameters: While the theory provides conditions for consistency, the practical choice of the parameter $k$ (number of neighbors) and other tuning parameters (like $\epsilon$, $R$, $N$) for the estimators is not explicitly addressed.
  • Computational Complexity: k-NN based methods can be computationally intensive, especially in high dimensions. The paper does not delve into the computational aspects of the proposed estimators.
  • Future Directions: The authors suggest that their approach can be extended to other divergence measures and that further investigation into the practical implementation and performance of these estimators would be valuable. The paper also hints at potential applications in areas like feature selection and classification.

Summary updated

Abstract

Asymptotic unbiasedness and L2-consistency are established, under mild conditions, for the estimates of the Kullback–Leibler divergence between two probability measures in Rd, absolutely continuous with respect to (w.r.t.) the Lebesgue measure. These estimates are based on certain k-nearest neighbor statistics for pair of independent identically distributed (i.i.d.) due vector samples. The novelty of results is also in treating mixture models. In particular, they cover mixtures of nondegenerate Gaussian measures. The mentioned asymptotic properties of related estimators for the Shannon entropy and cross-entropy are strengthened. Some applications are indicated.
BibTeX
@inproceedings{bulinski2021statistical,
  author = {Alexander Bulinski and Denis Dimitrov},
  title = {{Statistical Estimation of the Kullback–Leibler Divergence}},
  booktitle = {MDPI (MDPI AG)},
  year = {2021},
  doi = {10.3390/math9050544},
}
Figure