Learning Prototype Classifiers for Long-Tailed Recognition

1 Introduction

Imbalanced datasets are prevalent in the natural world due to the fundamental power-law distribution of objects [Van Horn and Perona, 2017]. Past decades have seen a lot of research in class-imbalanced learning [Estabrooks et al., 2004; He and Garcia, 2009], and more recently, due to its farreaching relevance in the era of deep-learning, the problem of long-tailed recognition (LTR) has received significant attention [Cui et al., 2019; Cao et al., 2019; Liu et al., 2019] in the field of computer vision.

A common underlying assumption of recent work in LTR is that softmax classifiers learned from imbalanced training datasets are biased towards head classes. They seek to rectify head class bias in the classifier through dataresampling [Kang et al., 2020], loss reshaping [Ren et al., 2020; Menon et al., 2021; Samuel and Chechik, 2021], ensemble-based models [Xiang et al., 2020; Wang et al., 2020; Zhou et al., 2020], and knowledge transfer [Liu et al., 2019; Liu et al., 2021]. Particularly, it was shown in [Kang et al., 2020] that deep models trained on imbalanced datasets have a high correlation of classifier norm to class size. To achieve similar classifier norms, they freeze the feature extractor and retrain the classifier with balanced class sampling in a second stage. Alternatively, they normalize every classifier by its L2 norm or a power of its norm, leading to balanced classifer norms. More recently, [Alshammari et al., 2022] showed that balanced weights in both the feature extractor and classifier can be achieved by regularizing the model with higher weight decay and/or MaxNorm constraints.

The shortcoming of correlating softmax classifier norm to class size is directly connected to the classification model. We show an illustration in Fig. 1. Consider the problem of learning a classifier fW parameterized by weight matrix W. We assume the feature backbone gθ is fixed and known. The classifier outputs logit scores fW (g(x)) = W T g(x), and the posterior probability p(y|g(x)) ∝ p(y)p(g(x)|y) ∝ (W T g(x))y . Note that softmax classifier has both a magnitude and direction associated to it. In the ideal case, the directions get aligned with the class means µy to encode p(g(x)|y) [Papyan et al., 2020; Thrampoulidis et al., 2022]. But for an imbalanced training dataset, to encode the prior of the label distribution p(y) into classifier weights, the learned classifier norm gets correlated to the class size.

To circumvent this shortcoming of softmax in the longtailed classification setting, it is advantageous to change the classification model from dot-product to distances in the representation space. More specifically, associate a learnable prototype cy to each class y, and let p(y|x) ∝ -d(g(x), cy), where d(·, ·) is a distance metric in the representation space. With a suitable choice of distance metric, such as Euclidean or cosine distances, we obtain a simple and effective prototype classifier which avoids the biased classifier norm problem. While prior work in long-tailed recognition explores the closely related Nearest-Class-Mean classifier [Kang et al., 2020], which is a special case of our model with fixed prototypes, the full potential of prototype based classifiers has not been fully explored. In this work we thoroughly analyze prototype classifiers and show that they offer a promising alternative to softmax in long-tailed recognition.

We theoretically analyze and show that the Euclidean distance based prototype classifier has stable gradient-based optimization properties for learning prototypes. In particular, the L2 norm of the gradient on a prototype cy from a point x is always equal in magnitude to the misclassification probability. Further, the gradient is oriented along the line joining cy to x. This leads to stable gradient updates that aren't affected by outliers that may be far from the prototypes.

We also allow for variable scales along the different dimensions of the feature representations in the prototype distance. This is enabled by learning channel dependent temperature parameters in the prototype distance function. We find that this is beneficial since it's a means of learnable feature scaling and/or selection in the prototype classifier. It also lets the model learn a general Mahalanobis distance metric parameterized by a diagonal matrix.

Overall, here is a summary of our main contributions:

