Top-k Simplex Projection Demo

A multiclass SVM (Crammer and Singer, 2001) learns, for every training example, how hard that example pushes against each wrong class. In the dual problem, these pushes are nonnegative and share a fixed budget r, so for one example they lie in a simplex. Nothing stops a single wrong class from taking the whole budget. That is the right incentive for top-1 error, but not for top-k: an example is still correct if up to k−1 wrong classes beat the true one. The top-k SVM keeps the budget but caps each class at 1/k of the total that the example actually spends:

We call this set the top-k simplex. Every update of the top-k SVM projects a point onto it, so the projection has to be exact and fast. Below, an example has three wrong classes, so its pushes live in 3D. Drop a point v and see where it lands for each k.

(The second view looks straight down the line where all coordinates are equal, so you see v’s position up to its total ⟨1, v⟩. Clicking keeps the total and moves v sideways. The shading shows, for every point you could click, how many classes the projection pushes.)

What the shapes say

For k = 1 the cap is no constraint at all, and Δ₁(r) is the familiar corner of the simplex: one wrong class may take the whole budget. For k = 2 no class may take more than half of the total, so whenever the example pushes at all, at least two classes share the push. The set shrinks to the smaller red pyramid, whose top corners sit halfway along the edges of the blue one. For k = 3 every class gets exactly a third, and the set collapses to the green segment along the diagonal. With m wrong classes, Δ_k has one vertex at the origin and one for every subset of k classes sharing the budget equally, which is Figure 2 in the paper.

The cap is the dual side of averaging. The multiclass SVM charges an example for its single largest margin violation; the top-k hinge loss charges the average of the k largest, which makes it a tighter upper bound on the top-k error. In the dual, that average becomes the rule that no class may take more than 1/k of the push (Proposition 2).

How the projection is computed

The projection solves min ‖v − x‖² + ρ⟨1, x⟩² over x ∈ Δ_k(r). With ρ = 0 this is the Euclidean projection. The algorithm in Section 4 of the paper splits it into two cases, and the last column of the table shows which one applies:

Below budget. First drop the budget and project onto the top-k cone {0 ≤ x_i ≤ ⟨1, x⟩/k}. The solution is v shifted down by a threshold t and clipped to [0, u], where u is the cap. The classes split into three groups: at the cap, in between, and at zero. For a given split, t and u solve a 2×2 linear system, so a search over splits in sorted order finds the answer (Lemma 3). If the sum of the k largest entries of v is not positive, the answer is 0 (Lemma 4). If this solution spends at most r, it is also the projection onto Δ_k(r).
Budget spent. Otherwise the optimum spends exactly r (Lemma 5). Then the cap is the constant r/k, the bias term is a constant too, and what remains is a continuous quadratic knapsack problem: project onto {⟨1, x⟩ = r, 0 ≤ x_i ≤ r/k}. We solve it with the variable fixing algorithm of Kiwiel (2008).

The whole projection takes O(m log m + km) time for m classes, about as fast as projecting onto the plain simplex. This page runs the same two cases every time v moves, with a simple sort-based solver for the knapsack step.

Where the projection is used

Training the top-k SVM. We train with proximal stochastic dual coordinate ascent (Shalev-Shwartz and Zhang, 2013, 2016), which updates one example at a time. The best update of that example’s dual variables is a projection onto Δ_k(1/(λn)) with bias ρ = 1 (Proposition 4), where λ is the regularization constant and n the number of examples. The bias pulls the total push down, which you can see by moving the ρ slider.
The smooth top-k hinge loss. In our CVPR 2016 paper we smoothed the top-k hinge loss. Its value and gradient come from projecting the vector of margins onto Δ_k(γ), where γ is the smoothing parameter, so the budget slider plays the role of γ (Proposition 7). The gradient is that projection divided by γ, so the bars in the table are how hard the smooth loss pushes on each class.

Both are implemented in libsdca, the library I wrote for these papers.

Cap by the total, or by the budget?

There is a second natural way to cap: let no class take more than r/k, a fixed share of the budget rather than of the total actually spent. It comes from the ranking losses of Usunier et al. (2009) and gives a looser top-k hinge loss, which we also optimize exactly in Section 5 of the paper. Switch Cap each class at to r / k and pick A weak push: with the fixed cap, one class may still take most of a small total, because the cap only bites when the example pushes near full strength. Capping by the total enforces the share at every strength, which is why that set is smaller and the loss is a tighter bound.

References

K. Crammer and Y. Singer. On the algorithmic implementation of multiclass kernel-based vector machines. JMLR, 2:265–292, 2001.
K. C. Kiwiel. Variable fixing algorithms for the continuous quadratic knapsack problem. Journal of Optimization Theory and Applications, 136(3):445–458, 2008.
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.
N. Usunier, D. Buffoni, and P. Gallinari. Ranking with ordered weighted pairwise classification. In ICML, 2009.

Cite

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