Analysis and Optimization of Loss Functions for Multiclass, Top-k, and Multilabel Classification

Introduction

Modern computer vision benchmarks are large scale , and are only likely to grow further both in terms of the sample size as well as the number of classes. While simply collecting more data may be a relatively straightforward exercise, obtaining high quality ground truth annotation is hard. Even when the annotation is just a list of image level tags, collecting a consistent and exhaustive list of labels for every image requires significant effort. Instead, existing benchmarks often offer only a single label per image, albeit the images may be inherently multilabel. The increased number of classes then leads to ambiguity in the labels as classes start to overlap or exhibit a hierarchical structure. The issue is illustrated in Figure 1, where it is difficult even for humans to guess the ground truth label correctly on the first attempt .

Allowing $k$ guesses instead of one leads to what we call the top-$k$ error, which is one of the main subjects of this work. While previous research is focused on minimizing the top-$1$ error, we consider $k\geq 1$. We are mainly interested in two cases: (i) achieving small top-$k$ error for all $k$ simultaneously; and (ii) minimization of a specific top-$k$ error. These goals are pursued in the first part of the paper which is concerned with single label multiclass classification. We propose extensions of the established multiclass loss functions to address top-$k$ error minimization and derive appropriate optimization schemes based on stochastic dual coordinate ascent (SDCA) . We analyze which of the multiclass methods are calibrated for the top-$k$ error and perform an extensive empirical evaluation to better understand their benefits and limitations. An earlier version of this work appeared in .

Moving forward, we see top-$k$ classification as a natural transition step between multiclass learning with a single label per training example and multilabel learning with a complete set of relevant labels. Multilabel learning forms the second part of this work, where we introduce a smoothed version of the multilabel SVM loss , and contribute two novel projection algorithms for efficient optimization of multilabel losses in the SDCA framework. Furthermore, we compare all multiclass, top-$k$, and multilabel methods in a novel experimental setting, where we want to quantify the utility of multilabel annotation. Specifically, we want to understand if it is possible to obtain effective multilabel classifiers from single label annotation.

The contributions of this work are as follows.

In § 2, we provide an overview of the related work and establish connections to a number of related research directions. In particular, we point to an intimate link that exists between top-$k$ classification, label ranking, and learning to rank in information retrieval.

In § 3, we introduce the learning problem for multiclass and multilabel classification, and discuss the respective performance metrics. We also propose $4$ novel loss functions for minimizing the top-$k$ error and a novel smooth multilabel SVM loss. A brief summary of the methods that we consider is given in Table I.

In § 4, we introduce the notion of top-$k$ calibration and analyze which of the multiclass methods are calibrated for the top-$k$ error. In particular, we highlight that the softmax loss is uniformly top-$k$ calibrated for all $k\geq 1$.

In § 5, we develop efficient optimization schemes based on the SDCA framework. Specifically, we contribute a set of algorithms for computing the proximal maps that can be used to train classifiers with the specified multiclass, top-$k$, and multilabel loss functions.

In § 6, the methods are evaluated empirically in three different settings: on synthetic data (§ 6.1), on multiclass datasets (§ 6.2), and on multilabel datasets (§ 6.3).

We release our implementation of SDCA-based solvers for training models with the loss functions considered in this work https://github.com/mlapin/libsdca. We also publish code for the corresponding proximal maps, which may be of independent interest.

Related Work

In this section, we place our work in a broad context of related research directions. First, we draw connections to the general problem of learning to rank. While it is mainly studied in the context of information search and retrieval, there are clear ties to multiclass and multilabel classification. Second, we briefly review related results on consistency and classification calibration. These form the basis for our theoretical analysis of top-$k$ calibration. Next, we focus on the technical side including the optimization method and the algorithms for efficient computation of proximal operators. Finally, we consider multiclass and multilabel image classification, which are the main running examples in this paper.

Learning to rank. Learning to rank is a supervised learning problem that arises whenever the structure in the output space admits a partial order . The classic example is ranking in information retrieval (IR), see e.g. for a recent review. There, a feature vector $\Phi(q,d)$ is computed for every query $q$ and every document $d$, and the task is to learn a model that ranks the relevant documents for the given query before the irrelevant ones. Three main approaches are recognized within that framework: the pointwise, the pairwise, and the listwise approach. Pointwise methods cast the problem of predicting document relevance as a regression or a classification problem. Instead, the pairwise approach is focused on predicting the relative order between documents . Finally, the listwise methods attempt to optimize a given performance measure directly on the full list of documents , or propose a loss function on the predicted and the ground truth lists .

Different from ranking in IR, our main interest in this work is label ranking which generalizes the basic binary classification problem to multiclass, multilabel, and even hierarchical classification, see for a survey. A link between the two settings is established if we consider queries to be examples (e.g. images) and documents to be class labels. The main contrast, however, is in the employed loss functions and performance evaluation at test time (§ 3).

Top-$k$ classification in our setting is directly related to label ranking as the task is to place the ground truth label in the set of top $k$ labels as measured by their prediction scores. An alternative approach is suggested by who use structured learning to aggregate the outputs of pre-trained one-vs-all binary classifiers and directly predict a set of $k$ labels, where the labels missing from the annotation are modelled with latent variables. That line of work is pursued further in . The task of predicting a set of items is also considered in , who frame it as a problem of maximizing a submodular reward function. A probabilistic model for ranking and top-$k$ classification is proposed by , while use metric learning to train a nearest neighbor model. An interesting setting related to top-$k$ classification is learning with positive and unlabeled data , where the absence of a label does not imply it is a negative label, and also learning with label noise .

Label ranking is closely related to multilabel classification , which we consider later in this paper, and to tag ranking . Ranking objectives have been also considered for training convolutional architectures , most notably with a loss on triplets , that consideres both positive and negative examples. Many recent works focus on the top of the ranked list . However, they are mainly interested in search and retrieval, where the number of relevant documents by far exceeds what users are willing to consider. That setting suggests a different trade-off for recall and precision compared to our setting with only a few relevant labels. This is correspondingly reflected in performance evaluation, as mentioned above.

Consistency and calibration. Classification is a discrete prediction problem where minimizing the expected (0-1) error is known to be computationally hard. Instead, it is common to minimize a surrogate loss that leads to efficient learning algorithms. An important question, however, is whether the minimizers of the expected surrogate loss also minimize the expected error. Loss functions which have that property are called calibrated or consistent with respect to the given discrete loss. Consistency in binary classification is well understood , and significant progress has been made in the analysis of multiclass , multilabel , and ranking methods. In this work, we investigate calibration of a number of surrogate losses with respect to the top-$k$ error, which generalizes previously established results for multiclass methods.

While there exist efficient projection algorithms for optimizing the SVM hinge loss and its descendants, the situation is a bit more complicated for logistic regression, both binary and multiclass. There exists no analytical solution for an update with the logistic loss, and suggest a formula in the binary case which computes an approximate update in closed form. Multiclass logistic (softmax) loss is optimized in the SPAMS toolbox , which implements FISTA . Alternative optimization methods are considered in who also propose a two-level coordinate descent method in the multiclass case. Different from these works, we propose to follow closely the same variable fixing scheme that is used for SVM training and use the Lambert $W$ function in the resulting entropic proximal map. Our runtime compares favourably with SPAMS, as we show in § 6.2.

Image classification. Multiclass and multilabel image classification are the main applications that we consider in this work to evaluate the proposed loss functions. We employ a relatively simple image recognition pipeline following , where feature vectors are extracted from a convolutional neural network (ConvNet), such as the VGGNet or the ResNet , and are then used to train a linear classifier with the different loss functions. The ConvNets that we use are pre-trained on the large scale ImageNet dataset, where there is a large number of object categories ($1000$), but relatively little variation in scale and location of the central object. For scene recognition, we also use a VGGNet-like architecture that was trained on the Places 205 dataset.