1. We propose a novel learnable prototype classifier for long-tailed recognition to counter the shortcoming of softmax to correlate classifier norm to class size. This offers a promising distance-based alternative to dot-product classifiers that is relatively underexplored in the long-tailed setting.
2. We theoretically analyze the properties of Euclidean distance based prototype classifiers that leads to stable gradient-based optimization which is robust to outliers.
3. We enhance prototype classifiers with channel dependent temperature parameters in the prototype distance function, allowing for learnable feature scaling and/or selection.
4. We evalute our proposed prototype classifier on four benchmark long-tailed datasets, CIFAR10-LT, CIFAR100LT, ImageNet-LT and iNaturalist18. Our results show that the prototype classifier outperforms or is comparable to the recent state-of-the-art methods.

2 RelatedWork

Prototype-based classifiers. Prototype and Nearest-ClassMean classifiers appear prominently in metric learning and few-shot learning. [Mensink et al., 2013] proposed learning a Mahalanobis distance metric on top of fixed representations, which leads to a NCM classifier based on the Euclidean distance in the learned metric space. [Snell et al., 2017] learn deep representations for few shot learning by minimizing the prototype based loss on task-specific epsiodes. [Guerriero et al., 2018] learn deep representations by optimizing the NCM classification objective on the entire training data. [Rebuffi et al., 2017] learn NCM classifiers by maintaining a fixed number of samples to compute prototypes or centroids. In this work, we neither learn a distance metric or finetune representations using the NCM objective; instead our Prototype classifier directly learns the prototypes from pre-trained representations for long-tailed recognition.

Long-tailed recognition. The literature on long-tailed recognition is quite vast. Data resampling or reweighting is the most commonplace strategy against imbalanced datasets. This generally takes three forms: (i) Oversampling minority class samples by adding small perturbations to the data [Chawla et al., 2002; Chawla et al., 2003], (ii) Undersampling majority class samples by throwing away some data [Drummond et al., 2003], and (iii) Uniform or classbalanced sampling based on the number of samples in a class [Sun et al., 2019; Xian et al., 2019]. However, oversampling minority class samples has been shown to lead to overfitting and undersampling majority class samples can cause poor generalization [He and Garcia, 2009]. Recently, [Kang et al., 2020] learn the representations using instance-based sampling and retrain the softmax classifier in a second step using uniform sampling while keeping underlying representations fixed. We also use the two-stage training strategy in our work; however, we avoid learning an additional softmax classifer and instead use Prototype classifiers as it operates in the representation space directly. Another line of prior work focuses on engineering loss functions suited for imbalanced datasets. Focal loss [Lin et al., 2017] reshapes the standard cross-entropy loss to push more weight on misclassified and/or tail class samples. Class-balanced loss [Cui et al., 2019] uses a theoretical estimate of the volume occupied by a class to reweigh the loss function. [Cao et al., 2019] offset the label's logit score with a power of class size to achieve a higher decision boundary margin for tail classes. [Ren et al., 2020] apply the offset to all the logits, and change the class size exponent from 1/4 in prior work to 1 and use a meta-sampler to retrain the classifier. [Menon et al., 2021] apply a label-dependent adjustment to the logit score before softmax which is theoretically consistent. In our work, we build upon the logit adjustment approach and show how it can also be adapted to Prototype classifiers. Many other papers employ a specialized ensemble of experts to reduce tail bias and model variance. [Sharma et al., 2020] train experts on class-balanced subsets of the training data and aggregate them using a joint confidence calibration layer. [Xiang et al., 2020] also train experts on class-balanced subsets and distill them into a unifed student model. [Wang et al., 2020] explicitly enforce diversity in experts and aggregate them using a routing layer. [Zhou et al., 2020] train two experts using regular and reversed sampling together with an adaptive learning strategy. In other works, self-supervised contrastive pretraining is used to improve feature representations for long-tailed recognition [Samuel and Chechik, 2021; Cui et al., 2021]. More recently, [Alshammari et al., 2022] show that quite good performance on long-tailed datasets is possible by simply tuning weight decay properly. Thus, we build our Prototype classifiers on top of the representation learning backbone provided by them. However, the gain of Prototype classifiers over Softmax is invariant to the choice of the backbone, as we show in our experiments.

