Optimal transport for machine learningRémi Flamary

AG GDR ISIS, Sète, 16 Novembre 2017Collaborators

N. Courty

M. Perrot

A. Rakotomamonjy

C. Févotte

D. Tuia

V. Emiya

A. Habrard

V. Seguy

M. Cuturi

M. Ducoffe+ ANR OATMIL project members
2 / 37

Table of content
Optimal transport
Introduction to OT
Wasserstein distance
Regularized optimal transport
Barycenters and geometry of optimal transport
Learning with optimal transport
Learning from histograms with OT
Learning from empirical distributions with OT
Mapping with optimal transport
Optimal transport mapping estimation
Color adaptation
Optimal transport for domain adaptation
Conclusion

3 / 37

The origins of optimal transport

Problem [Monge, 1781]
I

How to move dirt from one place (déblais) to another (remblais) while
minimizing the effort ?

I

Find a mapping T between the two distributions of mass (transport).

I

Optimize with respect to a displacement cost c(x, y) (optimal).

4 / 37

The origins of optimal transport
Source s
Target tc(x,y)

T(x)
x
y

x

y

Problem [Monge, 1781]
I

How to move dirt from one place (déblais) to another (remblais) while
minimizing the effort ?

I

Find a mapping T between the two distributions of mass (transport).

I

Optimize with respect to a displacement cost c(x, y) (optimal).

4 / 37

Optimal transport (Monge formulation)
Quadratic cost c(x, y) = |x y|2

Distributionsc(20, y)c(40, y)c(60, y)
0

20

40

x,y

60

80

100

0

20

40

y

60

80

100

I

Probability measures µs and µt on and a cost function c : Ωs × Ωt → R+ .

I

The Monge formulation [Monge, 1781] aim at finding a mapping T : Ωs → ΩtZ
infc(x, T (x))µs (x)dx(1)
T #µs =µtΩsINon-convex optimization problem, mapping does not exist in the general case.

I[Brenier, 1991] proved existence and unicity of the Monge map forc(x, y) = kx − yk2 and distributions with densities.

5 / 37

Optimal transport (Kantorovich formulation)
Joint distribution (x, y) = s(x) t(y)Source s(x)Target t(y)(x, y)

I

Transport cost c(x, y) = |x y|2xyc(x, y)xyThe Kantorovich formulation [Kantorovich, 1942] seeks for a probabilistic
coupling γ ∈ P(Ωs × Ωt ) between Ωs and Ωt :Z
γ 0 = arg minc(x, y)γ(x, y)dxdy,
γ


s.t.

γ∈P=

(2)

Ωs ×ΩtZ

Zγ ≥ 0,

γ(x, y)dy = µs ,Ωtγ(x, y)dx = µtΩsIγ is a joint probability measure with marginals µs and µt .

I

Linear Program that always have a solution.
6 / 37

Wasserstein distanceSource distribution

Divergences (scaled)
W11
W22
l1 (TV)l2 (sq. eucl.)

Target distributions

Wasserstein distance
Wpp (µs , µt ) = minγ∈PZc(x, y)γ(x, y)dxdy = E(x,y)∼γ [c(x, y)](3)Ωs ×Ωtwhere c(x, y) = kx − ykp
I

A.K.A. Earth Mover’s Distance (W11 ) [Rubner et al., 2000].

I

Do not need the distribution to have overlapping support.

I

Subgradients can be computed with the dual variables of the LP.

I

Works for continuous and discrete distributions (histograms, empirical).
7 / 37

Discrete distributions: Empirical vs Histogram
Discrete measure:

µ=

n
X

µi δxi ,xi ∈ Ω,

i=1

Lagrangian (point clouds)nXµi = 1i=1Eulerian (histograms)

xi

I
I

Constant weight: µi = n1nQuotient space: Ω , ΣnI

Fixed positions xi e.g. grid

I

Convex polytope
P Σn (simplex):{(µi )i ≥ 0; i µi = 1}

Slide stolen from Gabriel Peyré
8 / 37

Optimal transport with discrete distributions
OT matrix

Matrix C

Distributions
Source s
Target t

OT Linear Program(
γ 0 = arg minγ∈Phγ, CiF =)X

