8 Chain Rule Optimal Transport
207
log q(x)dx ≥ −H (U ) − H ( p i ) −
p(x) log q(x)dx, where U = (1/n, . . . , 1/n)
is the uniform distribution, and the integral
p(x) log q(x)dx is estimated by MonteCarlo sampling.
8.6 Conclusion
We defined the generic Chain Rule Optimal Transport (CROT) distance (Definition 8.1) H D for any ground distance D. CROT unifies and generalizes the Wasserstein/EMD distance between discrete measures [54] and the Mixture Component
Optimal Transport [33] distance. We proved that H D is a metric whenever D is
a metric (Property 8.2). We then dealt with statistical mixtures, and showed that
H D (m 1 , m 2 ) ≥ D(m 1 , m 2 ) (Theorem 8.8) whenever D is jointly convex, and considered the smooth Sinkhorn CROT distance S D (m 1 , m 2 ) (SCROT) for fast calculations of H D (m 1 , m 2 ) via matrix scaling algorithms (Sinkhorn–Knopp algorithm)
so that D(m 1 , m 2 ) ≤ H D (m 1 , m 2 ) ≤ S D (m 1 , m 2 ). These bounds hold in particular
for statistical f -divergences I f ( p : q) =
p(x) f (q(x)/ p(x))dx which includes the
Kullback–Leibler divergence). Finally, we proposed a novel efficient method to learn
Gaussian mixture models from a semi-SCROT distance that bypasses Sinkhorn iterations and uses a simple normalization (Eq. 8.15). Our learning method by KDE simplification is shown to outperform the EM algorithm of sklearn for the MNIST
and Fashion MNIST datasets.
Acknowledgements Frank Nielsen thanks Professor Steve Huntsman for pointing out reference [33] to his attention. The authors are grateful to Professor Patrick Forré (University of Amsterdam) for letting us know of an earlier error in the definition of CROT, and to Professor Rüschendorf
for sending us his work [55].
Disclaimer: Views and opinions expressed are those of the authors and do not necessarily represent
official positions of their respective companies.
A. Proof of CROT Metric (Property 8.2)
Proof We prove that H ( p, q) satisfies the following axioms of metric distances:
Non-negativity. As D
p(x|y), q(x|z)
≥ 0, we have by definition that
H D ( p, q) ≥ 0.
Law of indiscernibles. If H D ( p, q) = 0, then ∀ > 0, ∃r
∈ ( p(y), q(z)), such
that
E r (y,z) D ( p(x|y), q(x|z)) < <.
207
log q(x)dx ≥ −H (U ) − H ( p i ) −
p(x) log q(x)dx, where U = (1/n, . . . , 1/n)
is the uniform distribution, and the integral
p(x) log q(x)dx is estimated by MonteCarlo sampling.
8.6 Conclusion
We defined the generic Chain Rule Optimal Transport (CROT) distance (Definition 8.1) H D for any ground distance D. CROT unifies and generalizes the Wasserstein/EMD distance between discrete measures [54] and the Mixture Component
Optimal Transport [33] distance. We proved that H D is a metric whenever D is
a metric (Property 8.2). We then dealt with statistical mixtures, and showed that
H D (m 1 , m 2 ) ≥ D(m 1 , m 2 ) (Theorem 8.8) whenever D is jointly convex, and considered the smooth Sinkhorn CROT distance S D (m 1 , m 2 ) (SCROT) for fast calculations of H D (m 1 , m 2 ) via matrix scaling algorithms (Sinkhorn–Knopp algorithm)
so that D(m 1 , m 2 ) ≤ H D (m 1 , m 2 ) ≤ S D (m 1 , m 2 ). These bounds hold in particular
for statistical f -divergences I f ( p : q) =
p(x) f (q(x)/ p(x))dx which includes the
Kullback–Leibler divergence). Finally, we proposed a novel efficient method to learn
Gaussian mixture models from a semi-SCROT distance that bypasses Sinkhorn iterations and uses a simple normalization (Eq. 8.15). Our learning method by KDE simplification is shown to outperform the EM algorithm of sklearn for the MNIST
and Fashion MNIST datasets.
Acknowledgements Frank Nielsen thanks Professor Steve Huntsman for pointing out reference [33] to his attention. The authors are grateful to Professor Patrick Forré (University of Amsterdam) for letting us know of an earlier error in the definition of CROT, and to Professor Rüschendorf
for sending us his work [55].
Disclaimer: Views and opinions expressed are those of the authors and do not necessarily represent
official positions of their respective companies.
A. Proof of CROT Metric (Property 8.2)
Proof We prove that H ( p, q) satisfies the following axioms of metric distances:
Non-negativity. As D
p(x|y), q(x|z)
≥ 0, we have by definition that
H D ( p, q) ≥ 0.
Law of indiscernibles. If H D ( p, q) = 0, then ∀ > 0, ∃r
∈ ( p(y), q(z)), such
that
E r (y,z) D ( p(x|y), q(x|z)) < <.