Estimation of Rényi Entropy and Mutual Information Based on Generalized Nearest-Neighbor Graphs

Dávid Pál; Barnabás Póczos; Csaba Szepesvári

Source-linked AI summary

Estimation of Rényi Entropy and Mutual Information Based on Generalized Nearest-Neighbor Graphs

Dávid Pál, Barnabás Póczos, Csaba Szepesvári

arXiv:1003.1954v2Mar 9, 2010stat.MLcs.AI

TL;DR

The paper addresses nonparametric estimation of Rényi entropy and mutual information without directly estimating the unknown density. It uses generalized nearest-neighbor edge functionals and empirical copulas, proving strong consistency and finite-sample rate bounds under stated smoothness conditions, with experiments supporting practical use in independent subspace analysis.

Problem
The paper seeks estimators of Rényi entropy and mutual information from i.i.d. samples while avoiding direct estimation of the unknown density and its marginals.
Method
The estimators use sums of p-th powers of generalized nearest-neighbor edge lengths for entropy and empirical copula transformations for mutual information.
Results
The paper proves strong consistency and finite-sample high-probability error bounds for entropy and mutual-information estimators under bounded-support, Lipschitz-density, or Lipschitz-copula conditions.
Takeaways & Limitations
Nearest-neighbor methods are computationally efficient relative to MST and TSP, can be reused across α values, and empirically outperform histogram plug-in estimates in reported experiments.
Takeaways & Limitations
Open problems include selecting S to balance bias and variance and proving convergence-rate bounds for densities with higher-order smoothness.

Abstract

from arXiv · show