γi,j ci,ji,jwhere C is a cost matrix with ci,j = c(xsi , xtj ) and the marginals constraints areP=noγ ∈ (R+ )ns ×nt | γ1nt = µs , γ T 1ns = µt

Solved with Network Flow solver of complexity O(n3 ).
9 / 37

Optimal transport with discrete distributions
Matrix C

Distributions

OT matrix

Source s
Target t

OT Linear Program(
γ 0 = arg minγ∈Phγ, CiF =)X

γi,j ci,ji,jwhere C is a cost matrix with ci,j = c(xsi , xtj ) and the marginals constraints areP=noγ ∈ (R+ )ns ×nt | γ1nt = µs , γ T 1ns = µt

Solved with Network Flow solver of complexity O(n3 ).
9 / 37

Optimal transport with discrete distributions
Matrix C

Distributions

OT matrix with samples

Source s
Target t

OT Linear Program(
γ 0 = arg minγ∈Phγ, CiF =)X

γi,j ci,ji,jwhere C is a cost matrix with ci,j = c(xsi , xtj ) and the marginals constraints areP=noγ ∈ (R+ )ns ×nt | γ1nt = µs , γ T 1ns = µt

Solved with Network Flow solver of complexity O(n3 ).
9 / 37

Regularized optimal transport
γ λ0 = arg minγ∈Phγ, CiF + λΩ(γ),(4)

IGroup Lasso [Courty et al., 2016a].

I

KL, Itakura Saito, β-divergences,[Dessein et al., 2016].

Why regularize?
I

Smooth the “distance” estimation:Wλ (µs , µt ) = γ λ0 , C F

I

Encode prior knowledge on the data.

I

Better posed problem (convex, stability).

I

Fast algorithms to solve the OT problem.

=1e-2

Entropic regularization [Cuturi, 2013].

=1e-1

I

=0

Regularization term Ω(γ)

10 / 37

Entropic regularized optimal transport
Distributions

Reg. OT matrix with =1e-3

Reg. OT matrix with =1e-2

Source s
Target t

Entropic regularization [Cuturi, 2013]
XΩ(γ) =
γ(i, j) log γ(i, j)
i,jI

Regularization with the negative entropy of γ.

I

Solution of the form γ λ0 = diag(u) exp(−C/λ)diag(v).

ISinkhorn-Knopp algorithm (implementation in parallel, GPU).

I

Smooth problem in the dual can be solved with BFGS [Cuturi and Peyré, 2016],
SGD [Genevay et al., 2016, Seguy et al., 2017].
11 / 37

Entropic regularized optimal transport
Distributions

Reg. OT matrix with =1e-3

Reg. OT matrix with =1e-2

Source s
Target t

Entropic regularization [Cuturi, 2013]
XΩ(γ) =
γ(i, j) log γ(i, j)
i,jI

Regularization with the negative entropy of γ.

I

Solution of the form γ λ0 = diag(u) exp(−C/λ)diag(v).

ISinkhorn-Knopp algorithm (implementation in parallel, GPU).

I

Smooth problem in the dual can be solved with BFGS [Cuturi and Peyré, 2016],
SGD [Genevay et al., 2016, Seguy et al., 2017].
11 / 37

Wasserstein barycenter
Matrix C

Barycenters [Agueh and Carlier, 2011] and Wasserstein Geodesicµ̄ = arg minµnXλi Wpp (µi , µ)

i

Pn

I

λi > 0 andi λi = 1.

I

Uniform barycenter has λi = n1 , ∀i.

IInterpolation with n=2 and λ = [1 − t, t] with 0 ≤ t ≤ 1 [McCann, 1997].

I

Regularized barycenters using Bregman projections [Benamou et al., 2015].

I

The cost and regularization impacts the interpolation trajectory.
12 / 37

Wasserstein barycenter
Matrix C

Barycenters [Agueh and Carlier, 2011] and Wasserstein Geodesicµ̄ = arg minµnXλi Wpp (µi , µ)

i

Pn

I

λi > 0 andi λi = 1.

I

Uniform barycenter has λi = n1 , ∀i.

