From 0fc6938dc15e8888b0a73fa4b6a421f39f0e0697 Mon Sep 17 00:00:00 2001 From: Rémi Flamary Date: Thu, 6 Jun 2019 12:09:34 +0200 Subject: update conf + readme --- docs/source/readme.rst | 30 +++++++++++++++++++----------- 1 file changed, 19 insertions(+), 11 deletions(-) (limited to 'docs/source/readme.rst') diff --git a/docs/source/readme.rst b/docs/source/readme.rst index e7c2bd1..d1063e8 100644 --- a/docs/source/readme.rst +++ b/docs/source/readme.rst @@ -12,9 +12,11 @@ It provides the following solvers: - OT Network Flow solver for the linear program/ Earth Movers Distance [1]. -- Entropic regularization OT solver with Sinkhorn Knopp Algorithm [2] - and stabilized version [9][10] and greedy SInkhorn [22] with optional - GPU implementation (requires cudamat). +- Entropic regularization OT solver with Sinkhorn Knopp Algorithm [2], + stabilized version [9][10] and greedy Sinkhorn [22] with optional GPU + implementation (requires cupy). +- Sinkhorn divergence [23] and entropic regularization OT from + empirical data. - Smooth optimal transport solvers (dual and semi-dual) for KL and squared L2 regularizations [17]. - Non regularized Wasserstein barycenters [16] with LP solver (only @@ -115,14 +117,9 @@ below 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) +- **ot.gpu** (GPU accelerated OT) depends on cupy that have to be + installed following instructions on `this + page `__. obviously you need CUDA installed and a compatible GPU. @@ -226,6 +223,7 @@ The contributors to this library are: - `Kilian Fatras `__ - `Alain Rakotomamonjy `__ +- `Vayer Titouan `__ This toolbox benefit a lot from open source research and we would like to thank the following persons for providing some code (in various @@ -366,6 +364,16 @@ approximation algorithms for optimal transport via Sinkhorn iteration `__, Advances in Neural Information Processing Systems (NIPS) 31 +[23] Aude, G., Peyré, G., Cuturi, M., `Learning Generative Models with +Sinkhorn Divergences `__, Proceedings +of the Twenty-First International Conference on Artficial Intelligence +and Statistics, (AISTATS) 21, 2018 + +[24] Vayer, T., Chapel, L., Flamary, R., Tavenard, R. and Courty, N. +(2019). `Optimal Transport for structured data with application on +graphs `__ Proceedings +of the 36th International Conference on Machine Learning (ICML). + .. |PyPI version| image:: https://badge.fury.io/py/POT.svg :target: https://badge.fury.io/py/POT .. |Anaconda Cloud| image:: https://anaconda.org/conda-forge/pot/badges/version.svg -- cgit v1.2.3 From 4e2f6b45662fe206414652ccc8f715c420f3b9cd Mon Sep 17 00:00:00 2001 From: Rémi Flamary Date: Mon, 24 Jun 2019 17:13:33 +0200 Subject: first shot part OT Wass --- docs/source/howto.rst | 25 ---------- docs/source/index.rst | 2 +- docs/source/quickstart.rst | 119 +++++++++++++++++++++++++++++++++++++++++++++ docs/source/readme.rst | 7 ++- 4 files changed, 126 insertions(+), 27 deletions(-) delete mode 100644 docs/source/howto.rst create mode 100644 docs/source/quickstart.rst (limited to 'docs/source/readme.rst') diff --git a/docs/source/howto.rst b/docs/source/howto.rst deleted file mode 100644 index 48b1532..0000000 --- a/docs/source/howto.rst +++ /dev/null @@ -1,25 +0,0 @@ - -How to ? -======== - -In the following we provide some pointers about which functions and classes -to use for different problems related to optimal transport (OTs). - -1. **How to solve a discrete optimal transport problem ?** - - The solver for discrete is the function :py:mod:`ot.emd` that returns - the OT transport matrix. If you want to solve a regularized OT you can - use :py:mod:`ot.sinkhorn`. - - More detailed examples can be seen on this :ref:`auto_examples/plot_OT_2D_samples` - - Here is a simple use case: - - .. 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 - - diff --git a/docs/source/index.rst b/docs/source/index.rst index d92f50f..03943e8 100644 --- a/docs/source/index.rst +++ b/docs/source/index.rst @@ -13,7 +13,7 @@ Contents :maxdepth: 3 self - howto + quickstart all auto_examples/index diff --git a/docs/source/quickstart.rst b/docs/source/quickstart.rst new file mode 100644 index 0000000..3d3ce98 --- /dev/null +++ b/docs/source/quickstart.rst @@ -0,0 +1,119 @@ + +Quick start +=========== + + + +In the following we provide some pointers about which functions and classes +to use for different problems related to optimal transport (OT). + + +Optimal transport and Wasserstein distance +------------------------------------------ + +The optimal transport problem between discrete distributions is often expressed +as + .. math:: + \gamma^* = arg\min_\gamma \sum_{i,j}\gamma_{i,j}M_{i,j} + + s.t. \gamma 1 = a; \gamma^T 1= b; \gamma\geq 0 + +where : + +- :math:`M\in\mathbb{R}_+^{m\times n}` is the metric cost matrix defining the cost to move mass from bin :math:`a_i` to bin :math:`b_j`. +- :math:`a` and :math:`b` are histograms (positive, sum to 1) that represent the weights of each samples in the source an target distributions. + +Solving the linear program above can be done using the function :any:`ot.emd` +that will return the optimal transport matrix :math:`\gamma^*`: + +.. 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 + +.. hint:: + Examples of use for :any:`ot.emd` are available in the following examples: + + - :any:`auto_examples/plot_OT_2D_samples` + - :any:`auto_examples/plot_OT_1D` + - :any:`auto_examples/plot_OT_L1_vs_L2` + + +The value of the OT solution is often more of interest that the OT matrix : + + .. math:: + W(a,b)=\min_\gamma \sum_{i,j}\gamma_{i,j}M_{i,j} + + s.t. \gamma 1 = a; \gamma^T 1= b; \gamma\geq 0 + + +where :math:`W(a,b)` is the `Wasserstein distance +`_ between distributions a and b +It is a metrix that has nice statistical +properties. It can computed from an already estimated OT matrix with +:code:`np.sum(T*M)` or directly with the function :any:`ot.emd2`. + +.. code:: python + + # a,b are 1D histograms (sum to 1 and positive) + # M is the ground cost matrix + W=ot.emd2(a,b,M) # Wasserstein distance / EMD value + +.. note:: + In POT, most functions that solve OT or regularized OT problems have two + versions that return the OT matrix or the value of the optimal solution. Fir + instance :any:`ot.emd` return the OT matrix and :any:`ot.emd2` return the + Wassertsein distance. + + +Regularized Optimal Transport +----------------------------- + +Wasserstein Barycenters +----------------------- + +Monge mapping and Domain adaptation with Optimal transport +---------------------------------------- + + +Other applications +------------------ + + +GPU acceleration +---------------- + + + +How to? +------- + + + +1. **How to solve a discrete optimal transport problem ?** + + The solver for discrete is the function :py:mod:`ot.emd` that returns + the OT transport matrix. If you want to solve a regularized OT you can + use :py:mod:`ot.sinkhorn`. + + + + Here is a simple use case: + + .. 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 + + More detailed examples can be seen on this + :doc:`auto_examples/plot_OT_2D_samples` + + +2. **Compute a Wasserstein distance** + + + + diff --git a/docs/source/readme.rst b/docs/source/readme.rst index d1063e8..b7828d3 100644 --- a/docs/source/readme.rst +++ b/docs/source/readme.rst @@ -206,7 +206,12 @@ nbviewer `__ +- `Nicolas Courty `__ + +The contributors to this library are - `Rémi Flamary `__ - `Nicolas Courty `__ -- cgit v1.2.3 From 2d7db0ed112b9349dc0b0c4cc7a9f3ea8da4ebed Mon Sep 17 00:00:00 2001 From: Rémi Flamary Date: Thu, 27 Jun 2019 15:01:13 +0200 Subject: update readme --- docs/source/readme.rst | 14 ++++++++++++++ 1 file changed, 14 insertions(+) (limited to 'docs/source/readme.rst') diff --git a/docs/source/readme.rst b/docs/source/readme.rst index b7828d3..320ddd5 100644 --- a/docs/source/readme.rst +++ b/docs/source/readme.rst @@ -35,6 +35,7 @@ It provides the following solvers: - Stochastic Optimization for Large-scale Optimal Transport (semi-dual problem [18] and dual problem [19]) - Non regularized free support Wasserstein barycenters [20]. +- Unbalanced OT with KL relaxation distance and barycenter [10, 25]. Some demonstrations (both in Python and Jupyter Notebook format) are available in the examples folder. @@ -69,6 +70,13 @@ modules: Pip installation ^^^^^^^^^^^^^^^^ +Note that due to a limitation of pip, ``cython`` and ``numpy`` need to +be installed prior to installing POT. This can be done easily with + +:: + + pip install numpy cython + You can install the toolbox through PyPI with: :: @@ -229,6 +237,8 @@ The contributors to this library are - `Alain Rakotomamonjy `__ - `Vayer Titouan `__ +- `Hicham Janati `__ (Unbalanced OT) +- `Romain Tavenard `__ (1d 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 @@ -379,6 +389,10 @@ and Statistics, (AISTATS) 21, 2018 graphs `__ Proceedings of the 36th International Conference on Machine Learning (ICML). +[25] Frogner C., Zhang C., Mobahi H., Araya-Polo M., Poggio T. (2019). +`Learning with a Wasserstein Loss `__ +Advances in Neural Information Processing Systems (NIPS). + .. |PyPI version| image:: https://badge.fury.io/py/POT.svg :target: https://badge.fury.io/py/POT .. |Anaconda Cloud| image:: https://anaconda.org/conda-forge/pot/badges/version.svg -- cgit v1.2.3 From 6fdce8f75000ec6e609371ae39484f7edbb19b2c Mon Sep 17 00:00:00 2001 From: Rémi Flamary Date: Tue, 2 Jul 2019 13:38:20 +0200 Subject: quickstart wda + start unbalanced --- docs/source/quickstart.rst | 148 +++++++++++++++++++++++++++++++++++++++++++-- docs/source/readme.rst | 2 - 2 files changed, 144 insertions(+), 6 deletions(-) (limited to 'docs/source/readme.rst') diff --git a/docs/source/quickstart.rst b/docs/source/quickstart.rst index 8cce1c9..8f4a24e 100644 --- a/docs/source/quickstart.rst +++ b/docs/source/quickstart.rst @@ -278,7 +278,7 @@ choose the quadratic regularization. Group Lasso regularization """""""""""""""""""""""""" -Another regularization that has been used in recent years is the group lasso +Another regularization that has been used in recent years [5]_ is the group lasso regularization .. math:: @@ -333,7 +333,7 @@ Another solver is proposed to solve the problem s.t. \gamma 1 = a; \gamma^T 1= b; \gamma\geq 0 where :math:`\Omega_e` is the entropic regularization. In this case we use a -generalized conditional gradient [7]_ implemented in :any:`ot.opim.gcg` that does not linearize the entropic term and +generalized conditional gradient [7]_ implemented in :any:`ot.optim.gcg` that does not linearize the entropic term and relies on :any:`ot.sinkhorn` for its iterations. .. hint:: @@ -421,11 +421,11 @@ Estimating the Wassresein barycenter with free support but fixed weights corresponds to solving the following optimization problem: .. math:: - \min_\{x_i\} \quad \sum_{k} w_kW(\mu,\mu_k) + \min_{\{x_i\}} \quad \sum_{k} w_kW(\mu,\mu_k) s.t. \quad \mu=\sum_{i=1}^n a_i\delta_{x_i} -WE provide an alternating solver based on [20]_ in +We provide an alternating solver based on [20]_ in :any:`ot.lp.free_support_barycenter`. This function minimize the problem and return an optimal support :math:`\{x_i\}` for uniform or given weights :math:`a`. @@ -443,13 +443,149 @@ return an optimal support :math:`\{x_i\}` for uniform or given weights Monge mapping and Domain adaptation ----------------------------------- +The original transport problem investigated by Gaspard Monge was seeking for a +mapping function that maps (or transports) between a source and target +distribution but that minimizes the transport loss. The existence and uniqueness of this +optimal mapping is still an open problem in the general case but has been proven +for smooth distributions by Brenier in his eponym `theorem +`__. We provide in +:any:`ot.da` several solvers for Monge mapping estimation and domain adaptation. + +Monge Mapping estimation +^^^^^^^^^^^^^^^^^^^^^^^^ + +We now discuss several approaches that are implemented in POT to estimate or +approximate a Monge mapping from finite distributions. + +First note that when the source and target distributions are supposed to be Gaussian +distributions, there exists a close form solution for the mapping and its an +affine function [14]_ of the form :math:`T(x)=Ax+b` . In this case we provide the function +:any:`ot.da.OT_mapping_linear` that return the operator :math:`A` and vector +:math:`b`. Note that if the number of samples is too small there is a parameter +:code:`reg` that provide a regularization for the covariance matrix estimation. + +For a more general mapping estimation we also provide the barycentric mapping +proposed in [6]_ . It is implemented in the class :any:`ot.da.EMDTransport` and +other transport based classes in :any:`ot.da` . Those classes are discussed more +in the following but follow an interface similar to sklearn classes. Finally a +method proposed in [8]_ that estimate a continuous mapping approximating the +barycentric mapping is provided in :any:`ot.da.joint_OT_mapping_linear` for +linear mapping and :any:`ot.da.joint_OT_mapping_kernel` for non linear mapping. + + .. hint:: + + Example of the linear Monge mapping estimation is available + in the following example: + + - :any:`auto_examples/plot_otda_linear_mapping` + +Domain adaptation classes +^^^^^^^^^^^^^^^^^^^^^^^^^ + +The use of OT for domain adaptation (OTDA) has been first proposed in [5]_ that also +introduced the group Lasso regularization. The main idea of OTDA is to estimate +a mapping of the samples between source and target distributions which allows to +transport labeled source samples onto the target distribution with no labels. + +We provide several classes based on :any:`ot.da.BaseTransport` that provide +several OT and mapping estimations. The interface of those classes is similar to +classifiers in sklearn toolbox. At initialization several parameters (for +instance regularization parameter) can be set. Then one needs to estimate the +mapping with function :any:`ot.da.BaseTransport.fit`. Finally one can map the +samples from source to target with :any:`ot.da.BaseTransport.transform` and +from target to source with :any:`ot.da.BaseTransport.inverse_transform`. Here is +an example for class :any:`ot.da.EMDTransport` + +.. code:: + + ot_emd = ot.da.EMDTransport() + ot_emd.fit(Xs=Xs, Xt=Xt) + + Mapped_Xs= ot_emd.transform(Xs=Xs) + +A list +of the provided implementation is given in the following note. + +.. note:: + + Here is a list of the mapping classes inheriting from + :any:`ot.da.BaseTransport` + + * :any:`ot.da.EMDTransport` : Barycentric mapping with EMD transport + * :any:`ot.da.SinkhornTransport` : Barycentric mapping with Sinkhorn transport + * :any:`ot.da.SinkhornL1l2Transport` : Barycentric mapping with Sinkhorn + + group Lasso regularization [5]_ + * :any:`ot.da.SinkhornLpl1Transport` : Barycentric mapping with Sinkhorn + + non convex group Lasso regularization [5]_ + * :any:`ot.da.LinearTransport` : Linear mapping estimation between Gaussians + [14]_ + * :any:`ot.da.MappingTransport` : Nonlinear mapping estimation [8]_ + +.. hint:: + + Example of the use of OTDA classes are available in the following exmaples: + + - :any:`auto_examples/plot_otda_color_images` + - :any:`auto_examples/plot_otda_mapping` + - :any:`auto_examples/plot_otda_mapping_colors_images` + - :any:`auto_examples/plot_otda_semi_supervised` Other applications ------------------ +We discuss in the following several implementations that has been used and +proposed in the OT and machine learning community. + Wasserstein Discriminant Analysis ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ +Wasserstein Discriminant Analysis [11]_ is a generalization of `Fisher Linear Discriminant +Analysis `__ that +allows discrimination between classes that are not linearly separable. It +consist in finding a linear projector optimizing the following criterion + +.. math:: + P = \text{arg}\min_P \frac{\sum_i OT_e(\mu_i\#P,\mu_i\#P)}{\sum_{i,j\neq i} + OT_e(\mu_i\#P,\mu_j\#P)} + +where :math:`\#` is the push-forward operator, :math:`OT_e` is the entropic OT +loss and :math:`\mu_i` is the +distribution of samples from class :math:`i`. :math:`P` is also constrained to +be in the Stiefel manifold. WDA can be solved in pot using function +:any:`ot.dr.wda`. It requires to have installed :code:`pymanopt` and +:code:`autograd` for manifold optimization and automatic differentiation +respectively. Note that we also provide the Fisher discriminant estimator in +:any:`ot.dr.wda` for easy comparison. + +.. warning:: + Note that due to the hard dependency on :code:`pymanopt` and + :code:`autograd`, :any:`ot.dr` is not imported by default. If you want to + use it you have to specifically import it with :code:`import ot.dr` . + +.. hint:: + + An example of the use of WDA is available in the following example: + + - :any:`auto_examples/plot_WDA` + + +Unbalanced optimal transport +^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + +Unbalanced OT is a relaxation of the original OT problem where the violation of +the constraint on the marginals is added to the objective of the optimization +problem: + +.. math:: + \min_\gamma \quad \sum_{i,j}\gamma_{i,j}M_{i,j} + reg\cdot\Omega(\gamma) + \alpha KL(\gamma 1, a) + \alpha KL(\gamma^T 1, b) + + s.t. \quad \gamma\geq 0 + + +where KL is the Kullback-Leibler divergence. This formulation allwos for +computing approximate mapping between distributions that do not have the same +amount of mass. Interestingly the problem can be solved with a generalization of +the Bregman projections algorithm [10]_. Gromov-Wasserstein ^^^^^^^^^^^^^^^^^^ @@ -461,6 +597,10 @@ GPU acceleration We provide several implementation of our OT solvers in :any:`ot.gpu`. Those implementation use the :code:`cupy` toolbox. +.. warning:: + Note that due to the hard dependency on :code:`cupy`, :any:`ot.gpu` is not + imported by default. If you want to + use it you have to specifically import it with :code:`import ot.gpu` . FAQ diff --git a/docs/source/readme.rst b/docs/source/readme.rst index 320ddd5..0871779 100644 --- a/docs/source/readme.rst +++ b/docs/source/readme.rst @@ -221,8 +221,6 @@ This toolbox has been created and is maintained by The contributors to this library are -- `Rémi Flamary `__ -- `Nicolas Courty `__ - `Alexandre Gramfort `__ - `Laetitia Chapel `__ - `Michael Perrot `__ -- cgit v1.2.3