Optimal transport (OT) is a popular measure to compare probability distributions. However, OT suffers a few drawbacks such as (i) a high complexity for computation, (ii) indefiniteness which limits its applicability to kernel machines. In this work, we consider probability measures supported on a graph metric space and propose a novel Sobolev transport metric. We show that the Sobolev transport metric yields a closed-form formula for fast computation and it is negative definite. We show that the space of probability measures endowed with this transport distance is isometric to a bounded convex set in a Euclidean space with a weighted $\ell_p$ distance. We further exploit the negative definiteness of the Sobolev transport to design positive-definite kernels, and evaluate their performances against other baselines in document classification with word embeddings and in topological data analysis.
翻译:最佳运输(OT)是比较概率分布的流行度量。然而,OT有一些缺点,例如(一) 计算复杂程度高,(二) 无限期限制,限制了其对内核机器的适用性。在这项工作中,我们考虑在图形度空间上支持的概率度量,并提出新的Sobolev运输指标。我们显示,Sobolev运输指标为快速计算生成一种闭式公式,这是否定的。我们显示,这种运输距离所设定的概率度量空间与Euclidean 空间中带有加权 $\ell_p$距离的捆绑式锥形锥形空间的几度量量。我们进一步利用Sobolev运输的负确定性来设计正-定型内核,并对照文件分类中含有字嵌入和表层数据分析的其他基线评估其性能。