Year: 2020

Abstract:
Few-Shot Learning (FSL) is a challenging task of recognizing novel classes from scarce labeled samples. Many existing researches focus on learning good representations that generalize well to new categories. However, given low-data regime, the restricting factors of performance on novel classes has not been well studied. In this paper, our objective is to understand the cause of error in few-shot classification, as well as exploring the upper limit of error rate. We first introduce and derive a theoretical upper bound of error rate which is constrained to 1) linear separability in the learned embedding space and 2) discrepancy of task-specific and task-independent classifier. Quantitative experiment is conducted and results show that the error in FSL is dominantly caused by classifier discrepancy. We further propose a simple method to confirm our theoretical analysis and observation. The method adds a constraint to reduce classifier discrepancy so as to lower the upper bound of error rate. Experiments on three benchmarks with different base learners verify the effectiveness of our method. It shows that decreasing classifier discrepancy can consistently achieve improvements in most cases.

heading: 1 INTRODUCTION
text: Learning novel concepts from few samples is one of the most important ability in human cognition system (Chen et al. (2018); Dhillon et al. (2019); Wang et al. (2020)). By contrast, massive achievements of modern artificial intelligent systems are dependent upon lots of data and annotation which are hard to acquire in many scenarios. Blocked by the difficulty in obtaining large labeled datasets, community shows more interests in developing algorithms with high data-efficiency. It is so-called few-shot learning that learns to generalize well to new categories with scarce labeled samples (Sung et al. (2018); Vinyals et al. (2016)). Existing methods deal with few-shot learning in the general framework of meta-learning where a base learner is developed and optimized across different episodes (or tasks). Episodes are formed in a N-way K-shot fashion where K support samples per class are available for training. The overall objective is enabling the base learner to exploit on base classes and to transfer learnt knowledge to recognize novel classes with few support data. Since training and evaluation are performed on different tasks, the base learner holds different task-specific classifiers that depend on data sampling.
In general, classification model has two components: feature extractor and classifier (Simonyan & Zisserman (2015); He et al. (2016); Zagoruyko & Komodakis (2016)). Most approaches of few-shot learning exploit from according perspectives: learning a good embedding and finding a right base learner. Rethinking-FSC (Tian et al. (2020)) demonstrates that a good learned embedding space can be more effective than many sophisticated meta-learning algorithms. It argues for the performance on meta set where embeddings are learnt in supervised or self-supervised way. Goldblum et al. (2020) reveal the importance of feature clustering in few-shot learning. Since classifier performance is sample-dependent especially in one-shot scenario, variance of feature is expected to be small so as to retain good performance. It shows that classifier performance is not stable across different tasks. MetaOptNet (Lee et al. (2019)) and R2-D2 (Bertinetto et al. (2018)) explore training and optimization routines for linear classifier, enabling good few-shot performance through simple base learner. These literatures develop specific algorithms from the aspects of learning good representation or optimizing base learner. Most recent methods use linear classifier as base learner, so we also consider linear model in this paper. To our best knowledge, there has been little research focusing on how the
two components (aka feature representation and classifier) respectively influence the performance on novel classes in FSL.
In this paper, we introduce an upper bound of error rate in few-shot learning, indicating that the error comes from two aspects: 1) linear separability in the embedding space and 2) classifier discrepancy between task-specific and task-independent classifiers. The ideal classifier is viewed to be task-independent since its performance is not sample-dependent (Goldblum et al. (2020)). To quantitively estimate each term, an experiment is performed where we use error rate of supervised classification tasks on novel classes to measure feature separability, and use disagreement of results obtained from different classifiers to measure discrepancy. It comes to an interesting observation that features learned through simple methods are sufficiently discriminative and the error mainly comes from classifier discrepancy. Based on our observation and theoretical analysis, we propose a simple method of reducing classifier discrepancy so as to boost few-shot performance. Experiments on three benchmarks are conducted to empirically verify our theory. Results on different datasets with various base learners show consistent improvements, supporting our finding and theory in few-shot learning.
The main contributions of this paper are:
1. The upper bound of error rate on novel classes is theoretically analyzed. From derived equations we figure out that the error in FSL is caused by linear separability in the feature space and discrepancy between task-specific and task-independent classifiers.
2. Quantitative experiments are conducted to verify the theoretical analysis. Results show that the error is dominantly caused by classifier discrepancy.
3. Based on the theoretical analysis and the experiment results, a constraint is proposed to reduce classifier discrepancy so as to decrease the upper bound of error rate in FSL.
4. Further experiments on mini-ImageNet, tiered-ImageNet and CIFAR-FS confirm the effectiveness of the proposed method. It shows that decreasing classifier discrepancy can consistently achieve improvements in most cases.

