ot.bregman

与熵正则化最优传输相关的Bregman投影求解器

ot.bregman.barycenter(A, M, reg, weights=None, method='sinkhorn', numItermax=10000, stopThr=0.0001, verbose=False, log=False, warn=True, **kwargs)

计算分布的熵正则化 Wasserstein 重心 \(\mathbf{A}\)

该函数解决以下优化问题：

\[\mathbf{a} = \mathop{\arg \min}_\mathbf{a} \quad \sum_i W_{reg}(\mathbf{a},\mathbf{a}_i)\]

其中 :

• \(W_{reg}(\cdot,\cdot)\) 是熵正则化的沃瑟斯坦距离（见 ot.bregman.sinkhorn()），如果 method 是 sinkhorn 或 sinkhorn_stabilized 或 sinkhorn_log。

• \(\mathbf{a}_i\) 是矩阵中的训练分布 \(\mathbf{A}\) 的列

• reg 和 \(\mathbf{M}\) 分别是正则化项和 OT 的成本矩阵

用于解决该问题的算法是Sinkhorn-Knopp矩阵缩放算法，如[3]中所提议。

Parameters:

• A (类似数组, 形状 (维度, n_hists)) – n_hists 训练分布 \(\mathbf{a}_i\) 的大小为 dim

• M (类数组, 形状 (维度, 维度)) – OT 的损失矩阵

• reg (float) – 正则化项 > 0

• 方法 (str (可选)) – 求解器使用的方法，可以是‘sinkhorn’、‘sinkhorn_stabilized’或‘sinkhorn_log’

• weights (类数组, 形状 (n_hists,)) – 每个直方图 \(\mathbf{a}_i\) 在单纯形（重心坐标）的权重

• numItermax (int, 可选) – 最大迭代次数

• stopThr (float, 可选) – 错误的停止阈值 (>0)

• verbose (bool, 可选) – 在迭代过程中打印信息

• log (bool, 可选) – 如果为真，则记录日志

• warn (bool, 可选) – 如果为True，当算法不收敛时会发出警告。

Returns:

• a ((dim,) 类数组) – Wasserstein 重心

• log (字典) – 仅在参数中log==True时返回日志字典

参考文献

[3]

Benamou, J. D., Carlier, G., Cuturi, M., Nenna, L., & Peyré, G. (2015). 用于正则化运输问题的迭代Bregman投影。 SIAM科学计算期刊, 37(2), A1111-A1138.

ot.bregman.barycenter_debiased(A, M, reg, weights=None, method='sinkhorn', numItermax=10000, stopThr=0.0001, verbose=False, log=False, warn=True, **kwargs)

计算分布 A 的去偏 Sinkhorn 重心

该函数解决以下优化问题：

\[\mathbf{a} = \mathop{\arg \min}_\mathbf{a} \quad \sum_i S_{reg}(\mathbf{a},\mathbf{a}_i)\]

其中 :

• \(S_{reg}(\cdot,\cdot)\) 是去偏差的 Sinkhorn 发散 (见 ot.bregman.empirical_sinkhorn_divergence())

• \(\mathbf{a}_i\) 是矩阵中的训练分布 \(\mathbf{A}\) 的列

• reg 和 \(\mathbf{M}\) 分别是正则化项和 OT 的成本矩阵

用于解决该问题的算法是去偏差Sinkhorn算法，如[37]中所提到的

Parameters:

• A (类似数组, 形状 (维度, n_hists)) – n_hists 训练分布 \(\mathbf{a}_i\) 的大小为 dim

• M (类数组, 形状 (维度, 维度)) – OT 的损失矩阵

• reg (float) – 正则化项 > 0

• 方法 (str (可选)) – 求解器使用的方法，可以是‘sinkhorn’或‘sinkhorn_log’

• weights (类数组, 形状 (n_hists,)) – 每个直方图 \(\mathbf{a}_i\) 在单纯形（重心坐标）的权重

• numItermax (int, 可选) – 最大迭代次数

• stopThr (float, 可选) – 错误的停止阈值 (>0)

• verbose (bool, 可选) – 在迭代过程中打印信息

• log (bool, 可选) – 如果为真，则记录日志

• warn (bool, 可选) – 如果为True，当算法不收敛时会发出警告。

Returns:

• a ((dim,) 类数组) – Wasserstein 重心

• log (字典) – 仅在参数中log==True时返回日志字典

参考文献

[37]

Janati, H., Cuturi, M., Gramfort, A. 第37届国际机器学习会议录, PMLR 119:4692-4701, 2020

ot.bregman.barycenter_sinkhorn(A, M, reg, weights=None, numItermax=1000, stopThr=0.0001, verbose=False, log=False, warn=True)

计算分布的熵正则化 Wasserstein 重心 \(\mathbf{A}\)

该函数解决以下优化问题：

\[\mathbf{a} = \mathop{\arg \min}_\mathbf{a} \quad \sum_i W_{reg}(\mathbf{a},\mathbf{a}_i)\]

其中 :

• \(W_{reg}(\cdot,\cdot)\) 是熵正则化的Wasserstein距离（见 ot.bregman.sinkhorn()）

• \(\mathbf{a}_i\) 是矩阵中的训练分布 \(\mathbf{A}\) 的列

• reg 和 \(\mathbf{M}\) 分别是正则化项和 OT 的成本矩阵

解决该问题的算法是Sinkhorn-Knopp矩阵缩放算法，如[3]中所提出的。

Parameters:

• A (类似数组, 形状 (维度, n_hists)) – n_hists 训练分布 \(\mathbf{a}_i\) 的大小为 dim

• M (类数组, 形状 (维度, 维度)) – OT 的损失矩阵

• reg (float) – 正则化项 > 0

• weights (类数组, 形状 (n_hists,)) – 每个直方图 \(\mathbf{a}_i\) 在单纯形（重心坐标）的权重

• numItermax (int, 可选) – 最大迭代次数

• stopThr (float, 可选) – 错误的停止阈值 (>0)

• verbose (bool, 可选) – 在迭代过程中打印信息

• log (bool, 可选) – 如果为真，则记录日志

• warn (bool, 可选) – 如果为True，当算法不收敛时会发出警告。

Returns:

• a ((dim,) 类数组) – Wasserstein 重心

• log (字典) – 仅在参数中log==True时返回日志字典

参考文献

[3]

Benamou, J. D., Carlier, G., Cuturi, M., Nenna, L., & Peyré, G. (2015).

用于正则化运输问题的迭代Bregman投影。 SIAM科学计算杂志，37(2)，A1111-A1138。

ot.bregman.barycenter_stabilized(A, M, reg, tau=10000000000.0, weights=None, numItermax=1000, stopThr=0.0001, verbose=False, log=False, warn=True)

计算分布 \(\mathbf{A}\) 的熵正则化瓦瑟斯坦重心，带有稳定性。

该函数解决以下优化问题：

\[\mathbf{a} = \mathop{\arg \min}_\mathbf{a} \quad \sum_i W_{reg}(\mathbf{a},\mathbf{a}_i)\]

其中 :

• \(W_{reg}(\cdot,\cdot)\) 是熵正则化的沃瑟斯坦距离（参见 ot.bregman.sinkhorn()）

• \(\mathbf{a}_i\) 是矩阵中的训练分布 \(\mathbf{A}\) 的列

• reg 和 \(\mathbf{M}\) 分别是正则化项和 OT 的成本矩阵

用于解决该问题的算法是Sinkhorn-Knopp矩阵缩放算法，如[3]中所提议。

Parameters:

• A (类似数组, 形状 (维度, n_hists)) – n_hists 训练分布 \(\mathbf{a}_i\) 的大小为 dim

• M (类数组, 形状 (维度, 维度)) – OT 的损失矩阵

• reg (float) – 正则化项 > 0

• tau (float) – \(\mathbf{u}\) 或 \(\mathbf{v}\) 的最大值的阈值，用于对数缩放

• weights (类数组, 形状 (n_hists,)) – 每个直方图 \(\mathbf{a}_i\) 在单纯形（重心坐标）的权重

• numItermax (int, 可选) – 最大迭代次数

• stopThr (float, 可选) – 错误的停止阈值 (>0)

• verbose (bool, 可选) – 在迭代过程中打印信息

• log (bool, 可选) – 如果为真，则记录日志

• warn (bool, 可选) – 如果为True，当算法不收敛时会发出警告。

Returns:

• a ((dim,) 类数组) – Wasserstein 重心

