Smooth Loss Functions for Deep Top-k Classification

Abstract

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ïve algorithm would require $\mathcal{O}((\genfrac{}{}{0ex}{}{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}(kn)$. 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.

arXiv commentICLR 2018

References in corpus (1)

• Efficient Structured Prediction with Latent Variables for General Graphical Models

Cited by in corpus (16)

• Classification of Large-Scale High-Resolution SAR Images with Deep Transfer Learning
• Self-Regulated Learning for Egocentric Video Activity Anticipation
• IMAE for Noise-Robust Learning: Mean Absolute Error Does Not Treat Examples Equally and Gradient Magnitude's Variance Matters
• Deep Frank-Wolfe For Neural Network Optimization
• Top-k Training of GANs: Improving GAN Performance by Throwing Away Bad Samples
• Geometry-Inspired Top-k Adversarial Perturbations
• The Limited Multi-Label Projection Layer
• Differentiable Ranks and Sorting using Optimal Transport
• Backpropagation of Unrolled Solvers with Folded Optimization
• AutoCorrect: Deep Inductive Alignment of Noisy Geometric Annotations
• Optimizing Partial Area Under the Top-k Curve: Theory and Practice
• Higher Order Recurrent Space-Time Transformer for Video Action Prediction
• Learning Randomly Perturbed Structured Predictors for Direct Loss Minimization
• On the Consistency of Top-k Surrogate Losses
• Slim U-Net: Efficient Anatomical Feature Preserving U-net Architecture for Ultrasound Image Segmentation
• Predicting Human Activities from User-Generated Content