Quick start guide ================= 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 ------------------------------------------ .. 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. For instance :any:`ot.emd` return the OT matrix and :any:`ot.emd2` return the Wassertsein distance. Solving optimal transport ^^^^^^^^^^^^^^^^^^^^^^^^^ The optimal transport problem between discrete distributions is often expressed as .. math:: \gamma^* = arg\min_\gamma \quad \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 The method used for solving the OT problem is the network simplex, it is implemented in C from [1]_. It has a complexity of :math:`O(n^3)` but the solver is quite efficient and uses sparsity of the solution. .. 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` Computing Wasserstein distance ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ The value of the OT solution is often more of interest that the OT matrix : .. math:: OT(a,b)=\min_\gamma \quad \sum_{i,j}\gamma_{i,j}M_{i,j} s.t. \gamma 1 = a; \gamma^T 1= b; \gamma\geq 0 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 that the well known `Wasserstein distance `_ between distributions a and b is defined as .. math:: W_p(a,b)=(\min_\gamma \sum_{i,j}\gamma_{i,j}\|x_i-y_j\|_p)^\frac{1}{p} s.t. \gamma 1 = a; \gamma^T 1= b; \gamma\geq 0 This means that if you want to compute the :math:`W_2` you need to compute the square root of :any:`ot.emd2` when providing :code:`M=ot.dist(xs,xt)` that use the squared euclidean distance by default. Computing the :math:`W_1` wasserstein distance can be done directly with :any:`ot.emd2` when providing :code:`M=ot.dist(xs,xt, metric='euclidean')` to use the euclidean distance. .. hint:: Examples of use for :any:`ot.emd2` are available in the following examples: - :any:`auto_examples/plot_compute_emd` Special cases ^^^^^^^^^^^^^ Note that the OT problem and the corresponding Wasserstein distance can in some special cases be computed very efficiently. For instance when the samples are in 1D, then the OT problem can be solved in :math:`O(n\log(n))` by using a simple sorting. In this case we provide the function :any:`ot.emd_1d` and :any:`ot.emd2_1d` to return respectively the OT matrix and value. Note that since the solution is very sparse the :code:`sparse` parameter of :any:`ot.emd_1d` allows for solving and returning the solution for very large problems. Note that in order to computed directly the :math:`W_p` Wasserstein distance in 1D we provide the function :any:`ot.wasserstein_1d` that takes :code:`p` as a parameter. Another specials for estimating OT and Monge mapping is between Gaussian distributions. In this case there exists a close form solution given in Remark 2.29 in [15]_ and the Monge mapping is an affine function and can be also computed from the covariances and means of the source and target distributions. In this case when the finite sample dataset is supposed gaussian, we provide :any:`ot.da.OT_mapping_linear` that returns the parameters for the Monge mapping. Regularized Optimal Transport ----------------------------- Recent developments have shown the interest of regularized OT both in terms of computational and statistical properties. We address in this section the regularized OT problem that can be expressed as .. math:: \gamma^* = arg\min_\gamma \quad \sum_{i,j}\gamma_{i,j}M_{i,j} + \lambda\Omega(\gamma) 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. - :math:`\Omega` is the regularization term. We discuss in the following specific algorithms that can be used depending on the regularization term. Entropic regularized OT ^^^^^^^^^^^^^^^^^^^^^^^ This is the most common regularization used for optimal transport. It has been proposed in the ML community by Marco Cuturi in his seminal paper [2]_. This regularization has the following expression .. math:: \Omega(\gamma)=\sum_{i,j}\gamma_{i,j}\log(\gamma_{i,j}) The use of the regularization term above in the optimization problem has a very strong impact. First it makes the problem smooth which leads to new optimization procedures such as L-BFGS (see :any:`ot.smooth` ). Next it makes the problem strictly convex meaning that there will be a unique solution. Finally the solution of the resulting optimization problem can be expressed as: .. math:: \gamma_\lambda^*=\text{diag}(u)K\text{diag}(v) where :math:`u` and :math:`v` are vectors and :math:`K=\exp(-M/\lambda)` where the :math:`\exp` is taken component-wise. Other regularization ^^^^^^^^^^^^^^^^^^^^ Stochastic gradient descent ^^^^^^^^^^^^^^^^^^^^^^^^^^^ Wasserstein Barycenters ----------------------- Monge mapping and Domain adaptation with Optimal transport ---------------------------------------- Other applications ------------------ GPU acceleration ---------------- FAQ --- 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** References ---------- .. [1] Bonneel, N., Van De Panne, M., Paris, S., & Heidrich, W. (2011, December). `Displacement nterpolation using Lagrangian mass transport `__. In ACM Transactions on Graphics (TOG) (Vol. 30, No. 6, p. 158). ACM. .. [2] Cuturi, M. (2013). `Sinkhorn distances: Lightspeed computation of optimal transport `__. 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 `__. 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 `__, 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 `__, 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 `__. 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 `__. arXiv preprint arXiv:1510.06567. .. [8] M. Perrot, N. Courty, R. Flamary, A. Habrard (2016), `Mapping estimation for discrete optimal transport `__, Neural Information Processing Systems (NIPS). .. [9] Schmitzer, B. (2016). `Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems `__. arXiv preprint arXiv:1610.06519. .. [10] Chizat, L., Peyré, G., Schmitzer, B., & Vialard, F. X. (2016). `Scaling algorithms for unbalanced transport problems `__. arXiv preprint arXiv:1607.05816. .. [11] Flamary, R., Cuturi, M., Courty, N., & Rakotomamonjy, A. (2016). `Wasserstein Discriminant Analysis `__. arXiv preprint arXiv:1608.08063. .. [12] Gabriel Peyré, Marco Cuturi, and Justin Solomon (2016), `Gromov-Wasserstein averaging of kernel and distance matrices `__ International Conference on Machine Learning (ICML). .. [13] Mémoli, Facundo (2011). `Gromov–Wasserstein distances and the metric approach to object matching `__. Foundations of computational mathematics 11.4 : 417-487. .. [14] Knott, M. and Smith, C. S. (1984).`On the optimal mapping of distributions `__, Journal of Optimization Theory and Applications Vol 43. .. [15] Peyré, G., & Cuturi, M. (2018). `Computational Optimal Transport `__ . .. [16] Agueh, M., & Carlier, G. (2011). `Barycenters in the Wasserstein space `__. SIAM Journal on Mathematical Analysis, 43(2), 904-924. .. [17] Blondel, M., Seguy, V., & Rolet, A. (2018). `Smooth and Sparse Optimal Transport `__. Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics (AISTATS). .. [18] Genevay, A., Cuturi, M., Peyré, G. & Bach, F. (2016) `Stochastic Optimization for Large-scale Optimal Transport `__. Advances in Neural Information Processing Systems (2016). .. [19] Seguy, V., Bhushan Damodaran, B., Flamary, R., Courty, N., Rolet, A.& Blondel, M. `Large-scale Optimal Transport and Mapping Estimation `__. International Conference on Learning Representation (2018) .. [20] Cuturi, M. and Doucet, A. (2014) `Fast Computation of Wasserstein Barycenters `__. International Conference in Machine Learning .. [21] Solomon, J., De Goes, F., Peyré, G., Cuturi, M., Butscher, A., Nguyen, A. & Guibas, L. (2015). `Convolutional wasserstein distances: Efficient optimal transportation on geometric domains `__. ACM Transactions on Graphics (TOG), 34(4), 66. .. [22] J. Altschuler, J.Weed, P. Rigollet, (2017) `Near-linear time 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).