Instance-based Max-margin for Practical Few-shot Recognition

To make FSL simpler, more practical, and closer to human’s few-shot learning capability, we propose a new practical few-shot learning (pFSL) paradigm, which is characterized by the following properties:

• $\bullet$

  Removing the base set. The prior knowledge obtained through pretraining on the base set is limited, as the base set only contains limited number of concepts. In some applications, collecting data sharing similar concepts with the novel set may be as difficult as collecting more samples for the novel set itself.

• $\bullet$

  Pretrained model based on big data. A model pretrained on a large training set containing a wide variety of concepts is analogous to the common-sense and domain knowledge our brains encode, which will be useful for few shot learning in diverse domains.

• $\bullet$

  Many-way FSL. In an $N$-way $k$-shot FSL, we seek $N$ to be large and $k$ to be small, e.g., using all the CUB [39] categories ($N=200$ categories and $k$ is 1 or 5). This makes pFSL much closer to real-world applications than traditional FSL.

• $\bullet$

  Unsupervised pretraining. In pFSL, we require the pretraining to be unsupervised. Since a large scale dataset (e.g., ImageNet) may contain the concept in few-shot learning (e.g., those birds in CUB), avoiding using the labels during pretraining is necessary to make the evaluation of FSL algorithm fairer.

These properties distinguish pFSL from traditional FSL and some recent variants of it [22, 28, 9, 12, 23].

The pFSL framework is clearly simpler than traditional FSL, and it leads to not only benefits in the training phase, but more importantly better evaluation of FSL algorithms.

Traditional $N$-way $k$-shot FSL typical use $N=5$ and $k=1,5$, which inevitably leads to unreliable estimation of the test accuracy. Hence, the common practice is to sample a large number of $n$ episodes ($n\geq 500$), find the accuracy in each episode, and report the average accuracy $\mu$ along with its 95% confidence interval $Z_{95\%}$. Note that with $n$ episodes, the standard deviation $\sigma$ of the accuracy within the $n$ episodes is $\sigma=0.51\sqrt{n}Z_{95\%}$. For example, a typical result is: average accuracy 64.93%, 95% confidence interval 0.18%, but the standard deviation of accuracy is 9.18% [16] (in which $n=10000$). In short, one single evaluation of traditional FSL requires training and testing for $n$ times ($n\geq 500$) and the evaluation results are still unreliable. Because of the complicated setup, both learning and evaluation of traditional FSL algorithms are not only costly, but often carried out in slightly different ways, which renders the fair comparison even more difficult.

As a stark contrast, pFSL is much simpler and as the experimental results will show in Table 1, the estimate of average accuracy is reliable. The standard deviation is small (mostly $<1.0\%$). This reliable estimation comes from the fact that pSFL is many-way (i.e., $N$ is large). Hence, instead of running $n$ episodes, few episodes (e.g., 3) is enough to evaluate pFSL, which not only means savings in computation, but also more reliable evaluation of algorithms.

Since $k$ (the number of training images in each class) is still small but the number of classes ($N$) becomes much larger (e.g., from 5 in traditional FSL to 200 in pFSL), we expect that the challenge in learning a pFSL model is greater than that in traditional FSL. This is verified by our experiments (c.f. the results in Table 1 vs. those in Table 3).

Virtual examples, or examples that are sampled based on the original training examples, have been repeatedly proven useful when the number of training examples is small, e.g., in traditional few-shot learning [41] or long-tailed recognition (where the tail classes have few training images) [20].

The common idea in generating virtual samples is to make the virtual samples follow the underlying distributions of the classes. However, in few-shot learning this requirement is very difficult to entertain even with the help of techniques such as distribution calibration (DC) in [41], because there is only 1 or 5 examples per class.

In contrast, we do not try to sample from any underlying distribution, but try to achieve max-margin of the decision boundary, as illustrated in Fig. 1. Specifically, for every training instance $x_{i}$, we i.i.d. generate $R$ virtual samples $x_{i,r}$ ($1\leq r\leq R$) which distribute around the shell of the hypersphere centered at $x_{i}$ and whose radius is controlled by a parameter $\epsilon$. Note that the same $\epsilon$ is shared by all training examples $x_{i}$ ($1\leq i\leq kN$).

Technically, let $z_{i}$ be the feature vector produced by the pretrained model $\mathcal{M}$: $z_{i}=\mathcal{M}(x_{i})$ from a forward calculation. Then, a noise vector $\delta_{i,r}$ is randomly sampled from the standard multi-dimensional normal distribution $N(0,I_{d})$, where $d$ is the length of $z_{i}$ and $I_{d}$ is a $d\times d$ identity matrix. By adding a scaled version of the noise vector to the $i$-th training example, we obtain $z_{i,r}$ (the $r$-th virtual example for $x_{i}$):

