PaperlayerView exact revision on arXiv

Source-linked AI summary

Top-k Multiclass SVM

Maksim Lapin, Matthias Hein, Bernt Schiele

arXiv:1511.06683v1stat.MLcs.CVcs.LG

TL;DR

When class counts are large, overlapping classes make top-k evaluation relevant alongside standard zero-one loss. The paper generalizes multiclass SVM with a convex top-k loss and an efficient top-k simplex projection scheme. Across five image-recognition datasets, it reports consistent top-k improvements over baselines.

  • Problem

    With many ambiguous classes, standard zero-one evaluation can penalize mistakes even when the correct label is among k guesses.

    Source: §1 · p. 1, §2 · p. 2

  • Method

    The method generalizes multiclass SVM with a tight convex upper bound on top-k error and optimizes it using efficient top-k simplex projection.

    Source: §1 · p. 1, §2.2 · p. 3, §4 · p. 7

  • Results

    Top-k accuracy improved consistently across five datasets; top-5 accuracy rose +2.6% on Caltech 101 with top-10 SVMα versus top-1 SVMα.

    Source: §7 · p. 13, §6.2 · p. 13

  • Takeaways & Limitations

    For datasets with many classes, optimizing top-k performance is often more appropriate than optimizing only top-1 accuracy.

    Source: §6.2 · p. 13

    The Fenchel-duality treatment is scoped to j-compatible convex functions, with the defining condition evaluated for vectors y where y_j = 0.

    Source: §3.1 · p. 5

Abstract

from arXiv · show

Class ambiguity is typical in image classification problems with a large number of classes. When classes are difficult to discriminate, it makes sense to allow k guesses and evaluate classifiers based on the top-k error instead of the standard zero-one loss. We propose top-k multiclass SVM as a direct method to optimize for top-k performance. Our generalization of the well-known multiclass SVM is based on a tight convex upper bound of the top-k error. We propose a fast optimization scheme based on an efficient projection onto the top-k simplex, which is of its own interest. Experiments on five datasets show consistent improvements in top-k accuracy compared to various baselines.

1 Introduction

With many classes, overlap and multilabel examples complicate discrimination, motivating evaluation that permits k guesses. The paper generalizes multiclass SVM with a tight convex top-k loss and reports consistent top-k gains.

  • As class counts rise, class overlap and multilabel examples motivate adjusting both evaluation metrics and loss functions.Figure 1 illustrates SUN 397 ambiguity with Park, River, Pond, Campus, and Picnic area scenes.Source: §1 · p. 1, Figure 1 · p. 1
  • Top-k multiclass SVM generalizes multiclass SVM to optimize performance when evaluation allows k guesses.The proposed loss is a tight convex upper bound of top-k zero-one loss.Source: §1 · p. 1
  • The top-k hinge loss is a tighter upper bound on top-k zero-one loss than the related ranking-based version.The paper states that its loss is a lower bound on the ranking-based loss.Source: §1 · p. 1
  • An SDCA implementation uses a top-k simplex projection algorithm with O(m log m) complexity for x ∈ R^m.The projection is described as a key optimization ingredient.Source: §1 · p. 1
  • Experiments report consistent top-k error improvements over multiclass SVM, one-vs-all SVM, and other ranking-loss methods.The implementation scales to Places 205, with about 2.5 million examples and 205 classes.Source: §1 · p. 1

2 Top-k Loss in Multiclass Classification

With many ambiguous classes, top-k evaluation allows a classifier several guesses instead of applying the standard zero-one loss. The section extends multiclass SVM with a convex top-k hinge loss and relates it to ranking-based losses.

2.1 Multiclass Support Vector Machine

  • The multiclass SVM learns one linear predictor per class and minimizes risk using a convex upper bound of zero-one loss.The section reviews this model as the starting point for its top-k extension.Source: §2 · p. 2, §2.1 · p. 2

2 Top-k Loss in Multiclass Classification

  • Top-k error evaluates whether the correct label appears among k guesses, addressing ambiguity that makes single-guess classification challenging.The section frames this setting as especially relevant when the number of classes is large.Source: §2 · p. 2

2.2 Top-k Support Vector Machine

  • A direct top-k loss ignores the first k−1 scores and penalizes an error when the correct label falls below rank k, but it is nonconvex.The proposed top-k hinge loss is a convex upper bound on this loss.Source: §2.2 · pp. 2–3

2.2.1 Top-k Simplex and Convex Conjugate of the Top-k Hinge Loss

  • The top-k hinge loss has a conjugate whose effective domain is the top-k simplex, where coordinate upper bounds limit each value’s contribution to the total.The formulation recovers the multiclass SVM when k = 1, and the top-k simplex then reduces to the standard simplex.Source: §2.2.1 · pp. 3–4

2.3 Relation of the Top-k Hinge Loss to Ranking Based Losses

  • The proposed loss is no larger than the ranking-based top-k version, and is a strictly tighter upper bound when the leading score is positive and the kth score is negative.The bounds are equal when the leading score is nonpositive or the kth score is nonnegative.Source: §2.3 · p. 4
  • The section also describes a multiclass-to-binary reduction for evaluating ranking methods, while noting that a recall@k structured-SVM approach does not scale to very large datasets.The recall@k upper bound is not directly comparable because it is not decomposable into an instance-based loss.Source: §2.3 · p. 4

3 Optimization Framework

The framework applies multiclass or top-k SVM losses within an ℓ2-regularized optimization setup. It uses Fenchel duality and Prox-SDCA to optimize the dual variables while maintaining primal variables and a stopping criterion.

3 Optimization Framework

  • The optimization framework accepts either the multiclass SVM loss or the top-k multiclass SVM loss within a general ℓ2-regularized multiclass classification problem.The loss function is left unspecified in the general setup.Source: §3 · p. 5

