Estimating Mixture Entropy with Pairwise Distances
Artemy Kolchinsky

1,∗

and Brendan D. Tracey

1,2,†

1

arXiv:1706.02419v3 [cs.IT] 8 Nov 2017

2

Santa Fe Institute
Massachusetts Institute of Technology
∗
artemyk@gmail.com
†
btracey@santafe.edu

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 α-divergence gives a lower bound when chosen as
the distance function, with the Bhattacharyaa 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 pairwise 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

A mixture distribution is a probability distribution whose density function is a weighted sum of
individual densities. Mixture distributions are a common choice for modeling probability distributions, in both parametric settings, for example learning a mixture of Gaussians statistical model,
and non-parametric settings, such as kernel density estimation.
It is often necessary to compute the differential entropy [6] of a mixture distribution, which is
a measure of the inherent uncertainty in the outcome of X. Entropy estimation arises in image
retrieval tasks [10], image alignment and error correction [33], speech recognition [3, 14], analysis
of debris spread in rocket launch failures [2], and many other settings. Entropy also arises in
optimization contexts [28–30, 33], where it is minimized or maximized under some constraints (e.g.,
MaxEnt problems). Finally, entropy also plays a central role in minimization or maximization of
mutual information, such as in problems related to rate distortion [20].
Unfortunately, in most cases, the entropy of a mixture distribution has no known closed-form
expression. This is true even when the entropy of each component distribution does have a known
closed-form expression. For instance, the entropy of a Gaussian has a well-known form, while the
entropy of a mixture of Gaussians does not. As a result, the problem of finding a tractable and
accurate estimate for mixture entropy has been described as “a problem of considerable current
interest and practical significance” [35].
One way to approximate the entropy is with Monte Carlo (MC) sampling. MC sampling provides an unbiased estimate of mixture entropy, and this estimate can become arbitrarily accurate
by increasing the number of MC samples. Unfortunately, MC sampling is very computationally
intensive as for each sample, the (log) probability of the sample location must be computed under
every component in the mixture. MC sampling typically requires a large number of samples to

2
estimate entropy, especially in high-dimensions. Sampling is thus typically impractical, especially
for optimization problems where for every parameter change a new entropy estimate is required.
An alternative to Monte Carlo sampling is to use an analytic estimator of mixture entropy.
Analytic estimators have estimation bias, but are much more computationally efficient. There are
several existing analytic estimators of entropy, discussed in-depth below. To summarize, however,
commonly-used estimators have significant drawbacks: they have large bias relative to the true
entropy, and/or they are invariant to the amount of “overlap” between mixture components. For
example, many estimators do not depend on the locations of the means in a Gaussian mixture
model.
In this paper, we introduce a novel family of estimators for the mixture entropy. Each member of
this family is defined via a pairwise-distance function between component densities. The estimators
in this family have several attractive properties. They are computationally efficient, as long as the
pairwise-distance function and the entropy of each component distribution are easy to compute.
The estimation bias of any member of this family is bounded by a constant. The estimator is
continuous and smooth and is therefore useful for optimization problems. In addition, we show that
the Chernoff α-divergence (i.e., a scaled Rényi divergence), used as a pairwise-distance function,
gives a lower-bound on the mixture entropy; in particular, the Bhattacharrya distance (α = 0.5)
provides the tightest lower bound of all Chernoff α-divergences when the mixture components are
symmetric and belong to a location family (such as a mixture of Gaussians with equal covariances).
We also show the Kullback-Leibler [KL] divergence, when used as a pairwise-distance function,
gives an upper-bound on the mixture entropy. Finally, our family of estimators can compute the
exact mixture entropy when the component distributions are grouped into well-separated clusters,
a property not shared by other analytic estimators of entropy. In particular, the bounds mentioned
above converge to the same value for well-separated clusters.
A layout of the paper is as follows. We first review mixture distributions and entropy estimation
in Section II. We then present the pairwise distance estimator in Section III, prove bounds on
the error of any estimator in this class, and show distance functions that bound the entropy as
discussed above. In Section IV, we consider the special case of mixtures of Gaussians, and give
explicit expressions for lower and upper bounds on the mixture entropy. When all the Gaussian
components have the same covariance matrix, we show that these bounds have particularly simple
expressions. Then in Section V, we consider the closely related problem of estimating the mutual
information between two random variables, and show that our estimators and bounds can be directly
used to estimate the mutual information. Specializing to the Gaussian case, we show how this can
be used to bound the mutual information across a type of Additive White Noise Gaussian channel.
Finally, in Section VI, we run numerical experiments and compare the performance of our lower
and upper bounds relative to existing estimators. We consider both mixtures of Gaussians and
mixtures of uniform distributions.

II.

BACKGROUND AND DEFINITIONS

We consider the differential entropy, defined as

Z
H(X) := −

pX (x) ln pX (x) dx ,

3
of the mixture distribution pX ,
pX (x) =

N
X

ci pi (x) ,

i=1

where ci indicates the weight of component i (ci ≥ 0,
of component i.

P

i ci

= 1) and pi is the probability density

We can treat the set of component weights as a discrete random variable C with outcomes 1..N ,
where Pr(C = i) = ci . Consider the mixed joint distribution of the discrete random variable C and
the continuous random variable X,
pX,C (x, i) = pi (x)ci ,
and observe that the common identities for conditional and joint entropy still apply [21],
H (X, C) = H (X|C) + H (C) = H (C|X) + H (X)
where we use H for discrete and differential entropy interchangeably. Here the conditional entropies
are
Z
X
pi (x)ci
dx .
H(X|C) =
ci H(pi )
and
H(C|X) = pi (x)ci log
pX (x)
i

Using elementary results from information theory [6], H(X) can be bounded from below by
H(X) ≥ H(X|C) ,

(1)

since conditioning can only decrease entropy. Similarly, H(X) can be bounded from above by
H(X) ≤ H(X, C) = H(X|C) + H(C) ,

(2)

