diff options
| -rw-r--r-- | README.md | 4 | ||||
| -rw-r--r-- | docs/source/quickstart.rst | 64 | ||||
| -rw-r--r-- | docs/source/readme.rst | 104 | ||||
| -rwxr-xr-x | ot/partial.py | 68 |
4 files changed, 181 insertions, 59 deletions
@@ -261,4 +261,6 @@ You can also post bug reports and feature requests in Github issues. Make sure t [27] Redko I., Courty N., Flamary R., Tuia D. (2019). [Optimal Transport for Multi-source Domain Adaptation under Target Shift](http://proceedings.mlr.press/v89/redko19a.html), Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics (AISTATS) 22, 2019. -[28] Chapel, L., Alaya, M., Gasso, G. (2019). [Partial Gromov-Wasserstein with Applications on Positive-Unlabeled Learning"] (https://arxiv.org/abs/2002.08276), arXiv preprint arXiv:2002.08276.
\ No newline at end of file +[28] Caffarelli, L. A., McCann, R. J. (2020). [Free boundaries in optimal transport and Monge-Ampere obstacle problems](http://www.math.toronto.edu/~mccann/papers/annals2010.pdf), Annals of mathematics, 673-730. + +[29] Chapel, L., Alaya, M., Gasso, G. (2019). [Partial Gromov-Wasserstein with Applications on Positive-Unlabeled Learning](https://arxiv.org/abs/2002.08276), arXiv preprint arXiv:2002.08276.
\ No newline at end of file diff --git a/docs/source/quickstart.rst b/docs/source/quickstart.rst index 978eaff..d56f812 100644 --- a/docs/source/quickstart.rst +++ b/docs/source/quickstart.rst @@ -645,6 +645,53 @@ implemented the main function :any:`ot.barycenter_unbalanced`. - :any:`auto_examples/plot_UOT_barycenter_1D` +Partial optimal transport +^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + +Partial OT is a variant of the optimal transport problem when only a fixed amount of mass m +is to be transported. The partial OT metric between two histograms a and b is defined as [28]_: + +.. math:: + \gamma = \arg\min_\gamma <\gamma,M>_F + + s.t. + \gamma\geq 0 \\ + \gamma 1 \leq a\\ + \gamma^T 1 \leq b\\ + 1^T \gamma^T 1 = m \leq \min\{\|a\|_1, \|b\|_1\} + + +Interestingly the problem can be casted into a regular OT problem by adding reservoir points +in which the surplus mass is sent [29]_. We provide a solver for partial OT +in :any:`ot.partial`. The exact resolution of the problem is computed in :any:`ot.partial.partial_wasserstein` +and :any:`ot.partial.partial_wasserstein2` that return respectively the OT matrix and the value of the +linear term. The entropic solution of the problem is computed in :any:`ot.partial.entropic_partial_wasserstein` +(see [3]_). + +The partial Gromov-Wasserstein formulation of the problem + +.. math:: + GW = \min_\gamma \sum_{i,j,k,l} L(C1_{i,k},C2_{j,l})*\gamma_{i,j}*\gamma_{k,l} + + s.t. + \gamma\geq 0 \\ + \gamma 1 \leq a\\ + \gamma^T 1 \leq b\\ + 1^T \gamma^T 1 = m \leq \min\{\|a\|_1, \|b\|_1\} + +is computed in :any:`ot.partial.partial_gromov_wasserstein` and in +:any:`ot.partial.entropic_partial_gromov_wasserstein` when considering the entropic +regularization of the problem. + + +.. hint:: + + Examples of the use of :any:`ot.partial` are available in : + + - :any:`auto_examples/plot_partial` + + + Gromov-Wasserstein ^^^^^^^^^^^^^^^^^^ @@ -921,3 +968,20 @@ References .. [25] Frogner C., Zhang C., Mobahi H., Araya-Polo M., Poggio T. : Learning with a Wasserstein Loss, Advances in Neural Information Processing Systems (NIPS) 2015 + +.. [26] Alaya M. Z., Bérar M., Gasso G., Rakotomamonjy A. (2019). Screening Sinkhorn + Algorithm for Regularized Optimal Transport <https://papers.nips.cc/paper/9386-screening-sinkhorn-algorithm-for-regularized-optimal-transport>, + Advances in Neural Information Processing Systems 33 (NeurIPS). + +.. [27] Redko I., Courty N., Flamary R., Tuia D. (2019). Optimal Transport for Multi-source + Domain Adaptation under Target Shift <http://proceedings.mlr.press/v89/redko19a.html>, + Proceedings of the Twenty-Second International Conference on Artificial Intelligence + and Statistics (AISTATS) 22, 2019. + +.. [28] Caffarelli, L. A., McCann, R. J. (2020). Free boundaries in optimal transport and + Monge-Ampere obstacle problems <http://www.math.toronto.edu/~mccann/papers/annals2010.pdf>, + Annals of mathematics, 673-730. + +.. [29] Chapel, L., Alaya, M., Gasso, G. (2019). Partial Gromov-Wasserstein with + Applications on Positive-Unlabeled Learning <https://arxiv.org/abs/2002.08276>, + arXiv preprint arXiv:2002.08276. diff --git a/docs/source/readme.rst b/docs/source/readme.rst index d5f2161..6d98dc5 100644 --- a/docs/source/readme.rst +++ b/docs/source/readme.rst @@ -36,6 +36,9 @@ It provides the following solvers: problem [18] and dual problem [19]) - Non regularized free support Wasserstein barycenters [20]. - Unbalanced OT with KL relaxation distance and barycenter [10, 25]. +- Screening Sinkhorn Algorithm for OT [26]. +- JCPOT algorithm for multi-source domain adaptation with target shift + [27]. Some demonstrations (both in Python and Jupyter Notebook format) are available in the examples folder. @@ -48,19 +51,19 @@ POT using the following bibtex reference: :: - @misc{flamary2017pot, - title={POT Python Optimal Transport library}, - author={Flamary, R{'e}mi and Courty, Nicolas}, - url={https://github.com/rflamary/POT}, - year={2017} - } + @misc{flamary2017pot, + title={POT Python Optimal Transport library}, + author={Flamary, R{'e}mi and Courty, Nicolas}, + url={https://github.com/rflamary/POT}, + year={2017} + } 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: +C++ compiler for building/installing the EMD solver and relies on the +following Python modules: - Numpy (>=1.11) - Scipy (>=1.0) @@ -75,19 +78,19 @@ be installed prior to installing POT. This can be done easily with :: - pip install numpy cython + pip install numpy cython You can install the toolbox through PyPI with: :: - pip install POT + 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) + python setup.py install --user # for user install (no root) Anaconda installation with conda-forge ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ @@ -98,7 +101,7 @@ required dependencies: :: - conda install -c conda-forge pot + conda install -c conda-forge pot Post installation check ^^^^^^^^^^^^^^^^^^^^^^^ @@ -108,7 +111,7 @@ without errors: .. code:: python - import ot + import ot Note that for easier access the module is name ot instead of pot. @@ -121,9 +124,9 @@ below - **ot.dr** (Wasserstein dimensionality reduction) depends on autograd and pymanopt that can be installed with: - :: +:: - pip install pymanopt autograd + pip install pymanopt autograd - **ot.gpu** (GPU accelerated OT) depends on cupy that have to be installed following instructions on `this @@ -139,36 +142,36 @@ Short examples - Import the toolbox - .. code:: python +.. code:: python - import ot + import ot - Compute Wasserstein distances - .. code:: python +.. 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 + # 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 +.. 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 + # 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 +.. 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 + # 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 ~~~~~~~~~~~~~~~~~~~~~~ @@ -207,6 +210,10 @@ want a quick look: 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>`__ +- `Fused Gromov + Wasserstein <https://github.com/rflamary/POT/blob/master/notebooks/plot_fgw.ipynb>`__ +- `Fused Gromov Wasserstein + Barycenter <https://github.com/rflamary/POT/blob/master/notebooks/plot_barycenter_fgw.ipynb>`__ You can also see the notebooks with `Jupyter nbviewer <https://nbviewer.jupyter.org/github/rflamary/POT/tree/master/notebooks/>`__. @@ -237,6 +244,7 @@ The contributors to this library are - `Vayer Titouan <https://tvayer.github.io/>`__ - `Hicham Janati <https://hichamjanati.github.io/>`__ (Unbalanced OT) - `Romain Tavenard <https://rtavenar.github.io/>`__ (1d Wasserstein) +- `Mokhtar Z. Alaya <http://mzalaya.github.io/>`__ (Screenkhorn) This toolbox benefit a lot from open source research and we would like to thank the following persons for providing some code (in various @@ -274,11 +282,11 @@ 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. +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). +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 @@ -387,17 +395,29 @@ and Statistics, (AISTATS) 21, 2018 graphs <http://proceedings.mlr.press/v97/titouan19a.html>`__ Proceedings of the 36th International Conference on Machine Learning (ICML). -[25] Frogner C., Zhang C., Mobahi H., Araya-Polo M., Poggio T. (2019). +[25] Frogner C., Zhang C., Mobahi H., Araya-Polo M., Poggio T. (2015). `Learning with a Wasserstein Loss <http://cbcl.mit.edu/wasserstein/>`__ Advances in Neural Information Processing Systems (NIPS). -[26] Caffarelli, L. A., McCann, R. J. (2020). `Free boundaries in optimal transport and -Monge-Ampere obstacle problems <http://www.math.toronto.edu/~mccann/papers/annals2010.pdf>`__, -Annals of mathematics, 673-730. - -[27] Chapel, L., Alaya, M., Gasso, G. (2019). `Partial Gromov-Wasserstein with Applications -on Positive-Unlabeled Learning <https://arxiv.org/abs/2002.08276>`__. arXiv preprint -arXiv:2002.08276. +[26] Alaya M. Z., Bérar M., Gasso G., Rakotomamonjy A. (2019). +`Screening Sinkhorn Algorithm for Regularized Optimal +Transport <https://papers.nips.cc/paper/9386-screening-sinkhorn-algorithm-for-regularized-optimal-transport>`__, +Advances in Neural Information Processing Systems 33 (NeurIPS). + +[27] Redko I., Courty N., Flamary R., Tuia D. (2019). `Optimal Transport +for Multi-source Domain Adaptation under Target +Shift <http://proceedings.mlr.press/v89/redko19a.html>`__, Proceedings +of the Twenty-Second International Conference on Artificial Intelligence +and Statistics (AISTATS) 22, 2019. + +[28] Caffarelli, L. A., McCann, R. J. (2020). [Free boundaries in +optimal transport and Monge-Ampere obstacle problems] +(http://www.math.toronto.edu/~mccann/papers/annals2010.pdf), Annals of +mathematics, 673-730. + +[29] Chapel, L., Alaya, M., Gasso, G. (2019). [Partial +Gromov-Wasserstein with Applications on Positive-Unlabeled Learning"] +(https://arxiv.org/abs/2002.08276), arXiv preprint arXiv:2002.08276. .. |PyPI version| image:: https://badge.fury.io/py/POT.svg :target: https://badge.fury.io/py/POT diff --git a/ot/partial.py b/ot/partial.py index d32e054..f325d98 100755 --- a/ot/partial.py +++ b/ot/partial.py @@ -1,4 +1,3 @@ -#!/usr/bin/env python3 # -*- coding: utf-8 -*- """ Partial OT @@ -30,7 +29,9 @@ def partial_wasserstein_lagrange(a, b, M, reg_m=None, nb_dummies=1, log=False, 1^T \gamma^T 1 = m \leq \min\{\|a\|_1, \|b\|_1\} - or equivalently: + or equivalently (see Chizat, L., Peyré, G., Schmitzer, B., & Vialard, F. X. + (2018). An interpolating distance between optimal transport and Fisher–Rao + metrics. Foundations of Computational Mathematics, 18(1), 1-44.) .. math:: \gamma = \arg\min_\gamma <\gamma,M>_F + \sqrt(\lambda/2) @@ -47,7 +48,8 @@ def partial_wasserstein_lagrange(a, b, M, reg_m=None, nb_dummies=1, log=False, - :math:`\lambda` is the lagragian cost. Tuning its value allows attaining a given mass to be transported m - The formulation of the problem has been proposed in [26]_ + The formulation of the problem has been proposed in [28]_ + Parameters ---------- @@ -59,9 +61,17 @@ def partial_wasserstein_lagrange(a, b, M, reg_m=None, nb_dummies=1, log=False, cost matrix for the quadratic cost reg_m : float, optional Lagragian cost + nb_dummies : int, optional, default:1 + number of reservoir points to be added (to avoid numerical + instabilities, increase its value if an error is raised) log : bool, optional record log if True + .. warning:: + When dealing with a large number of points, the EMD solver may face + some instabilities, especially when the mass associated to the dummy + point is large. To avoid them, increase the number of dummy points + (allows a smoother repartition of the mass over the points). Returns ------- @@ -88,7 +98,7 @@ def partial_wasserstein_lagrange(a, b, M, reg_m=None, nb_dummies=1, log=False, References ---------- - .. [26] Caffarelli, L. A., & McCann, R. J. (2010) Free boundaries in + .. [28] Caffarelli, L. A., & McCann, R. J. (2010) Free boundaries in optimal transport and Monge-Ampere obstacle problems. Annals of mathematics, 673-730. @@ -182,6 +192,13 @@ def partial_wasserstein(a, b, M, m=None, nb_dummies=1, log=False, **kwargs): record log if True + .. warning:: + When dealing with a large number of points, the EMD solver may face + some instabilities, especially when the mass associated to the dummy + point is large. To avoid them, increase the number of dummy points + (allows a smoother repartition of the mass over the points). + + Returns ------- :math:`gamma` : (dim_a x dim_b) ndarray @@ -206,10 +223,10 @@ def partial_wasserstein(a, b, M, m=None, nb_dummies=1, log=False, **kwargs): References ---------- - .. [26] Caffarelli, L. A., & McCann, R. J. (2010) Free boundaries in + .. [28] Caffarelli, L. A., & McCann, R. J. (2010) Free boundaries in optimal transport and Monge-Ampere obstacle problems. Annals of mathematics, 673-730. - .. [28] Chapel, L., Alaya, M., Gasso, G. (2019). "Partial Gromov- + .. [29] Chapel, L., Alaya, M., Gasso, G. (2019). "Partial Gromov- Wasserstein with Applications on Positive-Unlabeled Learning". arXiv preprint arXiv:2002.08276. @@ -289,6 +306,13 @@ def partial_wasserstein2(a, b, M, m=None, nb_dummies=1, log=False, **kwargs): record log if True + .. warning:: + When dealing with a large number of points, the EMD solver may face + some instabilities, especially when the mass associated to the dummy + point is large. To avoid them, increase the number of dummy points + (allows a smoother repartition of the mass over the points). + + Returns ------- :math:`gamma` : (dim_a x dim_b) ndarray @@ -311,10 +335,10 @@ def partial_wasserstein2(a, b, M, m=None, nb_dummies=1, log=False, **kwargs): References ---------- - .. [26] Caffarelli, L. A., & McCann, R. J. (2010) Free boundaries in + .. [28] Caffarelli, L. A., & McCann, R. J. (2010) Free boundaries in optimal transport and Monge-Ampere obstacle problems. Annals of mathematics, 673-730. - .. [28] Chapel, L., Alaya, M., Gasso, G. (2019). "Partial Gromov- + .. [29] Chapel, L., Alaya, M., Gasso, G. (2019). "Partial Gromov- Wasserstein with Applications on Positive-Unlabeled Learning". arXiv preprint arXiv:2002.08276. """ @@ -411,7 +435,7 @@ def partial_gromov_wasserstein(C1, C2, p, q, m=None, nb_dummies=1, G0=None, - a and b are the sample weights - m is the amount of mass to be transported - The formulation of the problem has been proposed in [28]_ + The formulation of the problem has been proposed in [29]_ Parameters @@ -435,13 +459,12 @@ def partial_gromov_wasserstein(C1, C2, p, q, m=None, nb_dummies=1, G0=None, (default: 1) numItermax : int, optional Max number of iterations + tol : float, optional + tolerance for stopping iterations log : bool, optional return log if True verbose : bool, optional Print information along iterations - armijo : bool, optional - If True the steps of the line-search is found via an armijo research. Else closed form is used. - If there is convergence issues use False. **kwargs : dict parameters can be directly passed to the emd solver @@ -477,7 +500,7 @@ def partial_gromov_wasserstein(C1, C2, p, q, m=None, nb_dummies=1, G0=None, References ---------- - .. [28] Chapel, L., Alaya, M., Gasso, G. (2019). "Partial Gromov- + .. [29] Chapel, L., Alaya, M., Gasso, G. (2019). "Partial Gromov- Wasserstein with Applications on Positive-Unlabeled Learning". arXiv preprint arXiv:2002.08276. @@ -546,7 +569,7 @@ def partial_gromov_wasserstein(C1, C2, p, q, m=None, nb_dummies=1, G0=None, def partial_gromov_wasserstein2(C1, C2, p, q, m=None, nb_dummies=1, G0=None, - thres=0.75, numItermax=1000, tol=1e-7, + thres=1, numItermax=1000, tol=1e-7, log=False, verbose=False, **kwargs): r""" Solves the partial optimal transport problem @@ -570,7 +593,7 @@ def partial_gromov_wasserstein2(C1, C2, p, q, m=None, nb_dummies=1, G0=None, - a and b are the sample weights - m is the amount of mass to be transported - The formulation of the problem has been proposed in [28]_ + The formulation of the problem has been proposed in [29]_ Parameters @@ -594,6 +617,8 @@ def partial_gromov_wasserstein2(C1, C2, p, q, m=None, nb_dummies=1, G0=None, (default: 1) numItermax : int, optional Max number of iterations + tol : float, optional + tolerance for stopping iterations log : bool, optional return log if True verbose : bool, optional @@ -602,6 +627,13 @@ def partial_gromov_wasserstein2(C1, C2, p, q, m=None, nb_dummies=1, G0=None, parameters can be directly passed to the emd solver + .. warning:: + When dealing with a large number of points, the EMD solver may face + some instabilities, especially when the mass associated to the dummy + point is large. To avoid them, increase the number of dummy points + (allows a smoother repartition of the mass over the points). + + Returns ------- partial_gw_dist : (dim_a x dim_b) ndarray @@ -627,7 +659,7 @@ def partial_gromov_wasserstein2(C1, C2, p, q, m=None, nb_dummies=1, G0=None, References ---------- - .. [28] Chapel, L., Alaya, M., Gasso, G. (2019). "Partial Gromov- + .. [29] Chapel, L., Alaya, M., Gasso, G. (2019). "Partial Gromov- Wasserstein with Applications on Positive-Unlabeled Learning". arXiv preprint arXiv:2002.08276. @@ -831,6 +863,8 @@ def entropic_partial_gromov_wasserstein(C1, C2, p, q, reg, m=None, G0=None, Initialisation of the transportation matrix numItermax : int, optional Max number of iterations + tol : float, optional + Stop threshold on error (>0) log : bool, optional return log if True verbose : bool, optional @@ -966,6 +1000,8 @@ def entropic_partial_gromov_wasserstein2(C1, C2, p, q, reg, m=None, G0=None, Initialisation of the transportation matrix numItermax : int, optional Max number of iterations + tol : float, optional + Stop threshold on error (>0) log : bool, optional return log if True verbose : bool, optional |