Entropy Partial Transport with Tree Metrics: Theory and Practice

Abstract

Optimal transport (OT) theory provides powerful tools to compare probability measures. However, OT is limited to nonnegative measures having the same mass, and suffers serious drawbacks about its computation and statistics. This leads to several proposals of regularized variants of OT in the recent literature. In this work, we consider an \textit{entropy partial transport} (EPT) problem for nonnegative measures on a tree having different masses. The EPT is shown to be equivalent to a standard complete OT problem on a one-node extended tree. We derive its dual formulation, then leverage this to propose a novel regularization for EPT which admits fast computation and negative definiteness. To our knowledge, the proposed regularized EPT is the first approach that yields a \textit{closed-form} solution among available variants of unbalanced OT. For practical applications without priori knowledge about the tree structure for measures, we propose tree-sliced variants of the regularized EPT, computed by averaging the regularized EPT between these measures using random tree metrics, built adaptively from support data points. Exploiting the negative definiteness of our regularized EPT, we introduce a positive definite kernel, and evaluate it against other baselines on benchmark tasks such as document classification with word embedding and topological data analysis. In addition, we empirically demonstrate that our regularization also provides effective approximations.

arXiv commentTo appear in AISTATS 2021

References in corpus (9)

• Distributed Representations of Words and Phrases and their Compositionality
• Learning with a Wasserstein Loss
• Generalized Wasserstein distance and its application to transport equations with source
• Imaging with Kantorovich-Rubinstein discrepancy
• Unnormalized Optimal Transport
• Persistence Fisher Kernel: A Riemannian Manifold Kernel for Persistence Diagrams
• Large Scale computation of Means and Clusters for Persistence Diagrams using Optimal Transport
• Parallel Unbalanced Optimal Transport Regularization for Large Scale Imaging Problems
• Duality and quotient spaces of generalized Wasserstein spaces

Cited by in corpus (3)

• Optimal Transport Kernels for Sequential and Parallel Neural Architecture Search
• Fixed Support Tree-Sliced Wasserstein Barycenter
• On Multimarginal Partial Optimal Transport: Equivalent Forms and Computational Complexity