following from H(X) = H(X, C) − H(C|X) and the non-negativity of the conditional discrete
entropy H(C|X). This upper bound on the mixture entropy was previously proposed by Huber et
al. [16].
It is easy to see that the bound in Eq. (1) is tight when all the components have the same
distribution, since then H(pX ) = H(pi ) for all i. The bound in Eq. (2) becomes tight when
H(C|X) = 0, i.e., when any sample from pX uniquely determines the component identity C. This
occurs when the different mixture components have non-overlapping supports, pi (x) > 0 =⇒
pj (x) = 0 for all x and i 6= j. More generally, the bound of Eq. (2) becomes increasingly tight as
the mixture distributions move farther apart from one another.
Assuming that H(pi ), the entropy of each individual component density, has a simple closed
form expression, the bounds in Eq. (1) and Eq. (2) can be computed quickly. However, neither
bound depends on the “overlap” between components. For instance, in a Gaussian mixture model
these bounds are invariant to changes in the component means. The bounds are thus unsuitable for
many problems; for instance, in optimization one typically tunes parameters to adjust component
means, but the above entropy bounds remain the same for regardless of mean location.
There are two other estimators of the mixture entropy that should be mentioned. The first
estimator is based on kernel density estimation [11, 19]. It estimates the entropy using the average

4
probability of the component means, µi ,
ĤKDE (X) := −

X

ci ln

X

i

cj pj (µi ) .

(3)

j

The second estimator is a lower bound that is derived using Jensen’s inequality, −E [ln f (X)] ≥
− ln [E(f (X))], giving

Z X
X
X
X Z
H(X) := −
pi (x)pj (x) dx =: ĤELK . (4)
ci pi (x) ln
cj pj (x) dx ≥ −
ci ln
cj
i

j

i

j

R

In the literature, the term pi (x)pj (x) dx has been referred to as the “Cross Information Potential”
[26, 34] and the “Expected Likelihood Kernel” [17, 18] [ELK] (we use this second acronym to label
this estimator). When the component distributions are Gaussian, pi (x) := N (x; µi , Σi ), the ELK
has a simple closed-form expression, giving the lower bound
X
X
ci ln
cj N (µi ; µj , Σi + Σj ) .
(5)
H(X) ≥ −
i

j

This lower bound was previously proposed for Gaussian mixtures in [16]. Both of the estimators
in Eq. (3) and Eq. (5) are computationally efficient, continuous and differentiable, and depend on
component overlap, making them suitable for optimization. However, as will be shown via numerical
experiments (Section VI), they exhibit significant underestimation bias. However, we will also show
that for Gaussian mixtures with equal covariance, Eq. (3) plus an additive constant is actually an
estimator in our proposed class.

III.

ESTIMATORS BASED ON PAIRWISE-DISTANCES
A.

Overview

Let D(pi kpj ) be some (generalized) distance function between probability densities pi and pj .
Formally, we assume that D is a premetric, meaning that it is non-negative and D(pi kpj ) = 0 if
pi = pj . We do not assume that D is symmetric, nor that it obeys the triangle inequality, nor that
it is strictly greater than 0 when pi 6= pj .
For any allowable distance function D, we propose the following entropy estimator:
X
X
ĤD (X) := H(X|C) −
ci ln
cj exp(−D(pi kpj )) .
i

(6)

j

This estimator can be efficiently computed if the entropy of each component and D(pi kpj ) for all
i, j have simple closed-form expressions. There are many distribution-distance function pairs that
satisfy these conditions (e.g., Kullback-Leibler divergence, Renyi divergences, Bregman divergences,
f-divergences, etc. for Gaussian, uniform, exponential, etc.) [1, 4, 5, 7, 9].
It is straightforward to show that for any D, ĤD falls between the bounds of Eq. (1) and Eq. (2),
H(X|C) ≤ ĤD (X) ≤ H(X, C) .

(7)