• log (字典) – 仅在参数中log==True时返回日志字典

参考文献

[3]

Benamou, J. D., Carlier, G., Cuturi, M., Nenna, L., & Peyré, G. (2015). 用于正则化运输问题的迭代Bregman投影。 SIAM科学计算期刊, 37(2), A1111-A1138.

ot.bregman.convolutional_barycenter2d(A, reg, weights=None, method='sinkhorn', numItermax=10000, stopThr=0.0001, verbose=False, log=False, warn=True, **kwargs)

计算分布的熵正则化wasserstein重心 \(\mathbf{A}\)，其中 \(\mathbf{A}\) 是一组二维图像。

该函数解决以下优化问题：

\[\mathbf{a} = \mathop{\arg \min}_\mathbf{a} \quad \sum_i W_{reg}(\mathbf{a},\mathbf{a}_i)\]

其中 :

• \(W_{reg}(\cdot,\cdot)\) 是熵正则化的沃瑟斯坦距离（参见 ot.bregman.sinkhorn()）

• \(\mathbf{a}_i\) 是矩阵 \(\mathbf{A}\) 在最后两个维度中的训练分布（二维图像）

• reg 是正则化强度的标量值

用于解决该问题的算法是Sinkhorn-Knopp矩阵缩放算法，如[21]中提出的

Parameters:

• A (类数组, 形状 (n_hists, 宽度, 高度)) – n 个分布 (2D 图像)，大小为 宽度 x 高度

• reg (float) – 正则化项 >0

• weights (array-like, shape (n_hists,)) – 每个图像在单纯形上的权重（重心坐标）

• method (string, optional) – 求解器使用的方法，'sinkhorn' 或 'sinkhorn_log'

• numItermax (int, 可选) – 最大迭代次数

• stopThr (float, 可选) – 错误的停止阈值 (> 0)

• stabThr (float, 可选) – 稳定阈值以避免数值精度问题

• verbose (bool, 可选) – 在迭代过程中打印信息

• log (bool, 可选) – 如果为真，则记录日志

• warn (bool, 可选) – 如果为True，当算法不收敛时会发出警告。

Returns:

• a (类数组，形状 (宽度, 高度)) – 2D Wasserstein barycenter

• log (字典) – 只有在参数中 log==True 时返回日志字典

参考文献

[21]

Solomon, J., De Goes, F., Peyré, G., Cuturi, M., Butscher, A., Nguyen, A. & Guibas, L. (2015). 卷积瓦瑟斯坦距离： 在几何域上的有效最优运输。ACM图形学交易 (TOG), 34(4), 66

[37]

Janati, H., Cuturi, M., Gramfort, A. 第37届国际机器学习会议论文集，PMLR 119:4692-4701, 2020

ot.bregman.convolutional_barycenter2d_debiased(A, reg, weights=None, method='sinkhorn', numItermax=10000, stopThr=0.001, verbose=False, log=False, warn=True, **kwargs)

计算分布的去偏Sinkhorn重心 \(\mathbf{A}\)， 其中 \(\mathbf{A}\) 是一组2D图像。

该函数解决以下优化问题：

\[\mathbf{a} = \mathop{\arg \min}_\mathbf{a} \quad \sum_i S_{reg}(\mathbf{a},\mathbf{a}_i)\]

其中 :

• \(S_{reg}(\cdot,\cdot)\) 是去偏的熵正则化Wasserstein距离（见 ot.bregman.barycenter_debiased()）

• \(\mathbf{a}_i\) 是矩阵 \(\mathbf{A}\) 的前两维的训练分布（2D 图像）

• reg 是正则化强度的标量值

用于解决该问题的算法是去偏差的Sinkhorn缩放算法，如[37]中所提到的

Parameters:

• A (类数组, 形状 (n_hists, 宽度, 高度)) – n 个分布 (2D 图像)，大小为 宽度 x 高度

• reg (float) – 正则化项 >0

• weights (array-like, shape (n_hists,)) – 每个图像在单纯形上的权重（重心坐标）

• method (string, optional) – 求解器使用的方法，'sinkhorn' 或 'sinkhorn_log'

• numItermax (int, 可选) – 最大迭代次数

• stopThr (float, 可选) – 错误的停止阈值 (> 0)

• stabThr (float, 可选) – 稳定阈值以避免数值精度问题

• verbose (bool, 可选) – 在迭代过程中打印信息

• log (bool, 可选) – 如果为真，则记录日志

• warn (bool, 可选) – 如果为True，当算法不收敛时会发出警告。

Returns:

• a (类数组，形状 (宽度, 高度)) – 2D Wasserstein barycenter

• log (字典) – 只有在参数中 log==True 时返回日志字典

参考文献

[37]

Janati, H., Cuturi, M., Gramfort, A. 第37届国际机器学习会议录, PMLR 119:4692-4701, 2020

ot.bregman.empirical_sinkhorn(X_s, X_t, reg, a=None, b=None, metric='sqeuclidean', numIterMax=10000, stopThr=1e-09, isLazy=False, batchSize=100, verbose=False, log=False, warn=True, warmstart=None, **kwargs)

解决熵正则化的最优传输问题，并从经验数据中返回OT矩阵

该函数解决以下优化问题：

\[ \begin{align}\begin{aligned}\gamma = \mathop{\arg \min}_\gamma \quad \langle \gamma, \mathbf{M} \rangle_F + \mathrm{reg} \cdot\Omega(\gamma)\\\text{约束条件：} \ \gamma \mathbf{1} &= \mathbf{a}\\ \gamma^T \mathbf{1} &= \mathbf{b}\\ \gamma &\geq 0\end{aligned}\end{align} \]

其中 :

• \(\mathbf{M}\) 是（n_samples_a, n_samples_b）度量成本矩阵

• \(\Omega\) 是熵正则化项 \(\Omega(\gamma)=\sum_{i,j} \gamma_{i,j}\log(\gamma_{i,j})\)

• \(\mathbf{a}\) 和 \(\mathbf{b}\) 是源权重和目标权重（总和为1）

Parameters:

• X_s (类数组, 形状 (n_samples_a, 维度)) – 源域中的样本

• X_t (类似数组, 形状 (n_samples_b, 维度)) – 目标域中的样本

• reg (float) – 正则化项 >0

• a (类数组, 形状 (n_samples_a,)) – 源域中的样本权重

• b (数组类型, 形状 (n_samples_b,)) – 目标领域中的样本权重

• numItermax (int, 可选) – 最大迭代次数

• stopThr (float, 可选) – 错误的停止阈值 (>0)

• isLazy (boolean, optional) – 如果为 True，则仅按块计算成本矩阵，并仅返回对偶势（以节省内存）。如果为 False，则计算完整的成本矩阵并返回 sinkhorn 函数的输出。

• batchSize (int 或 tuple 的 2 int, 可选) – 用于计算 sinkhorn 更新而不带内存开销的批次大小。当提供一个元组时，它设置左/右批次的大小。

• verbose (bool, 可选) – 在迭代过程中打印信息

• log (bool, 可选) – 如果为真，则记录日志

• warn (bool, 可选) – 如果为True，当算法不收敛时会发出警告。

• warmstart (元组 的 数组, 形状 (dim_a, dim_b), 可选) – 对偶潜力的初始化。如果提供，应该给出对偶潜力 （即 u,v Sinkhorn 缩放向量的对数）

Returns:

• gamma (类数组，形状 (n_samples_a, n_samples_b)) – 给定参数的正则化最优运输矩阵

• log (字典) – 仅在参数中 log==True 时返回日志字典

示例

>>> import numpy as np
>>> n_samples_a = 2
>>> n_samples_b = 2
>>> reg = 0.1
>>> X_s = np.reshape(np.arange(n_samples_a, dtype=np.float64), (n_samples_a, 1))
>>> X_t = np.reshape(np.arange(0, n_samples_b, dtype=np.float64), (n_samples_b, 1))
>>> empirical_sinkhorn(X_s, X_t, reg=reg, verbose=False)  
array([[4.99977301e-01,  2.26989344e-05],
       [2.26989344e-05,  4.99977301e-01]])

参考文献

[2]

M. Cuturi, Sinkhorn距离：最优运输的快速计算，神经信息处理系统进展（NIPS）26，2013

[9]

Schmitzer, B. (2016). 稳定稀疏缩放算法用于熵正则化运输问题。arXiv 预印本 arXiv:1610.06519.

[10]

