Vivien Sainte

Fare Garnot

Loic Landrieu
email: loic.landrieu@ign.fr

Leveraging Class Hierarchies with Metric-Guided Prototype Learning

In many classification tasks, the set of target classes can be organized into a hierarchy. This structure induces a semantic distance between classes, and can be summarized under the form of a cost matrix, which defines a finite metric on the class set. In this paper, we propose to model the hierarchical class structure by integrating this metric in the supervision of a prototypical network. Our method relies on jointly learning a feature-extracting network and a set of class prototypes whose relative arrangement in the embedding space follows an hierarchical metric. We show that this approach allows for a consistent improvement of the error rate weighted by the cost matrix when compared to traditional methods and other prototype-based strategies. Furthermore, when the induced metric contains insight on the data structure, our method improves the overall precision as well. Experiments on four different public datasets-from agricultural time series classification to depth image semantic segmentation-validate our approach.

+ , defined such that the cost of predicting class k when the

Introduction

Most classification models focus on maximizing the prediction accuracy, regardless of the semantic nature of errors. This can lead to high performing models, but puzzling errors such as confusing tigers and sofas, and casts doubt on what a model actually understands of the required task and data distribution. Neural networks in particular have been criticized for their tendency to produce improbable yet confident errors, notably when under adversarial attacks [START_REF] Akhtar | Threat of adversarial attacks on deep learning in computer vision: A survey[END_REF]. Training deep models to produce not only produce fewer but also better errors can increase their trustworthiness, which is crucial for downstream applications such as autonomous driving or land use and land cover monitoring [START_REF] Bertinetto | Making better mistakes: Leveraging class hierarchies with deep networks[END_REF][START_REF] Deng | What does classifying more than 10,000 image categories tell us?[END_REF].

In many classification problems, the target classes can be organized according to a treeshaped hierarchical structure. Such a taxonomy can be generated by domain experts, or automatically inferred from class names using the WordNet graph [START_REF] Miller | Introduction to wordnet: An on-line lexical database[END_REF] or from word embeddings [START_REF] Mikolov | Efficient estimation of word representations in vector space[END_REF]. A step towards more reliable and interpretable algorithms would be to explicitly model the difference of gravity between errors, as defined by a hierarchical nomenclature.

For a classification task over a set K of K classes, the hierarchy of errors can be encapsulated by a cost matrix D ∈ R K×K true class is l is D[k, l] ≥ 0, and D[k, k] = 0 for all k = 1 • • • K. Among many other options [START_REF] Kosmopoulos | Evaluation measures for hierarchical classification: a unified view and novel approaches[END_REF], one can define D[k, l] as the length of the shortest path between the nodes corresponding to classes k and l in the tree-shaped class taxonomy.

As pointed out by Bertinetto et al. [START_REF] Bertinetto | Making better mistakes: Leveraging class hierarchies with deep networks[END_REF], the first step towards algorithms aware of hierarchical structures would be to generalize the use of cost-based metrics. For example, early iterations of the ImageNet challenge [START_REF] Deng | What does classifying more than 10,000 image categories tell us?[END_REF][START_REF] Russakovsky | Imagenet large scale visual recognition challenge[END_REF] proposed to weight errors according to hierarchy-based costs. For a dataset indexed by N , the Average Hierarchical Cost (AHC) between class predictions y ∈ K N and the true labels z ∈ K N is defined as:

AHC(y, z) = 1 |N | ∑ n∈N D[y n , z n ] . (1)
Along with the evaluation metrics, the loss functions should also take the cost matrix into account. While it is common to focus on retrieving certain classes through weighting [START_REF] Samuel Rota Bulo | Loss max-pooling for semantic image segmentation[END_REF][START_REF] Lin | Focal loss for dense object detection[END_REF] or sampling [START_REF] Shrivastava | Training region-based object detectors with online hard example mining[END_REF][START_REF] Sung | Learning and example selection for object and pattern detection[END_REF] schemes, preventing confusion between specific classes is less straightforward. For example, the cross entropy with one-hot target vectors singles out the predicted confidence for the true class, but treats all other classes equally. Beyond reducing the AHC, another advantage of incorporating the class hierarchy into the learning phase is that D may contain information about the structure of the data as well. Although it is not always the case, co-hyponyms (i.e. siblings) in a class hierarchy tend to share some structural properties. Encouraging such classes to have similar representations could lead to more efficient learning, e.g. by leveraging common feature detectors. Such priors on the class structure may be especially crucial when dealing with a large taxonomy, as noted by Deng et al. [START_REF] Deng | What does classifying more than 10,000 image categories tell us?[END_REF].

In this paper, we introduce a method to integrate a pre-defined class hierarchy into a classification algorithm. We propose a new distortion-based regularizer for prototypical network [START_REF] Chen | This looks like that: deep learning for interpretable image recognition[END_REF]51]. This penalty allows the network to learn prototypes organized so that their pairwise distances reflect the error cost defined by a class hierarchy. Our contributions are as follows:

• We introduce a scale-independent formulation of the distortion between two metric spaces and an associated smooth regularizer.

• This formulation allows us to incorporate knowledge of the class hierarchy into a neural network at no extra cost in trainable parameters and computation.

• We show on four public datasets (CIFAR100 , NYUDv2, S2-Agri, and iNaturalist-19) that our approach decreases the average cost of the prediction of standard backbones.

• As illustrated in Figure 1, we show that our approach can also lead to a better (unweighted) precision, which we attribute to the useful priors contained in the hierarchy.

Related Work

Prototypical Networks: Our approach builds on the growing corpus of work on prototypical networks. These models are deep learning analogues of nearest centroid classifiers [START_REF] Tibshirani | Diagnosis of multiple cancer types by shrunken of the National of Sciences, Grant Van Horn[END_REF] and Learning Vector Quantization networks [START_REF] Kohonen | Learning vector quantization[END_REF][START_REF] Sato | Generalized learning vector quantization[END_REF], which associate to each class a representation, or prototype, and classify the observations according to the nearest prototype. These networks have been successfully used for few-shot learning [START_REF] Dong | Few-shot semantic segmentation with prototype learning[END_REF][START_REF] Snell | Prototypical networks for few-shot learning[END_REF], zero-shot learning [START_REF] Jetley | Prototypical priors: From improving classification to zero-shot learning[END_REF], and supervized classification [START_REF] Chen | This looks like that: deep learning for interpretable image recognition[END_REF][START_REF] Guerriero | DeepNCM: deep nearest class mean classifiers[END_REF][START_REF] Mettes | Hyperspherical prototype networks[END_REF]51].

