PaperlayerView exact revision on arXiv

Source-linked AI summary

Estimating Mixture Entropy with Pairwise Distances

Artemy Kolchinsky, Brendan D. Tracey

arXiv:1706.02419v4cs.ITmath.ITstat.MEstat.ML

TL;DR

Mixture entropy is needed in applications including constrained optimization and mutual-information problems. The paper estimates it with a pairwise-distance family that includes lower and upper bounds. The bounds become exact for well-separated clusters, and simulations report better performance than existing well-known estimators.

  • Problem

    Mixture entropy is needed in applications including constrained entropy optimization and mutual-information problems.

    Source: §I · p. 1

  • Method

    The paper defines mixture-entropy estimators through pairwise distances between component densities, including Chernoff lower bounds and KL upper bounds.

    Source: §I · pp. 1–2

  • Results

    The estimator family includes lower and upper bounds that become exact for well-separated clusters, and simulations report better performance than existing well-known estimators.

    Source: §I · p. 2, D. Exact Estimation in the “Clustered”… · p. 5, §VII · p. 11

  • Takeaways & Limitations

    When the pairwise distance is continuous and smooth in mixture parameters, the entropy estimate is also smooth and can be used in gradient-based optimization.

    Source: §VII · p. 11

Abstract

from arXiv · show

Mixture distributions arise in many parametric and non-parametric settings -- for example, in Gaussian mixture models and in non-parametric estimation. It is often necessary to compute the entropy of a mixture, but, in most cases, this quantity has no closed-form expression, making some form of approximation necessary. We propose a family of estimators based on a pairwise distance function between mixture components, and show that this estimator class has many attractive properties. For many distributions of interest, the proposed estimators are efficient to compute, differentiable in the mixture parameters, and become exact when the mixture components are clustered. We prove this family includes lower and upper bounds on the mixture entropy. The Chernoff $\alpha$-divergence gives a lower bound when chosen as the distance function, with the Bhattacharyya distance providing the tightest lower bound for components that are symmetric and members of a location family. The Kullback-Leibler divergence gives an upper bound when used as the distance function. We provide closed-form expressions of these bounds for mixtures of Gaussians, and discuss their applications to the estimation of mutual information. We then demonstrate that our bounds are significantly tighter than well-known existing bounds using numeric simulations. This estimator class is very useful in optimization problems involving maximization/minimization of entropy and mutual information, such as MaxEnt and rate distortion problems.

I. INTRODUCTION

Mixture entropy matters across modeling and optimization, but usually lacks a closed form, while existing analytic estimates can be biased or insensitive to component overlap. The paper proposes pairwise-distance estimators with useful bounds and exactness for separated clusters.

I. INTRODUCTION

  • Mixture entropy estimation is relevant to applications including image retrieval, speech recognition, constrained entropy optimization, and mutual-information or rate-distortion problems.Mixture distributions are used in both parametric models such as Gaussian mixtures and non-parametric methods such as kernel density estimation.Source: §I · p. 1
  • Mixture entropy usually lacks a closed-form expression, and Monte Carlo or numerical integration can be costly, especially for high-dimensional or iterative optimization settings.Analytic alternatives are more efficient but may be biased or insensitive to component overlap.Source: §I · p. 1
  • The proposed estimator family uses pairwise distances between component densities and has bounded bias, smoothness, entropy bounds, and exactness for well-separated clusters.Chernoff α-divergence yields a lower bound, while KL divergence yields an upper bound; Bhattacharyya distance is tightest under symmetric location-family conditions.Source: §I · pp. 1–2

II. BACKGROUND AND DEFINITIONS

  • The conventional entropy bounds do not depend on component overlap and, for Gaussian mixtures, remain invariant to component-mean changes.This makes them unsuitable when optimization adjusts component means.Source: §II · pp. 2–3
  • KDE and Expected Likelihood Kernel estimators are efficient, continuous, differentiable, and overlap-sensitive, but exhibit significant underestimation bias in the reported experiments.For Gaussian mixtures with equal covariance, the KDE estimator is only an additive constant away from an estimator in the proposed class.Source: §II · p. 3

A. Overview