IInterpolation with n=2 and λ = [1 − t, t] with 0 ≤ t ≤ 1 [McCann, 1997].

I

Regularized barycenters using Bregman projections [Benamou et al., 2015].

I

The cost and regularization impacts the interpolation trajectory.
12 / 37

3D Wasserstein barycenter
Shape interpolation [Solomon et al., 2015]13 / 37

Principal Geodesics Analysis

Geodesic PCA in the Wasserstein space [Bigot et al., 2017]
I

Generalization of Principal Component Analysis to the Wassertsein manifold.

I

Regularized OT [Seguy and Cuturi, 2015].

I

Approximation using Wasserstein embedding [Courty et al., 2017a].

I

Also note recent Wasserstein Dictionary Learning approaches[Schmitz et al., 2017].
14 / 37

Section
Optimal transport
Introduction to OT
Wasserstein distance
Regularized optimal transport
Barycenters and geometry of optimal transport
Learning with optimal transport
Learning from histograms with OT
Learning from empirical distributions with OT
Mapping with optimal transport
Optimal transport mapping estimation
Color adaptation
Optimal transport for domain adaptation
Conclusion

14 / 37

Learning with optimal transport
OT matrix

Learning from histograms
I

Wasserstein distance.

I

Ground metric design.

I

Loss for multilabel classifier[Frogner et al., 2015]

I

Loss for linear unmixing[Flamary et al., 2016b].

Learning from empirical distributionsI

Non parametric divergence between
non overlapping distributions.

I

Estimate discriminant subspace[Flamary et al., 2016a].

I

Objective function for GAN[Arjovsky et al., 2017].
15 / 37

Supervised learning with Wasserstein Loss

Learning with a Wasserstein Loss [Frogner et al., 2015]

min
f

N
X

W11 (f (xi ), li )k=1

IEmpirical loss minimization with Wasserstein loss.

I

Multi-label prediction (labels l seen as histograms, f output softmax).

I

Cost between labels can encode semantic similarity between classes.

I

Good performances in image tagging.
16 / 37

Linear unmixing with optimal transport
Linear unmixing
min

h∈∆

WC (v, Dh)(5)I∆ is the probability simplex (positivity, sum to one).

Iv is the observation, D the dictionary, h the mixing coefficients.

I

Wasserstein as data fitting proposed in [Zen et al., 2014] for matrix factorization.

I

Fast algorithm with regularization in [Rolet et al., 2016], non linear unmixing in[Schmitz et al., 2017].

Musical spectral unmixing
I

State of the art: KL + designed dictionary.

I

Spectra with harmonic structure.

I

Variability in the fundamental frequency.

I

Variability in the magnitude of the harmonics.

⇒ Optimal spectral transportation [Flamary et al., 2016b].
17 / 37

Linear unmixing with optimal transport
Linear unmixing
min

h∈∆

WC (v, Dh)(5)I∆ is the probability simplex (positivity, sum to one).

Iv is the observation, D the dictionary, h the mixing coefficients.

I

Wasserstein as data fitting proposed in [Zen et al., 2014] for matrix factorization.

I

Fast algorithm with regularization in [Rolet et al., 2016], non linear unmixing in[Schmitz et al., 2017].

Musical spectral unmixing
I

State of the art: KL + designed dictionary.

I

Spectra with harmonic structure.

I

Variability in the fundamental frequency.

I

Variability in the magnitude of the harmonics.

⇒ Optimal spectral transportation [Flamary et al., 2016b].
17 / 37

Optimal spectral transportation (OST)
Quadratic cost C (log)

Quadratic cost between frequencies
I Allows small shift in frequencies.
I

Very sensitive to harmonics magnitude.

Harmonic invariant costcij =min (fi − qfj )2 +  δq6=1 ,f

q=1,..., f ijIAllow mass transfer between harmonics.

I > 0 discriminates between octaves.

Solving the optimization problem
I

A good invariant cost allows for extremely simple dictionary elements (diracs on
the fundamental frequency).

I

We take D as diracs on the fundamental frequencies of the notes.

I

Closed form for solving the OT problem.

I

Non-convex Group lasso for sparse estimates and/or entropic regularization.

18 / 37