Chizat, L., Peyré, G., Schmitzer, B., & Vialard, F. X. (2016). 不平衡运输问题的规模化算法。arXiv 预印本 arXiv:1607.05816.

ot.bregman.empirical_sinkhorn2(X_s, X_t, reg, a=None, b=None, metric='sqeuclidean', numIterMax=10000, stopThr=1e-09, isLazy=False, batchSize=100, verbose=False, log=False, warn=True, warmstart=None, **kwargs)

解决来自经验数据的熵正则化最优运输问题并返回OT损失

该函数解决以下优化问题：

\[ \begin{align}\begin{aligned}W = \min_\gamma \quad \langle \gamma, \mathbf{M} \rangle_F + \mathrm{reg} \cdot\Omega(\gamma)\\s.t. \ \gamma \mathbf{1} &= \mathbf{a}\\ \gamma^T \mathbf{1} &= \mathbf{b}\\ \gamma &\geq 0\end{aligned}\end{align} \]

其中 :

• \(\mathbf{M}\) 是（n_samples_a, n_samples_b）度量成本矩阵

• \(\Omega\) 是熵正则化项 \(\Omega(\gamma)=\sum_{i,j} \gamma_{i,j}\log(\gamma_{i,j})\)

• \(\mathbf{a}\) 和 \(\mathbf{b}\) 是源权重和目标权重（总和为1）

并返回 \(\langle \gamma^*, \mathbf{M} \rangle_F\) （不包括熵贡献）。

Parameters:

• X_s (类数组, 形状 (n_samples_a, 维度)) – 源域中的样本

• X_t (类似数组, 形状 (n_samples_b, 维度)) – 目标域中的样本

• reg (float) – 正则化项 >0

• a (类数组, 形状 (n_samples_a,)) – 源域中的样本权重

• b (数组类型, 形状 (n_samples_b,)) – 目标领域中的样本权重

• numItermax (int, 可选) – 最大迭代次数

• stopThr (float, 可选) – 错误的停止阈值 (>0)

• isLazy (boolean, optional) - 如果为 True，则仅按块计算成本矩阵并仅返回对偶势（以节省内存）。如果为 False，计算完整的成本矩阵并返回 sinkhorn 函数的输出。

• batchSize (int 或 tuple 的 2 int, 可选) – 用于计算 sinkhorn 更新而不带内存开销的批次大小。当提供一个元组时，它设置左/右批次的大小。

• verbose (bool, 可选) – 在迭代过程中打印信息

• log (bool, 可选) – 如果为真，则记录日志

• warn (bool, 可选) – 如果为True，当算法不收敛时会发出警告。

• warmstart (元组 的 数组, 形状 (dim_a, dim_b), 可选) – 对偶潜力的初始化。如果提供，应该给出对偶潜力 （即 u,v Sinkhorn 缩放向量的对数）

Returns:

• W ((n_hists) 类数组或浮点数) – 给定参数的最优运输损失

• log (字典) – 只有在参数中log==True时才返回日志字典

示例

>>> import numpy as np
>>> n_samples_a = 2
>>> n_samples_b = 2
>>> reg = 0.1
>>> X_s = np.reshape(np.arange(n_samples_a, dtype=np.float64), (n_samples_a, 1))
>>> X_t = np.reshape(np.arange(0, n_samples_b, dtype=np.float64), (n_samples_b, 1))
>>> b = np.full((n_samples_b, 3), 1/n_samples_b)
>>> empirical_sinkhorn2(X_s, X_t, b=b, reg=reg, verbose=False)
array([4.53978687e-05, 4.53978687e-05, 4.53978687e-05])

参考文献

[2]

M. Cuturi, Sinkhorn 距离：优化运输的快速计算，神经信息处理系统进展 (NIPS) 26, 2013

[9]

Schmitzer, B. (2016). 稳定稀疏缩放 算法用于熵正则化传输问题。 arXiv 预印本 arXiv:1610.06519.

[10]

Chizat, L., Peyré, G., Schmitzer, B., & Vialard, F. X. (2016). 缩放算法用于不平衡交通问题。 arXiv 预印本 arXiv:1607.05816.

ot.bregman.empirical_sinkhorn2_geomloss(X_s, X_t, reg, a=None, b=None, metric='sqeuclidean', scaling=0.95, verbose=False, debias=False, log=False, backend='auto')

使用geomloss解决熵正则化最优传输问题

该函数解决以下优化问题：

\[ \begin{align}\begin{aligned}\gamma = \arg\min_\gamma <\gamma,C>_F + \text{reg}\cdot\Omega(\gamma)\\\text{s.t.} \gamma 1 = a\\ \gamma^T 1= b\\ \gamma\geq 0\end{aligned}\end{align} \]

其中 :

• \(C\) 是成本矩阵，其中 \(C_{i,j}=d(x_i^s,x_j^t)\)，而 \(d\) 是一个度量。

• \(\Omega\) 是熵正则化项 \(\Omega(\gamma)=\sum_{i,j}\gamma_{i,j}\log(\gamma_{i,j})-\gamma_{i,j}+1\)

• \(a\) 和 \(b\) 是源权重和目标权重（总和为1）

用于解决该问题的算法是Sinkhorn-Knopp矩阵缩放算法，如所提及，并在对数空间中计算以实现更好的稳定性和ε缩放。该解决方案以懒惰的方式计算，使用Geomloss [60]和KeOps库 [61]。

Parameters:

• X_s (类数组, 形状 (n_samples_a, 维度)) – 源域中的样本

• X_t (类似数组, 形状 (n_samples_b, 维度)) – 目标域中的样本

• reg (float) – 正则化项 >0

• a (类似数组, 形状 (n_samples_a,), 默认为None) – 源领域中的样本权重

• b (数组类似, 形状 (n_samples_b,), 默认=None) – 目标领域中的样本权重

• 度量 (str, 默认='sqeuclidean') - 用于成本矩阵计算的度量，唯一接受的值是 ‘sqeuclidean’ 和 ‘euclidean’。

• 缩放 (浮点数, 默认=0.95) – 用于epsilon缩放的缩放参数。接近一的值促进精度，而接近零的值促进速度。

• verbose (bool, default=False) – 打印信息

• debias (bool, default=False) – 使用去偏的Sinkhorn算法版本 [12]_。

• log (bool, default=False) – 返回包含所有计算对象的日志字典

• backend (str, default='auto') – geomloss的数值后端。只有‘auto’、‘tensorized’、‘online’和‘multiscale’是接受的值。

Returns:

• value (float) – OT 值

• log (dict) – 日志字典，仅在参数中 log==True 时返回

参考文献

[60]

