PaperlayerView exact revision on arXiv

Source-linked AI summary

Smooth Loss Functions for Deep Top-k Classification

Leonard Berrada, Andrew Zisserman, M. Pawan Kumar

arXiv:1802.07595v1cs.LG

TL;DR

Ambiguous, limited, or noisy labels make top-k classification important, while cross-entropy can overfit in those settings despite its strong large-data performance. The paper introduces smoothed margin-based top-k losses with efficient computation, and reports greater robustness than cross-entropy when data are limited or noisy.

  • Problem

    Top-k classification must handle label ambiguity, while cross-entropy can overfit on limited data or noisy labels despite its strong large-data performance.

    Source: §1 · p. 1

  • Method

    The paper introduces temperature-smoothed margin-based top-k losses and an O(kn)-time algorithm for computing the loss and gradient.

    Source: §1 · pp. 1–2

  • Results

    The smooth top-5 loss is more robust to noise and overfitting than cross-entropy with limited training data; on noisy CIFAR-100, L5,1 improves top-5 testing accuracy by over 5% when p = 1.

    Source: §1 · p. 2, §5.1 · p. 9, §6 · p. 10

  • Takeaways & Limitations

    The experiments indicate that non-sparse gradients are essential for top-k losses to work well with deep neural networks.

    Source: §6 · p. 10

    The backward computation can be numerically unstable, so the proposed approximation is used to stabilize it with smaller overhead.

    Source: §4.3 · p. 8

Abstract

from arXiv · show

The top-k error is a common measure of performance in machine learning and computer vision. In practice, top-k classification is typically performed with deep neural networks trained with the cross-entropy loss. Theoretical results indeed suggest that cross-entropy is an optimal learning objective for such a task in the limit of infinite data. In the context of limited and noisy data however, the use of a loss function that is specifically designed for top-k classification can bring significant improvements. Our empirical evidence suggests that the loss function must be smooth and have non-sparse gradients in order to work well with deep neural networks. Consequently, we introduce a family of smoothed loss functions that are suited to top-k optimization via deep learning. The widely used cross-entropy is a special case of our family. Evaluating our smooth loss functions is computationally challenging: a na\"ive algorithm would require $\mathcal{O}(\binom{n}{k})$ operations, where n is the number of classes. Thanks to a connection to polynomial algebra and a divide-and-conquer approach, we provide an algorithm with a time complexity of $\mathcal{O}(k n)$. Furthermore, we present a novel approximation to obtain fast and stable algorithms on GPUs with single floating point precision. We compare the performance of the cross-entropy loss and our margin-based losses in various regimes of noise and data size, for the predominant use case of k=5. Our investigation reveals that our loss is more robust to noise and overfitting than cross-entropy.

1 INTRODUCTION

Label ambiguity makes single-label classification inadequate in some settings, while cross-entropy’s strong top-k performance on large, correctly labeled datasets does not prevent overfitting with limited or noisy labels. The paper introduces smoothed margin-based top-k losses and efficient computation, reporting greater robustness in those challenging regimes.

1 INTRODUCTION

  • When labels are ambiguous, top-k error counts a prediction as correct if any of its k labels matches the ground truth.ImageNet examples include incorrect labels and images for which several categories could be valid.Source: §1 · p. 1, Figure 1 · p. 2
  • Cross-entropy performs well on top-5 with large, correctly labeled datasets, but can overfit when data are limited or labels are noisy.Its top-k calibration is an asymptotic property.Source: §1 · p. 1
  • The proposed top-k losses create a margin between correct top-k predictions and incorrect ones, then smooth the loss with a temperature parameter.The authors associate poor deep-network performance of traditional top-k losses with nonsmoothness and sparse backpropagation derivatives.Source: §1 · pp. 1–2
  • The method computes the smoothed loss in O(kn) time and outperforms cross-entropy with noisy labels or limited data, with the gap shrinking on large, correctly labeled data.The paper also introduces an approximation to address backward-pass numerical instability.Source: §1 · p. 2

2 RELATED WORK

Prior top-k losses were studied mainly with shallow models, linear models, or fine-tuned deep networks; this paper situates its work among those approaches and related smoothing methods. Its focus is training deep networks from random initialization with smoothed top-k losses.

