This is a working document which will be frequently updated with materials concerning the discrepancy between two distributions.

This document is also available in the PDF Distance.pdf

There are many other acronyms used in the literature for referencing a dissimilarity; For example, the following 5 D’s: Discrepancies, deviations, dissimilarities, divergences, and distances.

Contents

1 Statistical distances between densities with computationally intractable normalizers

Consider a density p(x) = where (x) is an unnormalized computable density and Z_p = ∫ p(x)dμ(x) the computationally intractable normalizer (also called in statistical physics the partition function or free energy). A statistical distance D[p₁ : p₂] between two densities p₁(x) = and p₂(x) = with computationally intractable normalizers Z_p1 and Z_p2 is said projective (or two-sided homogeneous) if and only if

In particular, letting λ₁ = Z_p1 and λ₂ = Z_p2, we have

Notice that the rhs. does not rely on the computationally intractable normalizers. These projective distances are useful in statistical inference based on minimum distance estimators [2] (see next Section).

Here are a few statistical projective distances:

• γ-divergences (γ > 0) [10, 6]:
  

  When γ → 0, we have [6] D_γ[p : q] = D_KL[p : q], the Kullback-Leibler divergence (KLD). For example, we can estimate the KLD between two densities of an exponential-polynomial family by Monte Carlo stochastic integration of the γ-divergence for a small value of γ [27].

  The γ-divergences (projective, Bregman-type=Cross-entropy-entropy) and the density power divergence [1] (non-projective, Bregman-type divergence):

  

  can be encapsulated into the family of Φ-power divergences [37] (functional density power divergence class):

  

  where ϕ(e^x) convex and strictly increasing, ϕ continuous and twice continously differentiable with finite second order derivatives. We have D_ϕ,0[p : q] = ϕ′(1)∫ _ℝp(x)log dμ(x) = ϕ′(1)D_KL[p : q].

• Cauchy-Schwarz divergence [9] (CSD, projective)
  

  and Hölder divergences [35] (HD, projective, which generalizes the CSD):

  

  We have

  

  and

  

  Hölder divergences between two densities p_θp and p_θq of an exponential family with cumulant function F(θ) is available in closed-form [35]:

  

  The CSD is available in closed-form between mixtures of an exponential family with a conic natural parameter [18]: This includes the case of Gaussian mixture models [11].

• Hilbert distance [34] (projective): Consider two probability mass functions p = (p₁,…,p_d) and q = (q₁,…,q_d) of the d-dimensional probability simplex. Then the Hilbert distance is
  

  We have

  

  The Hilbert projective simplex distance can be extended to the cone of positive-definite matrices [34] (and its subspace of correlation matrices called the elliptope) as follows:

  

  where λ_max(X) and λ_min(X) denote the largest and smallest eigenvalue of matrix X, respectively.

2 Statistical distances between empirical distributions and densities with computationally intractable normalizers

When estimating the parameter for a parametric family of distributions {p_θ} from i.i.d. observations = {x₁,…,x_n}, we can define a minimum distance estimator (MDE):

where p = ∑ _i=1ⁿδ_xi is the empirical distribution (normalized). Thus we need only a right-sided projective divergence to estimate models with computationally intractable normalizers. For example, the Maximum Likelihood Estimator (MLE) is a MDE wrt. the KLD:

It is thus interesting to study the impact of the choice of the distance D to the properties of the corresponding estimator (e.g., γ-divergences yields provably robust estimators [6]).

• Hyvärinen divergence [7] (also called Fisher divergence):
  

  The Hyvarinen divergence has been extended for order-α Hyvarinen divergences [22] (for α > 0):

  

3 The Jensen-Shannon divergence and some generalizations

3.1 Origins of the Jensen-Shannon divergence

Let (,,μ) be a measure space, and (w₁,P₁),…,(w_n,P_n) be n weighted probability measures dominated by a measure μ (with w_i > 0 and ∑ w_i = 1). Denote by := {(w₁,p₁),…,(w_n,p_n)} the set of their weighted Radon-Nikodym densities p_i = with respect to μ.

A statistical divergence D[p : q] is a measure of dissimilarity between two densities p and q (i.e., a 2-point distance) such that D[p : q] ≥ 0 with equality if and only if p(x) = q(x) μ-almost everywhere. A statistical diversity index D() is a measure of variation of the weighted densities in related to a measure of centrality, i.e., a n-point distance which generalizes the notion of 2-point distance when ₂(p,q) := {(,p₁),(,p₂)}:

The fundamental measure of dissimilarity in information theory is the I-divergence (also called the Kullback-Leibler divergence, KLD, see Equation (2.5) page 5 of [12]):

The KLD is asymmetric (hence the delimiter notation “:” instead of ‘,’) but can be symmetrized by defining the Jeffreys J-divergence (Jeffreys divergence, denoted by I₂ in Equation (1) in 1946’s paper [8]):

Although symmetric, any positive power of Jeffreys divergence fails to satisfy the triangle inequality: That is, D_J^α is never a metric distance for any α > 0, and furthermore D_J^α cannot be upper bounded.

