Chernoff information of exponential families

Frank NielsenarXiv 2011 · arXiv

Abstract

Calculating the Chernoff information—the tightest upper bound on the Bayes error rate—is traditionally a computationally intensive task. This paper presents a unified framework for computing Chernoff information within the class of exponential families, which includes Gaussian, Poisson, and Multinomial distributions. By mapping the problem to information geometry, the author derives closed-form analytical solutions for simple families and introduces an efficient geodesic bisection algorithm for complex, multi-parametric distributions. This approach replaces fastidious numerical integration with geometric optimization, providing a robust tool for statistical inference and visual computing.

Introduction

In binary classification, the Bayes decision rule provides the minimum possible error rate. However, this "Bayes error" is often mathematically intractable to compute directly. Researchers rely on the Chernoff bound, which offers a tight upper bound but requires finding an optimal exponent ($\alpha$) that minimizes the error estimate. Historically, finding this "Chernoff point" has been a significant computational bottleneck. This paper addresses this challenge by leveraging the mathematical structure of exponential families and the tools of information geometry.

Methodology: Divergence Mapping

The core methodological contribution is the proof that the Chernoff $\alpha$-divergence between two distributions in the same exponential family is equivalent to a skew Jensen divergence of their log-normalizers ($F$). This transformation shifts the problem from the space of probability densities to the space of their natural parameters ($\theta$).

Geometric relationship between Jensen divergence ($J_F$) and Bregman divergence ($B_F$) used to map Chernoff information to parameter space.

For single-parameter families, such as Poisson or Gaussians with fixed variance, this mapping allows for the derivation of exact analytical formulas for the optimal $\alpha^*$. For more complex distributions, it provides a clear objective function for optimization.

Geometric Optimization via Geodesic Bisection

For multi-parametric families where closed-form solutions are unavailable, the paper introduces a novel geodesic bisection algorithm. The key insight is that the optimal Chernoff distribution (the Chernoff point) is the unique intersection of an exponential geodesic—the "shortest path" between two distributions in information space—and a Bregman Voronoi bisector.

The Chernoff point visualized as the intersection of a geodesic and a Voronoi bisector in both natural and expectation coordinate systems.

Instead of standard numerical optimization, this algorithm "walks" along the geometric path to find the intersection point. This method allows for arbitrarily fine approximations of Chernoff information, bypassing the need for complex integral computations.

Key Results and Discussion

The paper validates this framework across several standard statistical models, including Univariate/Multivariate Gaussians, Poisson, and Dirichlet distributions. Key findings include:

  • Analytical Formulas: Ready-to-use equations for Chernoff information in Poisson and Multivariate Gaussian cases.
  • Optimality over Bhattacharyya: The common Bhattacharyya distance (which assumes $\alpha = 0.5$) is shown to be frequently sub-optimal. The proposed method easily finds the true optimal $\alpha$, yielding a significantly tighter error bound.
  • Unified Framework: The work successfully integrates disparate statistical distances (like Renyi and Tsallis) into a single geometric context.

Conclusion and Future Work

While the current framework is tailored to exponential families, its geometric characterization of the Chernoff point offers a powerful alternative to traditional statistical methods. Future work may extend these concepts to non-exponential distributions or apply the bisection algorithm to real-time tasks in visual computing, such as image segmentation and feature registration, where precise statistical distance measures are critical.

Summary updated

Abstract

Chernoff information upper bounds the probability of error of the optimal Bayesian decision rule for $2$-class classification problems. However, it turns out that in practice the Chernoff bound is hard to calculate or even approximate. In statistics, many usual distributions, such as Gaussians, Poissons or frequency histograms called multinomials, can be handled in the unified framework of exponential families. In this note, we prove that the Chernoff information for members of the same exponential family can be either derived analytically in closed form, or efficiently approximated using a simple geodesic bisection optimization technique based on an exact geometric characterization of the "Chernoff point" on the underlying statistical manifold.
BibTeX
@misc{nielsen2011chernoff,
  author = {Frank Nielsen},
  title = {{Chernoff information of exponential families}},
  year = {2011},
  eprint = {1102.2684},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1102.2684},
}
Figure