Top-k Losses Demo

When a model is graded on its top k guesses, it only needs the true class somewhere in its top k. Softmax does not know that: it keeps pushing the true class towards first place. The top-k losses are built for the metric you actually report: they stop pushing once the job is done and spend the model's capacity where it counts. Pick two losses, then see how they behave on one example and on a small problem with a linear model.

1. One example: where does each loss push?

Before any model or dataset, it helps to see what each loss asks for. Take one example whose true class is orange, with two wrong classes, blue and green. A loss only looks at how far each wrong class scores above the true one, so every possible state of this example is a point on the plane below. Lines are loss contours, and the shaded corner is a top-2 error. Here the three scores are free to move, and gradient descent moves them downhill.

With free scores, every loss eventually puts orange first. What sets the losses apart is the direction of the push and when a loss considers the job done, and that is exactly what decides the outcome in section 2.

(Click or drag on either plot to drop your own start. The bars show how hard the loss pushes each wrong class down right now; the red arrow is the same push drawn on the plane.)

What this shows. Softmax always pushes every class that scores near or above orange, and pushes hardest on the strongest rival, because it only stops when orange is first by a wide margin. Truncated top-2 entropy pushes only the weaker rival: once orange beats one of the two, it is in the top 2, and the loss ignores the other. With one example, both end up fine. But in a real model, scores are not free. One set of weights scores every example, so a push that helps one example moves the scores of all the others. A loss that keeps pushing after the job is done spends the model's limited flexibility on something the metric does not reward. The next section shows where that bites.

2. Many examples, one linear model

The data

Each example is a point on a circle. The circle is split into five segments, and each segment has its own mix of labels. Every segment gets the same number of points, so the long bottom segment S4 is sparser than the rest. Segments S1, S2, and S5 are pure. S3 and S4 are ambiguous: an example there might carry either label, so even a perfect classifier cannot always be right on top-1. A top-2 guess can be.

How a linear model scores the circle

Segment	Arc	Labels	Best top-2 guess
S1	1/7	100% blue	blue + any
S2	1/7	100% orange	orange + any
S3	1/7	50% green, 40% orange, 10% blue	green + orange (90%)
S4	3/7	70% blue, 30% orange	blue + orange
S5	1/7	100% green	green + any

The model scores class j at a point x on the circle as ⟨w_j, x⟩. Each weight vector w_j is an arrow in the same plane. To score a direction, drop each arrow's shadow onto it: the class whose shadow reaches furthest is the first guess, the next one the second guess.

The ring around the circle is the data from above: in each segment, the thickness of a color is the share of that label. Inside the circle, the stripes are the model's second guess in each direction. Switch on 1st guess to shade in the first guess as well, and Missed by top 2 to fade the part of the ring that the top 2 misses and give it a red edge.

(Drag the arrow tips. Can you keep orange first in S2 and also in the top 2 across S4? Click anywhere on the circle to pin a direction and read off all three scores, then drag an arrow and watch them change. The marker on the circle turns red when the top 2 misses some of the labels there.)

Three arrows give each class one contiguous arc as first guess, and the second guesses are just as rigid. You cannot cover every segment. Something has to give, and the loss decides what.

Training the model with each loss

Now train the arrows with the two losses picked at the top, from the same start. Faint lines trace where the arrow tips travel. The strip under each circle is the same picture cut open at 0° and laid flat.

(Press Play. Drag an arrow tip to choose where training starts. Hover or click to inspect a direction.)

(In the strip, a linear score on a circle is a cosine, so each class gets one smooth bump. A training point shrinks when its loss stops pulling on the model, on the circle too if training points are switched on.)

(Accuracy is computed numerically against the data distribution, so it is a test score, not a training score.)

The losses

Let a_j = f_j(x) − f_y(x) be how far class j scores above the true class y. These are the two axes of the first plot.