The estimator is defined by a premetric between mixture components and lies between standard entropy bounds. Its bias is bounded, and it can be computed efficiently when component entropies and pairwise distances have closed forms.

A. Overview

  • The estimator uses a nonnegative premetric between component densities that is zero for identical densities; symmetry and the triangle inequality are not required.Its computation is efficient when component entropies and pairwise distances have simple closed forms.Source: A. Overview · p. 3
  • For any allowable distance function, the proposed estimate lies between the conditional-entropy and joint-entropy bounds, and its estimation bias is bounded.The distance function determines where the estimate falls within those bounds.Source: A. Overview · p. 3

B. Lower Bound

Chernoff α-divergences produce lower bounds on mixture entropy for α in [0, 1]. For symmetric location-family components, the Bhattacharyya choice gives the tightest lower bound.

B. Lower Bound

  • For every α in [0, 1], using Chernoff α-divergence as the pairwise distance gives a lower bound on mixture entropy.Values of α outside this interval do not define a valid distance function in the paper’s framework.Source: B. Lower Bound · p. 4
  • Although both the Chernoff lower bound and the Expected Likelihood Kernel lower bound use Jensen’s inequality, they apply it differently and have different empirical performance.The excerpt points to numerical experiments for that performance comparison without specifying the outcome here.Source: B. Lower Bound · p. 4
  • For a general mixture, the paper notes that α can be optimized to find the tightest Chernoff-based lower bound.The α = 0.5 result supplies the tight choice in the symmetric location-family case.Source: B. Lower Bound · p. 4
  • For symmetric components from a location family, α = 0.5 maximizes the Chernoff-based estimator and gives the tightest lower bound.Examples include homoscedastic Gaussian mixtures; the result does not apply to skewed distributions such as the skew-normal.Source: B. Lower Bound · p. 4

C. Upper Bound

Using KL divergence as the pairwise distance gives an upper bound on mixture entropy. In the clustered case, the Chernoff-based lower and KL-based upper bounds converge to the exact entropy under the stated conditions.

C. Upper Bound

  • The KL-divergence pairwise-distance estimator provides an upper bound on mixture entropy.The derivation uses a variational lower bound on an expectation of a log-sum.Source: C. Upper Bound · p. 5

D. Exact Estimation in the “Clustered” Case

  • The lower and upper bounds become similar when component pairs are either very close together or very far apart.In both regimes, the exponential of each distance is approximately one or zero, respectively.Source: D. Exact Estimation in the “Clustered”… · p. 5
  • Components are clustered when within-group KL divergences are small and between-group Bhattacharyya distances are large.The number of groups can range from one, where all components are nearly the same, to N, where all are very different.Source: D. Exact Estimation in the “Clustered”… · p. 5
  • When κ is small and β is large, the lower and upper bounds converge, making the pairwise-distance entropy estimate exact.Their difference decreases at least linearly in κ and exponentially in β.Source: D. Exact Estimation in the “Clustered”… · pp. 5–6
  • Any distance measure bounded between Bhattacharyya distance and KL divergence also gives an exact estimate in the clustered case.The argument can extend to other bounding distances, although some distance-measure and distribution pairs never meet the clustering criterion.Source: D. Exact Estimation in the “Clustered”… · p. 6
  • In the perfectly clustered case, the Bhattacharyya lower bound is at least as good as the Expected Likelihood Kernel lower bound.The paper refers to Appendix B for details.Source: D. Exact Estimation in the “Clustered”… · p. 6

IV. GAUSSIAN MIXTURES

For Gaussian mixtures, the paper gives explicit forms for its Chernoff-based lower and KL-based upper entropy bounds. With equal component covariances, the Bhattacharyya distance gives the tightest Chernoff lower bound, and the KL upper bound is closely related to a kernel density estimator.

IV. GAUSSIAN MIXTURES

  • The paper derives explicit lower and upper entropy bounds for Gaussian mixtures from closed-form Gaussian divergences and component entropies.The expressions are particularly simple when all components have equal covariance matrices.Source: §IV · p. 6
  • For homoscedastic Gaussian mixtures, the Bhattacharyya distance gives the tightest lower bound among the Chernoff α-divergences.It corresponds to α = 0.5.Source: §IV · p. 7
  • For homoscedastic Gaussian mixtures, the KL-based upper-bound expression equals the kernel density estimator plus a dimensional correction.The paper notes this may explain the estimator’s use in optimization despite its lack of a principled entropy-bound justification.Source: §IV · p. 7

