PaperlayerView exact revision on arXiv

Source-linked AI summary

The Burbea-Rao and Bhattacharyya centroids

Frank Nielsen, Sylvain Boltz

arXiv:1004.5049v3cs.ITcs.CG

TL;DR

The paper addresses how to define and compute centroids for Burbea-Rao divergences and related Bhattacharyya distances beyond previously limited Gaussian settings. It develops uniqueness and convergent iterative estimation results, then connects Bhattacharyya distances in exponential families to Burbea-Rao divergences for centroid computation and Gaussian-mixture applications.

  • Problem

    Bhattacharyya centroids had previously been studied only for univariate or diagonal multivariate Gaussians, with no reported convergence guarantees for the iterative estimator.

  • Method

    The paper relates Burbea-Rao divergences to Bregman and Bhattacharyya constructions, proves centroid uniqueness, and estimates centroids with an iterative concave-convex procedure.

  • Results

    Bhattacharyya distances within a common exponential family can be computed as Burbea-Rao divergences on natural parameters, enabling a generic centroid algorithm for broader parametric families.

  • Takeaways & Limitations

    The framework supports Bhattacharyya centroid computation and Gaussian-mixture simplification through k-means and hierarchical clustering applications.

Abstract

from arXiv · show

We study the centroid with respect to the class of information-theoretic Burbea-Rao divergences that generalize the celebrated Jensen-Shannon divergence by measuring the non-negative Jensen difference induced by a strictly convex and differentiable function. Although those Burbea-Rao divergences are symmetric by construction, they are not metric since they fail to satisfy the triangle inequality. We first explain how a particular symmetrization of Bregman divergences called Jensen-Bregman distances yields exactly those Burbea-Rao divergences. We then proceed by defining skew Burbea-Rao divergences, and show that skew Burbea-Rao divergences amount in limit cases to compute Bregman divergences. We then prove that Burbea-Rao centroids are unique, and can be arbitrarily finely approximated by a generic iterative concave-convex optimization algorithm with guaranteed convergence property. In the second part of the paper, we consider the Bhattacharyya distance that is commonly used to measure overlapping degree of probability distributions. We show that Bhattacharyya distances on members of the same statistical exponential family amount to calculate a Burbea-Rao divergence in disguise. Thus we get an efficient algorithm for computing the Bhattacharyya centroid of a set of parametric distributions belonging to the same exponential families, improving over former specialized methods found in the literature that were limited to univariate or "diagonal" multivariate Gaussians. To illustrate the performance of our Bhattacharyya/Burbea-Rao centroid algorithm, we present experimental performance results for $k$-means and hierarchical clustering methods of Gaussian mixture models.

I. INTRODUCTION

The paper frames centroids through axiomatic and optimization approaches, then develops information-theoretic means from f-divergences and Bregman divergences. These constructions support generalized means, weighted centroids, and clustering-oriented geometric aggregation.

  • Centroid definitions: Centroids can be defined axiomatically or as minimizers of an average distance over a point set.The optimization formulation includes non-negative weights representing multiplicity or relative importance.
  • Generalized means: Quasi-arithmetic means apply an arithmetic mean after transforming values by a strictly increasing function and then inverting that transform.Arithmetic, geometric, and harmonic means arise from f(x) = x, log x, and 1/x, respectively.
  • Information-theoretic means: f-divergence optimization yields unique entropic means that are invariant under linear scaling.The construction extends f-divergences from probability measures to positive measures.
  • Information-theoretic means: Bregman-divergence optimization yields a quasi-arithmetic mean generated by the derivative F′ of a strictly convex differentiable function.Right-sided centroids can also be defined because information-theoretic distances may be asymmetric.
  • Geometric extensions: Separable divergences extend centroid optimization coordinate-wise, while generalized quadratic distances provide a non-separable Mahalanobis example.Centroids are central to clustering because a cluster mean aggregates data into one center datum.
  • Scope: The paper does not cover the broader expectation-based framework for statistical centrality for brevity.That framework defines expectations using a Lebesgue-Stieltjes integral.