Optimal spectral transportation (OST)
Harmonic cost C (log)

Quadratic cost between frequencies
I Allows small shift in frequencies.
I

Very sensitive to harmonics magnitude.

Harmonic invariant costcij =min (fi − qfj )2 +  δq6=1 ,f

q=1,..., f ijIAllow mass transfer between harmonics.

I > 0 discriminates between octaves.

Solving the optimization problem
I

A good invariant cost allows for extremely simple dictionary elements (diracs on
the fundamental frequency).

I

We take D as diracs on the fundamental frequencies of the notes.

I

Closed form for solving the OT problem.

I

Non-convex Group lasso for sparse estimates and/or entropic regularization.

18 / 37

OST in action
Simulated data
I

Robust to shifted fundamental frequency.

I

Robust to harmonics magnitude variability.

I

Very fast (∼ms per frame).

MAPS Dataset [Emiya et al., 2010]I

Several piano sequence from classical music(m = 60 notes)

I

Comparison with ground truth given as MIDI.

I

OST similar of better than KL+Dico while≥ 70 times quicker.

Real time demonstration
I

Python+Pygame implementation.

I

Demo url:
https://github.com/rflamary/OST
19 / 37

Wasserstein Discriminant Analysis (WDA)
Original space

Optimal projected space
2
1
0
1
2

2

P∈∆

1

2

23

2
1
0
1
2
2

0

c
c
c,c0 >c Wλ (PX , PX )Pccc Wλ (PX , PX )

P
max

1 0

01
21

3

(6)

1

0

1

2

I

Xc are samples from class c.

I

P is an orthogonal projection;

I

Converges to Fisher Discriminant when λ → ∞.

I

Non parametric method that allows nonlinear discrimination.

I

Problem solved with gradient ascent in the Stiefel manifold.

I

Gradient computed using automatic differentiation of Sinkhorn algorithm.

20 / 37

Wasserstein Discriminant Analysis (WDA)
Original space

Optimal projected space
2
1
0
1
2

3 2 1

0 1 2

3

1
10
32

c
c0
c,c0 >c Wλ (PX , PX )Pccc Wλ (PX , PX )

23

3

P
max
P∈∆

3
2
1
0
1
2
3

(6)

2

1

0

1

2

3

I

Xc are samples from class c.

I

P is an orthogonal projection;

I

Converges to Fisher Discriminant when λ → ∞.

I

Non parametric method that allows nonlinear discrimination.

I

Problem solved with gradient ascent in the Stiefel manifold.

I

Gradient computed using automatic differentiation of Sinkhorn algorithm.

20 / 37

WDA in action
Simulated datasets : 10→2

MNIST Dataset: 784→10(→2 TSNE)
FDA

LFDA

LMNN

LDSR

CEML

WDA

Test data

Train data

PCA

21 / 37

Generative Adversarial Networks (GAN)

Generative Adversarial Networks (GAN) [Goodfellow et al., 2014]
min maxG

D

Ex∼µd [log D(x)] + Ez∼N (0,I) [log(1 − D(G(z)))]I

Learn a generative model G that outputs realistic samples from data µd .

I

Learn a classifier D to discriminate between the generated and true samples.

I

Make those models compete (Nash equilibrium [Zhao et al., 2016]).

I

Generator space has semantic meaning [Radford et al., 2015].

I

But extremely hard to train (vanishing gradients).
22 / 37

Generative Adversarial Networks (GAN)

Generative Adversarial Networks (GAN) [Goodfellow et al., 2014]
min maxG

D

Ex∼µd [log D(x)] + Ez∼N (0,I) [log(1 − D(G(z)))]I

Learn a generative model G that outputs realistic samples from data µd .

I

Learn a classifier D to discriminate between the generated and true samples.

I

Make those models compete (Nash equilibrium [Zhao et al., 2016]).

I

Generator space has semantic meaning [Radford et al., 2015].

I

But extremely hard to train (vanishing gradients).
22 / 37

Wasserstein Generative Adversarial Networks

Wasserstein GAN [Arjovsky et al., 2017]min
G

W11 (G(z), µd ),s.t. z ∼ N (0, I)

I

Minimize the Wasserstein distance between the data and the generated data.