Despite the differences between the benchmarks , image representations learned by ConvNets on large datasets have been observed to transfer well . We follow that scheme in single-label experiments, e.g. when recognizing birds and flowers using a network trained on ImageNet, or when transferring knowledge in scene recognition . However, moving on to multi-label classification on Pascal VOC and Microsoft COCO , we need to account for increased variation in scale and object placement.

While the earlier works ignore explicit search for object location , or require bounding box annotation , recent results indicate that effective classifiers for images with multiple objects in cluttered scenes can be trained from weak image-level annotation by explicitly searching over multiple scales and locations . Our multilabel setup follows closely the pipeline of with a few exceptions detailed in § 6.3.

Loss Functions for Classification

The rest of this section covers the technical background that is used later in the paper. We discuss our notation, introduce multiclass and multilabel classification, recall the standard approaches to classification, and introduce our recently proposed methods for top-$k$ error minimization.

In § 3.1, we discuss multiclass and multilabel performance evaluation measures that are used later in our experiments. In § 3.2, we review established multiclass approaches and introduce our novel top-$k$ loss functions; we also recall Moreau-Yosida regularization as a smoothing technique and compute convex conjugates for SDCA optimization. In § 3.3, we discuss multilabel classification methods, introduce the smooth multilabel SVM, and compute the corresponding convex conjugates. To enhance readability, we defer all the proofs to the appendix.

At test time, prediction depends on the evaluation metric and generally involves sorting / producing the top-$k$ highest scoring class labels in the multiclass setting, and predicting the labels that score above a certain threshold $\delta$ in multilabel classification. We come back to performance metrics shortly.

We use $\pi$ and $\tau$ to denote permutations of (indexes) $\mathcal{Y}$. Unless stated otherwise, $a_{\pi}$ reorders components of a vector $a$ in descending order, $a_{\pi_{1}}\geq a_{\pi_{2}}\geq\ldots\geq a_{\pi_{m}}$. Therefore, for example, $a_{\pi_{1}}=\max_{j}a_{j}$. If necessary, we make it clear which vector is being sorted by writing $\pi(a)$ to mean $\pi(a)\in\operatorname*{arg\,sort}a$ and let $\pi_{1:k}(a)\triangleq\{\pi_{1}(a),\ldots,\pi_{k}(a)\}$. We also use the Iverson bracket defined as $\llbracket{P}\rrbracket=1$ if $P$ is true and otherwise; and introduce a shorthand for the conditional probability $p_{y}(x)\triangleq\Pr(Y=y\nonscript\,|\nonscript\,X=x)$. Finally, we let $a^{\!\setminus y}$ be obtained by removing the $y$-th coordinate from $a$.

Here, we briefly review performance evaluation metrics employed in multiclass and multilabel classification.

Multiclass. A standard performance measure for classification problems is the zero-one loss, which simply counts the number of classification mistakes . While that metric is well understood and inspired such popular surrogate losses as the SVM hinge loss, it naturally becomes more stringent as the number of classes increases. An alternative to the standard zero-one error is to allow $k$ guesses instead of one. Formally, the top-$k$ zero-one loss (top-$k$ error) is

That is, we count a mistake if the ground truth label $y$ scores below $k$ other class labels. Note that for $k=1$ we recover the standard zero-one error. Top-$k$ accuracy is defined as $1$ minus the top-$k$ error, and performance on the full test sample is computed as the mean across all test examples.

Multilabel. Several groups of multilabel evaluation metrics are established in the literature and it is generally suggested that multiple contrasting measures should be reported to avoid skewed results. Here, we give a brief overview of the metrics that we report and refer the interested reader to , where multilabel metrics are discussed in more detail.

Ranking based. This group of performance measures compares the ranking of the labels induced by $f_{y}(x)$ to the ground truth ranking. We report the rank loss defined as

where $D_{i}=\{(y,\bar{y})\nonscript\,|\nonscript\,f_{y}(x_{i})\leq f_{\bar{y}}(x_{i}),\;(y,\bar{y})\in Y_{i}\times\bar{Y}_{i}\}$ is the set of reversely ordered pairs, and $\bar{Y}_{i}\triangleq\mathcal{Y}\setminus Y_{i}$ is the complement of $Y_{i}$. This is the loss that is implicitly optimized by all multiclass / multilabel loss functions that we consider since they induce a penalty when $f_{\bar{y}}(x_{i})-f_{y}(x_{i})>0$.

Finally, we report the standard Pascal VOC performance measure, mean average precision (mAP), which is computed as the one-vs-all AP averaged over all classes.

Let $h(x)\triangleq\{y\in\mathcal{Y}\nonscript\,|\nonscript\,f_{y}(x)\geq\delta\}$ be the set of predicted labels for a given threshold $\delta$, and let

be a set of $m\cdot n$ primitives defined as in . Now, one can use any performance measure $\Psi$ that is based on the binary confusion matrix, but, depending on where the averaging occurs, the following three groups of metrics are recognized.

Instance-averaging. The binary metrics are computed on the averages over labels and then averaged across examples:

Macro-averaging. The metrics are averaged across labels:

Micro-averaging. The metric is applied on the averages over both labels and examples:

Following , we consider the $\mathbf{F_{1}}$ score as the binary metric $\Psi$ with all three types of averaging. We also report multilabel accuracy, subset accuracy, and the hamming loss defined respectively as

where $\triangle$ is the symmetric set difference.

2 Multiclass Methods

In this section, we switch from performance evaluation at test time to how the quality of a classifier is measured during training. In particular, we introduce the loss functions used in established multiclass methods as well as our novel loss functions for optimizing the top-$k$ error (1).

We also write $L(a)$ instead of the full $L(y,f(x))$.

The OVA and multiclass methods were designed with the goal of minimizing the standard zero-one loss. Now, if we consider the top-$k$ error (1) which does not penalize $(k-1)$ mistakes, we discover that convexity of the above losses leads to phenomena where $\operatorname{err}_{k}\!\left(y,f(x)\right)=0$, but $L(y,f(x))\gg 0$. That happens, for example, when $f_{\pi_{1}}(x)\gg f_{y}(x)\geq f_{\pi_{k}}(x)$, and creates a bias if we are working with rigid function classes such as linear classifiers. Next, we introduce loss functions that are modifications of the above losses with the goal of alleviating that phenomenon.

Moreau-Yosida regularization. We follow and give the main points here for completeness. The Moreau envelope or Moreau-Yosida regularization $M_{f}$ of the function $f$ is

where $f^{*}$ is the convex conjugate The convex conjugate of $f$ is $f^{*}(x^{*})=\sup_{x}\{\left\langle x^{*},x\right\rangle-f(x)\}$. of $f$. A classical result in convex analysis states that a conjugate of a strongly convex function has Lipschitz smooth gradient, therefore, $M_{f}$ is indeed a smooth function.

Top-$k$ hinge conjugate. Here, we compute the conjugates of the top-$k$ hinge losses $\alpha$ and $\beta$. As we show in , their effective domains The effective domain of $f$ is $\operatorname{dom}f=\{x\in X\nonscript\,|\nonscript\,f(x)<+\infty\}$. are given by the top-$k$ simplex ($\alpha$ and $\beta$ respectively) of radius $r$ defined as

We let $\Delta^{\alpha}_{k}=\Delta^{\alpha}_{k}(1)$, $\Delta^{\beta}_{k}=\Delta^{\beta}_{k}(1)$, and note the relation $\Delta^{\alpha}_{k}\subset\Delta^{\beta}_{k}\subset\Delta,$ where \Delta=\big{\{}x\nonscript\,|\nonscript\,\left\langle\mathbf{1},x\right\rangle\leq 1,\;x_{i}\geq 0\big{\}} is the unit simplex and the inclusions are proper for $k>1$, while for $k=1$ all three sets coincide.