heading: 2 RELATED WORK
text: Algorithms of Few-Shot Learning Prototypical Network (Snell et al. (2017)) is a classical algorithm for its simplicity and effectiveness, which performs few-shot classification by nearestprototype matching. Since class prototype is the mean of features, the linear separability in feature space has direct impact on classification results. Performance of following series of prototype based methods (Allen et al. (2019); Liu et al. (2020)) is also limited by feature separability. Different with these methods using nearest-neighbor classifier, Bertinetto et al. (2018) adopt ridge regression and logistic regression as base learner. Similarly, Lee et al. (2019) use classical linear classifier SVM in few-shot learning to learn representations. Simple linear classifier shows competitive performance and in this paper, we use linear classifier in measuring linear separability and classifier discrepancy.
Theoretical Analysis of Few-Shot Learning Cao et al. (2019) introduce a bound for accuracy of Prototypical Network (Snell et al. (2017)), demonstrating that the intrinsic dimension of the embedding function’s output space varies with the number of shots. They further propose a method to overcome the negative impact of mismatched shots in meta-train and meta-test stages. As in (Liu et al. (2020)), they give a lower bound for accuracy cosine similarity based prototypical network. Two key factors: intra-class bias and cross-class bias are theoretically formulated. We also analyze theoretical bounds in few-shot learning. Theory in this paper does not focus on specific algorithm like Prototypical Network but on general scenarios, from the perspective of feature separability and classifier discrepancy.
Theoretical Analysis of Domain Adaptation: Methods of domain adaptation (Ben-David et al. (2007; 2010); Ganin & Lempitsky (2015)) solve the problem of how to train a classifier on source domain and guarantee the classifier performs well on target domain. A classifier’s target error is bound by its source error and the divergence between the two domains in (Ben-David et al. (2010)). They utilize H-divergence and H∆H-divergence to measure discrepancy between two domains. H∆H-divergence can be computed from finite unlabeled data, allowing us to directly estimate the
error of a source-trained classifier on the target domain. Inspired by their work, we also use H∆Hdivergence to measure discrepancy between sets on novel classes and base classes.

heading: 3 BACKGROUND

heading: 3.1 PROBLEM SETUP
text: The common setup of few-shot learning used in this paper is described below. A space of class is divided into two parts: base classes Cbase and novel classes Cnovel where Cbase ∩ Cnovel = ∅. Dataset Dbase of base classes is used for model training and the model is evaluated on dataset Dnovel whose samples belong to unseen classes during training. The model is composed of a feature extractor F and a classifier h. In few-shot learning, we usually consider N -way K-shot Q-query tasks T . In task τi = (Dsi , D q i , h), the support set D s i includes K data x ∈ Rd per class and its true label y ∈ {c1, ..., cN}. The goal is to predict labels for query data in Dqi given Dsi . In this paper, we use error rate on novel classes to evaluate the few-shot performance of a trained model. The error rate is formulated as:
novel = E[ τ ] = 1
M ×Q M∑ i Q∑ j 1(h(F (xi,j))! = yi,j) (1)
where M is the number of sampled tasks τi ∼ Tnovel. 1(·) is indicator function.

