Hierarchical Class-Based Curriculum Loss

1 Introduction

Machine learning (ML) models are trained on class labels that often have an underlying taxonomy or hierarchy defined over the label space. However, general ML models do not utilize the taxonomy relations between the labels and can thus make more egregious errors. For example, if an image contains "bulldog", the model would penalize a prediction of "dog" and "building" equally unlike a human evaluator who would consider "dog" to be a more accurate prediction. Although such nuances are not captured by the standard evaluation metrics, they are crucial for ensuring quality in real deployments of ML models.

Hierarchical multi-label classification (HMC) methods, which utilize the hierarchy of class labels, aim to tackle the above issue. Traditional methods in this domain broadly use one of three approaches: (i) architectural modifications to the original model to learn either levels or individual classes separately, (ii) converting the discrete label space to a continuous one and embedding the labels using relations between them, and (iii) modifying the loss function by adding more weights to specific classes in the hierarchy. However, the methods in this domain are mostly empirical and the choice of modifications is often experimental. To overcome this issue, we aim to incorporate the class dependencies in the loss function in a systematic fashion. To this end, we propose a formulation to incorporate hierarchical constraints in a base loss function and show that our proposed loss is a tight bound to the base loss.

∗The author only contributed to part of this work while working at Samsung Research America.

Further, we note that typically humans do not learn all the categories of objects at the same time, but rather learn them gradually starting with simple high-level categories. A similar setting was explored by Bengio et al. [Bengio et al., 2009], introducing the concept of curriculum learning feeding the model easier examples to mimic the way of human learning. They show that learning simple examples first makes the model learn a smoother function. Lyu et al. [Lyu and Tsang, 2019] extended this to define an example-based curriculum loss with theoretical bounds to 0-1 loss. We extend our hierarchically constrained loss function to incorporate a class-based curriculum learning paradigm, implicitly providing higher weights to simpler classes. With the hierarchical constraints, the model ensures that the classes higher in the hierarchy are selected to provide training examples until the model learns to identify them correctly, before moving on to classes deeper in the hierarchy (making the learning problem more difficult).

We theoretically show that our proposed loss function, hierarchical class-based curriculum loss, is a tight bound on 0-1 loss -we show that any other loss function that satisfies hierarchical constraints on a given base loss gives a higher loss compared to our loss. We evaluate this result empirically on four image data sets, showing that our loss function provides a significant improvement on the hierarchical distance metric compared to the baselines. We also show that, unlike many other hierarchical multi-label classification methods, our method does not have a degraded performance on non-hierarchical metrics and in most cases has a significant improvement over the baselines.

2 RelatedWork

Research in hierarchical classification falls into three categories: (i) embedding label relations in continuous space, (ii) structural modifications of base architecture, and (iii) adding hierarchical regularizers and loss function modifications.

Label-embedding methods [Kumar et al., 2018; Frome et al., 2013; Chen et al., 2019; He and Chua, 2017; Huang and Lin, 2017; Bertinetto et al., 2019] map class labels to continuous vectors capable of reconstructing the relation between labels. They then learn a model to predict the embedding instead of original labels. The disadvantage of these methods is typically the difficulty of mapping back the prediction to the discrete space and the noise introduced in this conversion.

Models that perform structural modifications use earlier layers in the network to predict higher level categories and later layers to predict lower level categories [Wehrmann et al., 2018; Masera and Blanzieri, 2018; Cerri et al., 2014; Bilal et al., 2017]. Structural methods are often domain-dependent, needing time and effort to analyze the data and come up with specific modifications. In comparison, our loss based HCL method is easier to implement and domain-agnostic.

Finally, models that modify the loss function to incorporate hierarchy assign a higher penalty to the prediction of labels which are more distant from the ground truth. AGGKNNL and ADDKNN-L-CSL [Verma et al., 2012] use a lowest common ancestor (LCA) based penalty between the classes. Similarly, Deng et. al. [Deng et al., 2010] introduce hierarchical cost giving penalty based on the height of LCA. CNNHL-LI [Wu et al., 2016] use a weighting parameter to control the contribution of fine-grained classes which is empirically learned. HXE [Bertinetto et al., 2019] use a probabilistic approach to assign penalties for a given class given the parent class and provide an information theoretic interpretation for it, while Papai et al. [Papai et al., 2012] use an approach where a subjective feedback provided by a user is translated to probabilistic constraints.