I

Wasserstein approximated in the dual (separable w.r.t. the samples).

I

Parametrization of the dual variable D with a neural network.

I

Lipschitz constraints in the dual (constrained parameters).

I

No vanishing gradients ! Far better convergence in practice.

(7)

23 / 37

Section
Optimal transport
Introduction to OT
Wasserstein distance
Regularized optimal transport
Barycenters and geometry of optimal transport
Learning with optimal transport
Learning from histograms with OT
Learning from empirical distributions with OT
Mapping with optimal transport
Optimal transport mapping estimation
Color adaptation
Optimal transport for domain adaptation
Conclusion

23 / 37

Mapping with optimal transport
Target and Source distributions Generated distribution

1.5

1.5

1.0

1.5
Target samples
Source samples 1.0

0.5

0.5

0.5

0.0

0.0

0.0

0.5

0.5

1.0

1.0

1.5

1.5

1

0

1

Sample displacement

1.0

0.5
Target samples
Generated samples
1

0

1

1.0
1.5

Source displacement
101Mapping estimation
I

Mapping do not exist in general between empirical distributions.

I

Barycentric mapping [Ferradans et al., 2014].

I

Smooth mapping estimation [Perrot et al., 2016, Seguy et al., 2017].

Why map ?
I

Sensible displacement to align distributions.

I

Color adaptation in image [Ferradans et al., 2014].

I

Domain adaptation and transfer learning [Courty et al., 2016b].
24 / 37

Transporting the discrete samples
Distributions

Classt OT

Reg. Entropic OT

Source s
Target t

Barycentric mapping [Ferradans et al., 2014]
Tbγ 0 (xsi ) = arg minxX

γ 0 (i, j)c(x, xtj ).

(8)

j

I

The mass of each source sample is spread onto the target samples (line of γ 0 ).

I

The mapping is the barycenter of the target samples weighted by γ 0IClosed form solution for the quadratic loss.

I

Limited to the samples in the distribution (no out of sample).
25 / 37

Transporting the discrete samples
Distributions

Classic OT (LP)Reg. Entropic OT

Source s
Target t

Barycentric mapping [Ferradans et al., 2014]
Tbγ 0 (xsi ) = arg minxX

γ 0 (i, j)c(x, xtj ).

(8)

j

I

The mass of each source sample is spread onto the target samples (line of γ 0 ).

I

The mapping is the barycenter of the target samples weighted by γ 0IClosed form solution for the quadratic loss.

I

Limited to the samples in the distribution (no out of sample).
25 / 37

Transporting the discrete samples
Distributions

Classic OT (LP)Reg. Entropic OT

Source s
Target t

Barycentric mapping [Ferradans et al., 2014]
Tbγ 0 (xsi ) = arg minxX

γ 0 (i, j)c(x, xtj ).

(8)

j

I

The mass of each source sample is spread onto the target samples (line of γ 0 ).

I

The mapping is the barycenter of the target samples weighted by γ 0IClosed form solution for the quadratic loss.

I

Limited to the samples in the distribution (no out of sample).
25 / 37

Transporting the discrete samples
Distributions

Classic OT (LP)Reg. Entropic OT

Source s
Target t

Barycentric mapping [Ferradans et al., 2014]
Tbγ 0 (xsi ) = arg minxX

γ 0 (i, j)c(x, xtj ).

(8)

j

I

The mass of each source sample is spread onto the target samples (line of γ 0 ).

I

The mapping is the barycenter of the target samples weighted by γ 0IClosed form solution for the quadratic loss.

I

Limited to the samples in the distribution (no out of sample).
25 / 37

Transporting the discrete samples

Barycentric mapping [Ferradans et al., 2014]
Tbγ 0 (xsi ) = arg minxX

γ 0 (i, j)c(x, xtj ).

(8)

j

I

The mass of each source sample is spread onto the target samples (line of γ 0 ).

I

The mapping is the barycenter of the target samples weighted by γ 0IClosed form solution for the quadratic loss.

I

Limited to the samples in the distribution (no out of sample).
25 / 37

Optimal transport mapping estimation
Joint OT and mapping estimation [Perrot et al., 2016]
I

