domain: math info

text:
Merci Nicolas

Elisabeth

Anne Domitille

Keywords: apprentissage profond, apprentissage statistique, classification d'images, classificateurs à valeurs d'ensembles, fonctions de perte deep learning, statistical learning, image classification, set-valued classification, loss functions

La dernière décennie a été marquée par l'émergence et l'essor des techniques d'apprentissage profond, conduisant à d'énormes progrès dans la vision artificielle, le traitement du langage naturel et la reconnaissance vocale. Ces avancées sont dues aux améliorations matérielles et aux nouvelles architectures, notamment les réseaux neuronaux convolutifs et les transformers, utilisées dans des applications populaires telles que Siri, Deepl, et ChatGPT. Un défi majeur du domaine de la vision artificielle a été ImageNet, une base de données d'un million d'images réparties en 1 000 classes, utilisée comme référence pour mesurer les performances des modèles. Les premiers résultats affichaient une erreur top-1 de 37,5%, tandis que les meilleurs modèles atteignent maintenant 9% d'erreur top-1. Cependant, ImageNet diffère des situations réelles car elle présente des classes artificiellement équilibrées et peu de similarités entre elles. Pour relever des défis plus réalistes, il est essentiel de se concentrer sur des tâches de catégorisation visuelle à grain fin, impliquant des classes similaires et des distributions déséquilibrées avec des classes rares. Pour ce faire, dans cette thèse nous prendrons pour cas d'étude Pl@ntNet, une application écologique basée sur l'apprentissage coopératif, qui permet aux utilisateurs d'identifier les plantes à partir d'images. Dans un tel contexte d'ambiguïté, les classificateurs multi-classes traditionnels qui ne renvoient qu'une seule proposition de classe ne suffisent pas. C'est pourquoi dans ce manuscrit nous étudierons les classificateurs à valeurs d'ensembles, qui retournent pour chaque image un ensemble de classes possibles. Les classificateurs à valeurs d'ensembles sont utiles s'ils renvoient un nombre restreint de classes pour chaque image. Ainsi, il existe plusieurs contraintes sur la taille des ensembles retournés. Dans cette thèse, nous étudions deux types de contraintes: une contrainte de taille ponctuelle, où le classificateur renvoie exactement K classes candidates pour chaque exemple (classification top-K), et une contrainte sur la taille moyenne des ensembles retournés (classification average-K). Afin d'optimiser ces classificateurs à valeurs d'ensembles, nous introduisons de nouvelles fonctions de perte pour améliorer les performances des modèles d'apprentissage profond, une pour chaque type de contrainte. La fonction de perte pour la classification top-K se base sur une fonction de perte charnière combinée à un lissage de la fonction top-K. Pour la classification average-K, nous proposons un modèle à deux têtes, où une tête est chargée d'identifier des classes candidates pour un example donné, et l'autre tête optimise ces suggestions avec une entropie croisée binaire. Les expériences sont menées sur un jeu de données crée à partir des données de Pl@ntNet, Pl@ntNet-300K, constitué de 306 146 images de plantes avec une forte déséquilibre de classes et des ambiguïtés visuelles importantes. Les résultats montrent que les nouvelles fonctions de perte améliorent significativement les performances par rapport à l'entropie croisée, en particulier dans les situations où l'incertitude est élevée.

INTRODUCTION

Notation

L number of classes

[L] set of all classes {1, • • • , L} [L] K set of all subsets of [L] of size K K Integer in [L] ∆ L-1 simplex, {p ∈ R L , p ≥ 0, L i=1 p i = 1} ∆ L-1 K top-K simplex, {p ∈ R L , 0 ≤ p ≤ 1, L i=1 p i = K} 2 [L]
set of all subsets of The last decade has seen the emergence and boom of deep learning techniques. Staggering progress was made in computer vision [START_REF] Voulodimos | Deep learning for computer vision: A brief review[END_REF], natural language processing [START_REF] Khurana | Natural language processing: State of the art, current trends and challenges[END_REF] and speech recognition [START_REF] Bou | Speech recognition using deep neural networks: A systematic review[END_REF]. This progress is largely linked with progress in hardware to execute rapid matrix products [START_REF] Raina | Large-scale deep unsupervised learning using graphics processors[END_REF]. It is also due to the emergence of novel architectures, such as convolutional neural networks [START_REF] Lecun | Handwritten digit recognition with a back-propagation network[END_REF] and transformers [START_REF] Vaswani | Attention is all you need[END_REF], that have now been widely adopted. This upheaval has had repercussions on many technological tools (Siri, Deepl, ChatGPT, etc.) used by billions of people around the world.

Since then, the community has always strived to solve ever more challenging problems. The toy tasks that served for the first developments of the domain are now considered solved [START_REF] Krizhevsky | Learning multiple layers of features from tiny images[END_REF][START_REF] Lecun | Gradientbased learning applied to document recognition[END_REF]. In computer vision, ImageNet [START_REF] Russakovsky | ImageNet Large Scale Visual Recognition Challenge[END_REF] has been a key challenge for researchers and practitioners. It is a database of more than 1M images and 1000 classes that was released in 2012. It is a recognized benchmark that has created a lot of emulation to reach ever-better levels of performance. The results in the seminal paper reported a top-1 error of 37.5%. Currently, the best models achieve only 9% top-1 error. While there may still be some improvements to gain, there is a need to turn to more realistic tasks. Indeed, ImageNet was crafted from web images, with classes that have little in common and are organized in a balanced way. It is different from real-world projects that can count several thousands of classes, many of which differ only via subtle variations. This is known as Fine-Grained Visual Categorization: the fine distinction of similar classes [START_REF] Wei | Deep learning for fine-grained image analysis: A survey[END_REF]. This arises in many situations: the categorization of different species, motorcycle models, architectural styles, etc. In addition, ImageNet was artificially balanced, meaning that all classes approximately share the same number of training examples. Again, this is an ideal setup. In reality, this balance rarely occurs in real life. The Pareto principle [START_REF] Barry | Pareto distribution[END_REF] is everywhere: a few classes account for the majority of examples. The problem with classical datasets like ImageNet is that they occult these aspects. When faced with real-world problems, we must deal with similar classes and long-tailed distributions. In this thesis, we will investigate these two aspects:

• How to deal with ambiguous classes?

• Can we obtain good performance in the long-tail, i.e., on classes with few examples?

To tackle this, we need data representative of what happens in real life, with ambiguous and imbalanced classes. Throughout this thesis, we will use data collected by an ecological, crowd-sourced application: Pl@ntNet [START_REF] Affouard | Pl@ntNet app in the era of deep learning[END_REF].

The Pl@ntNet project

Pl@ntNet is a participatory platform for the production, aggregation and dissemination of botanical observations supported by four founding organizations: CIRAD, INRA, Inria and IRD. Initiated in 2009, the visibility and use of this platform have accelerated since February 2013, with its deployment on mobile platforms (IOS in 2013, and Android in 2014). The application enables users to recognize plants, trees and flowers they encounter in the wild. Since 2013, the Pl@ntNet project has grown impressively: the number of users has doubled every year, reaching more than 20 million in 2022. An impact study concluded that the platform is having a strong societal and economic impact, with 12% of users exploiting it in a professional context in various fields, including agronomy, education, research, commerce and tourism. Figure 1.1 summarizes key milestones for the Pl@ntNet project.

Nowadays, the project counts several engineers, researchers and students to work full time on improving the application. In 2023, the application covers around 43 000 species all over the world. Since the beginning of the project, 800 million plants have The workflow of the application is shown in Figure 1.2. Pl@ntNet is based on a cooperative learning principle. The schematic operation is as follows: first, a Pl@ntNet user generates a plant observation in the field. The observation is then automatically identified by a neural network and some candidate species are returned to the observer for confirmation. All observations are stored in a database and can be reviewed by the community. A user can typically confirm the initial species name shared by the observer (often with the help of the neural network) or propose an alternative species name. Only the observations that reach a sufficient degree of confidence are labeled as valid observations and are added to the training set of the AI model.

The benefits of such a project are numerous. There is of course a pedagogical interest: users get to learn about their environment. Furthermore, Pl@ntNet contributes to the conservation of biodiversity by involving citizens in the collection of data on plant species. Indeed, by encouraging users to upload images of plants they encounter, Pl@ntNet helps create a large-scale database of plant observations. This data provides valuable insights into the distribution and abundance of various plant species, aiding researchers, conservationists, and policymakers in making informed decisions about biodiversity conservation. The data collected by Pl@ntNet is now one of the main sources of plant occurrence data worldwide [START_REF] Nigel Ca Pitman | Identifying gaps in the photographic record of the vascular plant flora of the Americas[END_REF]. They are integrated in the GBIF infrastructure, the world's largest network providing open access to biodiversity data (funded by governments).

However, with the growing number of species covered by the application, it is getting harder to come up with the true species corresponding to the image, as the number of possible ambiguities between species grows with the total number of classes.

Set-valued classification

Indeed, consider a classifier h : X → [L], where X is the image input space, L the number of classes (species), and [L] := {1, . . . , L}. Assume the pairs of image/label (X, Y ) are generated by an unknown probability distribution P. The risk, or error rate, corresponds to the probability of misclassification: R(h) := P(Y ̸ = h(X)) .

(1.1)

The optimal classifier (Bayes classifier) h * : X → [L] returns the most likely class for each input image x ∈ X : (1.3)

h * (x) = arg max
We can see that the risk is small whenever the quantities max l∈{1,...,L} P(Y = l|X = x) are large, i.e., when given an image x, one class is much more plausible than the other ones. This happens for easy problems, e.g., when the number of classes is small and the classes have little in common. This case typically corresponds to the MNIST dataset, which is a dataset of handwritten digits where each class represents a digit. The classes are easily distinguishable one from another and ambiguity is quasi non-existent. Some images of the database are shown in Figure 1.3. However, for real applications like Pl@ntNet, this assumption of low ambiguity does not hold: there are tens of thousands of classes, and many species share important visual traits. This is particularly true for species that belong to the same family. They sometimes differ only by slight variations in leaf shape or color. An example of two similar classes is available in Figure 1. 4 On top of that, when someone takes a picture of a plant, it is only a partial representation of that object. The user might zoom into a part of the plant but miss a discriminative feature of this species. For instance, some species differ only by the shape of the leaf, with identical flowers. This is illustrated in Figure 1.5. In that case, if the user only photographs the flower, several species will be possible, and returning a single one will likely result in a mistake. In such cases, the risk becomes high, meaning that even the best possible classifier will achieve low accuracy. This is problematic for various reasons. For example, an endangered species could be wrongly classified as an invasive species, with dramatic consequences (e.g., uprooting of the plant).

One way to alleviate this issue is to consider classifiers that do not return merely a single class, but a set of candidate classes, i.e., set-valued classifiers: Γ : X → 2 [L] , where 2 [L] is the power set of [L]. The associated minimization problem then reads:

min Γ R(Γ) := P(Y / ∈ Γ(X)) (1.4)
In practice, this is what Pl@ntNet does: it returns a list of species to the user. Each suggestion has an associated score, with higher scores indicating higher probability.

On the set size

The solution to Equation (1. 4) is trivial: it is the classifier that returns all classes for each input image x: Γ(x) = [L]. This results in a classifier with zero risk. However, such a classifier is completely useless. With this trivial example, we can understand easily that a set-valued classifier is informative only if it returns a few classes. For instance, in the Pl@ntNet context, we must always bear in mind the person that is going to use the application in the wild to recognize a plant. Is it useful if we make more than 100 suggestions? Probably not. On top of that, there are constraints linked to the device: a smartphone can not display dozens of species images on the screen. Therefore, for practical as well as user experience reasons, we are constrained in the set size. For an application like Pl@ntNet, it should not exceed let us say ten candidates. So really the problem we will look into is:

min Γ R(Γ) := P(Y / ∈ Γ(X)) (1.5) s.t. S(Γ) ≤ K , ( 1.6)
where S(Γ) denotes a constraint on the size of Γ and K the size constraint. In this thesis, we will consider the case where K ≥ 1 for the reasons stated above. We will consider K to be an integer, although it can be a real number. In this manuscript, we will study two types of constraint S: a pointwise size constraint and an average size constraint.

Top-K classification

The first type of constraint we will study is a pointwise constraint:

|Γ(x)| ≤ K, ∀x ∈ X . (1.7)
This is the simplest case: for each input image x, the classifier returns K classes exactly. This is known as top-K classification [START_REF] Lapin | Top-k multiclass SVM[END_REF]. We reduce the risk by allowing the classifier to return K ≥ 1 candidate classes for each example. While this is effective and rather simple to study, it has a drawback: precisely that the classifier returns the same number of classes for each example. Yet, the ambiguity depends on the image. Some images are well zoomed and depict an "easy" species (easily distinguishable from the other ones), in which case a set of size one suffices. Other images are particularly hard to handle and necessitate large sets. It is not a one size fits all.

INTRODUCTION

Average-K classification

To tackle this, we consider another constraint, this time an average size constraint:

E X |Γ(X)| ≤ K, ∀x ∈ X . (1.8)
This is known as average-K classification [START_REF] Denis | Confidence Sets with Expected Sizes for Multiclass Classification[END_REF]. The constraint is on the average size of the classifier. This allows for flexibility over the previous setting. Indeed, in this setup, the classifier is allowed to return variable-sized sets. This allows to return more classes when needed, and less for non-ambiguous samples.

Relevance of set-valued classifiers?

The risk of (1.5) is lower than that of (1.1) since we now allow the classifier to return multiple classes. So what is the catch? What is the price if we get less error? Well, we lose in informativeness. Although returning a single class will result in a high risk, it has the merit of clarity and simplicity. We provide an answer to the query, the user is provided with a species name. It might not be the correct one, but maybe the user will not notice it. This is not a very satisfactory solution, however. We feel that the set solution is more appropriate. However, if we simply return a set of size e.g., three with three species names, this is not satisfactory either. The user wants to have a clue as to what the true species is. This can be solved by adding extra information on the candidate classes. In Pl@ntNet, for instance, there is a similarity search procedure that displays, for each species suggestion, the images of that species most similar to the query image. This is illustrated in Figure 1.6. This way, the user has additional material to make his decision.

Notice that the traditional multi-class classifier Γ : X → [L] corresponds to the particular case of a set-valued classifier that always returns sets of size one.

Estimation of set-valued classifiers

In practice, we can not solve (1.5). The reason is that we do not know P. Instead, we have access to n train i.i.d. samples (x 1 , x 1 ), . . . , (x n train , y n train ) drawn from P. From these samples, we want to train a classifier to predict a relevant set of classes given a new image x. How to proceed? We first need to choose what kind of classifier to consider. In this thesis, we will consider deep learning models for their remarkable performances in computer vision tasks.

For now, let us assume that we have a trained deep model f that predicts a vector of scores f (x) ∈ R L given an image x ∈ X . How can we go from there to predict a set of candidate classes for input x? There is a natural plug-in way to construct these sets once we have an estimation of the scores (or equivalently of the conditional probabilities). In the top-K case, it suffices to return the top-K largest estimated scores (or equivalently conditional probabilities):

Γ(x) = T K ( f (x)) ,
(1.9) where T K : R L → [L] K is the operator that returns a set containing the K indices corresponding to the K largest value of a vector.

For the average-K case, the set predictor is obtained by thresholding the conditional probabilities on a calibration set, where the threshold is chosen to satisfy the average size constraint. We will detail this later.

The main question resides in how to learn to predict relevant sets, i.e., sets that contain the ground truth label. This translates into the following question: how to train the model? The recipe for training a deep learning model is to use a loss function ℓ : R L × [L] → R + , compute its gradient w.r.t. the predictions with backpropagation, and update the weights with SGD for instance. The most standard loss function to use is the cross-entropy loss. In this manuscript, the main question we try to answer is the following:

INTRODUCTION

• Is it possible to design loss functions that perform better than cross-entropy on real-world datasets (long-tailed distribution + class ambiguity) for set-valued classification?

Organization and contributions

The organization of the thesis is as follows:

In Chapter 2, we first list the topics related to the work presented in this manuscript. We then present an overview of set-valued classification methods before explaining the difference between conformal prediction and our work. Then, we derive the expressions of the Bayes top-K and average-K classifiers and explain how to estimate and evaluate such classifiers. We then explain the difference between top-K and average-K classification. Finally, we introduce the notion of surrogate loss functions and top-K and average-K consistency.

In Chapter 3, we present Pl@ntNet-300K, a novel image dataset with high intrinsic ambiguity and a long-tailed distribution built from the database of Pl@ntNet citizen observatory. It consists of 306 146 plant images covering 1 081 species. We highlight two particular features of the dataset, inherent to the way the images are acquired and to the intrinsic diversity of plants morphology: (i) the dataset has a strong class imbalance, i.e., a few species accounts for most of the images, and, (ii) many species are visually similar, rendering identification difficult even for the expert eye. These two features make the present dataset well-suited for the evaluation of set-valued classification methods and algorithms. Therefore, we recommend two set-valued evaluation metrics associated with the dataset (macro-average top-K accuracy and macroaverage average-K accuracy) and we provide baseline results established by training deep neural networks using the cross-entropy loss. We will present its main characteristics. This dataset will be the main support for our subsequent experiments.

In Chapter 4, we introduce a stochastic top-K hinge loss inspired by recent developments on top-K calibrated losses. Our proposal is based on the smoothing of the top-K operator building on the flexible "perturbed optimizer" framework. We show that our loss function performs very well in the case of balanced datasets while benefiting from a significantly lower computational time than the state-of-the-art top-K loss function. In addition, we propose a simple variant of our loss for the imbalanced case. Experiments on Pl@ntNet-300K show that our loss function significantly outperforms other baseline loss functions.

In Chapter 5, we propose an approach for the much challenging average-K classification. A simple method to solve this task is to threshold the softmax output of a model trained with the cross-entropy loss. This approach is theoretically proven to be asymptotically consistent, but it is not guaranteed to be optimal for a finite set of samples. In this paper, we propose a new loss function based on a multi-label classification head in addition to the classical softmax. This second head is trained using pseudo-labels generated by thresholding the softmax head while guaranteeing that K classes are returned on average. We show that this approach allows the model to better capture ambiguities between classes and, as a result, to return more consistent sets 1.4. Publications of possible classes. Experiments on two datasets from the literature demonstrate that our approach outperforms the softmax baseline, as well as several other loss functions more generally designed for weakly supervised multi-label classification. The gains are larger the higher the uncertainty, especially for classes with few samples (this work is currently under review: [START_REF] Garcin | A two-head loss function for deep Average-K classification[END_REF]) Finally, we conclude in Chapter 6. We take this opportunity to present work in progress on a multi-label loss that has been inspired by work on set-valued classification. This loss function is based on the orthogonal projection onto the top-K simplex. It has good theoretical properties, which we shall present briefly.

Publications

The work presented in this thesis led to two publications and one paper currently under review: There are a certain number of topics that are related to set-valued classification that we will not explore in this manuscript. They are presented here for the sake of completeness.

Curriculum learning

Curriculum learning (CL) is a field of machine learning that aims at optimizing the order in which the examples are fed to the model. In general batch gradient descent, the order is random. CL has its roots in human behavior, where learning starts with basic concepts/notions and then progressively extends to harder tasks. The challenge is then to estimate each example's difficulty and find a suitable schedule. The idea originated in [START_REF] Bengio | Curriculum learning[END_REF]. A comprehensive survey can be found in [START_REF] Wang | A survey on curriculum learning[END_REF]. Since Pl@ntNet comprises examples of various difficulties (e.g., well zoomed, easy species and blurry, ambiguous species), it would be an interesting object of study for CL techniques. However, this is an avenue we will not be exploring in this manuscript.

Classification with reject option

Classification with reject option [HW06; CDM16] allows the classifier to abstain from making a decision for a fraction of inputs. In addition to the traditional classifier h : X → [L], there is a rejector r : X → {0, 1}. The global prediction consists of the prediction of h if the rejector r does not reject the sample, otherwise, no prediction is made.

While this allows us to reduce the risk by discarding hard examples, this approach in our case is unsatisfactory for several reasons:

• This may lead the classifier to abstain from answering for challenging instances, which are arguably the most interesting ones. Indeed, in the case of highly similar species, the model may hesitate between multiple species, not returning a strong signal for a single one. In the case of a reject option, the model might reject such an example. Instead, in set-valued classification, the classifier will return several species for that example. With the similarity search engine and additional information e.g., the web, the user can then make up his mind to determine which is the true species among the proposed set.

• From a user experience point of view, it is best to return suggestions regardless of their relevance.

In fact, the Pl@ntNet pipeline already includes a rejector. It allows to reject images that are not plants or of poor quality. In Chapter 3, the dataset is constructed with filtered images. Thus, it contains only relevant pictures of good quality, for which we want to make a prediction. Therefore, in the rest of the thesis, we will consider classifiers that return a set of species for all input images x.

Hierarchical classification

Hierarchical classification [Gor87; SF11b] deals with classification when there is a structure on the labels, typically a tree structure. This is true for most problems where labels are organized in a certain way. For instance, CIFAR100 counts 100 classes that are divided into 20 superclasses (e.g., flowers, people, reptiles) each containing 5 classes. In ImageNet a tree structure also exists between the labels although it is much more complex than CIFAR100. In the case of plant species, there exists a hierarchy established by botanists: species are grouped into genera, which are organized into families. . . This hierarchy respects biological realities: species belonging to the same genus derive from a common ancestor and usually share important morphological features.

Several works [DKS04; DC00; KS97; CB+04] have proposed methods and algorithms to use this structure on labels. Although Pl@ntNet lends itself well to hierarchical classification, this an avenue we will not pursue in this thesis.

Multi-label classification

Set-valued classification should not be confused with multi-label classification. Both settings are different. The difference resides in the label space Y. For multi-label classification [Dem+12; Liu+21; ZZ14], several labels may be associated with an image x: Y = 2 [L] , whereas in set-valued classification a single class is present on the image: Y = [L]. For instance, in the Pl@ntNet application, the users are incentivized to take a clear, zoomed picture of a single plant. This is illustrated in Figure 2.1. Again, we stress that throughout this thesis, only a single label will be associated to each input image x. In particular, all our experiments will be on multi-class datasets, i.e., datasets for which a single label is associated with an image. This is different than multi-label datasets [Lin+14; Eve+10].

Set-valued classication

Overview