The domain of curriculum learning was introduced by Bengio et. al. [Bengio et al., 2009] based on the observation that humans learn much faster when presented information in a meaningful order as opposed to random, which is typically used for training machine learning models. Several follow up works have shown this type of learning to be successful [Smith, 2017; Matiisen et al., 2019; Lyu and Tsang, 2019]. Our approach builds on this line of work to develop a curriculum learning-based loss.

3 Preliminaries

We first define some notations for the rest of the paper. Let T = (xi, yi)i=1,...,N denote the training set with N examples where xi ∈ RD is the input feature vector and yi ∈ {0, 1}C is the ground truth assignment of the input to a category space. Here, C and D are the number of categories and dimensionality of input feature vector respectively. Note that we consider the problem of multi-label classification where an input can belong to multiple classes simultaneously. We denote the loss function as l : RN × RC → R where l(yi, ˆyi) denotes the loss when the prediction is ˆyi. For ease of notation, we will refer to it as l(ˆyi). In our problem, we assume that the set of categories C can be arranged in a hierarchy H = (C, P) where P is the set of directed parent-child relations between the categories, P(c) = p means parent of class c is p.

4 Hierarchical Class-Based CurriculumLoss

For the task of multi-class classification, given a multi-class loss function, our goal is to incorporate the hierarchical constraints present in the label space into the given loss function. In this section, we first define a hierarchical constraint which we require to be satisfied for a hierarchical label space. We then introduce our formulation of a hierarchically constrained loss and show that the proposed loss function indeed satisfies the constraint. We prove a bound on the proposed loss, extend the loss function using a curriculum learning paradigm to get a tight bound to the 0-1 loss using this, and present an algorithm to train the model using the proposed loss function. Note that the proposed loss function HCL corresponds to lhc. HCL-Hier (lh) is any generic loss that satisfies our proposed hierarchical constraint, the first component of HCL. HCL-CL (lhc without lh) is any generic loss that just uses class-based curriculum learning, the second component of HCL.

4.1 Incorporating Hierarchical Constraints

Consider the learning framework with training set T = (xi, yi)i=1,...,N . A general multi-class multi-label loss lower bounded by 0-1 loss can be defined as follows:

Note that this loss function does not impose any hierarchical constraints between the categories. Consider two categories in the category set C: Animal and Dog. Without constraints, a model trained using the above loss can have lAnimal > lDog. This implies that the model is more accurate in its prediction of Dog compared to Animal. However, this is counter-intuitive as Dog is an Animal and its confidence should not be greater than Animal's. To tackle this, we define the following hierarchical constraint Λ on a generic loss function l:

The constraint implies that the loss of a child node in the hierarchy is constrained to be more than the loss of the corresponding parent node. Satisfaction of this constraint encodes that the model suffers a lower loss when it predicts a finer category with less accuracy than its parent, which is intuitive. Note that this constraint can be modified to constrain levelwise relations instead of parent-child relations. The theorems in this paper can be proven for level-wise relations as well.

We now propose the loss function lh and show that it satisfies the hierarchical constraint Λ by definition:

We now show the following result for lh.

Theorem1. (Hierarchically Constrained Loss) Given a loss function l, the loss function lh defined in Equation 3 satisfies the hierarchical constraint Λ defined in Equation 2.

Proof. Let us assume that lh doesn't follow hierarchical constraint Λ i.e. ∃(xi, yi) ∈ T, ∃c1, c2 ∈ C s.t.

However, we have

yi,c2 )

which contradicts our assumption. This implies that lh has to follow the hierarchical constraint Λ.

Now, we show that the hierarchically constrained loss function is tightly bounded to the base function.

Theorem 2. (Bound on Constrained Loss) For a loss function l(ˆ y) lower-bounded by 0-1 loss, the loss function lh defined in Equation 3 is an element-wise tight bound on l(ˆ y) with constraint Λ. Let ⪯ denote elementwise inequality i.e. f ⪯ q means ∀x ∈ domain(f), f(x) ≤ q(x). We then have:

Using the definition of lh from Eq. 3, we have:

This leads to two cases:

Case 1. If l(ˆ yi,c1 ) > l(ˆ yi,P(c1)), then we get g(ˆ yi,c1 ) < l(ˆ yi,c1 ). This contradicts the assumption that g is lowerbounded by l i.e. l ⪯ g.

Case 2. If l(ˆ yi,P(c1)) > l(ˆ yi,c1 ), then we get g(ˆ yi,c1 ) < l(ˆ yi,P(c1)). As l ⪯ g, we have g(ˆ yi,P(c1)) >= l(ˆ yi,P(c1)). Combined, we get g(ˆ yi,P(c1)) > g(ˆ yi,c1 ). However, this violates the Λ constraint.