Estimate jointly the OT matrix and a smooth
mapping approximating the barycentricmapping.

I

The mapping is a regularization for OT.

I

Controlled generalization error.

I

Linear and kernel mappings limited to small
scale datasets.

2-step mapping estimation [Seguy et al., 2017]
1 Estimate regularized OT in the dual.
2 Estimate a smooth version of the barycentricmapping with a neural network.
I

Stochastic Gradient Descent on the OT dual.

I

Convergence to the true OT and mapping forsmall regularization.
26 / 37

Histogram matching in images
Pixels as empirical distribution [Ferradans et al., 2014]27 / 37

Histogram matching in images
Image colorization [Ferradans et al., 2014]27 / 37

Domain Adaptation problem
AmazonDLSR

Feature extraction

Feature extraction

Probability Distribution Functions over the domains

Our context
I

Classification problem with data coming from different sources (domains).

I

Distributions are different but related.
28 / 37

Unsupervised domain adaptation problem
AmazonDLSR

Feature extraction+ Labels

Feature extraction

no labels !
not working !!!!

decision function

Source Domain

Target Domain

Problems
I

Labels only available in the source domain, and classification is conducted in thetarget domain.

I

Classifier trained on the source domain data performs badly in the target domain
29 / 37

OT for domain adaptation : Step 1
DatasetOptimal transport

Class 1
Class 2
Samples
SamplesClassifier onClassification on transported samples

Samples

Samples

Samples

SamplesClassifier on

Step 1 : Estimate optimal transport between distributions.
I Choose the ground metric (squared euclidean in our experiments).
I

Using regularization allows
I
I

I

Large scale and regular OT with entropic regularization [Cuturi, 2013].
Class labels in the transport with group lasso [Courty et al., 2016b].

Efficient optimization based on Bregman projections [Benamou et al., 2015] andI
I

Majoration minimization for non-convex group lasso.
Generalized Conditionnal gradient for general regularization (cvx. lasso,
Laplacian).
30 / 37

OT for domain adaptation : Steps 2 & 3
DatasetOptimal transport

Class 1
Class 2
Samples
SamplesClassifier onClassification on transported samples

Samples

Samples

Samples

SamplesClassifier on

Step 2 : Transport the training samples onto the target distribution.
I The mass of each source sample is spread onto the target samples (line of γ ).
0ITransport using barycentric mapping [Ferradans et al., 2014].

I

The mapping can be estimated for out of sample prediction[Perrot et al., 2016, Seguy et al., 2017].

Step 3 : Learn a classifier on the transported training samples
I Transported sample keep their labels.
I

Classic ML problem when samples are well transported.
31 / 37

Visual adaptation datasets

Datasets
I Digit recognition, MNIST VS USPS (10 classes, d=256, 2 dom.).
I

Face recognition, PIE Dataset (68 classes, d=1024, 4 dom.).

I

Object recognition, Caltech-Office dataset (10 classes, d=800/4096, 4 dom.).

Numerical experiments
I Comparison with state of the art on the 3 datasets.
I

OT works very well on digits and object recognition.

I

Works well on deep features adaptation and extension to semi-supervised DA.
32 / 37

Seamless copy in images

Poisson image editing [Pérez et al., 2003]
I

Use the color gradient from the source image.

I

Use color border conditions on the target image.

I

Solve Poisson equation to reconstruct the new image.

33 / 37

Seamless copy in images

Poisson image editing [Pérez et al., 2003]
I

Use the color gradient from the source image.

I

Use color border conditions on the target image.

I

Solve Poisson equation to reconstruct the new image.

Seamless copy with gradient adaptation [Perrot et al., 2016]
I

Transport the gradient from the source to target color gradient distribution.

I

Solve the Poisson equation with the mapped source gradients.

I

Better respect of the color dynamic and limits false colors.
33 / 37

Seamless copy in images

Poisson image editing [Pérez et al., 2003]
I

Use the color gradient from the source image.

I

Use color border conditions on the target image.

I

Solve Poisson equation to reconstruct the new image.

Seamless copy with gradient adaptation [Perrot et al., 2016]
I

Transport the gradient from the source to target color gradient distribution.

I