Set-valued classification [START_REF] Chzhen | Set-valued classification -overview via a unified framework[END_REF] relates to classifiers Γ : X → 2 [L] that return a set of classes instead of a single class in the context of multiclass classification. There are two key fundamental properties of a set-valued classifier: its -output-size and its risk. There is a tradeoff to make: increasing the size of the classifier will lower its risk but at the cost of informativeness. There are two "dual" ways to look at the problem. Either we minimize the risk with a constraint on the set size, or we minimize the set size with a constraint on the risk. Let us introduce some notation pertaining to these two properties. For a set-valued classifier Γ and an input x ∈ X , we define:

S (Γ, x) = |Γ(x)| point-wise size (2.1) S (Γ) = E X |Γ(X)| average size (2.2) R(Γ, x) = P(Y / ∈ Γ(X)|X = x) point-wise error (2.3) R(Γ) = P(Y / ∈ Γ(X)) average error (2.4)
Several set-valued formulations exist, depending on the type of constraint and error. We summarize these formulations in Table 2.1. We refer the reader to [START_REF] Chzhen | Set-valued classification -overview via a unified framework[END_REF] for an overview of these methods. The authors give the Bayes classifier for each formulation. In this manuscript, we only focus on the point-wise size and average-size formulations, also known as top-K and average-K classification respectively. The reason is that in the scope of the Pl@ntNet project, as already mentioned, we need control over the size of the predicted sets. The point-wise error and average error do not provide such guarantees and can yield very large sets for some examples. However, some applications require guarantees on the risk (error rate) and would rather have large sets but with a controlled risk. For instance, in disease diagnosis [ALS22; Bat+20], it is best to return a large set of possible diseases than to miss a potentially fatal one. Note that no formulation is better than others. Instead, they correspond to different use cases, and one should choose the most appropriate given the problem at hand.

Conformal prediction

Conformal prediction [VGS05; SV08; FZV23] can also be counted in the set-valued classification methods, as it returns a set of classes for each example. The aim of conformal prediction is to return a set of classes for a test example, such that the probability of the true class to be in the set is larger than a user-defined threshold. Let us describe here the recipe of conformal prediction. Assume we have a model p that gives an estimate of the class conditional probabilities p(x) ∈ R L given an example x ∈ X . Typically, p(x) is the softmax output of a deep learning model trained with cross-entropy. The idea is to calibrate the output of the model. To this end, we use a set of n input/label pairs, unseen during training, (X 1 , Y 1 ), . . . , (X n , Y n ). Then, a

, x) = |Γ(x)|, S (Γ) = E X |Γ(X)|, R(Γ, x) = P(Y / ∈ Γ(X)|X = x) and R(Γ) = P(Y / ∈ Γ(X)).

Name Minimization objective Constraint References

Point-wise size

R(Γ) S (Γ, x) ≤ K [LHS15; LHS16; LHS17] Average size R(Γ) S (Γ) ≤ K [DH17]
Point-wise error

S (Γ) R(Γ, x) ≤ ϵ [FB+21; Lei14; LW14; RSC20] Average error S (Γ) R(Γ) ≤ ϵ [SLW19]
calibration score quantifying the uncertainty of the true label is computed for each example. For instance, the score can be computed as c i := 1p(X i ) Y i i.e., one minus the softmax output of the true class. We then define q to be the ⌈(n+1)(1-α)⌉ n empirical quantile of c 1 , . . . c n . Finally, given a test example X test , the predicted set for X test is defined to be: S (X test ) := {j, pj (X test ) ≥ 1 -q}. With this simple procedure, we obtain the following result:

1 -α ≤ P(Y test ∈ S (X test )) ≤ 1 -α + 1 n + 1 (2.5)
Notice that this result holds regardless of whether p estimates the conditional probabilities P(Y = l|X = x) well or not. Equation (2.5) means that we can guarantee the true class lies in the returned set with a level of confidence desired by the user. Conformal prediction allows to return sets of variable size, as the average-K setting. However, much like the point-wise error and average error setting evoked earlier, we have no guarantee on the set size. Again, in the context of Pl@ntNet, this is not a viable solution. However, conformal prediction appears like a pertinent choice for applications that need strict control of the risk, as Equation (2.5) gives a strong certificate. Finally, notice that for the calibration set, we need annotated data. Indeed, we use both the input X i and its label Y i . Annotated data can be costly when it requires the careful examination of one or several experts e.g., in medical applications. Instead, in average-K classification, the "calibration step" for the estimation of the threshold does not necessitate labeled data. This is a significant advantage since unannotated data often comes in plentiful and cheap.

We only presented here the application of conformal prediction to classification as this thesis deals with set-valued classification. However, conformal prediction is a broader framework that could also be applied to regression problems for instance.

Top-K classification

Bayes classifier.

Top-K classification [START_REF] Lapin | Top-k multiclass SVM[END_REF] corresponds to the case where, for each image, K suggestions are allowed. The problem becomes:

min Γ P(Y / ∈ Γ(X)) (2.6) s.t. |Γ(X)| ≤ K (2.7)
The Bayes classifier corresponds to the classifier that returns the K most probable classes. Indeed, we have:

P(Y / ∈ Γ(X)) = 1 -P(Y ∈ Γ(X)) (2.8) = 1 -E(1(Y ∈ Γ(X))) (2.9) = 1 -E X E Y |X (1(Y ∈ Γ(X))) (2.10) = 1 -E X L l=1 1(l ∈ Γ(X))p l (X) , (2.11)
which is minimized by predicting the K indices corresponding to the top-K largest conditional probabilities for every x ∈ X :

Γ * (x) = T K (p(x)) , (2.12)
where p(x) ∈ R L is the vector of conditional probabilities i.e., p l (x) = P(Y = l|X = x)

Estimation.

In practice, the conditional probabilities p l (x) are unknown and one ought to estimate them, typically by training a deep neural network with the cross-entropy loss. With the estimated conditional probabilities pl (x), we can then naturally define the plug-in estimator:

Γ(x) = T K (p(x)) ,
(2.13)

where p(x) ∈ R L is the vector of estimated conditional probabilities.

Note that (2.13) and (2.12) coincide when the top-K largest estimated conditional probabilities match the top-K largest true conditional probabilities. In particular, the order in which the estimated conditional probabilities are ranked does not matter, as long as they are in the top-K predictions. Note that Chapter 4 will present a method that does not require to estimate the conditionnal probabilities as this could be tricky in the context of high noise and little data. Instead, we work directly with the scores (or logits) and try to place the score of the true label in the top-K scores (i.e., the top-K highest scores).

Evaluation.

Given a test set (x 1 , y 1 ), . . . , (x ntest , y ntest ), we can evaluate a top-K classifier by computing the top-K accuracy. Formally:

Top-K accuracy = 1 n test ntest i=1 1 [y i ∈ T K (p(x i ))] (2.14) Compared to a multi-class classifier h : X → [L] with risk P(Y ̸ = h(X)), top-K classification yields a top-K classifier Γ : X → [L] K with risk P(Y /
∈ Γ(X)) Therefore, top-K classification lowers the risk by predicting K classes for each example. This is already an interesting study case that we will tackle in Chapter 4. However, this approach presents a shortcoming: it treats each example the same way by returning K classes for each example, regardless of the difficulty of each example. The next setting allows us to take that ambiguity into account.

Average-K classification

Bayes classifier.

Average-K classification [START_REF] Denis | Confidence Sets with Expected Sizes for Multiclass Classification[END_REF] has a constraint looser than top-K classification: the constraint on the set size is not anymore on each example, but rather a global constraint on the average set size:

min Γ P(Y / ∈ Γ(X)) (2.15) s.t. E X |Γ(X)| ≤ K (2.16)
This constrained optimization problem has the same solution as the following minimization problem [START_REF] Thien | The optimum class-selective rejection rule[END_REF]:

min Γ P(Y / ∈ Γ(X)) + λE X |Γ(X)| , ( 2.17)
where the relation between K and λ is derived next. Note that:

P(Y / ∈ Γ(X)) + λE X |Γ(X)| = E X,Y (1[Y / ∈ Γ(X)] + λ|Γ(X)|) (2.18) = E X E Y |X (1[Y / ∈ Γ(X)] + λ|Γ(X)|) (2.19) = E X L l=1 p l (X)1[Y / ∈ Γ(X)] + λ|Γ(X)| (2.20) = E X   1 - l∈Γ(X) p l (X) + λ l∈Γ(X) 1   (2.21) = E X   1 + l∈Γ(X) (λ -p l (X))   , (2.22)
which is minimized by predicting, for all x ∈ X , all classes l such that p l (x) ≥ λ.

Thus the Bayes classifier is:

Γ * λ (x) = {l, P(Y = l|X = x) ≥ λ} (2.23)
The parameter λ must be set so that on expectation K classes are returned. The expected number of classes is given by:

G(λ) := E X |Γ * λ (X)| = E X L l=1 1(l ∈ Γ * λ (X)) (2.24) = L l=1 P X (l ∈ Γ * λ (X)) (2.25) = L l=1 P X (p l (X) ≥ λ) .
(2.26)

The "right" λ, which we denote by λ * , is the one that will give a value of G equal to K. The G function is not necessarily invertible, so we will consider the generalized inverse function to obtain the threshold:

λ * = G -1 (K) := inf{λ, G(λ) ≤ K} . (2.27)
Finally, the expression of the Bayes classifier is:

Γ * (x) = {l, P(Y = l|X = x) ≥ G -1 (K)} (2.28) Estimation.
As in the top-K case, we first need to get an estimate of the conditional probabilities to define our plug-in classifier. This can be achieved by training a deep neural network with the cross-entropy. Once this is done, there is a calibration step. We need to estimate the threshold. Given a calibration set {x 1 , . . . , x n } of unseen samples, we first estimate the G function as follows:

Ĝ(t) = 1 n n i=1 L i=1 1[p l (x i ) ≥ t] .
(2.29)

The estimated threshold is then computed as:

λ := Ĝ-1 (K) .
(2.30)

Finally, we can define our plug-in classifier as:

Γ(x) = {l, pl (x) ≥ Ĝ-1 (K)} (2.31)
Notice that for the calibration step (2.29), we only need unlabeled data to estimate the threshold. This is different than conformal prediction for instance, where labeled data is required for the calibration step. This is a huge advantage since unlabeled data is often abundant and cheap whereas labeled data is more precious and it is best to use as much as possible for the training step.

Evaluation.

To evaluate an average-K classifier on a test set {(x 1 , y 1 ), . . . , (x ntest , y ntest )}, we can compute the average-K accuracy:

Average-K accuracy = 1 n test ntest i=1 1 py i (x i ) ≥ λ , (2.32)
where py i represents the estimated conditional probability of the true class.

Notice that the estimation procedure does not guarantee that the average number of classes returned on the test set 1 n n i=1 L j=1 1 pj (x) ≥ λ is equal to K. In practice, when the calibration set and the test set are sufficiently large, this number is very close to K.

Comparison of top-K and average-K classification

Equations (2.12) and (2.28) are quite different. The top-K Bayes classifier simply predicts the top-K largest conditional probabilities for every x ∈ X . The average-K Bayes classifier predicts all classes whose conditional probabilities are greater a threshold. Therefore, the set size can vary from one example to the other. When a single class has a much higher conditional probability than all of the other ones, the average-K predictor will return a single class, whereas the top-K predictor will return K classes no matter what. On the contrary, when multiple classes are plausible given an image x, the average-K predictor can return a set size greater than K, while the top-K predictor cannot.

When comparing (2.6) and (2.15), it is clear that the average-K Bayes predictor has a lower risk than the top-K Bayes predictor since the constraint is looser. The authors of [LJS21] quantify the difference between the two Bayes classifier. In particular, they provide a lower bound on the gap between the two risks. They conclude that the gain in using average-K over top-K is paricularly important in the case of heterogeneous ambiguity, that is when the level of ambiguity can be very different from on input to another. This is case for Pl@ntNet, as some species are easy to categorize while some species share similarities with many others. However, it is still relevant to study top-K classification, as top-K accuracy is still a widely reported metric and as it is the most intuitive entry point to set-valued classification. In addition, it is much easier to design a loss function for top-K classification as the constraint applies on a per-sample basis, thus permitting a separable loss (i.e. computable sample by sample). For average-K classification, the inputs are coupled via the global constraint λ which makes it much more difficult to design a loss: given an example x ∈ X , how many classes should we return ? It depends on the other samples.

Loss functions

In general, in machine learning, it is not possible to directly minimize the objective we want. Let us consider first the binary case, and say we want to construct a binary classifier h : X → {-1, 1}. To do this, we learn a measurable predictor function f : X → R whose output sign will be the prediction for the target Y . Ultimately, our objective is to minimize the 0/1 loss so that the classifier makes as little mistake as possible (i.e. get as close as possible to the Bayes classifier):

min f E (1[sign(f (X)) ̸ = Y ]) = E (1[f (X)Y ≤ 0]) (2.33) := E (ℓ(f (X)Y )) , (2.34)
where sign(α) is equal to one if α > 0, -1 otherwise and ℓ denotes the 0/1 loss.

However, it is not feasible to optimize the 0/1 loss with traditional algorithms like SGD because it is piecewise constant. Instead, the standard strategy is try to minimize a surrogate loss function ϕ : R → R + , an upper bound of the 0/1 loss. The objective then becomes:

min f E (ϕ(f (X)Y )) .
(2.35) Some ϕ correspond to famous algorithms like support vector machine

[CV95] (ϕ(t) = max(0, 1 -t)), Adaboost (ϕ(t) = exp(-t)) [FS97] or logistic regression (ϕ(t) = ln(1 + exp(-t)))[FHT00]
. These examples can be found in Figure 2.2.

A natural and legitimate question arises: if we manage to minimize (2.35), does it mean that we manage to minimize (2.33) as well? This property is called consistency. In the binary case, the answer is yes, if and only if ϕ satisfies a certain condition. To see that, let us write the conditional ϕ risk for a given x:

E[ϕ(f (X)Y )|X = x] = p 1 (x)ϕ(f (x)) + (1 -p 1 (x))ϕ(-f (x)) (2.36)
Let us remove the dependance on x to obtain the generic conditional ϕ-risk:

R ϕ (α, p) = pϕ(α) + (1 -p)ϕ(-α) (2.37)
We say that ϕ is classification calibrated [BJM06; Zha04; LV04] if, for any p ̸ = 1 2 :

inf α,α(2p-1)≤0 R ϕ (α, p) > inf α∈R R ϕ (α, p) (2.38)
In other words, the optimal predictor's output has the same sign as p -1 2 for all p ̸ = 1 2 . This means that minimizing the risk will always lead to the best possible decision: the class with the largest probability. This is a necessary and sufficient condition for consistency:

Theorem 2.3.1. (from [BJM06]) ϕ is consistent if and only if ϕ is classification-calibrated.
In [START_REF] Peter L Bartlett | Convexity, classification, and risk bounds[END_REF], the authors show that when ϕ is convex, then ϕ is classificationcalibrated if and only if ϕ is differentiable at 0 and ϕ ′ (0) < 0

In the multi-class case [START_REF] Tewari | On the Consistency of Multiclass Classification Methods[END_REF], the conditions to check if a loss is classificationcalibrated are much more complex and no such trivial condition exists.

Let us now turn to the case that interests us, that is to say set-valued classification. We can also define the notion of consistency for top-K and average-K classification. A definition was proposed in [Lor20] for plug-in classifiers based on an estimation of the conditional probabilities. We recall it here. Consider an estimator p(x) ∈ ∆ L-1 of the conditional probability vector p(x), where ∆ L-1 := {p ∈ R L , p ≥ 0, L i=1 p i = 1} denotes the simplex. As already explained, we can construct the top-K plug-in classifier Γtop-K (x) = T K (p(x)), and the average-K plug-in classifier Γaverage-K (x) = {l, pl (x) ≥ Ĝ-1 (K)}. We are interested in the risks of these estimators, respectively R( Γtop-K ) := P(Y / ∈ Γtop-K (X)) and R( Γaverage-K ) := P(Y / ∈ Γaverage-K (X)). As in the binary case, we can not directly minimize these quantities, so instead we minimize a surrogate loss

ℓ : ∆ L-1 × [L] → R + .
Again, the question is: does minimizing this surrogate loss entail minimizing the top-K and average-K risk ? We can also define consistency in the case of top-K and average-K classification [Lor20]: Definition 2.3.2. We say that a loss is top-K consistent if:

R ℓ (p) → R * ℓ =⇒ R( Γtop-K ) → R(Γ * top-K ) (2.39)
Definition 2.3.3. We say that a loss is average-K consistent if:

R ℓ (p) → R * ℓ =⇒ R( Γaverage-K ) → R(Γ * average-K ) , (2.40)
where Γ * top-K and Γ * average-K denote the Bayes top-K and average-K classifier respectively, R ℓ (p) is the ℓ-risk associated to the estimator p: R ℓ (p) := E(ℓ(p(X), Y )), and R * ℓ is the optimal ℓ-risk: R * ℓ := inf p E(ℓ(p(X), Y )).

In [LJS21], the authors show that strongly proper losses are consistent for both top-K and average-K classification. This emcompasses several classical losses, and in particular cross-entropy. This makes the estimation procedures described in Section 2.2.3 and Section 2.2.4 relevant. In [START_REF] Yang | On the consistency of top-k surrogate losses[END_REF], the authors propose a consistent top-K loss but we show in Chapter 4 that it performs poorly for deep classification. We propose a modification of this loss by smoothing the top-K operator. We provide a more in-depth review of existing losses for top-K classification in Chapter 4. To the best of our knowledge no loss tailored for average-K classification exists, hence we propose a method in Chapter 5.

Consistency seems like a desirable condition to have for a surrogate loss. It means that if you manage to minimize the ℓ-risk, you manage to minimize the risk. However, this property remains theoretical. In practice, we have a finite, imbalanced training set that we train our model on and try to predict on a test set. Usually, the value of the loss is much smaller for the training set than for the test set. In addition, for deep-learning models the optimization objective is highly non-convex, meaning that we are not guaranteed to find the optimum within our class of functions. Therefore, although consistency can guide the design of loss functions, it does not presume of the actual performance. We will see later that some consistent losses perform worse than others that do not possess this property. When classifying images, we are faced with two main types of uncertainties [START_REF] Der | Aleatory or epistemic? Does it matter?[END_REF]: (i) the aleatoric uncertainty that arises from the intrinsic randomness of the underlying process, which is considered irreducible, and (ii) the epistemic uncertainty that is caused by a lack of knowledge and is considered to be reducible with additional training data. In modern real-world applications, these two types of uncertainties are particularly difficult to handle. The ever-growing number of classes to distinguish tends to increase the class overlap (and thus the aleatoric uncertainty), and, on the other hand, the long-tailed distribution makes it difficult to learn the less populated classes (and thus increase the epistemic uncertainty). The presence of these two uncertainties is a central motivation for the use of set-valued classifiers, i.e., classifiers returning a set of candidate classes for each image [START_REF] Chzhen | Set-valued classification -overview via a unified framework[END_REF]. Although there are several datasets in the literature that have visually similar classes [NZ08; Maj+13; Yan+15; Rus+15], most of them do not aim to retain both the epistemic and the aleatoric ambiguity present in real-world data.

In this chapter, we propose a dataset designed to remain representative of real-life ambiguity, making it well-suited for the evaluation of set-valued classification methods. This dataset is extracted from real-world images collected as part of the Pl@ntNet project [START_REF] Affouard | Pl@ntNet app in the era of deep learning[END_REF], a large-scale citizen observatory dedicated to the collection of plant occurrences data through image-based plant identification. The key feature of Pl@ntNet is a mobile application that allows citizens to send a picture of a plant they encounter and get a list of the most likely species for that photo in return. The application is used by more than 20 million users in about 170 countries and is one of the main data publishers of GBIF1 , an international platform funded by the governments of many countries around the world to provide free and open access to biodiversity data. Another essential feature of Pl@ntNet is that the training set used to train the classifier is collaboratively enriched and revised. Nowadays, Pl@ntNet covers over 43K species illustrated by nearly 12 million validated images.

The entire Pl@ntNet database would be an ideal candidate for the evaluation of set-valued classification methods. However, it is far too large to allow for widespread use by the machine-learning community. Extracting a subsample from it must be done with care as we want to preserve the uncertainty naturally present in the whole database. The dataset presented in this chapter is constructed by retaining only a subset of the genera of the entire Pl@ntNet database (sampled uniformly at random). All species belonging to the selected genera are then retained. Doing so maintains the original ambiguity as species in the same genus are likely to be visually similar and to share common visual features.

The rest of the chapter is organized as follows. We first introduce the set-valued classification framework in Section 3.1, focusing on two special cases: top-K classification and average-K classification. In Section 3.2, we describe the construction procedure of the Pl@ntNet-300K dataset and show that it contains a large amount of ambiguity. Next, we present in Section 3.3 the metrics of interest for the dataset and propose benchmark results for these metrics, obtained by training several neural networks architectures. In Section 3.4, we compare Pl@ntNet-300K to several existing datasets. In Section 3.5, we discuss possible uses of Pl@ntNet-300K. Finally, we provide the link to the dataset in Section 3.6 before concluding.

Set-valued classification

We adopt the classical statistical setup of multi-class classification. Let L be the number of classes. We denote by [L] the set {1, . . . , L} and by X the input space. Random couples of images and labels (X, Y ) ∈ X × [L] are assumed to be generated i.i.d. by an unknown joint distribution P. Note that only one label is associated with each image, which differs from the multi-label setting [START_REF] Zhang | A Review on Multi-Label Learning Algorithms[END_REF]: P@ntNet-300K is composed of images containing a single specimen of a plant, so there is only one true label per image.

For some plant images, predicting the correct class label (the correct species) does not present much difficulty (consider for instance a common species very distinctive from other species). For other images, however, classifying the photographed specimen with a high degree of confidence is a much harder task, because some species differ only in subtle visual features (see Figure 3.4). In these cases, it is desirable to provide the user with a list of likely species corresponding to the image. We thus need a classifier able to produce sets of classes, also known as a set-valued classifier in the literature [START_REF] Chzhen | Set-valued classification -overview via a unified framework[END_REF].

A set-valued classifier Γ is a function mapping the feature space X to the set of all subsets of [L] (which we denote by 2 [L] ). Using these notations, we thus have