3.1 Fenchel Duality for ℓ2-Regularized Multiclass Classification Problems

  • Fenchel duality gives primal and dual objectives for ℓ2-regularized multiclass classification, with W = XA^⊤ and W^⊤x_i = AK_i.The framework requires each loss to be compatible with the ground-truth coordinate; the top-k hinge loss satisfies this condition.Source: §3.1 · pp. 5–6

3.2 Optimization of Top-k Multiclass SVM via Prox-SDCA

  • Prox-SDCA updates batches of dual variables to maximize the dual objective, maintains the primal variables, and stops when the relative duality gap falls below ϵ.The method also supports kernelization through W^⊤x_i = AK_i.Source: §3.2 · p. 6

3.2.1 Dual Variables Update

  • The top-k hinge loss's dual-variable optimization is a regularized, biased projection onto the top-k simplex.The update optimizes the dual objective over one example's variable vector while holding the others fixed.Source: §3.2.1 · p. 6

4 Efficient Projection onto the Top-k Simplex

The paper develops an efficient algorithm for Euclidean and biased projections onto the top-k simplex. It handles the coupled coordinate bound and bias by separating projection onto the top-k cone from the case where the sum constraint is active.

4 Efficient Projection onto the Top-k Simplex

  • The top-k simplex projection needs a dedicated algorithm because its coordinate upper bound couples variables, unlike the standard simplex, and existing methods do not apply.The objective may also include a bias term; the method covers general ρ, although the optimization update needs ρ = 1.Source: §4 · p. 7, §4.1 · p. 7

4.1 Continuous Quadratic Knapsack Problem

  • The continuous quadratic knapsack problem covers the projection when the sum constraint is tight, allowing a fixed coordinate upper bound of r/k.In this case the bias term is constant and has no effect on the projection.Source: §4.1 · p. 7

4.2 Projection onto the Top-k Cone

  • For the top-k cone, the algorithm searches feasible partitions after checking special cases, with runtime O(d log(d) + kd).For biased projection, a zero projection is a fallback because the stated sufficient condition is not necessary when ρ > 0.Source: §4.2 · p. 9

4.3 Projection onto the Top-k Simplex

  • When the sum constraint is inactive, projection reduces to the top-k cone problem; when active, it reduces to the continuous quadratic knapsack problem.The simplex projection procedure first tries the knapsack case, then checks its threshold condition and falls back to the cone case if needed.Source: §4.3 · p. 9

5 Optimization of Top-k Usunier Loss

The paper extends the optimization framework to the top-k Usunier loss. Its update uses a biased projection, whose fixed coordinate bounds make the Euclidean projection a continuous quadratic knapsack problem.

5 Optimization of Top-k Usunier Loss

  • The top-k Usunier loss can be optimized with Prox-SDCA using its conjugate loss and a biased projection as the two main ingredients.The conjugate differs from that of the paper's other top-k hinge loss in its effective domain.Source: §5 · p. 10
  • With coordinate upper bounds fixed at 1/k, the Euclidean projection for the Usunier update is a continuous quadratic knapsack problem.The proximal step is biased by an ℓ2 regularizer on the coordinate sum, so the paper extends its projection derivation to handle that term.Source: §5 · p. 10
  • The biased projection first solves the knapsack problem, then uses its threshold to accept that result or search feasible index sets.The knapsack step uses the algorithm of [14].Source: §5 · p. 10

6 Experimental Results

The projection scales linearly with dimension and runs in essentially the same time as the knapsack algorithm. On five image-classification datasets, top-k SVMs consistently improve top-k performance, with top-1 accuracy sometimes decreasing and sometimes increasing.

6.2 Image Classification Experiments

  • Top-k hinge losses consistently improved top-k performance; top-1 accuracy decreased on MIT Indoor 67 but increased on Caltech 101 Silhouettes and SUN 397.Top-10 SVMα improved top-5 accuracy over top-1 SVMα by +2.6% on Caltech 101, +1.2% on MIT Indoor 67, and +2.5% on SUN 397.Source: Table 2 · p. 12, §6.2 · p. 13

6.1 Scaling of the Projection onto the Top-k Simplex

  • Projection runtime scaled linearly with problem dimension and was essentially the same as the knapsack algorithm for k = 1, 5, and 10.The experiment timed 1,000 normally distributed points on a single Intel Xeon 2.20GHz processor.Source: §6.1 · p. 12, Figure 3 · p. 12

6.2 Image Classification Experiments

  • The evaluation covered five image-classification datasets, with results for Places 205 and ImageNet 2012 reported in the supplement.The datasets ranged from 67 to 1,000 classes; the two largest-scale datasets were Places 205 and ImageNet 2012.Source: §6.2 · p. 13
  • Baseline comparisons used cross-validated hyperparameters, and only TopPushOVA among the tried baselines scaled to both Places 205 and ImageNet in time and memory.For Places 205 and ImageNet results, Table 2 reports validation-set accuracy.Source: Table 2 · p. 12, §6.2 · p. 13

7 Conclusion

The conclusion reports that top-k multiclass SVM was scalable and effective on five image-recognition datasets, with consistent top-k performance improvements. It identifies generalizing the top-k hinge loss to ranking losses as future work.

  • The proposed top-k multiclass SVM was scalable and effective on five image-recognition datasets, consistently improving top-k performance.Source: §7 · p. 13
  • Future work could study generalizing the top-k hinge loss to the family of ranking losses.Source: §7 · p. 13
  • Such a generalization could lead to tighter convex upper bounds on the corresponding discrete losses.Source: §7 · p. 13

Related papers

Loading 1511.06683v1…