POT: Python 最优传输

目录

POT: Python 最优运输

这个开源Python库提供了几个用于与信号、图像处理和机器学习相关的最优运输优化问题的求解器。

网站和文档: https://PythonOT.github.io/

源代码 (MIT): https://github.com/PythonOT/POT

POT 提供以下通用 OT 解算器（示例链接）：

OT Network Simplex solver 用于线性规划/地球搬运者距离 [1]。
条件梯度 [6] 和广义条件梯度用于正则化的OT [7]。
熵正则化OT求解器，采用 Sinkhorn Knopp 算法 [2]，稳定版本 [9] [10] [34]，来自geomloss的懒惰CPU/GPU求解器 [60] [61]，贪婪的Sinkhorn [22] 和筛选Sinkhorn [26]。
Bregman 投影用于 Wasserstein 重心 [3]、卷积重心 [21] 和解混合 [4]。
Sinkhorn 发散 [23] 和来自经验数据的熵正则化 OT。
去偏差的Sinkhorn重心 Sinkhorn divergence barycenter [37]
平滑最优运输求解器（对偶和半对偶）用于KL和平方L2正则化 [17]。
经验分布之间的弱OT求解器 [39]
非正则化的 Wasserstein barycenters [16] 使用LP求解器（仅限小规模）。
Gromov-Wasserstein 距离和 GW 重心（精确 [13] 和正则化 [12,51]），使用来自图字典学习 [38] 的梯度可微分
融合的Gromov-Wasserstein距离求解器和 FGW重心（精确的[24]和正则化的[12,51]）。
随机求解器和可微损失用于大规模最优运输（半对偶问题 [18] 和对偶问题 [19]）
Gromov Wasserstein的抽样求解器用于任何损失函数的大规模问题 [33]
非正则化的自由支持Wasserstein重心 [20].
一维不平衡OT，带有KL松弛和重心 [10, 25]。也有精确不平衡OT，带有KL和二次正则化，以及UOT的正则化路径 [41]
局部瓦瑟斯坦和格罗莫夫-瓦瑟斯坦（精确 [29] 和熵 [3] 公式）。
切片瓦瑟斯坦 [31, 32] 和最大切片瓦瑟斯坦 [35] 可用于梯度流 [36]。
圆上的Wasserstein距离 [44, 45]
球面切片瓦瑟斯坦 [46]
图字典学习求解器 [38].
半放松（融合）Gromov-Wasserstein 发散及其对应的重心求解器（精确和正则化 [48]）。
量化（融合）Gromov-Wasserstein 距离 [68].
高效的离散多边际最优运输正则化 [50].
多个后端方便使用POT与 Pytorch/jax/Numpy/Cupy/Tensorflow 数组。
平滑强凸最邻近Brenier势 [58]，并扩展到使用[59]的边界潜力。
高斯混合模型 OT [69]
共同最优传输 [49] 和不平衡共同最优传输 [71].
融合的不平衡Gromov-Wasserstein [70].

POT提供以下与机器学习相关的求解器：

领域适应的最优传输结合组lasso正则化、拉普拉斯正则化 [5] [30] 和半监督设置。
线性OT映射 [14] 和联合OT映射估计 [8]。
瓦瑟斯坦判别分析 [11] (需要 autograd + pymanopt)。
具有目标偏移的多源领域适应的JCPOT算法 [27].
图神经网络OT层TFGW [52] 和TW (OT-GNN) [53]

其他一些示例可以在文档中找到。

使用和引用该工具箱

如果您在研究中使用这个工具箱并发现它有用，请引用POT，使用以下我们JMLR论文中的参考文献：

Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z. Alaya, Aurélie Boisbunon, Stanislas Chambon, Laetitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, Léo Gautheron, Nathalie T.H. Gayraud, Hicham Janati, Alain Rakotomamonjy, Ievgen Redko, Antoine Rolet, Antony Schutz, Vivien Seguy, Danica J. Sutherland, Romain Tavenard, Alexander Tong, Titouan Vayer,
POT Python Optimal Transport library,
Journal of Machine Learning Research, 22(78):1−8, 2021.
Website: https://pythonot.github.io/

以Bibtex格式：