Let $\gamma>0$ be the smoothing parameter. The smooth top-$k$ hinge loss ($\alpha$) and its conjugate are

where $p=\operatorname{proj}_{\Delta^{\alpha}_{k}(\gamma)}(a+c)^{\!\setminus y}$ is the Euclidean projection of $(a+c)^{\!\setminus y}$ onto $\Delta^{\alpha}_{k}(\gamma)$. Moreover, $L_{\gamma}(a)$ is $1/\gamma$-smooth.

where $\mathbf{I}_{y}$ is the identity matrix w/o the $y$-th column, $e_{y}$ is the $y$-th standard basis vector, and $\mathbf{1}_{y}$ is the $(m-1)$-dimensional vector of all ones. This follows from the definition of $a$, the fact that $L_{\gamma}(a)$ can be written as $\tfrac{1}{2\gamma}(\left\|x\right\|^{2}-\left\|x-p\right\|^{2})$ for $x=(a+c)^{\!\setminus y}$ and $p=\operatorname{proj}_{\Delta^{\alpha}_{k}(\gamma)}(x)$, and a known result which says that $\nabla_{x}\tfrac{1}{2}\left\|x-\operatorname{proj}_{C}(x)\right\|^{2}=x-\operatorname{proj}_{C}(x)$ for any closed convex set $C$.

where \Delta=\big{\{}x\nonscript\,|\nonscript\,\left\langle\mathbf{1},x\right\rangle\leq 1,\;x_{j}\geq 0\big{\}} is the unit simplex.

If there is only a single $j$ such that $f_{j}(x)-f_{y}(x)\gg 0$, then $L(y,f(x))\gg 0$ even though $\operatorname{err}_{2}\!\left(y,f(x)\right)$ is zero.

This problem is also present in all top-$k$ hinge losses considered above and is an inherent limitation due to their convexity. The origin of the problem is the fact that ranking based losses are based on functions such as

The function $\phi$ is convex if the sequence $(\alpha_{j})$ is monotonically non-increasing . This implies that convex ranking based losses have to put more weight on the highest scoring classifiers, while we would like to put less weight on them. To that end, we drop the first $(k-1)$ highest scoring predictions from the sum in (5), sacrificing convexity of the loss, and define the truncated top-$k$ entropy loss as follows

3 Multilabel Methods

Binary relevance (BR). Binary relevance is the standard one-vs-all scheme applied to multilabel classification. It is the default baseline for direct multilabel methods as it does not consider possible correlations between the labels.

Multilabel SVM. We follow the line of work by and consider the Multilabel SVM loss below:

In the multiclass setting, the set $Y$ is singleton, therefore $x_{y}=-\sum_{j\in\bar{Y}}x_{j}$ has no degrees of freedom and we recover the unit simplex $\Delta$ over $(x_{j})$, as in (4). In the true multilabel setting, on the other hand, there is freedom to distribute the weight across all the classes in $Y$.

As with the smooth top-$k$ SVM, there is no analytic formula for the smoothed loss. However, we can both compute and optimize it within our framework by solving the Euclidean projection problem onto what we call a bipartite simplex. It is a convenient modification of the set $S_{Y}$ above:

Let $\gamma>0$ be the smoothing parameter. The smooth multilabel SVM loss and its conjugate are

where $(p,\bar{p})=\operatorname{proj}_{B(\gamma)}(b,\bar{b})$ is the projection onto $B(\gamma)$ of b=\big{(}\tfrac{1}{2}-u_{y}\big{)}_{y\in Y}, \bar{b}=\big{(}\tfrac{1}{2}+u_{j}\big{)}_{j\in\bar{Y}}. $L_{\gamma}(u)$ is $1/\gamma$-smooth.

Assume that all the classes given in the ground truth set $Y$ are equally likely. We define an empirical distribution for a given $(x,Y)$ pair as $\hat{p}_{y}=(1/\left|Y\right|)\llbracket{y\in Y}\rrbracket$, and model the conditional probability $p_{y}(x)$ via the softmax:

The cross-entropy of the distributions $\hat{p}$ and $p(x)$ is given by

and the corresponding multilabel cross entropy loss is:

where $k=\left|Y\right|$ and $D_{Y}$ is the effective domain defined as:

Bayes Optimality and Top-k Calibration

This section is devoted to the theoretical analysis of multiclass losses in terms of their top-$k$ performance. We establish the best top-$k$ error in the Bayes sense, determine when a classifier achieves it, define the notion of top-$k$ calibration, and investigate which loss functions possess this property.

Bayes optimality. Recall that the Bayes optimal zero-one loss in binary classification is simply the probability of the least likely class . Here, we extend this notion to the top-$k$ error (1) introduced in § 3.1 for multiclass classification and provide a description of top-$k$ Bayes optimal classifier.

The Bayes optimal top-$k$ error at $x$ is

where $p_{\tau_{1}}(x)\geq p_{\tau_{2}}(x)\geq\ldots\geq p_{\tau_{m}}(x)$. A classifier $f$ is top-$k$ Bayes optimal at $x$ if and only if

where $f_{\pi_{1}}(x)\geq f_{\pi_{2}}(x)\geq\ldots\geq f_{\pi_{m}}(x)$.

Another way to write the optimal top-$k$ error is $\operatorname{\textstyle\sum}_{j=k+1}^{m}p_{\pi_{j}}(x)$, which naturally leads to an optimal prediction strategy according to the ranking of $p_{y}(x)$ in descending order. However, the description of a top-$k$ Bayes optimal classifier reveals that optimality for any given $k$ is better understood as a partitioning, rather than ranking, where the labels are split into $\pi_{1:k}$ and the rest, without any preference on the ranking in either subset. If, on the other hand, we want a classifer that is top-$k$ Bayes optimal for all $k\geq 1$ simultaneously, a proper ranking according to $p_{y}(x)$ is both necessary and sufficient.

Top-$k$ calibration. Optimization of the zero-one loss and the top-$k$ error leads to hard combinatorial problems. Instead of tackling a combinatorial problem directly, an alternative is to use a convex surrogate loss which upper bounds the discrete error. Under mild conditions on the loss function , an optimal classifier for the surrogate yields a Bayes optimal solution for the zero-one loss. Such loss functions are called classification calibrated, which is known in statistical learning theory as a necessary condition for a classifier to be universally Bayes consistent . We introduce now the notion of calibration for the top-$k$ error.

If a loss is not top-$k$ calibrated, it implies that even in the limit of infinite data, one does not obtain a classifier with the Bayes optimal top-$k$ error from Lemma 1. It is thus an important property, even though of an asymptotic nature. Next, we analyse which of the multiclass classification methods covered in § 3.2 are top-$k$ calibrated.

The OVA reduction is top-$k$ calibrated for any $1\leq k\leq m$ if the Bayes optimal function of a convex margin-based loss $L$ is a strictly monotonically increasing function of $p_{y}(x)=\Pr(Y=y\nonscript\,|\nonscript\,X=x)$ for every class $y\in\mathcal{Y}$.

Let the Bayes optimal classifier for the binary problem corresponding to a $y\in\mathcal{Y}$ have the form

where $g$ is a strictly monotonically increasing function. The ranking of $f_{y}$ corresponds to the ranking of $p_{y}(x)$ and hence the OVA reduction is top-$k$ calibrated for any $k\geq 1$. ∎

Next, we use Lemma 2 and the corresponding Bayes optimal classifiers to check if the one-vs-all schemes employing hinge and logistic regression losses are top-$k$ calibrated.

OVA logistic regression is top-$k$ calibrated.

