Few-shot Learning with LSSVM Base Learner and Transductive Modules

In a few-shot classification task, we are given some training data which contains $N$ distinct, unseen classes with $K$ samples each. For a test sample, we need to classify it correctly into one of the $N$ classes. In most prior works, each task is organized as an episode which consists of a support set $\mathcal{S}$ and a query set $\mathcal{Q}$, and a $N$-way $K$-shot task can be defined as a tuple $\{\mathcal{S},\mathcal{Q}\}$, where

	$\displaystyle\mathcal{S}=$	$\displaystyle\{s^{(c)}\}_{c=1}^{N},\quad|s^{(c)}|=K$
	$\displaystyle\mathcal{Q}=$	$\displaystyle\{q^{(c)}\}_{c=1}^{N},\quad|q^{(c)}|=Q$

where $c$ is the class index and $Q$ is the number of query samples in each class. A 3-way 2-shot task is shown in Figure 1. Before classification, a backbone $f_{\theta}(\cdot)$, a CNN or ResNet (He et al. 2016), is needed to map the original inputs to feature representations and is expected to extract similar representations for the (support or query) samples in the same class. Then a base learner $\mathcal{A}$ output the optimal classifier $\psi$ of the task basing on the support set $\mathcal{S}$, i.e., $\psi=\mathcal{A}(\mathcal{S};\theta)$. In particular, for transductive setting, the base learner $\mathcal{A}$ also takes the query samples as input.

Meta-learning approaches aim to learn some inductive bias that generation across a distribution of tasks, so they can be considered to learn over a collection of tasks, i.e., $\mathcal{T}_{train}=\{(\mathcal{S}_{i},\mathcal{Q}_{i})\}_{i=1}^{I}$, called meta-training set. The model is learned by minimizing generalization error across tasks given a base learner $\mathcal{A}$ and the learning objective is:

$$\min_{\theta}\mathbb{E}_{\mathcal{T}_{train}}\left[\mathcal{L}^{meta}(\mathcal{Q},\psi)\right]+\mathcal{R}(\theta),\psi=\mathcal{A}(\mathcal{S};\theta)$$

(1)

where $\mathcal{L}^{meta}$ is a loss function, e.g., cross entropy loss, and $\mathcal{R}(\theta)$ is the regularization term.

After the model is learned, its generalization is evaluated on a set of held-out tasks, called meta-testing set, $\mathcal{T}_{test}=\{(\mathcal{S}_{j},\mathcal{Q}_{j})\}_{j=1}^{J}$ and computed as

$$\mathbb{E}_{\mathcal{T}_{test}}\left[\mathcal{L}^{meta}(\mathcal{Q},\psi)\right],\quad\psi=\mathcal{A}(\mathcal{S};\theta)$$

(2)

Following prior work (Ravi and Larochelle 2016; Finn, Abbeel, and Levine 2017), the stages corresponding to Equation (1) and (2) are called meta-training and meta-testing respectively. In addition, during meta-training, a held-out meta-validation set $\mathcal{T}_{val}$ is kept to choose the best model parameters. The categories in $\mathcal{T}_{train}$, $\mathcal{T}_{test}$ and $\mathcal{T}_{val}$ are different to each other, which makes sure the tasks in $\mathcal{T}_{test}$ and $\mathcal{T}_{val}$ are unseen for the learned model.

The choice of base learner $\mathcal{A}$ is crucial to few-shot classification. Many choices of base learners have been proposed (Snell, Swersky, and Zemel 2017; Bertinetto et al. 2018; Gidaris and Komodakis 2018; Lee et al. 2019), among them MetaOptNet (Lee et al. 2019) achieve impressive performance using discriminatively trained linear classifier (e.g., SVM). However, it needs to solve the quadratic programming problem with iterative algorithm which brings an increase in computational overhead. In addition, due to the limitation of the number of iterations and the quadratic programming solver, the obtained classifier can only be approximately optimal. Instead, we use multi-class least square support vector machine as our base learner which only need to solve the system of linear equations obtained from the Karush-Kuhn-Tucker (KKT) condition and can get the optimal solution.

There are three basic coding approaches for multi-class problems using binary classifiers: one-vs-all, one-vs-one and error correcting output codes (ECOC) (García-Pedrajas and Ortiz-Boyer 2011). Given train set $\{(x_{i},y_{i})\}_{i=1}^{n}$ with $C$ distinct categories, coding each category with a vector of length $L$ with each element chosen from $\{0,\pm 1\}$, we can get a coding matrix $M\in\mathbb{R}^{C\times L}$ and $L$ train sets $\{(x_{i},y_{i}^{l})\}_{i=1}^{n},l=1,\cdots,L$ for $L$ binary classifiers respectively. The quadratic programming formulation is

	$\displaystyle\min_{w,b}\quad$	$\displaystyle\sum_{l=1}^{L}\left[\frac{1}{2}(w_{l}^{T}w_{l}+b_{l}^{2})+\frac{\gamma}{2}\sum_{i=1}^{n}e_{i}^{l2}\right]$		(3)
	$\displaystyle s.t.\quad$	$\displaystyle y_{i}^{l}\left[w_{l}^{T}\varphi(x_{i})+b_{l}\right]=1-e_{i}^{l},\forall i,l$		(4)