Solve the Poisson equation with the mapped source gradients.

I

Better respect of the color dynamic and limits false colors.
33 / 37

Seamless copy with gradient adaptation

Example and webcam demo: https://github.com/ncourty/PoissonGradient
34 / 37

Section
Optimal transport
Introduction to OT
Wasserstein distance
Regularized optimal transport
Barycenters and geometry of optimal transport
Learning with optimal transport
Learning from histograms with OT
Learning from empirical distributions with OT
Mapping with optimal transport
Optimal transport mapping estimation
Color adaptation
Optimal transport for domain adaptation
Conclusion

34 / 37

Optimal transport for machine learning
OT matrix

Learning with optimal transport
I

Natural divergence for machine learning and estimation.

I

Cost encode complex relations in an histogram.

I

Regularization is the key (performance, smoothness).

I

Recent optimization procedures opened it to
medium/large scale datasets.

I

Sensible loss between non overlapping distributions.

I

Works with both histograms and empirical distributions.

Mapping with optimal transport
I

Optimal displacement from one distribution to another.

I

Can estimate smooth mapping for out of sample
displacement.

I

Domain, color and gradient adaptation, transfer
learning.
35 / 37

Optimal transport for machine learning

Current and future works
I

Joint distribution domain adaptation OT [Courty et al., 2017b].

I

Large scale OT and mapping estimation (SGD) [Seguy et al., 2017].

I

Approximate Wasserstein embedding for fast data mining [Courty et al., 2017a].

Open questions
I

Generalization bounds for learning with OT.

I

Learning the ground metric (supervised, unsupervised).

I

Large scale OT and mapping estimation, accelerated stochastic optimization.
36 / 37

Thank you
Python code available on GitHub:
https://github.com/rflamary/POTI OT LP solver, Sinkhorn (stabilized, −scaling, GPU)I Domain adaptation with OT.
I Barycenters, Wasserstein unmixing.
I Wasserstein Discriminant Analysis.

Papers available on my website:
https://remi.flamary.com/

37 / 37

References I
Agueh, M. and Carlier, G. (2011).
Barycenters in the wasserstein space.
SIAM Journal on Mathematical Analysis, 43(2):904–924.
Arjovsky, M., Chintala, S., and Bottou, L. (2017).
Wasserstein gan.
arXiv preprint arXiv:1701.07875.
Benamou, J.-D., Carlier, G., Cuturi, M., Nenna, L., and Peyré, G. (2015).
Iterative Bregman projections for regularized transportation problems.
SISC.
Bigot, J., Gouet, R., Klein, T., López, A., et al. (2017).
Geodesic pca in the wasserstein space by convex pca.
In Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, volume 53, pages
1–26. Institut Henri Poincaré.
Brenier, Y. (1991).
Polar factorization and monotone rearrangement of vector-valued functions.
Communications on pure and applied mathematics, 44(4):375–417.
Courty, N., Flamary, R., and Ducoffe, M. (2017a).
Learning wasserstein embeddings.
38 / 37

References II
Courty, N., Flamary, R., Habrard, A., and Rakotomamonjy, A. (2017b).
Joint distribution optimal transportation for domain adaptation.
In Neural Information Processing Systems (NIPS).
Courty, N., Flamary, R., Tuia, D., and Rakotomamonjy, A. (2016a).
Optimal transport for domain adaptation.
IEEE Transactions on Pattern Analysis and Machine Intelligence.
Courty, N., Flamary, R., Tuia, D., and Rakotomamonjy, A. (2016b).
Optimal transport for domain adaptation.
Pattern Analysis and Machine Intelligence, IEEE Transactions on.
Cuturi, M. (2013).
Sinkhorn distances: Lightspeed computation of optimal transportation.
In Neural Information Processing Systems (NIPS), pages 2292–2300.
Cuturi, M. and Peyré, G. (2016).
A smoothed dual approach for variational wasserstein problems.
SIAM Journal on Imaging Sciences, 9(1):320–343.
Dessein, A., Papadakis, N., and Rouas, J.-L. (2016).
Regularized optimal transport and the rot mover’s distance.
arXiv preprint arXiv:1610.06447.
39 / 37