B. Burbea-Rao divergences

Burbea-Rao divergences are Jensen differences generated by strictly convex differentiable functions, generalizing Jensen-Shannon divergence and supporting centroid optimization. Unlike the square root of Jensen-Shannon divergence, they are not generally metrics because the triangle inequality can fail.

  • Definition and scope: Burbea-Rao divergences arise from Jensen differences induced by strictly convex differentiable functions and generalize Jensen-Shannon divergence.The paper studies separable Burbea-Rao divergences and defines centroids as minimizers of their average divergences.
  • Special cases: Quadratic generators recover generalized quadratic distances, including squared Mahalanobis distances, as a special Burbea-Rao case.For positive-definite Q, the resulting expression is 1/4∥p − q∥^2_Q.
  • Metric properties: Burbea-Rao divergences are not generally metrics because they can fail the triangle inequality, unlike the square root of Jensen-Shannon divergence.Their symmetry does not guarantee metricity.

C. Contributions and paper organization

The paper develops Burbea-Rao centroids and connects them to Bhattacharyya distances in exponential families. It establishes uniqueness and iterative computation, while showing that these symmetric divergences generally fail the triangle inequality.

  • Contributions: The paper defines skew Burbea-Rao divergences as Jensen-Bregman generalizations of Jensen-Shannon divergence, with Bregman divergences arising in limit cases.The construction uses a strictly convex differentiable generator and yields a broader family of symmetric divergence measures.
  • Contributions: Burbea-Rao centroids are unique and can be approximated arbitrarily finely by an iterative convex-concave optimization procedure with guaranteed convergence.The same contribution identifies Bregman-sided centroids in extremal skew cases.
  • Applications in Statistics: For distributions in one exponential family, skew Bhattacharyya distances are equivalent to skew Burbea-Rao divergences, while the limit case recovers a Bregman-form Kullback-Leibler divergence.The equivalence is expressed on the natural parameters of the exponential family.
  • Applications in Statistics: The Burbea-Rao centroid algorithm iteratively computes Bhattacharyya centroids for exponential-family distributions, including multivariate Gaussians, with both generic and Gaussian-specific schemes.The paper also applies these centroids to simplifying Gaussian mixture models through hierarchical clustering and reports favorable comparisons with prior Bregman-centroid results.
  • Burbea-Rao divergences: Burbea-Rao divergences are symmetric and non-negative but are not metrics because they fail the triangle inequality.Their geometric interpretation is the vertical distance between the midpoint of a chord and the midpoint of the graph of the convex generator.
  • Burbea-Rao divergences: Jensen-Bregman symmetrization uses the generator itself, unlike Jeffreys-Bregman symmetrization, which uses the gradient; the two yield different divergences.Both symmetrizations are finite for the negative Shannon entropy example discussed in the paper.

III. SKEW BURBEA-RAO DIVERGENCES

Skew Burbea-Rao divergences introduce a weighting parameter into Jensen-Bregman constructions and recover Bregman divergences in limiting cases. Their extremal behavior follows from one-sided limits and supports extensions beyond the open parameter interval.

  • Skew construction: A positive weight α ∈ (0, 1) defines skew Burbea-Rao divergences by averaging p and q asymmetrically.Swapping the arguments corresponds to replacing α with 1 − α.
  • Skew construction: Skew Burbea-Rao divergences arise from skew Jensen-Bregman sums because the gradient terms cancel.The construction combines weighted Bregman divergences evaluated at the weighted mixture αp + (1 − α)q.
  • Limit cases: Although the divergences vanish at α ∈ {0, 1}, scaling extends the family so Bregman divergences belong to skew Burbea-Rao divergences.The parameter can subsequently be extended from (0, 1) to the full real line.
  • Limit cases: As α → 0, skew Burbea-Rao divergences tend to Bregman divergences, while α → 1 yields reverse Bregman divergences.The result is established through one-sided limits and generalized derivatives of convex functions.
  • Special cases: The symmetric Burbea-Rao case is recovered from the skew definition when the weighting specializes to equal averaging.The construction includes generalized quadratic distances, including squared Mahalanobis distances, for suitable generators.