5
To do so, consider the “smallest” and “largest” allowable distance functions,
(
0 if pi = pj
Dmin (pi kpj ) = 0
and
Dmax (Xi kXj ) =
∞ otherwise

(8)

For any D and pi , pj , Dmin (pi kpj ) ≤ D(pi kpj ) ≤ Dmax (pi kpj ), thus
ĤDmin (X) ≤ ĤD (X) ≤ ĤDmax (X)
P
Plugging Dmin into Eq. (6) (noting that j cj = 1) gives ĤDmin (X) = H(X|C), while plugging
Dmax into Eq. (6) gives


X
X
X
ĤDmax = H (X|C) −
ci ln ci +
cj e−Dmax (Xi kXj ) ≤ H (X|C) −
ci ln ci = H(X, C)
i

i

j6=i

These two inequalities yield Eq. (7). The true entropy, as shown in Section II, also obeys H (X|C) ≤
H (X) ≤ H (X, C). The magnitude of the bias of ĤD is thus bounded by
ĤD (X) − H(X) ≤ H (X, C) − H (X|C) = H(C) .
In the next two subsections, we improve upon the bounds suggested in Eq. (1) and Eq. (2), by
examining bounds induced by particular distance functions.

B.

Lower Bound

Consider the “Chernoff α-divergence” [7, 22] for some real-valued α, defined as
Z
Cα (pkq) := − ln pα (x)q 1−α (x) dx .

(9)

Note that Cα (pkq) = (1 − α)Rα (pkq), where Rα is Rényi divergence of order α [32].
We show that for any α ∈ [0, 1], ĤCα (X) is a lower bound on the entropy (for α ∈
/ [0, 1], Cα is
not a valid distance function, see the Appendix). To do so, note that
H(X) = H(X|C) + M I(X; C)

(10)

where M I is mutual information. Using a derivation from [12], we bound M I from below,
Z X
pX (x)
dx
M I(X; C) = −
ci pi (x) ln
pi (x)
i
!
P
Z X
Z X
1−α
c
p
(x)
j
j
pX (x)
j
=−
ci pi (x) ln
dx
ci pi (x) ln
αP
1−α dx −
p
(x)
c
p
(x)
pi (x)1−α
i
j j j
i
i
!
P
Z X
1−α
(a)
j cj pj (x)
≥−
ci pi (x) ln
dx
1−α
p
(x)
i
i
Z
X
X
(b)
≥−
ci ln pi (x)α
cj pj (x)1−α dx
i

j

6
=−

X
i

ci ln

X

cj e−Cα (Xi kXj ) .

(11)

j

The inequalities (a) and (b) follow from Jensen’s inequality. This inequality is used directly in (b),
while in (a) it follows from
Z X
Z X
pX (x)
pX (x)
dx
≥
−
ln
ci pi (x)
−
ci pi (x) ln
P
α
1−α
αP
1−α dx
p
(x)
c
p
(x)
p
(x)
c
p
(x)
j
j
j
j
i
i
j
j
i
i
Z X
pX (x)
= − ln
ci pi (x)1−α P
1−α dx
j cj pj (x)
i
X Z
= − ln
ci pX (x) dx = 0
i

Combining gives
H(X) ≥ ĤCα (X) .
This shows that using Cα as a distance function gives a lower bound on the mixture entropy for
any α ∈ [0, 1]. For a general mixture distribution, one could optimize over the value of α to find
the tightest lower bound. We can show that the tightest bound is achieved α = 0.5 in the special
case when all of the mixture components pi are symmetric and come from a location family,
pi (x) = b(x − µi ) = b(µi − x)
Examples of this situation include mixtures of Gaussians with the same covariance (“homoscedastic”
mixtures), multivariate t-distributions with the same covariance, location-shifted bounded uniform
distributions, most kernels used in kernel density estimation, etc.
To show that α = 0.5 is optimal, first define the Chernoff α-coefficient as
Z
cα (pi kpj ) := pi (x)α pj (x)1−α dx .
(Hence, the Chernoff α-divergence is the negative logarithm of the Chernoff α-coefficient.) We show
that for any pair pi , pj of symmetric distributions from a location family, cα (pj kpj ) is minimized by
α = 0.5. This means that all pairwise distances Cα are maximized by α = 0.5, and therefore the
entropy estimator HCα (Eq. (6)) is maximized by α = 0.5.
Define a change of variables
y := µi + µj − x ,
which gives x − µi = µj − y and x − µj = µi − y. This allows us to write the Chernoff α-coefficient
as
Z
cα (pi kpj ) = pi (x)α pj (x)1−α dx
Z
= b(x − µi )α b(x − µj )1−α dx
Z
(a)
= b(µj − y)α b(µi − y)1−α dy
Z
(b)
= b(y − µj )α b(y − µi )1−α dy

7
=c1−α (pi kpj )
where in (a) we’ve substituted variables, and in (b) we used the assumption that b(x) = b(−x).
Since cα (pi kpj ) = c1−α (pi kpj ), cα is symmetric in α about α = 0.5. In the Appendix, we show that
cα (pkq) is everywhere convex in α. Together, this means that cα (pi kpj ) must achieve a minimum
value at α = 0.5. This value of α is a special case of the Chernoff α-coefficient, known as the
Bhattacharyya coefficient, with the corresponding Bhattacharyya distance [8] defined as,
Z p
BD(pkq) := − ln
p(x)q(x)dx = C0.5 (pkq)
Since any Chernoff α-divergence is a lower bound for the entropy, we write the particular case of
Bhattacharyya-distance lower bound as
X
X
H(X) ≥ ĤBD (X) := H(X|C) −
ci ln
cj e−BD(pi kpj ) .
(12)
i

C.

j

Upper bound

The Kullback-Leibler [KL] divergence [6], defined as
Z
p(x)
KL(pkq) := p(x) ln
dx ,
q(x)
provides an upper bound for the estimate of mixture entropy. We show this as follows:


X
X
H(X) = −
ci Epi ln
cj pj (x)
i
(a)

≤−

X

=−

ci ln

X

i

j

X

ci ln

X

i

=

j

X

cj eEpi [ln pj (x)]
cj e−H(pi kpj )

j

ci H(Xi ) −

X

i

ci ln

X

i

cj e−KL(pi kpj )

j

where we use H(·k·) to indicate the cross-entropy function, and employ the identity H(pi kpj ) =
H(pi ) + KL(pi kpj ). The inequality in step (a) uses a variational lower bound on the expectation of
a log-sum [14, 24],


X
X
E ln
Zj  ≥ ln
exp (E [ln Zj ]) .
j

j

Combining gives the upper bound
H(X) ≤ ĤKL := H(X|C) −

X
i

ci ln

X
j

cj e−KL(pi kpj ) .

(13)

8
D.

Exact estimation in the “clustered” case

In the previous sections, we described lower and upper bounds on the mixture entropy in the
general case. In this section, we show that in the special case when the mixture components are
“clustered” into well-separated groups, these lower and upper bounds become equal, and so the
pairwise-distance estimate of the entropy is tight. By “clustered”, we mean that there is a grouping
of component distributions such that distributions in the same group are approximately the same,
while distributions assigned to different groups are very different from one another. Though this
situation may seem like an edge case, clustered distributions do arise in mixture estimation, e.g.,
when there are repeated data points, and we have encountered it as solutions to informationtheoretic optimization problems [20]. Note that the number of groups is arbitrary, and therefore
this situation includes the extreme cases of a single group (all component distributions are nearly
the same) as well as N different groups (all component distributions are very different).
Formally, let the function g(i) indicate the group of component i. We define that the components
are “clustered” with respect to grouping g iff KL(pi kpj ) ≤ κ whenever g(i) = g(j) forP
some small κ,
and BD(pi kpj ) ≥ β whenever g(i) 6= g(j) some large β. We use the notation pG (k) = i δ(g(i), k)ci
to indicate the sum of the weights of the components in group k.
We show that when κ is small and β is large, both ĤCα for α ∈ (0, 1] and ĤKL approach
X
H(X|C) −
pG (k) ln pG (k) .
k

Since one is a lower bound and one is an upper bound on the true entropy, the estimators become
exact as they converge in value.
Recall that BD = C0.5 . For α ∈ (0, 1], α−1 Cα (pkq) is a monotonically decreasing function for
α ∈ (0, 1] [27], meaning that Cα ≥ 2αBD(pkq) for α ∈ (0, 0.5]. In addition, (1 − α)−1 Cα (pkq) is a
monotonically increasing function for α > 0 [27], thus Cα ≥ 2(1 − α)BD(pkq) for α ∈ [0.5, 1]. Using
the assumption that BD(pi kpj ) ≥ β and combining gives the bound
Cα (pkq) ≥ (1 − |1 − α|)β
for α ∈ (0, 1], leading to
ĤCα (X) := H(X|C) −

X

ci ln

X

i

≥ H(X|C) −

X

≥ H(X|C) −

X

cj exp(−Cα (pi kpj ))

j



X
X
ci ln 
δ(g(i), g(j))ci +
(1 − δ(g(i), g(j)))cj exp(−Cα (pi kpj ))

i

j

j

pG (k) ln [pG (k) + (1 − pG (k)) exp(−(1 − |1 − α|)β)] .

k

In the second line, for i, j in the same group, we’ve used that Cα (pi kpj ) ≥ 0.
For the upper bound ĤKL , we use that KL(pi kpj ) ≤ κ for i and j in the same group, and
otherwise exp(−KL(pi kpj )) ≥ 0. This gives the bound
X
X
ĤKL (X) := H(X|C) −
ci ln
cj exp(−KL(pi kpj ))
i

j



X
X
X
≤ H(X|C) −
ci ln 
δ(g(i), g(j))ci e−κ +
(1 − δ(g(i), g(j)))cj exp(−KL(pi kpj ))
i

j

j

9
≤ H(X|C) −

X

pG (k) ln pG (k)e−κ

k

The difference between the bounds is bounded by

ĤKL (X) − ĤCα (X) ≤ κ +

X

≤κ+

X

k



(1 − pG (k)) exp(−(1 − |1 − α|)β)
pG (k) ln 1 +
pG (k)
pG (k)

k



(1 − pG (k)) exp(−(1 − |1 − α|)β)
pG (k)

= κ + (|G| − 1) exp(−(1 − |1 − α|)β)
where |G| is the number of groups. Thus, the difference decreases at least linearly in κ and exponentially in β. This shows that in the clustered case, when κ ≈ 0 and β is very large, our lower
and upper bounds become exact.
It also shows that any distance measure bounded between BD and KL also gives an exact
estimate of entropy in the clustered case. Furthermore, the idea behind this proof can be extended
to estimators induced by other bounding distance function, beyond BD and KL, so as to show that
a particular estimator converges to an exact entropy estimate in the clustered case. Note, however,
that for some distribution-distance pairs the components will never be considered as “clustered”;
e.g., the α-Chernoff distance for α = 0 between any two Gaussians is 0, and so a Gaussian mixture
distributions will never be considered clustered according to this distance.

IV.

GAUSSIAN MIXTURES

Gaussians are very frequently used as components in a mixture distributions. Our family of
estimators is well-suited to estimating the entropies of Gaussian mixtures, since the entropy of a
d-dimensional Gaussian Xi ∼ N (µi , Σi ) has a simple closed-form expression,
H (Xi ) =

1
[ln |Σi | + d ln 2π + d] ,
2

(14)

and because there are many distance functions between Gaussians with closed-form expressions
(KL divergence, the Chernoffα-divergences, Wasserstein distance, etc.). In this section, we consider
Gaussian mixtures and state explicit expression for the lower and upper bounds derived in the
previous section. We also consider these bounds in the special case where all Gaussian components
have the same covariance matrix (homoscedastic mixtures).
We first consider the lower bound, ĤCα , based on the Chernoff α-divergence distance function.
For two multivariate Gaussians p1 ∼ N (µ1 , Σ1 ) and p2 ∼ N (µ2 , Σ2 ), this distance is defined as
[13, Eq. 6]


(1 − α) α
1
|(1 − α)Σ1 + αΣ2 |
−1
T
Cα (p1 kp2 ) =
(µ1 − µ2 ) ((1 − α)Σ1 + αΣ2 ) (µ1 − µ2 ) + ln
.
2
2
|Σ1 |1−α |Σ2 |α
(15)
(As a warning, note that most sources show erroneous expressions for the Chernoff and/or Rényi
α-divergence between two multivariate Gaussians including [25, p. 33], [15, Eq. 2.5], [22, Eq. 25],
[9], [23, Eq. 36], and even a late draft of this manuscript.)
For the upper bound HKL , the KL divergence between two multivariate Gaussians p1 ∼

10
N (µ1 , Σ1 ) and p2 ∼ N (µ2 , Σ2 ) is
i

1h
−1
KL(p1 kp2 ) =
ln |Σ2 | − ln |Σ1 | + (µ1 − µ2 )T Σ−1
(µ
−
µ
)
+
tr
Σ
Σ
−
d
.
1
1
2
2
j
2

(16)

The appropriate lower and upper bounds can be computed by plugging in Eq. (15) and Section IV
into Eq. (6).
These bounds have simple forms when all of the mixture components have equal covariance
matrices, i.e., Σi = Σ for all i. First, define a transformation in which each Gaussian component pj
is mapped to a different Gaussian p̃j,α , which has the same mean but where the covariance matrix
1
is rescaled by α(1−α)
,
pj := N (µj , Σ)

7→

p̃j,α


:= N µj ,


1
Σ .
α(1 − α)

Then, the lower bound of Eq. (11) can be written as
ĤCα =

X
X
d d
+ ln (α(1 − α)) −
ci ln
cj p̃j,α (µi ) .
2 2
i

j

This is derived by combining the expressions for Cα , Eq. (15), the entropy of a Gaussian, Eq. (14),
and the Gaussian density function. For a homoscedastic mixture, the tightest lower bound among
the Chernoff α-divergences is given by α = 0.5, corresponding to the Bhattacharyya distance,
ĤBD =

X
d d 1 X
+ ln −
ci ln
cj p̃j,0.5 (µi ) .
2 2 4
i

j

(This is derived above in Section III B.)
For the upper bound, when all Gaussians have the same covariance matrix, we again combine
the expressions for KL, Section IV, the entropy of a Gaussian, Eq. (14), and the Gaussian p.d.f. to
give
ĤKL (X) =

X
d X
−
ci ln
cj pj (µi ) .
2
i

j

Note that this is exactly the expression for the kernel density estimator ĤKDE (Eq. (3)), plus a dimensional correction. Thus, surprisingly ĤKDE is a reasonable entropy estimator for homoscedastic
Gaussian mixtures, since it is only an additive constant away from KL-distance based estimator
ĤKL (which has various beneficial properties, as described above). This may explain why ĤKDE
has been used effectively in optimization contexts [28–30, 33], where the additive constant is often
irrelevant, despite lacking a principled justification in terms of being a a bound on entropy.

V.

ESTIMATING MUTUAL INFORMATION

It is often of interest, for example in rate distortion problems and related problems [20], to
calculate the mutual information across a communication channel,
M I(X; U ) = H(X) − H(X|U ),

11
where U is the distribution of signals sent across the channel, and X is the distribution of messages
received on the other end of the channel. As with mixture distributions, it is often easy to compute
H(X|U ), the entropy of the received signal given the sent signal (i.e., the distribution of noise on
the channel). The entropy of the received signals, H(X), on the other hand, is often difficult to
compute.
In some cases, the distribution of U may be well approximated by a mixture model. In this case,
we can estimate the entropy of the received signals, H(X), using our pairwise distance estimators,
as discussed in Section III. In particular, we have the lower bound
X
X
M I(X; U ) ≥ −
ci ln
cj exp(−Cα (pi kpj )),
i

j

and the upper bound,
M I(X; U ) ≤ −

X
i

ci ln

X

cj exp(−KL(pi kpj )),

j

where pi is the density of component i, and noting that the H(X|U ) terms cancel in the expression.
P
P
This also illuminates that the actual pairwise portion of the estimator, − i wi ln j wj exp(−D(pi kpj ))
is a measure of the mutual information between the random variable specifying the component
and the random variable generated from the mixture distribution. If the components are identical,
this mutual information is zero, since knowing the component tells you nothing about the value of
X. On the other hand, when all of the components are very different from one another, knowing
the component that generated X is very informative, giving the maximum amount of information,
H(C).
As a practical example, consider a scenario in which U is a random variable representing outside temperature on any particular day. This temperature is measured with a thermometer with
Gaussian measurement noise (the “Additive White Noise Gaussian channel”). This gives our measurement distribution

X = U + N 0, Σ0 .
If the actual temperature distribution is (approximately or exactly) distributed as a mixture of M
Gaussians, each one having mixture weight ci , mean µi , and covariance matrix Σi , then X will also
be distributed as a mixture of M Gaussians, each with weight ci , mean µi , and covariance matrix
Σ0j := Σi + Σ0 . We can then use our estimators to estimate the mutual information between actual
temperature, U , and thermometer measurements, X.

VI.

NUMERICAL RESULTS

In this section, we run numerical experiments and compare estimators of mixture entropy under
a variety of conditions. We consider two different types of mixtures, mixtures of Gaussians and
mixtures of uniform distributions, for a variety of parameter values. We evaluate the following
estimators:
1. The true entropy, H(X), as estimated by a Monte-Carlo sampling of the mixture model.
2,000 samples were used for each MC estimate for the mixtures of Gaussians, and 5,000
samples were used for the mixtures of uniform distributions.
2. Our proposed upper-bound, based on the KL divergence, ĤKL (Eq. (13))

12
3. Our proposed lower-bound, based on the Bhattacharyya distance, ĤBD (Eq. (12))
4. The kernel density estimate based on the component means, ĤKDE (Eq. (3))
5. The lower bound based on the “Expected Likelihood Kernel”, ĤELK (Eq. (4))
6. The lower bound based on the conditional entropy, H(X|C) (Eq. (1))
7. The upper bound based on the joint entropy, H(X, C) (Eq. (2)).
We show the values of the estimators 1-5 as line plots, while the region between the conditional (6)
and joint entropy (7) is shown in shaded green. The code for these figures can be found at http://
www.github.com/btracey/mixent, and uses the Gonum numeric library http://www.gonum.org.
A

B
Entropy (nats)

Entropy (nats)

18

15

12

9

18

15

12

9
-2

-1

0

1

0

2

Ln(Mean Spread)

D

18

Entropy (nats)

Entropy (nats)

C

4

6

Ln(Covariance Similarity)

15

12

40

30

Monte Carlo
Pair Dist: KL
Pair Dist: Bhat.
KDE
Exp. Lik. Ker.
[H(X|C), H(X,C)]

20

10

9

0
-2

-1

0

Ln(Cluster Spread)

8

16

24

Dimension

Figure 1: Entropy estimates for a mixture of a 100 Gaussians. In each plot, the vertical axis shows the
entropy of the distribution, and the horizontal axis changes a feature of the components: A) the distance
between means is increased; B) the component covariances become more similar (at the right side of the
plot, all Gaussians have covariance ≈ I); C) the components are grouped into 5 “clusters”, and the distance
between the locations of the clusters is increased; D) the dimension is increased.