In 1991, Lin proposed the asymmetric K-divergence (Equation (3.2) in [14]):

and defined the L-divergence by analogy to Jeffreys’s symmetrization of the KLD (Equation (3.4) in [14]):

By noticing that

where h denotes Shannon entropy (Equation (3.14) in [14]), Lin coined the (skewed) Jensen-Shannon divergence between two weighted densities (1 - α,p) and (α,q) for α ∈ (0,1) as follows (Equation (4.1) in [14]):

(1)

Finally, Lin defined the generalized Jensen-Shannon divergence (Equation (5.1) in [14]) for a finite weighted set of densities:

This generalized Jensen-Shannon divergence is nowadays called the Jensen-Shannon diversity index.

To contrast with the Jeffreys’ divergence, the Jensen-Shannon divergence (JSD) D_JS := D_JS, is upper bounded by log 2 (does not require the densities to have the same support), and is a metric distance [4, 5]. Lin cited precursor work [42, 15] yielding definition of the Jensen-Shannon divergence: The Jensen-Shannon divergence of Eq. 1 is the so-called “increments of entropy” defined in (19) and (20) of [42].

The Jensen-Shannon diversity index was also obtained very differently by Sibson in 1969 when he defined the information radius [40] of order α using Rényi α-means and Rényi α-entropies [38]. In particular, the information radius IR₁ of order 1 of a weighted set of densities is a diversity index obtained by solving the following variational optimization problem:

(2)

Sibson solved a more general optimization problem, and obtained the following expression (term K₁ in Corollary 2.3 [40]):

Thus Eq. 2 is a variational definition of the Jensen-Shannon divergence.

3.2 Some extensions of the Jensen-Shannon divergence

• Skewing the JSD.

  The K-divergence of Lin can be skewed with a scalar parameter α ∈ (0,1) to give

  (3)

  Skewing parameter α was first studied in [13] (2001, see Table 2 of [13]). We proposed to unify the Jeffreys divergence with the Jensen-Shannon divergence as follows (Equation 19 in [17]):

  (4)

  When α = , we have D_K,^J = D_JS, and when α = 1, we get D_K,1^J = D_J.

  Notice that

  

  amounts to calculate

  

  where

  

  denotes the cross-entropy. By choosing α = β, we have h^×[(1-β)p+βq : (1-α)p+αq] = h[(1-α)p+αq], and thus recover the skewed Jensen-Shannon divergence of Eq. 1.

  In [21] (2020), we considered a positive skewing vector α ∈ [0,1]^k and a unit positive weight w belonging to the standard simplex Δ_k, and defined the following vector-skewed Jensen-Shannon divergence:

  

  where α = ∑ _i=1^kw_iα_i. The divergence D_JS^α,w generalizes the (scalar) skew Jensen-Shannon divergence when k = 1, and is a Ali-Silvey-Csiszár f-divergence upper bounded by log  [21].
• A priori mid-density. The JSD can be interpreted as the total divergence of the densities to the mid-density p = ∑ _i=1ⁿw_ip_i, a statistical mixture:
  

  Unfortunately, the JSD between two Gaussian densities is not known in closed form because of the definite integral of a log-sum term (i.e., K-divergence between a density and a mixture density p). For the special case of the Cauchy family, a closed-form formula [29] for the JSD between two Cauchy densities was obtained. Thus we may choose a geometric mixture distribution [19] instead of the ordinary arithmetic mixture p. More generally, we can choose any weighted mean M_α (say, the geometric mean, or the harmonic mean, or any other power mean) and define a generalization of the K-divergence of Equation 3:

  (7)

  where

  

  is a statistical M-mixture with Z_Mα(p,q) denoting the normalizing coefficient:

  

  so that ∫ (pq)_Mα(x)dμ(x) = 1. These M-mixtures are well-defined provided the convergence of the definite integrals.

  Then we define a generalization of the JSD [19] termed (M_α,N_β)-Jensen-Shannon divergence as follows:

  (8)

  where N_β is yet another weighted mean to average the two M_α-K-divergences. We have D_JS = D_JS^A,A where A(a,b) = is the arithmetic mean. The geometric JSD yields a closed-form formula between two multivariate Gaussians, and has been used in deep learning [3]. More generally, we may consider the Jensen-Shannon symmetrization of an arbitrary distance D as

  (9)

• A posteriori mid-density. We consider a generalization of Sibson’s information radius [40]. Let S_w(a₁,…,a_n) denote a generic weighted mean of n positive scalars a₁,…,a_n, with weight vector w ∈ Δ_n. Then we define the S-variational Jensen-Shannon diversity index [24] as

  (10)

  When S_w = A_w (with A_w(a₁,…,a_n) = ∑ _i=1ⁿw_ia_i the arithmetic weighted mean), we recover the ordinary Jensen-Shannon diversity index. More generally, we define the S-Jensen-Shannon index of an arbitrary distance D as

  (11)

  When n = 2, this yields a Jensen-Shannon-symmetrization of distance D.

  The variational optimization defining the JSD can also be constrained to a (parametric) family of densities , thus defining the (S,)-relative Jensen-Shannon diversity index:

  (12)

  The relative Jensen-Shannon divergences are useful for clustering applications: Let p_θ1 and p_θ2 be two densities of an exponential family with cumulant function F(θ). Then the -relative Jensen-Shannon divergence is the Bregman information of ₂(p,q) for the conjugate function F^*(η) = -h[p_θ] (with η = ∇F(θ)). The -relative JSD amounts to a Jensen divergence for F^*:

  

  since η^* := (a right-sided Bregman centroid [26]).