The hinge loss is not calibrated since the corresponding binary classifiers, being piecewise constant, are subject to degenerate cases that result in arbitrary rankings of classes. Surprisingly, the smoothing technique based on Moreau-Yosida regularization (§ 3.2) makes a smoothed loss more attractive not only from the optimization side, but also in terms of top-$k$ calibration. Here, we show that a smooth binary hinge loss from fulfills the conditions of Lemma 2 and leads to a top-$k$ calibrated OVA scheme.

Multiclass SVM is not top-$k$ calibrated.

Multiclass softmax loss is top-$k$ calibrated.

The implicit reason for top-$k$ calibration of the OVA schemes and the softmax loss is that one can estimate the probabilities $p_{y}(x)$ from the Bayes optimal classifier. Loss functions which allow this are called proper. We refer to and references therein for a detailed discussion.

Furthermore, convexity of the softmax and multiclass hinge losses leads to phenomena where $\operatorname{err}_{k}\!\left(y,f(x)\right)=0$, but $L(y,f(x))\gg 0$. We discussed this issue § 3.2 and motivated modifications of the above losses for the top-$k$ error. Next, we show that one of the proposed top-$k$ losses is also top-$k$ calibrated.

The truncated top-$k$ entropy loss is top-$s$ calibrated for any $k\leq s\leq m$.

Top-$k$ calibration of the remaining top-$k$ losses is an open problem, which is complicated by the absence of a closed-form expression for most of them.

Optimization Framework

In § 5.1, we state the primal and Fenchel dual optimization problems, and introduce the Lambert $W$ function. In § 5.2, we consider SDCA update steps and loss computation for multiclass methods, as well as present our runtime evaluation experiments. In § 5.3, we cover multilabel optimization and present our algorithm for the Euclidean projection onto the bipartite simplex.

We briefly recall the main facts about the SDCA framework , Fenchel duality , and the Lambert $W$ function .

where $L^{*}$ is the convex conjugate of $L$ and $y_{i}$ is interpreted as a set $Y_{i}$ if $L$ is a multilabel loss.

It turns out that every update step $\max_{a_{i}}D(A)$ is equivalent to the proximal operator The proximal operator, or the proximal map, of a function $f$ is defined as \operatorname{prox}_{f}(v)=\operatorname*{arg\,min}\limits_{x}\big{(}f(x)+\tfrac{1}{2}\left\|x-v\right\|^{2}\big{)}. of a certain function, which can be seen as a projection onto the effective domain of $L^{*}$.

To develop intuition about the function $V(t)=W(e^{t})$, which is the Lambert $W$ function of the exponent, we look at how it behaves for different values of $t$. An illustration is provided in Figure 2. One can see directly from the equation $x+\log x=t$ that the behavior of $x=V(t)$ changes dramatically depending on whether $t$ is a large positive or a large negative number. In the first case, the linear part dominates the logarithm and the function is approximately linear; a better approximation is $x(t)\approx t-\log t$, when $t\gg 1$. In the second case, the function behaves like an exponent $e^{t}$. To see this, we write $x=e^{t}e^{-x}$ and note that $e^{-x}\approx 1$ when $t\ll 0$, therefore, $x(t)\approx e^{t}$, if $t\ll 0$.

To compute $V(t)$, we use these approximations as initial points in a $5$-th order Householder method . A single iteration of that method is already sufficient to get full float precision and at most two iterations are needed for double, which makes the function $V(t)$ an attractive tool for computing entropic projections.

2 Multiclass Methods

In this section, we cover optimization of the multiclass methods from § 3.2 within the SDCA framework. We discuss how to efficiently compute the smoothed losses that were introduced via conjugation and do not have a closed-form expression. Finally, we evaluate SDCA convergence in terms of runtime and show that smoothing with Moreau-Yosida regularization leads to significant improvements in speed.

As mentioned in § 5.1 above, the core of the SDCA algorithm is the update step $a_{i}\leftarrow\operatorname*{arg\,max}_{a_{i}}D(A)$. Even the primal objective $P(W)$ is only computed for the duality gap and could conceivably be omitted if the certificate of optimality is not required. Next, we focus on how the updates are computed for the different multiclass methods.

We show that performing the update step is equivalent to projecting a certain vector $b$, computed from the prediction scores $f(x_{i})=W^{\top}x_{i}$, onto the effective domain of $L^{*}$, the top-$k$ simplex, with an added regularization $\rho\left\langle\mathbf{1},x\right\rangle^{2}$, which biases the solution to be orthogonal to $\mathbf{1}$.

where $b=\frac{1}{\left\langle x_{i},x_{i}\right\rangle+\gamma\lambda n}\left(q^{\!\setminus y_{i}}+(1-q_{y_{i}})\mathbf{1}\right)$, $q=W^{\top}x_{i}-\left\langle x_{i},x_{i}\right\rangle a_{i}$, and $\rho=\frac{\left\langle x_{i},x_{i}\right\rangle}{\left\langle x_{i},x_{i}\right\rangle+\gamma\lambda n}$.

Smooth top-$k$ hinge losses converge significantly faster than their nonsmooth variants as we show in the scaling experiments below. This can be explained by the theoretical results of on the convergence rate of SDCA. They also had similar observations for the smoothed binary hinge loss.

where $\alpha=\frac{\left\langle x_{i},x_{i}\right\rangle}{\lambda n}$, $b=q^{\!\setminus y_{i}}-q_{y_{i}}\mathbf{1}$, $q=W^{\top}x_{i}-\left\langle x_{i},x_{i}\right\rangle a_{i}$.

Problems (10) and (11) have similar structure, but the latter is considerably more difficult to solve due to the presence of logarithms. We propose to tackle this problem using the function $V(t)$ introduced in § 5.1 above.

Our algorithm is an instance of the variable fixing scheme with the following steps: (i) partition the variables into disjoint sets and compute an auxiliary variable $t$ from the optimality conditions; (ii) compute the values of the variables using $t$ and verify them against a set of constraints (e.g. an upper bound in the top-$k$ simplex); (iii) if there are no violated constraints, we have computed the solution, and otherwise examine the next partitioning.

As we discuss in , there can be at most $k$ partitionings that we need to consider for $\Delta^{\alpha}_{k}$ and $\Delta^{\beta}_{k}$. To see this, let $x\in\Delta^{\alpha}_{k}$ be a feasible point for (11), and define the subsets

Clearly, $\left|U\right|\leq k$ must hold, and $\left|U\right|=k$ we consider as a degenerate fall back case. Therefore, we are primarily interested in the $k$ partitions when $0\leq\left|U\right|<k$. Due to monotonicity in the optimality conditions, one can show that $U$ always corresponds to the largest elements $b_{j}$ of the vector being projected. Hence, we start with an empty $U$ and add indexes of the largest $b_{j}$’s until the solution is found.

Next, we show how to actually compute $t$ and $x$, given a candidate partition into $U$ and $M$.

Let $x^{*}$ be the solution of (11) and let the sets $U$ and $M$ be defined for the given $x^{*}$ as in (12), then

and the variables $s$, $t$ satisfy the nonlinear system

where $\rho\triangleq\tfrac{\left|U\right|}{k}$, $A\triangleq\tfrac{1}{k}\operatorname{\textstyle\sum}_{j\in U}b_{j}$, $V^{-1}$ is the inverse of $V$.

Moreover, if $U$ is empty, then $x_{j}^{*}=\tfrac{1}{\alpha}V(b_{j}-t)$ for all $j$, and $t$ can be found from

Note that (15) is similar to (11) and we use a similar variable fixing scheme, as described above. However, this problem is much easier: the auxiliary variables $s$ and $t$ are computed directly without having to solve a nonlinear system, and their computation does not involve the $V(t)$ function.

Let $x^{*}$ be the solution of (15) and let the sets $U$ and $M$ be defined for the given $x^{*}$ as in (12), then

and the variables $s$, $t$ are computed from