A.

Mixture of Gaussians

In the first experiment, we evaluate the estimators on a mixture of randomly placed Gaussians,
and look at their behavior as the distance between the means of the Gaussians increases. The
mixture is composed of 100 10-dimensional Gaussians, each Gaussian Xi ∼ N (µi , I), with means
are sampled from µi ∼N (0, σI). Fig. 1A depicts the change in estimated entropy as the means grow
farther apart, in particular a function of ln(σ). We see that our proposed bounds are the closest
to the true entropy over the whole range, and in the extremes, we see that our proposed bounds

13
approach the exact value of the true entropy. This is as expected, since as σ → 0 all of the Gaussian
mixture components become identical, and as σ → ∞ all of the Gaussian components grow very
far apart, approaching the case where each Gaussian is in its own “cluster”. The ELK lower bound
is a strictly worse estimate than ĤBD , in this experiment. As expected, we also observe that the
KDE estimator differs by exactly d/2 from the KL estimator.
In the second experiment, we evaluate the entropy estimators as the covariance matrices change
from less to more similar. We again generate 100 10-dimensional Gaussians. Each Gaussian is
1
distributed as Xi ∼ N (µi , Σi ), where now µi ∼N (0, I) and Σi ∼ W( d+n
I, n), where W is a
Wishart distribution with n degrees of freedom. Fig. 1B compares the the estimators with the true
entropy as a function of ln(n). When n is small, the Wishart distribution is broad and the covariance
matrices differ significantly from one another, while as n → ∞, all the covariance matrices become
close to the identity I. Thus, for small n, we essentially recover a “clustered” case, in which every
component is in its own cluster and our lower and upper bounds giving highly accurate estimates.
For large n, we converge to the σ = 1 case of the first experiment.
In the third experiment, we again generate a mixture of 100 10-dimensional Gaussians. Now,
however, the Gaussians are grouped into 5 “clusters”, with each Gaussian component randomly
assigned to one of the clusters. We use g(i) ∈ {1..5} to indicate the group of each Gaussian’s
component i ∈ {1..100}, and each of the 100 Gaussians is distributed as Xi ∼ N (µ̃g(i) , I). The
cluster means µ̃k for k ∈ {1..5} are drawn from N (0, σI). The results are depicted in Fig. 1C. In the
first experiment, we saw that the joint entropy H(X, C) became an increasingly better estimator as
the Gaussians grew increasingly far apart. Here, however, we see that there is a significant difference
between H(X, C) and the true entropy, even as the groups become increasingly separated. Our
proposed bounds, on the other hand, provide accurate estimates of the entropy across the entire
parameter sweep. As expected, they become exact in the limits of all clusters being at the same
location, and all clusters being very far apart from each other.
Finally, we evaluate the entropy estimators while changing the dimension of the Gaussian components. We again generate 100 Gaussian components, each distributed as Xi ∼ N (µi , I (d) ), where
I (d) indicates a d × d dimensional identity matrix. We vary the dimensionality d from 1 to 60.
The results are shown in Fig. 1D. First, we see that when d = 1, the KDE estimator and the
KL-divergence based estimator give a very similar prediction (differing only by 0.5) , but as the
dimension increases, the two estimates diverge at a rate of d/2. Similarly, ĤELK grows increasingly less accurate as the dimension increases. Our proposed lower and upper bounds provide good
estimates of the mixture entropy across the whole dimensional sweep.