References III
Emiya, V., Badeau, R., and David, B. (2010).
Multipitch estimation of piano sounds using a new probabilistic spectral smoothness
principle.
IEEE Transactions on Audio, Speech, and Language Processing, 18(6):1643–1654.
Ferradans, S., Papadakis, N., Peyré, G., and Aujol, J.-F. (2014).
Regularized discrete optimal transport.
SIAM Journal on Imaging Sciences, 7(3).
Flamary, R., Cuturi, M., Courty, N., and Rakotomamonjy, A. (2016a).
Wasserstein discriminant analysis.
arXiv preprint arXiv:1608.08063.
Flamary, R., Fevotte, C., Courty, N., and Emyia, V. (2016b).
Optimal spectral transportation with application to music transcription.
In Neural Information Processing Systems (NIPS).
Frogner, C., Zhang, C., Mobahi, H., Araya, M., and Poggio, T. A. (2015).
Learning with a wasserstein loss.
In Advances in Neural Information Processing Systems, pages 2053–2061.

40 / 37

References IV
Genevay, A., Cuturi, M., Peyré, G., and Bach, F. (2016).
Stochastic optimization for large-scale optimal transport.
In NIPS, pages 3432–3440.
Goodfellow, I., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S.,
Courville, A., and Bengio, Y. (2014).
Generative adversarial nets.
In Advances in neural information processing systems, pages 2672–2680.
Kantorovich, L. (1942).
On the translocation of masses.
C.R. (Doklady) Acad. Sci. URSS (N.S.), 37:199–201.
McCann, R. J. (1997).
A convexity principle for interacting gases.
Advances in mathematics, 128(1):153–179.
Monge, G. (1781).
Mémoire sur la théorie des déblais et des remblais.
De l’Imprimerie Royale.

41 / 37

References V
Pérez, P., Gangnet, M., and Blake, A. (2003).
Poisson image editing.
ACM Trans. on Graphics, 22(3).
Perrot, M., Courty, N., Flamary, R., and Habrard, A. (2016).
Mapping estimation for discrete optimal transport.
In Neural Information Processing Systems (NIPS).
Radford, A., Metz, L., and Chintala, S. (2015).
Unsupervised representation learning with deep convolutional generative adversarial
networks.
arXiv preprint arXiv:1511.06434.
Rolet, A., Cuturi, M., and Peyré, G. (2016).
Fast dictionary learning with a smoothed wasserstein loss.
In Proceedings of the 19th International Conference on Artificial Intelligence andStatistics, pages 630–638.
Rubner, Y., Tomasi, C., and Guibas, L. J. (2000).
The earth mover’s distance as a metric for image retrieval.
International journal of computer vision, 40(2):99–121.
42 / 37

References VI
Schmitz, M. A., Heitz, M., Bonneel, N., Mboula, F. M. N., Coeurjolly, D., Cuturi, M.,
Peyré, G., and Starck, J.-L. (2017).
Wasserstein dictionary learning: Optimal transport-based unsupervised non-linear
dictionary learning.
arXiv preprint arXiv:1708.01955.
Seguy, V., Bhushan Damodaran, B., Flamary, R., Courty, N., Rolet, A., and Blondel, M.
(2017).
Large-scale optimal transport and mapping estimation.
Seguy, V. and Cuturi, M. (2015).
Principal geodesic analysis for probability measures under the optimal transport metric.
In Advances in Neural Information Processing Systems, pages 3312–3320.
Solomon, J., De Goes, F., Peyré, G., Cuturi, M., Butscher, A., Nguyen, A., Du, T., andGuibas, L. (2015).
Convolutional wasserstein distances: Efficient optimal transportation on geometricdomains.
ACM Transactions on Graphics (TOG), 34(4):66.

43 / 37

References VII

Zen, G., Ricci, E., and Sebe, N. (2014).
Simultaneous ground metric learning and matrix factorization with earth mover’s
distance.
In ICPR, pages 3690–3695.
Zhao, J., Mathieu, M., and LeCun, Y. (2016).
Energy-based generative adversarial network.
arXiv preprint arXiv:1609.03126.

44 / 37

Collaborators

Barycenters

45 / 37