V. ESTIMATING MUTUAL INFORMATION

The paper applies mixture-entropy bounds to mutual information, where the received-signal entropy can be harder to compute than the conditional entropy. When the signal distribution is a mixture, pairwise-distance estimates of the received-signal entropy yield lower and upper mutual-information bounds.

V. ESTIMATING MUTUAL INFORMATION

  • The marginal entropy H(X) of received signals is often difficult to compute, while H(X|U) is often easy to compute.U denotes signals sent across the channel and X signals received.Source: §V · p. 7
  • When sent-signal distribution U is a mixture, the received-signal distribution X can also be represented as a mixture.Each received component q_i is formed by integrating the channel distribution against the corresponding sent-signal component.Source: §V · p. 7
  • Pairwise-distance estimates of H(X) provide mutual-information bounds when the received mixture components have tractable entropies and divergences.The method combines the bounds on H(X) with expressions for component-average entropy and H(X|U).Source: §V · p. 7
  • For Gaussian temperature mixtures measured with homoscedastic Gaussian noise, the paper obtains mutual-information bounds by combining mixture-entropy estimates with closed-form conditional entropies.The received Gaussian components have covariance Σ_i + Σ′, while H(X|U) is the entropy of N(0, Σ′).Source: §V · pp. 7–8

VI. NUMERICAL RESULTS

The numerical experiments compare mixture-entropy estimators on Gaussian and uniform mixtures across varied parameter values. The supplied passages describe the estimators and plot format but do not report comparative outcomes.

VI. NUMERICAL RESULTS

  • The experiments evaluate estimators on Gaussian and uniform mixtures across a variety of parameter values.The reference entropy is estimated by Monte Carlo sampling, using 2,000 samples for Gaussian mixtures and 5,000 for uniform mixtures.Source: §VI · p. 8
  • The comparison includes the proposed KL upper bound and Bhattacharyya lower bound alongside KDE, Expected Likelihood Kernel, conditional-entropy, and joint-entropy estimators.Monte Carlo estimates serve as the reference; the conditional- and joint-entropy bounds are also included.Source: §VI · p. 8
  • Estimator values are plotted as lines, while the region between the conditional- and joint-entropy bounds is shaded green.The text does not state which estimator performs best.Source: §VI · p. 8

A. Mixture of Gaussians

Across four Gaussian-mixture experiments, the proposed bounds estimate entropy accurately across changing means, covariances, cluster separation, and dimension. They become tight at the clustering extremes but are less tight in intermediate regimes.

A. Mixture of Gaussians

  • The proposed bounds stay close to true entropy across mean separation and dimension, but are less tight when components lack clear clustering.They become tight when components overlap heavily or form well-separated clusters.Source: A. Mixture of Gaussians · pp. 8–9, Figure 1 · p. 9
  • As Gaussian means separate, the proposed bounds approach true entropy at both extremes, and the ELK lower bound is strictly worse than the Bhattacharyya-based estimate.The extremes correspond to nearly identical components and components far apart; the KDE estimate differs from the KL estimate by exactly d/2.Source: A. Mixture of Gaussians · p. 8, Figure 1 · p. 9
  • With covariance matrices becoming more similar, small n yields a nearly one-component-per-cluster case where both bounds are highly accurate; large n approaches the first experiment’s σ = 1 case.Source: A. Mixture of Gaussians · p. 8, Figure 1 · p. 9
  • For five Gaussian clusters, the bounds remain accurate as cluster centers separate, while H(X, C) differs significantly from true entropy even at large separations.The bounds become exact when all clusters coincide and when they are very far apart.Source: A. Mixture of Gaussians · p. 8, Figure 1 · p. 9
  • Across dimensions 1–60, the proposed lower and upper bounds estimate mixture entropy well, while the ELK estimate becomes less accurate as dimension increases.The KDE and KL estimates diverge at a rate of d/2 as dimension grows.Source: A. Mixture of Gaussians · pp. 8–9, Figure 1 · p. 9