Γ : X → 2 [L] instead of Γ : X → [L]
for the classical setting in which the predictor can only predict a single class. Our goal is to build a classifier with low risk, defined as P(Y / ∈ Γ(X)). However, it is not desirable to simply minimize the risk: a set-valued classifier that always returns all classes achieves zero risk but is useless. On the other hand, a classifier is most useful if it returns only the most likely classes given a query image. Therefore, a quantity of interest will be |Γ(x)|, the number of classes returned by the classifier Γ, given an image x ∈ X .

In this section, we will examine two optimization problems that lead to different set-valued classifiers. Both of them aim to minimize the risk, but they differ in the way they constrain the set cardinality: either pointwise or on average. For x ∈ X and l ∈ [L], we define the conditional probability p l (x) := P(Y = l | X = x), and estimators of these quantities will be denoted by pl (x). In the following,

K ∈ [L].
The simplest constraint is to require that the number of returned classes is less than K for each input. This results in the following top-K error [START_REF] Lapin | Top-k multiclass SVM[END_REF] minimization problem:

Γ * top-K ∈ arg min Γ P(Y / ∈ Γ(X)) s.t. |Γ(x)| ≤ K, ∀x ∈ X . (3.1)
The closed form solution to (3.1) exists and is equal to [START_REF] Lapin | Analysis and optimization of loss functions for multiclass, top-k, and multilabel classification[END_REF]:

Γ * top-K (x) = T K (p(x)) . (3.2) PL@NTNET-300K
Yet, this is not practical since we do not know the distribution P and thus p l (x). However, if we have an estimator pl (x) of p l (x), we can naturally derive the plug-in estimator: Γ top-K = top K (p(x)). While the top-K accuracy is often reported in benchmarks, only a few works aim to directly optimize this metric [LHS15; LHS16; LHS17; BZK18]. An obvious limitation of top-K classification is that K classes are returned for every data sample, regardless of the difficulty of classifying that sample. Average-K classification allows for more adaptivity. In that setting, the constraint on the size of the predicted set is less restrictive and must be satisfied only on average, leading to:

Γ * average-K ∈ arg min Γ P(Y / ∈ Γ(X)) s.t. E X |Γ(X)| ≤ K . (3.3)
The closed-form solution is derived in [START_REF] Denis | Confidence Sets with Expected Sizes for Multiclass Classification[END_REF]:

Γ * average-K (x) = {l ∈ [L] : p l (x) ≥ G -1 (K)} , (3.4)
where the function G is defined as

: ∀t ∈ [0, 1], G(t) = L l=1 P(p l (X) ≥ t), and G -1 refers to the generalized inverse of G, namely G -1 (u) = inf{t ∈ [0, 1] : G(t) ≤ u}.
Note that if we define the classifier Γ t by: ∀x ∈ X ,

Γ t (x) = {l ∈ [L], p l (x) ≥ t}, then G(t) is the average number of classes returned by Γ t : G(t) = E X |Γ t (X)|. From (3.4)
we see that the optimal classifier corresponds to a thresholding operation: all classes having a conditional probability greater than G -1 (K) are returned, with the threshold chosen so that K classes are returned on average. To compute a plug-in counterpart, we just need to estimate the threshold on a calibration set such that on average on that set, K classes are returned. For technical details, we refer the reader to [START_REF] Denis | Confidence Sets with Expected Sizes for Multiclass Classification[END_REF].

Dataset

Label validation and data cleaning

Label validation is based on a weighted majority voting algorithm taking as input the labels proposed by Pl@ntNet users with an adaptive weighting principle according to the user's expertise and commitment. Thus, a single trusted annotator can be enough to validate an image label. On the other hand, images whose labels are proposed by several novice users may not be validated because they do not have sufficient weight. The technical details of this algorithm can be found in the supplementary material. At the time of the construction of Pl@ntNet-300K, the total number of annotators in the Pl@ntNet database was equal to 2,079,003. The average number of annotators per image is equal to 2.03.

In addition to the label validation procedure, Pl@ntNet's pipeline includes other data cleaning procedures: (i) automated filtering of inappropriate or irrelevant content (faces, humans, animals, buildings, etc.) using a CNN and user reports, and (ii) filtering on image quality (evaluated by users).

Construction of Pl@ntNet-300K

In taxonomy, species are organized into genera, with each genus containing one or more species, and the different genera do not overlap, as illustrated in Figure 3.1.

Instead of retaining randomly selected species or images from the entire Pl@ntNet dataset, we choose to retain randomly selected genera and keep all species belonging to these genera. This choice aims to preserve the large amount of ambiguity present in the original database, as species belonging to the same genus tend to share visual features. The dataset presented in this chapter is constructed by sampling uniformly at random only 10% of the genera of the whole Pl@ntNet database.

We then retain only species with more than 4 images, resulting in a total of 303 genera and L = 1 081 species. The images are divided into a training set, a validation set and a test set. 2 For each species, 80% of the images are placed in the training set (n train = 243 916), 10% in the validation set (n val = 31 118), and 10% in the test set (n test = 31 112), with at least one image of each species in each set. More formally, given a class j containing n j images, n val,j = ⌈0.1 × n j ⌉, n test,j = ⌈0.1 × n j ⌉ and n train,j = n j -n val,j -n test,j . This represents a total of n tot = n train +n val +n test = 306 146 color images. The average image size is (570, 570, 3), ranging from (180, 180, 3) to (900, 900, 3). The construction of the dataset preserves the class imbalance. To show this, we plot the Lorenz curves [START_REF] Joseph | A general definition of the Lorenz curve[END_REF] of the entire Pl@ntNet dataset and that of the Pl@ntNet-300K dataset in Figure 3.2.

Epistemic (model) uncertainty

Epistemic uncertainty refers mainly to the lack of data necessary to properly estimate the conditional probabilities. In Pl@ntNet, the most common species are easily observed by users in the wild and therefore represent a large fraction of the images, while the rarest species are harder to find and therefore less frequent in the database. In Figure 3.2, we see that 80% of the species (the ones with the lowest number of images) account Pl@ntNet-300K dataset Full Pl@ntNet dataset Figure 3.2: Lorenz curves of the Pl@ntNet database and the proposed dataset. Note that, for fair comparisons, we discard species with less than 4 images in the Pl@ntNet database.

for only 11% of the total number of images. Hence, training machine learning models is challenging for such a dataset, since for many classes the model only has a handful of images to train on, making identification difficult for these species.

In addition to the long-tailed distribution issue, epistemic uncertainty also arises from the high intra-species variability. Plants may take on different appearances depending on the season (e.g., , flowering time). Furthermore, a user of the application may photograph only a part of the plant (for instance, the trunk and not the leaves). As a last example, flowers belonging to the same species can have different colors. Figure 3.3 shows some examples of these phenomena which contribute to high intraclass variability, making it more challenging to model the species.

Aleatoric (data) uncertainty

In our case, the source of aleatoric uncertainty mostly resides in the limited information we are given to make a decision (assign a label to a plant). Some species, especially those belonging to the same genus, can be visually very similar. For example, consider the case where two species produce the same flowers but different leaves, typically because they have evolved differently from the same parent species. If a person photographs only the flower of a specimen of one of the two species, then it will be impossible, even for an expert, to know which species the flower belongs to. The discriminative information is not present in the image. The combination of this irreducible ambiguity with images of non-optimal quality (non-adapted close-up, low-light conditions, etc.) results in pairs of images that belong to different species but are difficult or even impossible to distinguish, see Figure 3.4 for illustration. In this figure, we show the ambiguity between pairs of species, but we could find similar examples involving a larger number of species. Thus, even an expert botanist might fail to assign a label to such pictures with certainty. This is embodied by p l (x): given an image, multiple classes are possible.

Evaluation

Metric

We consider two main metrics to evaluate set valued predictors on Pl@ntNet-300K: top-K accuracy and average-K accuracy. Let S denote a set of n (input, label) pairs: S = {(x 1 , y 1 ), (x 2 , y 2 ), . . . , (x n , y n )}. [START_REF] Lapin | Loss functions for top-k error: Analysis and insights[END_REF] is a widely used metric often reported in benchmarks. Average-K accuracy is a much less common metric that derives from average-K classification [START_REF] Denis | Confidence Sets with Expected Sizes for Multiclass Classification[END_REF]:

Top-K accuracy

average-K accuracy(S) = 1 n (x i ,y i )∈S 1 [y i ∈ Γ average-K (x i )] s.t. 1 n (x i ,y i )∈S | Γ average-K (x i )| ≤ K , (3.5)
where Γ average-K is a set-valued classifier constructed using the training data.

For Pl@ntNet-300K, both top-K accuracy and average-K accuracy mainly reflect the performance of the set-valued classifier on the few classes which represent most of the images. If we wish to capture the ability of a set-valued classifier to return relevant set of species for all classes, we will examine macro-average top-K accuracy and macro-average average-K accuracy which simply consist in computing respectively top-K accuracy and average-K accuracy for each class, and then computing the average over classes. For macro-average average-K accuracy, the constraint on the average size of the set must hold for the entire set S.

To derive both classifiers, one can first obtain an estimate of the conditional probabilities pl (x) and then derive the plug-in classifiers, as explained in Section 3.1. Our hope is for the Pl@ntNet-300K dataset to encourage novel ways to derive the setvalued classifiers Γ top-k and Γ average-K to optimize respectively the top-K accuracy and the average-K accuracy. Notice that a few works already propose methods to optimize the top-K accuracy [LHS15; LHS16; LHS17; BZK18].

Baseline

This section provides a baseline evaluation of the plug-in classifiers. We train several deep neural networks with the cross-entropy loss: The models are optimized with SGD with a momentum of 0.9 with the Nesterov acceleration [START_REF] Ruder | An overview of gradient descent optimization algorithms[END_REF]. We use a batch size of 32 for all models and a weight decay of 1.10 -4 . The number of epochs, initial learning rate and learning rate schedule used for each model can be found in the supplementary material. For the plug-in classifier Γ average-K, plug-in , we compute the threshold λ val on the validation set and use that same threshold to compute the average-K accuracy on the test set.

ResNets [He+16], DenseNets, [Hua+17], InceptionResNet-v2 [Sze+17], MobileNetV2 [San+18], MobileNetV3 [How+19], EfficientNets [TL19], Wide ResNets [ZK16], AlexNet [KSH12], Inception- v3 [Sze+16], Inception-v4 [Sze+17], ShuffleNet [Zha+18], SqueezeNet [Ian+16], VGG [SZ15]

Difficulty of Pl@ntNet-300K

Figure 3.5 highlights the significant gap between Pl@ntNet-300K top-1 accuracy and macro-average top-1 accuracy. This is a consequence of the long-tailed distribution: the few classes that represent most of the images are easily identified, which results in high top-1 accuracy. However, this seemingly high top-1 accuracy is misleading, as models struggle with classes with few images (which are a majority, see Figure 3.2). This effect is illustrated in Table 3.1, which shows that the top-1 accuracy depends strongly on the number of images in the class.

Figure 3.8(a) shows the correlation between Pl@ntNet-300K macro-average top-1 accuracy and ImageNet macro-average top-1 accuracy (note that as the ImageNet test set is balanced, top-1 accuracy and macro-average top-1 accuracy coincide). As expected, the two metrics are positively correlated: deep networks allow to model complex features. It works well both on ImageNet and Pl@ntNet-300K. Interestingly, due to the difference between the two datasets (long-tailed distribution, class ambiguity, . . . ), some models which perform similarly on ImageNet yield very different on Pl@ntNet-300K (inception_v3, densenet201), and vice versa.

In Figure 3.8(a) we can notice that ImageNet macro-average top-1 accuracy and Pl@ntNet-300K macro-average top-1 accuracy vary at different scales: the former goes up to 80% while the latter does not exceed 40%, making Pl@ntNet-300K a challenging dataset with both epistemic and aleatoric uncertainty at play. This can can also be seen in Figure 3.6: some models reach a macro-average average-5 accuracy of 97% for ImageNet, while that metric does not exceed 80% for Pl@ntNet-300K, which suggests that progress could be made with appropriate learning strategies.

To support that claim, we asked a botanist to label a mini dataset extracted from the Pl@ntNet-300K test set. The dataset is constructed as follows: we extract all species from two groups (Crotalaria and Lupinus), and select at most 5 images per species (randomly sampled). This results in 83 images. The botanist was asked to provide a set of possible species for each image. This results in an error rate of 20.5% for an average of 4,1 species returned (ranging from 1 to 10). We compare the botanist performance with that of several neural networks by calibrating the conditional probabilities' threshold to obtain on average 4,1 species on the mini-dataset. The results are reported in Figure 3.7, and show that the gap between the botanist error rate and the best-performing model is large (from 0.2 to 0.33), which suggests that there is room for improvement in the performance of average-K classifiers.

Top-K vs Average-K

From Equation (3.1) and (3.3), it is clear that the Bayes average-K classifier has a lower risk than the Bayes top-K classifier. Therefore, a model that accurately estimates the conditional probabilities should yield a better average-K accuracy than top-K accuracy. This is what can be observed in Figure 3.8(b) which shows the correlation between macro-average top-5 accuracy and macro-average average-5 accuracy. As expected, the two metrics are positively correlated. However, the relationship does not appear to be trivial and Figure 3.8(b) shows models with similar macro-average average-5 accuracies having very different macro-average top-5 accuracy and vice versa. For an in-depth comparison of average-K classification and top-K classification, we refer the reader to [Lor20].

Both metrics are of their own interest and deserve a specific treatment as they capture two different settings: top-K accuracy evaluates the performance of a classifier that systematically returns K classes, while average-K accuracy evaluates the performance of a classifier that returns sets of varying size (depending on the input), with the constraint to return K classes on average.

Evaluation of existing set-valued classification methods

To the best of our knowledge, there is no existing loss designed to specifically optimize average-K accuracy. For top-K classification, the most recent loss designed to optimize top-K accuracy is the one by [START_REF] Berrada | Smooth Loss Functions for Deep Top-k Classification[END_REF]. We report the top-5 accuracy obtained by training this loss with K = 5 on Pl@ntNet-300K in the supplementary material. The results are close to what is obtained with the cross entropy loss. However, this topic is still open research and our hope in releasing Pl@ntNet-300K is precisely to encourage novel methods for optimizing such metrics.

PL@NTNET-300K

Related work

Fined-Grained Visual Categorization (FGVC) is about discriminating visually similar classes. In order to better learn fine-grained classes, several approaches have been proposed by the FGVC community, including multi-stage metric learning [START_REF] Qi Qian | Fine-grained visual categorization via multi-stage metric learning[END_REF], high-order feature interaction [LRM15; Cui+17], and different network architectures [START_REF] Fu | Look Closer to See Better: Recurrent Attention Convolutional Neural Network for Fine-Grained Image Recognition[END_REF][START_REF] Ge | Fine-grained classification via mixture of deep convolutional neural networks[END_REF]. However, these approaches focus on optimizing top-1 accuracy. Setvalued classification, on the other hand, consists in returning more than a single class to reduce the error rate, with a constraint on the number of classes returned. Therefore, FGVC and set-valued classification methods are not mutually exclusive but rather complementary.

Several FGVC datasets, which exhibit visually similar classes, have been made publicly available by the community. They cover a variety of domains: aircraft [START_REF] Maji | Fine-grained visual classification of aircraft[END_REF], cars (Compcars [START_REF] Yang | A large-scale car dataset for fine-grained categorization and verification[END_REF], Census cars [START_REF] Gebru | Fine-grained car detection for visual census estimation[END_REF]), birds (CUB200 [START_REF] Welinder | Caltech-UCSD Birds 200[END_REF]), flowers (Oxford flower dataset [START_REF] Nilsback | Automated flower classification over a large number of classes[END_REF]).

However, most of these datasets focus exclusively on proposing visually similar classes (aleatoric uncertainty) with a limited amount of epistemic uncertainty. This is the case for balanced datasets which have approximately the same number of images per class, or with small intra-class variability such as aircraft and cars datasets, where most examples within a class are nearly the same except for angle, lighting, etc.

ImageNet [START_REF] Russakovsky | ImageNet Large Scale Visual Recognition Challenge[END_REF] has several visually similar classes, organized in groups: it contains many bird species and dog breeds. However, these groups of classes are very different: dogs, vehicles, electronic devices, etc. Besides, ImageNet does not exhibit a strong class imbalance.

Several of these datasets were constructed by web-scraping, which can be prone to noisy labels and low-quality images.

Most similar to our dataset is the iNat2017 dataset [START_REF] Van Horn | The INaturalist Species Classification and Detection Dataset[END_REF]. It contains images from the citizen science website iNaturalist. The images, posted by naturalists, are validated by multiple citizen scientists. The iNat2017 dataset contains over 5000 classes that are highly unbalanced. However, iNat2017 does not only focus on plants but proposes several other 'super-classes' such as Fungi, Reptilia, Insecta, etc. Moreover, the authors selected all classes with a number of observations greater than 20, whereas we choose to randomly sample 10% of the genera of the entire Pl@ntNet database and keep all species belonging to these groups with a number of observations greater than 4. We argue that keeping all species of the same genus maximizes aleatoric uncertainty because species belonging to the same genus tend to share visual features.

Finally, a plant disease dataset is introduced in [Sla+16], containing 4483 images downloaded from the web spread across 15 classes. This is a very different scale than Pl@ntNet-300K. We summarize the properties of the mentioned datasets in Table 3.2.

Possible uses of Pl@ntNet-300K

Although we are convinced of the need to design new set-valued methods due to the ever-increasing amount of classes to discriminate, the properties of Pl@ntNet-300K described in Section 3.2 make it an ideal candidate for various other tasks. The strong class imbalance can be used by researchers to evaluate new algorithms specifically wide_resnet101_2 (26), wide_resnet50_2 (27).

PL@NTNET-300K

✗ ✗ ✗ ✓ ✗ CUB200 ✗ ✗ ✗ ✓ ✗ Oxford flower dataset ✗ ✗ ✓ ✓ ✗ Aircraft dataset ✓ ✗ ✗ ✓ ✗ Compcars ✗ ✗ ✗ ✓ ✓ Census cars ✗ ✗ ✗ ✓ ✓ ImageNet ✗ ✗ ✓ ✗ ✗ iNat2017 ✓ ✓ ✓ ✗ ✗ Pl@ntNet-300K ✓ ✓ ✓ ✓ ✓
designed for tackling class imbalance [Zho+20; Cao+19]. Pl@ntNet-300K contains a large amount of aleatoric uncertainty resulting from many visually similar classes. It can therefore be used as an FGVC dataset to evaluate methods that aim to optimize top-1 accuracy for such datasets, see for instance [LRM15; FZM17; Cui+17]. Finally, in this chapter, we do not use the genus information and thus do not exploit the hierarchical structure of the problem. In this sense, we adopt the flat classification approach described in [START_REF] Silla | A survey of hierarchical classification across different application domains[END_REF]. This is consistent with ImageNet [START_REF] Russakovsky | ImageNet Large Scale Visual Recognition Challenge[END_REF] or CIFAR-100 [START_REF] Krizhevsky | Learning multiple layers of features from tiny images[END_REF], where a hierarchy does exist but is rarely used in benchmarks. However, researchers are free to use the genus information to evaluate hierarchical classification methods on Pl@ntNet-300K.

Data access and additional resources

The Pl@ntNet-300K dataset can be found here:

https://doi.org/10.5281/zenodo.5645731.

It is organized in three folders named "train", "val" and "test". Each of these folders contains L = 1 081 subfolders. We provide the correspondence between the names of the subfolders and the names of the classes in the file "plantnet300K_species_id_2_name.json". We also provide a metadata file named "plantnet300K_metadata.json" containing for each image the following information: the species identifier (class), the organ of the plant (flower, leaf, bark, . . . ), the author's name, the license and the split (i.e., train, validation or test set). A GitHub repository containing the code to reproduce the experiments of this chapter (where potential issues related to the dataset can be reported too) is available at: https://github.com/plantnet/PlantNet-300K/. To date (2023), the dataset has

Conclusion

been viewed 20,000 times and downloaded 5,000 times.4

Conclusion

In this chapter, we share and discuss a novel plant image dataset, called Pl@ntNet-300K, obtained as a subset of the entire Pl@ntNet database and intended primarily for evaluating set-valued classification methods. Unlike previous datasets, Pl@ntNet-300K is designed to preserve the high level of ambiguity across classes of the initial real-world dataset as well as its long-tailed distribution. To evaluate set-valued predictors on Pl@ntNet-300K, we investigate two different metrics: macro-average top-K accuracy and macro-average average-K accuracy, which is a more challenging task requiring to predict sets of various size but still equal to K on average. Our results suggest that there is room for new set-valued prediction methods that would improve the performance of average-K classifiers. We hope that Pl@ntNet-300K can serve as a reference dataset for this problem, which is our main motivation for releasing and sharing it with the community. We also stress that Pl@ntNet-300K can also be used to evaluate new methods for long-tailed classification and FGVC. In the next chapters, we propose methods to optimize respectively top-K and average-K accuracy use Pl@ntNet-300K to test our ideas.

PL@NTNET-300K

Appendix

Pl@ntNet label validation process

Only Pl@ntNet observations with a valid species name were included in the Pl@ntNet-300K dataset. The species name validation process of Pl@ntNet is based on a weighted majority voting algorithm taking as input the labels proposed by Pl@ntNet users with a principle of adaptive weights depending on the user's expertise and engagement. More precisely, the most probable label y i of an image x i is computed as:

y i = arg max k∈1,...,d u∈U i w u 1(y u i = k) ,
where U i is the set of users who suggested a label for the image x i and y u i is the label proposed by the user u. The weight w u of a user u is computed as:

w u = n α u -n β u + b 0 ,
where n u is the number of species observed by user u (i.e., the number of species for which the user is the author of at least one valid image), plus the number of distinct labels y u i proposed by a user u in the whole dataset. The constant power values α = 0.5, β = 0.2 and b 0 are determined empirically. To be considered as valid, the label y i of an image x i must satisfy:

u∈U i w u 1(y u i = y i ) > θ
where θ is a fixed threshold. Images with non-valid labels were discarded from Pl@ntNet-300K dataset.

Hyperparameters

The hyperparameters used for the experiments in Section 4 of the paper can be found in Table 3.3.

Evaluation of existing set-valued classification methods

Introduction