heading: 3.2 DISTRIBUTION DIVERGENCE
text: We adopt following concepts to explore the cause of error in few-shot scenarios.
Definition 1 Given a set D = {(x1, y1), ..., (xm, ym)} where xi ∈ X and yi ∈ Y , for any mappings h1, h2 ∈ X , disagreement is defined in Eqn. 2 to measure the difference of these two mappings.
dis(h1, h2) = Px∼DX (h1(x) 6= h2(x)) (2)
Definition 2 Given a domain X withD1 andD2 probability distributions over X , letH be a hypothesis class on X and denote by I(h) the set for which h ∈ H is the characteristic function; that is, x ∈ I(h)⇔ h(x) = 1. H divergence between D1 and D2 is
dH(D1,D2) = 2suph∈H|PrD1 [I(h)]− PrD2 [I(h)]| (3)
Definition 3 For hypotheses h, h′ ∈ H, the symmetric difference hypothesis space H∆H is the set of hypotheses g ∈ H∆H ⇔ g(x) = h(x)⊕h′(x) where ⊕ is the XOR function. H∆H divergence over distributions is defined as following:
dH∆H(D1,D2) = 2suph∈H|Prx∼D1 [h(x) 6= h′(x)]− Prx∼D2 [h(x) 6= h′(x)]| (4)

heading: 4 PROPOSED METHOD

heading: 4.1 MEASURING CLASSIFICATION PERFORMANCE ON NOVEL CLASSES
text: A classification model generally consists of two parts: feature extractor and classifier. Hence, the model holds two expectations: 1) Extracted features are expected to be discriminative for classification (Snell et al. (2017); Lee et al. (2019)). 2) Classifier is supposed to be stable concerning different tasks (Cao et al. (2019); Liu et al. (2020)). Consider linear classifier in this paper, we investigate from linear separability and classifier stability to measure classification performance on novel classes. To quantitively estimate these two terms, we design experiments using a base model with ResNet-12 backbone and FC (fully-connected) layer classifier. The base model is first trained on base classes in supervised way. When testing on novel classes, we replace FC layer classifier with ProtoNet (Snell et al. (2017)) and ridge regression (RR) as in paper Ye et al. (2020). The novel(h
∗)(i.e. error rate on Cnovel with classifier h∗), is used to approximate and quantify feature separability on novel classes (Eqn. 5).
novel(h ∗) =
1 N ×Q∗ N×Q∗∑ i 1(ŷi 6= yi) (5)
In Eqn. 5, Q∗ is the number of all samples of each class c ∈ {c1, ..., cN}. ŷi is predicted label and yi is true label. h∗ is trained under supervised way from large set of samples and is used to approximate the expected ideal N -way classifier. On the other hand, we use disagreement defined in Eqn. 6 to measure classifier discrepancy.
dis(h, h∗) = 1
N ×Q N×Q∑ i 1(ŷi 6= ŷ∗i ) (6)
where Q is the number of query samples. h is task-specific classifier that differentiates among tasks, decided by sampled support data. h∗ is task-independent concerning these N classes. Thus, dis(h, h∗) indicates the discrepancy between the task-specific classifiers and the ideal classifier.
Table 1 shows results on two benchmarks: mini-ImageNet and tiered-ImageNet. From Table 1, we can see that novel(h∗) is generally lower than dis(h, h∗) in a large margin. For example, 1-shot dis(h, h∗) on mini-ImageNet with RR is up to 38.34% while novel(h∗) is 6.72%, which is five times lower. Furthermore,the obvious drop of dis(h, h∗) from 1-shot to 5-shot indicates obvious raising of classifier discrepancy. An interesting conclusion can be drawn from this experiment that the error on novel classes is dominantly caused by classifier discrepancy in low-data regimes rather than linear separability. More details about this experiment are presented in the appendix.