Feydy, J., Roussillon, P., Trouvé, A., & Gori, P. (2019). [快速和可扩展的脑轨迹优化传输。在医学图像计算和计算机辅助干预–MICCAI 2019：第22届国际会议，中国深圳，2019年10月13日至17日，会议记录，第三部分22 (第636-644页)。斯普林格国际出版社。

[61]

Charlier, B., Feydy, J., Glaunes, J. A., Collin, F. D., & Durif, G. (2021). 在gpu上进行内核操作，带有自动微分，无内存溢出。《机器学习研究杂志》，22(1)，3457-3462。

ot.bregman.empirical_sinkhorn_divergence(X_s, X_t, reg, a=None, b=None, metric='sqeuclidean', numIterMax=10000, stopThr=1e-09, verbose=False, log=False, warn=True, warmstart=None, **kwargs)

计算来自经验数据的Sinkhorn发散损失

该函数求解以下优化问题并返回Sinkhorn散度 \(S\)：

\[ \begin{align}\begin{aligned}W &= \min_\gamma \quad \langle \gamma, \mathbf{M} \rangle_F + \mathrm{reg} \cdot\Omega(\gamma)\\W_a &= \min_{\gamma_a} \quad \langle \gamma_a, \mathbf{M_a} \rangle_F + \mathrm{reg} \cdot\Omega(\gamma_a)\\W_b &= \min_{\gamma_b} \quad \langle \gamma_b, \mathbf{M_b} \rangle_F + \mathrm{reg} \cdot\Omega(\gamma_b)\\S &= W - \frac{W_a + W_b}{2}\end{aligned}\end{align} \]

\[ \begin{align}\begin{aligned}s.t. \ \gamma \mathbf{1} &= \mathbf{a}\\ \gamma^T \mathbf{1} &= \mathbf{b}\\ \gamma &\geq 0\\ \gamma_a \mathbf{1} &= \mathbf{a}\\ \gamma_a^T \mathbf{1} &= \mathbf{a}\\ \gamma_a &\geq 0\\ \gamma_b \mathbf{1} &= \mathbf{b}\\ \gamma_b^T \mathbf{1} &= \mathbf{b}\\ \gamma_b &\geq 0\end{aligned}\end{align} \]

其中 :

• \(\mathbf{M}\)（分别为\(\mathbf{M_a}\)，\(\mathbf{M_b}\)） 是（n_samples_a，n_samples_b）度量成本矩阵 （分别为（n_samples_a, n_samples_a）和（n_samples_b，n_samples_b））

• \(\Omega\) 是熵正则化项 \(\Omega(\gamma)=\sum_{i,j} \gamma_{i,j}\log(\gamma_{i,j})\)

• \(\mathbf{a}\) 和 \(\mathbf{b}\) 是源权重和目标权重（总和为1）

并返回 \(\langle \gamma^*, \mathbf{M} \rangle_F -(\langle \gamma^*_a, \mathbf{M_a} \rangle_F + \langle \gamma^*_b , \mathbf{M_b} \rangle_F)/2\).

Sinkhorn散度如文献中所述。将来版本将提供考虑熵贡献的可能性。

Parameters:

• X_s (类数组, 形状 (n_samples_a, 维度)) – 源域中的样本

• X_t (类似数组, 形状 (n_samples_b, 维度)) – 目标域中的样本

• reg (float) – 正则化项 >0

• a (类数组, 形状 (n_samples_a,)) – 源域中的样本权重

• b (数组类型, 形状 (n_samples_b,)) – 目标领域中的样本权重

• numItermax (int, 可选) – 最大迭代次数

• stopThr (float, 可选) – 错误的停止阈值 (>0)

• verbose (bool, 可选) – 在迭代过程中打印信息

• log (bool, 可选) – 如果为真，则记录日志

• warn (bool, 可选) – 如果为True，当算法不收敛时会发出警告。

• warmstart (元组 的 数组, 形状 (dim_a, dim_b), 可选) – 对偶潜力的初始化。如果提供，应该给出对偶潜力 （即 u,v Sinkhorn 缩放向量的对数）

Returns:

• W ((1,) 类似数组) – 针对给定参数的最佳运输对称损失

• log (字典) – 仅在参数中的 log==True 时返回日志字典

示例

>>> import numpy as np
>>> n_samples_a = 2
>>> n_samples_b = 4
>>> reg = 0.1
>>> X_s = np.reshape(np.arange(n_samples_a, dtype=np.float64), (n_samples_a, 1))
>>> X_t = np.reshape(np.arange(0, n_samples_b, dtype=np.float64), (n_samples_b, 1))
>>> empirical_sinkhorn_divergence(X_s, X_t, reg)  
1.499887176049052

参考文献

[23]

Aude Genevay, Gabriel Peyré, Marco Cuturi, 使用Sinkhorn散度学习生成模型， 第21届国际人工智能与统计会议论文集， (AISTATS) 21, 2018

ot.bregman.free_support_sinkhorn_barycenter(measures_locations, measures_weights, X_init, reg, b=None, weights=None, numItermax=100, numInnerItermax=1000, stopThr=1e-07, verbose=False, log=None, **kwargs)

解决自由支持（重心的位置被优化，而不是权重）正则化Wasserstein重心问题（即2-Sinkhorn散度的加权Frechet均值），公式如下：

\[\min_\mathbf{X} \quad \sum_{i=1}^N w_i W_{reg}^2(\mathbf{b}, \mathbf{X}, \mathbf{a}_i, \mathbf{X}_i)\]

其中 :

• \(w \in \mathbb{(0, 1)}^{N}\) 是 barycenter 权重，其总和为 1

• measure_weights 表示 \(\mathbf{a}_i \in \mathbb{R}^{k_i}\): 经验度量权重（在单纯形上）

• measures_locations 指的是 \(\mathbf{X}_i \in \mathbb{R}^{k_i, d}\): 经验测量原子的位置

• \(\mathbf{b} \in \mathbb{R}^{k}\) 是所需的重心权重向量

这个问题在[20]（算法 2）中被考虑。以下代码有两个不同之处：

• 我们不对权重进行优化

• 我们不进行位置更新的线搜索，我们使用即 \(\theta = 1\) 在 [20]（算法 2）中。这可以看作是在连续设置中 [43] 提出的固定点算法的离散实现。

• 在每次迭代中，我们使用Sinkhorn算法来计算运输计划，而不是解决一个精确的OT问题，如[20]所示（算法2）。

Parameters:

• measures_locations (列表 的 N (k_i,d) 数组类型) – 测量支持于 \(k_i\) 位置的离散支持，在一个 d 维空间中 (\(k_i\) 对于列表的每个元素可以是不同的)

• measures_weights (列表 的 N (k_i,) 类数组) – Numpy 数组，其中每个 numpy 数组具有 \(k_i\) 个非负值，总和为一，代表每个离散输入度量的权重

• X_init ((k,d) 数组类型) – 重心的支持位置（在 k 个原子上）的初始化

• reg (float) – 正则化项 >0

• b ((k,) 类似数组) – 重心权重的初始化（非负数，总和为1）

• 权重 ((N,) 类数组) – 重心系数的初始化（非负，和为1）

• numItermax (int, 可选) – 最大迭代次数

• numInnerItermax (int, 可选) – 计算使用Sinkhorn的运输计划时的最大迭代次数

• stopThr (float, 可选) – 错误的停止阈值 (>0)

• verbose (bool, 可选) – 在迭代过程中打印信息

• log (bool, 可选) – 如果为真，则记录日志

Returns:

X – 重心的支持位置（在k个原子上）

Return type:

(k,d) 类似数组

另请参见

ot.bregman.sinkhorn

熵正则化OT求解器

ot.lp.free_support_barycenter

基于线性规划的重心求解器

参考文献

[20]

Cuturi, Marco, 和 Arnaud Doucet. “Wasserstein 序列中心的快速计算。” 国际机器学习大会. 2014.

[43]

Álvarez-Esteban, Pedro C., 等。“在Wasserstein空间中的重心的一个不动点方法。” 数学分析与应用杂志 441.2 (2016): 744-762.

ot.bregman.geometricBar(weights, alldistribT)

返回分布的加权几何平均值

ot.bregman.geometricMean(alldistribT)

返回分布的几何平均数

ot.bregman.greenkhorn(a, b, M, reg, numItermax=10000, stopThr=1e-09, verbose=False, log=False, warn=True, warmstart=None)

求解熵正则化最优运输问题并返回OT矩阵

使用的算法基于论文 [22]，这是一种 Sinkhorn-Knopp 算法的随机版本 [2]

该函数解决以下优化问题：

\[ \begin{align}\begin{aligned}\gamma = \mathop{\arg \min}_\gamma \quad \langle \gamma, \mathbf{M} \rangle_F + \mathrm{reg}\cdot\Omega(\gamma)\\\text{s.t.} \ \gamma \mathbf{1} &= \mathbf{a}\\ \gamma^T \mathbf{1} &= \mathbf{b}\\ \gamma &\geq 0\end{aligned}\end{align} \]

其中 :

• \(\mathbf{M}\) 是 (dim_a, dim_b) 费用矩阵

• \(\Omega\) 是熵正则化项 \(\Omega(\gamma)=\sum_{i,j} \gamma_{i,j}\log(\gamma_{i,j})\)

• \(\mathbf{a}\) 和 \(\mathbf{b}\) 是源权重和目标权重 （直方图，两个都加起来为1）

Parameters:

• a (类似数组, 形状 (dim_a,)) – 源域中的样本权重

• b (数组类似, 形状 (dim_b,) 或 数组类似, 形状 (dim_b, n_hists)) – 目标域中的样本，计算具有多个目标的sinkhorn并且如果\(\mathbf{b}\)是矩阵则固定\(\mathbf{M}\) （返回OT损失 + 对数中的对偶变量）

• M (类似数组, 形状 (dim_a, dim_b)) – 损失矩阵

• reg (float) – 正则化项 >0

• numItermax (int, 可选) – 最大迭代次数

• stopThr (float, 可选) – 错误的停止阈值 (>0)

• log (bool, 可选) – 如果为真，则记录日志

• warn (bool, 可选) – 如果为True，当算法不收敛时会发出警告。

• warmstart (元组 的 数组, 形状 (dim_a, dim_b), 可选) – 对偶潜力的初始化。如果提供，应该给出对偶潜力 （即 u,v Sinkhorn 缩放向量的对数）

Returns:

• gamma (array-like, shape (dim_a, dim_b)) – 给定参数的最佳交通矩阵

• log (dict) – 仅在参数中 log==True 时返回日志字典

示例

>>> import ot
>>> a=[.5, .5]
>>> b=[.5, .5]
>>> M=[[0., 1.], [1., 0.]]
>>> ot.bregman.greenkhorn(a, b, M, 1)
array([[0.36552929, 0.13447071],
       [0.13447071, 0.36552929]])

参考文献

[2]

M. Cuturi, Sinkhorn 距离：优化运输的快速计算，神经信息处理系统进展 (NIPS) 26, 2013

[22]

J. Altschuler, J.Weed, P. Rigollet : 近线性时间的最优传输近似算法通过Sinkhorn迭代，《神经信息处理系统进展》(NIPS) 31, 2017

另请参见

ot.lp.emd

未正则化的OT

ot.optim.cg

通用正则化OT

ot.bregman.jcpot_barycenter(Xs, Ys, Xt, reg, metric='sqeuclidean', numItermax=100, stopThr=1e-06, verbose=False, log=False, warn=True, **kwargs)

联合OT和多源目标偏移的比例估计，如[27]中所提议

该函数解决以下优化问题：

\[ \begin{align}\begin{aligned}\mathbf{h} = \mathop{\arg \min}_{\mathbf{h}} \quad \sum_{k=1}^{K} \lambda_k W_{reg}((\mathbf{D}_2^{(k)} \mathbf{h})^T, \mathbf{a})\\s.t. \ \forall k, \mathbf{D}_1^{(k)} \gamma_k \mathbf{1}_n= \mathbf{h}\end{aligned}\end{align} \]

其中 :

• \(\lambda_k\) 是第 k 个源领域的权重

• \(W_{reg}(\cdot,\cdot)\) 是熵正则化的Wasserstein距离（见 ot.bregman.sinkhorn()）

• \(\mathbf{D}_2^{(k)}\) 是一个与 k -th 源域相关的权重矩阵，定义如 [p. 5, 27] 所示，其期望形状为 \((n_k, C)\)，其中 \(n_k\) 是 k -th 源域中的元素数量，而 C 是类别的数量

• \(\mathbf{h}\) 是目标领域中估计比例的一个向量，大小为 C

• \(\mathbf{a}\) 是目标域中大小为 n 的均匀权重向量

• \(\mathbf{D}_1^{(k)}\) 是一个类分配矩阵，如在 [p. 5, 27] 中定义，预期形状为 \((n_k, C)\)

该问题在于解决一个Wasserstein重心问题，以估计目标域中的比例\(\mathbf{h}\)。

用于解决该问题的算法是迭代Bregman投影算法，该算法具有与未知向量\(\mathbf{h}\)和均匀目标分布相关的两个边际约束集。

Parameters:

• Xs (list 的 K 类数组(nsk,d)) – 所有源域样本的特征

• Ys (列表 of K 类似数组(nsk,)) – 所有源领域样本的标签

• Xt (数组类型 (nt,d)) – 目标领域中的样本

• reg (float) – 正则化项 > 0

• metric (string, 可选 (默认="sqeuclidean")) – Wasserstein 问题的基础度量

• numItermax (int, 可选) – 最大迭代次数

• stopThr (float, 可选) – 重心相对变化的停止阈值 (>0)

• verbose (bool, 可选 (默认=False)) – 控制优化算法的详细程度

• log (bool, 可选) – 如果为真，则记录日志

• warn (bool, 可选) – 如果为True，当算法不收敛时会发出警告。

Returns:

• h ((C,) 类似数组) – 目标域中的比例估计

• log (字典) – 仅在参数中log==True时返回日志字典

参考文献

[27]

Ievgen Redko, Nicolas Courty, Rémi Flamary, Devis Tuia “在目标偏移下的多源领域适应的最优传输”, 国际人工智能与统计会议 (AISTATS), 2019.

ot.bregman.projC(gamma, q)

返回列约束上的KL投影

ot.bregman.projR(gamma, p)

返回行约束上的KL投影

ot.bregman.screenkhorn(a, b, M, reg, ns_budget=None, nt_budget=None, uniform=False, restricted=True, maxiter=10000, maxfun=10000, pgtol=1e-09, verbose=False, log=False)

正则化最优传输的筛选Sinkhorn算法

该函数解决了Sinkhorn散度的近似对偶 [2]，其形式如下优化问题：

\[(\mathbf{u}, \mathbf{v}) = \mathop{\arg \min}_{\mathbf{u}, \mathbf{v}} \quad \mathbf{1}_{ns}^T \mathbf{B}(\mathbf{u}, \mathbf{v}) \mathbf{1}_{nt} - \langle \kappa \mathbf{u}, \mathbf{a} \rangle - \langle \frac{1}{\kappa} \mathbf{v}, \mathbf{b} \rangle\]

其中：

\[\mathbf{B}(\mathbf{u}, \mathbf{v}) = \mathrm{diag}(e^\mathbf{u}) \mathbf{K} \mathrm{diag}(e^\mathbf{v}) \text{，其中 } \mathbf{K} = e^{-\mathbf{M} / \mathrm{reg}} \text{ 和}\]

\[ \begin{align}\begin{aligned}s.t. \ e^{u_i} &\geq \epsilon / \kappa, \forall i \in \{1, \ldots, ns\}\\ e^{v_j} &\geq \epsilon \kappa, \forall j \in \{1, \ldots, nt\}\end{aligned}\end{align} \]

参数 kappa 和 epsilon 是相对于点的组合数量预算 (ns_budget, nt_budget) 确定的，见 [26] 中的公式 (5)

Parameters:

• a (类似数组, 形状=(ns,)) – 源域中的样本权重

• b (类数组, 形状=(nt,)) – 目标领域中的样本权重

• M (类似数组, 形状=(ns, nt)) – 成本矩阵

• reg (float) – 熵正则化的水平

• ns_budget (int, default=None) – 要在源域中保留的点数预算。如果为None，则将保留50%的源样本点。

• nt_budget (int, default=None) – 要保留在目标域中的点数预算。如果为 None，则将保留目标样本点的 50%

• uniform (bool, default=False) – 如果 True，源分布和目标分布假定为均匀，即 \(a_i = 1 / ns\) 和 \(b_j = 1 / nt\)

• restricted (bool, default=True) – 如果 True，则使用最多进行5次迭代的限制Sinkhorn算法对L-BFGS-B求解器进行热启动初始化

• maxiter (int, default=10000) – LBFGS 求解器中的最大迭代次数

• maxfun (int, default=10000) – LBFGS求解器中函数评估的最大次数

• pgtol (float, default=1e-09) – LBFGS求解器中的最终目标函数精度

• verbose (bool, default=False) – 如果 True，显示活动集的基数以及参数 kappa 和 epsilon 的信息

依赖

为了提高效率， ot.bregman.screenkhorn() 需要在筛选预处理步骤中调用“Bottleneck”包 (https://pypi.org/project/Bottleneck/)。

如果没有安装Bottleneck，将显示以下错误信息：

“Bottleneck模块不存在。请从 https://pypi.org/project/Bottleneck/ 安装它”

Returns:

• gamma (类数组，形状=(ns, nt)) – 对给定参数的筛选最优运输矩阵

• log (字典, 默认=False) – 仅在参数log==True时返回日志字典

参考文献

[2]

M. Cuturi, Sinkhorn距离：优化运输的快速计算，神经信息处理系统进展（NIPS）26，2013

[26]

Alaya M. Z., Bérar M., Gasso G., Rakotomamonjy A. (2019). 筛选Sinkhorn算法用于正则化最优传输 (NIPS) 33, 2019

ot.bregman.sinkhorn(a, b, M, reg, method='sinkhorn', numItermax=1000, stopThr=1e-09, verbose=False, log=False, warn=True, warmstart=None, **kwargs)

求解熵正则化最优运输问题并返回OT矩阵

该函数解决以下优化问题：

\[ \begin{align}\begin{aligned}\gamma = \mathop{\arg \min}_\gamma \quad \langle \gamma, \mathbf{M} \rangle_F + \mathrm{reg}\cdot\Omega(\gamma)\\\text{s.t.} \ \gamma \mathbf{1} &= \mathbf{a}\\ \gamma^T \mathbf{1} &= \mathbf{b}\\ \gamma &\geq 0\end{aligned}\end{align} \]

其中 :

• \(\mathbf{M}\) 是 (dim_a, dim_b) 费用矩阵

• \(\Omega\) 是熵正则化项 \(\Omega(\gamma)=\sum_{i,j} \gamma_{i,j}\log(\gamma_{i,j})\)

• \(\mathbf{a}\) 和 \(\mathbf{b}\) 是源权重和目标权重 （直方图，两个都加起来为1）

注意

此函数与后端兼容，并且适用于所有兼容后端的数组。

用于解决问题的算法是Sinkhorn-Knopp矩阵缩放算法，如[2]中所提议的

选择一个Sinkhorn求解器

默认情况下，当使用的正则化参数不太小的时候，默认的 sinkhorn 求解器应该已经足够。如果你需要使用较小的正则化来获得更清晰的 OT 矩阵，你应该使用 ot.bregman.sinkhorn_stabilized() 求解器，以避免数值错误。最后这个求解器在实践中可能非常慢，甚至可能在有限时间内无法收敛到一个合理的 OT 矩阵。这就是为什么 ot.bregman.sinkhorn_epsilon_scaling() 依赖于迭代正则化值（并使用热启动）有时会导致更好的解决方案。请注意，贪婪版本的 sinkhorn ot.bregman.greenkhorn() 也可以带来加速，而 sinkhorn 的筛选版本 ot.bregman.screenkhorn() 旨在提供 Sinkhorn 问题的快速近似。对于 GPU 的使用和小迭代次数的梯度计算，我们强烈推荐 ot.bregman.sinkhorn_log() 求解器，因为它不需要检查数值问题。

Parameters:

• a (类似数组, 形状 (dim_a,)) – 源域中的样本权重

• b (类数组, 形状 (dim_b,) 或 ndarray, 形状 (dim_b, n_hists)) – 目标域中的样本，如果\(\mathbf{b}\)是一个矩阵，则计算带有多个目标和固定\(\mathbf{M}\)的Sinkhorn（返回OT损失 + 对数中的双变量）

• M (类似数组, 形状 (dim_a, dim_b)) – 损失矩阵

• reg (float) – 正则化项 >0

• 方法 (str) – 求解器使用的方法，可能是‘sinkhorn’，‘sinkhorn_log’，‘greenkhorn’，‘sinkhorn_stabilized’ 或 ‘sinkhorn_epsilon_scaling’，具体参数请参见这些函数

• numItermax (int, 可选) – 最大迭代次数

• stopThr (float, 可选) – 错误的停止阈值 (>0)

• verbose (bool, 可选) – 在迭代过程中打印信息

• log (bool, 可选) – 如果为真，则记录日志

• warn (bool, 可选) – 如果为True，当算法不收敛时会发出警告。

• warmstart (元组 的 数组, 形状 (dim_a, dim_b), 可选) – 对偶潜力的初始化。如果提供，应该给出对偶潜力 （即 u,v Sinkhorn 缩放向量的对数）

Returns:

• gamma (array-like, shape (dim_a, dim_b)) – 给定参数的最佳交通矩阵

• log (dict) – 仅在参数中 log==True 时返回日志字典

示例

>>> 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]])