Fine-grained visual categorization (FGVC) has recently attracted a lot of attention [START_REF] Wang | Guest Editorial: Introduction to the Special Section on Fine-Grained Visual Categorization[END_REF], in particular in the biodiversity domain [START_REF] Van Horn | The INaturalist Species Classification and Detection Dataset[END_REF][START_REF] Garcin | Pl@ntNet-300K: a plant image dataset with high label ambiguity and a long-tailed distribution[END_REF][START_REF] Van Horn | Building a bird recognition app and large scale dataset with citizen scientists: The fine print in fine-grained dataset collection[END_REF]. In FGVC, one aims to classify an image into subordinate categories (such as plant or bird species) that contain many visually similar instances. The intrinsic ambiguity among the labels makes it difficult to obtain high levels of top-1 accuracy as is typically the case with standard datasets such as CIFAR10 [START_REF] Krizhevsky | Learning multiple layers of features from tiny images[END_REF] or MNIST [START_REF] Lecun | Gradientbased learning applied to document recognition[END_REF]. For systems like Merlin [START_REF] Van Horn | Building a bird recognition app and large scale dataset with citizen scientists: The fine print in fine-grained dataset collection[END_REF] or Pl@ntNet [START_REF] Affouard | Pl@ntNet app in the era of deep learning[END_REF], due to the difficulty of the task, it is generally relevant to provide the user with a set of classes in the hope that the true class belongs to that set. In practical applications, the display limit of the device only allows to give a few labels back to the user. A straightforward strategy consists in returning a set of K classes for each input, where K is a small integer with respect to the total number of classes. Such classifiers are called top-K classifiers, and their performance is evaluated with the well known top-K accuracy [START_REF] Lapin | Top-k multiclass SVM[END_REF][START_REF] Russakovsky | ImageNet Large Scale Visual Recognition Challenge[END_REF]. While such a metric is very popular for evaluating applications, common learning strategies typically consist in learning a deep neural network with the cross-entropy loss, neglecting the top-K constraint in the learning step.

Yet, recent works have focused on optimizing the top-K accuracy directly. [LHS15] have introduced the top-K hinge loss and a convex upper-bound, following techniques introduced by [UBG09] for ranking. A limit of this approach was raised by [START_REF] Berrada | Smooth Loss Functions for Deep Top-k Classification[END_REF], as they have shown that the top-K hinge loss by [START_REF] Lapin | Top-k multiclass SVM[END_REF] can not be directly used for training a deep neural network. The main arguments put forward by the authors to explain this practical limitation are: (i) the non-smoothness of the top-K hinge loss and (ii), the sparsity of its gradient. Consequently, they propose a smoothed alternative adjustable with a temperature parameter. However, their smoothing procedure is computationally costly when K increases (as demonstrated in our experiments), despite the efficient algorithm they provide to cope with the combinatorial nature of the loss. Moreover, this approach has the drawback to be specific to the top-K hinge loss introduced by [START_REF] Lapin | Top-k multiclass SVM[END_REF].

In contrast, we propose a new top-K loss that relies on the smoothing of the top-K operator (the operator returning the K-th largest value of a vector). The smoothing framework we consider, the perturbed optimizers [START_REF] Berthet | Learning with differentiable perturbed optimizers[END_REF], can be used to smooth variants of the top-K hinge loss but could independently be considered for other learning tasks such as K-nearest neighbors or top-K recommendation [HWC19; CAS16]. Additionally, we introduce a simple variant of our loss to deal with imbalanced datasets. Indeed, for many real-world applications, a long-tailed phenomenon appears [START_REF] William | The Pareto, Zipf and other power laws[END_REF]: a few labels enjoy a lot of items (e.g., images), while the vast majority of the labels receive only a few items, see for instance a dataset like Pl@ntnet-300k [START_REF] Garcin | Pl@ntNet-300K: a plant image dataset with high label ambiguity and a long-tailed distribution[END_REF] for a more quantitative overview. We find that the loss by [START_REF] Berrada | Smooth Loss Functions for Deep Top-k Classification[END_REF] fails to provide satisfactory results on the tail classes in our experiments. On the contrary, our proposed loss based on uneven margins outperforms the loss from [START_REF] Berrada | Smooth Loss Functions for Deep Top-k Classification[END_REF] and the LDAM loss [START_REF] Cao | Learning Imbalanced Datasets with Label-Distribution-Aware Margin Loss[END_REF], a loss designed for imbalance cases known for its very good performance in fine-grained visual classification challenges [START_REF] Wang | Long-tailed Recognition by Routing Diverse Distribution-Aware Experts[END_REF]. To the best of our knowledge, our proposed loss is the first loss function tackling both the top-K classification and class imbalance problems jointly.

Related work

Several top-K losses have been introduced and experimented with in [LHS15; LHS16; LHS17]. However, the authors assume that the inputs are features extracted from a deep neural network and optimize their losses with SDCA [START_REF] Shalev | Stochastic dual coordinate ascent methods for regularized loss minimization[END_REF]. [START_REF] Berrada | Smooth Loss Functions for Deep Top-k Classification[END_REF] have shown that the top-K hinge loss from [START_REF] Lapin | Top-k multiclass SVM[END_REF] could not be directly used in a deep learning optimization pipeline. Instead, we are interested in end-to-end deep neural network learning. The state-of-the art top-K loss for deep learning is that of [START_REF] Berrada | Smooth Loss Functions for Deep Top-k Classification[END_REF], which is a smoothing of a top-K hinge loss by [START_REF] Lapin | Top-k multiclass SVM[END_REF]. The principle of the top-K loss of [START_REF] Berrada | Smooth Loss Functions for Deep Top-k Classification[END_REF] is based on the rewriting the top-K hinge loss of [START_REF] Lapin | Top-k multiclass SVM[END_REF] as a difference of two maxes on a combinatorial number of terms, smooth the max with the logsumexp, and use a divide-and-conquer approach to make their loss tractable. Instead, our approach relies on smoothing the top-K operator and using this smoothed top-K operator on a top-K calibrated loss recently proposed by [START_REF] Yang | On the consistency of top-k surrogate losses[END_REF]. Our approach could be used out-of-the box with other top-K hinge losses. In contrast, the smoothing method of [START_REF] Berrada | Smooth Loss Functions for Deep Top-k Classification[END_REF] is tailored for the top-K hinge loss of [START_REF] Lapin | Top-k multiclass SVM[END_REF], which is shown to be not top-K calibrated in [START_REF] Yang | On the consistency of top-k surrogate losses[END_REF].

For a general theory of smoothing in optimization, we refer the reader to [BT12; Nes05] while for details on perturbed optimizers, we refer the reader to [START_REF] Berthet | Learning with differentiable perturbed optimizers[END_REF] and references therein. In the literature, other alternatives have been proposed to perform top-K smoothing. [START_REF] Xie | Differentiable Top-k with Optimal Transport[END_REF] formulate the smooth top-K operator as the solution of a regularized optimal transport problem between well-chosen discrete measures. The authors rely on a costly optimization procedure to compute the optimal plan. [START_REF] Michael | Reparameterizable subset sampling via continuous relaxations[END_REF] propose a smoothing of the top-K operator through K successive softmax. Besides the additional cost with large K, the computation of K successive softmax brings numerical instabilities.

Concerning imbalanced datasets, several recent contributions have focused on architecture design [START_REF] Zhou | BBN: Bilateral-Branch Network With Cumulative Learning for Long-Tailed Visual Recognition[END_REF][START_REF] Wang | Long-tailed Recognition by Routing Diverse Distribution-Aware Experts[END_REF]. Instead, we focus here on the design of the loss function and leverage existing popular neural networks architectures. A popular loss for imbalanced classification is the focal loss [START_REF] Lin | Focal Loss for Dense Object Detection[END_REF] which is a modification of the cross entropy where well classified-examples induce a smaller loss, putting emphasis on difficult examples. Instead, we use uneven margins in our formulation, requiring examples of the rarest classes to be well classified by a larger margin than examples of the most common classes. Uneven margin losses have been studied in the binary case in [Sco12; LST03; IMV19]. For the multi-class setting, the LDAM loss [START_REF] Cao | Learning Imbalanced Datasets with Label-Distribution-Aware Margin Loss[END_REF] is a widely used uneven margin loss which can be seen as a cross entropy incorporating uneven margins in the logits. Instead, our imbalanced top-K loss relies on the smoothing of the top-K operator. 4.1, for L = 3 classes, K = 2 and a true label y = 3 (corresponding to the upper corner of the triangles). For visualization the loss are rescaled between 0 and 1, and the level sets are restricted to vector s ∈ 2 • ∆ 2 . The losses have been harmonized to display a margin equal to 1. For our proposed loss, we have averaged the level sets over 100 replications to avoid meshing artifacts.

ℓ γ focal (s, y) (1 -log [ℓ CE (s, y)] γ ℓ CE (s, y) γ [Cao+19] ℓ K Hinge (s, y) 1 + τ K (s \y ) -sy + K Equation (4.4), [LHS15] ℓ K CVXHinge (s, y) 1 K k∈[K] τ k (1 L -δy + s) -sy + K [LHS15] ℓ K Cal. Hinge (s, y) (1 + τ K+1 (s) -sy) + K Equation (4.17), [YK20] ℓ K,τ Smoothed Hinge (s, y) τ ln   A⊂[L],|A|=K e 1 {y / ∈A} τ + j∈A s j Kτ   -τ ln   A⊂[L],|A|=K e j∈A s j Kτ   K, τ [BZK18] ℓ K,ϵ,M Noised bal. (s, y) (1 + τ K+1,ϵ,M (s) -sy) + ,
) ∈ X × [L],
where X is the input data space (X is the space of RGB images of a given size in our vision applications) and the y's are the associated labels among L possible ones.

For a training pair of observed features and label (x, y), s ∈ R L refers to the associated score vector (often referred to as logits). From now on, we use bold font to represent vectors. For k ∈ [L], s k refers to the score attributed to the k-th class while s y refers to the score of the true label and s [k] refers to the k-th largest score1 , so that s

[1] ≥ • • • ≥ s [k] ≥ • • • ≥ s [L] . For K ∈ [L],
we define τ K and topΣ K , functions from R L to R as:

τ K : s → s [K] (4.1) topΣ K : s → k∈[K] s [k] . (4.2)
In this thesis, τ K is referred to as the top-K function or top-K operator. We write 1 L = (1, . . . , 1) ⊤ ∈ R L . For s ∈ R L , the gradient ∇τ K (s) is a vector with a single one at the K-th largest coordinate of s and 0 elsewhere (denoted as arg τ K (s)). Similarly, ∇topΣ K (s) is a vector with K ones at the K largest coordinates of s and 0 elsewhere (denoted as arg topΣ K (s)). The top-K loss (a 0/1 loss) can now be written:

ℓ K (s, y) = 1 {τ K (s)>sy} . (4.3)
This loss reports an error when the score of the true label y is not among the K-th largest scores. One would typically seek to minimize this loss. Yet, being a piece-wise constant function w.r.t. to its first argument2 , numerical difficulties make solving this problem particularly hard in practice. In what follows we recall some popular surrogate top-K losses from the literature before providing new alternatives. We summarize such variants in Table 4.1 and illustrate their differences in Figure 4.1 for L = 3, K = 2 (see also Figure 4.6 in Appendix, for L = 3, K = 1).

A first alternative introduced by [LHS15] is a relaxation generalizing the multi-class hinge loss introduced by [CS01] to the top-K case:

ℓ K Hinge (s, y) = 1 + τ K (s \y ) -s y + , ( 4.4)
where s \y is the vector in R d-1 obtained by removing the y-th coordinate of s, and (•) + ≜ max(0, •). The authors propose a convex loss function ℓ K CVXHinge (see Table 4.1) which upper bounds the loss function ℓ K Hinge . [START_REF] Berrada | Smooth Loss Functions for Deep Top-k Classification[END_REF] have proposed a smoothed counterpart of ℓ K Hinge , relying on a recursive algorithm tailored for their combinatorics smoothed formulation. Yet, a theoretical limitation of ℓ K Hinge and ℓ K CVXHinge was raised by [START_REF] Yang | On the consistency of top-k surrogate losses[END_REF] showing that they are not top-K calibrated. Top-K calibration is a property defined by [START_REF] Yang | On the consistency of top-k surrogate losses[END_REF]. We recall some technical details in Section 4.6.1 and the precise definition of top-K calibration is given in Definition 4.6.2.

We let ∆ L-1 ≜ {p ∈ R L : L l=1 p l = 1, p l ≥ 0} denote the probability simplex of size L. For a score s ∈ R L and p ∈ ∆ L-1 representing the conditional distribution of y given x, we write the conditional ℓ-risk at x ∈ X as R ℓ|x (s, p) = E y|x∼p (ℓ(s, y)) and the (integrated) ℓ-risk as R ℓ (f ) ≜ E (x,y)∼P [ℓ(f (x), y)] for a scoring function f : X → R L . The associated Bayes risks are defined respectively by

R * ℓ|x (p) ≜ inf s∈R L R ℓ|x (s, p) and R * ℓ ≜ inf f :X →R L R ℓ (f ).
The following result by [START_REF] Yang | On the consistency of top-k surrogate losses[END_REF] shows that a top-K calibrated loss is top-K consistent, meaning that a minimizer of such a loss would also lead to Bayes optimal classifiers: Theorem 4.3.1. [YK20, Theorem 2.2]. Suppose ℓ is a nonnegative top-K calibrated loss function. Then, ℓ is top-K consistent, i.e., for any sequence of measurable functions f (n) : X → R L , we have:

R ℓ f (n) → R * ℓ =⇒ R ℓ K f (n) → R * ℓ K .
In their paper, [START_REF] Yang | On the consistency of top-k surrogate losses[END_REF] propose a slight modification of the multi-class hinge loss ℓ K Hinge and show that it is top-K calibrated:

ℓ K Cal. Hinge (s, y) = (1 + τ K+1 (s) -s y ) + . (4.5)
The loss ℓ K Cal. Hinge thus has an appealing theoretical guarantee that ℓ K Hinge does not have. Therefore we will use ℓ K Cal. Hinge as the starting point of our smoothing proposal.

New loss for balanced top-K classification

[BZK18] have shown experimentally that a deep learning model trained with ℓ K Hinge does not learn. The authors claim that the reason for this is the non smoothness of the loss and the sparsity of its gradient.

We also show in Table 4.2 that a deep learning model trained with ℓ K Cal. Hinge yields poor results. The problematic part stems from the top-K function which is non-smooth and whose gradient has only one non-zero element (that is equal to one). In this chapter we propose to smooth the top-K function with the perturbed optimizers method developed by [START_REF] Berthet | Learning with differentiable perturbed optimizers[END_REF]. We follow this strategy due to its flexibility and to the ease of evaluating associated first order information (a crucial point for deep neural network frameworks). Definition 4.3.2. For a smoothing parameter ϵ > 0, we define for any s ∈ R L the ϵ-smoothed version of topΣ K as:

topΣ K,ϵ (s) ≜ E Z [topΣ K (s + ϵZ)] , (4.6)
where Z is a standard normal random vector, i.e., Z ∼ N (0, Id L ).

Proposition 4.3.3. For a smoothing parameter ϵ > 0,

• The function topΣ K,ϵ : R L → R is strictly convex, twice differentiable and √ K-Lipschitz continuous.

• The gradient of topΣ K,ϵ reads:

∇ s topΣ K,ϵ (s) = E[arg topΣ K (s + ϵZ)] . (4.7) • ∇ s topΣ K,ϵ is √ KL ϵ -Lipschitz. • When ϵ → 0, topΣ K,ϵ (s) → topΣ K (s).
All proofs are given in the appendix.

The smoothing strategy introduced leads to a natural smoothed approximation of the top-K operator, leveraging the link τ K (s) = topΣ K (s) -topΣ K-1 (s) for any score s ∈ R L (where we use the convention topΣ 0 = 0 L ∈ R L ):

Definition 4.3.4. For any s ∈ R L and k ∈ [L], we define τ K,ϵ (s) ≜ topΣ K,ϵ (s) -topΣ K-1,ϵ (s) .
This definition leads to a smooth approximation of the top-K function, in the following sense: Proposition 4.3.5. For a smoothing parameter ϵ > 0,

• τ K,ϵ is 4 √ KL ϵ -smooth. • For any s ∈ R L , |τ K,ϵ (s) -τ K (s)| ≤ ϵ • C K,L , where C K,L = K √ 2 log L.
Observe that the last point implies that for any s ∈ R L , τ K,ϵ (s) → τ K (s) when ϵ → 0.

We can now define an approximation of the calibrated top-K hinge loss ℓ K Cal. Hinge using τ K,ϵ in place of τ K (see Figures 4.1(h) and 4.1(i) for level sets with K = 2)3 . Definition 4.3.6. We define ℓ K,ϵ Noised bal. the noised balanced top-K hinge loss as:

ℓ K,ϵ Noised bal. (s, y) = (1 + τ K+1,ϵ (s) -s y ) + . (4.8)
We call the former balanced as the margin (equal to 1) is the same for all L classes. The parameter ϵ controls the variance of the noise added to the score vectors. When ϵ = 0, we recover the top-K calibrated loss of [YK20], ℓ K Cal. Hinge .

Proposition 4.3.7. For a smoothing parameter ϵ > 0 and a label y

∈ [L], • ℓ K,ϵ Noised bal. (•, y) is continuous, differentiable almost everywhere, with continuous derivative. • The gradient of ℓ(•, y) ≜ ℓ K,ϵ
Noised bal. (•, y) is given by:

∇ℓ(s, y) = 1 {1+τ K+1,ϵ (s)≥sy} •(∇τ K+1,ϵ (s) -δ y ), (4.9)
where δ y ∈ R L is the vector with 1 at coordinate y and 0 elsewhere.

Practical implementation:

As is, the proposed loss can not be used directly to train modern neural network architectures due to the expectation and remains a theoretical tool. Following [START_REF] Berthet | Learning with differentiable perturbed optimizers[END_REF], we simply rely on a Monte Carlo method to estimate the expectation for both the loss and its gradient: we draw M noise vectors Z 1 , . . . , Z M , with

Z m i.i.d. ∼ N (0, Id L ) for m ∈ [M ]. The loss ℓ K,ϵ
Noised bal. is then estimated by:

ℓ K,ϵ,M Noised bal. (s, y) = (1 + τ K+1,ϵ,M (s) -s y ) + , (4.10)
where τ K+1,ϵ,M (s) ≜ topΣ K+1,ϵ,M (s) -topΣ K,ϵ,M (s) is a Monte Carlo estimate with M samples:

topΣ K,ϵ,M (s) = 1 M M m=1 topΣ K (s + ϵZ m ) . ( 4

.11)

We approximate ∇ s ℓ K,ϵ Noised bal. (s, y) by G, with:

G = 1 {1+ τ K+1,ϵ,M (s)≥sy} •( ∇τ K+1,ϵ,M (s)-δ y ), (4.12)
where the Monte Carlo estimate

∇τ K+1,ϵ,M (s) ≜ arg τ K+1,ϵ,M (s)
is given by:

arg τ K+1,ϵ,M (s) = 1 M M m=1 arg τ K+1 (s + ϵZ m ) .
We train our loss with SGD. Hence, M repetitions are drawn each time the loss is evaluated. The iterative nature of this process helps amplify the smoothing power of the approach, explaining why even small values of M can lead to good performance (see Section 5.6).

Illustration

Z 1 = 0.2 -0.1 0.1 0.3 , Z 2 = 0.1 0.1 -0.1 0.1 , Z 3 = -0.1 -0.1 0.1 -0.1 .
The perturbed vectors are now:

s + ϵZ 1 = 2.6 2.5 2.4 0.8 , s + ϵZ 2 = 2.5 2.7 2.2 0.6 , s + ϵZ 3 = 2.3 2.5 2.4 0.4 .
The induced perturbation may provoke a change in both τ K and arg τ K . For the perturbed vector s + ϵZ 2 , the added noise changes the second largest value but it is still achieved at coordinate 1: τ K (s + ϵZ 2 ) = 2.5 and arg τ K (s + ϵZ 2 ) = 1 0 0 0 . However, for s + ϵZ 1 and s + ϵZ 3 , the added noise changes the coordinate of the second largest value: arg τ K (s + ϵZ 1 ) = 0 1 0 0 and arg τ K (s + ϵZ 3 ) = 0 0 1 0 , with τ K (s + ϵZ 1 ) = 2.5 and τ K (s + ϵZ 3 ) = 2.4, giving: τ K,ϵ,M (s) = (2.5 + 2.5 + 2.4)/3 = 2.47 ,

∇τ K,ϵ,M (s) = 1 3 0 1 0 0 + 1 0 0 0 + 0 0 1 0 =    1 3 1 3 1 3 0    .
We see the added noise results in giving weight to the gradient coordinates k whose associated score s k is close to τ K (s) (in this example the first and third coordinates). Note that if we set ϵ to a smaller value, e.g., ϵ = 0.1, the added perturbation is not large enough to change the arg τ K in the perturbed vectors, leading to the same gradient as the non-smoothed top-K operator: ∇τ K,0.1 (s) = 1 0 0 0

. Hence, ϵ acts as a parameter which allows exploring coordinates k whose score values s k are close to the top-K score (provided that ϵ and/or M are large enough).

New loss for imbalanced top-K classification

In real world applications, a long-tailed distribution between the classes is often present, i.e., few classes receive most of the annotated labels. This occurs for instance in datasets such as Pl@ntNet-300K [START_REF] Garcin | Pl@ntNet-300K: a plant image dataset with high label ambiguity and a long-tailed distribution[END_REF] and Inaturalist [START_REF] Van Horn | The INaturalist Species Classification and Detection Dataset[END_REF], where a few classes represent the vast majority of images. For these cases, the performance of deep neural networks trained with the cross entropy loss is much lower for classes with a small numbers of images, see [START_REF] Garcin | Pl@ntNet-300K: a plant image dataset with high label ambiguity and a long-tailed distribution[END_REF].

We present an extension of the loss presented in Section 4.3.2 to the imbalanced case. This imbalanced loss is based on uneven margins [Sco12; LST03; IMV19; Cao+19]. The underlying idea is to require larger margins for classes with few examples, which leads to a higher incurred loss for mistakes made on examples of the least common classes.

Imposing a margin m y parameter per class in Equation (4.10) leads to the following formulation:

ℓ K,ϵ,M,my Noised Imbal. (s, y) = (m y + τ K+1,ϵ,M (s) -s y ) + . (4.13)
Here, we follow [START_REF] Cao | Learning Imbalanced Datasets with Label-Distribution-Aware Margin Loss[END_REF] and set m y = C/n 1/4 y , with n y the number of samples in the training set with class y, and C a hyperparameter to be tuned on a validation set.