B. Mixture of Uniforms

For uniform mixtures, the Bhattacharyya-based estimate provides a useful lower bound across varied component sizes, cluster separation, and dimensions. The KL-based upper bound’s behavior depends on overlap and support: it can match H(X, C) or outperform it.

B. Mixture of Uniforms

  • For equal-sized uniforms with distinct means, pairwise KL distances are infinite, making the KL-based estimate equal H(X, C); the Bhattacharyya-based estimate tracks true entropy well.For equal-sized uniform components, the ELK and Bhattacharyya-based estimates are equal.Source: B. Mixture of Uniforms · pp. 10–11, Figure 2 · p. 10
  • The Bhattacharyya-based estimate provides a tight lower bound across component-size variation, cluster separation, and dimensions.Source: Figure 2 · p. 10, B. Mixture of Uniforms · p. 11
  • As uniform component sizes become more similar, the Bhattacharyya-based estimate outperforms the other estimators, and the lower and upper bounds tightly estimate true entropy.The KL-based estimate need not equal H(X, C) when supports overlap.Source: Figure 2 · p. 10, B. Mixture of Uniforms · p. 11
  • With five clusters of perfectly overlapping uniform components, the KL-based upper bound significantly outperforms H(X, C), while the Bhattacharyya-based estimate remains a relatively accurate lower bound.Source: Figure 2 · p. 10, B. Mixture of Uniforms · p. 11
  • As dimension increases from 1 to 16, the Bhattacharyya-based estimate remains a tight lower bound, while the KL-based estimate equals H(X, C).The true entropy shifts from being close to H(X|C) at low dimensions toward H(X, C) at high dimensions.Source: Figure 2 · p. 10, B. Mixture of Uniforms · p. 11

VII. DISCUSSION

The paper presents pairwise-distance estimators that provide bounded-bias estimates and useful lower and upper bounds on mixture entropy, becoming exact for well-separated clusters. Simulations show stronger performance than well-known existing estimators, and the authors note that optimality of the bounds remains unproved.

VII. DISCUSSION

  • The pairwise-distance estimator class has bounded estimation bias and includes useful lower and upper bounds on mixture entropy.The derivation uses existing results, which the authors say had not previously been used to estimate mixture entropy or compared with better-known bounds.Source: §VII · p. 11
  • Simulations on Gaussian and bounded (hypercube) uniform mixtures show the estimators perform much better than existing well-known estimators.The bounds also become exact when mixture components are grouped into well-separated clusters.Source: §VII · p. 11
  • When the pairwise distance is continuous and smooth in mixture parameters, the entropy estimate is also smooth and can be used with gradient-based optimization.The paper names gradient descent as an example.Source: §VII · p. 11
  • The authors report using their upper bound to minimize mutual information between neural-network input and hidden layers in a nonlinear Information Bottleneck implementation [43].The optimal distributions were often clustered; the authors cite this work as demonstrating the practical value of an accurate, differentiable upper bound in that regime [11].Source: §VII · p. 11
  • The paper does not prove that its bounds are the best possible; identifying better bounds or proving optimality within a class remains future work.Source: §VII · p. 11

Appendix A: Chernoff α-Divergence Is Not a Distance Function for α /∈[0, 1]

Appendix A shows that Chernoff α-divergence is not a valid distance function outside α ∈ [0, 1]. Appendix B states a perfect-clustering assumption for its comparison of the Bhattacharyya-distance and Expected Likelihood Kernel estimators.

Appendix A: Chernoff α-Divergence Is Not a Distance Function for α /∈[0, 1]

  • For distinct densities, cα is strictly convex and equals 1 at α = 0 and α = 1, so it exceeds 1 outside [0, 1].Source: Appendix A · p. 12
  • Because cα exceeds 1 outside [0, 1], Chernoff α-divergence is negative there and is not a valid distance function under the paper’s definition.Source: Appendix A · p. 12

Appendix B: For Clustered Mixtures, ˆ HBD ≥ˆ HELK

  • The Appendix B comparison assumes perfect clustering, beginning with the condition that components assigned to the same group satisfy a specified relation.Source: Appendix B · p. 12
Loading 1706.02419v4…