1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
|
POT: Python Optimal Transport
=============================
|PyPI version| |Build Status| |Documentation Status|
This open source Python library provide several solvers for optimization
problems related to Optimal Transport for signal, image processing and
machine learning.
It provides the following solvers:
- OT solver for the linear program/ Earth Movers Distance [1].
- Entropic regularization OT solver with Sinkhorn Knopp Algorithm [2]
and stabilized version [9][10] with optional GPU implementation
(required cudamat).
- Bregman projections for Wasserstein barycenter [3] and unmixing [4].
- Optimal transport for domain adaptation with group lasso
regularization [5]
- Conditional gradient [6] and Generalized conditional gradient for
regularized OT [7].
- Joint OT matrix and mapping estimation [8].
- Wasserstein Discriminant Analysis [11] (requires autograd +
pymanopt).
- Gromov-Wasserstein distances and barycenters [12]
Some demonstrations (both in Python and Jupyter Notebook format) are
available in the examples folder.
Installation
------------
The library has been tested on Linux, MacOSX and Windows. It requires a
C++ compiler for using the EMD solver and relies on the following Python
modules:
- Numpy (>=1.11)
- Scipy (>=0.17)
- Cython (>=0.23)
- Matplotlib (>=1.5)
Pip installation
^^^^^^^^^^^^^^^^
You can install the toolbox through PyPI with:
::
pip install POT
or get the very latest version by downloading it and then running:
::
python setup.py install --user # for user install (no root)
Anaconda installation with conda-forge
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
If you use the Anaconda python distribution, POT is available in
`conda-forge <https://conda-forge.org>`__. To install it and the
required dependencies:
::
conda install -c conda-forge pot
Post installation check
^^^^^^^^^^^^^^^^^^^^^^^
After a correct installation, you should be able to import the module
without errors:
.. code:: python
import ot
Note that for easier access the module is name ot instead of pot.
Dependencies
~~~~~~~~~~~~
Some sub-modules require additional dependences which are discussed
below
- **ot.dr** (Wasserstein dimensionality rediuction) depends on autograd
and pymanopt that can be installed with:
::
pip install pymanopt autograd
- **ot.gpu** (GPU accelerated OT) depends on cudamat that have to be
installed with:
::
git clone https://github.com/cudamat/cudamat.git
cd cudamat
python setup.py install --user # for user install (no root)
obviously you need CUDA installed and a compatible GPU.
Examples
--------
Short examples
~~~~~~~~~~~~~~
- Import the toolbox
.. code:: python
import ot
- Compute Wasserstein distances
.. code:: python
# a,b are 1D histograms (sum to 1 and positive)
# M is the ground cost matrix
Wd=ot.emd2(a,b,M) # exact linear program
Wd_reg=ot.sinkhorn2(a,b,M,reg) # entropic regularized OT
# if b is a matrix compute all distances to a and return a vector
- Compute OT matrix
.. code:: python
# a,b are 1D histograms (sum to 1 and positive)
# M is the ground cost matrix
T=ot.emd(a,b,M) # exact linear program
T_reg=ot.sinkhorn(a,b,M,reg) # entropic regularized OT
- Compute Wasserstein barycenter
.. code:: python
# A is a n*d matrix containing d 1D histograms
# M is the ground cost matrix
ba=ot.barycenter(A,M,reg) # reg is regularization parameter
Examples and Notebooks
~~~~~~~~~~~~~~~~~~~~~~
The examples folder contain several examples and use case for the
library. The full documentation is available on
`Readthedocs <http://pot.readthedocs.io/>`__.
Here is a list of the Python notebooks available
`here <https://github.com/rflamary/POT/blob/master/notebooks/>`__ if you
want a quick look:
- `1D optimal
transport <https://github.com/rflamary/POT/blob/master/notebooks/plot_OT_1D.ipynb>`__
- `OT Ground
Loss <https://github.com/rflamary/POT/blob/master/notebooks/plot_OT_L1_vs_L2.ipynb>`__
- `Multiple EMD
computation <https://github.com/rflamary/POT/blob/master/notebooks/plot_compute_emd.ipynb>`__
- `2D optimal transport on empirical
distributions <https://github.com/rflamary/POT/blob/master/notebooks/plot_OT_2D_samples.ipynb>`__
- `1D Wasserstein
barycenter <https://github.com/rflamary/POT/blob/master/notebooks/plot_barycenter_1D.ipynb>`__
- `OT with user provided
regularization <https://github.com/rflamary/POT/blob/master/notebooks/plot_optim_OTreg.ipynb>`__
- `Domain adaptation with optimal
transport <https://github.com/rflamary/POT/blob/master/notebooks/plot_otda_d2.ipynb>`__
- `Color transfer in
images <https://github.com/rflamary/POT/blob/master/notebooks/plot_otda_color_images.ipynb>`__
- `OT mapping estimation for domain
adaptation <https://github.com/rflamary/POT/blob/master/notebooks/plot_otda_mapping.ipynb>`__
- `OT mapping estimation for color transfer in
images <https://github.com/rflamary/POT/blob/master/notebooks/plot_otda_mapping_colors_images.ipynb>`__
- `Wasserstein Discriminant
Analysis <https://github.com/rflamary/POT/blob/master/notebooks/plot_WDA.ipynb>`__
- `Gromov
Wasserstein <https://github.com/rflamary/POT/blob/master/notebooks/plot_gromov.ipynb>`__
- `Gromov Wasserstein
Barycenter <https://github.com/rflamary/POT/blob/master/notebooks/plot_gromov_barycenter.ipynb>`__
You can also see the notebooks with `Jupyter
nbviewer <https://nbviewer.jupyter.org/github/rflamary/POT/tree/master/notebooks/>`__.
Acknowledgements
----------------
The contributors to this library are:
- `Rémi Flamary <http://remi.flamary.com/>`__
- `Nicolas Courty <http://people.irisa.fr/Nicolas.Courty/>`__
- `Alexandre Gramfort <http://alexandre.gramfort.net/>`__
- `Laetitia Chapel <http://people.irisa.fr/Laetitia.Chapel/>`__
- `Michael Perrot <http://perso.univ-st-etienne.fr/pem82055/>`__
(Mapping estimation)
- `Léo Gautheron <https://github.com/aje>`__ (GPU implementation)
- `Nathalie
Gayraud <https://www.linkedin.com/in/nathalie-t-h-gayraud/?ppe=1>`__
- `Stanislas Chambon <https://slasnista.github.io/>`__
- `Antoine Rolet <https://arolet.github.io/>`__
- Erwan Vautier (Gromov-Wasserstein)
This toolbox benefit a lot from open source research and we would like
to thank the following persons for providing some code (in various
languages):
- `Gabriel Peyré <http://gpeyre.github.io/>`__ (Wasserstein Barycenters
in Matlab)
- `Nicolas Bonneel <http://liris.cnrs.fr/~nbonneel/>`__ ( C++ code for
EMD)
- `Marco Cuturi <http://marcocuturi.net/>`__ (Sinkhorn Knopp in
Matlab/Cuda)
Using and citing the toolbox
----------------------------
If you use this toolbox in your research and find it useful, please cite
POT using the following bibtex reference:
::
@article{flamary2017pot,
title={POT Python Optimal Transport library},
author={Flamary, R{\'e}mi and Courty, Nicolas},
year={2017}
}
Contributions and code of conduct
---------------------------------
Every contribution is welcome and should respect the `contribution
guidelines <CONTRIBUTING.md>`__. Each member of the project is expected
to follow the `code of conduct <CODE_OF_CONDUCT.md>`__.
Support
-------
You can ask questions and join the development discussion:
- On the `POT Slack channel <https://pot-toolbox.slack.com>`__
- On the POT `mailing
list <https://mail.python.org/mm3/mailman3/lists/pot.python.org/>`__
You can also post bug reports and feature requests in Github issues.
Make sure to read our `guidelines <CONTRIBUTING.md>`__ first.
References
----------
[1] Bonneel, N., Van De Panne, M., Paris, S., & Heidrich, W. (2011,
December). `Displacement interpolation using Lagrangian mass
transport <https://people.csail.mit.edu/sparis/publi/2011/sigasia/Bonneel_11_Displacement_Interpolation.pdf>`__.
In ACM Transactions on Graphics (TOG) (Vol. 30, No. 6, p. 158). ACM.
[2] Cuturi, M. (2013). `Sinkhorn distances: Lightspeed computation of
optimal transport <https://arxiv.org/pdf/1306.0895.pdf>`__. In Advances
in Neural Information Processing Systems (pp. 2292-2300).
[3] Benamou, J. D., Carlier, G., Cuturi, M., Nenna, L., & Peyré, G.
(2015). `Iterative Bregman projections for regularized transportation
problems <https://arxiv.org/pdf/1412.5154.pdf>`__. SIAM Journal on
Scientific Computing, 37(2), A1111-A1138.
[4] S. Nakhostin, N. Courty, R. Flamary, D. Tuia, T. Corpetti,
`Supervised planetary unmixing with optimal
transport <https://hal.archives-ouvertes.fr/hal-01377236/document>`__,
Whorkshop on Hyperspectral Image and Signal Processing : Evolution in
Remote Sensing (WHISPERS), 2016.
[5] N. Courty; R. Flamary; D. Tuia; A. Rakotomamonjy, `Optimal Transport
for Domain Adaptation <https://arxiv.org/pdf/1507.00504.pdf>`__, in IEEE
Transactions on Pattern Analysis and Machine Intelligence , vol.PP,
no.99, pp.1-1
[6] Ferradans, S., Papadakis, N., Peyré, G., & Aujol, J. F. (2014).
`Regularized discrete optimal
transport <https://arxiv.org/pdf/1307.5551.pdf>`__. SIAM Journal on
Imaging Sciences, 7(3), 1853-1882.
[7] Rakotomamonjy, A., Flamary, R., & Courty, N. (2015). `Generalized
conditional gradient: analysis of convergence and
applications <https://arxiv.org/pdf/1510.06567.pdf>`__. arXiv preprint
arXiv:1510.06567.
[8] M. Perrot, N. Courty, R. Flamary, A. Habrard, `Mapping estimation
for discrete optimal
transport <http://remi.flamary.com/biblio/perrot2016mapping.pdf>`__,
Neural Information Processing Systems (NIPS), 2016.
[9] Schmitzer, B. (2016). `Stabilized Sparse Scaling Algorithms for
Entropy Regularized Transport
Problems <https://arxiv.org/pdf/1610.06519.pdf>`__. arXiv preprint
arXiv:1610.06519.
[10] Chizat, L., Peyré, G., Schmitzer, B., & Vialard, F. X. (2016).
`Scaling algorithms for unbalanced transport
problems <https://arxiv.org/pdf/1607.05816.pdf>`__. arXiv preprint
arXiv:1607.05816.
[11] Flamary, R., Cuturi, M., Courty, N., & Rakotomamonjy, A. (2016).
`Wasserstein Discriminant
Analysis <https://arxiv.org/pdf/1608.08063.pdf>`__. arXiv preprint
arXiv:1608.08063.
[12] Gabriel Peyré, Marco Cuturi, and Justin Solomon,
`Gromov-Wasserstein averaging of kernel and distance
matrices <http://proceedings.mlr.press/v48/peyre16.html>`__
International Conference on Machine Learning (ICML). 2016.
[13] Mémoli, Facundo. `Gromov–Wasserstein distances and the metric
approach to object
matching <https://media.adelaide.edu.au/acvt/Publications/2011/2011-Gromov%E2%80%93Wasserstein%20Distances%20and%20the%20Metric%20Approach%20to%20Object%20Matching.pdf>`__.
Foundations of computational mathematics 11.4 (2011): 417-487.
.. |PyPI version| image:: https://badge.fury.io/py/POT.svg
:target: https://badge.fury.io/py/POT
.. |Build Status| image:: https://travis-ci.org/rflamary/POT.svg?branch=master
:target: https://travis-ci.org/rflamary/POT
.. |Documentation Status| image:: https://readthedocs.org/projects/pot/badge/?version=latest
:target: http://pot.readthedocs.io/en/latest/?badge=latest
|