Comparisons of various top-K losses

In Table 4.1, we synthesize the various top-K loss functions evoked above. To better understand their differences, Figure 4.1 provides a plot of the losses for s in the 2simplex, for K = 2 and L = 3. The correct label is set to be y = 3 and corresponds to the vertex on top and in red. Figure 4.1(a) shows the classical top-K that we would ideally want to optimize. It has 0 error when s 3 is larger than the smallest coordinate of s (i.e., is in the top-2) and 1 otherwise. Figure 4.1(b) shows the cross-entropy, by far the most popular (convex) loss used in deep learning. As mentioned by [START_REF] Yang | On the consistency of top-k surrogate losses[END_REF], the cross-entropy happens to be top-K calibrated for all K. Figure 4.1(c) shows the top-K hinge loss proposed by [START_REF] Lapin | Top-k multiclass SVM[END_REF] and Figure 4.1(e) is a convex upper relaxation. Unfortunately, [START_REF] Yang | On the consistency of top-k surrogate losses[END_REF] have shown that such losses are not top-K calibrated and propose an alternative, illustrated in Figure 4.1(d). We show that the loss of [START_REF] Yang | On the consistency of top-k surrogate losses[END_REF] performs poorly when used for optimizing a deep neural network. Figure 4.1(f) and Figure 4.1(g) show the smoothing proposed by [START_REF] Berrada | Smooth Loss Functions for Deep Top-k Classification[END_REF] of the loss in Figure 4.1(c), while Figure 4.1(h) and Figure 4.1(i) show our proposed noised smoothing of the loss in Figure 4.1(d). The difference with [START_REF] Berrada | Smooth Loss Functions for Deep Top-k Classification[END_REF] is that we start with a top-K calibrated hinge loss, and our smoothing consists in smoothing only the top-K operator, which mostly affects classes whose scores are close to the top-K score, while the method from [START_REF] Berrada | Smooth Loss Functions for Deep Top-k Classification[END_REF] results in a gradient where all coordinates are non-zero.

Finally, Figure 4.1(j) shows our noised imbalanced top-K loss. Additional visualizations of our noised top-K loss illustrating the effect of M and ϵ can be found in the appendix, see Figures 4.4 Av. number of non-zero gradient coordinates

K = 3 K = 5 K = 10

Experiments

The Pytorch [Pas+19] code for our top-K loss and experiments can be found at: https: //github.com/garcinc/noised-topk. We also provide a python package containing our top-K losses as well as the smoothed top-K function. The package is easily installed with pip: pip install pytopk

Influence of ϵ and gradient sparsity

Table 4.2 shows the influence of ϵ on CIFAR-1004 top-5 accuracy. When ϵ = 0, ℓ K,ϵ,M Noised bal. coincides with ℓ K Cal. Hinge . We see that a model trained with this loss fails to learn properly. This resonates with the observation made by [START_REF] Berrada | Smooth Loss Functions for Deep Top-k Classification[END_REF] that a model trained with ℓ K Hinge , which is close to ℓ K Cal. Hinge , also fails to learn. Table 4.2 also shows that when ϵ is too small (ϵ = 10 -4 or ϵ = 10 -3 ), the optimization remains difficult and the learned models have very low performance. For sufficiently high values of ϵ, in the order of 10 -2 or greater, the smoothing is effective and the learned models achieve a very high top-5 accuracy. Table 4.2 also shows that although the optimal value of ϵ appears to be around 10 -1 , the optmization is robust to high values of ϵ.

[BZK18] argue that a reason a model trained with ℓ K Hinge fails to learn is because of the sparsity of the gradient of ℓ K Hinge . Indeed, for any s ∈ R L , y ∈ [L], ∇ s ℓ K Hinge (s, y) has at most two non-zero coordinates. This is one of the main reasons put forward We investigate the behaviour of the gradient of our loss by computing

∇ s ℓ K,ϵ,M
Noised bal. (s, y) for each training example during the first epoch. We then compute the average number of non-zero coordinates in the gradient. We repeat this process for several values of ϵ and report the results in Figure 4.2. There are two points to highlight:

• The number of non-zero gradients coordinates increases with ϵ. This is consistent with our illustration example in Section 4.3.2: high values of ϵ allow putting weights on gradient coordinates whose score is close to the K-th largest score.

• Even when ϵ is large, the number of non-zero gradient coordinates is small: on average, 4 out of 100. In comparison, for ℓ K CE and ℓ K,τ Smoothed Hinge , all gradient coordinates are non-zero. Yet, even with such sparse gradient vectors, we manage to reach better top-5 accuracies than ℓ K CE and ℓ K,τ Smoothed Hinge (see Table 4.4). Therefore, one of the main takeaway is that a non-sparse gradient does not appear to be a necessary condition for successful learning contrary to what is suggested in [START_REF] Berrada | Smooth Loss Functions for Deep Top-k Classification[END_REF]. A sufficiently high probability (controlled by ϵ) that each coordinate is updated at training is enough to achieve good performance.

Influence of M

Table 4.3 shows the influence of the number of sampled standard normal random vectors M on CIFAR-100 top-5 accuracy for a model trained with our balanced loss with K = 5. M appears to have little impact on top-5 accuracy, indicating that there is no need to precisely estimate the expectation in Equation (4.11). As increasing M comes with computation overhead (see next section) and does not yield an increase of top-K accuracy, we advise setting it to a small value (e.g., 3 ≤ M ≤ 10).

Computation time

In for ℓ K,τ Smoothed Hinge is 90s versus 60s for ℓ K,ϵ,M Noised bal. with M = 3. While for most classical datasets [START_REF] Russakovsky | ImageNet Large Scale Visual Recognition Challenge[END_REF][START_REF] Krizhevsky | Learning multiple layers of features from tiny images[END_REF] small values of K are enough to achieve high top-K accuracy, for other applications high values of K may be used [CAS16; Col+20], making our balanced loss computationally attractive.

Comparisons for balanced classification

The CIFAR-100 [START_REF] Krizhevsky | Learning multiple layers of features from tiny images[END_REF] dataset contains 60,000 images (50,000 images in the training set and 10,000 images in the test set) categorized in 100 classes. The classes are grouped into 20 superclasses (e.g., fish, flowers, people), each regrouping 5 classes. Here we compare the top-K accuracy of a deep learning model trained on CIFAR-100 with either our balanced loss ℓ K,ϵ,M Noised bal. , the cross entropy ℓ CE , or the loss from [BZK18], ℓ K,τ Smoothed Hinge , which is the current state-of-the art top-K loss for deep learning. We repeat the experiment from Section 5.1 of [START_REF] Berrada | Smooth Loss Functions for Deep Top-k Classification[END_REF] to study how ℓ K,ϵ,M Noised bal. reacts when noise is introduced in the labels. More precisely, for each training image, its label is sampled randomly within the same super-class with probability p. Thus, p = 0 corresponds to the original dataset and p = 0.5 corresponds to a dataset where all the training examples have a label corresponding to the right superclass, but half of them (on average) have a different label than the original one. With such a dataset, a perfect top-5 classifier is expected to have a 100% top-5 accuracy. As in [START_REF] Berrada | Smooth Loss Functions for Deep Top-k Classification[END_REF] we extract 5000 images from the training set to build a validation set. We use the same hyperparameters as [START_REF] Berrada | Smooth Loss Functions for Deep Top-k Classification[END_REF]: we train a DenseNet 40-40 [START_REF] Huang | Densely Connected Convolutional Networks[END_REF] for 300 epochs with SGD and a Nesterov momentum of 0.9. For the learning rate, our policy consists in starting with value of 0.1 and dividing it by ten at epoch 150 and 225. The batch size and weight decay are set to 64 and 1.10 -4 respectively. Following [START_REF] Berrada | Smooth Loss Functions for Deep Top-k Classification[END_REF], the smoothing parameter τ of ℓ K,τ Smoothed Hinge is set to 1.0. For ℓ K,ϵ,M Noised bal. , we set the noise parameter ϵ to 0.2 and the number of noise samples M at 10. We keep the models with the best top-5 accuracies on the validation set and report the top-5 accuracy on the test set in Table 4.4. The results are averaged over four runs with four different random seeds (we give the 95% confidence inverval). They show that the models trained with ℓ5,0.2,10 Noised bal. give the best top-5 accuracies except when p = 0.1 where it is slightly below ℓ 5,1.0 Smoothed Hinge . We also observe that the performance gain over the cross entropy is significant in the presence of label noise (i.e., for p > 0).

We provide additional experiments on ImageNet [START_REF] Russakovsky | ImageNet Large Scale Visual Recognition Challenge[END_REF] in Section 4.6.4.

Comparison for imbalanced classification 4.4.5.1 Pl@ntNet-300K

We consider Pl@ntNet-300K 5 , a dataset of plant images recently introduced in [START_REF] Garcin | Pl@ntNet-300K: a plant image dataset with high label ambiguity and a long-tailed distribution[END_REF]. It consists of 306,146 plant images distributed in 1,081 species (the classes). The particularities of the dataset are its long-tailed distribution (80% of the species with the least number of images account for only 11% of the total number of images) and the class ambiguity: many species are visually similar. For such an imbalanced dataset, accuracy and top-K accuracy mainly reflect the performance of the model on the few classes representing the vast majority of images. Often times, we also want the model to yield satisfactory results on the classes with few images. Therefore, for this dataset we report macro-average top-K accuracy, which is obtained by computing top-K accuracy for each class separately and then taking the average over classes. Thus, the class with only a few images contributes the same as the class with thousands of images to the overall result.

In this section we compare the macro-average top-K accuracy of a deep neural network trained with either ℓ CE , ℓ K,τ Smoothed Hinge , ℓ K,ϵ,M Noised bal. , ℓ

K,ϵ,M,my

Noised imbal. and ℓ my LDAM , the loss from [START_REF] Cao | Learning Imbalanced Datasets with Label-Distribution-Aware Margin Loss[END_REF] based on uneven margins providing state-of-the-art performance in Fine-Grained Visual Categorization tasks.

Setup:

We train a ResNet-50 [START_REF] He | Deep residual learning for image recognition[END_REF] pre-trained on ImageNet [START_REF] Russakovsky | ImageNet Large Scale Visual Recognition Challenge[END_REF] for 30 epochs with SGD with a momentum of 0.9 with the Nesterov acceleration. We use a learning rate of 2.10 -3 divided by ten at epoch 20 and epoch 25. The batch size and weight decay are set to 32 and 1.10 -4 respectively. The smoothing parameter τ for ℓ K,τ Smoothed Hinge is set to 0.1.

To tune the margins of ℓ . We find that for both losses, the optimal largest margin is 0.2. For ℓ K,ϵ,M,my Noised imbal. , we set ϵ = 10 -2 and M = 5. We further discuss hyperparameter tuning in Section 4.6.5.

We train the network with the top-K losses ℓ K,τ Smoothed Hinge , ℓ K,ϵ,M Noised bal. and ℓ

K,ϵ,M,my

Noised imbal. for K ∈ {1, 3, 5}. For all losses, we perform early stopping based on the best macro-average top-K accuracy on the validation set (for K ∈ {1, 3, 5}). We report the results on the 4.6. Appendix

Appendix

Reminder on Top-K calibration

Here we provide some elements introduced by [YK20] on top-K calibration. Definition 4.6.1. [YK20, Definition 2.3]. For a fixed K ∈ [L], and given y ∈ R L and ỹ ∈ R L , we say that y is top-K preserving w.r.t. ỹ, denoted

P K (y, ỹ), if for all k ∈ [L], ỹk > τ K+1 (ỹ) =⇒ y k > τ K+1 (y) (4.14) ỹk < τ K (ỹ) =⇒ y k < τ K (y) . (4.15)
The negation of this statement is ¬P k (y, ỹ).

We let

∆ L-1 ≜ {p ∈ R L : k∈[L] p k = 1, p k ≥ 0}
denote the probability simplex of size L. For a score s ∈ R L and p ∈ ∆ L-1 representing the conditional distribution of y given x, we write the conditional risk at x ∈ X as R ℓ|x (s, p) = E y|x∼p (ℓ(s, y)) and the (integrated) risk as R ℓ (f ) ≜ E (x,y)∼P [ℓ(f (x), y)] for a scoring function f : X → R L . The associated Bayes risks are defined respectively by

R * ℓ|x (p) ≜ inf s∈R L R ℓ|x (s, p) and R * ℓ ≜ inf f :X →R L R ℓ (f ). Definition 4.6.2. [YK20, Definition 2.4]. A loss function ℓ : R L × Y → R is top-K calibrated if for all p ∈ ∆ L-1 and all x ∈ X : inf s∈R L :¬P k (s,p) R ℓ|x (s, p) > R * ℓ|x (p) . ( 4.16)
In other words, a loss is calibrated if the infimum can only be attained among top-K preserving vectors w.r.t. the conditional probability distribution. Theorem 4.6.3. Suppose ℓ is a nonnegative top-K calibrated loss function. Then ℓ is top-K consistent, i.e., for any sequence of measurable functions f (n) : X → R L , we have:

R ℓ f (n) → R * ℓ =⇒ R ℓ K f (n) → R * ℓ K .
In their paper, [START_REF] Yang | On the consistency of top-k surrogate losses[END_REF] propose a slight modification of the multi-class hinge loss ℓ K Hinge and show that it is top-K calibrated: Proof. We define