In most approaches, the prototypes are directly defined as the centroid of the learnt representations of samples of their classes, and updated at each episode [START_REF] Snell | Prototypical networks for few-shot learning[END_REF] or iteration [START_REF] Guerriero | DeepNCM: deep nearest class mean classifiers[END_REF]. In the work of Mettes et al. [START_REF] Mettes | Hyperspherical prototype networks[END_REF] and Jetley et al. [START_REF] Jetley | Prototypical priors: From improving classification to zero-shot learning[END_REF], the prototypes are defined prior to learning the embedding function. In this work, we follow the approach of [51] and learn the prototypes simultaneously with the data embedding function.

Hierarchical Priors: The idea of exploiting the latent taxonomic structure of semantic classes to improve the accuracy of a model has been extensively explored [START_REF] Carlos | A survey of hierarchical classification across different application domains[END_REF], from traditional Bayesian modeling [START_REF] Gelman | Bayesian data analysis[END_REF]Chapter 5] to adaptive deep learning architectures [START_REF] Ayub | ECG classification and abnormality detection using cascade forward neural network[END_REF][START_REF] Roy | Tree-CNN: a hierarchical deep convolutional neural network for incremental learning[END_REF][START_REF] Salakhutdinov | Learning with hierarchical-deep models[END_REF]50]. However, for these neural networks, the hierarchy is discovered by the network itself to improve the overall accuracy of the model. In our setting, the hierarchy is defined a priori and serves both to evaluate the quality of the model and to guide the learning process towards a reduced prediction cost. [START_REF] Srivastava | Discriminative transfer learning with treebased priors[END_REF] propose to implement Gaussian priors on the weight of neurons according to a fixed hierarchy. Redmon and Farhadi [START_REF] Redmon | YOLO9000: better, faster, stronger[END_REF] implements an inference scheme based on a tree-shaped graphical model derived from a class taxonomy. Closest to our work, Hou et al. [START_REF] Hou | Squared earth mover's distance-based loss for training deep neural networks[END_REF] propose a regularization based on the earth mover distance to penalize errors with high cost.

Srivastava and Salakhutdinov

More recently, Bertinetto et al. [START_REF] Bertinetto | Making better mistakes: Leveraging class hierarchies with deep networks[END_REF] highlighted the relative lack of well-suited methods for dealing with hierarchical nomenclatures in the deep learning literature. They advocate for a more widespread use of the AHC for evaluating models, and detail two simple baseline classification modules able to decrease the AHC of deep models: Soft-Labels and Hierarchical Cross-Entropy. See the appendix for more details on these schemes. Following this objective, Karthik et al. [START_REF] Karthik | No cost likelihood manipulation at test time for making better mistakes in deep networks[END_REF] propose a an inference-time risk minimization scheme to reduce the AHC of the predictions based on the predicted posteriors.

Hyperbolic Prototypes: Motivated by their capacity to embed hierarchical data structures into low-dimensional spaces, [START_REF] De Sa | Representation tradeoffs for hyperbolic embeddings[END_REF], hyperbolic spaces are at the center of recent advances in modeling hierarchical relations [START_REF] Khrulkov | Hyperbolic image embeddings[END_REF][START_REF] Nickel | Poincaré embeddings for learning hierarchical representations[END_REF]. Closer to this work, [START_REF] Liu | Hyperbolic visual embedding learning for zero-shot recognition[END_REF][START_REF] Long | Searching for actions on the hyperbole[END_REF] also propose to embed a class hierarchy into the latent representation space. However, both approaches embed the class hierarchy before training the data embedding network. In contrast, we argue that incorporating the hierarchical structure during the training of the model allows the network and class embeddings to share their respective insights, leading to a better trade-off between AHC and accuracy. In this paper, we only explore Euclidean geometry, as this setting allows for the seamless integration of our method without changing the number of bits of precision or the optimizer [START_REF] De Sa | Representation tradeoffs for hyperbolic embeddings[END_REF].

Finite Metric Embeddings: Our objective of computing class representations with pairwise distances determined by a cost matrix has links with finding an isometric embedding of the cost matrix-seen as a finite metric. This problem has been extensively studied [START_REF] Bourgain | On Lipschitz embedding of finite metric spaces in Hilbert space[END_REF][START_REF] Indyk | Low-distortion embeddings of finite metric spaces[END_REF] and is at the center of the growing interest for hyperbolic geometry [START_REF] De Sa | Representation tradeoffs for hyperbolic embeddings[END_REF]. Here, our goal is simply to influence the learning of prototypes with a metric rather than necessarily seeking the best possible isometry.

Method

We consider a generic dataset N of N elements x ∈ X N with ground truth classes z ∈ K N . The classes K are organized along a tree-shape hierarchical structure, allowing us to define a cost matrix D by considering the shortest path between nodes. The matrix thus defined is symmetric, with a zero diagonal, strictly positive elsewhere, and respects the triangle inequality: D[k, l] + D[l, m] ≥ D[k, m] for all k, l, m in K. In other words, D defines a finite metric. We denote by Ω an embedding space which, when equipped with the distance function d : Ω × Ω → R + , forms a continuous metric space.

Prototypical Networks

A prototypical network is characterized by an embedding function f : X → Ω, typically a neural network, and a set π ∈ Ω K of K prototypes. π must be chosen such that any sample x n of true class k has a representation f (x n ) which is close to π k and far from other prototypes.

Following the methodology of Snell et al. [START_REF] Snell | Prototypical networks for few-shot learning[END_REF], a prototypical network ( f , π) associates to an observation x n the posterior probability over its class z n defined as follows:

p(z n = k|x n ) = exp (-d ( f (x n ), π k )) ∑ l∈K exp (-d ( f (x n ), π l )) , ∀k ∈ K (2)
We define an associated loss as the normalized negative log-likelihood of the true classes:

L data ( f , π) = 1 N ∑ n∈N d( f (x n ), π z n ) + log ∑ l∈K exp (-d( f (x n ), π l )) . (3)
This loss encourages the representation f (x n ) to be close to the prototype of the class z n and far from the other prototypes. Conversely, the prototype π k is drawn towards the representations f (x n ) of samples n with true class k, and away from the representations of samples of other classes.

Following the insights of [51], the embedding function f and the prototypes π are learned simultaneously. This differs from many works on prototypical networks which learn prototypes separately or define them as centroids of representations. We take advantage of this joint training to learn prototypes which take into account both the distribution of the data and the relationships between classes, as described in the next section.

Metric-Guided Penalization

We propose to incorporate the cost matrix D into a regularization term in order to encourage the prototypes' positions in the embedding space Ω to be consistent with the finite metric defined by D. Since the sample representations are attracted to their respective prototypes in [START_REF] Bertinetto | Making better mistakes: Leveraging class hierarchies with deep networks[END_REF], such regularization will also affect the embedding network.

Metric Distortion As described in De Sa et al. [START_REF] De Sa | Representation tradeoffs for hyperbolic embeddings[END_REF], the distortion of a mapping k → π k between the finite metric space (K, D) and the continuous metric space (Ω, d) can be defined as the average relative difference between distances in the source and target space:

disto(π, D) = 1 K(K -1) ∑ k,l∈K 2 , k =l |d(π k , π l ) -D[k, l]| D[k, l] . (4)
We argue that a network ( f , π) trained to minimize L data and whose prototypes π have a low distortion with respect to D should produce errors with low hierarchical costs. To understand the intuition behind this idea, let us consider a sample x n of true class k and misclassified as class l. This tells us that the distance between f (x n ) and π l is small. If k and l have a high cost according to D, and since k → π k is of low distortion, then d(π k , π l ) must be large. The triangular inequality tells us that d( f

(x n ), π k ) ≥ d(π k , π l ) -d( f (x n ), π l )
, and consequently that d( f (x n ), π k ) must be large as well, which contradicts that ( f , π) minimizes L data .

Scale-Free Distortion For a prototype arrangement π to have a small distortion with respect to a finite metric D as defined in Equation 4, the distance between prototypes must correspond to the distance between classes. This imposes a specific scale on the distances between prototypes in the embedding space. This scale may conflict with the second term of L data which encourages the distance between embeddings and unrelated prototypes to be as large as possible. Therefore, lower distortion may also cause lower precision. To remove this conflicting incentive, we introduce a scale-independent formulation of the distortion [START_REF] Brankatschk | Modeling crop rotation in agricultural lcas-challenges and potential solutions[END_REF] where s • π are the scaled prototypes, whose coordinates in Ω are multiplied by a scalar factor s. As shown in the appendix, disto scale-free can be efficiently computed algorithmically.

disto scale-free (π, D) = min

s∈R + disto(s • π, D) , (5)
Distortion-Based Penalization We propose to incorporate the error qualification D into the prototypes' relative arrangement by encouraging a low scale-free distortion between π and D. To this end, we define L disto , a smooth surrogate of disto scale-free [START_REF] Donald | Critical reviews in plant sciences[END_REF]. as detailed in the appendix, L disto can be computed in closed form as a function of π and can be directly used as a regularizer.

L disto (π) = 1 K(K -1) min s∈R + ∑ k,l∈K 2 , k =l sd(π k , π l ) -D[k, l] D[k, l] 2 . ( 6
)

End-to-end Training

We combine L data and L disto in a single loss L. L data allows to jointly learn the embedding function f and the class prototypes π, while L disto enforces a metric-consistent prototype arrangement, with λ ∈ R + an hyper-parameter setting the strength of the regularization:

L( f , π) = L data ( f , π) + λ L disto (π) . (7)
4 Experiments We evaluate our approach with different tasks and public datasets with fine-grained class hierarchies: image classification on CIFAR100 [START_REF] Krizhevsky | Learning multiple layers of features from tiny images[END_REF] and iNaturalist-19 [49], RGB-D image segmentation on NYUDv2 [START_REF] Kohli | Indoor segmentation and support inference from RGBD images[END_REF], and image sequence classification on S2-Agri [START_REF] Sainte | Satellite image time series classification with pixel-set encoders and temporal selfattention[END_REF]. We define the cost matrix of these class sets as the length of the shortest path between nodes in the associated tree-shape taxonomies represented in the Appendix. As shown in Table 1, these datasets cover different settings in terms of data distribution and hierarchical structure.

Datasets and Backbones

Illustrative Example on MNIST:

In Figure 1, we illustrate the difference in performance and embedding organization of the embedding space for different approaches. We use a small 3-layer convolutional net trained on MNIST with random rotations (up to 40 degrees) and affine transformations (up to 1.3 scaling). For plotting convenience, we set the features' dimension to 2.

Image Classification on CIFAR100: We use a super-class system inspired by Krizhevsky et al. [START_REF] Krizhevsky | Learning multiple layers of features from tiny images[END_REF] and form a 5-level hierarchical nomenclature of size: 2, 4, 8, 20, and 100 classes. We use as backbone the established ResNet-18 [START_REF] He | Deep residual learning for image recognition[END_REF] as embedding network for this dataset.

RGB-D Semantic Segmentation on NYUDv2: We use the standard split of 795 training and 654 testing pairs. We combine the 4 and 40 class nomenclatures of Gupta et al. [START_REF] Gupta | Perceptual organization and recognition of indoor scenes from RGB-D images[END_REF] and the 13 class system defined by Handa et al. [START_REF] Handa | Uunderstanding real world indoor scenes with synthetic data[END_REF] to construct a 3-level hierarchy. We use FuseNet [START_REF] Hazirbas | Fusenet: Incorporating depth into semantic segmentation via fusion-based CNN architecture[END_REF] as backbone for this dataset.