where $\gamma$ is the regularization parameter and $\varphi(\cdot)$ is a mapping function. Using the Karush-Kuhn-Tucker (KKT) condition, we only need to solve the system of linear equations:

$$\begin{bmatrix}-2I&Y^{T}\\ Y&\Omega\end{bmatrix}\begin{bmatrix}\textbf{b}\\ \bm{\alpha}\end{bmatrix}=\begin{bmatrix}\textbf{0}\\ \textbf{1}\end{bmatrix}$$

(5)

where $I$ is the identity matrix, $\bm{\alpha}=[\alpha_{1}^{T},\cdots,\alpha_{L}^{T}]^{T}$ is the dual variable and

$$\Omega=\begin{bmatrix}\Omega_{1}&\cdots&0\\ \vdots&\ddots&\vdots\\ 0&\cdots&\Omega_{L}\end{bmatrix}\qquad Y=\begin{bmatrix}y^{1}&\cdots&0\\ \vdots&\ddots&\vdots\\ 0&\cdots&y^{L}\end{bmatrix}$$

(6)

and $y^{l}_{i}\in\{0,\pm 1\},\Omega_{l}^{ij}=y_{i}^{l}y_{j}^{l}\Phi(x_{i},x_{j})+\frac{1}{\gamma}\delta_{ij},\forall i,j,l$ with $\Phi(\cdot,\cdot)$ is the kernel function and $\delta_{ij}$ is the Kronecker delta function. Given a test sample $x$, its classification results in the $L$ classifiers constitute its class code and take the class with the smallest code Hamming distance as the prediction class, i.e.,

	$\displaystyle y=$	$\displaystyle\arg\min_{r}\sum_{l=1}^{L}\frac{1-sgn(M_{rl}\cdot sgn(c_{l}(x)))}{2}$		(7)
	$\displaystyle\approx$	$\displaystyle\arg\max_{r}\sum_{l=1}^{L}M_{rl}\cdot c_{l}(x),r=1,\cdots,C$		(8)

where $c_{l}(x)=\sum_{i=1}^{n}\alpha_{l}^{i}y^{l}_{i}\Phi(x_{i},x)+b_{l}$ and $sgn(\cdot)$ is the sign function.

Note that there are only $L(n+1)$ variables in Equation (5) which is small in the few-shot task ($n=NK$), and there is no need to iterate multiple steps. Using this base learner, our system is end-to-end trainable which means we need to calculate $\frac{\partial\alpha}{\partial x}$ and $\frac{\partial b}{\partial x}$, where $x$ corresponds to the output of the backbone. Using implicit function theorem (Dontchev and Rockafellar 2009; Krantz and Parks 2012) on Equation (5), we can solve it easily.

Next, we introduce how to use query samples to modify the support set so as to obtain the better classifier parameters.

We evaluate our model on two standard few-shot learning benchmarks: miniImageNet (Vinyals et al. 2016) and CIFAR-FS (Bertinetto et al. 2018).

For fair and comprehensive comparison with previous approaches, we employ two popular networks as our backbone: 1) Conv4 (Kim et al. 2019; Ye et al. 2020; Yang et al. 2020) consists of four Conv-BN-ReLU blocks and the last two blocks contain the dropout layer (Srivastava et al. 2014); 2) ResNet12 (Lee et al. 2019; Ye et al. 2020; Yang et al. 2020) consists of four residual blocks and each residual block consists of three Conv-BN-ReLU blocks. Instead of optimizing from scratch, we apply an additional pretraining strategy as in (Fei et al. 2020) which pretrains the backbone using Places365-standard dataset (Zhou et al. 2017) for the standard 365-way classification. The purpose of using the pretraining strategy is to warm up the backbone and thus assist training the transductive modules. During pretraining, we crop the images to $84\times 84$ and $32\times 32$ for miniImageNet and CIFAR-FS respectively. We use SGD with Nesterov momentum of 0.9 and weight decay of 0.0005. The model is meta-trained for 60 epochs and each epoch consists of 1000 batches with each batch consisting of 8 episodes. Considering the Pseudo Support Module can be performed multiple times, we choose the number of iterations $k=10$ during meta-testing for all experiments.

We evaluate our model in 5-way 1-shot/5-shot settings and randomly sample 1000 episodes for evaluation and report the average accuracy ($\%$) as well as $95\%$ confidence interval.

Please see the supplementary material for more details.