ℓ K Cal. Hinge (s, y) = (1 + τ K+1 (s) -s y ) + . ( 4
∆ L-1 K ≜ p ∈ R L , l∈[L] p k = K, 0 ≤ p l ≤ 1, ∀l ∈ [L] . For s ∈ R L , one can check that arg topΣ K (s) = arg max p∈∆ L-1 K ⟨p, s⟩.
Recall that Z is a standard normal random vector, i.e., Z ∼ N (0, Id L ).

• ∆ L-1 K is a convex polytope and the multivariate normal has positive differentiable density. So, we can apply [Ber+20, Proposition 2.2]. For that, it remains to determine the constant

R ∆ L-1 K and M µ . First, R ∆ L-1 K ≜ max p∈∆ L-1 K ∥p∥. For simplicity, let us compute max p∈∆ L-1 K ∥p∥ 2 , i.e., max ∥p∥ 2 (4.18) k∈[L] p k = K, ∀k ∈ [L], p k ∈ [0, 1]. (4.19)
Note that this corresponds to the well known quadratic knapsack problem. A numerical solution can be obtained, see for instance [START_REF] Helgason | A polynomially bounded algorithm for a singly constrained quadratic program[END_REF]. To obtain our bound, note that for p ∈ ∆ L-1 K one can check that

∥p∥ 2 = k∈[L] p 2 k ≤ k∈[L] p k (since ∀k ∈ [L], p k ∈ [0, 1]).
Hence, we have ∀p ∈ ∆ L-1 K , ∥p∥ 2 ≤ K. Now, one can check that this equality is achieved when choosing p = (1, . . . , 1, 0, . . . , 0

) ⊤ ∈ R L with K non-zeros values, yielding max p∈∆ L-1 K ∥p∥ = √ K. Following [Ber+20, Proposition 2.2] this guarantees that topΣ K,ϵ is √ K-Lipschitz. Let us show now that M µ ≜ E Z [∥∇ Z ν(Z)∥ 2 ] = √ L with ν(Z) = 1 2 ∥Z∥ 2 and Z ∼ N (0, Id L ).
Hence, M µ can be computed as:

M µ = E Z ∥∇ Z ν(Z)∥ 2 = E Z ∥Z∥ 2 = √ L ,
where the last equality comes from Z ∼ N (0, Id L ). Following [Ber+20, Proposition 2.2] this guarantees that ∇topΣ K,ϵ is √ KL ϵ -Lipschitz. • The last bullet of our proposition comes derives now directly from of [Ber+20, Proposition 2.3].

Proof of Proposition 4.3.5

Proof.

• From the triangle inequality and proposition 4.3.3 we get for any s, s ′ ∈ R L :

∥∇τ K,ϵ (s) -∇τ K,ϵ (s ′ )∥ = ∥[∇topΣ K,ϵ (s) -∇topΣ K,ϵ (s ′ )] -[∇topΣ K-1,ϵ (s) -∇topΣ K-1,ϵ (s ′ )]∥ ≤ ∥∇topΣ K,ϵ (s) -∇topΣ K,ϵ (s ′ )∥ + ∥∇topΣ K-1,ϵ (s) -∇topΣ K-1,ϵ (s ′ )∥ ≤   2 √ KL ϵ + 2 (K -1)L ϵ   ∥s -s ′ ∥ ≤ 4 √ KL ϵ ∥s -s ′ ∥

Additional experiments

CIFAR-100: Table 4.7 reports the top-1 accuracy obtained by the models corresponding to the results of Table 4.4. Hence, we show here a misspecified case: we optimized our balanced loss for K = 5, seeking to optimize top-5 accuracy, which is reported in Table 4.4, but report top-1 information. Table 4.7 shows that when there is no label noise, as expected cross entropy gives better top-1 accuracy than our top-5 loss. When the label noise is high, however, our loss leads to better top-1 accuracy.

Pl@ntNet-300K: Table 4.8 reports the top-K accuracy obtained by the models corresponding to the results of Table 4.5. The top-K accuracies are much higher than the macro-average top-K accuracies reported in Table 4.5 because of the long-tailed distribution of Pl@ntNet-300K. The models perform well on classes with a lot of examples which leads to high top-K accuracy. However, they struggle on classes with a small number of examples (which is the majority of classes, see [START_REF] Garcin | Pl@ntNet-300K: a plant image dataset with high label ambiguity and a long-tailed distribution[END_REF]). Thus, for Pl@ntNet-300K top-K accuracy is not very relevant as it mainly reflects the performance of the few classes with a lot of images, ignoring the performance on challenging classes (the one with few labels) [START_REF] Affouard | Pl@ntNet app in the era of deep learning[END_REF]. We report it for completeness and make a few comments: First, our balanced noise loss gives better top-K accuracies than the cross entropy or the loss from [START_REF] Berrada | Smooth Loss Functions for Deep Top-k Classification[END_REF] for all K. Then, ℓ K,ϵ,M,my Noised imbal. and ℓ K,ϵ,M Noised bal. produce the best top-1 accuracy, respectively 81.0 and 80.8. However, we insist that in such an imbalanced setting the macro-average top-K accuracy reported in Table 4.5 is much more informative than regular top-K accuracy. We see significant differences between the losses in Table 4.5 which are hidden in Table 4.8 because of the extreme class imbalance.

ImageNet: We test ℓ K,ϵ,M
Noised bal. on ImageNet. We follow the same procedure as [BZK18]: we train a ResNet-18 with SGD for 120 epochs with a batch size of 120 epochs. The learning rate is decayed by ten at epoch 30, 60 and 90. For ℓ K,τ Smoothed Hinge , the smoothing parameter τ is set to 0.1, the weight decay parameter to 0.000025 and the initial learning rate to 1.0, as in [START_REF] Berrada | Smooth Loss Functions for Deep Top-k Classification[END_REF]. For ℓ CE , the weight decay parameter is set to 0.0001 and the initial learning rate to 0.1, following [START_REF] Berrada | Smooth Loss Functions for Deep Top-k Classification[END_REF]. For ℓ K,ϵ,M Noised bal. , we use the same validation set as in [START_REF] Berrada | Smooth Loss Functions for Deep Top-k Classification[END_REF] to set ϵ to 0.5, the weight decay parameter to 0.00015 and the initial learning rate to 0.1. M is set to 10. We optimize all losses for K = 1 and K = 5. We perform early stopping based on best top-K accuracy on the validation set and report the results on the test set (the official validation set of ImageNet) in Table 4.9 (3 seeds, 95% confidence interval). In the presence of low label noise, with an important number of training examples per class and for a nearly balanced dataset, all three losses give similar results. This is in contrast with Table 4.4 and Table 4.5, where significant differences appear between the different losses in the context of label noise or class imbalance.

Hyperparameter tuning

Balanced case: For both experiments on CIFAR-100 and ImageNet, we follow the same learning strategy and use the same hyperparameters for ℓ K,τ Smoothed Hinge than [START_REF] Berrada | Smooth Loss Functions for Deep Top-k Classification[END_REF]. For ℓ K,ϵ,M Noised bal. , we refer the reader for the choice of ϵ and M respectively to Section 4.4.1 and Section 4.4.2: ϵ should be set to a sufficiently large value so that learning occurs and M should be set to a small value for computational efficiency.

Imbalanced case:

For our experiments on imbalanced datasets, we use the grid {0.5, 1.0, 2.0, 5.0} for the parameter γ of the focal loss and {0.1, 1.0} for the parameter τ of ℓ K,τ Smoothed Hinge . For ℓ max my

LDAM and ℓ K,ϵ,M,max my

Noised imbal. , the hyperparameter max m y is searched in the grid {0.2, 0.3, 0.4, 0.5} and we find in our experiments that the best working values of max m y happen to be the same for both losses. For the scaling constant for the scores, we find that 30 and 50 are good default values for respectively ℓ max my LDAM and ℓ K,ϵ,M,max my Noised imbal. . Finally, for ℓ K,ϵ,M,max my Noised imbal. , ϵ is searched in the grid {0.01, 0.05, 0.1}.

Introduction

The rise of visual sensors and the democratization of crowd-sourcing approaches (e.g., citizen science) are contributing to the emergence of new massive image datasets with a very large number of classes [Hor+18; Gar+21; Yua+21; Rob+19]. These datasets contain many classes that are similar to each other and are prone to label ambiguity due to the crowd-sourced acquisition and/or annotation process. In such cases, it is difficult to achieve high levels of top-1 accuracy. This is consistent with theory: most of the time, the Bayes classifier has a non-zero error rate due to the random nature of the underlying generation process [START_REF] Der | Aleatory or epistemic? Does it matter?[END_REF]. This is problematic for systems that aim to provide their users with a correct answer from an image [START_REF] Adam G Hart | Assessing the accuracy of free automated plant identification applications[END_REF][START_REF] Machado | A systematic review on product recognition for aiding visually impaired people[END_REF].

One way to deal with this difficulty is to allow the classifier to return more than one class. The most standard way to do this is through top-K classification, in which we allow the classifier to return exactly K candidate classes for all images [START_REF] Lapin | Top-k multiclass SVM[END_REF]. For instance, top-K accuracy is the official ImageNet [START_REF] Russakovsky | ImageNet Large Scale Visual Recognition Challenge[END_REF] metric.

Although top-K classifiers reduce the error rate by returning K classes, they lack flexibility: for some clean, unambiguous images, it is not necessary to return K candidate classes. Conversely, for some ambiguous images, K may not be sufficient for the true class to be in the returned set. Figure 5.1 illustrates how ambiguity can vary from one image to the other.

To address this variability, classifiers that return a variable number of classes from an input must be used. There exists a broad range of set-valued classifiers [START_REF] Chzhen | Set-valued classification -overview via a unified framework[END_REF] and strategies [START_REF] Fontana | Conformal prediction: a unified review of theory and new challenges[END_REF], some more flexible than others. In this chapter, we focus on average-K classifiers [START_REF] Denis | Confidence Sets with Expected Sizes for Multiclass Classification[END_REF] that return class sets of average size K, where the average is taken over the dataset. This constraint is less strict than for top-K classification, where the cardinal of the returned sets must be K for each instance. This flexibility allows returning more than K classes for ambiguous images and less than K classes for easy ones.

Controlling the average number of classes returned is useful for many applications, as it meets both UI (User Interface) design needs (e.g., the average number of results should fit on a mobile app screen) and UX (User eXperience) design needs (e.g., a recommender system should not recommend too many items on average). In some cases, the expected average size may also be known or estimated from other data sources (e.g., the average number of species present at a given location).

The simplest approach to perform average-K classification is to threshold the softmax predictions of a deep neural network optimized with cross-entropy loss. While cross-entropy is theoretically grounded in the infinite sample limit [Lor20], no guarantee exists in the finite sample case.

In this chapter, we propose a novel method to optimize average-K accuracy by adding an auxiliary head to a classical deep learning model. One head is responsible for identifying candidate classes to be returned in the set and the second head maximizes the likelihood of each candidate class.

We experiment on two datasets and report significant improvements over vanilla cross-entropy training and other methods.

Problem statement

We are in the multi-class setting, where the image/label pairs (X, Y ) are assumed to be generated i.i.d. by an unknown probability distribution P. Each image x is associated with a label y ∈ [L] := {1, . . . , L}, where L is the number of classes. Traditional multi-class classifiers are functions h : X → [L] that map an image to a single label.

To reduce the risk of not returning the true class associated to an image, we are interested in set-valued classifiers Γ : X → 2 [L] that map an image to a set of labels [START_REF] Chzhen | Set-valued classification -overview via a unified framework[END_REF], where 2 [L] is the power set of [L]. Our objective is then to build a classifier g with minimal risk R(Γ) := P(Y / ∈ Γ(X)).

A trivial solution would be to take Γ(x) = [L] for all x ∈ X , i.e., the classifier that returns the set of all classes for each input image. To build a useful classifier, a constraint must be enforced on this optimization problem (as discussed in [START_REF] Chzhen | Set-valued classification -overview via a unified framework[END_REF] where a unified framework encompassing several possible constraints is proposed). In this chapter, we focus on the average set size constraint that controls the average size of the returned set:

E X [|Γ(X)|] ≤ K , (C) (5.1)
where K is an integer and | • | denotes the cardinal.

It has been shown [START_REF] Denis | Confidence Sets with Expected Sizes for Multiclass Classification[END_REF] that the optimal classifier Γ * minimizing R while satisfying C is:

Γ * (x) = {j ∈ [L], P(Y = j|X = x) ≥ λ} , (5.2)
where λ ∈ [0, 1] is calibrated so that K classes are returned on average.

These quantities are theoretical since we do not know P. In practice, given a real dataset, the typical workflow for building an average-K classifier is to learn the model with cross-entropy on the training set and compute the threshold -so that on average K classes are returned -on the estimated conditional probabilities (softmax layer) with a validation set. The model is then evaluated on the test set.

While cross-entropy is theoretically grounded in the infinite limit sample case [Lor20], there is no guarantee in the finite sample regime. In this chapter, we propose an alternative to cross-entropy to optimize average-K accuracy by formulating the problem as a multi-label problem.

Related work

Several works have studied set-valued classification. The most studied case is top-K classification. In [START_REF] Lapin | Top-k multiclass SVM[END_REF], the authors propose a top-K hinge loss and optimize it with Stochastic Dual Coordinate Ascent [START_REF] Shalev | Stochastic dual coordinate ascent methods for regularized loss minimization[END_REF]. In [START_REF] Yang | On the consistency of top-k surrogate losses[END_REF], the authors propose a slight variation of the top-K hinge loss with stronger theoretical guarantees. In [START_REF] Berrada | Smooth Loss Functions for Deep Top-k Classification[END_REF] and [START_REF] Garcin | Stochastic smoothing of the top-K calibrated hinge loss for deep imbalanced classification[END_REF], the authors propose to smooth top-K hinge losses to make them suitable for deep learning.

Average-K classification is less studied. In [START_REF] Denis | Confidence Sets with Expected Sizes for Multiclass Classification[END_REF], the authors derive the average-K Bayes classifier. They also show that minimizing a certain ϕ-risk with specific conditions on ϕ implies minimizing the average-K error. In [Lor20], the authors show that strongly proper losses are consistent for average-K classification, which means that minimizing the expected value of such a loss leads to minimizing the expected value of the average-K error. They also show that the cross-entropy loss is strongly proper, which gives a theoretical argument for using the cross-entropy loss for average-K classification. While the two previous works give theoretical results in the infinite limit case, we instead propose a practical method for optimizing average-K accuracy and show that it performs better than cross-entropy and other methods on real-world datasets.

Another framework close to set-valued classification is conformal prediction [START_REF] Vovk | Algorithmic learning in a random world[END_REF][START_REF] Shafer | A Tutorial on Conformal Prediction[END_REF][START_REF] Fontana | Conformal prediction: a unified review of theory and new challenges[END_REF]. Conformal prediction also aims to generate prediction sets, but it relies on the use of calibration data to determine them based on hypothesis testing. It has the advantage of working on any pre-trained classifier Γ : X → [L], but it does not optimize the model itself towards the set-valued classification objective. Furthermore, the availability of calibration data can be problematic, especially for classes with few training examples (often the most numerous in the case of real-world datasets [START_REF] Garcin | Pl@ntNet-300K: a plant image dataset with high label ambiguity and a long-tailed distribution[END_REF]).

Set-valued classification can also be connected to multi-label classification [START_REF] Dembczyński | On label dependence and loss minimization in multi-label classification[END_REF][START_REF] Liu | The emerging trends of multi-label learning[END_REF]. Indeed, in both settings, a set of labels is predicted in output. A crucial difference, however, lies in the data generation process. In multi-label classification, each input x is associated with a set of labels, whereas in the set-valued setting, each input x is associated with a single label. The work of [START_REF] Cole | Multi-Label Learning from Single Positive Labels[END_REF] is the closest to ours. The authors study the positive-only multi-label classification case, which is a particular case of multi-label classification where a single positive class is observed for the training images, but all the other classes are not observed (meaning they could be either positive or negative, we do not know). Their objective is then to learn a good classifier with this partial information. Our setting is different in the sense that in multi-class classification a single object is present in the image, but we want to return a set of possible classes to reduce the risk. However, both settings share similarities: a single class label is available during training and for each input image we return a set of classes.

Set-valued classification as multi-label

Preliminaries

In most multi-class datasets [Gar+21; Kri09; Rus+15], the label y associated with an object o of true class y * is estimated by the annotators from a partial representation of o: an image x. Figure 5.2 summarizes how the final label y is obtained in most cases.

It may be difficult to determine the true class y * of an object o given the partial representation x. The image may be of poor quality, lack a discriminative feature of y * , etc. In such cases, several candidate classes are plausible for the object o, which we denote by the set S(x) ∈ 2 [L] , see Figure 5.1.

Regardless of this difficulty, a single label y -possibly different from y * -is selected in multi-class datasets. In the case of multiple annotators, the default policy is to select the label with the most votes [START_REF] Khan | Toward a Robust and Universal Crowd Labeling Framework[END_REF].

In this chapter, we propose to dynamically estimate the sets S(x) during training and use S(x) as the ground truth labels with the binary cross-entropy loss in a multi-label fashion.

Notation

Let N train , N val and N test denote respectively the training set, the validation set and the test set indices. In the rest of the chapter, we use mini-batch gradient descent [START_REF] Ruder | An overview of gradient descent optimization algorithms[END_REF] to optimize all models. In the following, B ⊂ N train denotes a random batch of training input.

For i ∈ N train ∪ N val ∪ N test , z i ∈ R L denotes the score vector -logit-predicted by the model, z ij its j-th component, and y i ∈ [L] the label assigned to i.

Given a batch B = {i 1 , i 2 , . . . , i |B| } ⊂ N train , we define:

Z B =        -z i 1 - -z i 2 - . . . -z i |B| -        and Y B =        y i 1 y i 2 . . . y i |B|       
, respectively the batch predictions and batch labels.

Let P be a vector and k ∈ N * a positive integer. P [k] will denote the k-th largest value of P .

Finally, let us note ς : R L → R L the softmax function whose j-th component is given, for any z i ∈ R L by:

ς j (z i ) = e z ij L k=1 e z ik ,
and σ the sigmoid function, defined for any t ∈ R by:

σ(t) = 1 1 + e -t .

Cross-entropy loss

Given a logit vector z i ∈ R L and a label y i , the cross-entropy loss for example i writes:

ℓ CE (z i , y i ) = -log(ς y i (z i )) .
(5.

3)

The partial derivatives read:

∂ℓ CE ∂z j (z i , y i ) =    ς y i (z i )(1 -ς y i (z i )), if j = y i -ς y i (z i ) • ς j (z i ), o.w. , ( 5.4)
which is positive only if j = y i .

Therefore, after a gradient descent update on ℓ CE , z i,y i will increase and all other scores (z ij ) j̸ =y i will decrease.

As stated in Sections 5.1 to 5.3, in the infinite limit case, ℓ CE has theoretical grounds [Lor20]. However, it is not clear that this approach is optimal when only scarce/noisy data is available. Indeed, let us consider the case where two labels y i and ỹi are equiprobable for the image x i :

P(Y = y i |X = x i ) = P(Y = ỹi |X = x i ) = 0.5 ,
and assume that the label y i was assigned to x i when the dataset was constructed. With ℓ CE , the score z i,ỹ i will decrease and z i,y i will increase during training, while we would like both z i,ỹ i and z i,y i to increase. Hence, in the context of high ambiguity, it is reasonable to formulate the problem as a multi-label classification task, in which each image x i is associated with a set of labels S(x i ) ∈ 2 [L] , the difficulty being that only one of them is observed, y i .

Assume negative

A first multi-label approach similar to cross-entropy is to consider that for any i ∈ N train , S(x i ) = {y i }, i.e., there is no ambiguity in the labels. This results in the Assume Negative loss ℓ AN [START_REF] Cole | Multi-Label Learning from Single Positive Labels[END_REF], essentially the binary cross entropy-loss with a single positive label:

ℓ AN (z i , y i ) = - L j=1 1 [j=y i ] log(σ(z ij )) + 1 L-1 1 [j̸ =y i ] log(1 -σ(z ij )) ,
(5.5) where the negative labels are weighted to have the same contribution as the positive label.

Expected positive regularization

The problem with ℓ AN is that the second term of Equation (5.5) assumes that the scores of all classes different from y i must be minimized, regardless of their relevance to example i. Removing the second term yields the positive cross-entropy loss [START_REF] Cole | Multi-Label Learning from Single Positive Labels[END_REF]:

ℓ + BCE (z i , y i ) = - L j=1 1 [j=y i ] log(σ(z ij )) .
(5.6) However, ℓ + BCE is minimized by predicting 1 for all classes, which is not desirable as it would lead to a large number of false positives.

A workaround proposed in [START_REF] Cole | Multi-Label Learning from Single Positive Labels[END_REF] is to constrain the current batch probability predictions σ(Z B ) to sum to K on average, where σ is applied pointwise and the average is over the batch dimension. Here K is a hyperparameter that can be thought of as the expected average set size. More formally, the expected number of positive classes can be estimated as:

K(Z B ) = 1 |B| i∈B L j=1 σ(z ij ) .
(5.7)

The Expected positive regularization loss [Col+21] ℓ β EPR then reads:

ℓ β EPR (Z B , Y B ) = -1 |B| i∈B log(σ(z i,y i )) + β( K(Z B )-K) 2 , (5.8)
where β is a hyperparameter to be tuned on a validation set.

Although the idea behind ℓ β EPR seems reasonable, there is an infinite number of combinations for the matrix σ(Z B ) to sum to K on average. In particular, the model could learn to place diffuse probabilities on all classes without promoting strong class candidate alternatives to the true label class in the training set.

Online estimation of labels

In [START_REF] Cole | Multi-Label Learning from Single Positive Labels[END_REF], the authors introduce a loss ℓ λ,Θ ROLE that builds on ℓ β EPR . In addition, they keep a matrix estimate of the unobserved labels Θ ∈ R n train ×L , where n train :=|N train | is the number of training examples in the dataset. During training, the labels predicted by the model are trained to match the current estimates of the labels in Θ via a crossentropy term and, in addition, to satisfy the constraint in Equation (5.8). The role of the predicted and estimated labels is then reversed. For more details, we refer the reader to [START_REF] Cole | Multi-Label Learning from Single Positive Labels[END_REF].

Although ℓ λ,Θ

ROLE is more sophisticated than EPR, we find in our experiments that it does not perform well. Moreover, it requires tuning several hyperparameters and, most importantly, keeping in GPU memory a matrix of size n train × L, which is prohibitive for large datasets. They are assigned a pseudo-label 1 in the ML head. The remaining cells, the red ones, are those that were not selected as pseudo-positives by the SCCP head and are considered pseudo-negatives by the ML head (with a pseudo-label 0). Here @ denotes matrix multiplication.

Proposed method

Outline

Let us assume that given a random batch B ⊂ N train of examples, we are able to estimate for each i ∈ B a set of possible classes different than y i which we denote S c (x i ). We can then define S(x i ) = {y i } ∪ S c (x i ). A legitimate objective is to increase the scores (z ij ) j∈S(x i ) and decrease the scores (z ij ) j / ∈S(x i ) , which is achieved by the following binary cross-entropy loss:

ℓ(Z B , Y B , S B c ) = - 1 |B| i∈B j∈[L] 1 [j=y i ] log(σ(z ij ))
(5.9)

-α i∈B j∈[L] 1 [j∈Sc(x i )] log(σ(z ij )) i∈B j∈[L] 1 [j∈Sc(x i )] -α i∈B j∈[L] 1 [j / ∈S(x i )] log(1 -σ(z ij )) i∈B j∈[L] 1 [j / ∈S(x i )]
,

where the hyperparameter α ∈ R + controls the weighting between the training set observed labels and the candidate labels and can be seen as setting a different learning rate for the "hypothetical" labels (i.e., the pseudo-labels) and the observed labels. We used the notation S B c = {S c (x i ), i ∈ B}. The main difficulty is: how to obtain the candidate labels S c (x i )?

Candidate classes estimation

To this end, we propose a two-head model, where the first head is responsible for identifying the candidate classes S c (x i ) for each i ∈ B (Set Candidate Classes Proposal -SCCP-head) and the second head (Multi-Label -ML-head) optimizes its predictions with the loss from Equation (5.9) in a multi-label fashion with the candidate classes S c (x i ) estimated by the SCCP head.

Let us denote H B ∈ R B×d as the output of the second to last layer of a deep neural network, where d is the dimension of the latent space. We define each head prediction as the output of a single linear layer building on H B : Z B = H B W ∈ R B×L for the BCE head and Z ′B = H B W ′ ∈ R B×L for the SCCP head. To identify relevant candidate classes, we rely on cross-entropy for its theoretical foundations [Lor20]. More formally, we optimize the SCCP head with:

ℓ CE (Z ′B , Y B ) = - 1 |B| i∈B log(ς y i (z ′ i )) , (5.10)
where z ′ i ∈ R L is the score prediction of the SCCP head for example i.

To propose sets of candidate classes, we select the maximum activations of the matrix [Σ -∞ ij ] i∈B,j∈[L] defined as:

Σ -∞ ij =    ς j (z ′ i ), if y i ̸ = j -∞, otherwise .
(5.11)

To construct the candidate classes sets S B c , we then select the top (K -1)|B| values of Σ -∞ to obtain sets of average size K. More formally, for i ∈ B, we define S c (x i ) as:

S c (x i ) = {j, Σ -∞ ij is in the top-(K-1)|B| values of Σ -∞ } .
(5.12)

This choice leads to sets of average size K on the batch:

1 |B| i∈B |S(x i )| = 1 |B| i∈B |S c (x i ) ∪ {y i }| (5.13) = (K -1)|B| + |B| |B| = K
An illustrative schema of the method is available in Figure 5.3. We can now plug the estimated candidate sets S B c into Equation (5.9):

ℓ BCE (Z B , Y B , S B c ) = -1 |B| i∈B j∈[L] 1[j = y i ] log(σ(z ij )) (5.14) -α (K-1)|B| i∈B j∈[L] 1[j∈S c (x i )] log(σ(z ij )) -α (L-K)|B| i∈B j∈[L] 1[j / ∈S(x i )] log(1-σ(z ij )) ,
The model is then trained jointly by minimizing the sum of the two losses:

ℓ K,α AVG-(Z ′B , Z B , Y B ) = ℓ CE (Z ′B , Y B ) + ℓ BCE (Z B , Y B , S B c ) (5.15)
At test time, the SCCP head is no longer needed, so we simply use the predictions of the ML head for prediction.

Hyperparameters

Our method depends heavily on the batch size since the candidate classes are selected from the whole batch. If the batch size is one, then for all i ∈ N train |S(x i )| = K with |S c (x i )| = K -1 and the method is not able to capture the variability of ambiguity. As soon as |B| ≥ 2, the set sizes can vary within the batch, allowing to account for the difference in ambiguity between different images of the batch. In our experiments, we found that classical values of |B| work well. The hyperparameter α should be tuned on a validation. We found that [0.1, 10.0] is a good default search range. We include experiments in the supplementary material to study the influence of |B| and α on average-K accuracy.

Discussion

Our method has the advantage of being both computationally and memory efficient since it only requires the addition of a linear layer. In particular, it does not require storing a matrix of size n train × L in memory as in [START_REF] Cole | Multi-Label Learning from Single Positive Labels[END_REF], which is prohibitive for large datasets. Besides, instead of a constraint on the average value of the predictions [START_REF] Cole | Multi-Label Learning from Single Positive Labels[END_REF], which can be satisfied by the model in various ways, we dynamically infer the instances target sets with the first head.

Algorithm 1: Computation of the threshold λ val .

Input : n

val := |N val |, X val = {x i } i∈N val , batch size |B|, model f θ , K Output : λ val Split X val into ⌈ |B| n val ⌉ batches X 1 , . . . , X ⌈ |B| n val ⌉ f 1 ← f θ (X 1 ) // get batch logits P ← ς(f 1 ) // apply softmax for i = 2 to ⌈ |B| n val ⌉ do f i ← f θ (X i ) // get batch logits p i ← ς(f i ) //

Experiments

Metrics

We compare ℓ K,α AVG with ℓ CE , ℓ AN , ℓ β EPR and ℓ λ,Θ ROLE on two datasets with different degrees of ambiguity. We also include the balanced top-K loss ℓ K,ϵ,M Noised bal. from Chapter 4 [START_REF] Garcin | Stochastic smoothing of the top-K calibrated hinge loss for deep imbalanced classification[END_REF]. For all datasets, we follow the same workflow: we train a neural network on the dataset with the different methods we compare. Early stopping is performed on best validation average-K accuracy, computed as follows:

ℓ CE ℓ K,α AVG- ℓ λ,Θ ROLE ℓ AN ℓ β EP R ℓ K,ϵ
val avg-K accuracy = 1 |N val | i∈N val 1[ς y i (z i ) ≥ λ val ] ,
(5.16) where the computation of λ val is described in Algorithm 1. We then report average-K accuracies on the test set, using the threshold λ val :

test avg-K accuracy = 1 |N test | i∈Ntest 1[ς y i (z i ) ≥ λ val ] .
(5.17)

The hyperparameters specific to all tested methods are tuned on the validation set using grid search, and the best model is then evaluated on the test set. The results are the average of several runs with different seeds and reported with 95% confidence intervals.

CIFAR100

Training: We first experiment our method on CIFAR-100 [Kri09], a dataset with L = 100 classes. We split the original training set (50 000 images) into a balanced training set of 45 000 images and a balanced validation set of 5 000 images on which all hyperparameters are tuned. We train a DenseNet40-40 [START_REF] Huang | Densely Connected Convolutional Networks[END_REF] for 300 epochs with SGD and a Nesterov momentum of 0.9, following [Gar+22; BZK18]. The batch size is set to 64 and the weight decay to 0.0001. The learning rate is initially set to 0.1 and divided by ten at epoch 150 and 225.

Results:

We report test average-5 accuracy in Table 5.1. CIFAR-100 is composed of 20 superclasses each containing 5 classes, e.g., the superclass "aquatic mammals" groups "beaver", "dolphin", "otter", "seal", and "whale". Therefore, most of the ambiguity resides within each superclass, and we are able to achieve high average-5 accuracies (∼ 96-97%, cf. Table 5.1.) This relatively low ambiguity explains the good performances of ℓ CE and ℓ AN . We find that ℓ β EP R and ℓ λ,Θ ROLE lag behind, while ℓ K,α AVG based on the proposal of candidate sets benefits from a performance gain over all the other methods.

Pl@ntNet-300K

Description: Pl@ntNet-300K [Gar+21] is a plant image dataset of 306 146 images and 1 081 classes (species) that contains a lot of class ambiguity. It is composed of 303 genera (superclasses) each comprising one or more species. Ambiguity is particularly important within a genus: for instance, two orchid species may be very similar. In Pl@ntNet-300K, a genus can include from one to several dozen species. This makes the ambiguity in this dataset very variable (see Figure 5.1). Moreover, the labels are crowdsourced so Pl@ntNet-300K is particularly prone to label noise. These reasons make it a perfect candidate for average-K classification.

Training: We finetune a ResNet-18 [START_REF] He | Deep residual learning for image recognition[END_REF] pre-trained on ImageNet [START_REF] Russakovsky | ImageNet Large Scale Visual Recognition Challenge[END_REF] for 30 epochs. We use SGD and a Nesterov momentum of 0.9, with a batch size of 32 and an initial learning rate of 0.002, divided by ten at epoch 25. The weight decay is fixed at 0.0001. All methods are trained for K ∈ {2, 3, 5, 10} and the average-K accuracy on the test set is then reported for each value of K.

Results and interpretation:

The results can be found in Table 5.2. It shows that our method is more effective for all K except when K = 2 where it gives results similar to the top-K loss. For high values of K, the gain is particularly important for few-shot and medium-shot classes, i.e., classes with few examples (for a precise definition of few/medium/long shot classes, see the caption of Table 5.2). For instance, for K = 10, the average-10 accuracy of few-shot classes is 75.75 for our method compared to 56.49 for the top-K loss and 46.58 for the cross-entropy. These results are interesting because of Pl@ntNet-300K's long-tail: few-shot and medium-shot classes account for 48% and 25% of the total number of classes, respectively. This means that the model recognition capabilities are significantly higher for a vast majority of the classes. It should be noted that high values of K can arise in certain applications, for instance for the diagnosis of rare diseases [START_REF] Faviez | Diagnosis support systems for rare diseases: a scoping review[END_REF] or for the automatic prediction of likely species at a particular location [START_REF] Lorieul | Overview of GeoLifeCLEF 2022: Predict-ing species presence from multi-modal remote sensing, bioclimatic and pedologic data[END_REF].

From Table 5.2 we see that the most naive methods ℓ AN and ℓ β EPR perform poorly compared to the other losses. In particular, ℓ AN which gave decent performances on CIFAR-100 struggles on Pl@ntNet-300K. One possible reason is that ℓ AN assumes no class ambiguity while Pl@ntNet-300K has many.

It is worth noting that ℓ K,ϵ,M Noised bal. gives interesting results and even outperforms cross-entropy. This is not surprising since the top-K loss optimizes top-K accuracy, and average-K and top-K classifiers are somewhat related (top-K classifiers are particular average-K classifiers that return K classes for each example). For a thorough comparison of top-K and average-K classification, we refer the reader to [Lor20]. AVG or ℓ CE to return sets of average size 5. The cross-entropy is over-confident for many images, which results in an important number of sets of size one, whereas our method is more conservative and tends to return fewer sets of size one but more sets of size two, three and four. AVG to return sets of average size 5. It appears clearly that images belonging to long-shot classes are associated with small set sizes. This is because the model saw enough training images belonging to these classes to make confident predictions. For medium-shot classes, the mode of the distribution is higher and the tail is heavier. For the most challenging images that belong to few-shot classes, the uncertainty results in larger set sizes, going up to ∼ 50 classes.

Limitations and future work

While ℓ K,α AVG allows practical gains in average-K accuracy, its particular structure, based on a two-headed deep neural network makes its theoretical analysis difficult. In particular, it can not be shown easily that ℓ K,α AVG is average-K calibrated [Lor20] like the cross-entropy.

We have proposed a loss function for average-K classification which is a particular instance of set-valued classification. Other settings exist [START_REF] Chzhen | Set-valued classification -overview via a unified framework[END_REF] (point-wise error control, average coverage control) and could be the object of ad-hoc optimization methods in future work.

Conclusion

We propose a loss function to optimize average-K accuracy, a setting in which sets of variable size are returned by the classifier to reduce the risk. Our method is based on the addition of an auxiliary head in the deep neural network trained the cross-entropy whose goal is to propose candidate class sets for the current batch of images. The candidate classes identified by the auxiliary head are then treated as pseudo-positives by a multi-label head optimized with the binary cross entropy. We show that our method compares favorably to the cross-entropy loss and other binary methods as well as to a top-K loss. We further show that the gain in average-K accuracy increases with K and is substantial for classes in the tail of a heavily imbalanced dataset. Our method has the advantage to be both memory and computationally efficient since it estimates the candidate classes on the fly with a single linear layer.

5.9. Appendix 5.9 Appendix

Hyperparameter sensitivity

We study the impact of the hyperparameters α and |B| on average-K accuracy by conducting further experiments on CIFAR-100 (Section 5.6.2).

Figure 5.5 shows how CIFAR-100 average-5 accuracy varies as a function of the hyperparameter α. Average-5 accuracy is stable over a wide range of α values (roughly 10 -2 to 10 1 ), which means that α does not require a precise tuning to obtain good results. It drops sharply for high α values, i.e., when the candidate classes have much more weight than the annotated labels of the training set in the objective function.

Figure 5.6 shows how average-K accuracy varies with the batch size for a model trained with ℓ CE or ℓ K,α AVG . For a fair comparison we maintain the ratio of learning rate to batch size constant. As expected, average-K accuracy decreases for both methods when the batch size becomes too small. However, we find that ℓ K,α AVG is more robust than ℓ CE to large batch size values. This can be explained by the choice of more relevant candidate classes when the batch size becomes large. This is counterbalanced by the empricical fact that SGD tends not to work well with very large batch sizes in deep learning. AVG or ℓ CE . For a fair comparison we maintain the ratio of learning rate to batch size constant. The 95% confidence interval is represented.

Experiments details

We report in Tables 5.3 and 5.4 the hyperparameters selected after grid search for all losses, for CIFAR-100 and Pl@ntNet-300K datasets respectively.

Summary and possible lines of work

In this manuscript, we have proposed two methods to optimize respectively top-K and average-K accuracy. Our methods have proved efficient on datasets with ambiguous classes and a long-tailed distribution. The top-K loss we proposed was based on the smoothing of the top-K function with the perturbed optimizer framework. For the average-K loss, we introduced a two-headed model, where one head is responsible for identifying candidate classes to include in the set of classes and the other head is optimized with a binary cross entropy loss with the candidate classes as ground truth.

Overall, we have seen in Chapter 4 and 5 that it is possible to design loss functions that perform better than cross-entropy in the finite sample regime. We have seen that the ad-hoc methods we proposed are particularly well suited for datasets with high ambiguity and a long-tailed distribution, which arises in many real-world situations. In such cases, we obtain significant gain over cross-entropy, especially so on the few-shot classes, see for instance Table 4.4, Table 4.5 and Table 5.2. When data is abundant and numerous, cross-entropy works as well as our methods, as hinted by results in Table 4.9. This is not surprising as we have seen that cross-entropy is consistent for both top-K and average-K classification, making it a solid default choice.

While we have made two propositions for the top-K and average-K settings, there are other formulations as we have seen in Chapter 2, namely the average error and point-wise error settings. These methods attempt to minimize the average size while imposing a constraint respectively on the average error and point-wise error. We have not delved into these methods because they do not provide guarantees on the set size. In particular, both settings could lead to arbitrarily large sets, which is impractical in the context of Pl@ntNet, where one desires to return only a few species to the user. In contrast, top-K and average-K classification provide a certificate on the set size, either point-wise or on average. However, it would be interesting to derive methods for these formulations as well. This could be the object of future work. Finally, some difficult theoretical work remains. It would be valuable to produce a theoretical analysis of the finite case to better understand the differences between the proposed approaches and cross-entropy. In particular, it would be interesting to understand what is happening on the long-tail classes and why we get large differences in performance on these classes.

Towards a sparse multi-label loss

As we have mentioned, multi-label classification is different from set-valued classification. The difference lies in the label space: in multi-label classification, an input example x can be associated to several labels: Y = 2 [L] . In set-valued classification, a single label is associated to the input x. While this manuscript only dealt with set-valued classification, multi-label classification is very common as in many cases several classes can appear in an image. For instance, in a x-ray image classification [START_REF] Bustos | Padchest: A large chest x-ray image dataset with multi-label annotated reports[END_REF], you can have several pathologies. In genomics, sequences often have multiple functional annotations [START_REF] Zhang | Multilabel neural networks with applications to functional genomics and text categorization[END_REF], etc. Inspired by insights from top-K classification, we present here ongoing work on a multi-label loss based on the projection on the top-K simplex.

In this section, we are in the multi-label classification setting i.e., Y = 2 [L] : several labels may be associated with an image x. In the rest of this section, K ∈ [L]. We recall that the simplex is denoted by: ∆ L-1 := {p ∈ R L , p ≥ 0, L i=1 p i = 1} .

(6.1)

Let us define the top-K simplex:

∆ L-1 K := {q ∈ R L , 0 ≤ q ≤ 1, L i=1 q i = K} . (6.
2)

The top-K simplex is the space of vectors that sum to K but where each entry is comprised between 0 and 1. Notice that the simplex and top-K simplex coincide when K = 1: ∆ L-1 = ∆ L-1 1 .

Motivation

The most standard loss for multi-label classification is the binary cross-entropy loss, which writes:

ℓ BCE (s, y) = L j=1
-y log(σ(s i )) -(1 -y) log(1 -σ(s i )) , (

where σ denotes the sigmoid function.

This loss is theoretically grounded since it is consistent for multi-label classification. One drawback of this approach is that it produces a prediction with full support, i.e., the predicted probabilities σ(s i ) are non-zero. However, in most multi-label classifications problems, the number of classes present in the input is typically very small compared to the total number of classes. This motivates the need for a sparse multi-label loss, which we introduce next.

From sparsemax to sparse-top

We recall that the softmax can be seen as a projection onto the simplex: From equation (6.5) it is clear that the softmax has full support, i.e., softmax(s) j > 0 for all j ∈ [L]. For some applications, a sparse distribution is desired. To tackle this,

Derivatives

In deep learning, it is essential to provide the jacobian of the functions we use to train the model end to end. In this section, we provide the jacobian of sparse-top and compare it with that of the softmax and sparsemax. First, note that from Equation (6.14) that sparse-top is differentiable everywhere except at the transition points between the sets H K , M K and L K . We remind the derivatives of the softmax: ∂softmax i ∂s j (s) = softmax i (s)(δ ijsoftmax j (s)) . (6.16)

To compute the derivatives of sparse-top, we must first compute the derivatives of s → λ K (s). We have:

∂λ K ∂s j (s) = 1 |M K (s)|
if j ∈ M K (s), 0 otherwise , (6.17) which gives, after simplification:

∂sparse-top i ∂s j (K, s) = δ ij - 1 |M K (s)|
if i, j ∈ M K (s), 0 otherwise . (6.18)

We remind that the derivatives of the sparsemax write:

∂sparsemax i ∂s j (s) = δ ij - 1 |S(s)|
if i, j ∈ S(s), 0 otherwise . (6.19) Equations (6.18) and (6.19) are quasi-identical. In the derivatives of sparse-top, M K (s) plays the role that S(s) plays in the sparsemax.

Let us write the jacobians in matrix notations. Let us denote p = softmax(s). Then the jacobian of the softmax then reads: J softmax (s) = Diag(p)pp T (6.20)

Let m be an indicator vector whose i-th entry is 1 if i ∈ M (s) and 0 otherwise. Then the jacobian of sparse-top K reads: Let v be an indicator vector whose i-th entry is 1 if i ∈ S(v) and 0 otherwise. Then the jacobian of sparsemax reads:

J sparsemax (v) = Diag(v) - vv T |S(v)| (6.22)

Multi-label loss function with sparse-top

We remind that the gradient of the softmax loss reads:

∇ s ℓ CE (s, y) = -δ y + softmax(s). (6.23)

If you attempt to minimize ℓ CE with SGD, the optimum is reached when ∇ s ℓ CE (s, y) is equal to 0, i.e., when softmax(s) = δ y , that is when the softmax is equal to the target vector, with one at the grund truth and 0 elsewhere (which never happens since the softmax has full support). For multi-label classification, the target for an example x ∈ X is a set Y ∈ 2 [L] that can contain several labels. Our intent is to design a loss that exactly predicts at optimum Y . To this end, we wish to design a loss ℓ sparse-top so that: This way, the gradient of this loss is 0 when sparse-top is equal to 1 on ground truth coordinates and 0 otherwise. By integrating, this leads to:

ℓ sparse-top (s, Y ) = - k∈Y s k + k∈H |Y | (s) s k - 1 2 + 1 2 k∈M |Y | (s) (s 2 k -λ 2 (s)) +
|Y | 2 (6.25)

Properties

The following properties make ℓ sparse-top a suitable loss for machine learning: it is a convex, differentiable loss.

Open questions

One of the question with ℓ sparse-top is what happens at prediction time. Indeed, during training, one has access to the labels Y and hence it is possible to project on ∆ L-1 |Y | . However, at test time, we do not normally have access to the label and therefore we can not project on ∆ L-1 |Y | . As a consequence, for a test example x, the best we can do is to obtain the associated predicted logits s ∈ R L after inference. Notice that it is still possible to compute usual multi-label metrics with the logits so this is not a major problem. In addition, it would be possible to compute ℓ sparse-top if one had access not to the full label Y , but merely to its cardinal |Y |. Therefore, if for some application and for some reason we knew the number of classes present in an input image x, we could compute the sparse-top of the logits and use this as a prediction. This would have the advantage to be sparse, which can be desired in some contexts. Finally, we believe that ℓ sparse-top could be useful in other contexts where we need a vector on the top-K simplex, for instance in K-nearest neighbors. We are currently investing possible applications.

s

  Vector of scores (logits) in R LXImage input spaceP Proability measure on X × [L] p l (x) class conditional probability P(Y = l|X = x) p(x) Vector of class conditional probabilities for x ∈ X , in R L τ K (s), s [K] top-K function,returns the K-th largest value of s s → T K (s) returns a set containing the indices of the K largest values of s

Figure 1 . 1 :

 11 Figure 1.1: Key milestones of the Pl@ntNet project.

INTRODUCTIONFigure 1 . 2 :

 12 Figure 1.2: Cooperative learning workflow of Pl@ntNet

Figure 1 . 3 :

 13 Figure 1.3: Images from the MNIST dataset: a case with low ambiguity.

  l∈{1,...,L} P(Y = l|X = x) , (1.2) which results in the Bayes risk: R(h * ) = P(Y ̸ = h * (X)) = 1 -E X [ max l∈{1,...,L} P(Y = l|X)] .

Figure 1 . 4 :

 14 Figure 1.4: Examples of visually similar images belonging to two different classes.

< l a t

  Figure 1.5: Example of a case with two species differing only by their leaves but having the same flower. If the user takes only a picture of the flower, it is impossible to discriminate between the two species.

Figure 1 . 6 :

 16 Figure 1.6: Example of how Pl@ntNet adds information along with the proposed sets. The image above is the query image. Below, the application makes two suggestions of species for the query. For each suggestion, it displays the images of that class most similar to the query image.

Figure 2 . 1 :

 21 Figure 2.1: Instruction on how to take a picture in Pl@ntNet. The users are asked to take a zoomed picture of a single specimen.

Figure 2 . 2 :

 22 Figure 2.2: Examples of widespread surrogate losses.

  -valued classification . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.2 Dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.2.1 Label validation and data cleaning . . . . . . . . . . . . . . . . 28 3.2.2 Construction of Pl@ntNet-300K . . . . . . . . . . . . . . . . . . 29 3.2.3 Epistemic (model) uncertainty . . . . . . . . . . . . . . . . . . 29 3.2.4 Aleatoric (data) uncertainty . . . . . . . . . . . . . . . . . . . . 30 3.3 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.3.1 Metric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.3.2 Baseline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.3.3 Difficulty of Pl@ntNet-300K . . . . . . . . . . . . . . . . . . . . 33 3.3.4 Top-K vs Average-K . . . . . . . . . . . . . . . . . . . . . . . . 35 3.3.5 Evaluation of existing set-valued classification methods . . . . 35 3.4 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.5 Possible uses of Pl@ntNet-300K . . . . . . . . . . . . . . . . . . . . . 37 3.6 Data access and additional resources . . . . . . . . . . . . . . . . . . 38 3.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.8 Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.8.1 Pl@ntNet label validation process . . . . . . . . . . . . . . . . 40 3.8.2 Hyperparameters . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.8.3 Evaluation of existing set-valued classification methods . . . . 41 PL@NTNET-300K

Figure 3 . 1 :

 31 Figure 3.1: Genus taxonomy: we display three genera present in the proposed dataset-Fedia, Pereskia and Nyctaginia-which contain respectively two, three and one species.

Figure 3 . 3 :

 33 Figure 3.3: Examples of visually different images belonging to the same class.

Figure 3 . 4 :

 34 Figure 3.4: Examples of visually similar images belonging to two different classes.

  and Vision Transformer [Dos+21]. All models are pre-trained on ImageNet. During training, images are resized to 256 and a random crop of size 224 × 224 is extracted. During test time, we take the centered crop.

  Figure 3.5: Pl@ntNet-300K test top-1 accuracy and macro-average top-1 accuracy for several neural networks.

Figure 3 . 6 :

 36 Figure 3.6: Pl@ntNet-300K vs ImageNet macro-average average-5 accuracy for several models (evaluated on the test set).

Figure 3 . 7 :

 37 Figure 3.7: Error rate on the mini test set of an expert compared to several neural networks. All models and the expert return on average 4.1 species on the mini test set.

3. 5 .

 5 Possible uses of Pl@ntNet-300K 0.26 0.28 0.30 0.32 0.34 0.36 0.38 0.40 Pl@ntNet-300K macro-average top-ImageNet macro-average top-1 accuracy vs. Pl@ntNet-300K macroaverage top-1 accuracy (evaluated on the test set). Pl@ntNet-300K macro-average average-5 accuracy vs. macro-average top-5 accuracy (evaluated on the test set).

Figure 3 . 8 :

 38 Figure 3.8: Benchmark for several popular deep neural network architectures 3 .

Figure 3 .Figure 3 . 9 :

 339 Figure3.9 compares the top-5 accuracy of several models when they are trained with either the cross entropy loss or the top-K loss by[START_REF] Berrada | Smooth Loss Functions for Deep Top-k Classification[END_REF]. The hyperparameters used for training the top-K loss are the same as in Section 4. The smoothing parameter τ of the top-K loss is set to 1.0.

Figure 4 . 1 :

 41 Figure 4.1: Level sets of the function s → ℓ(s, y) for different losses described in Table4.1, for L = 3 classes, K = 2 and a true label y = 3 (corresponding to the upper corner of the triangles). For visualization the loss are rescaled between 0 and 1, and the level sets are restricted to vector s ∈ 2 • ∆ 2 . The losses have been harmonized to display a margin equal to 1. For our proposed loss, we have averaged the level sets over 100 replications to avoid meshing artifacts.

..(

  Consider the case L = 4, K = 2, M = 3, ϵ = 1.0 with a score vector We have τ K (s) = 2.4 and arg τ K (s) = the second largest component of s corresponds to the first coordinate). Assume the three noise vectors sampled are:

Figure

  Figure 4.2: Average number of non-zero gradient coordinates as a function of ϵ (loss ℓ K,ϵ,3 Noised bal. , CIFAR-100 dataset, DenseNet 40-40 model, 1st epoch). The gradient dimension is 100. We see that the gradient remains sparse even for large values of ϵ. Together with Table4.2, this shows that having a non-sparse gradient is not a necessary condition for successful learning, contrary to what is suggested in[START_REF] Berrada | Smooth Loss Functions for Deep Top-k Classification[END_REF]

Figure 4 .

 4 3, we plot the average epoch duration of a model trained with the cross entropy ℓ CE , the loss from [BZK18] ℓ K,τ Smoothed Hinge , and our balanced loss ℓ K,ϵ,M Noised bal. (for several values of M ) as a function of K. For standard training values, i.e., K = 5, M = 3, the average epoch time is 65s for ℓ CE , 68s for ℓ K,ϵ,M Noised bal. (+4.6% w.r.t. ℓ CE ) and 81s for ℓ K,τSmoothed Hinge (+24.6% w.r.t. ℓ CE ).

Figure 4 .Figure 4 . 3 :

 443 Figure 4.3: Average epoch time as a function of K for different losses (CIFAR-100 dataset, DenseNet 40-40 model). The proposed loss ℓ K,ϵ,M Noised bal. is not sensitive to the parameter K contrarily to ℓ K,τ Smoothed Hinge

my

  LDAM and ℓ K,ϵ,M,myNoised imbal. more easily, we follow [Wan+18; Cao+19]: we normalize the last hidden activation and the weight vectors of the last fully-connected layer to both have unit ℓ 2 -norm, and we multiply the scores by a scaling constant, tuned for both losses on the validation set, leading to 40 for ℓ my LDAM and 60 for ℓ K,ϵ,M,my Noised imbal. . Finally, we tune the constant C by tuning the largest margin max y∈[L] m y for both ℓ my LDAM and ℓ K,ϵ,M,my Noised imbal.

Figure 5 . 1 :

 51 Figure 5.1: Variety of ambiguity in Pl@ntNet-300K dataset[START_REF] Garcin | Pl@ntNet-300K: a plant image dataset with high label ambiguity and a long-tailed distribution[END_REF]. The images on the left are from the dataset while the ones on the right represent the likely corresponding classes. The first row corresponds to the case where there is almost no uncertainty, the second row to the case where two classes are viable candidates for the image, etc.

Figure 5 . 2 :

 52 Figure 5.2:Common annotation processes for multi-class datasets. The label y given to the input image is either obtained: a) after direct observation of the whole original object e.g.,[START_REF] Damon P Little | An algorithm competition for automatic species identification from herbarium specimens[END_REF] b) by aggregating the labels of annotators having access only to a partial representation of the object (the input image), e.g., [Kri09; Rus+15] c) with a combination of both previous cases e.g.,[START_REF] Garcin | Pl@ntNet-300K: a plant image dataset with high label ambiguity and a long-tailed distribution[END_REF]. In all cases, annotations errors can occur resulting in a final label y different than the true class y * .