The above result is for a generic loss - it can be used to get the following property for 0-1 loss.

Corollary 1. (Bound on Constrained 0-1 Loss) For a 0-1 loss function e(ˆ y), the loss function eh is defined as

is an element-wise tight bound on e(ˆ y) with constraint Λ, i.e., the following relation holds:

We have shown above that the hierarchy constrained loss function lh provides an element-wise tight bound on the base loss l. We now extend this loss function to use a curriculum learning paradigm and show that the loss is a tighter bound to 0-1 loss compared to any other hierarchy preserving loss.

4.2 Hierarchical CurriculumLoss

As shown by Hu et al. [Hu et al., 2016], 0-1 loss ensures that the empirical risk has a monotonic relation with adversarial empirical risk. However, it is non-differentiable and difficult to optimize. Following the groundwork by Lyu et al. [Lyu and Tsang, 2019] who propose example based curriculum loss, we present a class-based curriculum loss for any given hierarchically constrained loss function l and a class selection parameter s in the following theorem. The theorem also proves that the function defined is tighter bound to 0-1 loss compared to any loss function which satisfies the hierarchical constraint and is lower bounded by l. Note that a general loss function l is element-wise lower bounded by 0-1 loss e, i.e., e ⪯ l.

Theorem 3. (Hierarchical Class-Based Curriculum Loss) For a general hierarchy constrained loss function lh(ˆ y), we define the loss function lhc(ˆ y) as follows:

Then, e(ˆ y) ≤ lhc(ˆ y) ≤ g(ˆ y) ∀g ∈ L satisfying hierarchical constraint Λ, s.t. l ⪯ g i.e. the following holds

Proof. Consider lhc(ˆ y) which is

For the lower bound we have,

This gives e(ˆ y) ≤ lhc(ˆ y) ≤ g(ˆ y). Subtracting e(ˆ y) from both sides, we get the theorem.

Note that s governs classes to be selected for training, i.e., s(i) = 1 implies that class i is selected by the loss function. This is primarily used to select easy classes first followed by harder classes. Intuitively, the max in the loss function sub-selects classes based on their loss values.

4.3 Algorithm

In the above theorem, we prove that the proposed hierarchical class-based curriculum loss provides a tighter bound to 0-1 loss compared to the hierarchically constrained loss function. Given the above, we now need to find the optimal class selection parameters si for each class. We show that Algorithm 1 provides the optimal selection parameters.

Theorem 4. (Class Selection) Given a base loss function l, a hierarchically constrained loss function lh, a solution s for Equation 9 is provided by Algorithm 1.

The proof for above is provided in the Appendix. The algorithm first creates a hierarchically constrained loss function lh given the loss function l. It then sorts the loss values of classes in increasing order of magnitude. Finally, it selects the first K classes from this list such that the cumulative sum is greater than thresh + 1 - K, where thresh is an hyper-parameter. The first K - 1 classes go in the selection pool.

Note that the time complexity of our approach is O(NClog(C)) and that of a typical base loss is O(NC). The additional log(C) is computationally inexpensive as class sizes are typically very small.

Algorithm 1: Class Selection for Hierarchical ClassBased Curriculum Learning. Number of samples N, Number of classes C, Base Loss l, Threshold threshdetermines the selection of classes to contribute to the loss function in an iteration

Function selectClasses (l, thresh) for j = 1 . . . C do lh(ˆ y.,j ) ← 0; for i = 1 . . . N do lh(ˆ yi,j ) ← max(l(ˆ yi,j), l(ˆ yi,P(j))); lh(ˆ y.,j) += lh(ˆ yi,j ); Sort class indices in non-decreasing order of lh; Get minimum K s.t. ∑Kc=1 lh(ˆ y.,c) > thresh + 1 - K; for i = 1 . . . C do if i <K then si ← 1; elsesi ← 0; return s

5 Experiments

In this section, we present experiments to showcase the performance of hierarchical class-based loss. We show the results on four data sets with the state-of-the-art hierarchical loss functions. Further, we perform statistical tests to show the significance of our results. We also perform an ablation study on each of the component of hierarchical class-based curriculum loss, including the hierarchically constrained loss(HCL-Hier) and class-based curriculum loss(HCL-CL), and show how they interplay to provide the proposed final loss function(HCL). We performed our experiments on 2 Nvidia GeForce RTX 2080 Ti with 12 GB memory with 3.30 GHz CPU clock speed.

5.1 Experimental Setup