where $\rho\triangleq\tfrac{\left|U\right|}{k}$, $A\triangleq\tfrac{1}{k}\operatorname{\textstyle\sum}_{j\in U}a_{j}$, $Z\triangleq\operatorname{\textstyle\sum}_{j\in M}\exp a_{j}$, and

3 Multilabel Methods

b=\rho\big{(}\tfrac{1}{2}-q_{y}\big{)}_{y\in Y_{i}}, \bar{b}=\rho\big{(}\tfrac{1}{2}+q_{j}\big{)}_{j\in\bar{Y}_{i}}, $q=W^{\top}x_{i}-\left\langle x_{i},x_{i}\right\rangle a_{i}$, and $\rho=\tfrac{1}{\left\langle x_{i},x_{i}\right\rangle+\gamma\lambda n}$.

Euclidean projection onto the bipartite simplex $B(\rho)$. The optimization problem that we seek to solve is:

This problem has been considered by Shalev-Shwartz and Singer , who proposed a breakpoint searching algorithm based on sorting, as well as by Liu and Ye , who formulated it as a root finding problem that is solved via bisection. Next, we contribute a novel variable fixing algorithm that is inspired by the algorithm of Kiwiel for the continuous quadratic knapsack problem (a.k.a. projection onto simplex).

Initialization. Define the sets $I_{x}=\{1,\ldots,m\}$, $L_{x}=\{\}$, $I_{y}=\{1,\ldots,n\}$, $L_{y}=\{\}$, and solve the independent subproblems below using the algorithm of .

Let $t^{\prime}$ and $s^{\prime}$ be the resulting optimal thresholds, such that $p=\max\{0,b-t^{\prime}\}$ and $\bar{p}=\max\{0,\bar{b}-s^{\prime}\}$. If $t^{\prime}+s^{\prime}\geq 0$, then $(p,\bar{p})$ is the solution to (17); stop.

and let $x_{j}(t)=b_{j}-t$, $y_{j}(t)=\bar{b}_{j}+t$.

Stopping criterion. If $\Delta_{x}=\Delta_{y}$, then the solution to (17) is given by $p=\max\{0,b-t\}$ and $\bar{p}=\max\{0,\bar{b}+t\}$; stop.

Variable fixing. If $\Delta_{x}>\Delta_{y}$, update $I_{x}\leftarrow I_{x}\setminus I_{x}^{L}$, $L_{x}\leftarrow L_{x}\cup I_{x}^{L}$. If $\Delta_{x}<\Delta_{y}$, update $I_{y}\leftarrow I_{y}\setminus I_{y}^{L}$, $L_{y}\leftarrow L_{y}\cup I_{y}^{L}$. Go to step 2.

The proposed algorithm is easy to implement, does not require sorting, and scales well in practice, as demonstrated by our experiments on VOC 2007 and MS COCO.

Runtime evaluation. We also compare the runtime of the proposed variable fixing algorithm and the sorting based algorithm of . We perform no comparison to as their code is not available. Furthermore, the algorithms that we consider are exact, while the method of is approximate and its runtime is dependent on the required precision. The experimental setup is the same as in § 5.2 above, and our results are reported in Table II.

$k=\left|Y_{i}\right|$, $\alpha=\tfrac{\left\langle x_{i},x_{i}\right\rangle}{\lambda n}$, b=\big{(}\tfrac{1}{\alpha}q_{j}+\tfrac{1}{k}\big{)}_{j\in Y_{i}}, \bar{b}=\big{(}\tfrac{1}{\alpha}q_{j}\big{)}_{j\in\bar{Y}_{i}}, and $q=W^{\top}x_{i}-\left\langle x_{i},x_{i}\right\rangle a_{i}$.

Moreover, the solution of (18) is given by

Experiments

This section provides a broad array of experiments on $24$ different datasets comparing multiclass and multilabel performance of the $13$ loss functions from § 3. We look at different aspects of empirical evaluation: performance on synthetic and real data, use of handcrafted features and the features extracted from a ConvNet, targeting a specific performance measure and being generally competitive over a range of metrics.

In this section, we demonstrate in a synthetic experiment that our proposed top-$2$ losses outperform the top-$1$ losses when the aim is optimal top-$2$ performance. The dataset with three classes is shown in the inner circle of Figure 4.

2 Multiclass Experiments

Please refer to Table I for an overview of the methods and our naming convention. Further comparison with other established ranking based losses can be found in .

Features. For ALOI, Letter, and News20 datasets, we use the features provided by the LibSVM datasets. For ALOI, we randomly split the data into equally sized training and test sets preserving class distributions. The Letter dataset comes with a separate validation set, which we use for model selection only. For News20, we use PCA to reduce dimensionality of sparse features from $62060$ to $15478$ preserving all non-singular PCA components Our SDCA-based solvers are designed for dense inputs..

For Caltech101 Silhouettes, we use the features and the train/val/test splits provided by .

For CUB, Flowers, FMD, and ImageNet 2012, we use MatConvNet to extract the outputs of the last fully connected layer of the VGGNet-16 model .

For Indoor 67, SUN 397, and Places 205, we perform the same feature extraction, but use the VGGNet-16 model of which was pre-trained on Places 205.

Discussion. The results are given in Table V, and we can make several interesting observations. First, while the OVA schemes perform quite similar to the multiclass approaches (OVA logistic regression vs. softmax, OVA SVM vs. multiclass SVM), which confirms earlier observations in , the OVA schemes performed worse on ALOI and Letter. Thus, we generally recommend the multiclass losses instead of the OVA schemes.

Comparing the softmax loss and multiclass SVM, we see that there is no clear winner in top-$1$ performance, but softmax consistently outperforms multiclass SVM in top-$k$ performance for $k>1$. This might be due to the strong property of softmax being top-$k$ calibrated for all $k$. Note that this trend is uniform across all datasets, in particular, also for the ones where the features are not coming from a ConvNet. Both the smooth top-$k$ SVM and the top-$k$ entropy losses perform slightly better than softmax if one compares specific top-$k$ errors. However, the good performance of the truncated top-$k$ entropy loss on synthetic data did not transfer to the real world datasets.

3 Multilabel Experiments

The aim of this section is threefold. First, we establish competitive performance of our multilabel classification methods from § 3.3 comparing them to the top $3$ methods from an extensive experimental study by Madjarov et al. on $10$ multilabel benchmark datasets of varying scale and complexity. Next, we discuss an interesting learning setting when top-$k$ classification methods emerge as a transition step between multiclass and multilabel approaches. Finally, we evaluate multiclass, top-$k$, and multilabel classification methods on Pascal VOC 2007 and the more challenging Microsoft COCO image classification benchmarks.

We follow closely the evaluation protocol of except for the selection of the cut-off threshold $\delta$ (see § 3.1 for definition). Following , Madjarov et al. choose $\delta$ by matching label cardinality between the training and test data. While it is fast and easy to compute, that approach has two drawbacks: (i) being an instance of transductive learning, the method requires re-computation of $\delta$ every time test data changes; (ii) the choice of $\delta$ is not tuned to any performance measure and is likely to be suboptimal. In our experiments (not reported here), we observed generally comparable, but slightly lower results compared to when $\delta$ is selected on a validation set as discussed next.

Instead, Koyejo et al. recently showed that a consistent classifier is obtained when one computes $\delta$ by optimizing a given performance measure on a hold-out validation set. While there are at most $mn$ distinct values of $\delta$ that would need to be considered, we limit the search to the grid $\{-10^{(-5.9:.2:1)},0,10^{(-5.9:.2:1)}\}$ of $71$ values.

Following , we use $10$-fold cross-validation to select $C=1/(\lambda n)$, the RBF kernel parameter $\theta=1/(2\sigma^{2})$, and the threshold $\delta$, as described above. We use rather large and fine-grained grids both for $C$ (from $2^{-20}$ to $2^{5}$) and $\theta$ (from $2^{-15}$ to $2^{3}$). The smoothing parameter is always set $\gamma=1$.