@article{flamary2021pot,
  author  = {R{\'e}mi Flamary and Nicolas Courty and Alexandre Gramfort and Mokhtar Z. Alaya and Aur{\'e}lie Boisbunon and Stanislas Chambon and Laetitia Chapel and Adrien Corenflos and Kilian Fatras and Nemo Fournier and L{\'e}o Gautheron and Nathalie T.H. Gayraud and Hicham Janati and Alain Rakotomamonjy and Ievgen Redko and Antoine Rolet and Antony Schutz and Vivien Seguy and Danica J. Sutherland and Romain Tavenard and Alexander Tong and Titouan Vayer},
  title   = {POT: Python Optimal Transport},
  journal = {Journal of Machine Learning Research},
  year    = {2021},
  volume  = {22},
  number  = {78},
  pages   = {1-8},
  url     = {http://jmlr.org/papers/v22/20-451.html}
}

安装

该库已在Linux、MacOSX和Windows上进行了测试。它需要一个C++编译器来构建/安装EMD求解器，并依赖以下Python模块：

Numpy (>=1.16)
Scipy (>=1.0)
Cython (>=0.23) （仅在构建时需要，从pip或conda安装时不必要）

Pip 安装

您可以通过 PyPI 安装该工具箱：

pip install POT

或者通过运行以下命令获取最新版本：

pip install -U https://github.com/PythonOT/POT/archive/master.zip # with --user for user install (no root)

可选依赖项可以通过以下方式安装

pip install POT[all]

请注意，这会安装 cvxopt，该软件遵循 GPL 3.0 许可证。或者，如果您无法使用 GPL 许可的软件，可以单独安装特定的可选依赖项，或按子模块安装。可用的可选安装包括 backend-jax, backend-tf, backend-torch, cvxopt, dr, gnn, all。

通过 conda-forge 安装 Anaconda

如果您使用Anaconda python分发版，POT可以在 conda-forge 中获得。要安装它和所需的依赖项：

conda install -c conda-forge pot

安装后检查

正确安装后，您应该能够无错误地导入该模块：

import ot

请注意，为了更方便访问，模块被命名为 ot 而不是 pot。

依赖项

某些子模块需要额外的依赖项，以下是相关讨论

ot.dr（华氏维数降低）依赖于 autograd 和 pymanopt，可以通过以下方式安装：

pip install pymanopt autograd

示例

简短示例

导入工具箱

import ot

计算Wasserstein距离

# a,b are 1D histograms (sum to 1 and positive)
# M is the ground cost matrix
Wd = ot.emd2(a, b, M) # exact linear program
Wd_reg = ot.sinkhorn2(a, b, M, reg) # entropic regularized OT
# if b is a matrix compute all distances to a and return a vector

计算OT矩阵

# a,b are 1D histograms (sum to 1 and positive)
# M is the ground cost matrix
T = ot.emd(a, b, M) # exact linear program
T_reg = ot.sinkhorn(a, b, M, reg) # entropic regularized OT

计算沃瑟斯坦重心

# A is a n*d matrix containing d  1D histograms
# M is the ground cost matrix
ba = ot.barycenter(A, M, reg) # reg is regularization parameter

示例和笔记本

示例文件夹包含该库的几个示例和用例。完整的文档，包括示例和输出，可在 https://PythonOT.github.io/ 上获得。

致谢

这个工具箱是由

目前由以下人员维护

该库的众多贡献者列在这里。

POT 受益于以下合作伙伴的资金或人力支持：

ANR CNRS 3IA Hi!PARIS

贡献和行为准则

每一个贡献都是受欢迎的，并应尊重贡献指南。项目的每个成员都应遵循行为准则。

支持

您可以提问并加入开发讨论：

在POT slack频道
在 POT gitter 频道上
在 POT 邮件列表上

您还可以在Github问题中发布错误报告和功能请求。请确保先阅读我们的指导原则。

参考文献

[1] Bonneel, N., Van De Panne, M., Paris, S., & Heidrich, W. (2011年12月). 利用拉格朗日质量运输进行位移插值. 发表在《ACM图形学交易》（TOG）(第30卷，第6期，页158). ACM.

[2] Cuturi, M. (2013). Sinkhorn distances: Lightspeed computation of optimal transport. 在神经信息处理系统进展中 (pp. 2292-2300).

[3] Benamou, J. D., Carlier, G., Cuturi, M., Nenna, L., & Peyré, G. (2015). 迭代Bregman投影用于正规化运输问题. SIAM科学计算杂志, 37(2), A1111-A1138.

[4] S. Nakhostin, N. Courty, R. Flamary, D. Tuia, T. Corpetti, 有监督的行星解混合与最优传输, 高光谱图像与信号处理：遥感中的演变研讨会 (WHISPERS), 2016.

[5] N. Courty; R. Flamary; D. Tuia; A. Rakotomamonjy, 最优运输用于领域适应, 在 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). 正则化离散最优传输. SIAM Journal on Imaging Sciences, 7(3), 1853-1882.

[7] Rakotomamonjy, A., Flamary, R., & Courty, N. (2015). 广义条件梯度：收敛分析及应用. arXiv 预印本 arXiv:1510.06567.

[8] M. Perrot, N. Courty, R. Flamary, A. Habrard (2016), 离散最优运输的映射估计, 神经信息处理系统 (NIPS).

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

[10] Chizat, L., Peyré, G., Schmitzer, B., & Vialard, F. X. (2016). 不平衡运输问题的缩放算法. arXiv 预印本 arXiv:1607.05816.

[11] Flamary, R., Cuturi, M., Courty, N., & Rakotomamonjy, A. (2016). Wasserstein Discriminant Analysis. arXiv 预印本 arXiv:1608.08063.

[12] Gabriel Peyré, Marco Cuturi, 和 Justin Solomon (2016), Gromov-Wasserstein averaging of kernel and distance matrices 国际机器学习会议 (ICML).

[13] Mémoli, Facundo (2011). Gromov–Wasserstein 距离和对象匹配的度量方法. 计算数学基础 11.4 : 417-487.

[14] Knott, M. 和 Smith, C. S. (1984).关于分布的最优映射, 最优化理论与应用杂志第43卷.

[15] Peyré, G., & Cuturi, M. (2018). 计算最优传输 .

[16] Agueh, M., & Carlier, G. (2011). Wasserstein空间中的重心. SIAM数学分析杂志, 43(2), 904-924.

[17] Blondel, M., Seguy, V., & Rolet, A. (2018). 平滑和稀疏的最优传输. 第二十一届人工智能与统计国际会议（AISTATS）会议论文。

[18] Genevay, A., Cuturi, M., Peyré, G. & Bach, F. (2016) 大规模最优传输的随机优化. 神经信息处理系统进展 (2016).

[19] Seguy, V., Bhushan Damodaran, B., Flamary, R., Courty, N., Rolet, A.& Blondel, M. 大规模最优运输和映射估计. 国际学习表征会议 (2018)

[20] Cuturi, M. 和 Doucet, A. (2014) 快速计算Wasserstein重心。国际机器学习会议

[21] Solomon, J., De Goes, F., Peyré, G., Cuturi, M., Butscher, A., Nguyen, A. & Guibas, L. (2015). 卷积瓦瑟斯坦距离：几何域上的高效最优传输. ACM图形学期刊(TOG), 34(4), 66.

[22] J. Altschuler, J.Weed, P. Rigollet, (2017) 通过Sinkhorn迭代的近线性时间最优传输近似算法, Advances in Neural Information Processing Systems (NIPS) 31

[23] Aude, G., Peyré, G., Cuturi, M., 使用Sinkhorn散度学习生成模型, 第二十一届国际人工智能与统计会议论文集，(AISTATS) 21, 2018

[24] Vayer, T., Chapel, L., Flamary, R., Tavenard, R. 和 Courty, N. (2019). 用于结构化数据的最优传输在图上的应用第36届国际机器学习会议论文集 (ICML).

[25] Frogner C., Zhang C., Mobahi H., Araya-Polo M., Poggio T. (2015). 使用Wasserstein损失进行学习神经信息处理系统进展 (NIPS).

[26] Alaya M. Z., Bérar M., Gasso G., Rakotomamonjy A. (2019). 筛选Sinkhorn算法用于正则化最优传输, Advances in Neural Information Processing Systems 33 (NeurIPS).

[27] Redko I., Courty N., Flamary R., Tuia D. (2019). 目标转移下的多源领域适应的最优传输, 第二十二届人工智能与统计国际会议(AISTATS) 22, 2019.

[28] Caffarelli, L. A., McCann, R. J. (2010). 最优传输和Monge-Ampere障碍问题中的自由边界, 数学年鉴, 673-730.

[29] Chapel, L., Alaya, M., Gasso, G. (2020). 部分最优传输及其在正无标记学习中的应用, 神经信息处理系统进展 (NeurIPS), 2020.

[30] Flamary R., Courty N., Tuia D., Rakotomamonjy A. (2014). 带有拉普拉斯正则化的最优传输：在领域适应和形状匹配中的应用, NIPS 2014 年最优传输与机器学习工作坊 OTML。

[31] Bonneel, Nicolas, et al. 测度的切片和拉东瓦瑟斯坦重心, Journal of Mathematical Imaging and Vision 51.1 (2015): 22-45

[32] Huang, M., Ma S., Lai, L. (2021). 一种用于计算投影鲁棒瓦瑟斯坦距离的黎曼随机坐标下降方法, 第38届国际机器学习会议论文集 (ICML).

[33] Kerdoncuff T., Emonet R., Marc S. 采样的Gromov Wasserstein, 机器学习期刊 (MJL), 2021

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

[35] Deshpande, I., Hu, Y. T., Sun, R., Pyrros, A., Siddiqui, N., Koyejo, S., … & Schwing, A. G. (2019). 最大切片瓦瑟斯坦距离及其在生成对抗网络中的应用. 在IEEE/CVF计算机视觉与模式识别会议论文集中 (pp. 10648-10656).

[36] Liutkus, A., Simsekli, U., Majewski, S., Durmus, A., & Stöter, F. R. (2019年5月). 切片-瓦瑟斯坦流：通过最优运输和扩散进行非参数生成建模. 在国际机器学习会议上 (第4104-4113页). PMLR.

[37] Janati, H., Cuturi, M., Gramfort, A. 去偏置的Sinkhorn重心国际机器学习第37届会议论文集, PMLR 119:4692-4701, 2020

[38] C. Vincent-Cuaz, T. Vayer, R. Flamary, M. Corneli, N. Courty, 在线图字典学习, 国际机器学习大会 (ICML), 2021.

[39] Gozlan, N., Roberto, C., Samson, P. M., & Tetali, P. (2017). 关于一般运输成本及其应用的Kantorovich对偶性. 功能分析杂志, 273(11), 3327-3405.

[40] Forrow, A., Hütter, J. C., Nitzan, M., Rigollet, P., Schiebinger, G., & Weed, J. (2019年4月). 统计最优传输通过分解耦合. 在第22届人工智能与统计国际会议上 (第2454-2465页). PMLR.

[41] Chapel*, L., Flamary*, R., Wu, H., Févotte, C., Gasso, G. (2021). 通过非负惩罚线性回归进行不平衡最优运输神经信息处理系统进展 (NeurIPS), 2020. (两个主要共同作者)

[42] Delon, J., Gozlan, N., 和 Saint-Dizier, A. 不同子空间上存在的概率测度之间的广义Wasserstein重心. arXiv预印本 arXiv:2105.09755, 2021.

[43] Álvarez-Esteban, Pedro C., 等. 在Wasserstein空间中使用不动点方法求重心。数学分析与应用杂志 441.2 (2016): 744-762.

[44] Delon, Julie, Julien Salomon, 和 Andrei Sobolevski. 在圆上快速运输优化Monge成本. SIAM应用数学杂志 70.7 (2010): 2239-2258.

[45] Hundrieser, Shayan, Marcel Klatt, 和 Axel Munk. 圆形最优运输的统计学. 创新应用的方向统计学：纪念弗洛伦斯·南丁格尔的双世纪庆典. 新加坡：施普林格·自然新加坡, 2022. 57-82.

[46] Bonet, C., Berg, P., Courty, N., Septier, F., Drumetz, L., & Pham, M. T. (2023). 球面切片-瓦瑟斯坦. 国际学习表征会议.

[47] Chowdhury, S., & Mémoli, F. (2019). 网络与稳定网络不变之间的Gromov–Wasserstein距离. 信息与推理：IMA期刊, 8(4), 757-787.

[48] Cédric Vincent-Cuaz, Rémi Flamary, Marco Corneli, Titouan Vayer, Nicolas Courty (2022). 半放松Gromov-Wasserstein散度及其在图上的应用. 国际学习表征会议 (ICLR), 2022.

[49] Redko, I., Vayer, T., Flamary, R., 和 Courty, N. (2020). CO-Optimal Transport. 神经信息处理系统进展, 33.

[50] Liu, T., Puigcerver, J., & Blondel, M. (2023). 稀疏约束最优传输. 第十一届国际学习表征会议（ICLR）纪要。

[51] Xu, H., Luo, D., Zha, H., & Duke, L. C. (2019). Gromov-wasserstein学习用于图匹配和节点嵌入. 在国际机器学习会议 (ICML), 2019.

[52] Collas, A., Vayer, T., Flamary, F., & Breloy, A. (2023). 熵瓦瑟斯坦分量分析. ArXiv.

[53] C. Vincent-Cuaz, R. Flamary, M. Corneli, T. Vayer, N. Courty (2022). 基于模板的图神经网络与最优传输距离. 神经信息处理系统进展, 35.

[54] Bécigneul, G., Ganea, O. E., Chen, B., Barzilay, R., & Jaakkola, T. S. (2020). 最优传输图神经网络。

[55] Ronak Mehta, Jeffery Kline, Vishnu Suresh Lokhande, Glenn Fung, & Vikas Singh (2023). 高效的离散多边际最优运输正则化. 在第十一届国际学习表征会议 (ICLR) 上.

[56] Jeffery Kline. d维地球搬运工问题的性质. 离散应用数学, 265: 128–141, 2019.

[57] Delon, J., Desolneux, A., & Salmona, A. (2022). Gromov–Wasserstein 在高斯分布之间的距离. 应用概率杂志, 59(4), 1178-1198.

[58] Paty F-P., d’Aspremont 1., & Cuturi M. (2020). 作为正则化的规则性：最优传输中的光滑且强凸的Brenier势. 在国际人工智能与统计会议，页码1222–1232。PMLR，2020.

[59] 泰勒 A. B. (2017). 凸插值和凸优化的一级方法性能评估。博士论文，洛万大学，洛万-拉-诺夫，比利时，2017。

[60] Feydy, J., Roussillon, P., Trouvé, A., & Gori, P. (2019). 快速且可扩展的大脑轨迹最优传输. 在医学图像计算与计算机辅助干预–MICCAI 2019: 第22届国际会议，深圳，中国，2019年10月13–17日，会议录，第III部分 22 (第636-644页). 施普林格国际出版.

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

[62] H. Van Assel, C. Vincent-Cuaz, T. Vayer, R. Flamary, N. Courty (2023). 使用Gromov-Wasserstein在聚类和降维之间插值. NeurIPS 2023研讨会最优运输与机器学习.

[63] Li, J., Tang, J., Kong, L., Liu, H., Li, J., So, A. M. C., & Blanchet, J. (2022). 图数据中Gromov-Wasserstein松弛的收敛单循环算法. 发表在第十一届国际学习表示大会上。

[64] Ma, X., Chu, X., Wang, Y., Lin, Y., Zhao, J., Ma, L., & Zhu, W. (2023). 融合的Gromov-Wasserstein图混合用于图级分类. 在第三十七届神经信息处理系统会议上.

[65] Scetbon, M., Cuturi, M., & Peyré, G. (2021). 低秩Sinkhorn分解.

[66] Pooladian, Aram-Alexandre, 和 Jonathan Niles-Weed. 最佳运输地图的熵估计. arXiv 预印本 arXiv:2109.12004 (2021).

[67] Scetbon, M., Peyré, G. & Cuturi, M. (2022). 线性时间Gromov-Wasserstein距离使用低秩耦合和成本. 在国际机器学习会议 (ICML), 2022.

[68] Chowdhury, S., Miller, D., & Needham, T. (2021). 量化的Gromov-Wasserstein. ECML PKDD 2021. 施普林格国际出版。

[69] Delon, J., & Desolneux, A. (2020). 一种在高斯混合模型空间中的Wasserstein类型距离. SIAM Journal on Imaging Sciences, 13(2), 936-970.

[70] A. Thual, H. Tran, T. Zemskova, N. Courty, R. Flamary, S. Dehaene & B. Thirion (2022). 将个体大脑与融合不平衡的Gromov-Wasserstein对齐。. 神经信息处理系统 (NeurIPS).

[71] H. Tran, H. Janati, N. Courty, R. Flamary, I. Redko, P. Demetci & R. Singh (2023). 不平衡的共同最优运输. AAAI 人工智能会议。

[72] Thibault Séjourné, François-Xavier Vialard, 和 Gabriel Peyré (2021). 不平衡的 Gromov Wasserstein 距离：锥形公式和放松. 神经信息处理系统 (NeurIPS).

[73] Séjourné, T., Vialard, F. X., & Peyré, G. (2022). 更快的不平衡最优传输：平移不变Sinkhorn和1-D Frank-Wolfe. 在国际人工智能与统计会议上 (pp. 4995-5021). PMLR.