2 RELATED WORK

  • Earlier top-k loss work addressed shallow models using convex surrogates, selected largest individual losses, truncated reweighting, or ensembles of top-k classifiers.The cited approaches are Lapin et al. (2016), Fan et al. (2017), Chang et al. (2017), and Yan et al. (2017), respectively.Source: §2 · p. 2
  • Lapin et al. (2017) established cross-entropy’s top-k calibration, but their experiments used linear models or fine-tuned pretrained networks rather than random initialization.The paper aims to extend analysis to training deep networks from random initialization.Source: §2 · p. 2
  • Prior smoothing work spans optimization, binary SVMs, structured prediction, and top-k surrogates, including Moreau-Yosida regularization by Lapin et al. (2017).Beck & Teboulle (2012), Lee & Mangasarian (2001), and Schwing et al. (2012) are also cited.Source: §2 · p. 2
  • Deep-network smoothing has been used to speed optimization or improve generalization, whereas this work argues it is necessary for its top-k loss to work well.The authors suggest this insight may also inform loss design for tasks beyond top-k error minimization.Source: §2 · p. 3

3 TOP-K SVM

The section builds from the multi-class SVM surrogate to a top-k margin loss, then smooths it to address deep-network optimization. The smoothed objective has non-sparse gradients, recovers cross-entropy as a special case, and its training behavior depends on temperature.

3.1 BACKGROUND: MULTI-CLASS SVM

  • For k = 1, Crammer & Singer (2001)'s surrogate upper-bounds the discontinuous classification loss and penalizes margin shortfalls linearly; the margin can be rescaled.The margin is measured between the ground-truth score and the highest-scoring other class.Source: §3.1 · p. 3

3.2 TOP-K CLASSIFICATION

  • The top-k SVM surrogate margins the ground-truth score against the kth-largest score, while its non-smooth form has at most two nonzero derivatives and often trains deep nets poorly.The loss disregards the values of the other k − 1 largest scores.Source: §3.2 · p. 4

3.3 SMOOTH SURROGATE LOSS

  • For τ > 0, Lk,τ is infinitely differentiable with non-sparse gradients, approaches lk as τ → 0+, and is a scaled upper bound on Λk.Lk,τ is an upper bound on lk only when k = 1.Source: §3.3 · p. 5
  • With margin scale α → 0+ and τ = 1, L1,1 becomes exactly cross-entropy, generalizing it across k, temperature, and margin scale.The paper keeps α = 1 for simplicity.Source: §3.3 · p. 5
  • At τ = 0.01 or larger, DenseNet 40-12 trains to good accuracy; with τ too small, it fails to reach a good critical point.High temperatures also yield non-sparse gradients informative about more labels.Source: §3.3 · p. 5, Figure 2 · p. 5

4 COMPUTATIONAL CHALLENGES AND EFFICIENT ALGORITHMS

The paper addresses the cost and numerical challenges of computing the smoothed top-k loss and its gradients. It uses polynomial structure for an O(kn) forward algorithm and reuses forward-pass results to accelerate backward computation.

4.1 CHALLENGE

  • Naïvely evaluating the smooth loss requires summing over label combinations, while practical GPU training also requires numerical stability in single precision.The paper therefore seeks algorithms that meet both computational and numerical requirements.Source: §4.1 · p. 6

4.2 FORWARD COMPUTATION

  • A divide-and-conquer polynomial algorithm computes the required symmetric-polynomial terms in O(kn), with parallelizable operations that scale well on GPUs.It exploits the relationship between elementary symmetric polynomials and polynomial coefficients, computing only the first k coefficients needed when k is small relative to n.Source: §4.1 · p. 6, §4.2 · p. 7

4.3 BACKWARD COMPUTATION

  • The backward pass reuses forward-pass results and avoids memory allocations, making it one to two orders of magnitude faster and negligible relative to the forward pass.The recursive derivative computation still has numerical instabilities; the paper proposes an approximation that stabilizes it with significantly smaller overhead than repeated forward passes.Source: §4.3 · pp. 7–8

5 EXPERIMENTS