Multiclass to multilabel. Collecting ground truth annotation is hard. Even when the annotation is simply an image level tag, providing a consistent and exhaustive list of labels for every image in the training set would require significant effort. It is much easier to provide a weaker form of annotation where only a single prominent object is tagged. An interesting question is then whether it is still possible to train multilabel classifiers from multiclass annotation. And if so, how large is the performance gap compared to methods trained with full multilabel annotation? In the following, we set to explore that setting and answer the questions above.

We also note that top-$k$ classification emerges naturally as an intermediate step between multiclass and multilabel learning. Recall that top-$k$ loss functions operate in the multiclass setting where there is a single label per example, but that label is hard to guess correctly on the first attempt. One could imagine that the example is actually associated with $k$ labels, but only a single label is revealed in the annotation. Therefore, it is also interesting to see if our top-$k$ loss functions can offer an advantage over the classic multiclass losses in this setting.

To evaluate the multiclass, top-$k$, and multilabel loss functions on a common task, we choose two multilabel image classification benchmarks: Pascal VOC 2007 and Microsoft COCO. Multilabel methods are trained using full image level annotation (i.e. all class labels, but no bounding boxes or segmentation), while multiclass and top-$k$ methods are trained using a single label per image. Both datasets offer object level bounding box annotations which can be used to estimate relative sizes of objects in the scene. For multiclass training, we only keep the label of the largest object, which is our proxy to estimating the prominent object in the image. All methods are evaluated using full annotation at test time. Note that except for pruning the training labels, we do not use bounding boxes anywhere during training or testing.

To isolate the effect of loss functions on classifier training from feature learning, we follow the classic approach of extracting features as a pre-processing step and then train our classifiers on the fixed image representation. We use our own implementation of SDCA based solvers for all of the methods considered in this section. That offers strong convergence guarantees due to (i) convexity of the objective and (ii) having the duality gap as the stopping criterion.

Every feature vector can be mapped to a region in the original image. For training, we simply replicate the same image labels effectively increasing the size of the training set. At test time, we obtain a single ranking of class labels per image by max pooling the scores for each class. We follow this basic setup, but note that a $1-2\%$ improvement is possible with a more sophisticated aggregation of information from the different image regions .

Comparing the smooth and nonsmooth losses, we see that nonsmooth loss functions tend to perform better on this dataset. Moreover, SVM seems to perform significantly better than softmax. While this is a somewhat surprising result, it has been observed previously, e.g. with the R-CNN detector , and with deeply-supervised CNNs , even though their comparison was to OVA SVM.

The current state of the art classification results on COCO are reported in . A comparable architecture achieved $69.7\%$ mAP, while performing inference on the multiple regions per image and exploiting the bounding box annotations boosted the performance to $73\%$ mAP.

Conclusion

References

Appendix A Proofs from § 3

We take the convex conjugate of the top-$k$ hinge loss, which was derived in [9, Proposition 2], and add a regularizer $\frac{\gamma}{2}\left\langle v,v\right\rangle$ to obtain the $\gamma$-strongly convex conjugate loss $L_{\gamma}^{*}(v)$. Note that since $v_{y}=-\sum_{j\neq y}v_{j}$ and $a_{y}=f_{y}(x)-f_{y}(x)=0$, we only need to work with $(m-1)$-dimensional vectors where the $y$-th coordinate is removed. The primal loss $L_{\gamma}(a)$, obtained as the convex conjugate of $L_{\gamma}^{*}(v)$, is $1/\gamma$-smooth due to a known result in convex analysis (see also [8, Lemma 2]). We now derive a formula to compute it based on the Euclidean projection onto the top-$k$ simplex. By definition,

For the constraint $\frac{v}{\gamma}\in\Delta^{\alpha}_{k}(1)$, we have

The final expression follows from the fact that

A.2 Proof of Proposition 3

Here, we use the notation $u\triangleq f(x)$ as we need to take special care of the differences $f_{j}(x)-f_{y}(x)$ when computing the conjugate. Therefore, the softmax loss is

where $a=H_{y}u$ as before and $H_{y}\triangleq\mathbf{I}-\mathbf{1}e_{y}^{\top}$. Define

then $L(u)=\phi(H_{y}u)$ and the convex conjugate is computed similar to [9, Lemma 2] as follows.

which together with $\left\langle\mathbf{1},v\right\rangle=0$ implies $(H^{\dagger}_{y})^{\top}v=v-v_{y}e_{y}.$

The function inside $\sup$ is concave and differentiable, hence the global optimum is at the critical point . Setting the partial derivatives to zero yields

for $j\neq y$, from which we conclude, similar to [8, § 5.1], that $\left\langle\mathbf{1},v\right\rangle\leq 1$ and $0\leq v_{j}\leq 1$ for all $j\neq y$, i.e. $v^{\!\setminus y}\in\Delta$. Let $Z\triangleq\sum_{j\neq y}\exp(u_{j})$, we have at the optimum

Since $\left\langle\mathbf{1},v\right\rangle=0$, we also have that $v_{y}=-\sum_{j\neq y}v_{j}$, hence

Summing $v_{j}$ and using the definition of $Z$,

if $\left\langle\mathbf{1},v\right\rangle=0$ and $v^{\!\setminus y}\in\Delta$ as stated in the proposition. ∎

A.3 Proof of Proposition 4

The convex conjugate of the top-$k$ entropy loss is

The (primal) top-$k$ entropy loss is defined as the convex conjugate of the $L^{*}(v)$ above. We have

Note that $a_{y}=0$, and hence the corresponding term vanishes. Finally, we let $x\triangleq v^{\!\setminus y}$ and $s\triangleq\sum_{j\neq y}v_{j}=\left\langle\mathbf{1},x\right\rangle$.

Next, we discuss how this problem can be solved and show that it reduces to the softmax loss for $k=1$. Let $a\triangleq a^{\!\setminus y}$ and consider an equivalent problem below.

Consider $x_{j}$’s for which $0<x_{j}<\frac{s}{k}$ holds at the optimum. The complementary slackness conditions imply that the corresponding $\mu_{j}=\nu_{j}=0$. Let $p\triangleq\left\langle\mathbf{1},\nu\right\rangle$ and re-define $t$ as $t\leftarrow 1+t$. We obtain the simplified equations

If $k=1$, then $0<x_{j}<s$ for all $j$ in a multiclass problem as discussed above, hence also $p=0$. We have

Taking into account the minus in front of the $\min$ in (20) and the definition of $a$, we finally recover the softmax loss

A.4 Proof of Proposition 5

When the infimum is attained, the conjugate can be computed by solving the following optimization problem, otherwise the conjugate is $+\infty$. The corresponding dual variables are given on the right.

Computing the partial derivatives and setting them to zero,

After a basic derivation, we arrive at the solution of the dual problem given by

where $v$ must be in the following feasible set $S_{Y}$:

To complete the proof, note that $L^{*}(v)=-\lambda$ if $v\in S_{Y}$. ∎

A.5 Proof of Proposition 6

Before we add $\frac{\gamma}{2}\left\|v\right\|^{2}$, recall that $\sum_{y\in Y}v_{y}=-\sum_{j\in\bar{Y}}v_{j}$, and so \sum_{y\in Y}v_{y}=\frac{1}{2}\big{(}\operatorname{\textstyle\sum}_{y\in Y}v_{y}-\operatorname{\textstyle\sum}_{j\in\bar{Y}}v_{j}\big{)}. We use the average instead of an individual sum for symmetry and improved numerical stability. The smoothed conjugate loss is then

To derive the primal loss, we take the conjugate again:

Next, we define the following auxiliary variables:

and rewrite the smooth loss $L_{\gamma}(u)$ equivalently as

which is the Euclidean projection onto the set $B(\gamma)$. ∎