heading: 4.2 UPPER BOUND OF ERROR RATE
text: In this section, we introduce an upper bound of error rate on novel classes in few-shot learning.
Proposition 1 Consider a feature extractor F and a hypothesis space H. Based on triangular inequality, for h, h∗ ∈ H, it follows that:
(h;F ) ≤ (h∗;F ) + dis(h, h∗;F ) (7)
h∗ is the ideal hypothesis in H, holding that h∗ = arg minh∈HE[ τ (h;F )]. Proof is in the appendix.
In few-shot learning, error rate on novel classes is usually denoted by novel = E[ τ (h;F )]. Hence, the upper bound is: novel ≤ E[ τ (h∗;F )] + E[disτ (h, h∗;F )] (8) where τ ∼ Tnovel. From Eqn. 8, boosting few-shot performance can be achieved by minimizing the two terms in right side of above inequality. However, h∗ is unavailable when testing on novel classes. In order to connect the performance on novel set and it on base set we consifer following setting.
Consider N -way K-shot tasks where N is assumed to be same in meta-train and meta-test stages. h, h′ are linear classifiers of novel classes and base classes respectively. For classification weights Wb,Wn ∈ RN×d of base and novel classes, there exists a linear transformation matrix W̃ ∈ Rd×d that hasWb = WnW̃ . We define the linear transformation between the ideal hypothesis on the novel set and that on the base set as Λ, h′∗ = Λ(h∗), h∗ = Λ−1(h′∗). For query samples X = {xi ∈ Rd}, predicted results are:
h(X;Wn) = XW T n = X(WbW̃
−1) T (9)
According to the above analysis we know that performing a transformation on the classifier is equivalent to perform the transformation on the data, Λ(h)(X) = h(Λ(X)).
Lemma 1 LetH be a hypothesis space of VC dimension d. h∗, h′∗ are ideal hypotheses on Dnovel and Dbase. There is an ideal hypothesis ĥ = arg minh∈H novel(h) + base(Λ
−1(h)). Then for h∗ and h′∗:
novel(h ∗) ≤ base(h′∗) +
1 2 dH∆H(D novel, Dbase) + λ (10)
where λ = novel(ĥ) + base(Λ−1(ĥ)) is the combined error of the ideal hypothesis ĥ.
Lemma 2 For linear hypotheses h, h′ ∈ H and ideal hypotheses h∗ on Dnovel, h′∗ on Dbase, there exists:
dis(h, h∗;Dnovel)
≤ dis(h,Λ(h′∗);Dbase) + 1 2 dH∆H(D novel, Λ(Dbase)) ≤ dis(h′, h′∗;Dbase) + dis(h′, Λ(h);Dbase) + 1 2 dH∆H(D novel, Λ(Dbase))
(11)
Proofs of Lemma 1 and Lemma 2 are provided in the appendix. We give the core theory in this paper by plugging Lemma 1 and Lemma 2 into Eqn. 8.
Theorem 1 The upper bound of error rate on novel classes in few-shot learning is: novel ≤ base(h′∗) + dis(h′, h′∗;Dbase)
+ dis(Λ−1(h), h′;Dbase) + λ+ 1
2 dH∆H(D
novel, Dbase) + 1
2 dH∆H(D
novel, Λ(Dbase))
(12)
Based on theoretical analysis and experiments, we come to several conclusions:
1. In theory, the error rate of few-shot classification is influenced by linear separability of feature representation and classifier discrepancy between task-specific and task-independent classifiers. Experiment results indicate that the main cause of error in few-shot learning is classifier discrepancy.
2. From Theorem 1, we can see that the upper bound of error rate on novel classes is positively related to 1) linear separability on Dbase, 2) classifier discrepancy on Dbase, 3) the combined error and 4)H∆H-divergence of Dnovel and Dbase measuring the discrepancy between two domains.