Its label $y_{i,r}$ is $y_{i}$ (the label of $x_{i}$) and $\epsilon$ is a positive number.

Interesting properties exist in our virtual examples:

• $\bullet$

  Hypersphere for different training examples can overlap, so long as they belong to the same class (c.f. Fig. 1).

• $\bullet$

  We require the virtual examples to be correctly classified, or, the original training examples are discarded.

• $\bullet$

  The virtual examples lie around the shell, not the interior of the hypersphere. According to the Gaussian Annulus Theorem [4], almost all the probability of a high-dimensional spherical Gaussian with unit variance is concentrated in a thin annulus of width $O(1)$ with radius $\sqrt{d}$ when $d$ is large. Since $d$ is indeed large (e.g., $d=2048$), the virtual examples reside around the shell. Hence, if we maximize the radius parameter $\epsilon$ but require that the virtual examples are correctly classified, as Fig. 1 shows, we in essence achieve margin maximization in an instance-based manner.

Hence, the proposed method is named Instance-based Max-margin, abbreviated as IbM2.

One issue with the above isotropic noise sampling is that it ignores the structural property of the training examples. For instance, if the ranges for two feature dimensions are $[-1,1]$ and $[-100,100]$, respectively, isotropic sampling is clearly unsuitable.

To overcome this drawback, we calculate a range vector $s=(s_{1},s_{2},\dots,s_{d})$ using all the original training examples regardless of the class label, where $s_{i}$ is the sample standard deviation for the $i$-th dimension. Then, the IbM2 virtual examples are generated as (replacing Eq. 1)

where $\odot$ is element-wise multiplication. The final virtual example generation process is illustrated in Fig. 2. Note that estimating $s$ is dramatically easier than estimating the underlying distribution of every novel class.

It is worth noting that this ellipsoidal noise generation is unsupervised, which distinguishes itself from Distribution calibration (DC) [41]. DC samples virtual examples based on an estimated covariance structure, which is estimated from the few novel class training examples in a sample-wise manner and calibrated using the base set. As aforementioned, we argue that it makes sense to get rid of the dependency on a base set, then DC is not applicable.

More importantly, the reliability of this estimation of a dense covariance matrix is understandably much lower than our estimation of the range indicator vector $s$—we estimate $d$ values using $k\times N$ examples, while DC estimates $d\times d$ values using only 1 example and the base set. The base set calibration will help DC, but clearly its estimation is still unreliable, as shown by experiments in [41, 46]

Obviously we want $\epsilon$ to be as large as possible to achieve max-margin, under the condition that virtual examples are classified correctly. Hence, we design a simple binary search to find the optimal value for $\epsilon$.

For any given $\epsilon$ value, we can generate $kNR$ virtual examples $(x_{i,r},y_{i,r})$ ($1\leq i\leq kN$, $1\leq r\leq R$) using Eq. 2. We denote the virtual training set for this particular value of $\epsilon$ as $D^{\epsilon}$. Then, we train a linear classifier with parameters $W$ to classify $D^{\epsilon}$ and obtain the training accuracy. If the training accuracy is too high (larger than a threshold $T$), $\epsilon$ is enlarged; otherwise $\epsilon$ is shrunk. The binary search maintains a search range, when the search range is tight enough (when the range is less than 0.05 in Algorithm 1), the search terminates, and we have found the optimal value $\hat{\epsilon}$.

We have a few notes for finding $\hat{\epsilon}$:

• $\bullet$

  Unlike DC [41], we do not need a validation set.

• $\bullet$

  The threshold $T$ does not need to be 1 (100%). In SVM learning, the slack variable trick allows some support vectors not to have max-margin. Similarly, we just need $T$ to be close to 1 (0.9 in our experiments).

Finally, the IbM2 pipeline is simple: First, use Algorithm 1 to find $\hat{\epsilon}$. Second, generate the virtual dataset $D^{\hat{\epsilon}}$. And third, learn a linear classifier $W$.

Note that the pretrained model $\mathcal{M}$ is frozen and will not be updated.

For both the searching and training stages of IbM2, all features extracted by the backbone $\mathcal{M}$ were $L2$-normalized first. When learning the classification head (both during the binary search and after $\hat{\epsilon}$ was determined), we used Adam as the optimizer and the label smoothed cross-entropy loss [35] as the learning objective. The pretrained model was trained using various self-supervised learning methods on the ImageNet-1K [30] training set.

During the binary search, for all the experiments we will report, we always set $R$ as 200, $T$ as 0.9 in pFSL and $0.999$ in the traditional FSL setting, except when we carried out ablation experiments on these hyperparameters.