We compare our model with several state-of-the-art transductive meta-learning approaches, and the result is shown in Table 1. We use the same pretraining strategy as us for several baselines for fair comparison. Specifically, for FEAT (Ye et al. 2020) which uses a different pretraining strategy, we directly replace its original pretraining weights with the weights obtained by our pretraining strategy. For SIB (Hu et al. 2020) which freezes the backbone during meta-training, if we directly use the weights pretrained on Places365-standard dataset, the final result is very poor because there is no information about miniImageNet or CIFAR-FS, so we first use the weights pretrained on Places365-standard dataset as initialization, and then pretrain the backbone again on miniImageNet and CIFAR-FS using the strategy in SIB. For DPGN (Yang et al. 2020) which does not use any pretraining strategy, we use the weights obtained by our pretraining strategy as the initialization of the backbone and reduce its learning rate. All results are obtained using the public implementation published by the authors.

As shown in Table 1, the new pretraining strategy improves the few-shot classification accuracy to different degrees, which shows the potential of transfer learning to improve few-shot learning. Furthermore, our first transductive module, IAM, can achieve the improvements ranging from $0.84\%$ to $3.93\%$ over the LSSVM base learner, and outperforms batch normalization. Our second transductive module, PSM, further improve the few-shot classification accuracy, especially for difficult 1-shot tasks with the improvement ranging from $3.69\%$ to $6.19\%$. Those results clearly validate the effectiveness of our transductive modules and our model, FSLSTM (LSSVM+IAM+PSM), achieves state-of-the-art performance on both datasets.

Next, we compare the LSSVM base learner with existing ones, i.e., nearest-neighbor classifier (Snell, Swersky, and Zemel 2017), ridge-regression (Bertinetto et al. 2018; Lee et al. 2019) and SVM (Lee et al. 2019), in terms of accuracy and inference speed. For fair comparisons, we employ them on miniImageNet and CIFAR-FS using the same backbone without pretraining. Specifically, we use ResNet12 as the backbone to evaluate accuracy, and use Conv4 as the backbone to evaluate inference speed. Using the small convolutional network can better reflect the difference in inference speed among different base learners. We compare the amount of time required to solve 10,000 randomly sampled tasks on a single NVIDIA RTX2080Ti GPU.

As shown in Table 2, the LSSVM base learner achieves higher accuracy than existing ones with faster inference speed. Specifically, the LSSVM base learner outperforms MetaOptNet-SVM (Lee et al. 2019) on both few-shot learning benchmarks and is $2\sim 6$ times faster than it with Conv4 as the backbone. On the other hand, the LSSVM base learner is as fast as Prototypical Network (Snell, Swersky, and Zemel 2017) but achieves significantly better results.

A closely related work (Hou et al. 2019) with our Pseudo Support Module augments the support set using the confidently classified query images during meta-testing, i.e., choosing the query samples with higher predicted scores as the pseudo support samples. Similar to our module, their method can also be iterated multiple times. It is worth noting that their method is specifically designed for metric-learning based approaches, i.e., matching network (Vinyals et al. 2016), prototypical network (Snell, Swersky, and Zemel 2017) and relation network (Sung et al. 2018). So it is interesting to explore the effect of this method on other base learners (e.g., ridge-regression, SVM and LSSVM), and can be directly compared with our module.

For a fair comparison, we use the transductive operation in CAN (Hou et al. 2019) and our Pseudo Support Module for various base learners, i.e., nearest-neighbor classifier (Snell, Swersky, and Zemel 2017), ridge-regression (Lee et al. 2019), SVM (Lee et al. 2019) and the LSSVM base learner. We use ResNet12 as the backbone and do not apply the pre-training initialization. We implement the transductive operation in CAN (Hou et al. 2019) for two iterations with 35 candidates for the first iteration and 70 for the second iteration, as suggested by the authors.

The results are shown in Table 3. From these results, we can make following observations: 1) our Pseudo Support Module achieves impressive effect on various base learners, not only the metric-learning based ones, but also the optimization-based ones; 2) the transductive method in CAN (Hou et al. 2019) significantly improves the metric-learning based approaches, but reduces the accuracy of the optimization-based approaches, and the reason may be that in the metric-learning based approaches, the predicted scores are directly related to the confidence of the candidate samples, while other optimization-based approaches have more complex classification mechanisms and the predicted scores and the confidence are no longer directly related, so the candidate samples become noise; 3) our transductive operation consistently outperforms the method in (Hou et al. 2019), even in metric-learning based approaches, which means our method is more universal and effective, and the class prototypes are more statistically valid and robust compared with specific samples.

Finally, we analyze our transductive modules in detail. We perform qualitative study on the Inverse Attention Module, visualizing the change of the support samples. Then we perform quantitative study on the Pseudo Support Module to explore the impact of its iteration number on accuracy.