REGO: Rank-based Estimation of Renyi Information using Euclidean Graph Optimization

Barnabás Póczos, Sergey Kirshner, Csaba SzepesváriAISTATS 2010 · OpenReview

Abstract

We propose REGO (Rank-based Estimation of Rényi Information), a novel non-parametric method for estimating Rényi and Shannon information in multivariate distributions. By combining copula theory with geometric graph optimization, REGO transforms data into empirical ranks before calculating graph lengths (such as Minimum Spanning Trees). This approach yields an estimator that is computationally efficient ($O(dn \log n)$), strongly consistent, and uniquely robust to outliers.

Introduction

Measuring dependence between random variables is fundamental to machine learning, with applications ranging from feature selection to image registration. While Shannon mutual information (MI) is a standard metric, its estimation for continuous variables is challenging when the underlying distribution is unknown. Existing methods typically involve density estimation (plug-in) or direct estimation from data points (e.g., $k$-nearest neighbor graphs). Plug-in estimators often suffer from the curse of dimensionality, while direct estimators can be sensitive to outliers and primarily target Shannon information.

The REGO Framework

The REGO algorithm addresses these challenges through a two-step process:

  1. Copula Transformation: Instead of raw values, REGO utilizes empirical ranks. Data is transformed via its empirical distribution function into a unit hypercube $[0, 1]^d$. This copula transformation preserves the dependence structure while standardizing marginals. Crucially, this step bounds the influence of any single data point, providing maximal robustness to outliers.
  2. Euclidean Graph Optimization (EGO): In the copula domain, the algorithm constructs geometric graphs, such as Minimum Spanning Trees (MST) or $k$-Nearest Neighbor ($k$-NN) graphs. The total edge length of these graphs is mathematically linked to Rényi entropy, allowing for direct information estimation without explicit density modeling.

Experimental Evaluation

The authors validated REGO across several scenarios, including synthetic 2D distributions (Independent Beta, Rotated Uniform, $t$-copula, and Gaussian) to verify convergence, and high-dimensional data (10D Uniform and Gaussian copulas) to test performance against the curse of dimensionality.

Key Results

REGO demonstrates strong consistency, with mathematical guarantees of convergence to true Rényi information for $d \geq 3$. In 2D synthetic tests, the estimator shows clear convergence across diverse distribution types as the sample size increases.

Convergence of REGO estimators on 2D synthetic distributions.

In high-dimensional settings, REGO exhibits remarkably fast convergence. For instance, in 10D Gaussian copula tests, it provides accurate estimates with relatively small sample sizes, outperforming traditional histogram-based methods that would require significantly more data to overcome the curse of dimensionality.

Estimation of mutual information in a 10D Gaussian copula.

Furthermore, REGO's robustness was highlighted in image registration tasks. While standard EGO methods failed when 4% of pixels were corrupted by noise, REGO remained unaffected due to its rank-based nature, which limits the influence of extreme outliers.

Conclusion and Future Work

REGO provides a robust, efficient, and largely "tuning-free" alternative for information estimation. While currently proven consistent for $d \geq 3$ and $\alpha \neq 1$, future work aims to extend these proofs to 2D cases and specifically address the Shannon information limit (where $\alpha \to 1$).

Summary updated

Abstract

We propose a new method for a non-parametric estimation of Renyi and Shannon information for a multivariate distribution using a corresponding copula, a multivariate distribution over normalized ra...
BibTeX
@inproceedings{poczos2010rego,
  author = {Barnabás Póczos and Sergey Kirshner and Csaba Szepesvári},
  title = {{REGO: Rank-based Estimation of Renyi Information using Euclidean Graph Optimization}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2010},
  url = {https://openreview.net/forum?id=iJzHc9EAsoU},
}
Figure