IV. BURBEA-RAO CENTROIDS

Burbea-Rao centroids minimize weighted sums of skew divergences over a point set. They are unique, can be computed iteratively with CCCP, and converge in extremal skew cases to closed-form Bregman centroids.

  • Centroid definition: A skew Burbea-Rao centroid minimizes a weighted sum of divergences BR_F^(α_i)(x, p_i) over points p_i with positive weights and skew parameters.The parameters α_i lie in (0, 1), and the centroid is defined through the resulting optimization task.
  • Optimization: The centroid objective decomposes into convex and concave components, enabling iterative solution with the Convex-Concave Procedure.The update scheme begins from an initial point such as the weighted barycenter.
  • Closed forms and limits: For most Burbea-Rao divergences, the centroid equation must be solved numerically rather than in closed form.The ordinary barycenter is obtained in the quadratic special case, where the gradient condition gives the weighted mean.
  • Closed forms and limits: As α approaches 0 or 1, skew Burbea-Rao centroids approach left- or right-sided Bregman centroids with closed-form expressions.This provides a smooth transition from the center of mass to a quasi-arithmetic mean generated by ∇F.
  • Optimization: Skew Burbea-Rao centroids are unique and can be estimated iteratively using the CCCP algorithm.Strict monotonicity of the gradient makes the centroid equation a fixed-point problem with at most one solution.

A. Burbea-Rao divergences of a population

Burbea-Rao divergences are defined for weighted populations and connect naturally to exponential-family distributions. In that setting, statistical Bhattacharyya and Chernoff distances reduce to Burbea-Rao computations.

  • Population divergences: For a population with normalized positive weights, the Burbea-Rao divergence measures the Jensen difference induced by a convex generator.The framework includes Jensen-Rényi divergences when the generator is the negative Rényi entropy.
  • Connection to statistical distances: Statistical Bhattacharyya and Chernoff distances between distributions in the same exponential family amount to computing Burbea-Rao divergences.This establishes the connection used later for centroid computation.
  • Exponential-family distributions: The canonical representation uses sufficient statistics t(x), a carrier term k(x), and an inner product appropriate to scalar, vector, or matrix parameters.For composite parameters, the inner product combines the corresponding component products or traces.
  • Exponential-family distributions: Exponential families share a canonical decomposition in which distributions are indexed by natural parameters and characterized by a strictly convex log-normalizer F.The natural parameter θ is related one-to-one to source parameters λ through the coordinate map τ.
  • Examples and scope: The framework covers discrete and continuous distributions, including Poisson and multivariate Gaussian exponential families.The paper explicitly gives canonical decompositions for these examples and treats Gaussian families in subsequent applications.

B. Bhattacharyya/Chernoff coefficients and α-divergences as skew Burbea-Rao divergences

For distributions in the same exponential family, Bhattacharyya and Chernoff divergences have closed-form representations as skew Burbea-Rao divergences, with extremal cases recovering Bregman and Kullback–Leibler divergences.

  • The Bhattacharyya coefficient measures distribution overlap, while Chernoff coefficients generalize it through the parameter α.The Bhattacharyya divergence corresponds to α = 1/2.
  • For same-family exponential distributions, Chernoff distances equal weighted skew Burbea-Rao divergences.The result is stated in closed form for the family’s natural parameters.
  • The same-family formulation also provides closed-form expressions for related α-divergences and Chernoff coefficients.The paper connects these quantities through their shared exponential-family parameterization.
  • The skew Bhattacharyya divergence is exactly the Burbea-Rao divergence evaluated on the corresponding exponential-family parameters.This follows from expressing the coefficient as the exponential of a Burbea-Rao divergence.
  • At α = 0 or 1, these divergences reduce to Kullback–Leibler divergences and equivalent Bregman divergences on swapped natural parameters.The limiting identities use the log-normalizer of the exponential family.