Full implementation details are included in the appendix.

Datasets and Evaluation Setup. We explored two common many-way classification datasets, ImageNet-1K [30] and CUB-200-2011 (CUB) [39]. ImageNet-1K contains about 1.28 million training images from 1,000 classes and 50,000 images for evaluation. CUB is a fine-grained recognition dataset composed of 11,788 images belonging to 200 classes of birds, 5,994 for training and 5,794 for evaluation.

For both datasets, we randomly sampled the training sets for pFSL by selecting $k$ images from every class (i.e., $k$-shot) and using all the classes (1000 and 200, respectively) to form the novel set. $k$ is chosen from $\{1,2,3,4,5,8,16\}$. The evaluation was carried out on the full validation (for ImageNet) or test (for CUB) set.

Utilizing various self-supervised backbone network $\mathcal{M}$ pretrained on ImageNet, we compare two sets of results: one in which the linear classifier was obtained by using the original training set, the other by using IbM2’s virtual examples. We report the top-1 accuracy and its standard deviation computed over 3 randomly sampled novel sets.

Main Results. As the results in Table 1 suggest, we evaluated on two types of backbones: Vision Transformer (ViT) [13] and ResNet50 [19]. The pretraining methods included DINO [6], MoCov3 [10], MSN [2], SimCLR [8] and BYOL [17]. Table 1 shows that in almost all cases, IbM2 benefited the few-shot learning process and improved the top-1 accuracy.

When the number of shots ($k$) is very small ($\leq 2$), the improvement of IbM2 over the baseline is roughly $0.5\%$ on average. However, as the number of training shots goes larger, it is clear that the level of accuracy improvement increases gradually from $\sim 0.5\%$ to $\sim 1.0\%$, even $>2\%$ in some cases.

A useful observation from these results is that in pFSL, both the baseline and IbM2 have small standard deviations, that is, more robust in evaluation. Hence, we do not need 500 episodes in pFSL any longer—3 is enough.

Semi-supervised learning. In the self-supervised learning literature, it is a common practice to use ImageNet-1K training images to learn a backbone in the unsupervised manner, then use a small portion (e.g., 1%) of the training data now with labels to train a classifier. This semi-supervised learning task can also be viewed as in our pFSL setting. Hence, we also report the 1% ImageNet-1K semi-supervised learning (on average 12 labeled training images per class) results in Table 2. IbM2 consistently improved various self-supervised models and backbone architectures in all cases, with 0.5% to 1.2% top-1 accuracy increase.

Datasets and Evaluation Setup. We evaluated IbM2 in the traditional FSL setup, too. We conducted experiments on two standard benchmark datasets, mini-ImageNet [38] and CIFAR-FS [3]. mini-ImageNet consists of 100 categories selected from ImageNet-1K, which are further split into 64 base, 16 val and 20 novel categories according to [29]. CIFAR-FS is created by randomly shuffling the 100 categories of CIFAR-100 [24] into 64 base, 16 val, 20 novel categories. Note that in order to perform traditional few-shot learning, only the novel split of these two datasets is required to sample many 5-way 1/5-shot episodes. We report the metrics mentioned in [16]: the average ($\text{ACC}_{m}$), worst-case ($\text{ACC}_{1}$), average of worst 10 ($\text{ACC}_{10}$), average of worst 100 ($\text{ACC}_{100}$) episodes’ accuracy, and the standard deviation ($\sigma$) over 500 episodes for comprehensive evaluation. To make the results more reliable, we average the value of each metric from 5 runs with different random seeds. We adopted PMF [22], $S2M2_{R}$ [28] and Meta-Baseline [11] as the pretraining or meta-training approaches to obtain the backbone weights out of the base set.

Main Results. As shown in Table 3, by plugging IbM2 in during classifier learning, the proposed IbM2 improved the average accuracy $\text{ACC}_{m}$ in all cases except only 1 result. And, the standard deviation $\sigma$ was reduced by IbM2 or remain unchanged in all cases. As [16] advocated, smaller $\sigma$ means the learning process is more stable.

[16] also advocates the worst-case episodes accuracy is more important than the average accuracy among all episodes. Table 3 shows that IbM2 almost always leads to higher worst-case ($\text{ACC}_{1}$) or near-worst-case ($\text{ACC}_{10}$, $\text{ACC}_{100}$) accuracy. Furthermore, the average gain of $\text{ACC}_{m}$ is 0.4%, which is far less than that of $\text{ACC}_{1}$ (1.3%). As for $\text{ACC}_{10}$ and $\text{ACC}_{100}$, their gains are very similar, both around 0.5%. These observations demonstrate that IbM2 can boost the recognition accuracy of few-shot learning in almost every scenario, especially the worst case one.