参考文献

[2]

M. Cuturi, Sinkhorn 距离：快速计算最优传输，神经信息处理系统进展（NIPS）26, 2013

[9]

Schmitzer, B. (2016). 稳定的稀疏缩放算法 用于熵正则化运输问题。arXiv 预印本 arXiv:1610.06519。

[10]

Chizat, L., Peyré, G., Schmitzer, B., & Vialard, F. X. (2016). 缩放算法用于不平衡交通问题。 arXiv 预印本 arXiv:1607.05816.

[34]

Feydy, J., Séjourné, T., Vialard, F. X., Amari, S. I., Trouvé, A., & Peyré, G. (2019年4月). 使用Sinkhorn散度在最优传输和MMD之间进行插值。在第22届国际人工智能与统计会议(pp. 2681-2690). PMLR.

另请参见

ot.lp.emd

未正则化的OT

ot.optim.cg

通用正则化OT

ot.bregman.sinkhorn_knopp

经典Sinkhorn [2]

ot.bregman.sinkhorn_stabilized

稳定的Sinkhorn [9] [10]

ot.bregman.sinkhorn_epsilon_scaling

Sinkhorn与epsilon缩放 [9] [10]

ot.bregman.sinkhorn2(a, b, M, reg, method='sinkhorn', numItermax=1000, stopThr=1e-09, verbose=False, log=False, warn=False, warmstart=None, **kwargs)

