Smooth loss functions for deep top-k classification

Conference item

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}(\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.

Authors: Berrada, L; Zisserman, A; Kumar, MP

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: OpenReview
• Host title: ICLR 2018 Conference Track
• Article number: 547
• Publication date: 2018-02-15
• Acceptance date: 2018-01-29
• Event title: 6th International Conference on Learning Representations (ICLR 2018)
• Event location: Vancouver, Canada
• Event website: https://iclr.cc/Conferences/2018
• Event start date: 2018-04-30
• Event end date: 2018-05-03
• Language: English