3 Our Approach

3.1 Prototype Classifier

The Prototype classifier assigns probability scores to classes based on distances to learnable prototypes in representation space. We assume that the representations g(x) are fixed. In other words, the weights θ of the feature extractor gθ are learned in a prior stage and fixed to enable learning of prototype classifiers. The decoupling of representation and classifier learning is commonly used to train softmax classifiers in long-tailed recognition [Kang et al., 2020]; here we adopt the same strategy to learn prototype classifiers.

Let the learnable prototype for class y be denoted by cy. Under the assumption that the class-conditional distribution p(g(x)|y) is a Gaussian with unit variance centered around the prototype cy, we get the following probabilistic model for the class posterior p(y|g(x)):

This leads to the nearest class prototype decision function for classification:y∗ = argmin

Different choices of distance metric lead to different prototype classifiers. While squared Euclidean distance and Euclidean distance lead to equivalent decision boundaries, we find that Euclidean distance is more amenable for learning of the prototypes due to its stable gradient. The Prototype classifier with Euclidean distance metric specifically uses:

The prototypes are learned using the Maximum Likelihood Estimation principle by minimizing the Negative Log Likelihood objective function:

The remainder of this section is organized as follows: in Section 3.2, we show how Euclidean distance leads to stable gradient updates on prototypes, then in Section 3.3 we show how learning prototypes addresses the biased softmax problem, followed by Section 3.4 which details our channel-dependent temperatures to enhance prototype learning, and Section 3.5 which describes logit adjustment for learning prototypes. Our entire pipeline in presented in Algorithm 1.

3.2 Stable Gradient Updates on Prototypes

In Prototype classifier, we use the Euclidean distance in Eq. 2 due to its stable gradient optimization. We now describe the gradient updates on the prototypes.

Theorem 1. Let Lxy denote the NLL loss on a single sample x with label y. Then, the L2 norm of the gradient on prototype cz is given by,

Further, if z = y, then the gradient descent direction lies along g(x) - cz, else it is exactly the opposite direction.

Proof. Let Z(x) = ∑y′ e- 12 d(g(x),c′y ) denote the normalization term over all the classes, and δyz denotes the Kronecker delta. Then, we get a closed form expression for the gradient using repeated application of the chain rule,

From the gradient update, we see that if sample x belongs to class y, then the updated prototype is shifted in the direction (g(x)-cz), weighted by the misclassification probability (1 - p(z|x)), otherwise it's shifted in the opposite direction weighted by the misclassification probability p(z|x).

In both cases, the L2 norm of the gradient is equal to the misclassification probability, leading to stable gradient updates. Importantly, it is invariant to d(g(x), cz), thus both inliers and outliers contribute equally. On the other hand, if we use squared Euclidean distance, it is easy to see that the L2 norm of the gradient is scaled by d(g(x), cz), which is highly sensitive to outliers. We also verify empirically in Section 4.4 that Euclidean distance outperforms squared Euclidean distance for learning prototypes.

3.3 Addressing the Biased Softmax Problem

We show how learning prototypes addresses the biased softmax problem by drawing a connection with the softmax classifier. We consider below a Prototype classifier based on the squared Euclidean distance metric:

Since the term- 1 2 g(x)T g(x) is shared by all classes, it can be ignored. Thus, the Prototype classifier with squared Euclidean distance metric is a softmax classifier with weight cy and bias - 12 cTy cy. Now, we know that softmax can increase or decreases the norm of its weight terms to account for an imbalanced prior label distribution p(y) [Kang et al., 2020]. However, the same is not true for the Prototype classifier, because the bias term negates the gains from increasing or decreasing the norm of the weight term. Due to this coupling of the weight and bias terms, the Prototype classifier is more robust to imbalanced distributions and learns equinorm prototypes. We further show in our experiments in Section 4.5 that the learned prototypes are actually very similar in norm.

3.4 Channel-Dependent Temperatures

