arXiv Analytics

Sign in

arXiv:1905.11885 [cs.LG]AbstractReferencesReviewsResources

Differentiable Sorting using Optimal Transport:The Sinkhorn CDF and Quantile Operator

Marco Cuturi, Olivier Teboul, Jean-Philippe Vert

Published 2019-05-28Version 1

Sorting an array is a fundamental routine in machine learning, one that is used to compute rank-based statistics, cumulative distribution functions (CDFs), quantiles, or to select closest neighbors and labels. The sorting function is however piece-wise constant (the sorting permutation of a vector does not change if the entries of that vector are infinitesimally perturbed) and therefore has no gradient information to back-propagate. We propose a framework to sort elements that is algorithmically differentiable. We leverage the fact that sorting can be seen as a particular instance of the optimal transport (OT) problem on $\mathbb{R}$, from input values to a predefined array of sorted values (e.g. $1,2,\dots,n$ if the input array has $n$ elements). Building upon this link , we propose generalized CDFs and quantile operators by varying the size and weights of the target presorted array. Because this amounts to using the so-called Kantorovich formulation of OT, we call these quantities K-sorts, K-CDFs and K-quantiles. We recover differentiable algorithms by adding to the OT problem an entropic regularization, and approximate it using a few Sinkhorn iterations. We call these operators S-sorts, S-CDFs and S-quantiles, and use them in various learning settings: we benchmark them against the recently proposed neuralsort [Grover et al. 2019], propose applications to quantile regression and introduce differentiable formulations of the top-k accuracy that deliver state-of-the art performance.

Related articles: Most relevant | Search more
arXiv:1906.09218 [cs.LG] (Published 2019-06-21)
FlipTest: Fairness Auditing via Optimal Transport
arXiv:1903.03850 [cs.LG] (Published 2019-03-09)
Stochastic Incremental Algorithms for Optimal Transport with SON Regularizer
arXiv:1911.02053 [cs.LG] (Published 2019-11-05)
Alleviating Label Switching with Optimal Transport