Image Sequence Classification on S2-Agri: S2-Agri is composed of 189 971 sequences of multi-spectral satellite images of agricultural parcels. We define a 4-level crop type hierarchy of size 4, 12, 19, and 44 classes with the help of experts from a European agricultural monitoring agency (ASP). We use the PSE+TAE architecture [START_REF] Sainte | Satellite image time series classification with pixel-set encoders and temporal selfattention[END_REF] as backbone, and follow their 5-fold cross-validation scheme for training. Crop mapping in particular benefits from predictions with a low hierarchical cost. Indeed, payment agencies monitor the allocation of agricultural subsidies and whether crop rotations follow best practice recommendations [START_REF] Grant | The common agricultural policy[END_REF]. The monetary and environmental impact of misclassifications are typically reflected in the class hierarchy designed by domain experts [START_REF] Brankatschk | Modeling crop rotation in agricultural lcas-challenges and potential solutions[END_REF][START_REF] Donald | Critical reviews in plant sciences[END_REF]. By achieving a low AHC, we ensure that these downstream tasks can be meaningfully realized from the predictions.

Fine-Grained Image Classification on iNaturalist-19 (iNat-19) iNat-19 [49] contains 1 010 different classes organized into a 7 level hierarchy with respective width 3, 4, 9, 34, 57, 72, and 1 010. We use ResNet-18 pretrained on ImageNet as backbone. We sample 75% of available images for training, while the rest is evenly split into a validation and test set.

Hyper-Parameterization

The embedding space Ω is chosen as R 512 for iNat-19 and R 64 for all other datasets. We chose d as the Euclidean norm. (see 4.6 for a discussion on this choice). We evaluate our approach (Guided-proto) with λ = 1 in (7) for all datasets. We use the same training schedules and learning rates as the backbone networks in their respective papers. In particular, the class imbalance of S2-Agri is handled with a focal loss [START_REF] Lin | Focal loss for dense object detection[END_REF].

Competing methods

In the paper where they are introduced, all backbone networks presented in Section 4.1 use a linear mapping between the sample representation and the class scores, as well as the crossentropy loss. The resulting performance defines a baseline, denoted as Cross-Entropy, and is used to estimate the gains in Average Hierarchical Cost (AHC) and Error Rate (ER) provided by different approaches. We reimplemented other competing methods: Hierarchical Cross-Entropy (HXE) [START_REF] Bertinetto | Making better mistakes: Leveraging class hierarchies with deep networks[END_REF], Soft Labels [START_REF] Bertinetto | Making better mistakes: Leveraging class hierarchies with deep networks[END_REF], Earth Mover Distance regularization (XE+EMD) [START_REF] Hou | Squared earth mover's distance-based loss for training deep neural networks[END_REF], Hierarchical Inference (YOLO) [START_REF] Redmon | YOLO9000: better, faster, stronger[END_REF], Hyperspherical Prototypes (Hypersphericalproto) [START_REF] Mettes | Hyperspherical prototype networks[END_REF], and Deep Mean Classifiers (Deep-NCM) [START_REF] Guerriero | DeepNCM: deep nearest class mean classifiers[END_REF]. See the Appendix for more details on these methods. Lastly, we evaluate simple prototype learning (Learnt-proto) [51] by setting λ = 0 in [START_REF] Samuel Rota Bulo | Loss max-pooling for semantic image segmentation[END_REF].

Analysis

Overall Performance: As displayed in Figure 2, the benefits provided by our approach can be appreciated on all datasets. Compared to the Cross-Entropy baseline, our model improves the AHC by 3% on NYUDv2 and S2-Agri, and up to 9% and 14% for CIFAR100, and Guided-proto, the Cross-Entropy baseline (in bold), and competing approaches. Methods that use the hierarchical knowledge are indicated with the symbol . The best performances on each dataset are plotted in green. Our guided prototype approach improves both the ER and AHC across the four datasets compared to the baseline. The metrics are computed with the median over 5 runs for CIFAR100, the average over 5 cross-validation folds for S2-Agri, and a single run for NYUDv2 and iNat-19. The numeric values are given in the Appendix. ( : not evaluated).

iNat-19 respectively. The hierarchical inference scheme YOLO of Redmon and Farhadi [START_REF] Redmon | YOLO9000: better, faster, stronger[END_REF] performs on par or better than our methods for NYUDv2 and S2-Agri, while Soft-labels perform well on CIFAR100 and NYUDv2. Yet, metric guided prototypes brings the most consistent reduction of the hierarchical cost across all tasks, datasets, and class hierarchies configurations. This suggest that arranging the embedding space consistently with the cost metric is a robust way of reducing a model's hierarchical error cost. We argue that these results, combined with its ease of implementation, make a strong case for our approach.

While being initially designed to reduce the AHC, our method also provides a relative decrease of the ER by 3 to 4% across all datasets compared to the cross-entropy baseline. This indicates that cost matrices derived from the class hierarchies can indeed help neural networks to learn richer representations.

Prototype Learning: We observe that the learnt prototype approach Learnt-proto consistently outperforms the Deep-NCM method. This suggests that defining prototypes as the centroids of their class representations might actually be disadvantageous. As illustrated on Figure 1, the positions of the embeddings tend to follow a Voronoi partition [START_REF] Fortune | Voronoi diagrams and Delaunay triangulations[END_REF] with respect to the learnt prototypes of their true class rather than prototypes being the centroid of their associated representations. A surprising observation for us is that Learnt-proto consistently outperforms the Cross-Entropy baseline, both in terms of AHC and ER. For readability, we only display (in black) entries of the matrices with at least one confusion. We also represent the cost of confusing different classes in shades of reds (c). We note that our approach yields fewer confusions between pairs of classes with high costs, such as plants and animals.

Computational Efficiency: Computing distances between representations and prototypes is comparable in terms of complexity than computing a linear mapping. The scaling factor in L disto can be efficiently obtained as described in the Appendix. In practice, we observed that both training and inference time are identical for Cross-Entropy and Guided-proto: most of the time is taken by the computation of the embeddings. We observed that the Learnt-proto method decreases the AHC across all four datasets even though it does not take the cost matrix into account. This suggests that, given enough data, this simple model can learn an empirical taxonomy through its prototypes' arrangement. Furthermore, this taxonomy can share enough similarity with the one designed by experts to result in a decrease in AHC.

Restricted Training Data Regime

To further evaluate the benefit of explicitly using the expert taxonomy with our approach, we train the models Learnt-proto, Guided-proto, and EMD with only part of the 160k images in the training set of iNat-19, and without pretraining on ImageNet. To compensate for the lack of data, we increase the regularization strength to λ = 20.