While computing distances for prototype classifiers, it is worthwhile to consider that all dimensions in the representation space may not have the same distance scale. Specifically, for a large distance along a dimension with high variance may not mean as much a large distance along a dimension with low variance. Thus, we define the channel-dependent temperature (CDT) prototype distance function using learnable temperatures Ti,

A high value of temperature T implies low sensitivity to distances along that dimension, and a low value implies high sensitivity. Learnable temperatures allow the model to learn feature scaling in the distance function. By letting the temperature approach very high values the model can also filter out potentially harmful features, i.e, feature selection. Finally, the CDT distance can also be interpreted as a Mahalanobis distance √(g(x) - cy)T Σ-1 (g(x) - cy), where Σ is a diagonal matrix with the temperatures on the diagonal.

3.5 Logit Adjustment for Learning Prototypes

Recent work by [Menon et al., 2021] suggests that, for a classifier trained on an imbalanced dataset, it is important to perform an additive adjustment to the logits based on the distribution prior. Motivated by this strategy, we modify the prototype classifier loss function in Eq. 3 as follows:

Algorithm 1: Learning prototype classifier

Require: Pretrained feat reps g(x), class means µy Require: Class-sizes Ny, logit-adj weight τ , lrs α, β Initialize prototypes cy = µy and temperatures Ti = 1; for j ← 0 to num batches do

Sample class-balanced batch (g(xk), yk)batchsize k=1 ; ∀k & ∀y′ compute dCDT (g(xk), cy′ ) using Eq. 4 Compute L = ∑k Lxkyk using Eq. 5; ∀y′ update cy′ ← cy′ - α∇cy′ L; ∀Ti update Ti ← Ti - β∇Ti L;

Here Ny denotes the number of training samples for class y and τ is a hyperparameter. Logit adjustment is only done during training and not during inference. It places a higher penalty on misclassifying tail class samples relative to head classes. Empirical results show that logit adjustment does yield better results for learning prototype classifiers.

4 Experiments

4.1 Datasets

We evaluate our proposed method on the following three benchmark long-tailed datasets: 1. CIFAR100-LT [Cao et al., 2019]: CIFAR100 consists of 60K images from 100 classes. Following prior work, we exponentially decay number of training samples and control the degree of data imbalance with an imbalance factor β. β = Nmax/Nmin, where Nmax and Nmin are the maximum and minimum number of training images per class respectively. Nmax is kept fixed at 500, and we report on three commonly used imbalance ratios β ∈ [100, 50, 10]. The validation set consists of 100 images per class and is also used as the test set. 2. ImageNet-LT [Liu et al., 2019]: This is a long-tailed split of ImageNet. ImageNet-LT has an imbalanced training set with 115,846 images for 1,000 classes from ImageNet-1K [Deng et al., 2009]. The class frequencies follow a natural power-law distribution [Van Horn and Perona, 2017] with a maximum of 1,280 and a minimum of 5 images per class. The validation and testing sets are balanced and contain 20 and 50 images per class respectively. 3. iNaturalist-LT [Van Horn et al., 2018]: This is a species classification dataset that naturally follows a long-tailed distribution. There are 8,142 classes, with a maximum of 118,800 images per class and a minimum of 16. The validation set contains 3 images per class and is also used as the test set.

4.2 Evaluation Protocol

To distinguish the performance of the model on head vs tail classes, we report average top-1 accuracy on balanced test sets across four splits, Many: classes with ≥ 100 samples, Med: classes with 20 ∼ 100 samples, Few: classes < 20 samples, and All classes. Since the test sets are balanced, average accuracy and mean precision are the same.

4.3 Implementation Details

We train prototype classifiers on fixed representations from a prior pre-trained model. Our training pipeline consists of two stages, representation learning followed by prototype learning. To compare fairly with prior work, we use the same backbone architectures: ResNet-32 for CIFAR100, ResNeXt50 for ImageNet-LT and ResNet-50 for iNaturalist18.

