API and modules¶
ot
:
Solvers for the original linear program OT problem |
|
Bregman projections solvers for entropic regularized OT |
|
Smooth and Sparse Optimal Transport solvers (KL an L2 reg.) |
|
Gromov-Wasserstein and Fused-Gromov-Wasserstein solvers |
|
Generic solvers for regularized OT |
|
Domain adaptation with optimal transport |
|
GPU implementation for several OT solvers and utility functions. |
|
Dimension reduction with OT |
|
Various useful functions |
|
Simple example datasets |
|
Functions for plotting OT matrices |
|
Stochastic solvers for regularized OT. |
|
Regularized Unbalanced OT solvers |
|
Partial OT solvers |
|
Sliced Wasserstein Distance. |
Warning
The list of automatically imported sub-modules is as follows:
ot.lp
, ot.bregman
, ot.optim
ot.utils
, ot.datasets
,
ot.gromov
, ot.smooth
ot.stochastic
The following sub-modules are not imported due to additional dependencies:
-
ot.
barycenter
(A, M, reg, weights=None, method='sinkhorn', numItermax=10000, stopThr=0.0001, verbose=False, log=False, **kwargs)[source]¶ Compute the entropic regularized wasserstein barycenter of distributions A
The function solves the following optimization problem:
\[\mathbf{a} = arg\min_\mathbf{a} \sum_i W_{reg}(\mathbf{a},\mathbf{a}_i)\]where :
\(W_{reg}(\cdot,\cdot)\) is the entropic regularized Wasserstein distance (see ot.bregman.sinkhorn)
\(\mathbf{a}_i\) are training distributions in the columns of matrix \(\mathbf{A}\)
reg and \(\mathbf{M}\) are respectively the regularization term and the cost matrix for OT
The algorithm used for solving the problem is the Sinkhorn-Knopp matrix scaling algorithm as proposed in [3]_
- Parameters
A (ndarray, shape (dim, n_hists)) – n_hists training distributions a_i of size dim
M (ndarray, shape (dim, dim)) – loss matrix for OT
reg (float) – Regularization term > 0
method (str (optional)) – method used for the solver either ‘sinkhorn’ or ‘sinkhorn_stabilized’
weights (ndarray, shape (n_hists,)) – Weights of each histogram a_i on the simplex (barycentric coodinates)
numItermax (int, optional) – Max number of iterations
stopThr (float, optional) – Stop threshol on error (>0)
verbose (bool, optional) – Print information along iterations
log (bool, optional) – record log if True
- Returns
a ((dim,) ndarray) – Wasserstein barycenter
log (dict) – log dictionary return only if log==True in parameters
References
- 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.
-
ot.
barycenter_unbalanced
(A, M, reg, reg_m, method='sinkhorn', weights=None, numItermax=1000, stopThr=1e-06, verbose=False, log=False, **kwargs)[source]¶ Compute the entropic unbalanced wasserstein barycenter of A.
The function solves the following optimization problem with a
\[\mathbf{a} = arg\min_\mathbf{a} \sum_i Wu_{reg}(\mathbf{a},\mathbf{a}_i)\]where :
\(Wu_{reg}(\cdot,\cdot)\) is the unbalanced entropic regularized
Wasserstein distance (see ot.unbalanced.sinkhorn_unbalanced) - \(\mathbf{a}_i\) are training distributions in the columns of matrix \(\mathbf{A}\) - reg and \(\mathbf{M}\) are respectively the regularization term and the cost matrix for OT - reg_mis the marginal relaxation hyperparameter The algorithm used for solving the problem is the generalized Sinkhorn-Knopp matrix scaling algorithm as proposed in [10]_
- Parameters
A (np.ndarray (dim, n_hists)) – n_hists training distributions a_i of dimension dim
M (np.ndarray (dim, dim)) – ground metric matrix for OT.
reg (float) – Entropy regularization term > 0
reg_m (float) – Marginal relaxation term > 0
weights (np.ndarray (n_hists,) optional) – Weight of each distribution (barycentric coodinates) If None, uniform weights are used.
numItermax (int, optional) – Max number of iterations
stopThr (float, optional) – Stop threshol on error (> 0)
verbose (bool, optional) – Print information along iterations
log (bool, optional) – record log if True
- Returns
a ((dim,) ndarray) – Unbalanced Wasserstein barycenter
log (dict) – log dictionary return only if log==True in parameters
References
- 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.
- 10
Chizat, L., Peyré, G., Schmitzer, B., & Vialard, F. X. (2016). Scaling algorithms for unbalanced transport problems. arXiv preprin arXiv:1607.05816.
-
ot.
dist
(x1, x2=None, metric='sqeuclidean')[source]¶ Compute distance between samples in x1 and x2 using function scipy.spatial.distance.cdist
- Parameters
x1 (ndarray, shape (n1,d)) – matrix with n1 samples of size d
x2 (array, shape (n2,d), optional) – matrix with n2 samples of size d (if None then x2=x1)
metric (str | callable, optional) – Name of the metric to be computed (full list in the doc of scipy), If a string, the distance function can be ‘braycurtis’, ‘canberra’, ‘chebyshev’, ‘cityblock’, ‘correlation’, ‘cosine’, ‘dice’, ‘euclidean’, ‘hamming’, ‘jaccard’, ‘kulsinski’, ‘mahalanobis’, ‘matching’, ‘minkowski’, ‘rogerstanimoto’, ‘russellrao’, ‘seuclidean’, ‘sokalmichener’, ‘sokalsneath’, ‘sqeuclidean’, ‘wminkowski’, ‘yule’.
- Returns
M – distance matrix computed with given metric
- Return type
np.array (n1,n2)
-
ot.
emd
(a, b, M, numItermax=100000, log=False, center_dual=True)[source]¶ Solves the Earth Movers distance problem and returns the OT matrix
\[ \begin{align}\begin{aligned}\gamma = arg\min_\gamma <\gamma,M>_F\\s.t. \gamma 1 = a\\ \gamma^T 1= b\\ \gamma\geq 0\end{aligned}\end{align} \]where :
M is the metric cost matrix
a and b are the sample weights
Warning
Note that the M matrix needs to be a C-order numpy.array in float64 format.
Uses the algorithm proposed in [1]_
- Parameters
a ((ns,) numpy.ndarray, float64) – Source histogram (uniform weight if empty list)
b ((nt,) numpy.ndarray, float64) – Target histogram (uniform weight if empty list)
M ((ns,nt) numpy.ndarray, float64) – Loss matrix (c-order array with type float64)
numItermax (int, optional (default=100000)) – The maximum number of iterations before stopping the optimization algorithm if it has not converged.
log (bool, optional (default=False)) – If True, returns a dictionary containing the cost and dual variables. Otherwise returns only the optimal transportation matrix.
center_dual (boolean, optional (default=True)) – If True, centers the dual potential using function center_ot_dual.
- Returns
gamma ((ns x nt) numpy.ndarray) – Optimal transportation matrix for the given parameters
log (dict) – If input log is true, a dictionary containing the cost and dual variables and exit status
Examples
Simple example with obvious solution. The function emd accepts lists and perform automatic conversion to numpy arrays
>>> import ot >>> a=[.5,.5] >>> b=[.5,.5] >>> M=[[0.,1.],[1.,0.]] >>> ot.emd(a,b,M) array([[0.5, 0. ], [0. , 0.5]])
References
- 1
Bonneel, N., Van De Panne, M., Paris, S., & Heidrich, W. (2011, December). Displacement interpolation using Lagrangian mass transport. In ACM Transactions on Graphics (TOG) (Vol. 30, No. 6, p. 158). ACM.
See also
ot.bregman.sinkhorn
Entropic regularized OT
ot.optim.cg
General regularized OT
-
ot.
emd2
(a, b, M, processes=36, numItermax=100000, log=False, return_matrix=False, center_dual=True)[source]¶ Solves the Earth Movers distance problem and returns the loss
\[ \begin{align}\begin{aligned}\min_\gamma <\gamma,M>_F\\s.t. \gamma 1 = a\\ \gamma^T 1= b\\ \gamma\geq 0\end{aligned}\end{align} \]where :
M is the metric cost matrix
a and b are the sample weights
Warning
Note that the M matrix needs to be a C-order numpy.array in float64 format.
Uses the algorithm proposed in [1]_
- Parameters
a ((ns,) numpy.ndarray, float64) – Source histogram (uniform weight if empty list)
b ((nt,) numpy.ndarray, float64) – Target histogram (uniform weight if empty list)
M ((ns,nt) numpy.ndarray, float64) – Loss matrix (c-order array with type float64)
processes (int, optional (default=nb cpu)) – Nb of processes used for multiple emd computation (not used on windows)
numItermax (int, optional (default=100000)) – The maximum number of iterations before stopping the optimization algorithm if it has not converged.
log (boolean, optional (default=False)) – If True, returns a dictionary containing the cost and dual variables. Otherwise returns only the optimal transportation cost.
return_matrix (boolean, optional (default=False)) – If True, returns the optimal transportation matrix in the log.
center_dual (boolean, optional (default=True)) – If True, centers the dual potential using function center_ot_dual.
- Returns
gamma ((ns x nt) ndarray) – Optimal transportation matrix for the given parameters
log (dictnp) – If input log is true, a dictionary containing the cost and dual variables and exit status
Examples
Simple example with obvious solution. The function emd accepts lists and perform automatic conversion to numpy arrays
>>> import ot >>> a=[.5,.5] >>> b=[.5,.5] >>> M=[[0.,1.],[1.,0.]] >>> ot.emd2(a,b,M) 0.0
References
- 1
Bonneel, N., Van De Panne, M., Paris, S., & Heidrich, W. (2011, December). Displacement interpolation using Lagrangian mass transport. In ACM Transactions on Graphics (TOG) (Vol. 30, No. 6, p. 158). ACM.
See also
ot.bregman.sinkhorn
Entropic regularized OT
ot.optim.cg
General regularized OT
-
ot.
emd2_1d
(x_a, x_b, a=None, b=None, metric='sqeuclidean', p=1.0, dense=True, log=False)[source]¶ Solves the Earth Movers distance problem between 1d measures and returns the loss
\[ \begin{align}\begin{aligned}\gamma = arg\min_\gamma \sum_i \sum_j \gamma_{ij} d(x_a[i], x_b[j])\\s.t. \gamma 1 = a, \gamma^T 1= b, \gamma\geq 0\end{aligned}\end{align} \]where :
d is the metric
x_a and x_b are the samples
a and b are the sample weights
When ‘minkowski’ is used as a metric, \(d(x, y) = |x - y|^p\).
Uses the algorithm detailed in [1]_
- Parameters
x_a ((ns,) or (ns, 1) ndarray, float64) – Source dirac locations (on the real line)
x_b ((nt,) or (ns, 1) ndarray, float64) – Target dirac locations (on the real line)
a ((ns,) ndarray, float64, optional) – Source histogram (default is uniform weight)
b ((nt,) ndarray, float64, optional) – Target histogram (default is uniform weight)
metric (str, optional (default='sqeuclidean')) – Metric to be used. Only strings listed in
ot.dist()
are accepted. Due to implementation details, this function runs faster when ‘sqeuclidean’, ‘minkowski’, ‘cityblock’, or ‘euclidean’ metrics are used.p (float, optional (default=1.0)) – The p-norm to apply for if metric=’minkowski’
dense (boolean, optional (default=True)) – If True, returns math:gamma as a dense ndarray of shape (ns, nt). Otherwise returns a sparse representation using scipy’s coo_matrix format. Only used if log is set to True. Due to implementation details, this function runs faster when dense is set to False.
log (boolean, optional (default=False)) – If True, returns a dictionary containing the transportation matrix. Otherwise returns only the loss.
- Returns
loss (float) – Cost associated to the optimal transportation
log (dict) – If input log is True, a dictionary containing the Optimal transportation matrix for the given parameters
Examples
Simple example with obvious solution. The function emd2_1d accepts lists and performs automatic conversion to numpy arrays
>>> import ot >>> a=[.5, .5] >>> b=[.5, .5] >>> x_a = [2., 0.] >>> x_b = [0., 3.] >>> ot.emd2_1d(x_a, x_b, a, b) 0.5 >>> ot.emd2_1d(x_a, x_b) 0.5
References
- 1
Peyré, G., & Cuturi, M. (2017). “Computational Optimal Transport”, 2018.
See also
ot.lp.emd2
EMD for multidimensional distributions
ot.lp.emd_1d
EMD for 1d distributions (returns the transportation matrix instead of the cost)
-
ot.
emd_1d
(x_a, x_b, a=None, b=None, metric='sqeuclidean', p=1.0, dense=True, log=False)[source]¶ Solves the Earth Movers distance problem between 1d measures and returns the OT matrix
\[ \begin{align}\begin{aligned}\gamma = arg\min_\gamma \sum_i \sum_j \gamma_{ij} d(x_a[i], x_b[j])\\s.t. \gamma 1 = a, \gamma^T 1= b, \gamma\geq 0\end{aligned}\end{align} \]where :
d is the metric
x_a and x_b are the samples
a and b are the sample weights
When ‘minkowski’ is used as a metric, \(d(x, y) = |x - y|^p\).
Uses the algorithm detailed in [1]_
- Parameters
x_a ((ns,) or (ns, 1) ndarray, float64) – Source dirac locations (on the real line)
x_b ((nt,) or (ns, 1) ndarray, float64) – Target dirac locations (on the real line)
a ((ns,) ndarray, float64, optional) – Source histogram (default is uniform weight)
b ((nt,) ndarray, float64, optional) – Target histogram (default is uniform weight)
metric (str, optional (default='sqeuclidean')) – Metric to be used. Only strings listed in
ot.dist()
are accepted. Due to implementation details, this function runs faster when ‘sqeuclidean’, ‘cityblock’, or ‘euclidean’ metrics are used.p (float, optional (default=1.0)) – The p-norm to apply for if metric=’minkowski’
dense (boolean, optional (default=True)) – If True, returns math:gamma as a dense ndarray of shape (ns, nt). Otherwise returns a sparse representation using scipy’s coo_matrix format. Due to implementation details, this function runs faster when ‘sqeuclidean’, ‘minkowski’, ‘cityblock’, or ‘euclidean’ metrics are used.
log (boolean, optional (default=False)) – If True, returns a dictionary containing the cost. Otherwise returns only the optimal transportation matrix.
- Returns
gamma ((ns, nt) ndarray) – Optimal transportation matrix for the given parameters
log (dict) – If input log is True, a dictionary containing the cost
Examples
Simple example with obvious solution. The function emd_1d accepts lists and performs automatic conversion to numpy arrays
>>> import ot >>> a=[.5, .5] >>> b=[.5, .5] >>> x_a = [2., 0.] >>> x_b = [0., 3.] >>> ot.emd_1d(x_a, x_b, a, b) array([[0. , 0.5], [0.5, 0. ]]) >>> ot.emd_1d(x_a, x_b) array([[0. , 0.5], [0.5, 0. ]])
References
- 1
Peyré, G., & Cuturi, M. (2017). “Computational Optimal Transport”, 2018.
See also
ot.lp.emd
EMD for multidimensional distributions
ot.lp.emd2_1d
EMD for 1d distributions (returns cost instead of the transportation matrix)
-
ot.
sinkhorn
(a, b, M, reg, method='sinkhorn', numItermax=1000, stopThr=1e-09, verbose=False, log=False, **kwargs)[source]¶ Solve the entropic regularization optimal transport problem and return the OT matrix
The function solves the following optimization problem:
\[ \begin{align}\begin{aligned}\gamma = arg\min_\gamma <\gamma,M>_F + reg\cdot\Omega(\gamma)\\s.t. \gamma 1 = a\\ \gamma^T 1= b\\ \gamma\geq 0\end{aligned}\end{align} \]where :
M is the (dim_a, dim_b) metric cost matrix
\(\Omega\) is the entropic regularization term \(\Omega(\gamma)=\sum_{i,j} \gamma_{i,j}\log(\gamma_{i,j})\)
a and b are source and target weights (histograms, both sum to 1)
The algorithm used for solving the problem is the Sinkhorn-Knopp matrix scaling algorithm as proposed in [2]_
- Parameters
a (ndarray, shape (dim_a,)) – samples weights in the source domain
b (ndarray, shape (dim_b,) or ndarray, shape (dim_b, n_hists)) – samples in the target domain, compute sinkhorn with multiple targets and fixed M if b is a matrix (return OT loss + dual variables in log)
M (ndarray, shape (dim_a, dim_b)) – loss matrix
reg (float) – Regularization term >0
method (str) – method used for the solver either ‘sinkhorn’, ‘greenkhorn’, ‘sinkhorn_stabilized’ or ‘sinkhorn_epsilon_scaling’, see those function for specific parameters
numItermax (int, optional) – Max number of iterations
stopThr (float, optional) – Stop threshol on error (>0)
verbose (bool, optional) – Print information along iterations
log (bool, optional) – record log if True
a Sinkhorn solver** (**Choosing) –
default and when using a regularization parameter that is not too small (By) –
default sinkhorn solver should be enough. If you need to use a small (the) –
to get sharper OT matrices (regularization) –
should use the (you) –
:param
ot.bregman.sinkhorn_stabilized
solver that will avoid numerical: :param errors. This last solver can be very slow in practice and might not even: :param converge to a reasonable OT matrix in a finite time. This is why: :paramot.bregman.sinkhorn_epsilon_scaling
that relie on iterating the value: :param of the regularization (and using warm start) sometimes leads to better: :param solutions. Note that the greedy version of the sinkhorn: :paramot.bregman.greenkhorn
can also lead to a speedup and the screening: :param version of the sinkhornot.bregman.screenkhorn
aim a providing a: :param fast approximation of the Sinkhorn problem.:- Returns
gamma (ndarray, shape (dim_a, dim_b)) – Optimal transportation matrix for the given parameters
log (dict) – log dictionary return only if log==True in parameters
Examples
>>> import ot >>> a=[.5, .5] >>> b=[.5, .5] >>> M=[[0., 1.], [1., 0.]] >>> ot.sinkhorn(a, b, M, 1) array([[0.36552929, 0.13447071], [0.13447071, 0.36552929]])
References
- 2
Cuturi, Sinkhorn Distances : Lightspeed Computation of Optimal Transport, Advances in Neural Information Processing Systems (NIPS) 26, 2013
- 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.
See also
ot.lp.emd
Unregularized OT
ot.optim.cg
General regularized OT
ot.bregman.sinkhorn_knopp
Classic Sinkhorn [2]
ot.bregman.sinkhorn_stabilized
Stabilized sinkhorn [9][10]
ot.bregman.sinkhorn_epsilon_scaling
Sinkhorn with epslilon scaling [9][10]
-
ot.
sinkhorn2
(a, b, M, reg, method='sinkhorn', numItermax=1000, stopThr=1e-09, verbose=False, log=False, **kwargs)[source]¶ Solve the entropic regularization optimal transport problem and return the loss
The function solves the following optimization problem:
\[ \begin{align}\begin{aligned}W = \min_\gamma <\gamma,M>_F + reg\cdot\Omega(\gamma)\\s.t. \gamma 1 = a\\ \gamma^T 1= b\\ \gamma\geq 0\end{aligned}\end{align} \]where :
M is the (dim_a, dim_b) metric cost matrix
\(\Omega\) is the entropic regularization term \(\Omega(\gamma)=\sum_{i,j} \gamma_{i,j}\log(\gamma_{i,j})\)
a and b are source and target weights (histograms, both sum to 1)
The algorithm used for solving the problem is the Sinkhorn-Knopp matrix scaling algorithm as proposed in [2]_
- Parameters
a (ndarray, shape (dim_a,)) – samples weights in the source domain
b (ndarray, shape (dim_b,) or ndarray, shape (dim_b, n_hists)) – samples in the target domain, compute sinkhorn with multiple targets and fixed M if b is a matrix (return OT loss + dual variables in log)
M (ndarray, shape (dim_a, dim_b)) – loss matrix
reg (float) – Regularization term >0
method (str) – method used for the solver either ‘sinkhorn’, ‘sinkhorn_stabilized’ or ‘sinkhorn_epsilon_scaling’, see those function for specific parameters
numItermax (int, optional) – Max number of iterations
stopThr (float, optional) – Stop threshol on error (>0)
verbose (bool, optional) – Print information along iterations
log (bool, optional) – record log if True
a Sinkhorn solver** (**Choosing) –
default and when using a regularization parameter that is not too small (By) –
default sinkhorn solver should be enough. If you need to use a small (the) –
to get sharper OT matrices (regularization) –
should use the (you) –
:param
ot.bregman.sinkhorn_stabilized
solver that will avoid numerical: :param errors. This last solver can be very slow in practice and might not even: :param converge to a reasonable OT matrix in a finite time. This is why: :paramot.bregman.sinkhorn_epsilon_scaling
that relie on iterating the value: :param of the regularization (and using warm start) sometimes leads to better: :param solutions. Note that the greedy version of the sinkhorn: :paramot.bregman.greenkhorn
can also lead to a speedup and the screening: :param version of the sinkhornot.bregman.screenkhorn
aim a providing a: :param fast approximation of the Sinkhorn problem.:- Returns
W ((n_hists) ndarray or float) – Optimal transportation loss for the given parameters
log (dict) – log dictionary return only if log==True in parameters
Examples
>>> import ot >>> a=[.5, .5] >>> b=[.5, .5] >>> M=[[0., 1.], [1., 0.]] >>> ot.sinkhorn2(a, b, M, 1) array([0.26894142])
References
- 2
Cuturi, Sinkhorn Distances : Lightspeed Computation of Optimal Transport, Advances in Neural Information Processing Systems (NIPS) 26, 2013
- 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.
[21] Altschuler J., Weed J., Rigollet P. : Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration, Advances in Neural Information Processing Systems (NIPS) 31, 2017
See also
ot.lp.emd
Unregularized OT
ot.optim.cg
General regularized OT
ot.bregman.sinkhorn_knopp
Classic Sinkhorn [2]
ot.bregman.greenkhorn
Greenkhorn [21]
ot.bregman.sinkhorn_stabilized
Stabilized sinkhorn [9][10]
ot.bregman.sinkhorn_epsilon_scaling
Sinkhorn with epslilon scaling [9][10]
-
ot.
sinkhorn_lpl1_mm
(a, labels_a, b, M, reg, eta=0.1, numItermax=10, numInnerItermax=200, stopInnerThr=1e-09, verbose=False, log=False)[source]¶ Solve the entropic regularization optimal transport problem with nonconvex group lasso regularization
The function solves the following optimization problem:
\[ \begin{align}\begin{aligned}\gamma = arg\min_\gamma <\gamma,M>_F + reg\cdot\Omega_e(\gamma) + \eta \Omega_g(\gamma)\\s.t. \gamma 1 = a\\ \gamma^T 1= b\\ \gamma\geq 0\end{aligned}\end{align} \]where :
M is the (ns,nt) metric cost matrix
\(\Omega_e\) is the entropic regularization term \(\Omega_e (\gamma)=\sum_{i,j} \gamma_{i,j}\log(\gamma_{i,j})\)
\(\Omega_g\) is the group lasso regularization term \(\Omega_g(\gamma)=\sum_{i,c} \|\gamma_{i,\mathcal{I}_c}\|^{1/2}_1\) where \(\mathcal{I}_c\) are the index of samples from class c in the source domain.
a and b are source and target weights (sum to 1)
The algorithm used for solving the problem is the generalized conditional gradient as proposed in 5 7
- Parameters
a (np.ndarray (ns,)) – samples weights in the source domain
labels_a (np.ndarray (ns,)) – labels of samples in the source domain
b (np.ndarray (nt,)) – samples weights in the target domain
M (np.ndarray (ns,nt)) – loss matrix
reg (float) – Regularization term for entropic regularization >0
eta (float, optional) – Regularization term for group lasso regularization >0
numItermax (int, optional) – Max number of iterations
numInnerItermax (int, optional) – Max number of iterations (inner sinkhorn solver)
stopInnerThr (float, optional) – Stop threshold on error (inner sinkhorn solver) (>0)
verbose (bool, optional) – Print information along iterations
log (bool, optional) – record log if True
- Returns
gamma ((ns x nt) ndarray) – Optimal transportation matrix for the given parameters
log (dict) – log dictionary return only if log==True in parameters
References
- 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
- 7
Rakotomamonjy, A., Flamary, R., & Courty, N. (2015). Generalized conditional gradient: analysis of convergence and applications. arXiv preprint arXiv:1510.06567.
See also
ot.lp.emd
Unregularized OT
ot.bregman.sinkhorn
Entropic regularized OT
ot.optim.cg
General regularized OT
-
ot.
sinkhorn_unbalanced
(a, b, M, reg, reg_m, method='sinkhorn', numItermax=1000, stopThr=1e-06, verbose=False, log=False, **kwargs)[source]¶ Solve the unbalanced entropic regularization optimal transport problem and return the OT plan
The function solves the following optimization problem:
\[ \begin{align}\begin{aligned}W = \min_\gamma <\gamma,M>_F + reg\cdot\Omega(\gamma) + reg_m KL(\gamma 1, a) + reg_m KL(\gamma^T 1, b)\\s.t. \gamma\geq 0\end{aligned}\end{align} \]where :
M is the (dim_a, dim_b) metric cost matrix
- \(\Omega\) is the entropic regularization
term \(\Omega(\gamma)=\sum_{i,j} \gamma_{i,j}\log(\gamma_{i,j})\)
a and b are source and target unbalanced distributions
KL is the Kullback-Leibler divergence
- The algorithm used for solving the problem is the generalized
Sinkhorn-Knopp matrix scaling algorithm as proposed in [10, 23]_
- Parameters
a (np.ndarray (dim_a,)) – Unnormalized histogram of dimension dim_a
b (np.ndarray (dim_b,) or np.ndarray (dim_b, n_hists)) – One or multiple unnormalized histograms of dimension dim_b If many, compute all the OT distances (a, b_i)
M (np.ndarray (dim_a, dim_b)) – loss matrix
reg (float) – Entropy regularization term > 0
reg_m (float) – Marginal relaxation term > 0
method (str) – method used for the solver either ‘sinkhorn’, ‘sinkhorn_stabilized’ or ‘sinkhorn_reg_scaling’, see those function for specific parameters
numItermax (int, optional) – Max number of iterations
stopThr (float, optional) – Stop threshol on error (>0)
verbose (bool, optional) – Print information along iterations
log (bool, optional) – record log if True
- Returns
if n_hists == 1 –
- gamma(dim_a x dim_b) ndarray
Optimal transportation matrix for the given parameters
- logdict
log dictionary returned only if log is True
else –
- ot_distance(n_hists,) ndarray
the OT distance between a and each of the histograms b_i
- logdict
log dictionary returned only if log is True
Examples
>>> import ot >>> a=[.5, .5] >>> b=[.5, .5] >>> M=[[0., 1.], [1., 0.]] >>> ot.sinkhorn_unbalanced(a, b, M, 1, 1) array([[0.51122823, 0.18807035], [0.18807035, 0.51122823]])
References
- 2
M. Cuturi, Sinkhorn Distances : Lightspeed Computation of Optimal Transport, Advances in Neural Information Processing Systems (NIPS) 26, 2013
- 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.
- 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
See also
ot.unbalanced.sinkhorn_knopp_unbalanced
Unbalanced Classic Sinkhorn [10]
ot.unbalanced.sinkhorn_stabilized_unbalanced
Unbalanced Stabilized sinkhorn [9][10]
ot.unbalanced.sinkhorn_reg_scaling_unbalanced
Unbalanced Sinkhorn with epslilon scaling [9][10]
-
ot.
sinkhorn_unbalanced2
(a, b, M, reg, reg_m, method='sinkhorn', numItermax=1000, stopThr=1e-06, verbose=False, log=False, **kwargs)[source]¶ Solve the entropic regularization unbalanced optimal transport problem and return the loss
The function solves the following optimization problem:
\[ \begin{align}\begin{aligned}W = \min_\gamma <\gamma,M>_F + reg\cdot\Omega(\gamma) + reg_m KL(\gamma 1, a) + reg_m KL(\gamma^T 1, b)\\s.t. \gamma\geq 0\end{aligned}\end{align} \]where :
M is the (dim_a, dim_b) metric cost matrix
- \(\Omega\) is the entropic regularization term
\(\Omega(\gamma)=\sum_{i,j} \gamma_{i,j}\log(\gamma_{i,j})\)
a and b are source and target unbalanced distributions
KL is the Kullback-Leibler divergence
The algorithm used for solving the problem is the generalized Sinkhorn-Knopp matrix scaling algorithm as proposed in [10, 23]_
- Parameters
a (np.ndarray (dim_a,)) – Unnormalized histogram of dimension dim_a
b (np.ndarray (dim_b,) or np.ndarray (dim_b, n_hists)) – One or multiple unnormalized histograms of dimension dim_b If many, compute all the OT distances (a, b_i)
M (np.ndarray (dim_a, dim_b)) – loss matrix
reg (float) – Entropy regularization term > 0
reg_m (float) – Marginal relaxation term > 0
method (str) – method used for the solver either ‘sinkhorn’, ‘sinkhorn_stabilized’ or ‘sinkhorn_reg_scaling’, see those function for specific parameters
numItermax (int, optional) – Max number of iterations
stopThr (float, optional) – Stop threshol on error (>0)
verbose (bool, optional) – Print information along iterations
log (bool, optional) – record log if True
- Returns
ot_distance ((n_hists,) ndarray) – the OT distance between a and each of the histograms b_i
log (dict) – log dictionary returned only if log is True
Examples
>>> import ot >>> a=[.5, .10] >>> b=[.5, .5] >>> M=[[0., 1.],[1., 0.]] >>> ot.unbalanced.sinkhorn_unbalanced2(a, b, M, 1., 1.) array([0.31912866])
References
- 2
M. Cuturi, Sinkhorn Distances : Lightspeed Computation of Optimal Transport, Advances in Neural Information Processing Systems (NIPS) 26, 2013
- 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.
- 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
See also
ot.unbalanced.sinkhorn_knopp
Unbalanced Classic Sinkhorn [10]
ot.unbalanced.sinkhorn_stabilized
Unbalanced Stabilized sinkhorn [9][10]
ot.unbalanced.sinkhorn_reg_scaling
Unbalanced Sinkhorn with epslilon scaling [9][10]
-
ot.
sliced_wasserstein_distance
(X_s, X_t, a=None, b=None, n_projections=50, seed=None, log=False)[source]¶ Computes a Monte-Carlo approximation of the 2-Sliced Wasserstein distance
\[\mathcal{SWD}_2(\mu, \nu) = \underset{\theta \sim \mathcal{U}(\mathbb{S}^{d-1})}{\mathbb{E}}[\mathcal{W}_2^2(\theta_\# \mu, \theta_\# \nu)]^{\frac{1}{2}}\]where :
\(\theta_\# \mu\) stands for the pushforwars of the projection \(\mathbb{R}^d \ni X \mapsto \langle \theta, X \rangle\)
- Parameters
X_s (ndarray, shape (n_samples_a, dim)) – samples in the source domain
X_t (ndarray, shape (n_samples_b, dim)) – samples in the target domain
a (ndarray, shape (n_samples_a,), optional) – samples weights in the source domain
b (ndarray, shape (n_samples_b,), optional) – samples weights in the target domain
n_projections (int, optional) – Number of projections used for the Monte-Carlo approximation
seed (int or RandomState or None, optional) – Seed used for numpy random number generator
log (bool, optional) – if True, sliced_wasserstein_distance returns the projections used and their associated EMD.
- Returns
cost (float) – Sliced Wasserstein Cost
log (dict, optional) – log dictionary return only if log==True in parameters
Examples
>>> n_samples_a = 20 >>> reg = 0.1 >>> X = np.random.normal(0., 1., (n_samples_a, 5)) >>> sliced_wasserstein_distance(X, X, seed=0) 0.0
References
- 31
Bonneel, Nicolas, et al. “Sliced and radon wasserstein barycenters of measures.” Journal of Mathematical Imaging and Vision 51.1 (2015): 22-45
-
ot.
unif
(n)[source]¶ return a uniform histogram of length n (simplex)
- Parameters
n (int) – number of bins in the histogram
- Returns
h – histogram of length n such that h_i=1/n for all i
- Return type
np.array (n,)
-
ot.
wasserstein_1d
(x_a, x_b, a=None, b=None, p=1.0)[source]¶ Solves the p-Wasserstein distance problem between 1d measures and returns the distance
\[ \begin{align}\begin{aligned}\min_\gamma \left( \sum_i \sum_j \gamma_{ij} \|x_a[i] - x_b[j]\|^p \right)^{1/p}\\s.t. \gamma 1 = a, \gamma^T 1= b, \gamma\geq 0\end{aligned}\end{align} \]where :
x_a and x_b are the samples
a and b are the sample weights
Uses the algorithm detailed in [1]_
- Parameters
x_a ((ns,) or (ns, 1) ndarray, float64) – Source dirac locations (on the real line)
x_b ((nt,) or (ns, 1) ndarray, float64) – Target dirac locations (on the real line)
a ((ns,) ndarray, float64, optional) – Source histogram (default is uniform weight)
b ((nt,) ndarray, float64, optional) – Target histogram (default is uniform weight)
p (float, optional (default=1.0)) – The order of the p-Wasserstein distance to be computed
- Returns
dist – p-Wasserstein distance
- Return type
Examples
Simple example with obvious solution. The function wasserstein_1d accepts lists and performs automatic conversion to numpy arrays
>>> import ot >>> a=[.5, .5] >>> b=[.5, .5] >>> x_a = [2., 0.] >>> x_b = [0., 3.] >>> ot.wasserstein_1d(x_a, x_b, a, b) 0.5 >>> ot.wasserstein_1d(x_a, x_b) 0.5
References
- 1
Peyré, G., & Cuturi, M. (2017). “Computational Optimal Transport”, 2018.
See also
ot.lp.emd_1d
EMD for 1d distributions