200
F. Nielsen and K. Sun
Figure 8.1 illustrates the performances of the various lower/upper bounds on the
total variation between mixtures of Gaussian, Gamma, and Rayleigh distributions
with respect to the true value which is estimated using Monte Carlo samplings (consistent estimations).
The acronyms of the various bounds are as follows: CELB: Combinatorial Envelope Lower Bound ([44]; applies only for 1D mixtures); CEUB: Combinatorial Envelope Upper Bound ([44]; applies only for 1D mixtures); CGQLB: Coarse-Grained
Quantization Lower Bound [44] for 1000 bins (applies only for f -divergences that
satisfy the information monotonicity property); CROT: Chain Rule Optimal Transport H D (this paper); Sinkhorn CROT: Entropy-regularized CROT [8] S D ≤ H D ,
with λ = 1 and = 10
−8 (for convergence of the Sinkhorn–Knopp iterative matrix
scaling algorithm).
Next, we consider the renown MNIST handwritten digit database [32] of 70,000
handwritten digit 28 × 28 grey images and the Fashion-MNIST images with exactly
the same sample size and dimensions but different image contents [64]. We first use
PCA to reduce the original dimensionality d = 28 × 28 = 784 to D ∈ {10, 50}. Then
we extract two subsets of samples, and estimate respectively two GMMs composed of
10 multivariate Gaussian distributions with a diagonal covariance matrix. The GMMs
are learned by the Expectation-Maximization (EM) algorithm implementation of
scikit-learn [50]. Notice that we did not use the labels in our estimation, and therefore
the mixture components do not necessarily correspond to different digits.
We approximate the TV between D-dimensional GMMs using Monte Carlo by
performing stochastic integration of the following integrals:
TV( p, q) :=
1
2
| p(x) − q(x)|dx =
1
2m
x i ∼ p(x)
1 − exp(r (x i ))
1 + exp(r (x i ))
+
1
2m
y i ∼q(x)
1 − exp(r (y i ))
1 + exp(r (y i ))
,
where {x i }
m
i=1 and {y i }
m
i=1 are i.i.d. samples drawn from p(x) and q(x), respectively,
and r (x) = | log p(x) − log q(x)|. In our experiments, we set m = 0.5 × 10
4 .
To compute the CROT, we use the EMD and Sinkhorn implementations provided
by the Python Optimal Transport, POT, library [18]. For Sinkhorn, we set the entropy
regularization strength as follows: Sinkhorn (1) means median(M) and Sinkhorn (10)
means median(M)/10, where M is the metric cost matrix. For example, to compute
CROT-TV, M is the pairwise TV distance matrix from all components in the first
mixture model to all components in the second mixture. The maximum number of
Sinkhorn iterations is 1000, with a stop threshold of 10
−10 .
To get some intuitions, see Fig. 8.2 for the cost matrix and the corresponding
optimal transport matrix, where the cost is defined by TV distance, and the dataset is
PCA-processed MNIST. It shows the 10 × 10 TV distance matrix between mm1’s
(mixture model) components and mm2’s components. Red means a large distance;
blue means a small distance. We see that the transportation scheme tries to assign
higher weights to small cost pairs (blue region in the cost matrix).
F. Nielsen and K. Sun
Figure 8.1 illustrates the performances of the various lower/upper bounds on the
total variation between mixtures of Gaussian, Gamma, and Rayleigh distributions
with respect to the true value which is estimated using Monte Carlo samplings (consistent estimations).
The acronyms of the various bounds are as follows: CELB: Combinatorial Envelope Lower Bound ([44]; applies only for 1D mixtures); CEUB: Combinatorial Envelope Upper Bound ([44]; applies only for 1D mixtures); CGQLB: Coarse-Grained
Quantization Lower Bound [44] for 1000 bins (applies only for f -divergences that
satisfy the information monotonicity property); CROT: Chain Rule Optimal Transport H D (this paper); Sinkhorn CROT: Entropy-regularized CROT [8] S D ≤ H D ,
with λ = 1 and = 10
−8 (for convergence of the Sinkhorn–Knopp iterative matrix
scaling algorithm).
Next, we consider the renown MNIST handwritten digit database [32] of 70,000
handwritten digit 28 × 28 grey images and the Fashion-MNIST images with exactly
the same sample size and dimensions but different image contents [64]. We first use
PCA to reduce the original dimensionality d = 28 × 28 = 784 to D ∈ {10, 50}. Then
we extract two subsets of samples, and estimate respectively two GMMs composed of
10 multivariate Gaussian distributions with a diagonal covariance matrix. The GMMs
are learned by the Expectation-Maximization (EM) algorithm implementation of
scikit-learn [50]. Notice that we did not use the labels in our estimation, and therefore
the mixture components do not necessarily correspond to different digits.
We approximate the TV between D-dimensional GMMs using Monte Carlo by
performing stochastic integration of the following integrals:
TV( p, q) :=
1
2
| p(x) − q(x)|dx =
1
2m
x i ∼ p(x)
1 − exp(r (x i ))
1 + exp(r (x i ))
+
1
2m
y i ∼q(x)
1 − exp(r (y i ))
1 + exp(r (y i ))
,
where {x i }
m
i=1 and {y i }
m
i=1 are i.i.d. samples drawn from p(x) and q(x), respectively,
and r (x) = | log p(x) − log q(x)|. In our experiments, we set m = 0.5 × 10
4 .
To compute the CROT, we use the EMD and Sinkhorn implementations provided
by the Python Optimal Transport, POT, library [18]. For Sinkhorn, we set the entropy
regularization strength as follows: Sinkhorn (1) means median(M) and Sinkhorn (10)
means median(M)/10, where M is the metric cost matrix. For example, to compute
CROT-TV, M is the pairwise TV distance matrix from all components in the first
mixture model to all components in the second mixture. The maximum number of
Sinkhorn iterations is 1000, with a stop threshold of 10
−10 .
To get some intuitions, see Fig. 8.2 for the cost matrix and the corresponding
optimal transport matrix, where the cost is defined by TV distance, and the dataset is
PCA-processed MNIST. It shows the 10 × 10 TV distance matrix between mm1’s
(mixture model) components and mm2’s components. Red means a large distance;
blue means a small distance. We see that the transportation scheme tries to assign
higher weights to small cost pairs (blue region in the cost matrix).