The Balanced-Pairwise-Affinities Feature Transform

The Balanced-Pairwise-Affinities (BPA) feature transform is designed toupgrade the features of a set of input items to facilitate downstream matchingor grouping related tasks. The transformed set encodes a rich representation ofhigh order relations between the input features. A particular min-cost-max-flowfractional matching problem, whose entropy regularized version can beapproximated by an optimal transport (OT) optimization, leads to a transformwhich is efficient, differentiable, equivariant, parameterless andprobabilistically interpretable. While the Sinkhorn OT solver has been adaptedextensively in many contexts, we use it differently by minimizing the costbetween a set of features to $itself$ and using the transport plan's $rows$ asthe new representation. Empirically, the transform is highly effective andflexible in its use and consistently improves networks it is inserted into, ina variety of tasks and training schemes. We demonstrate state-of-the-artresults in few-shot classification, unsupervised image clustering and personre-identification. Code is available at \url{github.com/DanielShalam/BPA}.