In Figure 4, we observe that the two prototype-based approaches consistently improve the performance of the baseline for all training set sizes in terms of AHC. Moreover, the advantages brought by our proposed regularization are all the more significant when applied to small training sets. This observation reinforces the idea that the learnt-proto method requires large amounts of data to learn a meaningful class hierarchy in an unsupervized way.

Ablation Study

In the Appendix, we present an extensive ablation study. We present here its main take-away.

Scale-Free Distortion: Our method for automatically choosing the best scale in our smooth distortion surrogate leads to an improvement of 0.9 ER on the iNat-19 dataset, which amounts to half the improvement compared to the baseline. In the other datasets, the improvements were more limited. We attribute the impact of our scale-free distortion on iNat-19 in particular to the structure of its class hierarchy: at the lowest level, iNat-19 classes have on average 14 co-hyponyms (siblings), compared to only 2 to 5 for the other datasets. When minimizing the distortion with a fixed scale of 1, the prototypes of hyponyms are incentivized to be close with respect to d since hyponyms have a small hierarchical distance of 2. This clashes with the minimization of the second part of L data as defined in (3), which mutually repels prototypes of different classes. This conflict, made worse by classes with many hyponyms, is removed by our scale-free distortion. See the Appendix for additional insights into how our automatic scaling addresses this issue. Choice of Metric Space: Prototypical networks operating on Ω = R m typically use the squared Euclidean norm in the distance function, motivated by its quality as a Bregman divergence [START_REF] Snell | Prototypical networks for few-shot learning[END_REF]. However, given the large distance between prototypes induced by our regularization, this metric can cause stability issues. We observe for all datasets that that defining d as the Euclidean norm yields significantly better results across all datasets. Guided vs. fixed prototypes : As suggested by the lower performance of Hyperspherical-proto, jointly learning the prototypes and the embedding network can be advantageous. To confirm this observation, we altered our Guided-proto method to first learn the prototypes and then the embedding network. We observed a significant decrease in performance across the board, up to 5 more points of ER in iNat-19. Conversely, we altered Hyperspherical-proto to learn spherical prototypes together with the embedding network. This improved the performance of Hyperspherical-proto even though it remained worse than the Cross-Entropy baseline (+1.20 ER, +0.10 AHC on CIFAR100). These observations suggest that insights from the data distribution can benefit the positioning of prototypes, and that they should be learned conjointly.

Conclusion

We introduced a new regularizer modeling the hierarchical relationships between the classes of a nomenclature. This approach can be incorporated into any classification network at no computational cost and with very little added code. We showed that our method consistently decreased the average hierarchical cost of three different backbone networks on different tasks and four datasets. Furthermore, our approach can reduce the rate of errors as well. In contrast to most recent works on hierarchical classification, we showed that this joint training is beneficial compared to the staged strategy of first positioning the prototypes and then training a feature extracting network. A PyTorch implementation of our framework as well as an illustrative notebook are available at https://github.com/VSainteuf /metric-guided-prototypes-pytorch.

[50] Zhicheng Yan, Hao Zhang, Robinson Piramuthu, Vignesh Jagadeesh, Dennis DeCoste, Wei Di, and Yizhou Yu. HD-CNN: hierarchical deep convolutional neural networks for large scale visual recognition. In ICCV, 2015.

[51] Hong-Ming Yang, Xu-Yao Zhang, Fei Yin, and Cheng-Lin Liu. Robust classification with convolutional prototype learning. In CVPR, 2018.

Supplementary Materials -Leveraging Class Hierarchies with Metric-Guided Prototype Learning 6 Notebook and illustration

In Figure 5, we represent the embeddings and prototypes generated by variations of our networks as well as their respective performance. We note that the fixed prototypes approach performs significantly worse than our metric-guided method. We observe that the resulting prototypes are more compact when they are learned independently, which can lead to an increase in misclassification. We also remark that when the hierarchy contains no useful information, such as the arbitrary order of digits, the metric-based approach has a worse performance than the free (unguided) method. This is particularly drastic for the fixed prototype approach.

An illustrated notebook to reproduce this figure can be accessed at the following URL:

https://colab.research.google.com/drive/1VoQfBx5q5lWFev0cw xLZ0qQOZU7Rlmb_#offline=true&sandboxMode=true To run this notebook locally, you can also download it from our repository: https://github.com/VSainteuf/metric-guided-prototypes-pytorc h.

Additional methodological details 7.1 Scale-Independent Distortion

Computing the scale-free distortion defined in Equation 5 amounts to finding a minimizer of the following function f : R → R:

f (s) = ∑ i∈I |sα i -1| , (8)
with α k,l = d(π k , π l )/D[k, l] ≥ 0, and I an ordering of {k, l} k,l∈K 2 such that the sequence [α i ] i∈I is non-decreasing.

Proposition 1. A global minimizer of f defined in ( 8) is given by s = 1/α k with k defined as:

k = min k ∈ I ∑ i≤k α i ≥ ∑ i>k α i . (9)
Proof. First, such k exists as it is the smallest member of a discrete, non-empty set. Indeed, since all α i are nonnegative, the set contains at least k = |I|. We now verify that s = 1/α k is a critical point of f . By definition of k we have that ∑ i≤k α i ≥ ∑ i>k α i and ∑ i<k α i < ∑ i≥k α i . By combining these two inequalities, we have that The visual hierarchy is represented in (g) and the numerical order in (h). AHC vis corresponds to the cost defined by our proposed visual hierarchy, while AHC abs is defined after the chain-like structure obtained when organizing the digits along their numerical values. While embedding the metric with prototypes prior to learning the representations leads to lower (scale-free) distortion, this translates into worst performance in terms of AHC and ER. Joint learning achieves better performance on both evaluation metrics. We also remark that when the hierarchy is arbitrary (e-f), metric guiding is detrimental to precision. Since I orders the α i in increasing order, we can write the subgradient of f at s under the following form:

-∑ i<k α i + ∑ i>k α i ∈ [-α k , α k ] . ( 10
)
∂ s f (s ) = ∑ i<k ∂ s |s α i -1| + ∑ i>k ∂ s |s α i -1| + ∂ s |s α k -1| (11) = -∑ i<k α i + ∑ i>k α i + [-α k , α k ]. (12)
By using the inequality defined in Equation 10, we have that 0 ∈ ∂ s f (s ) and hence s is a critical point of f . Since f is convex, such s is also a global minimizer of f , i.e. an optimal scaling.