解决熵正则化最优传输问题并返回损失

该函数解决以下优化问题：

\[ \begin{align}\begin{aligned}W = \min_\gamma \quad \langle \gamma, \mathbf{M} \rangle_F + \mathrm{reg}\cdot\Omega(\gamma)\\s.t. \ \gamma \mathbf{1} &= \mathbf{a}\\ \gamma^T \mathbf{1} &= \mathbf{b}\\ \gamma &\geq 0\end{aligned}\end{align} \]

其中 :

• \(\mathbf{M}\) 是 (dim_a, dim_b) 费用矩阵

• \(\Omega\) 是熵正则化项 \(\Omega(\gamma)=\sum_{i,j} \gamma_{i,j}\log(\gamma_{i,j})\)

• \(\mathbf{a}\) 和 \(\mathbf{b}\) 是源权重和目标权重 （直方图，两个都加起来为1）

并返回 \(\langle \gamma^*, \mathbf{M} \rangle_F\) （不包括熵贡献）。

注意

此函数与后端兼容，并且适用于所有兼容后端的数组。

用于解决问题的算法是Sinkhorn-Knopp矩阵缩放算法，如[2]中所提议的

选择一个Sinkhorn求解器

默认情况下，当使用的正则化参数不是太小的时候，默认的 sinkhorn 求解器应该是足够的。如果您需要使用较小的正则化来获得更清晰的 OT 矩阵，您应该使用 ot.bregman.sinkhorn_log() 求解器，这将避免数值错误。最后这个求解器在实践中可能非常慢，甚至可能根本无法在有限的时间内收敛到合理的 OT 矩阵。这就是为什么 ot.bregman.sinkhorn_epsilon_scaling() 依靠迭代正则化的值（并使用热启动）有时会导致更好的解决方案。请注意，贪婪版本的 sinkhorn ot.bregman.greenkhorn() 也可以带来加速，而 sinkhorn 的筛选版本 ot.bregman.screenkhorn() 旨在提供 Sinkhorn 问题的快速近似。对于使用 GPU 和小迭代次数的梯度计算，我们强烈推荐 ot.bregman.sinkhorn_log() 求解器，它无需检查数值问题。

Parameters:

• a (类似数组, 形状 (dim_a,)) – 源域中的样本权重

• b (类数组, 形状 (dim_b,) 或 ndarray, 形状 (dim_b, n_hists)) – 目标域中的样本，如果\(\mathbf{b}\)是一个矩阵，则计算带有多个目标和固定\(\mathbf{M}\)的Sinkhorn（返回OT损失 + 对数中的双变量）

• M (类似数组, 形状 (dim_a, dim_b)) – 损失矩阵

• reg (float) – 正则化项 >0

• 方法 (str) – 求解器使用的方法，可以是‘sinkhorn’，’sinkhorn_log’，‘sinkhorn_stabilized’，有关具体参数，请参见这些函数

• numItermax (int, 可选) – 最大迭代次数

• stopThr (float, 可选) – 错误的停止阈值 (>0)

• verbose (bool, 可选) – 在迭代过程中打印信息

• log (bool, 可选) – 如果为真，则记录日志

• warn (bool, 可选) – 如果为True，当算法不收敛时会发出警告。

• warmstart (元组 的 数组, 形状 (dim_a, dim_b), 可选) – 对偶潜力的初始化。如果提供，应该给出对偶潜力 （即 u,v Sinkhorn 缩放向量的对数）

Returns:

• W ((n_hists) 浮点数/数组类型) – 给定参数的最优运输损失

• log (字典) – 仅在参数中log==True时返回日志字典

示例

>>> import ot
>>> a=[.5, .5]
>>> b=[.5, .5]
>>> M=[[0., 1.], [1., 0.]]
>>> ot.sinkhorn2(a, b, M, 1)
0.26894142136999516

参考文献

[2]

M. Cuturi, Sinkhorn 距离：优化运输的快速计算，神经信息处理系统进展 (NIPS) 26, 2013