The experiments compare cross-entropy with the smoothed top-k loss under label noise and varying training-set sizes. The smoothed loss performs better in noisy or data-limited settings, while the difference diminishes with more data.

5 EXPERIMENTS

  • The experiments vary label noise on CIFAR-100 and training-set size on ImageNet to compare CE with L5,τ.The study examines noise levels on CIFAR-100 and multiple ImageNet training-set sizes.Source: §5 · p. 8

5.1 CIFAR-100 WITH NOISE

  • CIFAR-100 noise replaces fine labels only within their coarse class, so a perfect top-5 classifier can still attain 100% accuracy.The CE baseline uses a held-out validation set for early stopping when noise is non-negligible; results average three runs.Source: §5.1 · p. 9

5 EXPERIMENTS

  • Noisy CIFAR-100: L5,1 beats CE on top-5 accuracy by over 5% at p=1; on ImageNet it wins with restricted data, while CE edges it slightly at full size.The ImageNet performance difference becomes very small as training-set size increases.Source: Table 1 · p. 9, §5.1 · p. 9, Table 2 · p. 10

5.2 IMAGENET

  • ImageNet experiments use ResNet-18 across training subsets from 64k to 1.23M images, with the best validation top-5 accuracy determining the reported test result.Training on the full dataset takes about a day and a half, with L5,0.1 taking 10% longer than CE.Source: §5.2 · pp. 9–10
  • For multi-crop ImageNet predictions, the method marginalizes each label's probability over top-5 combinations before averaging across crops.This approach boosts top-5 performance for all losses by at least 0.2%, and benefits CE by up to 1% in the small-data setting.Source: §5.2 · p. 10

6 CONCLUSION

The conclusion presents smooth top-k losses as direct objectives that need no fine-tuning and reports greater robustness than cross-entropy when training data are limited. The appendix also gives an equivalent reformulation and analyzes properties of the loss, including when it bounds its non-smooth counterpart.

6 CONCLUSION

  • The smooth top-5 loss is more robust to noise and overfitting than cross-entropy when training data are limited.The authors also report that performance differences shrink with large, correctly labeled data.Source: §6 · p. 10

A.1 REFORMULATION

  • Proposition 1 gives an equivalent reformulation of lk.Source: §A.1 · p. 14

A.3 BOUND ON NON-SMOOTH FUNCTION

  • The smoothed loss Lk,τ upper-bounds the non-smooth loss lk if and only if k = 1.Source: §A.3 · p. 15

A.4 BOUND ON PREDICTION LOSS

This appendix section establishes a scaled upper bound on prediction loss and analyzes the algorithm's complexity. It also describes a log-space computation intended to keep the forward pass numerically stable.

A.4 BOUND ON PREDICTION LOSS

  • Lk,τ is an upper bound on the prediction loss Λk up to a scaling factor.Source: §A.4 · p. 18

B.1 TIME COMPLEXITY

B.2.1 FORWARD PASS

  • The forward pass uses log-space operations, including log-sum-exp for additions, to maintain numerical stability.Source: §B.2.1 · p. 19

B.2.2 BACKWARD PASS

The backward recursion can become unstable for large elements, so the authors use a gradient approximation in unstable cases. The appendix also describes a summation alternative for computing elementary symmetric polynomials.

B.2.2 BACKWARD PASS

  • The backward recursion is unstable when ei is much larger than 1 and the other elements; such cases can produce unstable results.Source: §B.2.2 · pp. 19–20
  • When instability is detected, the authors use a p-th order gradient approximation, with p ≃ 0.2k as an empirically effective heuristic.The approximation error is not controlled at runtime; the heuristic increases forward-pass runtime by about 20%.Source: §B.2.2 · p. 20

B.3.1 SUMMATION ALGORITHM

  • The Summation Algorithm computes elementary symmetric polynomials with an essentially sequential outer loop and a parallelizable inner loop.Source: §B.3.1 · p. 20

B.3.2 SPEED

The appendix compares GPU runtimes and forward-pass stability for the algorithms. It also describes how marginal probabilities for top-k predictions are computed.

B.3.2 SPEED

B.3.3 STABILITY

  • The stability evaluation treats overflow as instability; the cited stability assumption for SA excludes overflow and underflow, which the authors say is not met in their use case.Source: §B.3.3 · pp. 21–22