We evaluate our loss function on four real world image data sets - (i) IMCLEF [Dimitrovski et al., 2011], (ii) Wipo [Rousu et al., 2006], (iii) Reuters [Lewis et al., 2004], and (iv) iNaturalist [Van Horn et al., 2018]. A summary of these datasets is provided in Tables 1 & 2.

Experimental Details. For evaluation on datasets with preextracted features, we use a multi-layer perceptron with the extracted features as input and the categories as output. We select the hyperparameters of the neural network using evaluation on a validation set with binary cross entropy loss. Based on this, we get a structure with 800 hidden neurons and a dropout of 0.25. Note that we fix this network for all the baseline loss functions and our loss function to ensure fair comparison of results. For evaluation on iNaturalist, we used a ResNet-18 architecture (pre-trained on ImageNet). We use Adam optimizer and a learning rate of 10-5 .

Baselines. We compare the hierarchical class-based curriculum loss with the following state-of-the-art losses - (i) binary cross entropy loss [Goodfellow et al., 2016], (ii) focal loss [Lin et al., 2018] and (iii) hierarchical cross entropy loss [Bertinetto et al., 2019]. Further, we also compare it with a label-embedding approach called SoftLabels [Bertinetto et al., 2019], which modifies the ground truth labels in accordance with the hierarchy. For all the baselines, we use the range of hyperparameters used in their respective works.

5.2 Metrics

We use the following metrics to evaluate each of the losses for the classification task - (i) Hit@1, (ii) MRR (Mean Reciprocal Rank) [Radev et al., 2002], (iii) HierDist [Deng et al., 2010], (iv) HierCons. The first two metrics capture the accuracy of ranking of the model predictions while the other two metrics capture preservation of hierarchical information. Hierarchy capturing methods often show lower performance compared to non-hierarchical methods on first two metric as the losses get more constrained. However, these hierarchical methods often show improvements on a metric which captures how close to the ground truth class the prediction is in the given hierarchy.

HierDist captures this and is defined as the minimum height of the lowest common ancestor (LCA) between the ground truth labels and the top prediction from the model. Mathematically, for a data point (xi, yi) ∈ T , it is defined as

where H denotes the hierarchy of the labels. The minimum height of LCA is taken as 0 for a correct prediction. As pointed out by Deng [Deng et al., 2010], the metric is effectively on a log scale. It is measured by the height in the hierarchy of the lowest common ancestor, and moving up a level can be more than double the number of descendants depending on the fan out of the parent class (often greater than 3-4). We show that our loss function is superior to the baseline losses for this metric. In addition, our model's performance also doesn't deteriorate on non-hierarchical metrics.

We further propose another metric Hierarchical Consistency (HierCons) to measure the consistency of predictions w.r.t. the hierarchy. We define a pair of predictions to be consistent if they satisfy constraint Λ (Eq. 2). HierCons@k considers the top k predictions and takes the ratio of total consistent pairs and maximum possible pairs which is kC2.

5.3 Overall Results

We now compare our proposed loss (HCL) with the state-ofthe-art loss functions capturing hierarchy as well as a label embedding method (SoftLabels). From Table 1 & 2, we observe that our loss significantly outperforms the base loss functions. Consistent with earlier results [Bertinetto et al., 2019], we see that previously proposed hierarchically constrained loss functions especially SoftLabels & HXE improve on hierarchical metrics but the performance deteriorates for non-hierarchical metrics. On the other hand, HCL is able to get significant boost in Hit@1, MRR and HierDist while also improving or maintaining similar HierCons@3 as compared to all state-of-the-art loss functions including the base cross-entropy loss. HierCons@3 is also a dataset dependent metric, iNaturalist data sets have higher inherent consistency than say IMCLEF. We observe that overall Hier-CE is the best performing baseline but our model outperforms it on every metric except HierCons@3 on Wipo. Label embedding of SoftLabels(SL) facilitate parent classes to contribute to loss of all children classes in the hierarchy, thus inherently preserving hierarchical consistency. HCL significantly outperforms SL in all metric except HierCons@3 with slight trade-off on MRR in IMCLEF. Note that HCL is also computationally efficient and takes the least time compared to the best performing hierarchical baselines (e.g. HXE). We ranked performance of HCL loss as compared to other state-of-the-art losses on all 4 metric across datasets. As per Table 3, HCL has the best rank in terms of improvement across metrics, slightly above 1 is contributed by slightly lesser improvement in MRR with sizeable gains in other metrics. We present statistical tests on this table in the next section.

5.4 Detailed Analysis