B.

Mixture of Uniforms

In the second set of experiments, we consider a mixture of uniform distributions. Unlike Gaussians, uniform distributions are bounded within a hyper-rectangle and do not have full support
over the domain. These means that there can be significant regions within which pX (x) > 0, but
pi (x) = 0 for some i.
Here we list the formulae for pairwise distance measure between uniform distributions. In the
following, we use Vi to indicate the “volume” of distribution pi . Uniform components have a constant
p(x) over their support, and so Vi = 1/pi (x) (for all x where pi (x) > 0). Similarly, we use Vi∩j as
the “volume
of overlap” between pi and pj , i.e., the volume of the intersection of the support of pi
R
and pj , x 1{pi (x) > 0}1{pj (x) > 0}dx. The distance measures between uniforms are then
H(pi ) = ln Vi

14
(
ln(Vj /Vi ) supp pi ⊆ supp pj
KL(pi kpj ) =
∞
o.w.
BD(pi ||pj ) = 0.5 ln Vi + 0.5 ln Vj − ln Vi∩j
X
X Vi∩j
ĤELK = −
wi ln
wj
Vi Vj
i

A

j

B
Entropy (nats)

Entropy (nats)

11

10

9

12

9

6

8

7

3
-4

-3

-2

-1

0

1

-2

0

Ln(Mean Spread)

D 15

11

Entropy (nats)

Entropy (nats)

C

2

Ln(Width Variability)

10

9

8

10

Monte Carlo
Pair Dist: KL
Pair Dist: Bhat.
KDE
Exp. Lik. Ker.
[H(X|C), H(X,C)]

5

7
0
-6

-4

-2

Ln(Cluster Spread)

0

5

10

15

Dimension

Figure 2: Entropy estimates for a mixture of a 100 uniform. In each plot, the vertical axis shows the
entropy of the distribution, and the horizontal axis changes a feature of the components: A) the mean
distance is increased; B) the uniform widths become more similar (at the right side of the plot, all
uniforms have width ≈ 2); C) the components are grouped into 5 “clusters”, and the distance between
these clusters is increased; D) the dimension is increased.