We present simple and computationally efficient nonparametric estimators of Rényi entropy and mutual information based on an i.i.d. sample drawn from an unknown, absolutely continuous distribution over $\R^d$. The estimators are calculated as the sum of $p$-th powers of the Euclidean lengths of the edges of the `generalized nearest-neighbor' graph of the sample and the empirical copula of the sample respectively. For the first time, we prove the almost sure consistency of these estimators and upper bounds on their rates of convergence, the latter of which under the assumption that the density underlying the sample is Lipschitz continuous. Experiments demonstrate their usefulness in independent subspace analysis.

1 Introduction

The paper develops direct nearest-neighbor estimators for Rényi entropy and mutual information, addressing limitations of plug-in density estimation. It proves consistency and convergence-rate results, extends mutual-information estimation through empirical copulas, and evaluates the methods numerically.

Plug-in estimators require estimating the nuisance density and tuning parameters, potentially including cross-validation.
The paper proves strong consistency for generalized nearest-neighbor entropy estimators when f has bounded support and α ∈ (0, 1).
It proves a finite-sample high-probability entropy error bound when f is Lipschitz, presenting this as the first rate result for Rényi entropy estimation.
It proves strong consistency for a nearest-neighbor mutual-information estimator using empirical copula transformation for d ≥ 3 and α ∈ (1/2, 1).
k-NN graphs can be computed faster than MST and TSP, parallelized easily, and reused across α values because the graph is unchanged by monotone distance powers.
Experiments report that nearest-neighbor methods empirically outperform plug-in estimates and illustrate mutual-information estimation in independent subspace analysis.

2 The Formal Definition of the Problem

The formal problem is to estimate Rényi entropy and mutual information from an i.i.d. sample drawn from an unknown distribution with joint and marginal densities. Shannon entropy and mutual information arise as the α = 1 limiting cases.

Rényi entropy and mutual information are defined for d real-valued variables with joint density f and marginal densities f_i.
For α = 1, Rényi entropy and mutual information are defined by limits and recover Shannon entropy and Shannon mutual information.
Given i.i.d. observations X_1:n, the task is to construct estimates of H_α(f) and I_α(f) using the sample.

3 Generalized Nearest-Neighbor Graphs

The generalized nearest-neighbor graph connects each sample point to selected ranked neighbors, and its edge-length power sum supplies the central geometric functional. A uniform-sample theorem establishes the scaling constant used by the estimators.

For a finite set V and finite nonempty S, each vertex connects to its i-th nearest neighbor for every i ∈ S.
The functional L_p(V) is the sum of p-th powers of Euclidean edge lengths in the generalized nearest-neighbor graph.
For uniform samples on [0,1]^d, a constant γ exists for the normalized functional for every p ≥ 0 and finite nonempty S.
Because γ generally lacks an analytical formula, it can be estimated empirically from a large uniform sample using L_p(X_1:n)/n^(1-p/d).

4 An Estimator of R´enyi Entropy

The Rényi entropy estimator applies a logarithmic normalization to the generalized nearest-neighbor edge functional. Under bounded support it is strongly consistent, and Lipschitz densities additionally yield a high-probability convergence bound.

For α ∈ (0, 1), the estimator uses L_p(X_1:n), γ, and n^(1-p/d), with p = d(1 − α).
The estimator is strongly consistent for absolutely continuous distributions with bounded support.
When f is Lipschitz, the estimator also has a finite-sample high-probability upper bound on its convergence error.

5 Copulas and Estimator of Mutual Information

The paper uses copula transformations to reduce Rényi mutual-information estimation to entropy estimation, replacing unknown marginal CDFs with empirical CDFs. The resulting nearest-neighbor estimator is strongly consistent and has a high-probability rate under a Lipschitz copula-density condition.

Strictly increasing coordinate transformations preserve Rényi mutual information, enabling marginal rescaling without changing the target.
Choosing each transformation as the corresponding marginal CDF makes every transformed marginal uniform on [0, 1].
Unknown marginal CDFs are replaced by empirical CDFs, forming the empirical copula from transformed sample points.
Although empirical-copula observations are dependent, the paper treats them as a good approximation to an i.i.d. sample from the copula distribution.
The mutual-information estimator applies the Rényi entropy estimator to the empirical copula and is proved strongly consistent with convergence-rate bounds.

6 Experiments

Experiments examine convergence rates and an Independent Subspace Analysis application. The estimator follows the predicted upper-bound trend, outperforms histogram plug-in estimates in tested settings, and successfully estimates subspaces on a six-source benchmark.

6.1 The Rate of Convergence: The convergence-rate experiment evaluates uniform and Gaussian distributions in 3D and 20D using α = 0.7, kth and knn graph variants, and 25 independent runs.
6.1 The Rate of Convergence: The observed estimation errors support the derived rate as an upper bound, while the theoretical rates are described as conservative for the tested regular densities.
6.1 The Rate of Convergence: The nearest-neighbor estimators outperform histogram plug-in estimators in the reported experiments, while histograms are not practically applicable in the 20D case.
6.2 Application to Independent Subspace Analysis: Using the copula estimator with α = 0.99 and S = {1, 2, 3}, the ISA procedure provides good estimation of the source subspaces.
6.2 Application to Independent Subspace Analysis: The ISA experiment uses 2,000 samples from six independent 3D wireframe sources mixed by a random invertible 18×18 matrix.

7 Further Related Works

The paper situates its nearest-neighbor estimators within earlier Euclidean-functional and entropy-estimation work. It generalizes prior nearest-neighbor constructions while emphasizing differences in graph selection, weighting, and consistency results.

The closest Euclidean-functional precedent studied NNS graphs with S = {1, 2, ..., k} and p = 1.
Earlier Shannon-entropy work used S = {1}, while later work used S = {k} and established weak consistency under density conditions.
The earlier Shannon estimator uses logarithms and a different normalization, whereas the paper’s estimator uses p-th powers of edge lengths.
The earlier Rényi estimator with S = {k} is essentially a special case of the paper’s NNS-based estimator.

8 Conclusions and Open Problems

The estimators are strongly consistent, with convergence-rate upper bounds under technical conditions. The authors identify open problems concerning tuning, Shannon-entropy limits, empirical-copula errors, and smoother densities.

The NN-graph estimators are strongly consistent, with upper bounds on their convergence rates under technical conditions.
Choosing S as a function of n, d, and p to balance estimator bias and variance remains open.
Using α close to 1 estimates Shannon entropy and mutual information, but an asymptotically optimal choice of α remains unresolved.
The mutual-information consistency proof restricts α to (1/2, 1) and dimension to d > 2, leaving broader settings open.
Convergence-rate bounds for densities with higher-order β-Hölder smoothness remain an important open problem.

A Quasi-Additive and Very Strong Euclidean Functionals

The analysis models nearest-neighbor edge-length sums as quasi-additive and very strong Euclidean functionals, enabling established limit and rate results. The paper verifies the required axioms and applies the resulting theorems to entropy estimation.

The nearest-neighbor functional L_p is analyzed using quasi-additive Euclidean-functional theory and its stronger axiomatic extension.The framework uses established results for quasi-additive and very strong functionals.
A quasi-additive Euclidean functional consists of a power-weighted functional L_p and a boundary functional L*_p on finite point sets in cubes.
Quasi-additive functionals satisfy axioms (A1)–(A7), whereas very strong functionals additionally satisfy axioms (A8)–(A9).
The Redmond–Yukich theorem gives the asymptotic limit for quasi-additive functionals, while the Koo–Lee theorem supplies a rate under Lipschitz density.
Compared with the original Koo–Lee result, the stated theorem restricts densities to Lipschitz ones and removes an extraneous log(n) factor from the rate.
The paper verifies the axioms for the nearest-neighbor functional, derives consistency and rate results, and handles mutual information through the empirical copula transformation.

B The Boundary Functional L∗

The boundary functional replaces sample edges that extend beyond a cube with edges to the nearest boundary points. This construction preserves edge correspondence, supports geometric bounds, and enables the smoothness arguments needed for the Euclidean-functional framework.

The boundary nearest-neighbor graph augments the sample with cube-boundary points and redirects overly long sample edges to the closest boundary point.
Each original nearest-neighbor edge corresponds bijectively to one edge in the boundary graph, allowing their power-weighted sums to be compared.
The boundary functional is no larger than the ordinary nearest-neighbor functional because boundary-replacement edges are shorter.
Geometric properties: The nearest-neighbor graph has uniformly bounded in-degree depending on dimension and k, which supports the functional's growth and smoothness bounds.
Growth bounds: For 0 < p < d, the nearest-neighbor edge functional grows as O(|V|^(1-p/d)), while for p ≥ d it is bounded by O(1).
Smoothness: Adding or removing points changes the functional by a bound controlled by the symmetric difference, establishing smoothness for both ordinary and boundary functionals.

C.3 Uniformly Distributed Points

For uniformly sampled points in the unit cube, the analysis bounds expected nearest-neighbor edge-power sums by controlling boundary connections and average k-th-neighbor distances. These bounds support the graph-functional arguments used later for consistency and convergence rates.

The sample consists of n points chosen independently and uniformly from [0, 1]^d.
The expected p-th power of a point’s distance to its k-th nearest neighbor is controlled through a ball-volume integral and gamma-function asymptotics.
The boundary contribution satisfies E[Lp(bUn)] ≤ O(max(n^(1−p/d−1/d), 1)).
O(n^(1−1/d)) bounds the number of sample points connected to the boundary through a partition of the interior cube into rectangles.
The proof concludes by combining the boundary estimates with the graph construction and bounds on in-degrees and out-degrees.

D Concentration and Estimator of Entropy

The concentration analysis establishes that nearest-neighbor graph functionals remain tightly controlled for i.i.d. samples, independently of the generating distribution’s density. These results feed into consistency and rate guarantees for the entropy estimator.

Lp(Vn) is tightly concentrated around its expected value within O(n^(1/2−p/(2d))) with high probability.
The concentration proof uses smoothness of Lp together with an isoperimetric inequality for Hamming distance and product measures.
Theorem 21 gives concentration of Lp(Vn) around its median for i.i.d. samples from absolutely continuous distributions over [0, 1]^d.
For 0 ≤ p ≤ d, Corollaries 22 and 23 provide deviation and concentration statements for the mean and median.

E Copulas and Estimator of Mutual Information

The mutual-information estimator is analyzed by comparing the empirical copula transformation with the population copula and propagating this perturbation through nearest-neighbor graph functionals. Under stated dimensional and parameter restrictions, the estimator is strongly consistent with rate bounds.

The Kiefer-Dvoretzky-Wolfowitz theorem controls the difference between empirical and population copula transformations.
Order-statistics stability transfers uniform pairwise distance perturbations to corresponding nearest-neighbor distances.
For 0 < p < 1, the perturbation scales as O(nε^p), while for 1 ≤ p it scales as O(nε).
The copula perturbation analysis bounds how coordinatewise sample changes affect p-th-powered nearest-neighbor edge sums.
When the copula density is Lipschitz, the estimator also receives a high-probability convergence bound.