Figure 5 . 3 :

 53 Figure 5.3: The Set Candidate Classes Proposal -SCCP-head (on top) is responsible for determining, for each example of the batch, which classes to include in the target label set. The light blue cells correspond to the training set labels. Only one label is assigned per example/row. The dark blue cells correspond to the classes selected as pseudo-positives by the SCCP head. They correspond to the top (K -1)|B|highest values of the SCCP's softmax prediction matrix deprived of the light blue true labels. In this example, K = 2 and |B| = 3, so (2 -1) × 3 = 3 classes are selected as pseudo-positives in the batch. They are assigned a pseudo-label 1 in the ML head. The remaining cells, the red ones, are those that were not selected as pseudo-positives by the SCCP head and are considered pseudo-negatives by the ML head (with a pseudo-label 0). Here @ denotes matrix multiplication.

Figure 5 . 4 :

 54 Figure 5.4: Histograms of set sizes.

Figure 5

 5 Figure 5.4(b) shows the distribution of set size for few-shot, medium-shot and long-shot classes for a model trained with ℓ 5,αAVG to return sets of average size 5. It appears clearly that images belonging to long-shot classes are associated with small set sizes. This is because the model saw enough training images belonging to these classes to make confident predictions. For medium-shot classes, the mode of the distribution is higher and the tail is heavier. For the most challenging images that belong to few-shot classes, the uncertainty results in larger set sizes, going up to ∼ 50 classes.