Like the Gaussian case, we run four different computational experiments and compare the mixture entropy estimates to the true entropy, as determined by Monte-Carlo sampling.
In the first experiment, the mixture consists of 100 10-dimensional uniform components, with
Xi ∼ U(µi − 1, µi + 1) , and µi ∼N (0, σI). Fig. 2A depicts the change in entropy as the value
of σ increases. For very small σ, the distributions are almost overlapping, while for large σ they
tend very far apart. As expected, the entropy increases with σ. Here, we see that the prediction
of ĤKL is identical to H(X, C), which arises because KL(pi kpj ) is infinite whenever pi has broader
support than pj . Uniform components with equal size and non-equal means must have some region
of non-overlap, and so the KL is infinite between all pairs of components, thus KL is effectively
Dmax (Eq. (8)). In contrast, we see that ĤBD estimates the true entropy quite well. This example
demonstrates that getting an accurate estimate of mixture entropy may require selecting a distance
function that works will with the component distributions. Finally, it turns out that for uniform
components of equal size, ĤELK = ĤBD . This can be seen by moving BD(pi kpj ) out of the

15
exponential, and noting that Vi = Vj when the components have equal size.
In the second experiment, we adjust the size of the uniform components. We again have 100
10-dimensional components, Xi ∼ U(µi − γi , µi + γi ) , where µi ∼N (0, I), and γi ∼ Γ(1 + σ, 1 + σ),
where Γ is the Gamma distribution. Fig. 2B shows the change in entropy as ln σ increases. When
σ is small, the widths have significant spread, while as σ grows the distributions become close to
equally sized. We again see that ĤBD is a good estimator of entropy, outperforming all of the
non-pairwise based estimators. Generally, not all supports will be non-overlapping, so ĤKL will not
necessarily be equal to H(X, C), though we find the two to be numerically quite close. However,
we also find that the difference between the estimates given ĤBD vs. ĤKL provides a tight estimate
of the true entropy.
In the third experiment, we again consider a mixture with clustered components, and evaluate
the entropy estimators as these clusters grow apart. Here, there are 100 components with Xi ∼
U(µg(i) − 1, µg(i) + 1), where g(i) ∈ {1..5} is the identity of the cluster for distribution i, which are
randomly assigned. The cluster centers are generated according to N (0, σI). Fig. 2C shows the
change in entropy as the clusters locations move apart. Note that in this case, the upper bound
ĤKL significantly outperforms H(X, C), unlike the first and second experiment. We again see that
ĤBD provides a relatively accurate lower bound for the true entropy.
In the final experiment, the dimension of the uniform components is varied. There are again 100
components, with Xi ∼ U(µi − 1, µi + 1) , and µi ∼N (0, σI). Fig. 2D shows the change in entropy
as the dimension increases. On the extreme left, the uniforms are univariate, and on the extreme
left the components are 16-dimensional. Interestingly, the low-dimensional case, H(X|C) is a very
close estimate for the true entropy, while in the high-dimensional case the entropy becomes very
close to H(X, C). This is because in the higher dimensional problems there is more space to be far
away from each other. As in the first experiment, ĤKL is equal to H(X; C). Despite this changing
regime, we see that ĤBD gives good estimates of mixture entropy, regardless of dimension.