We perform an ablation study on each component of the proposed loss and show their interplay. We then show statistical analyses to further evaluate the performance of the final loss, HCL. Finally, we show how the hyperparameter of HCL was selected and its effect on performance.

Ablation Studies

We show the effects of the hierarchical constraints and the curriculum loss using cross entropy loss as the base function in Table 4. We show results on test set of IMCELF.

We observe that the hierarchically constrained cross entropy loss, HCL-Hier, improves on the hierarchical metrics and non-hierarchical metrics. This shows that adding the hierarchical constraint doesn't deteriorate typical metrics all the while making the predictions more consistent with the label space hierarchy as well as making predictions closer to the ground truth label in the hierarchical space. We believe that the improvement in non-hierarchical metrics may be attributed to the modified ranking due to hierarchical constraint making the top predictions more likely.

Looking into class-based curriculum loss individually, we observe that as suggested by theory, carefully selecting the classes based on their loss (giving more weight to simpler classes at higher hierarchy levels) improves the hierarchical evaluation metric, making the predictions more relevant.

Overall, combining the two aspects yields our proposed loss HCL which shows the best performance. We see that for all the metrics, HCL gives significant gains both with respect to baseline loss and individual components. This follows theory in which we have shown that combining class-based curriculum loss with hierarchical constraints gives a tighter bound to 0-1 loss with respect to the hierarchically constrained loss. Further, as this loss explicitly ensures that loss of a higher level node is lower than the a lower level, and implicitly gives more weight to higher level node as they are selected more, the combined effect makes it more consistent to the hierarchy. This can be particularly seen from the fact that each individual component gave good improvements for the hierarchical metric but the combined loss gave much more significant gain. HCL loss finds the best trade-off between maintaining hierarchical metrics HierDist & HierCons while significantly improving non-hierarchical metrics Hit@1 & MRR. It is able to improve Hit@1, MRR and even HierDist much significantly with much lower deviation in Hit@1 metric compared to base cross-entropy loss when both hierarchical constraints and curriculum loss are applied together.

Quantitative Analysis

We perform statistical tests to understand the significance of our results. Based on Tables 1 & 2, the methods are ranked (summarized in Table 3). We evaluate our method using Friedman test and Bonferroni-Dunn's test.

Based on Friedman test, we get a χ2 value of 12.1 and 12.93 for Hit@1 and HierDist respectively (with p-values 0.017 and 0.011 respectively). Thus, the results of various approaches vary widely with a confidence value of 95% enabling us to use difference statistics to compare the approaches.

We use Bonferroni-Dunn's test to identify the difference between the methods. The critical difference (CDα) is given by the formula qα√ g(g+1) 6N , where qα is the critical value, g is the number of methods and N is the number of samples (i.e. data sets in our case). For α = 0.15, we have qα of 2.4324 which leads to CDα of 2.2205. The comparison of methods with HCL is provided in Figure 1. We conclude that with 85% confidence, HCL outperforms all baselines on Hit@1 metric and all methods except Focal Loss on HierDist metric.

Hyperparameter Variation

As mentioned in Algorithm 1, HCL uses a threshold which determines the selection of classes to contribute to the loss function at a particular iteration. We select the appropriate value of the threshold based on the percentage of classes selected with the random initialization of the model (i.e. using the 0th iteration loss values). We analyze the impact of varying the percentage of class-selection by HCL on its performance. From Figure 2 we observe that, both significant metrics, HierDist and Hit@1 change significantly in their performance based on the percentage of classes selected and hence threshold used for class-selection. HierDist is at its best of 0.258 and Hit@1 at its best of 91.24 at 40% class-selection of the total 47 classes in IMCLEF. We also note that the drop in the performance with less than optimal or more than the required class-selection percentage is smooth and in accordance with the learning-method of HCL loss as explained in section 4.2.

6 Conclusion

In this paper, we propose a hierarchical class-based curriculum loss for multi-label classification with theoretical analysis and provable bounds, making it general and dataset-agnostic. We propose a class-based curriculum loss to enhance the performance of the hierarchically constrained loss, and show significant empirical gains on multiple data sets. We observed that our models improve on both hierarchical and non-hierarchical metrics, making it widely applicable. We further perform statistical tests to illustrate the significance of results.

In the future, we would like to relax the hierarchical constraints and develop a loss for a general graph-based relation structure between the labels. Further, we would like to test the model on other real world data sets that contain relation between labels. Finally, we would also like to test the model performance when we introduce noise into the hierarchical labels of the class taxonomy.