This proposition gives us a fast algorithm to obtain an optimal scaling and hence a scalefree distortion: compute the cumulative sum of the α k,l sorted in ascending order until the equality in ( 9) is first verified at index k . The resulting optimal scaling is then given by 1/α k .

Smooth Distortion

The minimization problem with respect to s defined in Equation 6 can be solved in closed form: In Figure 6, we represent the evolution of the scaling factor s * in L disto during training of our guided prototype method on the four datasets. Across all four models, s * presents a decreasing trend overall, which signifies that the average distance between prototypes increases. This is consistent with our analysis of prototypical networks: as the feature learning network and the prototypes are jointly learned, the samples' representations get closer to their true class' prototype. In doing so, they repel the other prototypes, which translate into an inflation of the global scale of the problem. Our optimal scaling allows the prototypes' scale to expand accordingly. Without adaptive scaling, the data loss (3) and regularizer [START_REF] Donald | Critical reviews in plant sciences[END_REF] would conflict. In all our experiments, this scale remained bounded and did not diverge. This can be explained by the fact that for each misclassification k → l of a sample x n , the representation f (x n is by definition closer to the erroneous prototype π l than of the true prototype π k . The first term of L data pushes the true prototype π k towards f (x n ), and by transitivity-towards the erroneous prototype π l . This phenomenon prevents prototypes from being pushed away from one another indefinitely. However, if the prediction is too precise, i.e. most samples are correctly classified, the prototypes may diverge. This setting, which we haven't yet encountered, may necessitate a regularization such as weight decay on the prototypes parameters.

s = ∑ d(π k , π l ) D[k, l] ∑ d(π k , π l ) 2 D[k, l] 2 . ( 13
)

Evolution of Optimal Scaling

Lastly, we remark that the asymptotic optimal scalings are different from one dataset to another. This can be explained foremost by differences in the depth and density of the class hierarchy of each dataset, as presented in Table 1. As explained above, the inherent difficulty of the classification tasks also have an influence on the problem's scale. However, our parameter-free method is able to automatically find an optimal scaling.

Inference

As with other prototypical networks, we associate to a sample n the class k whose prototype π k is the closest to the representation f (x n ) with respect to d, corresponding to the class of highest probability. This process can be made efficient for a large number of classes K and a high embedding dimension m with a KD-tree data structure, which offers a query complexity of O(log(K)) instead of O(K • m) for an exhaustive comparison. Hence, our method does not induce longer inference time than the cross-entropy for example, as the embedding function typically takes up the most time.

Rank-based Guiding

Following the ideas of Mettes et al. [START_REF] Mettes | Hyperspherical prototype networks[END_REF], we also experiment with a RankNet-inspired loss [START_REF] Burges | Learning to rank using gradient descent[END_REF] which encourages the distances between prototypes to follow the same order as the costs between their respective classes, without imposing a specific scaling:

L rank (π) = - 1 |T | ∑ k,l,m∈T Rk,l,m • log(R k,l,m ) + (1 -Rk,l,m ) • log(1 -R k,l,m ) , (14)
with

T = {(k, l, m) ∈ K 3 | k = l, l = m, k = m}

Additional experimental details

We give additional details on our experiments and some supplementary results in the following subsections.

Competing methods

Hierarchical Cross-Entropy (HXE) Bertinetto et al. [START_REF] Bertinetto | Making better mistakes: Leveraging class hierarchies with deep networks[END_REF] model the class structure with a hierarchical loss composed of the sum of the cross-entropies at each level of the class hierarchy. As suggested, a parameter α taken as 0.1 defines exponentially decaying weights for higher levels.

Soft Labels (Soft-labels) Bertinetto et al. [START_REF] Bertinetto | Making better mistakes: Leveraging class hierarchies with deep networks[END_REF] propose as second baseline in which the the one-hot target vectors are replaced by soft target vectors in the cross-entropy loss. These target vectors are defined as the softmin of the costs between all labels and the true label, with a temperature 1/β chosen as 0.1, as recommended in Bertinetto et al. [START_REF] Bertinetto | Making better mistakes: Leveraging class hierarchies with deep networks[END_REF].

Earth Mover Distance regularization (XE+EMD): Hou et al. [START_REF] Hou | Squared earth mover's distance-based loss for training deep neural networks[END_REF] propose to account for the relationships between classes with a regularization based on the squared earth mover distance. We use D as the ground distance matrix between the probabilistic prediction p and the true class y. This regularizer is added along the cross-entropy with a weight of 0.5 and an offset µ of 3.

Hierarchical Inference (YOLO): Redmon and Farhadi [START_REF] Redmon | YOLO9000: better, faster, stronger[END_REF] propose to model the hierarchical structure between classes into a tree-shaped graphical model. First, the conditional probability that a sample belongs to a class given its parent class is obtained with a softmax restricted to the class' co-hyponyms (i.e. siblings). Then, the posterior probability of a leaf class is given by the product of the conditional probability of its ancestors. The loss is defined as the cross-entropy of the resulting probability of the leaf-classes.

Hyperspherical Prototypes (Hyperspherical-proto): The method proposed by Mettes et al. [START_REF] Mettes | Hyperspherical prototype networks[END_REF] is closer to ours, as it relies on embedding class prototypes. They advocate to first position prototypes on the hypersphere using a rank-based loss (see Section 4.6) combined with a prototype-separating term. They then use the squared cosine distance between the image embeddings and prototypes to train the embedding network. Note that in our reimplementation, we used the finite metric defined by D instead of Word2Vec [START_REF] Mikolov | Efficient estimation of word representations in vector space[END_REF] embeddings to position prototypes. Lastly, we do not evaluate on S2-Agri as the integration of the focal loss is non-trivial.

Deep Mean Classifiers (Deep-NCM): Guerriero et al. [START_REF] Guerriero | DeepNCM: deep nearest class mean classifiers[END_REF] present another prototypebased approach. Here, the prototypes are the cumulative mean of the embeddings of the classes' samples, updated at each iteration. The embedding network is supervised with L data with d defined as the squared Euclidean norm.

Numerical results

The numerical values of the results shown in Figure 2 are given in Table 2.

---------------------