VII.

DISCUSSION

We have presented a new class of estimators for the entropy of a mixture distribution. We have
shown that any estimator in this class has a bounded estimation bias, and that this class includes
useful lower and upper bounds on the entropy of a mixture. Finally, we show that these bounds
become exact when mixture components are grouped into well-separated clusters.
Our derivation of the bounds make use of some existing results [12, 14]. However, to our
knowledge, these results have not been previously used to estimate mixture entropies. Furthermore,
they have not been compared numerically or analytically to better-known bounds.
We evaluated these estimators using numerical simulations of mixtures of Gaussians as well as
mixtures of bounded (hypercube) uniform distributions. Our results demonstrate that our estimators perform much better than existing well-known estimators.
This estimator class can be especially useful for optimization problems that involve minimization
of entropy or mutual information. If the distance function used in the pairwise estimator class is
continuous and smooth in the parameters of the mixture components, then the entropy estimate is
also continuous and smooth. This enables use within gradient-based optimization techniques, for
example gradient descent, as often used for machine learning problems.
In fact, we have used our upper bound to carry out a non-parametric, nonlinear version of the
“Information Bottleneck” [31]. Specifically, we minimized an upper bound on the mutual information
between input and hidden layer in a neural networks [20]. We found that the optimal distributions
were often clustered (Section III D). That work demonstrated practically the value of having an
accurate, differentiable upper bound on mixture entropy that performs well in the clustered regime.

16
ACKNOWLEDGEMENTS

We thank David H. Wolpert for useful discussions. We would also like to thank the Santa Fe
Institute for helping to support this research. This work was made possible through the support
of AFOSR MURI on multi-information sources of multi-physics systems under Award Number
FA9550-15-1-0038.

AUTHOR CONTRIBUTIONS

AK and BDT designed the method and experiments; BDT performed the experiments; AK and
BDT wrote the paper.

CONFLICTS OF INTEREST

The authors declare no conflict of interest.

Appendix A: Chernoff α-divergence is not a distance function for α ∈
/ [0, 1]

For any pair of densities p and q, consider the Chernoff α-divergence
Z
Cα := − ln pα (x)q 1−α (x) dx = − ln cα
where the quantity cα is called the Chernoff α-coefficient [22]. Taking the second derivative of
cα with respect to α gives
d2
cα =
dα2

Z

α

p (x)q

1−α



p(x)
(x) ln
q(x)

2
dx

Observe that this quantity is everywhere positive, meaning that cα is convex everywhere. For
simplicity, consider the case p 6= q, in which case this function is strictly convex. Because cα is
equal to 1 for α = 0 and α = 1, this means that cα > 1 for α ∈
/ [0, 1]. This in turn means that
the Chernoff α-divergence Cα is strictly negative for α ∈
/ [0, 1]. Thus, Cα is not a valid distance
function for α ∈
/ [0, 1], as defined in Section III.

[1] Arindam Banerjee, Srujana Merugu, Inderjit S Dhillon, and Joydeep Ghosh. Clustering with
bregman divergences. Journal of machine learning research, 6(Oct):1705–1749, 2005.
[2] Francisco M Capristan and Juan J Alonso. Range safety assessment tool (rsat): An analysis
environment for safety assessment of launch and reentry vehicles. In 52nd Aerospace Sciences
Meeting, page 0304, 2014.
[3] Jia-Yu Chen, John R Hershey, Peder A Olsen, and Emmanuel Yashchin. Accelerated monte
carlo for kullback-leibler divergence between gaussian mixture models. In Acoustics, Speech
and Signal Processing, 2008. ICASSP 2008. IEEE International Conference on, pages 4553–
4556. IEEE, 2008.
[4] Andrzej Cichocki and Shun-ichi Amari. Families of alpha-beta-and gamma-divergences: Flexible and robust measures of similarities. Entropy, 12(6):1532–1568, 2010.