A.6 Proof of Proposition 7

Let $Z\triangleq\sum_{j\in\mathcal{Y}}\exp u_{j}$, then

Thus, for the supremum to be attained, we must have

which means $v_{j}\geq-\tfrac{1}{k}$ if $j\in Y$, and $v_{j}\geq 0$ otherwise. Moreover, we have

Plugging the optimal $u^{*}$, we compute the conjugate as

where $\left\langle\mathbf{1},v\right\rangle=0$ and

This leads to the definition of the effective domain $D_{Y}$, since

Appendix B Proofs from § 4

The error is minimal when $\operatorname{\textstyle\sum}_{j=1}^{k}p_{\pi_{j}}(x)$ is maximal, which corresponds to taking the $k$ largest conditional probabilities $\operatorname{\textstyle\sum}_{j=1}^{k}p_{\tau_{j}}(x)$ and yields the Bayes optimal top-$k$ error at $x$.

Since the relative order within $\{p_{\tau_{j}}(x)\}_{j=1}^{k}$ is irrelevant for the top-$k$ error, any classifier $f(x)$, for which the sets $\{\pi_{1},\ldots,\pi_{k}\}$ and $\{\tau_{1},\ldots,\tau_{k}\}$ coincide, is Bayes optimal.

Note that we assumed w.l.o.g. that there is a clear cut $p_{\tau_{k}}(x)>p_{\tau_{k+1}}(x)$ between the $k$ most likely classes and the rest. In general, ties can be resolved arbitrarily as long as we can guarantee that the $k$ largest components of $f(x)$ correspond to the classes (indexes) that yield the maximal sum $\operatorname{\textstyle\sum}_{j=1}^{k}p_{\pi_{j}}(x)$ and lead to top-$k$ Bayes optimality. ∎

B.2 Proof of Proposition 8

First, we show that the Bayes optimal function for the binary hinge loss is

Thus, one can compute the Bayes optimal classifier $f^{*}$ pointwise by solving

where $p_{y}(x)\triangleq\Pr(Y=y\nonscript\,|\nonscript\,X=x)$. It is obvious that the optimal $\alpha^{*}$ is contained in $$. We get

The minimum is attained at the boundary and we get

Therefore, the Bayes optimal classifier for the hinge loss is not a strictly monotonically increasing function of $p_{1}(x)$.

To show that OVA hinge is not top-$k$ calibrated, we construct an example problem with $3$ classes and $p_{1}(x)=0.4$, $p_{2}(x)=p_{3}(x)=0.3$. Note that for every class $y=1,2,3$, the Bayes optimal binary classifier is $-1$, hence the predicted ranking of labels is arbitrary and may not produce the Bayes optimal top-$k$ error. ∎

B.3 Proof of Proposition 9

First, we show that the Bayes optimal function for the binary logistic loss is

As above, the pointwise optimization problem is

The logistic loss is known to be convex and differentiable and thus the optimum can be computed via

which can be solved as \alpha^{*}=\log\Big{(}\frac{p_{1}(x)}{p_{-1}(x)}\Big{)} and leads to the formula for the Bayes optimal classifier stated above.

The derivative is strictly positive on $(0,1)$, which implies that $\phi$ is strictly monotonically increasing. The logistic loss, therefore, fulfills the conditions of Lemma 2 and is top-$k$ calibrated for any $1\leq k\leq m$. ∎

B.4 Proof of Proposition 10

In order to derive the smooth hinge loss, we first compute the conjugate of the standard binary hinge loss,

The corresponding primal smooth hinge loss is given by

$L_{\gamma}(\alpha)$ is convex and differentiable with the derivative

We compute the Bayes optimal classifier pointwise.

Let $p\triangleq p_{1}(x)$, the optimal $\alpha^{*}$ is found by solving

Case $0<\gamma\leq 1$. Consider the case $1-\gamma\leq\alpha\leq 1$,

This case corresponds to $p\geq\frac{1}{2}$, which follows from the constraint $\alpha^{*}\geq 1-\gamma$. Next, consider $\gamma-1\leq\alpha\leq 1-\gamma$,

unless $p=\frac{1}{2}$, which is already captured by the first case. Finally, consider $-1\leq\alpha\leq\gamma-1\leq 1-\gamma$. Then

where we have $-1\leq\alpha^{*}\leq\gamma-1$ if $p\leq\frac{1}{2}$. We obtain the Bayes optimal classifier for $0<\gamma\leq 1$ as follows:

Note that while $f^{*}(x)$ is not a continuous function of $p=p_{1}(x)$ for $\gamma<1$, it is still a strictly monotonically increasing function of $p$ for any $0<\gamma\leq 1$.

Case $\gamma>1$. First, consider $\gamma-1\leq\alpha\leq 1$,

From $\alpha^{*}\geq\gamma-1$, we get the condition $p\geq\frac{\gamma}{2}$. Next, consider $1-\gamma\leq\alpha\leq\gamma-1$,

which is in the range $[1-\gamma,\gamma-1]$ if $1-\frac{\gamma}{2}\leq p\leq\frac{\gamma}{2}$. Finally, consider $-1\leq\alpha\leq 1-\gamma$,

where we have $-1\leq\alpha^{*}\leq 1-\gamma$ if $p\leq 1-\frac{\gamma}{2}$. Overall, the Bayes optimal classifier for $\gamma>1$ is

Note that $f^{*}$ is again a strictly monotonically increasing function of $p=p_{1}(x)$. Therefore, for any $\gamma>0$, the one-vs-all scheme with the smooth hinge loss (23) is top-$k$ calibrated for all $1\leq k\leq m$ by Lemma 2. ∎

B.5 Proof of Proposition 11

Suppose that the maximum of $(g_{j})_{j\in\mathcal{Y}}$ is not unique. In this case, we have

as the term $\llbracket{j\neq l}\rrbracket$ is always active. The best possible loss is obtained by setting $g_{j}=c$ for all $j\in\mathcal{Y}$, which yields an expected loss of $1$. On the other hand, if the maximum is unique and is achieved by $g_{y}$, then

As the loss only depends on the gap $g_{y}-g_{l}$, we can optimize this with $\beta_{l}=g_{y}-g_{l}$.

As only the minimal $\beta_{l}$ enters the last term, the optimum is achieved if all $\beta_{l}$ are equal for $l\neq y$ (otherwise it is possible to reduce the first term without affecting the last term). Let $\alpha\triangleq\beta_{l}$ for all $l\neq y$. The problem becomes

Let $p\triangleq p_{y}(x)=\Pr(Y=y\nonscript\,|\nonscript\,X=x)$. The solution is

Moreover, we have that the Bayes risk at $x$ is

It follows, that the multiclass hinge loss is not (top-$1$) classification calibrated at any $x$ where $\max_{y\in\mathcal{Y}}p_{y}(x)<\frac{1}{2}$ as its Bayes optimal classifier reduces to a constant. Moreover, even if $p_{y}(x)\geq\frac{1}{2}$ for some $y$, the loss is not top-$k$ calibrated for $k\geq 2$ as the predicted order of the remaining classes need not be optimal. ∎

B.6 Proof of Proposition 12

The multiclass softmax loss is (top-$1$) calibrated for the zero-one error in the following sense. If

then for some $\alpha>0$ and all $y\in\mathcal{Y}$

We now prove this result and show that it also generalizes to top-$k$ calibration for $k>1$. Using the identity

As the loss is convex and differentiable, we get the global optimum by computing a critical point. We have

for $j\in\mathcal{Y}$. We note that the critical point is not unique as multiplication $g\rightarrow\kappa g$ leaves the equation invariant for any $\kappa>0$. One can verify that $e^{g_{j}}=\alpha p_{j}(x)$ satisfies the equations for any $\alpha>0$. This yields a solution