heading: 4.3 REDUCING CLASSIFIER DISCREPANCY FOR FEW-SHOT LEARNING
text: Based on our theoretical analysis, we propose a simple method to reduce the upper bound of error rate, boosting few-shot performance by reducing classifier discrepancy.
Measuring Classifier Discrepancy It is proved in Sec. 4.2 that reduce error on novel classes can be achieved by improving linear separability and reducing classifier discrepancy. Furthermore, experiment reveals that the cause is the discrepancy between task-specific classifier and ideal classifier. For these reasons, we target to reduce the upper bound by decreasing classifier discrepancy. Discrepancy denoted in Eqn. 6 is non-differentiable so that we propose two measurements of classifier discrepancy to ease gradient propagation in training stage. Since we consider linear classifier in this paper, an intuitive way to reduce classifier discrepancy is to reduce distance between classification weights. Squared euclidean distance can be used as a measurement:
disMSE(h, h ∗;W,W ∗) = E[‖W −W ∗‖22] (13)
where W is the weight of task-specific classifier h and W ∗ is the weight of task-independent classifier h∗. disMSE measures the variance of classification weights. Since task-specific classifier is decided by data sampling, taking data distribution into consideration, we suggest to calculate the difference of logit predicted by various classifiers. Consider commonly used KL divergence to measure the difference of logits:
disKL(h, h ∗) = E[KLD(h(Dq;Ds), h∗(Dq))] (14)
Training Policy Training process of proposed method Reducing Classifier Discrepancy (RCD) consists two phases. In the first phase, model is trained in conventional supervised way on base classes. Loss function in phase 1 is:
Lsup = Lce(h(F (x)), y),with (x, y) ∼ Dbase (15)
where Lce is standard cross-entropy loss. The classifier h∗ = arg minh Lsup obtained in this stage is treated as the ideal classifier, also the task-independent classifier, on Dbase. With fixed h∗, we train the model on meta tasks T base with loss in Eqn. 16:
Lmeta = Lce(h(F (x)), y) + β dis(h, h ∗),with (x, y) ∼ T base (16)
The second training procedure aims to reduce classifier discrepancy on base classes. Consequently, the upper bound of novel can be decreased as verified in Theorem 1.
Our method shows great flexibility that training in the first phase is free of carefully designing base learners. Moreover, policy in the second phase can generalize to different base learners. Algorithm is shown in the appendix.

heading: 5 EXPERIMENTS

heading: 5.1 IMPLEMENTATION DETAILS
text: Dataset and Backbone We conduct experiments on three benchmarks: mini-ImageNet (Vinyals et al. (2016)), tiered-ImageNet (Ren et al. (2018)) and CIFAR-FS (Bertinetto et al. (2018)). ResNet12 (Lee et al. (2019)) and ConvNet-64 (Snell et al. (2017)) are employed as backbones in this paper. Details about data setting and architectures are shown in the appendix.
Base Learner To illustrate the effectiveness of our proposed method, we use three base learners: PN, Ridge Regression (RR) and Logistic Regression (LR) (Bertinetto et al. (2018)). 1)PN is derived from (Snell et al. (2017)) which finds the nearest prototype based on cosine similarity. Prototype is computed from support samples: P = norm( 1K ∑K i F (xi)). Predicted labels of query samples are given by Ŷ = arg minc Cos(Pc, X). 2) RR Classification weight is estimated by W = (XTX + γI)−1XTY where Y is one-hot labels of support samples and I is identity matrix. Prediction of query samples are Ŷ = X · W . 3) LR Classification weight in logistic regression is W = arg minW Lce(D
s,W ). Query samples are predicted by Ŷ = X ·W . Descriptions are detailed in the appendix.