Representation learning. We train all models end to end with an auxilliary softmax classifier by minimizing the average cross-entropy classification loss. At the end of training we discard the softmax classifier. We use instancebalanced data sampling [Kang et al., 2020] and regularize model weights using high weight decay [Alshammari et al., 2022], which achieves balanced weights in the feature extractor. We use the SGD optimizer with momentum 0.9, learning rate 0.01 along with cosine learning rate schedule [Loshchilov and Hutter, 2017] decaying to 0 for all models. For CIFAR100-LT and ImageNet-LT we train for 200 epochs with batch size 64 and for iNaturalist18 we train for 200 epochs with batch size 512. The weight decay parameter is found using Bayesian hyperparameter search [Nogueira and others, 2014]. We use random cropping and horizontal flipping for training data augmentation. All our training is done on NVIDIA V100 GPUs.

Prototype learning. We freeze representations and compute empirical centroids to initialize the class prototypes. We minimize the average logit-adjusted cross entropy loss with logit-adjustment weight τ = 1/4. We train for 1 epoch with class-balanced sampling, set prototype learning rate 4, CDT learning rate 0.005 and use the SGD optimizer with momentum 0.9. We also use random cropping, horizontal flipping, Autoaug [Cubuk et al., 2018] and Cutout [DeVries and Taylor, 2017] for data augmentation.

4.4 Ablation Study

Model components. The benefits gained by adding different components to our Prototype classifier (PC) are investigated in an ablation study over CIFAR100-LT with imbalance ratio 100, shown in Table 1. We make several observations: (i) NCM, which is a special case of our model where the empirical centroids are used as class prototypes, i.e cy = 1 Ni g(x), makes considerable gains above softmax, boosting All accuracy from 46.12 to 48.67 and Few accuracy from 11.34 to 14.13. NCM does not suffer from classifier norm correlation to class size like softmax and can do better even without any learning. (ii) Prototype classifier (PC) lifts us above NCM significantly, achieving 4% improvement on All accuracy and 10% improvement on Few accuracy. Thus, learning prototypes gives a far superior nearestprototype model than simply using the class-centroids as done by previous work. (iii) Adding channel dependent temperatures (CDT) to PC further improves the results by 0.5% on All accuracy and 4% on Few accuracy. CDT enhances the model by effecting distinct distance scales for all the features. (iv) Logit adjustment (LA) further improves results for PC. By combining both CDT and LA to PC we're able to gain 1% and 9% improvements over the baseline PC in All and Few accuracies respectively. In the remainder, PC refers to our best model PC + CDT + LA.

Distance metrics. We experiment with different distance metrics for the Prototype classifier, particularly (a) Euclidean distance from Eq. 2, (b) Squared Euclidean distance and (c) Cosine distance: d(g(x), cy) = 1- g(x)T cy ∥g(x)∥∥cy∥ . The results on CIFAR100-LT are depicted in Table 2. We make some important observations: (i) Squared euclidean distance does considerably worse, with All accuracy dropping by more than 30%. This agrees with our theoretical analysis that the Squared euclidean distance is highly sensitive to outliers for learning prototypes. (ii) Cosine distance underperforms Euclidean distance on All and Tail accuracy. This suggests that the geometry of the representation space is closer to Euclidean and not hyperspherical.

Feature backbones. Since Prototype classifier is agnostic to the feature backbone used to generate representations, we experiment with various representation learning and classifier learning schemes from the LTR literature. Particularly, we use CE, DRO-LT [Samuel and Chechik, 2021] and WD [Alshammari et al., 2022] as pre-trained feature backbones. For classifier learning, we use CE, cRT [Kang et al., 2020], WD + MaxNorm [Alshammari et al., 2022] and Prototype classifier (PC). The results on CIFAR100-LT are depicted in Table 3. We observe that Prototype classifier outperforms the competing classifier learning schemes for all the different feature backbones, thus showing that the performance gain is agnostic to the choice of backbone. Our best results are obtained using the WD baseline, which applies strong weight decay for regularizing feature weights.

4.5 Prototype Norms