17
[5] Andrzej Cichocki, Rafal Zdunek, Anh Huy Phan, and Shun-Ichi Amari. Similarity measures
and generalized divergences. Nonnegative Matrix and Tensor Factorizations: Applications to
Exploratory Multi-Way Data Analysis and Blind Source Separation, pages 81–129, 2009.
[6] Thomas M. Cover and Joy A. Thomas. Elements of information theory. John Wiley & Sons,
2012.
[7] Gavin E Crooks. On Measures of Entropy and Information. Technical Report 009 v0.6, 2017.
[8] Keinosuke Fukunaga. Introduction to statistical pattern recognition. Computer science and
scientific computing. Academic Press, Boston, 2nd ed edition, 1990.
[9] Manuel Gil, Fady Alajaji, and Tamas Linder. Rényi divergence measures for commonly used
univariate continuous distributions. Information Sciences, 249:124–131, 2013.
[10] Jacob Goldberger, Shiri Gordon, Hayit Greenspan, et al. An efficient image similarity measure
based on approximations of kl-divergence between two gaussian mixtures. In ICCV, volume 3,
pages 487–493, 2003.
[11] Peter Hall and Sally C Morton. On the estimation of entropy. Annals of the Institute of
Statistical Mathematics, 45(1):69–88, 1993.
[12] D. Haussler and M. Opper. Mutual information, metric entropy and cumulative relative
entropy risk. Ann Stat, 25(6), 1997.
[13] Alfred O. Hero, Bing Ma, Olivier Michel, and John Gorman. Alpha-Divergence for Classification, Indexing and Retrieval. 2001.
[14] John R. Hershey and Peder A. Olsen. Approximating the Kullback Leibler divergence between
Gaussian mixture models. In 2007 IEEE International Conference on Acoustics, Speech and
Signal Processing-ICASSP’07, volume 4, pages IV–317. IEEE, 2007.
[15] Tomáš Hobza, Domingo Morales, and Leandro Pardo. Rényi statistics for testing equality of
autocorrelation coefficients. Statistical Methodology, 6(4):424–436, July 2009.
[16] Marco F Huber, Tim Bailey, Hugh Durrant-Whyte, and Uwe D Hanebeck. On entropy
approximation for gaussian mixture random vectors. In Multisensor Fusion and Integration
for Intelligent Systems, 2008. MFI 2008. IEEE International Conference on, pages 181–188.
IEEE, 2008.
[17] Tony Jebara and Risi Kondor. Bhattacharyya and expected likelihood kernels. In Learning
theory and kernel machines, pages 57–71. Springer, 2003.
[18] Tony Jebara, Risi Kondor, and Andrew Howard. Probability product kernels. Journal of
Machine Learning Research, 5(Jul):819–844, 2004.
[19] Harry Joe. Estimation of entropy and other functionals of a multivariate density. Annals of
the Institute of Statistical Mathematics, 41(4):683–697, 1989.
[20] Artemy Kolchinsky, Brendan D. Tracey, and David H. Wolpert. Nonlinear Information Bottleneck. arXiv:1705.02436 [cs, math, stat], May 2017. arXiv: 1705.02436.
[21] Chandra Nair, Balaji Prabhakar, and Devavrat Shah. On entropy for mixtures of discrete
and continuous variables. arXiv preprint cs/0607075, 2006.
[22] Frank Nielsen. Chernoff information of exponential families. arXiv preprint arXiv:1102.2684,
2011.
[23] Frank Nielsen. Generalized Bhattacharyya and Chernoff upper bounds on Bayes error using
quasi-arithmetic means. Pattern Recognition Letters, 42:25–34, June 2014.
[24] John Paisley. Two useful bounds for variational inference. Technical report, Technical report,
Department of Computer Science, Princeton University, Princeton, NJ, 2010.
[25] Leandro Pardo. Statistical Inference Based on Divergence Measures. CRC Press, October
2005. Google-Books-ID: ziDGGIkhqlMC.
[26] Jose C Principe, Dongxin Xu, and John Fisher. Information theoretic learning. Unsupervised
adaptive filtering, 1:265–319, 2000.
[27] Igal Sason and Sergio Verdú. f -divergence inequalities. IEEE Transactions on Information
Theory, 62(11):5973–6006, 2016.
[28] Nicol N. Schraudolph. Gradient-based manipulation of nonparametric entropy estimates.
Neural Networks, IEEE Transactions on, 15(4):828–837, 2004.
[29] Nicol Norbert Schraudolph. Optimization of entropy with neural networks. PhD thesis,
Citeseer, 1995.

18
[30] Sarit Shwartz, Michael Zibulevsky, and Yoav Y. Schechner. Fast kernel entropy estimation
and optimization. Signal Processing, 85(5):1045–1058, 2005.
[31] N. Tishby, F. Pereira, and W. Bialek. The information bottleneck method. In 37th Allerton
Conf on Communication, 1999.
[32] Tim Van Erven and Peter Harremos. Rényi divergence and kullback-leibler divergence. IEEE
Transactions on Information Theory, 60(7):3797–3820, 2014.
[33] Paul Viola, Nicol N. Schraudolph, and Terrence J. Sejnowski. Empirical Entropy Manipulation for Real-World Problems. Advances in neural information processing systems, pages
851–857, 1996.
[34] Jian-Wu Xu, António RC Paiva, Il Park, and Jose C Principe. A reproducing kernel hilbert
space framework for information-theoretic learning. IEEE Transactions on Signal Processing,
56(12):5891–5902, 2008.
[35] O Zobay et al. Variational bayesian inference with gaussian-mixture approximations. Electronic Journal of Statistics, 8(1):355–389, 2014.