Ablation Studies

Choice of distance : In Table 3, we report the performance of the Guided-proto model on the four datasets when replacing the Euclidean norm with the squared Euclidean norm.

Across our experiments, the squared-norm based model yields a worse performance. This is a notable result as it is the distance commonly used in most prototypical networks [START_REF] Guerriero | DeepNCM: deep nearest class mean classifiers[END_REF][START_REF] Snell | Prototypical networks for few-shot learning[END_REF].

Rank-based Regularization: Mettes et al. [START_REF] Mettes | Hyperspherical prototype networks[END_REF] use a rank-based loss [START_REF] Burges | Learning to rank using gradient descent[END_REF] to encourage prototype mappings whose pairwise distance follows the same order as an external qualification of errors D. We argue that our formulation of L disto provides a stronger supervision than only considering the order of distances, and allows the prototypes to find a more profitable arrangement in the embedding space. In Table 3, we observe that replacing our distortionbased loss by a rank-based one results in a slight decrease of overall performance.

Robustness: As shown in Table 4, our presented method has low sensitivity with respect to regularization strength: models trained with λ ranging from 0.5 to 3 yield sensibly equivalent performances. Choosing λ = 1 seems to be the best configuration in terms of AHC. Hidden prototypes: In cases where the cost matrix D is derived from a tree-shaped class hierarchy, it is possible to also learn prototypes for the internal nodes of this tree, corresponding to super-classes of leaf-level labels. These prototypes do not appear in L data , but can be used in the prototype penalization to instill more structure into the embedding space.

In Table 4, line leaf-proto, we note a small but consistent improvement in terms of AHC resulting in associating prototypes for classes corresponding to the internal-nodes of the tree hierarchy as well.

Illustration of Results

In Figure 7 and Figure 3, we illustrate that our model particularly improves the classification rates of classes with high visual similarity and comparatively large error costs.

9 Additional Implementation Details CIFAR100 ResNet-18 is trained on CIFAR100 using SGD with initial learning rate l r = 10 -1 , momentum set to 0.9 and weight decay w d = 5 • 10 -4 . The network is trained for 200 epochs in batches of size 128, and the learning rate is divided by 5 at epochs 60, 120, and 160. The model is evaluated using its weights of the last epoch of training, and the results reported in the paper are median values over 5 runs.

NYUDv2

We train FuseNet on NYUDv2 using SGD with momentum set to 0.9. The learning rate is set initially to 10 -3 and multiplied at each epoch by a factor that exponentially decreases from 1 to 0.9. The network is trained for 300 epochs in batches of 4 with weight decay set to 5 • 10 -3 . We report the performance of the best-of-five last testing epochs.

S2-Agri

We train PSE+TAE on S2-Agri using Adam with l r = 10 -3 , β = (0.9; 0.999) and no weight decay. The dataset is randomly separated in five splits. For each of the five folds, 3 splits are used as training data on which the network is trained in batches of 128 samples for 100 epochs. The best epoch is selected based on its performance on the validation set, and we use the last split to measure the final performance of the model. We report the average performance over the five folds.

iNaturalist-19 Given the complexity of the dataset, we follow [START_REF] Bertinetto | Making better mistakes: Leveraging class hierarchies with deep networks[END_REF] and use a ResNet-18 pre-trained on ImageNet. The network is trained for 65 epochs in batches of 64 epochs using Adam with l r = 10 -4 , β = (0.9; 0.999) and no weight decay. The best epoch is selected based on the performance on the validation set, and we report the performance on the heldout test set.

Hierarchies used in Experiments

We present here the hierarchy used in the numerical experiments to derive the cost matrix. We define the cost between two classes as the length of the shortest path in the proposed treeshape hierarchy. The hierarchy of CIFAR100 is presented in Figure 8, NYUDv2 in Figure 9, Note that for S2-Agri, following [START_REF] Sainte | Satellite image time series classification with pixel-set encoders and temporal selfattention[END_REF] we have removed all classes that had less than 100 samples among the almost 200 000 parcels to limit the imbalance of the dataset.

things