C. Direct method for calculating the Bhattacharyya centroids of multivariate normals

The paper develops iterative procedures for Bhattacharyya centroids of multivariate Gaussians, extending a specialized Gaussian approach and comparing it with the generic Burbea-Rao formulation.

  • Earlier Bhattacharyya-centroid work addressed univariate or diagonal multivariate Gaussians without reported convergence guarantees.The paper extends that approach to general multivariate Gaussians.
  • The tailored Gaussian method minimizes an energy obtained by inserting Gaussian Bhattacharyya distances into the centroid optimization problem.The resulting objective is differentiated with respect to the centroid mean and covariance.
  • The centroid mean is updated iteratively because the matrix U_i depends on the unknown centroid covariance.Here U_i is defined as (Σ_c + Σ_i)^−1.
  • The centroid covariance is likewise estimated through an iterative update derived using matrix differentials for symmetric matrices.The paper presents separate differential calculations before specifying the covariance update.
  • The generic Burbea-Rao and tailored Gaussian schemes are positioned as alternative methods for computing Bhattacharyya centroids of multivariate Gaussians.The comparison concerns their stability and accuracy.

D. Applications to mixture simplification in statistics

The paper applies Bhattacharyya centroids to Gaussian-mixture simplification and reports qualitatively stable clustering, with better performance for hierarchical clustering on one image.

  • Gaussian-mixture simplification supports signal-processing applications and studies of Fisher-metric geometry requiring mixtures with prescribed component counts.The authors adapt hierarchical clustering by replacing Jeffreys-Bregman centroids with Bhattacharyya centroids.
  • The first experiments report qualitative stability of clustering performance.This result is stated for the experiments shown in Figure 3.
  • Hierarchical clustering with Bhattacharyya distance performs qualitatively much better on the last colormap image.The comparison is reported as an experimental observation rather than a numerical metric.
  • A second experiment compares numerical convergence of the generic Burbea-Rao and tailored Gaussian centroid methods using their Bhattacharyya-distance energy values.Methods are considered beaten when their energy values differ by more than 1%.

VI. CONCLUDING REMARKS

The paper concludes that Bhattacharyya distances within a common exponential family are equivalent to Burbea-Rao divergences, enabling centroid computation through generic and Gaussian-specific iterative methods.

  • Bhattacharyya distances for distributions in the same statistical exponential family can be computed as Burbea-Rao divergences on natural parameters.The equivalence extends to skew Chernoff coefficients and skew Bhattacharyya distances.
  • Skew Burbea-Rao centroids are unique and can be efficiently estimated by an iterative concave-convex procedure with guaranteed convergence.The paper also identifies Bregman-sided centroids in closed form at extremal skew values.

APPENDIX

The appendix establishes that Burbea-Rao centroids are unique despite possible non-convexity, and that CCCP iteratively approximates them with guaranteed convergence.

  • Uniqueness: Burbea-Rao centroid minimization may be non-convex, so general local-minimum concerns arise a priori.For univariate generators, the Jensen divergence can have alternating curvature.
  • Uniqueness: Despite non-convexity, the centroid induced by a Jensen divergence is unique.The result holds for strictly convex generators.
  • CCCP convergence: CCCP generates iterated quasi-arithmetic means whose interness keeps each iterate within its current extremal range.This range property underpins both the uniqueness proof and convergence analysis.
  • CCCP convergence: The centroid approximations converge to a unique centroid for any strictly convex generator F.The limiting centroid lies within the initial data range, with the center depending on F.
  • CCCP convergence: 1 2^t relative precision is achieved after t iterations, demonstrating linear convergence of CCCP.The algorithm can stop using the maintained approximation range; with ∇F = log x, machine precision 10^-12 is reached in about 50 iterations.
  • Multivariate extension: The convergence analysis extends naturally to separable multivariate functions by treating each dimension independently.The univariate interval argument therefore applies coordinatewise in the separable multivariate case.
Loading 1004.5049v3…