heading: 5.2 RESULTS OF RCD
text: We evaluate the proposed Reducing Classifier Discrepancy (RCD) on three benchmarks, with three base learners and two backbones. Table 2 and Table 3 summarize few-shot results with disMSE and disKL be auxiliary loss respectively. Overall, RCD achieves consistent improvements in most cases.
Auxiliary Loss As displayed in Eqn. 16, two measurements of classifier discrepancy can be added as auxiliary loss in meta-train stage. We compare the results without and with auxiliary constraints in Table 2 and Table 3. Each second column of three base learners shows few-shot accuracies by reducing classifier discrepancy constrained by disMSE or disKL. Generally, disMSE is an useful
constraint which results in improvements up to 2.82% on 1-shot CIFAR-FS with RR. By contrast, disKL shows superiority in reducing classifier discrepancy that by adding constraint disKL, accuracy is raised in all cases, up to 3.45% on 1-shot CIFAR-FS with PN. Under the same conditions, reducing classifier discrepancy can bring in larger improvements in 1-shot scenarios. For example, on mini-ImageNet with PN, reducing classifier discrepancy through diminishing KL divergence achieves improvement by margins of 2.91% in 1-shot and 2.07% in 5-shot. Experiment results are consistent with our theory. In 1-shot settings, discrepancy is larger due to data scarcity. Thus, RCD makes more obvious increase on 1-shot tasks.
Base Learner We argue for the flexibility and generalization of proposed RCD. For verification, we adopt three commonly used linear classifiers as base learner in meta-train stage. Results in Table 2 and Table 3 demonstrate feasibility of our method in improving few-shot performance regardless of specific classifier. It indicates that reducing classifier discrepancy on base set is effective to lower the upper bound of novel.
Backbone In this section, ResNet-12 and ConvNet-64 are used for ablation study. Overall performance on ResNet-12 is prominently better than performance on ConvNet-64. Moreover, RCD makes relatively larger improvements when taking ResNet-12 as architecture. Note that dimension of features extracted by ConvNet-64 is 64 while dimension of ResNet-12 features is 640. Higher dimension indicates larger hypothesis space. That is, classifier in higher-dimension space is less stable so classifier discrepancy is larger. ResNet-12 holds a higher-dimension space where reducing classifier discrepancy can result in more obvious improvements.

heading: 5.3 CLASSIFIER DISCREPANCY
text: We compare changes of discrepancy in Table 4 to clearly illustrate the proposed method is effective in reducing classifier discrepancy. Changes are denoted in colors. It can be clearly see that after the second training stage with constraints disMSE and disKL, classifier discrepancy is reduced in nearly all settings, especially on mini-ImageNet and CIFAR-FS. Downward trend of classifier discrepancy is positively correlated to decreasing the upper bound of error rate. Results in Table 4 are consistent with accuracy increment in Table 2 and Table 3, further proving the rationality of our proposed theory.

heading: 5.4 VISUALIZATION
text: T-SNE visualization (Maaten & Hinton (2008)) is provided in Fig. 1 to give an intuitive understanding of our method. In Fig. 1, figures in the first column display the distribution of features that trained in conventional way. Figures in latter columns visualize features trained with proposed constraints disMSE and disKL. We can see that features within same classes cluster more tightly and the boundaries among different classes become more clear. Our method enables larger separability in feature space.

heading: 6 CONCLUSION
text: In this paper, we theoretically analyze the upper bound of error rate on novel classes in few-shot learning. We derive that the upper bound is decided by feature separability and classifier discrepancy. Furthermore, the observation shows that classification error is mainly caused by classifier discrepancy in few-shot scenarios. Based on our observation and theory, we propose a simple method to lower the upper bound of classification error by reducing classifier discrepancy. Two differentiable discrepancy measurements are proposed as auxiliary constraints in our method RCD which is feasible on different base learners. To verify the feasibility and generalization of proposed RCD, comprehensive experiments are conducted on three few-shot benchmarks with three base learners. Experiment results powerfully prove that RCD is effective to reduce classifier discrepancy and consequently lower the upper bound of error rate in few-shot learning.

Review summaries:
This paper seeks to understand theoretically the current bottleneck in few-shot learning and address it with a new way of training the embedding. The authors find that the key issue in few-shot learning is not the separability of the novel classes but the discrepancy between classifiers trained on large datasets and few-shot classifiers. They then propose a way to reducee this discrepancy.

This paper analyzes the upper bound of error rate on novel classes in few-shot learning theoretically. It derives that the upper bound is decided by feature separability and classifier discrepancy and shows that classification error is mainly caused by classifier discrepancy in few-shot scenarios. In addition, this paper proposes a new method to lower the upper bound of classification error by reducing classifier discrepancy. 

This paper aims to understand the cause of error in few-shot classification. The authors are particularly interested in the upper-bound of the error rate, which they break down into linear separability in the feature space of the meta-train classes and classifier discrepancy on the meta-train classes, among other terms. Empirical results show that the latter is the dominant term. After identifying this, the authors propose a method, Reducing Classifier Discrepancy, to reduce the classifier discrepancy, lowering the upper-bound of the error rate. Empirical results show the benefits of the proposed method on three few-shot datasets.