for any fixed $\alpha>0$. We note that $f^{*}_{y}$ is a strictly monotonically increasing function of the conditional class probabilities. Therefore, it preserves the ranking of $p_{y}(x)$ and implies that $f^{*}$ is top-$k$ calibrated for any $1\leq k\leq m$. ∎

B.7 Proof of Proposition 13

Therefore, the expected loss at $x$ can be written as

Note that the sum inside the logarithm does not depend on $g_{\pi_{r}}$ for $r<k$. Therefore, a Bayes optimal classifier will have $g_{\pi_{r}}=+\infty$ for all $r<k$ as then the first sum vanishes.

Let $p\triangleq(p_{y}(x))_{y\in\mathcal{Y}}$ and $q\triangleq(L(y,g))_{y\in\mathcal{Y}}$, then

where $p_{\tau_{1}}\geq p_{\tau_{2}}\geq\ldots\geq p_{\tau_{m}}$ and we used the rearrangement inequality. Therefore, the expected loss is minimized when $\pi$ and $\tau$ coincide (up to a permutation of the first $k-1$ elements), which already establishes top-$s$ calibration for all $s\geq k$.

We can also derive a Bayes optimal classifier following the proof of Proposition 12. We have

A critical point is found by setting partial derivatives to zero for all $y\in\{\tau_{k},\ldots,\tau_{m}\}$, which leads to

We let $g_{y}=-\infty$ if $p_{y}(x)=0$, and obtain finally

as a Bayes optimal classifier for any $\alpha>0$.

Note that $g^{*}$ preserves the ranking of $p_{y}(x)$ for all $y$ in $\{\tau_{k},\ldots,\tau_{m}\}$, hence, it is top-$s$ calibrated for all $s\geq k$. ∎

Appendix C Proofs from § 5

We follow the proof of [9, Proposition 4]. Choose an $i\in\{1,\ldots,n\}$ and update $a_{i}$ to maximize

For the nonsmooth top-$k$ hinge loss, it was shown that

if $-\lambda n(a_{i}-a_{y_{i},i}e_{y_{i}})\in\Delta^{\alpha}_{k}$ and $+\infty$ otherwise. Now, for the smoothed loss, we add regularization and obtain

with $-\lambda n(a_{i}-a_{y_{i},i}e_{y_{i}})\in\Delta^{\alpha}_{k}$. Using $c=\mathbf{1}-e_{y_{i}}$ and $\left\langle\mathbf{1},a_{i}\right\rangle=0$, one can simplify it to

and the feasibility constraint can be re-written as

For the regularization term $\operatorname{tr}\left(AKA^{\top}\right)$, we have

We let $q=\sum_{j\neq i}K_{ij}a_{j}=AK_{i}-K_{ii}a_{i}$ and $x=-a_{i}^{\!\setminus y_{i}}$:

Now, we plug everything together and multiply with $-2/\lambda$.

Collecting the corresponding terms finishes the proof. ∎

C.2 Proof of Proposition 15

Let $v\triangleq-\lambda na_{i}$ and $y=y_{i}$. Using Proposition 3,

where $\left\langle\mathbf{1},v\right\rangle=0$ and $v^{\!\setminus y}\in\Delta^{\alpha}_{k}$. Let $x\triangleq v^{\!\setminus y}$ and $s\triangleq-v_{y}$. We have $s=\left\langle\mathbf{1},x\right\rangle$ and from $\operatorname{tr}\left(AKA^{\top}\right)$ we get

where $q=\sum_{j\neq i}K_{ij}a_{j}=AK_{i}-K_{ii}a_{i}$. Finally, we plug everything together as in Proposition 14. ∎

C.3 Proof of Proposition 16

Note that only $x_{j}>0$ and $s<1$ satisfy the above constraints, which implies $\mu_{j}=0$ and $\lambda=0$. We re-write the above as

These equations correspond to the Lambert $W$ function of the exponent, $V(t)=W(e^{t})$, discussed in § 5.1. Let $p\triangleq\left\langle\mathbf{1},\nu\right\rangle$ and re-define $t\leftarrow 1+t-\log\alpha$.

Note that $V(t)$ is a strictly monotonically increasing function, therefore, it is invertible and we can write

Next, we use the definition of the sets $U$ and $M$,

Let $\rho\triangleq\tfrac{\left|U\right|}{k}$ and $A\triangleq\tfrac{1}{k}\operatorname{\textstyle\sum}_{U}b_{j}$, we get

Finally, we eliminate $p$ and obtain the system:

Moreover, when $U$ is empty, it simplifies into a single equation

C.4 Proof of Proposition 17

We continue the derivation started in the proof of Propostion 4. First, we write the system that follows directly from the KKT optimality conditions.

Next, we define the two index sets $U$ and $M$ as follows

Note that the set $U$ contains at most $k$ indexes corresponding to the largest components of $a_{j}$. Now, we proceed with finding a $t$ that solves (24). Let $\rho\triangleq\frac{\left|U\right|}{k}$. We eliminate $p$ as

Let $Z\triangleq\sum_{M}\exp a_{j}$, we write for $s$

Let $A\triangleq\tfrac{1}{k}\sum_{U}a_{j}$. We further write

which yields the following equation for $s$

We note that: a) $Q$ is readily computable once the sets $U$ and $M$ are fixed; and b) $Q=1/Z$ if $k=1$ since $\rho=A=0$ in that case. This yields the formula for $t$ as

As a sanity check, we note that we again recover the softmax loss for $k=1$, since $t=\log Z+\log(1+1/Z)=\log(1+Z)=\log(1+\sum_{j}\exp a_{j})$.

To verify that the computed $s$ and $t$ are compatible with the choice of the sets $U$ and $M$, we check if this holds:

C.5 Proof of Proposition 18

where $\lambda>0$ is a regularization parameter. Equivalently, we can divide both the primal and the dual objectives by $\lambda$ and use $C\triangleq\frac{1}{\lambda n}>0$ as the regularization parameter instead. The optimization problem becomes

where the ${\rm const}$ does not depend on $a$. We ignore that constant in the following derivation and also define an auxiliary vector $q\triangleq\sum_{j\neq i}K_{ij}a_{j}=AK_{i}-K_{ii}a_{i}$ . Plugging the conjugate from Proposition 6 into (25), we obtain

We re-write the constraint $-\frac{1}{C}a\in S_{Y_{i}}$ as

and switch to the equivalent minimization problem below.

The final projection problem for the update step is

C.6 Proof of Proposition 19

We sketch the main parts of the proof that show correctness of the algorithm. A complete and formal derivation would follow the proof given in .

The Lagrangian for the optimization problem (17) is

and it leads to the following KKT conditions

If $\rho=0$, the solution is trivial. Assume $\rho>0$ and let

where $t$, $s$ are the dual variables from (27) and we have

and similar sets $I_{y}$, $L_{y}$ for $y$. Solving a reduced subproblem

for $t$ and a similar problem for $s$, yields

We consider two cases: $r=\rho$ and $r<\rho$. If $r=\rho$, then we have two variables $t$ and $s$ to optimize over, but the optimization problem (17) decouples into two simplex projection problems which can be solved independently.

Let $t^{\prime}$ and $s^{\prime}$ be solutions to the independent problems (29). If $t^{\prime}+s^{\prime}\geq 0$, we have that the KKT conditions (27) are fulfilled and we have, therefore, the solution to the original problem (17). Otherwise, we have that the optimal $t^{*}+s^{*}>t^{\prime}+s^{\prime}$ and so at least one of the two variables must increase. Let $t^{*}>t^{\prime}$, then $\left\langle\mathbf{1},x(t^{*})\right\rangle<\left\langle\mathbf{1},x(t^{\prime})\right\rangle=\rho$, therefore $r^{*}<\rho$.

If $r<\rho$, then $t+s=0$. We eliminate $s$, which leads to