C TOP-K PREDICTION: MARGINALIZATION WITH THE ELEMENTARY SYMMETRIC POLYNOMIALS

D HYPER-PARAMETERS & EXPERIMENTAL DETAILS

Temperature choice balances optimization ease against whether the surrogate remains informative. The authors also report that a fixed setting can match annealing and suggest the temperature considerations may extend beyond top-k losses.

D.1.1 OPTIMIZATION AND LEARNING

  • Low temperatures provide a sound learning objective but can make optimization difficult or cause it to fail; high temperatures ease optimization but make the loss uninformative.The authors recommend a low temperature that still permits satisfactory optimization.Source: §D.1.1 · p. 23

D.1.2 ILLUSTRATION ON CIFAR-100

  • Table 6 examines the influence of the temperature parameter through accuracy results, described in the text as training and validation accuracies and in its caption as training and testing accuracy.Source: Table 6 · p. 23, §D.1.2 · p. 23

D.1.3 TO ANNEAL OR NOT TO ANNEAL

  • Changing temperature can alter loss scale and the energy landscape, so regularization and learning-rate settings may need corresponding adjustment.The quadratic regularization value and learning rate are given as examples of hyperparameters to adapt.Source: §D.1.3 · p. 23
  • An appropriate fixed temperature matched careful annealing fine-tuning, while annealing required substantial engineering and yielded no substantial experimental improvement.Other hyperparameters also depend on temperature and require sensitive dynamic heuristics during annealing.Source: §D.1.3 · p. 23

D.1.4 PRACTICAL METHODOLOGY

The practical method uses a low fixed temperature and tunes other hyperparameters on validation data. The appendix relates margin and squared-norm regularization for the non-smooth loss, while noting a boundary for the smooth loss.

D.1.4 PRACTICAL METHODOLOGY

  • Set a low fixed temperature that permits learning, then tune other hyperparameters by validation; the optimal temperature is believed mostly architecture-independent but strongly influenced by k and n.The authors connect k and n to the number of summands in the loss and thus its scale.Source: §D.1.4 · p. 23

D.2.1 RELATIONSHIP WITH SQUARED NORM REGULARIZATION

  • The equivalence result requires no particular norm and uses positive homogeneity; the authors say the results readily generalize to linear latent structural SVMs.The regularizing norm is typically the Frobenius norm in deep learning, but the result follows for any norm.Source: §D.2.1 · pp. 24–25
  • For α > 0 and λ > 0, problem (Pλ,α) is equivalent to both (Pαλ,1) and (P1,αλ); if α = 0 or λ = 0, it is equivalent to (P0,0).Source: §D.2.1 · p. 24
  • For deep networks, fixing α=1 and tuning last-layer quadratic regularization independently keeps the loss scale unchanged and may ease learning-rate selection.Source: §D.2.1 · p. 25
  • The smooth loss has no direct equivalent of this result because log-sum-exp is not positively homogeneous, though the insight may still apply at low temperature.Source: §D.2.1 · p. 25

D.2.2 EXPERIMENT ON IMAGENET

The ImageNet appendix compares margin settings for top-1 and top-5 performance, and reports supplementary CIFAR-100 scores across label-noise levels. The supplied passages identify these comparisons but do not give their outcomes.

D.2.2 EXPERIMENT ON IMAGENET

  • The ImageNet margin experiments use validation-set results and do not use multiple crops.Source: §D.2.2 · p. 25
  • The top-1 comparison contrasts the cross-entropy setting (k, τ, α)=(1, 1, 0) with margin 1, with Table 7 covering top-1 performance.Source: Table 7 · p. 25, §D.2.2 · p. 25
  • The top-5 comparison contrasts (k, τ, α)=(5, 0.1, 0) with (5, 0.1, 1), with Table 8 covering top-5 performance.Source: Table 8 · p. 25, §D.2.2 · p. 25

D.3 SUPPLEMENTARY DETAILS

  • For CIFAR-100 testing across label-noise levels, Table 9 reports means and standard deviations; the main paper presents average scores for clarity.Source: Table 9 · p. 25, §D.3 · p. 25

Related papers

Loading 1802.07595v1…