Entropy Partial Transport with Tree Metrics: Theory and Practice

• URL: http://arxiv.org/abs/2101.09756v1
• Date: Sun, 24 Jan 2021 17:04:24 GMT
• Title: Entropy Partial Transport with Tree Metrics: Theory and Practice
• Authors: Tam Le, Truyen Nguyen
• Abstract summary: We consider an textitentropy partial transport (EPT) problem for nonnegative measures on a tree having different masses. We propose a novel regularization for EPT which admits fast computation and negative definiteness. We empirically demonstrate that our regularization also provides effective approximations.
• Score: 5.025654873456756
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Leveraging Nested MLMC for Sequential Neural Posterior Estimation with Intractable Likelihoods [0.8287206589886881]
  SNPE techniques are proposed for dealing with simulation-based models with intractable likelihoods. In this paper, we propose a nested APT method to estimate the involved nested expectation. Since the nested estimators for the loss function and its gradient are biased, we make use of unbiased multi-level Monte Carlo (MLMC) estimators.
  arXiv  Detail & Related papers  (2024-01-30T06:29:41Z)
• Optimal Transport for Measures with Noisy Tree Metric [29.950797721275574]
  We study optimal transport problem for probability measures supported on a tree metric space. In general, this approach is hard to compute, even for measures supported in one space. We show that the robust OT satisfies the metric property and is negative definite.
  arXiv  Detail & Related papers  (2023-10-20T16:56:08Z)
• Lower Complexity Adaptation for Empirical Entropic Optimal Transport [0.0]
  Entropic optimal transport (EOT) presents an effective and computationally viable alternative to unregularized optimal transport (OT) We derive novel statistical bounds for empirical plug-in estimators of the EOT cost. Our techniques employ empirical process theory and rely on a dual formulation of EOT over a single function class.
  arXiv  Detail & Related papers  (2023-06-23T16:06:13Z)
• Unbalanced Optimal Transport meets Sliced-Wasserstein [11.44982599214965]
  We propose two new loss functions based on the idea of slicing unbalanced OT, and study their induced topology and statistical properties. We show that the resulting methodology is modular as it encompasses and extends prior related work.
  arXiv  Detail & Related papers  (2023-06-12T15:15:00Z)
• Joint Metrics Matter: A Better Standard for Trajectory Forecasting [67.1375677218281]
  Multi-modal trajectory forecasting methods evaluate using single-agent metrics (marginal metrics) Only focusing on marginal metrics can lead to unnatural predictions, such as colliding trajectories or diverging trajectories for people who are clearly walking together as a group. We present the first comprehensive evaluation of state-of-the-art trajectory forecasting methods with respect to multi-agent metrics (joint metrics): JADE, JFDE, and collision rate.
  arXiv  Detail & Related papers  (2023-05-10T16:27:55Z)
• Robust computation of optimal transport by $\beta$-potential regularization [79.24513412588745]
  Optimal transport (OT) has become a widely used tool in the machine learning field to measure the discrepancy between probability distributions. We propose regularizing OT with the beta-potential term associated with the so-called $beta$-divergence. We experimentally demonstrate that the transport matrix computed with our algorithm helps estimate a probability distribution robustly even in the presence of outliers.
  arXiv  Detail & Related papers  (2022-12-26T18:37:28Z)
• Learning to Estimate Without Bias [57.82628598276623]
  Gauss theorem states that the weighted least squares estimator is a linear minimum variance unbiased estimation (MVUE) in linear models. In this paper, we take a first step towards extending this result to non linear settings via deep learning with bias constraints. A second motivation to BCE is in applications where multiple estimates of the same unknown are averaged for improved performance.
  arXiv  Detail & Related papers  (2021-10-24T10:23:51Z)
• Efficient Semi-Implicit Variational Inference [65.07058307271329]
  We propose an efficient and scalable semi-implicit extrapolational (SIVI) Our method maps SIVI's evidence to a rigorous inference of lower gradient values.
  arXiv  Detail & Related papers  (2021-01-15T11:39:09Z)
• Scaling Equilibrium Propagation to Deep ConvNets by Drastically Reducing its Gradient Estimator Bias [65.13042449121411]
  In practice, training a network with the gradient estimates provided by EP does not scale to visual tasks harder than MNIST. We show that a bias in the gradient estimate of EP, inherent in the use of finite nudging, is responsible for this phenomenon. We apply these techniques to train an architecture with asymmetric forward and backward connections, yielding a 13.2% test error.
  arXiv  Detail & Related papers  (2020-06-06T09:36:07Z)
• Targeted free energy estimation via learned mappings [66.20146549150475]
  Free energy perturbation (FEP) was proposed by Zwanzig more than six decades ago as a method to estimate free energy differences. FEP suffers from a severe limitation: the requirement of sufficient overlap between distributions. One strategy to mitigate this problem, called Targeted Free Energy Perturbation, uses a high-dimensional mapping in configuration space to increase overlap.
  arXiv  Detail & Related papers  (2020-02-12T11:10:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.