瓦斯坦距离测量分布之间的差异，显示出各种类型的自然语言处理（NLP）和计算机视觉（CV）应用的功效。估计Wasserstein距离的挑战之一是，它在计算上很昂贵，并且对于许多分配比较任务而言，它的扩展不是很好。在本文中，我们的目标是通过树 - 瓦斯汀距离（TWD）近似1-wasserstein距离，其中TWD是带有基于树的嵌入的1-wasserstein距离，并且可以在线性时间内相对于节点的数量进行计算在树上。更具体地说，我们提出了一种简单而有效的L1调查方法来学习树中边缘的权重。为此，我们首先证明1-wasserstein近似问题可以使用树上的最短路径距离作为距离近似问题进行表述。然后，我们证明最短的路径距离可以用线性模型表示，并且可以作为基于LASSO的回归问题配方。由于凸公式，我们可以有效地获得全球最佳解决方案。此外，我们提出了这些方法的树形变体。通过实验，我们证明了加权TWD可以准确地近似原始的1-wasserstein距离。

计算分布之间的最佳传输（OT）耦合在机器学习中起着越来越重要的作用。虽然可以将OT问题求解为线性程序，但添加熵平滑项会导致求解器对离群值更快，更强大，可区分且易于并行化。 Sinkhorn固定点算法是这些方法的基石，结果，已经进行了多次尝试以缩短其运行时，例如退火，动量或加速度。本文的前提是，\ textit {initialization}的sindhorn算法受到了相对较少的关注，可能是由于两个先入为主的：由于正规化的ot问题是凸的，因此可能不值得制定量身定制的初始化，因为\ textit {\ textit { }保证工作；其次，由于sindhorn算法在端到端管道中通常是区分的，因此数据依赖性初始化可能会通过展开迭代而获得的偏差梯度估计。我们挑战了这种传统的观点，并表明精心选择的初始化可能会导致巨大的加速，并且不会偏向梯度，这些梯度是通过隐式分化计算的。我们详细介绍如何使用1D或高斯设置中的已知结果从封闭形式或近似OT解决方案中恢复初始化。我们从经验上表明，这些初始化可以在现成的情况下使用，几乎没有调整，并且导致各种OT问题的速度持续加速。

在各种机器学习问题中，包括转移，多任务，连续和元学习在内，衡量不同任务之间的相似性至关重要。最新的测量任务相似性的方法依赖于体系结构：1）依靠预训练的模型，或2）在任务上进行培训网络，并将正向转移用作任务相似性的代理。在本文中，我们利用了最佳运输理论，并定义了一个新颖的任务嵌入监督分类，该分类是模型的，无训练的，并且能够处理（部分）脱节标签集。简而言之，给定带有地面标签的数据集，我们通过多维缩放和串联数据集样品进行嵌入标签，并具有相应的标签嵌入。然后，我们将两个数据集之间的距离定义为其更新样品之间的2-Wasserstein距离。最后，我们利用2-wasserstein嵌入框架将任务嵌入到矢量空间中，在该空间中，嵌入点之间的欧几里得距离近似于任务之间提出的2-wasserstein距离。我们表明，与最佳传输数据集距离（OTDD）等相关方法相比，所提出的嵌入导致任务的比较显着更快。此外，我们通过各种数值实验证明了我们提出的嵌入的有效性，并显示了我们所提出的距离与任务之间的前进和向后转移之间的统计学意义相关性。

作为度量度量空间的有效度量，Gromov-Wasserstein（GW）距离显示了匹配结构化数据（例如点云和图形）问题的潜力。但是，由于其较高的计算复杂性，其实践中的应用受到限制。为了克服这一挑战，我们提出了一种新颖的重要性稀疏方法，称为SPAR-GW，以有效地近似GW距离。特别是，我们的方法没有考虑密集的耦合矩阵，而是利用一种简单但有效的采样策略来构建稀疏的耦合矩阵，并使用几个计算进行更新。我们证明了所提出的SPAR-GW方法适用于GW距离，并以任意地面成本适用于GW距离，并且将复杂性从$ \ Mathcal {o}（n^4）$降低到$ \ Mathcal {o}（n^{2） +\ delta}）$对于任意的小$ \ delta> 0 $。另外，该方法可以扩展到近似GW距离的变体，包括熵GW距离，融合的GW距离和不平衡的GW距离。实验表明，在合成和现实世界任务中，我们的SPAR-GW对最先进的方法的优越性。

Wasserstein barycenter, built on the theory of optimal transport, provides a powerful framework to aggregate probability distributions, and it has increasingly attracted great attention within the machine learning community. However, it suffers from severe computational burden, especially for high dimensional and continuous settings. To this end, we develop a novel continuous approximation method for the Wasserstein barycenters problem given sample access to the input distributions. The basic idea is to introduce a variational distribution as the approximation of the true continuous barycenter, so as to frame the barycenters computation problem as an optimization problem, where parameters of the variational distribution adjust the proxy distribution to be similar to the barycenter. Leveraging the variational distribution, we construct a tractable dual formulation for the regularized Wasserstein barycenter problem with c-cyclical monotonicity, which can be efficiently solved by stochastic optimization. We provide theoretical analysis on convergence and demonstrate the practical effectiveness of our method on real applications of subset posterior aggregation and synthetic data.

比较图形等结构的对象是许多学习任务中涉及的基本操作。为此，基于最优传输（OT）的Gromov-Wasserstein（GW）距离已被证明可以成功处理相关对象的特定性质。更具体地说，通过节点连接关系，GW在图表上运行，视为特定空间上的概率测量。在OT的核心处是质量守恒的想法，这在两个被认为的图表中的所有节点之间施加了耦合。我们在本文中争辩说，这种财产可能对图形字典或分区学习等任务有害，我们通过提出新的半轻松的Gromov-Wasserstein发散来放松它。除了立即计算福利之外，我们讨论其属性，并表明它可以导致有效的图表字典学习算法。我们经验展示其对图形上的复杂任务的相关性，例如分区，聚类和完成。

在数据集中定义样本之间有意义的距离是机器学习中的一个基本问题。最佳传输（OT）在样品之间提高特征（“地面度量”）到几何意义上的距离之间的距离。但是，通常没有直接的地面度量选择。有监督的地面度量学习方法存在，但需要标记的数据。在没有标签的情况下，仅保留临时地面指标。因此，无监督的地面学习是启用数据驱动的OT应用程序的基本问题。在本文中，我们首次通过同时计算样本之间和数据集功能之间的OT距离来提出规范答案。这些距离矩阵自然出现，作为函数映射接地指标的正奇异向量。我们提供标准以确保这些奇异向量的存在和独特性。然后，我们使用随机近似和熵正则化引入可扩展的计算方法以在高维设置中近似它们。最后，我们在单细胞RNA测序数据集上展示了Wasserstein奇异向量。

Optimal Transport (OT) provides a useful geometric framework to estimate the permutation matrix under unsupervised cross-lingual word embedding (CLWE) models that pose the alignment task as a Wasserstein-Procrustes problem. However, linear programming algorithms and approximate OT solvers via Sinkhorn for computing the permutation matrix come with a significant computational burden since they scale cubically and quadratically, respectively, in the input size. This makes it slow and infeasible to compute OT distances exactly for a larger input size, resulting in a poor approximation quality of the permutation matrix and subsequently a less robust learned transfer function or mapper. This paper proposes an unsupervised projection-based CLWE model called quantized Wasserstein Procrustes (qWP). qWP relies on a quantization step of both the source and target monolingual embedding space to estimate the permutation matrix given a cheap sampling procedure. This approach substantially improves the approximation quality of empirical OT solvers given fixed computational cost. We demonstrate that qWP achieves state-of-the-art results on the Bilingual lexicon Induction (BLI) task.

我们考虑人口Wasserstein Barycenter问题，用于随机概率措施支持有限一组点，由在线数据流生成。这导致了复杂的随机优化问题，其中目标是作为作为随机优化问题的解决方案给出的函数的期望。我们采用了问题的结构，并获得了这个问题的凸凹陷的随机鞍点重构。在设置随机概率措施的分布是离散的情况下，我们提出了一种随机优化算法并估计其复杂性。基于内核方法的第二个结果将前一个延伸到随机概率措施的任意分布。此外，这种新算法在许多情况下，与随机近似方法相结合的随机近似方法，具有优于随机近似方法的总复杂性。我们还通过一系列数值实验说明了我们的发展。

Optimal transport (OT) has become exceedingly popular in machine learning, data science, and computer vision. The core assumption in the OT problem is the equal total amount of mass in source and target measures, which limits its application. Optimal Partial Transport (OPT) is a recently proposed solution to this limitation. Similar to the OT problem, the computation of OPT relies on solving a linear programming problem (often in high dimensions), which can become computationally prohibitive. In this paper, we propose an efficient algorithm for calculating the OPT problem between two non-negative measures in one dimension. Next, following the idea of sliced OT distances, we utilize slicing to define the sliced OPT distance. Finally, we demonstrate the computational and accuracy benefits of the sliced OPT-based method in various numerical experiments. In particular, we show an application of our proposed Sliced-OPT in noisy point cloud registration.

Measuring the semantic similarity between two sentences is still an important task. The word mover's distance (WMD) computes the similarity via the optimal alignment between the sets of word embeddings. However, WMD does not utilize word order, making it difficult to distinguish sentences with large overlaps of similar words, even if they are semantically very different. Here, we attempt to improve WMD by incorporating the sentence structure represented by BERT's self-attention matrix (SAM). The proposed method is based on the Fused Gromov-Wasserstein distance, which simultaneously considers the similarity of the word embedding and the SAM for calculating the optimal transport between two sentences. Experiments on paraphrase identification and semantic textual similarity show that the proposed method improves WMD and its variants. Our code is available at https://github.com/ymgw55/WSMD.

Projection robust Wasserstein (PRW) distance, or Wasserstein projection pursuit (WPP), is a robust variant of the Wasserstein distance. Recent work suggests that this quantity is more robust than the standard Wasserstein distance, in particular when comparing probability measures in high-dimensions. However, it is ruled out for practical application because the optimization model is essentially non-convex and non-smooth which makes the computation intractable. Our contribution in this paper is to revisit the original motivation behind WPP/PRW, but take the hard route of showing that, despite its non-convexity and lack of nonsmoothness, and even despite some hardness results proved by~\citet{Niles-2019-Estimation} in a minimax sense, the original formulation for PRW/WPP \textit{can} be efficiently computed in practice using Riemannian optimization, yielding in relevant cases better behavior than its convex relaxation. More specifically, we provide three simple algorithms with solid theoretical guarantee on their complexity bound (one in the appendix), and demonstrate their effectiveness and efficiency by conducing extensive experiments on synthetic and real data. This paper provides a first step into a computational theory of the PRW distance and provides the links between optimal transport and Riemannian optimization.

分发比较在许多机器学习任务中起着核心作用，例如数据分类和生成建模。在这项研究中，我们提出了一种称为希尔伯特曲线投影（HCP）距离的新型度量，以测量具有高鲁棒性和低复杂性的两个概率分布之间的距离。特别是，我们首先使用希尔伯特曲线投射两个高维概率密度，以获得它们之间的耦合，然后根据耦合在原始空间中这两个密度之间的传输距离进行计算。我们表明，HCP距离是一个适当的度量标准，对于绝对连续的概率度量，定义明确。此外，我们证明，经验HCP距离在规律性条件下以不超过$ O（n^{ - 1/2d}）$的速度收敛到其人口。为了抑制差异性的诅咒，我们还使用（可学习的）子空间投影开发了HCP距离的两个变体。合成数据和现实世界数据的实验表明，我们的HCP距离是瓦斯汀距离的有效替代，其复杂性低并克服了切成薄片的瓦斯坦距离的缺点。

近年来，图表匹配中有一系列的研究活动，旨在在两个图表中找到节点的对应关系，并位于许多人工智能应用的核心。然而，匹配具有部分重叠的异构图形仍然是现实世界应用中的具有挑战性的问题。本文提出了第一种实用的学习 - 匹配方法来满足这一挑战。该提出的无监督方法采用新的部分OT范例同时学习运输计划和节点嵌入。在一对一的方式中，整个学习过程被分解成一系列易于解决的子过程，每个子程序仅处理单个类型节点的对齐。还提出了一种搜索传输质量的机制。实验结果表明，所提出的方法优于最先进的图形匹配方法。

The Sinkhorn algorithm (arXiv:1306.0895) is the state-of-the-art to compute approximations of optimal transport distances between discrete probability distributions, making use of an entropically regularized formulation of the problem. The algorithm is guaranteed to converge, no matter its initialization. This lead to little attention being paid to initializing it, and simple starting vectors like the n-dimensional one-vector are common choices. We train a neural network to compute initializations for the algorithm, which significantly outperform standard initializations. The network predicts a potential of the optimal transport dual problem, where training is conducted in an adversarial fashion using a second, generating network. The network is universal in the sense that it is able to generalize to any pair of distributions of fixed dimension. Furthermore, we show that for certain applications the network can be used independently.

聚类是基于它们的相似性对组对象的重要探索性数据分析技术。广泛使用的$ k $ -MEANS聚类方法依赖于一些距离的概念将数据划分为较少数量的组。在欧几里得空间中，$ k $ -Means的基于质心和基于距离的公式相同。在现代机器学习应用中，数据通常是作为概率分布而出现的，并且可以使用最佳运输指标来处理测量值数据。由于瓦斯坦斯坦空间的非负亚历山德罗夫曲率，巴里中心遭受了规律性和非舒适性问题。 Wasserstein Barycenters的特殊行为可能使基于质心的配方无法代表集群内的数据点，而基于距离的$ K $ -MEANS方法及其半决赛计划（SDP）可以恢复真实的方法集群标签。在聚集高斯分布的特殊情况下，我们表明SDP放松的Wasserstein $ k $ - 金钱可以实现精确的恢复，因为这些集群按照$ 2 $ - WASSERSTEIN MERTRIC进行了良好的分离。我们的仿真和真实数据示例还表明，基于距离的$ K $ -Means可以比基于标准的基于质心的$ k $ -Means获得更好的分类性能，用于聚类概率分布和图像。

Weisfeiler-Lehman（WL）测试已广泛应用于图内核，指标和神经网络。但是，它仅考虑图的一致性，从而导致结构信息的描述能力较弱。因此，它限制了应用方法的性能提高。另外，WL检验定义的图之间的相似性和距离是粗略的测量。据我们所知，本文首次阐明了这些事实，并定义了我们称为Wasserstein WL子树（WWLS）距离的指标。我们将WL子树引入节点附近的结构信息，并将其分配给每个节点。然后，我们定义一个基于$ l_1 $ - 应用的树编辑距离（$ l_1 $ - ted）的新图嵌入空间：$ l_1 $ norm of noce noce node node nord noce node fartial farture varter vectors in space上的差异为$ l_1 $ - 节点。我们进一步提出了一种用于图嵌入的快速算法。最后，我们使用Wasserstein距离来反映$ L_1 $的图形级别。 WWL可以捕获传统指标困难的结构的小变化。我们在几个图形分类和度量验证实验中演示了其性能。

测量本体论元素之间的距离是任何匹配解决方案的基本组成部分。依靠离散符号操作的基于字符串的距离指标对于浅层句法匹配是臭名昭著的。在这项研究中，我们探索了跨本体概念嵌入的Wasserstein距离度量。 Wasserstein距离度量目标连续空间可以包含语言，结构和逻辑信息。在我们的探索性研究中，我们使用预先训练的单词嵌入式系统FastText来嵌入本体元素标签。我们研究了Wasserstein距离在测量安大略省（块）之间相似性，发现各个元素之间的匹配以及完善上下文信息的匹配项之间的有效性。与AML和Logmap等领先的系统相比，我们对OAEI会议轨道和MSE基准测试的实验实现了竞争成果。结果表明，适用于最佳运输的有希望的轨迹和Wasserstein距离，以改善基于嵌入的无监督本体匹配。

许多实际问题可以作为两种几何模式之间的对齐方式提出。以前，大量研究集中于计算机视觉领域中2D或3D模式的对齐。最近，高维度的对齐问题在实践中发现了一些新的应用。但是，该研究在算法方面仍然相当有限。据我们所知，大多数现有的方法只是对2D和3D案例的简单扩展，并且经常遭受诸如高计算复杂性之类的问题。在本文中，我们提出了一个有效的框架来压缩高维几何模式。任何现有的比对方法都可以应用于压缩的几何模式，并且可以大大降低时间复杂性。我们的想法的灵感来自观察到高维数据通常具有较低的内在维度。我们的框架是一种“数据依赖性”方法，其复杂性取决于输入数据的内在维度。我们的实验结果表明，与原始模式的结果相比，在压缩模式上运行对齐算法可以达到相似的质量，但是运行时间（包括压缩的时间成本）大大降低。

Computing empirical Wasserstein distance in the independence test is an optimal transport (OT) problem with a special structure. This observation inspires us to study a special type of OT problem and propose a modified Hungarian algorithm to solve it exactly. For an OT problem involving two marginals with $m$ and $n$ atoms ($m\geq n$), respectively, the computational complexity of the proposed algorithm is $O(m^2n)$. Computing the empirical Wasserstein distance in the independence test requires solving this special type of OT problem, where $m=n^2$. The associated computational complexity of the proposed algorithm is $O(n^5)$, while the order of applying the classic Hungarian algorithm is $O(n^6)$. In addition to the aforementioned special type of OT problem, it is shown that the modified Hungarian algorithm could be adopted to solve a wider range of OT problems. Broader applications of the proposed algorithm are discussed -- solving the one-to-many and the many-to-many assignment problems. Numerical experiments are conducted to validate our theoretical results. The experiment results demonstrate that the proposed modified Hungarian algorithm compares favorably with the Hungarian algorithm and the well-known Sinkhorn algorithm.