论文标题
不平衡的格罗莫夫·瓦斯堡（Gromov Wasserstein）距离：圆锥形配方和放松
The Unbalanced Gromov Wasserstein Distance: Conic Formulation and Relaxation
论文作者
论文摘要
比较度量度量空间（即具有与众不同性分布的度量空间）是许多机器学习问题的核心。这种度量度量空间之间最流行的距离是gromov-Wasserstein（GW）距离，这是二次分配问题的解决方案。但是，GW距离仅限于与概率分布的度量度量空间的比较。为了减轻这个问题，我们介绍了两个不平衡的Gromov-Wasserstein公式：距离和更易于处理的上限放松。它们均允许比较配备了任意阳性测量的指标空间。第一个公式是基于使用一种新型的二次抗衡性差异的质量保护约束的放松基于质量保护约束的放松。这种差异与熵正规化方法息息相关，该方法很受欢迎，可以解决大规模的最佳运输问题。我们表明，可以使用高度可行且适合GPU的迭代方案有效解决潜在的非凸优化问题。第二个公式是基于圆锥提升的MM空间与异构体之间的距离。最后，我们提供了数值实验，并具有正共同的学习示例和域适应数据，并具有正标记的学习任务，以突出显示不平衡差异的显着特征及其在ML中的潜在应用。
Comparing metric measure spaces (i.e. a metric space endowed with aprobability distribution) is at the heart of many machine learning problems. The most popular distance between such metric measure spaces is theGromov-Wasserstein (GW) distance, which is the solution of a quadratic assignment problem. The GW distance is however limited to the comparison of metric measure spaces endowed with a probability distribution. To alleviate this issue, we introduce two Unbalanced Gromov-Wasserstein formulations: a distance and a more tractable upper-bounding relaxation.They both allow the comparison of metric spaces equipped with arbitrary positive measures up to isometries. The first formulation is a positive and definite divergence based on a relaxation of the mass conservation constraint using a novel type of quadratically-homogeneous divergence. This divergence works hand in hand with the entropic regularization approach which is popular to solve large scale optimal transport problems. We show that the underlying non-convex optimization problem can be efficiently tackled using a highly parallelizable and GPU-friendly iterative scheme. The second formulation is a distance between mm-spaces up to isometries based on a conic lifting. Lastly, we provide numerical experiments onsynthetic examples and domain adaptation data with a Positive-Unlabeled learning task to highlight the salient features of the unbalanced divergence and its potential applications in ML.