At last, by comparing the numbers in Tables 1 and 3, pFSL is more challenging than traditional FSL, which leads to more open questions to solve.

We performed ablation studies for IbM2 in the pFSL setting on ImageNet-1K.

Instance-based vs. class-based max-margin. IbM2 seeks max-margin through an instance-based manner. In this study, we compare this instance-based max-margin with the well-known support vector machine (SVM), which achieves max-margin in a class-based manner. We experimented with SVM using the linear kernel function in the LIBSVM [7] software package. By iterating the value of SVM’s regularization hyperparameter $C$ from the set $\{0.1,1,10,100,1000\}$, we found the best accuracy among them to compare with our IbM2 method.

As shown in Table 4, the proposed IbM2 method outperforms SVM with the best $C$ by a significant margin in all cases. Specifically, the recognition accuracy improves $\sim$2% on average, and even up to $\sim$4% in the extremely scarce 1-shot case. These results demonstrate that our instance-based margin generated by IbM2 helps more to learn a robust classification boundary, especially when the training distribution is drastically shifted.

Sensitivity of $R$. As described in Sec. 4, one original training example is turned into $R$ virtual examples to form the training set $D^{\hat{\epsilon}}$. In this part, we study the effect of the hyperparameter $R$. As shown in Table 5, when the training shots are highly limited, increasing $R$ significantly improves recognition accuracy. As the number of training shots gets larger, the accuracy difference between a large $R$ ($R=400$) and a small one ($R=1$) gradually decreases from 1.6% to 0.2%.

When training samples are extremely scarce, it is difficult to model the correct Gaussian distribution with a few samples in a high-dimensional space. Therefore, increasing $R$ is necessary for a good estimation. When more training shots are available, the need for a large value of sampling times is reduced, hence the accuracy difference between different $R$ becomes smaller, too. Based on these results, we let $R=200$ in all our experiments.

Ellipsoidal vs. isotropic sampling. We have described two noise sampling strategies to generate virtual examples. The ellipsoidal one is preferred over the isotropic one, and is used in IbM2. In this part, we evaluate the effectiveness of this sampling schema by experimentally comparing these two sampling strategies. The isotropic sampling strategy is denoted as Spherical in Table 6.

As shown in Table 6, the accuracy in the ellipsoidal sampling schema is consistently better than its spherical counterpart or the baseline. Moreover, in low-shot cases ($\leq 3$), sampling with spherical Gaussian slightly degraded the recognition accuracy. The reason may be that the standard deviation of different channels calculated from training features varied a lot, thus simply regarding all channels as independent and identically distributed might make the sampled points significantly shifted from the underlying distribution. However, as the number of training samples increases, both isotropic and ellipsoidal sampling outperformed the baseline.

Based on these observations, we chose to adopt the ellipsoidal noise sampling (Eq. 2) in IbM2.

On what classes can IbM2 help? Finally, we study what classes will benefit from IbM2—will most or only a small portion of classes be improved by IbM2? After the training of the baseline and IbM2 finished, we calculated the class-wise validation accuracy for every class on ImageNet-1K, as

where $\text{ACC}^{k}$ is the per-class accuracy (recall) of the $k$-th class, $N_{cls}^{k}$ is the number of test samples from class $k$ ($N_{cls}^{k}=50$ in ImageNet-1K) and ${N_{cor}^{k}}$ is the number of correctly classified samples of class $k$. For every class, we obtain the difference of per-class accuracy (that of IbM2 minus that of the baseline). A positive difference is an accuracy gain and a negative gain is in fact an accuracy loss.

We then sort the baseline’s per-class accuracy in the ascending order. Following this order, we rearrange the per-class accuracy gains. The 1000 accuracy gains are divided into 10 histogram bins in the rearranged order, and inside each bin the 100 per-class accuracy gains are averaged to obtain the accuracy gain of that bin. Fig. 3 plots the average accuracy gain in each bin.

We find that IbM2 improves average per-class accuracy in almost every histogram bin (i.e., is above the “0.0” horizon in the $y$-axis). More detailed numbers reveal that the recognition accuracy of more than 65% categories out of 1000 is improved in all shots. Furthermore, Fig. 3 shows a trend: the more accurate a class is, the higher gains IbM2 can achieve over the baseline. That is, when the task is too difficult for the baseline, IbM2 can help but its usefulness is restricted. But, when the baseline is already accurate enough (categorical subset 9 and later), the room for IbM2’s further improvement is small again. It is the middle range that IbM2 is the most useful.