To understand the advantage of prototype classifier over softmax, we plot the norm of softmax classifier, empirical centroids and learned prototypes In Fig. 2. We recover the correlation of classifier norm to class size for softmax, as shown by prior work. For empirical centroids, it is interesting to see that this correlation does not hold; however the centroid norms are far from balanced. After learning the prototypes, we see that the norms become more balanced, with a slight favor towards the head classes. Since higher norm implies a negative bias in the prototype classifier, this actually favors the tail classes slightly.

4.6 HowDo Prototypes Evolve During Training?

We are interested in the evolution of the class prototypes as training proceeds. Particularly, we seek to know the average separation in terms of Euclidean distance, as well as the average cosine similarity between the class prototypes. In Fig. 3, we plot the average of these values between pairs of All-All classes, Head-Head classes, Head=Tail classes and Tail-Tail classes. The average distance increases monotonically for all the pairs. The separation between Head-Head classes is greater than Tail-Tail classes. Similarly, the average cosine similarity decreases monotonically for all the pairs, therefore the angular separation increases. There is higher angular separation between Head-head classes over Tail-Tail classes. Thus, the prototype classifier learns prototypes that are better separated than the empirical centroids, leading to lower classification error using the nearest-prototype decision function. It also mitigates Minority Collapse, wherein Minority Class means collapse towards the same point [Fang et al., 2021].

5 Comparison to State-of-the-Art

Compared methods. We compare against recently published and relevant methods in the LTR field. We choose representative models from the different solutions spaces(i) data reweighting: Classifier retraining (cRT) [Kang et al., 2020] and DisAlign [Zhang et al., 2021], (ii) loss reshaping: Focal loss [Lin et al., 2017], Label-distribution aware margin (LDAM) loss [Cao et al., 2019] and Logitadjustment loss [Menon et al., 2021], (iii) Ensemble-based models: RIDE [Wang et al., 2020], (iv) Self-supervised contrastive learning: DRO-LT [Samuel and Chechik, 2021] and PaCO [Cui et al., 2021], and (v) Weight Regularization: WD, and WD + WD + Max [Alshammari et al., 2022].

Results. Our results on CIFAR100-LT, ImageNet-LT and iNaturalist18 are reported in Table 4, Table 5 and Table 6 respectively. The numbers of compared methods are taken from their respective papers. Prototype classifier outperforms the prior state-of-the-art methods DRO-LT, DisAlign etc. on all imbalance ratios in CIFAR100. We outperform WD + WD + Max, with whom we share the weight decay tuned baseline WD, on all three benchmark datasets. For ImageNet-LT, Prototype classifier outperforms all prior state-of-the-arts on Tail and All accuracy except models with "bells and whistles," particularly RIDE, which learns and fuses multiple models into an ensemble. A similar conclusion can be derived on iNaturalist18, where our results rival prior state-of-the-arts, except the ensemble model RIDE, and PaCO, which uses self-supervised pre-training and aggressive data augmentation techniques [Cubuk et al., 2020; He et al., 2020]. However, since Prototype classifier is a classifier layer that can be applied to any feature backbone, our method is complimentary to ensembles and self-supervised pre-training. We leave this exploration for future work.

6 Conclusion

In this article, we proposed Prototype classifiers to address the biased softmax softmax problem for long-tailed recognition. Prototype classifiers do not suffer from the biased softmax problem of correlating classifier norm to class size. This is because they rely on distances to learnable prototypes in representation space instead of dot-product with learnable weights, which leads to a coupling of the weight and bias terms. Our theoretical analysis shows that Euclidean distance is stable for gradient-based optimization, and this is confirmed empirically. We further enable independent distance scales in the prototype distance function using channeldependent temperatures. Our results on four benchmark longtailed datasets show that Prototype classifier outperforms or is comparable to the prior state-of-the-art. Moreover, experiments reveal that the learned prototypes are equinorm and are much better separated in representation space than centroids.

Acknowledgements

Research was partially sponsored by the NSF under award #2229876.