Figure 1 :

 1 Figure 1: Mean class representation , prototypes , and 2-dimensional embeddings learnt on perturbed MNIST by a 3-layer convolutional net with three different classification modules: (a) crossentropy, (b) learnt prototypes, and (c) learnt prototypes guided by a tree-shaped taxonomy (constructed according to the authors' perceived visual similarity between digits). The guided prototypes (d) embed more faithfully the class hierarchy: classes with low error cost are closer. This is associated with a decrease in the Average Hierarchical Cost (AHC), as well as Error Rate (ER), indicating that our taxonomy may contain useful information for learning better visual features.

Figure 2 :

 2 Figure 2: Error Rate (ER) in % and Average Hierarchical Cost (AHC) on four datasets for

Figure 3 :

 3 Figure3: Partial confusion matrix for the "living organism" class subset of CIFAR100 for the Cross-Entropy baseline (a) and our approach (b). For readability, we only display (in black) entries of the matrices with at least one confusion. We also represent the cost of confusing different classes in shades of reds (c). We note that our approach yields fewer confusions between pairs of classes with high costs, such as plants and animals.

Figure 4 :

 4 Figure 4: AHC of ResNet-18 trained on restricted training sets of iNaturalist-19 with Guided-proto, Learnt-proto, and EMD. We represent the relative improvement compared to the performance of the Cross-Entropy baseline, which is shown on top of the plots.

Figure 5 :

 5 Figure 5: Mean class representation , prototypes , and 2-dimensional embeddings learnt on perturbed MNIST by a 3-layer convolutional net with six different classification modules: (a) cross-entropy, (b) learnt prototypes, (c) learnt prototypes guided by a visual taxonomy, (d) fixed prototypes (see Section 8.2) from a visual taxonomy , (e) learnt prototypes guided by the numbers' values, and (f) fixed prototypes from the numbers' values.The visual hierarchy is represented in (g) and the numerical order in (h). AHC vis corresponds to the cost defined by our proposed visual hierarchy, while AHC abs is defined after the chain-like structure obtained when organizing the digits along their numerical values. While embedding the metric with prototypes prior to learning the representations leads to lower (scale-free) distortion, this translates into worst performance in terms of AHC and ER. Joint learning achieves better performance on both evaluation metrics. We also remark that when the hierarchy is arbitrary (e-f), metric guiding is detrimental to precision.

Figure 6 :

 6 Figure 6: Evolution of the scaling factor s * in L disto along the training iterations of the four networks. We observe that s * consistently decreases to values smaller than 1, which allow the prototypes to spread apart while respecting the fix distances defined by D.

  the set of ordered triplet of K, Rk,l,m the hard ranking of the costs between D k,l and D k,m , equal to 1 if D k,l > D k,m and 0 otherwise, and R k,l,m = sigmoid(d(π k , π l )-d(π k , π m )) the soft ranking between d(π k , π l ) and d(π k , π m ). For efficiency reasons, we sample at each iteration only a S-sized subset of T . We use S = 10 in our experiments.

  (a) Porcupine ↔ Shrew -80%, D a = 4 (b) Caterpillar ↔ Lizard -64%, D b = 4 (c) Plate ↔ Clock -40%, D c = 4 (d) Streetcar ↔ Bus +58%, D d = 4 (e) Otter ↔ Seal +60%, D e = 2 (f) Boy ↔ Man +78%, D f = 2

Figure 7 :

 7 Figure 7: Best (a-c) and worse (d-f) improvements in terms of class confusion provided by Guided-proto compared to the cross-entropy baseline for CIFAR100, given in %, along with their error cost. The metric guided regularization particularly helps decreasing the confusions between classes that are visually similar (e.g. Plate and Clock) but are not direct siblings in the class hierarchy (D = 4). Conversely, the regularization hinders performance for visually similar siblings classes (e.g. Otter and Seal, D = 2).

Figure 8 :

 8 Figure 8: Class hierarchy for CIFAR100. The arcs at different radii represent the different classes of each level of the hierarchy. Unlabelled arcs share the same name as their parent class.

Figure 9 :

 9 Figure 9: Class hierarchy for NYUv2

Figure 10 :

 10 Figure 10: Class hierarchy for S2-Agri

Figure 11 :

 11 Figure 11: Class hierarchy for iNat-19, only the first 6 levels of the hierarchy are represented. At the time of writing, only the classes' obfuscated names were publicly available

Table 1 :

 1 Data

	Dataset	Data Volume (Gb) Samples	IR	Hierarchical Tree Depth Nodes (leaves) ABF	D
	NYUDv2	2.8	1449	93	3	57 (40)	5.0	4.3
	S2-Agri	28.2 189 971 617	4	83 (45)	5.8	6.5
	CIFAR100	0.2	60 000	1	5	134 (100)	3.8	7.0
	iNat-19	82.0 265 213	31	7	1189 (1010)	6.6	11.0

composition and taxonomies of the four studied datasets. IR stands for the Imbalance Ratio (largest over smallest class count), nodes and leaves denote respectively the total number of classes and leaf-classes in the tree-shape hierarchy, ABF stands for the Average Branching Factor, and D stands for the average pairwise distance.

Table 2 :

 2 Error Rate (ER) in % and Average Hierarchical Cost (AHC) on three datasets for our proposed methods (top) and the competing approaches (bottom). The values are computed with the median over 5 runs for CIFAR100, the average over 5 cross-validation folds for S2-Agri, and a single run for NYUDv2 and iNat-19. (HSP: Hyperspherical Prototypes, GP: Guided Prototypes).

		CIFAR100	NYUDv2	S2-Agri	iNat-19
		ER	AHC	ER	AHC	ER	AHC	ER	AHC
	Cross-Entropy 24.2 1.160	32.7 1.486	19.4 0.699	40.9 1.993
	HXE	24.1 1.168	32.4 1.456	19.5 0.731	41.8 2.013
	Soft-label	23.5 1.046	32.4 1.424	19.2 0.703	52.8 2.029
	XE+EMD	24.5 1.196	33.3 1.498	19.0 0.687	40.1 1.893
	YOLO	26.2 1.214	32.0 1.425	19.1 0.685	42.0 1.942
	HSP	29.4 1.472	49.7 2.329	-	-	42.4 2.027
	Deep-NCM	25.6 1.249	33.5 1.498	19.4 0.702	40.8 1.929
	Free-proto	23.8 1.091	32.5 1.462	19.1 0.691	38.8 1.728
	Fixed-proto	24.7 1.083	33.1 1.462	19.4 0.710	43.9 2.148
	GP-rank	23.3 1.056	32.7 1.445	19.1 0.691	39.3 1.718
	GP-disto	23.6 1.052	32.5 1.440	18.9 0.685	38.9 1.721

Table 3 :

 3 Influence of the choice of scaling in L disto , metric guiding regularizer, guiding scheme, and distance function d on the performance of Guided-proto on the four datasets. For d, we compare the performance of the Euclidean norm, the pseudo-Huberized Euclidean norm, and the square Euclidean norm.

		CIFAR100	NYUDv2	S2-Agri	iNat-19
		ER	AHC	ER	AHC	ER	AHC	ER	AHC
	Guided-proto	23.6	1.052	32.5	1.440	18.9	0.685	38.9	1.721
	Fixed-scale	+0.1 +0.003	0.0	0.000	+0.2 +0.001	+0.9	0.000
	Fixed-proto	+1.1 +0.031	+0.6 +0.013	+0.5	+0.025	+5.0 +0.427
	Rank-based guiding	-0.3	+0.004	+0.2 +0.005	+0.2	+0.006	+0.4	-0.003
	Squared Norm	+1.0 +0.118	0.0	+0.005	+0.6	+0.022	+2.2 +0.233
	Table 4: Robustness assessment of guided prototypes on CIFAR100 (left) and S2-Agri
	(right). The top line is our chosen hyper-parameter configuration.
				CIFAR100		S2-Agri
				ER	AHC		ER	AHC
	Guided-proto λ = 1, hidden proto,	23.6	1.052		18.9	0.685
	λ = 0.5		-0.2 +0.015		+0.5 +0.019
	λ = 2			+0.3 +0.013		+0.2 +0.010
	λ = 3			+0.1 +0.004		+0.1 +0.010
	leaf proto only	+0.2 +0.015		+0.3 +0.011

For a formal definition of scale-free distortion, see Section 3.2; the distortion is computed with respect to the means of class embeddings for the cross entropy.