4 Statistical distances between mixtures

Pearson [36] first considered a unimodal Gaussian mixture of two components for modeling distributions crabs in 1894. Statistical mixtures [16] like the Gaussian mixture models (GMMs) are often met in information sciences, and therefore it is important to assess their dissimilarities. Let m(x) = ∑ _i=1^kw_ip_i(x) and m′(x) = ∑ _i=1^k′w_i′p_i′(x) be two finite statistical mixtures. The KLD between two GMMs m and m′ is not analytic [41] because of the log-sum terms:

However, the KLD between two GMMs with the same prescribed components p_i(x) = p_i′(x) = p_μi,Σi(x) (i.e., k = k′, and only the normalized positive weights may differ) is provably a Bregman divergence [28] for the differential negentropy F(θ):

where m(θ) = ∑ _i=1^k-1w_ip_i(x) + (1 -∑ _i=1^k-1w_i)p_k(x) and F(θ) = ∫ m(θ)log m(θ)dx. The family {m_θ  θ ∈ Δ_k-1^∘} is called a mixture family in information geometry, where Δ_k-1^∘ denotes the (k - 1)-dimensional open standard simplex. However, F(θ) is usually not available in closed-form because of the log-sum integral. In some special cases like the mixture of two prescribed Cauchy distributions, we get a closed-form formula for the KLD, JSD, etc. [30, 25]. Thus when dealing with mixtures (like GMMs), we either need efficient approximating (§4.1), bounding (§4.2) KLD techniques, or new distances (§4.3) that yields closed-form formula between mixture densities.

4.1 Approximating and/or fast statistical distances between mixtures

• The Jeffreys divergence (JD) D_J[m,m′] = D_KL[m : m′]+D_KL[m′ : m] between two (Gaussian) MMs is not available in closed-form, and can be estimated using Monte Carlo integration as
  

  where _s = {x₁,…,x_s} are s IID samples from the mid mixture m₁₂(x) := (m(x) + m′(x)) (with lim_s→∞J^s[m,m′] = D_J[m,m′]). In [23], the mixtures m and m′ are converted into densities of an exponential-polynomial family. The JD between densities p_θ and p_θ′ of an exponential family with cumulant function F is available in closed-form:

  

  with η = ∇F(θ) and θ = ∇F^*(η), where F^* denotes the convex conjugate. Any smooth density r (includes a mixture r = m) is converted into close densities p_θr^MLE and p^η_rSME of a exponential-polynomial family using extensions of the Maximum Likelihood Estimator (MLE) and Score Matching Estimator (SME). Then JD between mixtures is approximated as follows

  
• Given a finite set of mixtures {m_i(x)} sharing the same components (e.g., points on a mixture family manifold), we precompute the KLD between pairwise components to obtain fast approximation of the KLD D_KL[m_i : m_j] between any two mixtures m_i and m_j, see [39].

4.2 Bounding statistical distances between mixtures

• Log-Sum-Exp bounds: In [31, 32], we lower and upper bound the cross-entropy between mixtures using the fact that the log-sum term log m(x) and be interpreted as a LSE function. We then compute lower envelopes and upper envelopes of density functions using technique of computational geometry to report deterministic lower and upper bounds on the KLD and α-divergences. These bounds are said combinatorial because we decompose the support into elementary intervals. Bounds between the Total Variation Distance (TVD) between univariate mixtures are reported in [33].

4.3 Newly designed statistical distances yielding closed-form formula for mixtures

• Statistical Minkowski distances [20]: Consider the Lebesgue space
  

  for α ≥ 1, where F denotes the set of all real-valued measurable functions defined on the support . Minkowski’s inequality writes as ∥p + q∥_α ≤∥p∥_α + ∥q∥_α for α ∈ [1,∞). The statistical Minkowski difference distance between p,q ∈ L_α(μ) is defined as

  (18)

  The statistical Minkowski log-ratio distance is defined by:

  (19)

  These statistical Minkowski distances are symmetric, and L_α[p,q] is scale-invariant. For even integers α ≥ 2, D_α^Minkowski[m : m′] is available in closed-form.

• We show that the Cauchy-Schwarz divergence (CSD), the quadratic Jensen-Rényi divergence (JRD), and the total square Distance (TSD) between two GMMs, and more generally two mixtures of exponential families, can be obtained in closed-form in [18].

Initially created 13th August 2021 (last updated August 16, 2021).

References