Differentiable Top-k with Optimal Transport

Yujia Xie, Hanjun Dai, Minshuo Chen, Bo Dai, Tuo Zhao, Hongyuan Zha, Wei Wei, Tomas PfisterNeurIPS 2020 · OpenReview

In the world of deep learning, gradients are king. If you cannot compute a gradient for a function, you cannot easily train a neural network to use it in an end-to-end manner. This creates a major roadblock for one of the most common operations in computer science: the top-$k$ operation. Whether you are picking the $k$ nearest neighbors in a classifier or the $k$ most likely words in a translation beam search, the act of "sorting and picking" is inherently discrete and non-differentiable.

A team of researchers recently tackled this head-on in their paper, "Differentiable Top-k with Optimal Transport." They introduce a novel operator called SOFT that turns this discrete bottleneck into a smooth, differentiable layer.

TL;DR

The authors propose SOFT, a differentiable version of the top-$k$ operation based on Entropic Optimal Transport. By smoothing the selection process, they enable end-to-end training for models that rely on $k$-nearest neighbors or beam search, leading to significant performance gains in image classification and machine translation.

What Problem Does This Paper Address?

The standard top-$k$ operation (finding the $k$ largest or smallest elements in a set) is a "hard" operation. If you change an input score slightly, the output (the set of top indices) doesn't change at all—until it suddenly jumps when one element overtakes another. Mathematically, this means the gradient is zero almost everywhere and undefined at the points where elements swap.

Comparison of the original discontinuous top-k operator and the proposed smoothed SOFT top-k operator.

Because of this discontinuity, researchers usually have to use "two-stage" training. For example, in a $k$-Nearest Neighbors (kNN) system, you might train a feature extractor using a standard loss function first, and then plug those features into a kNN algorithm later. This creates a misalignment: the features weren't actually optimized to work well with the kNN logic. The same issue plagues "beam search" in natural language processing, where models are trained on single-word predictions but evaluated on multi-word sequences.

Methods

The authors' core innovation is re-imagining top-$k$ as an Optimal Transport (OT) problem.

  1. Top-$k$ as Mass Moving: Imagine you have $n$ input scores. You want to move "mass" from these scores into two bins: a "top-$k$" bin (which holds $k/n$ of the total mass) and a "rest" bin. The "cost" of moving a score to the top-$k$ bin is lower if the score is larger.
  2. Entropic Smoothing: To make this transport plan differentiable, they add an entropy regularization term. This turns the "hard" assignment into a "soft" one, where every input has a probability of belonging to the top-$k$ set.
  3. The SOFT Operator: They call this the Scalable Optimal transport-based diFferenTiable (SOFT) top-$k$ operator.
  4. Efficiency: They solve the transport problem using the Sinkhorn algorithm, which is fast and hardware-friendly. To keep memory usage low during training, they use implicit differentiation, allowing them to compute gradients without storing every intermediate step of the Sinkhorn loop.

Key Insights and Applications

The researchers evaluated SOFT across two distinct domains to prove its versatility:

  • End-to-End kNN (Image Classification): By making top-$k$ differentiable, they can train a neural network specifically to produce features that cluster well for a kNN classifier. The network "knows" it will be evaluated by looking at neighbors, so it learns more robust representations. On CIFAR-10, the SOFT-kNN approach achieved 92.6% accuracy, outperforming standard CNNs trained with cross-entropy (91.3%) and other differentiable ranking methods like NeuralSort (90.7%).
  • Solving Exposure Bias (Machine Translation): In translation, "exposure bias" occurs because models are trained to predict the next word given the ground truth previous words, but at test time, they must predict given their own (potentially wrong) previous words. SOFT allows the model to be trained through the beam search process, exposing it to its own search behavior during training. In the WMT’14 English-French task, integrating SOFT into the beam search training improved the BLEU score from a baseline of 35.38 to 36.27.

Limitations and Future Work

While powerful, the SOFT operator introduces new considerations for practitioners:

  • The Bias-Smoothing Trade-off: There is a hyperparameter ($\epsilon$) that controls how "soft" the operator is. If it's too high, the approximation is poor (high bias); if it's too low, the gradients become unstable (vanishing/exploding). Finding the "sweet spot" is crucial for stable training.
Effect of varying the smoothing parameter epsilon on the SOFT operator's output distribution.
  • Search Space in Beam Search: While SOFT makes beam search differentiable, the search space for translation is still massive. The authors had to use a "hybrid" training approach (mixing standard training with SOFT training) to keep the process stable.
  • Broader Applications: The authors suggest this could be applied to other areas like information retrieval, point cloud processing, and any domain where "picking the best" is a core part of the logic. Because the algorithm maintains a complexity of $O(n)$, it remains practical for large-scale sets.

Summary updated

Abstract

Finding the k largest or smallest elements from a collection of scores, i.e., top-k operation, is an important model component widely used in information retrieval, machine learning, and data mining. However, if the top-k operation is implemented in an algorithmic way, e.g., using bubble algorithm, the resulted model cannot be trained in an end-to-end way using prevalent gradient descent algorithms. This is because these implementations typically involve swapping indices, whose gradient cannot be computed. Moreover, the corresponding mapping from the input scores to the indicator vector of whether this element belongs to the top-k set is essentially discontinuous. To address the issue, we propose a smoothed approximation, namely SOFT (Scalable Optimal transport-based diFferenTiable) top-k operator. Specifically, our SOFT top-k operator approximates the output of top-k operation as the solution of an Entropic Optimal Transport (EOT) problem. The gradient of the SOFT operator can then be efficiently approximated based on the optimality conditions of EOT problem. We then apply the proposed operator to k-nearest neighbors algorithm and beam search algorithm. The numerical experiment demonstrates their achieve improved performance.
BibTeX
@inproceedings{xie2020differentiable,
  author = {Yujia Xie and Hanjun Dai and Minshuo Chen and Bo Dai and Tuo Zhao and Hongyuan Zha and Wei Wei and Tomas Pfister},
  title = {{Differentiable Top-k with Optimal Transport}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=oNjSMIKyUa},
}
Figure