[9]

Schmitzer, B. (2016). 稳定稀疏缩放算法用于熵正则化运输问题。 arXiv预印本 arXiv:1610.06519。

[10]

Chizat, L., Peyré, G., Schmitzer, B., & Vialard, F. X. (2016). 缩放算法用于不平衡交通问题。 arXiv 预印本 arXiv:1607.05816.

[21]

Altschuler J., Weed J., Rigollet P. : 通过Sinkhorn迭代的最优传输近线性时间近似算法，神经信息处理系统进展 (NIPS) 31, 2017

[34]

Feydy, J., Séjourné, T., Vialard, F. X., Amari, S. I., Trouvé, A., & Peyré, G. (2019年4月). 通过Sinkhorn散度在最优运输和MMD之间进行插值。在第22届国际人工智能与统计会议（第2681-2690页）。PMLR。

另请参见

ot.lp.emd

未正则化的OT

ot.optim.cg

通用正则化OT

ot.bregman.sinkhorn_knopp

经典Sinkhorn [2]

ot.bregman.greenkhorn

Greenkhorn [21]

ot.bregman.sinkhorn_stabilized

稳定的Sinkhorn [9] [10]

ot.bregman.sinkhorn_epsilon_scaling(a, b, M, reg, numItermax=100, epsilon0=10000.0, numInnerItermax=100, tau=1000.0, stopThr=1e-09, warmstart=None, verbose=False, print_period=10, log=False, warn=True, **kwargs)

求解具有对数稳定化和 epsilon 缩放的熵正则化最优传输问题。 该函数解决以下优化问题：

\[ \begin{align}\begin{aligned}\gamma = \mathop{\arg \min}_\gamma \quad \langle \gamma, \mathbf{M} \rangle_F + \mathrm{reg}\cdot\Omega(\gamma)\\\text{s.t.} \ \gamma \mathbf{1} &= \mathbf{a}\\ \gamma^T \mathbf{1} &= \mathbf{b}\\ \gamma &\geq 0\end{aligned}\end{align} \]

其中 :

• \(\mathbf{M}\) 是 (dim_a, dim_b) 费用矩阵

• \(\Omega\) 是熵正则化项 \(\Omega(\gamma)=\sum_{i,j} \gamma_{i,j}\log(\gamma_{i,j})\)

• \(\mathbf{a}\) 和 \(\mathbf{b}\) 是源权重和目标权重（直方图，两者之和为1）

用于解决该问题的算法是Sinkhorn-Knopp矩阵缩放算法，正如在 [2] 中提出的，但使用了在 [10] 中提出的对数稳定化和在 [9] 中提出的对数缩放算法 3.2

Parameters:

• a (类似数组, 形状 (dim_a,)) – 源域中的样本权重

• b (数组类型, 形状 (dim_b,)) – 目标域中的样本

• M (类似数组, 形状 (dim_a, dim_b)) – 损失矩阵

• reg (float) – 正则化项 >0

• tau (float) – 对于对数缩放的\(\mathbf{u}\)或\(\mathbf{b}\)的最大值的阈值

• warmstart (元组 类型为 向量) – 如果提供，则为 alpha 和 beta 对数缩放的起始值

• numItermax (int, 可选) – 最大迭代次数

• numInnerItermax (int, 可选) – 内部稳定化Sinkhorn算法的最大迭代次数

• epsilon0 (int, 可选) – 第一个epsilon正则化值（然后指数递减到正则化）

• stopThr (float, 可选) – 错误的停止阈值 (>0)

• verbose (bool, 可选) – 在迭代过程中打印信息

• log (bool, 可选) – 如果为真，则记录日志

• warn (bool, 可选) – 如果为True，当算法不收敛时会发出警告。

Returns:

• gamma (array-like, shape (dim_a, dim_b)) – 给定参数的最佳交通矩阵

• log (dict) – 仅在参数中 log==True 时返回日志字典

示例

>>> import ot
>>> a=[.5, .5]
>>> b=[.5, .5]
>>> M=[[0., 1.], [1., 0.]]
>>> ot.bregman.sinkhorn_epsilon_scaling(a, b, M, 1)
array([[0.36552929, 0.13447071],
       [0.13447071, 0.36552929]])

参考文献

[2]

M. Cuturi, Sinkhorn距离：最优运输的快速计算，神经信息处理系统进展（NIPS）26，2013

[9]

Schmitzer, B. (2016). 稳定稀疏缩放算法用于熵正则化运输问题。arXiv 预印本 arXiv:1610.06519.

[10]

Chizat, L., Peyré, G., Schmitzer, B., & Vialard, F. X. (2016). 不平衡运输问题的规模化算法。arXiv 预印本 arXiv:1607.05816.

另请参见

ot.lp.emd

未正则化的OT

ot.optim.cg

通用正则化OT

ot.bregman.sinkhorn_knopp(a, b, M, reg, numItermax=1000, stopThr=1e-09, verbose=False, log=False, warn=True, warmstart=None, **kwargs)

求解熵正则化最优运输问题并返回OT矩阵

该函数解决以下优化问题：

\[ \begin{align}\begin{aligned}\gamma = \mathop{\arg \min}_\gamma \quad \langle \gamma, \mathbf{M} \rangle_F + \mathrm{reg}\cdot\Omega(\gamma)\\\text{s.t.} \ \gamma \mathbf{1} &= \mathbf{a}\\ \gamma^T \mathbf{1} &= \mathbf{b}\\ \gamma &\geq 0\end{aligned}\end{align} \]

其中 :

• \(\mathbf{M}\) 是 (dim_a, dim_b) 费用矩阵

• \(\Omega\) 是熵正则化项 \(\Omega(\gamma)=\sum_{i,j} \gamma_{i,j}\log(\gamma_{i,j})\)

• \(\mathbf{a}\) 和 \(\mathbf{b}\) 是源权重和目标权重 （直方图，两个都加起来为1）

用于解决该问题的算法是Sinkhorn-Knopp矩阵缩放算法，如[2]中所提议的

Parameters:

• a (类似数组, 形状 (dim_a,)) – 源域中的样本权重

• b (数组类似, 形状 (dim_b,) 或 数组类似, 形状 (dim_b, n_hists)) – 目标域中的样本，计算具有多个目标的sinkhorn并且如果\(\mathbf{b}\)是矩阵则固定\(\mathbf{M}\) （返回OT损失 + 对数中的对偶变量）

• M (类似数组, 形状 (dim_a, dim_b)) – 损失矩阵

• reg (float) – 正则化项 >0

• numItermax (int, 可选) – 最大迭代次数

• stopThr (float, 可选) – 错误的停止阈值 (>0)

• verbose (bool, 可选) – 在迭代过程中打印信息

• log (bool, 可选) – 如果为真，则记录日志

• warn (bool, 可选) – 如果为True，当算法不收敛时会发出警告。

• warmstart (元组 的 数组, 形状 (dim_a, dim_b), 可选) – 对偶潜力的初始化。如果提供，应该给出对偶潜力 （即 u,v Sinkhorn 缩放向量的对数）

Returns:

• gamma (array-like, shape (dim_a, dim_b)) – 给定参数的最佳交通矩阵

• log (dict) – 仅在参数中 log==True 时返回日志字典

示例

>>> 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]])

参考文献

[2]

M. Cuturi, Sinkhorn 距离：优化运输的快速计算，神经信息处理系统进展 (NIPS) 26, 2013

另请参见

ot.lp.emd

未正则化的OT

ot.optim.cg

通用正则化OT

ot.bregman.sinkhorn_log(a, b, M, reg, numItermax=1000, stopThr=1e-09, verbose=False, log=False, warn=True, warmstart=None, **kwargs)

在对数空间中解决熵正则化最优传输问题并返回OT矩阵

该函数解决以下优化问题：

\[ \begin{align}\begin{aligned}\gamma = \mathop{\arg \min}_\gamma \quad \langle \gamma, \mathbf{M} \rangle_F + \mathrm{reg}\cdot\Omega(\gamma)\\\text{s.t.} \ \gamma \mathbf{1} &= \mathbf{a}\\ \gamma^T \mathbf{1} &= \mathbf{b}\\ \gamma &\geq 0\end{aligned}\end{align} \]

其中 :

• \(\mathbf{M}\) 是 (dim_a, dim_b) 费用矩阵

• \(\Omega\) 是熵正则化项 \(\Omega(\gamma)=\sum_{i,j} \gamma_{i,j}\log(\gamma_{i,j})\)