Softmax (cross-entropy). log(1 + Σ_j≠y exp a_j). Every wrong class with a high score costs something, even when the true class is safely in the top k.
Multiclass SVM (Crammer and Singer, 2001). max(0, max_j≠y (1 + a_j)). Zero once the true class beats every other class by a margin of 1, and it only ever pushes the worst offender.
Top-k SVM (our NeurIPS 2015 paper). The hinge on the average of the k largest entries of [j≠y] + a_j, where the true class contributes a 0. It upper-bounds the top-k error more tightly than the multiclass SVM and spreads its push over k classes, each at most 1/k. With three classes and k = 2 its zero region is the same as the SVM's.
Top-k entropy (our CVPR 2016 paper). The convex conjugate of softmax, with its domain restricted to the top-k simplex. This caps how hard a single wrong class can be pushed. It has no closed form, but an O(km) algorithm computes it exactly, and this page runs that algorithm. With three classes and k = 2 the top-k simplex shrinks to a single ray, so the loss only sees the average gap and pushes both wrong classes equally: its contours in the first plot are straight lines.
Truncated top-k entropy (also from the CVPR 2016 paper). Softmax with the k−1 highest-scoring wrong classes left out of the sum. It no longer cares which classes come first, only that the true class makes the top k. That focus is what makes it nonconvex: in the first plot its contours bend around a corner.

With k = 1, all three top-k losses reduce to their top-1 versions: multiclass SVM or softmax.

The circle problem

This is the synthetic example from Section 4 of our CVPR 2016 paper. The interval [0, 7] is split into five segments: four of length 1 and one of length 3. Every segment gets the same number of points, drawn uniformly within it, and each segment has its own class probabilities, shown in the ring. Then the position is wrapped onto the unit circle, and the model is linear in the two coordinates, with no bias: f_j(x) = ⟨w_j, x⟩, so each weight vector w_j is an arrow in the same plane as the data. All losses minimize the same regularized objective, one over n times the sum of losses plus λ/2 ‖W‖², with full-batch Adam (Kingma and Ba, 2015) from the same start.

The convex losses reach the same solution wherever you drop the arrows. The truncated loss is not convex, so its start matters. As in the paper, this page starts it from the softmax solution and lets it improve from there. Clear the warm-start box and try the trap preset to see why that helps.

What to take away

On the default sample, softmax reaches 84.9% top-2 accuracy and truncated top-2 entropy 95.2%, close to the best possible 98%. Softmax ranks orange last on part of S4 and loses its 30% share there, because it is busy making orange first where orange is certain. The truncated loss does not chase top-1 accuracy, which the metric does not reward, and keeps orange in the top 2 almost everywhere.

The circle is small on purpose, but the situation it captures is common: many classes, ambiguous labels, a model that cannot fit everything, and a metric that forgives the first k−1 misses. That is when it pays to train for the metric you report. On 11 datasets in the paper, from text classification to scene recognition, the smooth top-k SVM and top-k entropy improved the top-k accuracy they targeted, and fine-tuning a scene network with the top-5 SVM gave the best top-1 to top-5 accuracy of all the losses we tried on Places 205.

The convex losses here, including top-k entropy, are implemented in libsdca, the library I wrote for these papers, which trains them with stochastic dual coordinate ascent (Shalev-Shwartz and Zhang, 2013, 2016).

References

K. Crammer and Y. Singer. On the algorithmic implementation of multiclass kernel-based vector machines. JMLR, 2:265–292, 2001.
D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
M. Lapin, M. Hein, and B. Schiele. Top-k multiclass SVM. In NeurIPS, 2015.
M. Lapin, M. Hein, and B. Schiele. Loss functions for top-k error: Analysis and insights. In CVPR, 2016.
S. Shalev-Shwartz and T. Zhang. Stochastic dual coordinate ascent methods for regularized loss minimization. JMLR, 14:567–599, 2013.
S. Shalev-Shwartz and T. Zhang. Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization. Mathematical Programming, 155:105–145, 2016.

Cite

@inproceedings{lapin2015topk,
  title     = {Top-k Multiclass {SVM}},
  author    = {Lapin, Maksim and Hein, Matthias and Schiele, Bernt},
  booktitle = {NeurIPS},
  year      = {2015}
}

@inproceedings{lapin2016loss,
  title     = {Loss Functions for Top-k Error: Analysis and Insights},
  author    = {Lapin, Maksim and Hein, Matthias and Schiele, Bernt},
  booktitle = {CVPR},
  year      = {2016}
}