Sobolev Transport: A Scalable Metric for Probability Measures with Graph Metrics
Sobolev Transport: A Scalable Metric for Probability Measures with Graph Metrics
复制标题
DOI：
--
复制
发表时间：
2022-02
期刊：
影响因子：
--
通讯作者：
Tam Le;Truyen V. Nguyen;Dinh Q. Phung;Viet Anh Nguyen
中科院分区：
文献类型：
--
作者：
Tam Le;Truyen V. Nguyen;Dinh Q. Phung;Viet Anh Nguyen
最优运输（OT）是比较概率分布的一种常用方法。然而，OT具有一些缺点，如（i）计算复杂度高，（ii）不确定性，这限制了其适用于内核机器。在这项工作中，我们认为概率措施支持图度量空间，并提出了一种新的Sobolev运输度量。我们证明了Sobolev输运度规给出了一个用于快速计算的封闭公式，并且它是负定的。我们证明了赋予这种运输距离的概率测度空间是等距的一个有界凸集在一个加权$\ell_p$距离的欧氏空间。我们进一步利用Sobolev运输的负定性设计正定内核，并评估其性能对其他基线的文档分类与词嵌入和拓扑数据分析。
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.