• \(\mathbf{a}\) 和 \(\mathbf{b}\) 是源权重和目标权重（直方图，两者之和为1）

用于解决该问题的算法是Sinkhorn-Knopp矩阵缩放算法 [2]，其实现来自 [34]

Parameters:

• a (类似数组, 形状 (dim_a,)) – 源域中的样本权重

• b (数组类型, 形状 (dim_b,) 或 数组类型, 形状 (dim_b, n_hists)) – 目标域中的样本，使用多个目标计算sinkhorn 并在\(\mathbf{b}\)为矩阵时固定\(\mathbf{M}\)（返回OT损失 + 对偶变量的对数）

• M (类似数组, 形状 (dim_a, dim_b)) – 损失矩阵

• reg (float) – 正则化项 >0

• numItermax (int, 可选) – 最大迭代次数

• stopThr (float, 可选) – 错误的停止阈值 (>0)

• verbose (bool, 可选) – 在迭代过程中打印信息

• log (bool, 可选) – 如果为真，则记录日志

• warn (bool, 可选) – 如果为True，当算法不收敛时会发出警告。

• warmstart (元组 的 数组, 形状 (dim_a, dim_b), 可选) – 对偶潜力的初始化。如果提供，应该给出对偶潜力 （即 u,v Sinkhorn 缩放向量的对数）

Returns:

• gamma (array-like, shape (dim_a, dim_b)) – 给定参数的最佳交通矩阵

• log (dict) – 仅在参数中 log==True 时返回日志字典

示例

>>> 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]])

参考文献

[2]

M. Cuturi, Sinkhorn 距离 : 最优运输的快速计算，神经信息处理系统进展（NIPS）26, 2013

[34]

Feydy, J., Séjourné, T., Vialard, F. X., Amari, S. I., Trouvé, A., & Peyré, G. (2019年4月). 在Sinkhorn散度下，插值最优运输和MMD。在第22届国际人工智能与统计会议上（第2681-2690页）。PMLR.

另请参见

ot.lp.emd

未正则化的OT

ot.optim.cg

通用正则化OT

ot.bregman.sinkhorn_stabilized(a, b, M, reg, numItermax=1000, tau=1000.0, stopThr=1e-09, warmstart=None, verbose=False, print_period=20, log=False, warn=True, **kwargs)

解决带有对数稳定化的熵正则化OT问题

该函数解决以下优化问题：

\[ \begin{align}\begin{aligned}\gamma = \mathop{\arg \min}_\gamma \quad \langle \gamma, \mathbf{M} \rangle_F + \mathrm{reg}\cdot\Omega(\gamma)\\\text{s.t.} \ \gamma \mathbf{1} &= \mathbf{a}\\ \gamma^T \mathbf{1} &= \mathbf{b}\\ \gamma &\geq 0\end{aligned}\end{align} \]

其中 :

• \(\mathbf{M}\) 是 (dim_a, dim_b) 费用矩阵

• \(\Omega\) 是熵正则化项 \(\Omega(\gamma)=\sum_{i,j} \gamma_{i,j}\log(\gamma_{i,j})\)

• \(\mathbf{a}\) 和 \(\mathbf{b}\) 是源权重和目标权重 （直方图，两个都加起来为1）

用于解决该问题的算法是Sinkhorn-Knopp矩阵缩放算法，如[2]所提及，但进行了[10]中提出的对数稳定化，并在[9]中定义（算法3.1）。

Parameters:

• a (类似数组, 形状 (dim_a,)) – 源域中的样本权重

• b (数组类型, 形状 (dim_b,)) – 目标域中的样本

• M (类似数组, 形状 (dim_a, dim_b)) – 损失矩阵

• reg (float) – 正则化项 >0

• tau (float) – \(\mathbf{u}\) 或 \(\mathbf{v}\) 的最大值的阈值，用于对数缩放

• warmstart (表 的 向量) – 如果提供，则为 alpha 和 beta 对数缩放的起始值

• numItermax (int, 可选) – 最大迭代次数

• stopThr (float, 可选) – 错误的停止阈值 (>0)

• verbose (bool, 可选) – 在迭代过程中打印信息

• log (bool, 可选) – 如果为真，则记录日志

• warn (bool, 可选) – 如果为True，当算法不收敛时会发出警告。

Returns:

• gamma (array-like, shape (dim_a, dim_b)) – 给定参数的最佳交通矩阵

• log (dict) – 仅在参数中 log==True 时返回日志字典

示例

>>> import ot
>>> a=[.5,.5]
>>> b=[.5,.5]
>>> M=[[0.,1.],[1.,0.]]
>>> ot.bregman.sinkhorn_stabilized(a, b, M, 1)
array([[0.36552929, 0.13447071],
       [0.13447071, 0.36552929]])

参考文献

[2]

M. Cuturi, Sinkhorn 距离 : 最优运输的快速计算，神经信息处理系统进展（NIPS）26, 2013

[9]

Schmitzer, B. (2016). 稳定稀疏缩放算法用于熵正则化运输问题。 arXiv预印本 arXiv:1610.06519。

[10]

Chizat, L., Peyré, G., Schmitzer, B., & Vialard, F. X. (2016). 缩放算法用于不平衡交通问题。 arXiv 预印本 arXiv:1607.05816.

另请参见

ot.lp.emd

未正则化的OT

ot.optim.cg

通用正则化OT

ot.bregman.unmix(a, D, M, M0, h0, reg, reg0, alpha, numItermax=1000, stopThr=0.001, verbose=False, log=False, warn=True)

使用Wasserstein距离计算给定字典的观测值的解混合

该函数解决以下优化问题：

\[\mathbf{h} = \mathop{\arg \min}_\mathbf{h} \quad (1 - \alpha) W_{\mathbf{M}, \mathrm{reg}}(\mathbf{a}, \mathbf{Dh}) + \alpha W_{\mathbf{M_0}, \mathrm{reg}_0}(\mathbf{h}_0, \mathbf{h})\]

其中 :

• \(W_{M,reg}(\cdot,\cdot)\) 是带有熵正则化的Wasserstein距离，使用的是 \(\mathbf{M}\) 损失矩阵（见 ot.bregman.sinkhorn()）

• \(\mathbf{D}\) 是一个包含 n_atoms 个维度为 dim_a 的原子的字典，它的预期形状为 (dim_a, n_atoms)

• \(\mathbf{h}\) 是维度 n_atoms 的估计混合解

• \(\mathbf{a}\) 是一个维度为 dim_a 的观察分布

• \(\mathbf{h}_0\) 是维度为 dim_prior 的 \(\mathbf{h}\) 的先验

• reg 和 \(\mathbf{M}\) 分别是正则化项和 OT 数据拟合的成本矩阵 (dim_a, dim_a)

• reg\(_0\) 和 \(\mathbf{M_0}\) 分别是正则化项和成本矩阵 (dim_prior，n_atoms) 正则化

• \(\alpha\) 权重数据拟合和正则化

优化问题按照[4]中描述的算法进行求解

Parameters:

• a (类数组, 形状 (dim_a)) – 观察到的分布（直方图，总和为1）

• D (类似数组, 形状 (dim_a, n_atoms)) – 字典矩阵

• M (类似数组, 形状 (dim_a, dim_a)) – 损失矩阵

• M0 (类数组, 形状 (n_atoms, dim_prior)) – 损失矩阵

• h0 (类似数组, 形状 (原子数,)) – 对估计的解混合 h 的先验

• reg (float) – 正则化项 >0 （Wasserstein 数据拟合）

• reg0 (float) – 正则化项 >0 (与 h0 的 Wasserstein 正则化)

• alpha (float) – 我们应该多大程度上信任先验 ([0,1])

• numItermax (int, 可选) – 最大迭代次数

• stopThr (float, 可选) – 错误的停止阈值 (>0)

• verbose (bool, 可选) – 在迭代过程中打印信息

• log (bool, 可选) – 如果为真，则记录日志

• warn (bool, 可选) – 如果为True，当算法不收敛时会发出警告。

Returns:

• h (数组类型，形状为 (n_atoms,)) – Wasserstein 重心

• log (字典) – 仅在参数中 log==True 时返回日志字典

参考文献

[4]

S. Nakhostin, N. Courty, R. Flamary, D. Tuia, T. Corpetti, 使用最优传输的监督行星解混，关于高光谱图像与信号处理的研讨会： 遥感发展的演变 (WHISPERS)，2016。