Figure 5 . 5 :

 55 Figure 5.5: CIFAR-100 best validation average-5 accuracy for a DenseNet 40-40 trained with ℓ 5,α AVG for different values of α.

Figure 5 . 6 :

 56 Figure 5.6: CIFAR-100 best validation average-5 accuracy as a function of batch size for a DenseNet 40-40 trained with ℓ 5,αAVG or ℓ CE . For a fair comparison we maintain the ratio of learning rate to batch size constant. The 95% confidence interval is represented.

  .0, learning rate Θ: ×1.0 Table 5.3: Hyperparameters selected after grid search for the CIFAR-100 experiments.

  softmax(s) = arg min p∈∆ L-1 -⟨s, p⟩ -H(p) , (6.4)where H(p) := -L j=1 p j log(p j ) is the entropy function. This simplifies into the most famous formulation for the softmax: softmax(s) j = exp(s j )

J

  sparse-top (K, s) = Diag(m) -mm T |M (s)| (6.21)

∇

  s ℓ sparse-top (s, Y ) = -k∈Y δ k + sparse-top(|Y |, s) (6.24)

•

  ℓ sparse-top is convex • ∀s, Y : ℓ sparse-top (s, Y ) ≥ 0 • ℓ sparse-top (s, Y ) = 0 ⇔ sparse-top(|Y |, s) = k∈Y δ k Proof.• The hessian is given by:∂ 2 ℓ sparse-top ∂s i ∂s j (s, Y ) = δ ij -1 |M |Y | (s)| if i, j ∈ M |Y | (s), 0 otherwise. (6.26)It is positive semi-definite so ℓ sparse-top is convex.• For the second and last point, the minimum is attained when its gradient is zero i.e., when sparse-top(|Y |, s) = k∈Y δ k , in which case M |Y | (s) = ∅, H |Y | (s) = Y ,and ℓ sparse-top (s, Y ) = -k∈Y s k + k∈H |Y | (s) s k = 0

Table 2 .1:

 2 Summary of the different set-valued classifications formulations. We recall that S (Γ

share of species from the smallest to the largest number of images

	PL@NTNET-300K
		100%
	Cumulative share of images	40% 60% 80%
		20%
		0% Cumulative 11% 20% 40%	60%	80%	100%

Table 3 .

 3

1: Test accuracy depending on the number of images per class in the training set. Obtained with a ResNet50.

Table 3 . 2 :

 32 Comparison of several datasets with Pl@ntNet-300K. "Focused domain" indicates whether the dataset is made up of a single category (i.e., cars) and "Ambiguity preserving sampling" indicates whether in the construction of the dataset, all classes belonging to the same parent in the class hierarchy were kept or not (in our case, the parent corresponds to the genus level).

	Human-in-the-loop labeling	Long-tailed distribu-tion	Intra-class variability	Focused domain	Ambiguity preserving sampling
	Plant disease dataset

Table 3 .3:

 3 Learning rate, number of epochs and learning rate schedule for the different models. At each learning rate decay, the learning rate is divided by ten.

	Models	Initial learning rate Number of epochs First decay Second decay
	mobilenet_v2, mobilenet_v3_large,
	resnet 18, 34, 50, 101, 152,
	densenet 121, 161, 169, 201, inception_v3, inception_v4,	0.01	30	20	25
	inception_resnet_v2, wide_resnet50_2,
	wide_resnet101_2, shufflenet
	vgg11, alexnet, mobilenet_v3_small, squeezenet	0.001	30	20	25
	efficientnet b0, b1, b2, b3, b4	0.01	20	10	15
	vit	5e-4	20	15	-

Table 4 .

 4

	ℓ K Hinge ; Convexified hinge top-K ℓ K CVXHinge ; Calibrated hinge top-K ℓ K Cal. Hinge ; Log-sum Smoothed hinge
	top-K ℓ K,τ Smoothed Hinge ; Noised balanced hinge top-K ℓ K,ϵ,M Noised bal. (proposed); Noised imbalanced hinge
	top-K ℓ K,ϵ,M,my Noised Imbal. (proposed).
	Loss : ℓ(s, y)	Expression		Param.	Reference
	ℓ K (s, y)	1 {τ K (s)>sy }		K	Equation (4.3)
	ℓ CE (s, y)	-ln e sy / k∈[L] e s k	-
	ℓ my LDAM (s, y)	-ln e sy -my / e sy -my +	k∈[L],k̸ =y e s k	my	[Lin+17]

1: Summary of standard top-K losses: vanilla top-K ℓ K ; Cross Entropy ℓ CE ; hinge top-K

Table 4 . 2 :

 42 Influence of ϵ on CIFAR-100 best validation top-5 accuracy obtained by training a DenseNet 40-40 with loss ℓ K=5,ϵ,M =10

	Noised bal.	. The training procedure is the same as in Section 4.4.4.
	ϵ	0.0	1e-4 1e-3 1e-2 1e-1	1.0	10.0 100.0
	Top-5 acc. 19.38 14.84 11.4 93.36 94.46 94.24 93.78 93.12

  Noised bal. , CIFAR-100 dataset, DenseNet 40-40 model, 1st epoch). The gradient dimension is 100. We see that the gradient remains sparse even for large values of ϵ. Together with Table4.2, this shows that having a non-sparse gradient is not a necessary condition for successful learning, contrary to what is suggested in[START_REF] Berrada | Smooth Loss Functions for Deep Top-k Classification[END_REF]

4.2:

Average number of non-zero gradient coordinates as a function of ϵ (loss ℓ

K,ϵ,3

Table 4 . 3 :

 43 Influence of M hyper-parameter on the best validation top-5 accuracy (loss ℓ 5,0.2,M Noised bal. , CIFAR-100 dataset, DenseNet 40-40 model. The training procedure is the same as inSection 4.4.4.)

	M	1	2	3	5	10	50	100
	Top-5 acc 94.28 94.2 94.46 94.52 94.24 94.64 94.52
	by the authors to motivate the smoothing of ℓ K Hinge into ℓ K,τ Smoothed Hinge , whose gradient
	coordinates are all non-zero.

Table 4 . 4 :

 44 Top-5 accuracy for different losses as a function of the label noise probability p within the superclasses of CIFAR-100 (DenseNet 40-40 model).

		Label noise p	ℓ K CE		ℓ 5,1.0 Smoothed Hinge	ℓ 5,0.2,10 Noised bal.
		0.0	94.2±0.1	93.3±0.0	94.4±0.1
		0.1	90.3±0.2	92.2±0.3	91.9±0.1
		0.2	87.6±0.1	90.4±0.2	90.7±0.5
		0.3	85.7±0.4	88.8±0.1	89.7±0.1
		0.4	83.6±0.2	87.4±0.1	87.8±0.6
	Table 4.5: Macro-average top-K accuracy (on test set) for different losses measured on Pl@ntNet-300K,
	a heavy-tailed dataset with high ambiguity (ResNet-50 model). The three numbers in parentheses
	represent respectively the mean top-K accuracies of 1) few shot classes (< 20 training images) 2)
	medium shot classes (20 ≤ . ≤ 100 training images) 3) many shot classes (> 100 training images).
	K	1			3	5
	ℓ CE	36.3±0.3 (12.6/42.9/71.7) 58.8±0.4 (32.4/75.3/92.0) 68.7±0.2 (45.1/86.3/95.4)
	ℓ K,0.1 Smoothed Hinge	35.7±0.2 (13.1/41.5/71.1) 50.3±0.2 (16.7/69.8/92.7) 50.9±0.3 (12.1/78.1/95.7)
	ℓ K,1.0,5 Noised bal.	35.8±0.3 (12.4/42.1/72.1) 58.7±0.4 (32.2/73.8/88.8) 66.4±0.5 (42.0/82.5/95.5)
	focal (γ = 2.0)	37.6±0.3 (15.5/43.4/71.4)	60.4±0.3 (35.9/74.8/92.0) 69.7±0.2 (47.5/84.8/95.8)
	ℓ max my=0.2 LDAM	40.6±0.1 (20.9/45.8/71.2)	63.3±0.3 (43.0/74.1/90.0) 71.9±0.3 (54.0/83.0/94.0)
	ℓ K,0.01,5,max my=0.2 Noised imbal.	42.4±0.3 (23.9/46.3/72.1) 64.9±0.4 (44.8/74.5/92.1) 73.2±0.5 (55.3/84.2/95.3)

Table 4 . 6 :

 46 Top-K accuracy (on test set) for different losses measured on ImageNet-LT (ResNet-34 model). The three numbers in parentheses represent respectively the mean top-K accuracies of 1) few shot classes (< 20 training images) 2) medium shot classes (20 ≤ . ≤ 100 training images) 3) many shot classes (> 100 training images).

	K	1	3	5
	ℓ CE	37.0±0.1 (1.5/28.2/60.6)	55.5±0.1 (8.2/53.0/75.3)	63.2±0.1 (15.8/63.1/80.1)
	ℓ K,0.1 Smoothed Hinge	37.3±0.1 (1.3/28.6/60.7)	42.0±0.1 (0.0/29.1/72.9)	39.0±0.1 (0.0/20.7/75.5)
	focal (γ = 1.0)	37.7±0.0 (2.4/29.8/59.9)	56.2±0.0 (10.2/54.0/75.1) 63.8±0.1 (17.8/63.6/80.3)
	ℓ max my=0.4 LDAM	39.3±0.2 (10.5/33.1/57.1) 56.0±0.2 (24.1/52.0/72.3)	63.1±0.2 (32.9/60.1/77.7)
	ℓ K,0.1,5,max my=0.4 Noised imbal.	38.7±0.0 (7.6/32.3/57.6)	56.5±0.1 (27.0/52.6/71.7) 63.5±0.1 (37.0/60.2/77.0)

Table 4 .

 4

		7: top-1 accuracy cifar100
	Label noise	ℓ K CE	ℓ 5,1.0 Smoothed Hinge	ℓ 5,0.2,10 Noised bal.
	0.0	76.6±0.1	69.2±0.1	68.7±0.3
	0.1	71.0±0.2	71.2±0.4	68.3±0.5
	0.2	68.1±0.1	71.3±0.3	69.4±0.5
	0.3	65.5±0.3	70.8±0.6	69.3±0.3
	0.4	61.8±0.4	70.6±0.2	69.1±0.4

Table 4 .

 4 8: regular top-K accuracy corresponding to the models inTable 4.5

	K	ℓ CE	ℓ K,τ Smoothed Hinge	ℓ K,ϵ,M Noised bal.	focal	K,ϵ,M,my LDAM ℓ Noised imbal.
	1	80.1±0.1	79.8±0.0	80.8±0.1 79.8±0.1 79.6±0.1 81.0±0.1
	3	93.1±0.0	93.2±0.0	93.5±0.1 93.5±0.0 92.3±0.1 93.5±0.1
	5	95.7±0.0	95.0±0.1	95.8±0.0 96.0±0.0 95.2±0.2 95.8±0.1
	10 97.5±0.0	95.5±0.0	97.5±0.0 97.7±0.0 97.2±0.1 97.5±0.0

Table 4 . 9 :

 49 ImageNet test top-K accuracy, ResNet-18.

	K	ℓ CE	ℓ K,0.1 Smoothed Hinge	ℓ K,0.5,10 Noised bal.
	1 72.24±0.15 71.43±0.14 72.46±0.15
	5 90.60±0.05 90.71±0.06 90.52±0.07

  ,M

	Noised bal.

96.83 ± 0.16 97.35 ± 0.06 96.12 ± 0.11 96.71 ± 0.02 95.88 ± 0.05 96.32 ± 0.05

Table 5 .

 5

1: CIFAR-100 test average-5 accuracy,

Table 5 . 2 :

 52 Pl@ntNet-300K test average-K accuracy (ResNet-18). The three numbers in parentheses represent respectively the mean average-K accuracies of 1) few shot classes (< 20 training images) 2) medium shot classes (20 ≤ • ≤ 100 training images) 3) many shot classes (> 100 training images).

Table 5 . 4 :

 54 Hyperparameters selected after grid search for the Pl@ntNet-300K experiments.

https://www.gbif.org/

The division is performed at the species level due to the long-tailed distribution.

The architectures chosen are: alexnet (1), densenet121 (2), densenet161 (3), densenet169 (4), densenet201 (5), efficientnet_b1 (6), efficientnet_b1 (7), efficientnet_b2 (8), efficientnet_b3 (9), effi-cientnet_b4 (10), inception_resnet_v2 (11), inception_v3 (12), inception_v4 (13), mobilenet_v2 (14), mobilenet_v3_large (15), mobilenet_v3_small (16), resnet101 (17), resnet152 (18), resnet18 (19), resnet34 (20), resnet50 (21), shufflenet (22), squeezenet (23), vgg11 (24), vit_base_patch16_224 (25),

Source: https://doi.org/10.5281/zenodo.5645731

Ties are broken arbitrarily.

See for instanceFigure 4.1(a) for a visualization.

For illustrations with K = 1, see Figures

4.6(h) and 4.6(j)

For experiments with CIFAR-100, we consider a DenseNet 40-40 model[START_REF] Huang | Densely Connected Convolutional Networks[END_REF], similarly as[START_REF] Berrada | Smooth Loss Functions for Deep Top-k Classification[END_REF].

For the experiments with Pl@ntNet-300K, we consider a ResNet-50 model[START_REF] He | Deep residual learning for image recognition[END_REF].

Remerciements

test set in Table 4.5 (three seeds, 95% confidence interval). We find that the loss from [START_REF] Berrada | Smooth Loss Functions for Deep Top-k Classification[END_REF] fails to generalize to the tail classes in such an imbalanced setting. In contrast, ℓ K,ϵ,M Noised bal. gives results similar to the cross-entropy while ℓ

K,ϵ,M,my

Noised imbal. provides the best results (regardless of the value of K). Noticeably, it outperforms ℓ my LDAM [START_REF] Cao | Learning Imbalanced Datasets with Label-Distribution-Aware Margin Loss[END_REF] for all cases.

ImageNet-LT

We test ℓ K,ϵ,M,my Noised imbal. on ImageNet-LT [START_REF] Liu | Large-Scale Long-Tailed Recognition in an Open World[END_REF], a dataset of 115,836 training images obtained by subsampling images from ImageNet with a pareto distribution. The resulting class imbalance is much less pronounced than for Pl@ntNet-300K.

We train a ResNet34 with several losses for K ∈ {1, 3, 5} for 100 epochs with a learning rate of 1.10 -2 divided by 10 at epoch 60 and 80. We use a batch size of 128 and set the weight decay to 2.10 -3 . All hyperparameters are tuned on the 20,000 images validation set from [START_REF] Liu | Large-Scale Long-Tailed Recognition in an Open World[END_REF]. The results on the test set (four seeds, 95% confidence interval) are reported in Table 4.6. They show that ℓ K,ϵ,M,my Noised Imbal. performs very well on few shot classes compared to the other losses. Since ImageNet-LT is much less imbalanced than Pl@ntNet-300K, there are fewer such classes, hence the overall gain is less salient than for Pl@ntNet-300K.

Conclusion and perspectives

We propose a novel top-K loss as a smoothed version of the top-K calibrated hinge loss of [START_REF] Yang | On the consistency of top-k surrogate losses[END_REF]. Our loss function is well suited for training deep neural networks, contrarily to the original top-K calibrated hinge loss (e.g., the poor performance of the case ϵ = 0 in Table 4.2, that reduces to their loss). The smoothing procedure we propose applies the perturbed optimizers framework to smooth the top-K operator. We show that our loss performs well compared to the current state-of-the-art top-K losses for deep learning while being significantly faster to train when K increases. At training, the gradient of our loss w.r.t. the score is sparse, showing that non-sparse gradients are not necessary for successful learning. Finally, a slight adaptation of our loss for imbalanced datasets (leveraging uneven margins) outperforms other baseline losses. Studying deep learning optimization methods for other set-valued classification tasks, such as average size control or point-wise error control [START_REF] Chzhen | Set-valued classification -overview via a unified framework[END_REF] are left for future work.

• Using the notation from [Ber+20, Appendix A], with F (s) = topΣ K (s) and F ϵ (s) = topΣ K,ϵ (s), we get the following bounds:

Additionally, using the maximal inequality for i.i.d. Gaussian variables, see for instance [BLM13, Section 2.5], leads to:

Subtracting (4.21) to (4.20), and reminding that τ K (s) = topΣ K (s) -topΣ K-1 (s) (and similarly τ K,ϵ (s) = topΣ K,ϵ (s) -topΣ K-1,ϵ (s)) gives:

thus leading to:

with

Proof of Proposition 4.3.7

Proof.

• First, note that s → ℓ K,ϵ Noised bal. (s, y) is continuous as a composition and sum of continuous functions. It is differentiable wherever ψ : s → 1 + τ K+1,ϵ (s)s y is non-zero. From Definition 4.3.4 and Proposition 4.3.3 we get ∇ s ψ(s) = E[arg topΣ K+1 (s + ϵZ)] -δ y . The formula of the gradient follows from the chain rule.

Illustrations of the various losses encountered

In Figures 4.1 and 4.6, we provide a visualization of the loss landscapes for respectively K = 1 and K = 2 with L = 3 labels. With L = 3 labels, we display the visualization as level-sets restricted to a rescaled simplex: 2 . . . ∆ 2 . Moreover, we have min/max rescaled all the losses so that they fully range the interval [0, 1]. Note that as we are mainly interested in minimizing the losses, this post-processing would not modify the learned classifiers.

We provide also two additional figures illustrating the impact on our loss of the two main parameters: ϵ and M . 4.1, for L = 3 classes, K = 1 and a true label y = 2 (corresponding to the upper corner of the triangles). For visualization the loss are rescaled between 0 and 1, and the level sets are restricted to vector s ∈ 2 • ∆ 2 . The losses have been harmonized to display a margin equal to 1. For our proposed loss, we have averaged the level sets over 100 replications to avoid meshing artifacts.

CHAPTER 5 CHAPTER 6 the sparsemax [START_REF] Martins | From softmax to sparsemax: A sparse model of attention and multi-label classification[END_REF] was introduced as a substitution for softmax. We recall its definition:

CONCLUSION AND PERSPECTIVES

It consists simply of the orthogonal projection on the simplex. The authors have shown that equation (6.6) leads to the following sparse solution:

sparsemax(s) j = max(0, s j -τ (s)) , (

where τ : R L → R is the unique function that satisfies, for all s ∈ R L :

From (6.7) is is clear that sparsemax only has some components activated while the rest are zero. sparsemax is obtained by simple thresholding of the logits, where components below the threshold are zeroed out and where the threshold is chosen so that the sum of the "excess" L j=1 max(0, s j -τ (s)) is equal to one. As softmax is used for the cross-entropy loss, similarly, we can design a loss function with sparsemax. We recall that the cross-entropy loss is defined by: ℓ CE (s, y) = -log(softmax y (s)) , (6.9) whose gradient reads:

∇ s ℓ CE (s, y) = -δ y + softmax(s) , (6.10)

where δ y is the vector with one at coordinate y and 0 otherwise. By analogy to (6.10), the authors of sparsemax have designed a loss whose gradient is equal to:

∇ s ℓ sparsemax (s, y) = -δ y + sparsemax(s) , (6.11) which by integration yields:

where S(s) :== {j, sparsemax j (s) > 0}. The sparsemax is not well suited for multilabel classification. Indeed, it produces a vector p in the simplex, which is appropriate for multiclass classification, but what if we want to predict several labels? Actually, the authors proposed as an application of the sparsemax the task of proportion estimation, where the target is a proportion q ∈ ∆ L-1 . This problem can occur in an agronomic context for instance, when you have to estimate grain proportion. But in multilabel classification, the target y ∈ {0, 1} L does not belong to the simplex, it is a vector of zeros and ones. The sparsemax can not predict such a distribution as it sums to one. What could be done is to normalize such labels so that they belong to the simplex. For instance, a target vector y =

This is a bit odd, as this would lead to stronger signal for examples with few classes and a more diffuse response for examples with many classes. Instead, we would like to directly predict the 0/1 target vector. For this purpose, we introduce sparse-top as:

sparse-top(K, s) := arg min q∈∆ L-1 K ∥s -q∥ 2 (6.13)

Computation of sparse-top

Equation (6.13) actually belongs to a family of problems known as continuous quadratic knapsack [START_REF] Helgason | A polynomially bounded algorithm for a singly constrained quadratic program[END_REF]. This type of problems can be found in many applications such as resource allocation [BH81; HH95], multicommodity network flow problems [START_REF] Ali | Computational comparison among three multicommodity network flow algorithms[END_REF], traffic equilibrium problems [DS69], etc.

As in the case K = 1, equation (6.13) admits a rather simple expression in the general case K ≥ 1:

where λ K : R L → [0, 1] is the threshold function that satisfies:

Equation (6.14) ressembles the particular K = 1 case of Equation (6.7). Again the solution is obtained by thresholding the logits. The difference is that this time, the solution is truncated at 1 and the sum of the "excess" (the difference between the logit and the threshold) must be equal to K. Equation (6.14) induces three disjoint sets: the coordinates whose projections is equal to one, the coordinates whose projections is equal to zero and the coordinates whose projections lies strictly between 0 and 1. Therefore we define:

The main difficulty in computing sparse-top for a given input vector s comes down to estimate the threshold λ K (s). Several algorithms have been developed to address this. They can be grouped into two groups: breakpoint searching methods [HKL80a; HH95; CH94; CM87; Bru84; MPJ89; PK90; Mac+03; Kiw07] and variable fixing methods [START_REF] Kiwiel | Variable fixing algorithms for the continuous quadratic knapsack problem[END_REF][START_REF] Ag Robinson | On the continuous quadratic knapsack problem[END_REF][START_REF] Michelot | A finite algorithm for finding the projection of a point onto the canonical simplex of R n[END_REF]. For breaking points methods, there are algorithms with complexity O(L) to find the threshold and therefore the whole sparse-top K is of complexity O(L), where L is the size of the input vector.