Year: 2020

Abstract:
Few-shot classification is the task of predicting the category of an example from few labeled examples. The number of labeled examples per category is called the number of shots (or shot number). Recent works tackle this task through metalearning, where a meta-learner extracts information from observed tasks during meta-training to quickly adapt to new tasks during meta-testing. In this formulation, the number of shots exploited during meta-training has an impact on the recognition performance at meta-test time. Generally, the shot number used in meta-training should match the one used in meta-testing to obtain the best performance. We introduce a theoretical analysis of the impact of the shot number on Prototypical Networks, a state-of-the-art few-shot classification method. From our analysis, we propose a simple method that is robust to the choice of shot number used during meta-training, which is a crucial hyperparameter. The performance of our model trained for an arbitrary meta-training shot number shows great performance for different values of meta-testing shot numbers. We experimentally demonstrate our approach on different few-shot classification benchmarks.

heading: 1 INTRODUCTION
text: Human cognition has the impressive ability of grasping new concepts from exposure to a handful of examples (Yger et al., 2015). In comparison, while modern deep learning methods achieve unprecedented performances with very deep neural-networks (He et al., 2016; Szegedy et al., 2015), they require extensive amounts of data to train, often ranging in the millions. Few-shot learning aims to bridge the sample-efficiency gap between deep learning and human learning in fields such as computer vision, reinforcement learning and speech recognition (Santoro et al., 2016; Ravi & Larochelle, 2017; Finn et al., 2017; Vinyals et al., 2016; Wang et al., 2019a). These methods fall under the framework of meta-learning, in which a meta-learner extracts knowledge from many related tasks (in the meta-training phase) and leverages that knowledge to quickly learn new tasks (in the meta-testing phase). In this paper, we focus on the few-shot classification problem where each task is defined as a N -way classification problem with k samples (shots) per class available for training.
Many meta-learning methods use the episodic training setup in which the meta-learner iterates through episodes in the meta-training phase. In each episode, a task is drawn from some population and a limited amount of support and query data from that task is made available. The meta-learner then learns a task-specific classifier on the support data and the classifier predicts on the query data. Updates to the meta-learner is computed based on the performance of the classifier on the query set. Evaluation of the meta-learner (during a phase called meta-testing) is also carried out in episodes in a similar fashion, except that the meta-learner is no longer updated and the performance on query data across multiple episodes is aggregated.
In the episodic setup, the selection of k during meta-training time can have significant effects on the learning outcomes of the meta-learner. Intuitively, if support data is expected to be scarce, the meta-learner needs to provide strong inductive bias to the task-specific learner as the danger of overfitting is high. In contrast, if support data is expected to be abundant, then the meta-learner can provide generally more relaxed biases to the task-specific learner to achieve better fitting to the task
data. Therefore it is plausible that a meta-learner trained with one k value can be suboptimal at adapting to tasks with a different k value and thus exhibit meta-overfitting to k. In experiments, k is often simply kept fixed between meta-training and meta-testing, but in real-world usage, one cannot expect to know beforehand the amount of support data from unseen tasks during deployment.
In this paper we will focus on Prototypical networks (Snell et al., 2017), a.k.a. ProtoNet. ProtoNet is of practical interest because of its flexibility: a single trained instance of ProtoNet can be used on new tasks with any k and N . However, ProtoNet exhibits performance degradation when the k used in training does not match the k used in testing.1 First, we will undertake a theoretical investigation to elicit the connection from k to a lower bound of expected performance, as well as to the intrinsic dimension of the learned embedding space. Then, we conduct experiments to empirically verify our theoretical results across various settings. Guided by our new understanding of the effects of k, we propose an elegant method to tackle performance degradation in mismatched k cases. Our contributions are threefold:
• We provide performance bounds for ProtoNets given an embedding function. From which, we argue that k affects learning and performance by scaling the contribution of intra-class variance.
• Through VC-learnability theory, we connect the value of k used in meta-training to the intrinsic dimension of the embedding space.
• The most important contribution of this paper (introduced in Section 3.3) is a new method that improves upon vanilla ProtoNets by eliminating the performance degradation in cases where the k is mismatched between meta-training and meta-testing. Our evaluation protocol more closely adheres to real-world scenarios where the model is exposed to different numbers of training samples.

heading: 2 BACKGROUND

heading: 2.1 PROBLEM SETUP
text: The few-shot classification problem considered in this paper is set up as described below. Consider a space of classes C with a probability distribution τ , N classes c = {c1, ..., cN} are sampled i.i.d. from τ to form a N -way classification problem. For each class ci, k support data are sampled from class-conditional distribution Si = {sx1, .., sxk}
iid∼ P (x|Y (x) = ci), where x ∈ RD, D denotes the dimension of data, and Y (x) denotes the class assignment of x. Note that we assume that Y (x) is singular (e.g. each x can only have 1 label), and does not depend on N (e.g. a data point with a label “cat” will always have the label “cat”), in contrast to y defined below.
Additionally, the set Q = {qx1, ..., qxl} containing l query data is sampled from the joint distribution 1 N ∑N i=1 P (x|ci).2 For each x, let y ∈ {1, ..., N} denote its label in the context of the few-shot classification task. Define Ŝi = {(sx1, y1 = i), ..., (sxk, yk = i)} as the augmented set of supports for class ci, and denote the union of support sets for N classes as S = ⋃N i=1 Ŝi. The few-shot classification task is to predict y for each x in Q given S. During meta-training, the ground truth label for Q is also available to the learner.

heading: 2.2 META-LEARNING SETUP
text: Meta-learning approaches train on a distribution of tasks to obtain information that generalizes to unseen tasks. For few-shot classification, a task is determined by which classes are involved in the N -way classification task. During meta-training, the meta-learner observes episodes of few-shot classification tasks consisting of N classes, k labelled samples per class, and l unlabelled samples, as previously described. The collection of all classes observed during meta-training forms the metatraining split Dtr = {trc1, ..., trcR}. Critically, we assume that every unseen class that the learner is evaluated upon (during meta-testing) is also drawn from the same distribution τ .
1For example, 1-shot accuracy of a 10-shot trained network performs 9% (absolute) worse than the 1-shot trained network
2We assume equal likelihood of drawing from each class for simplicity

heading: 2.3 PROTOTYPICAL NETWORKS
text: ProtoNets (Snell et al., 2017) compute E-dimensional embeddings for all samples in S and Q. The embedding function φ : RD → RE is usually a deep network.The prototype representation for each class is formed by averaging the embeddings for all supports of said class: φ(Si) = 1k ∑ x∈Si φ(x). Classification of any input x (e.g. x ∈ Q) is performed by computing the softmax over squared Euclidean distances of the input point’s embedding to the prototypes. Let ŷ denote the prediction of the classifier for one of the categories j ∈ {1, · · · , N}:
pφ(ŷ = j|x, S) = e−‖φ(x)−φ(Sj)‖
2
∑N i=1 e − ∥∥∥φ(x)−φ(Si)2∥∥∥ , where ‖v‖2 = E∑ d=1 v2d (1)
The parameters of the embedding functions are learned through meta-training. Negative log-likelihood J(φ) = − log (p(ŷ = y|x)) of the correct class y is minimized on the query points through SGD. As explained in (Law et al., 2019), ProtoNets can be seen as a metric learning approach optimized for the supervised hard clustering task (Law et al., 2016). The model φ is learned so that the representations of similar examples (i.e. belonging to a same category) are all grouped into the same cluster in RE . We propose in this paper a subsequent metric learning step which learns a linear transformation that maximizes inter-to-intra class variance ratio.

heading: 3 PROPOSED METHOD
text: We first present theoretical results explaining the effect of the shot number on ProtoNets, and then introduce our method for addressing performance degradation in cases of mismatched shots.
3.1 RELATING k TO LOWER BOUND OF EXPECTED ACCURACY
To better understand the role of k on the performance of ProtoNets, we study how it contributes to the expected accuracy across episodes when using any kind of fixed embedding function (e.g. the embedding function obtained at the end of the meta-training phase). With I denoting the indicator function, we define the expected accuracy R as:
R(φ) = EcES,x,yI [arg max j {pφ(ŷ = j|x, S)} = y] (2)
Definitions: Throughout this section, we will use the following symbols to denote the means and variances of embeddings under different expectations:
µc , Ex[φ(x)| Y (x) = c] Σc , Ex[(φ(x)− µc)(φ(x)− µc)T | Y (x) = c] µ , Ec[µc] Σ , Ec[(µc − µ)(µc − µ)T ]
Remark. µc is the expectation of the embedding conditioned on class c. µ is the (full) expectation of the embedding, which can be expressed as the expectation of µc over classes. Σ is the variance of class means in the embedding space - it can be interpreted as the signal of the input to the classifier, as larger Σ implies larger distances between classes. Σc is the expected intra-class variance - it represents the noise in the above signal.
Modelling assumptions of ProtoNets: The use of the squared Euclidean distance and softmax activation in ProtoNets implies that classification with ProtoNets is equivalent to a mixture density estimation on the support set with spherical Gaussian densities (Snell et al., 2017). Specifically, we adopt the modelling assumptions that the distribution of φ(x) given any class assignment is normally distributed (p(φ(x)|Y (x) = c) = N (µc,Σc)), with equal covariance for all classes in the embedding space (∀(c, c′),Σc = Σc′ )3. We present the analysis for the special case of episodes with binary classification (i.e. with N = 2) for ease of presentation, but the conclusion can be generalized to arbitrary N > 2 (see appendix).
3The second assumption is more general than the one used in the original paper as we do not require Σ to be diagonal
Also, as noted in Section 2.1, we assume equal likelihood between the classes. We would like to emphasize that the assignment of labels can be permuted freely and the classifier’s prediction would not be affected due to symmetry. Hence, we only need to consider one case for the ground truth label without loss of generality. Let a and b denote any pair of classes sampled from τ . Let x be drawn from a, and overload a and b to also indicate the ground truth label in the context of that episode, then equation 2 can be written as:
R(φ) = Ea,b∼τEx,SI [ŷ = a] (3)
Additionally, noting that p(ŷ = a) can be expressed as a sigmoid function σ:
p(ŷ = a|x) = e −‖φ(x)−φ(Sa)‖2
e−‖φ(x)−φ(Sb)‖ 2 + e−‖φ(x)−φ(Sa)‖ 2 = σ( ∥∥∥φ(x)− φ(Sb)∥∥∥2 − ∥∥∥φ(x)− φ(Sa)∥∥∥2) = σ(α) , where α ,
∥∥∥φ(x)− φ(Sb)∥∥∥2 − ∥∥∥φ(x)− φ(Sa)∥∥∥2 We can express equation 3 as a probability:
R(φ) = Pr a,b,x,S (ŷ = a) = Pr a,b,x,S (α > 0) (4)
We will introduce a few auxiliary results before stating the main result for this section.
Proposition 1. From the one-sided Chebyshev’s inequality, it immediately follows that:
R(φ) = Pr(α > 0) ≥ E[α] 2
Var(α) + E[α]2 (5)
In Lemma 1 and Lemma 2, we derive the expectation and variance of α when conditioned on the classes sampled in a episode. Then, in Theorem 3, we compose them into the RHS of Proposition 1 through law of total expectation.
Lemma 1. Consider space of classes C with sampling distribution τ , a, b iid∼ τ . Let S = {Sa, Sb} Sa = {ax1, ..., axk}, Sb = {bx1, ..., bxk}, k ∈ N is the shot number, and Y (x) = a. Define φ(Sa) , 1k ∑ x∈Sa φ(x) and φ(Sb) , 1 k ∑ x∈Sb φ(x). Consider Σ as defined earlier. Assume p(φ(x)|Y (x) = c) = N(µc,Σc) and Σc = Σc′ for any choice of c, c′ ∈ C , then,
Ex,S|a,b[α] = (µa − µb)T (µa − µb) , and Ea,b,x,S [α] = 2Tr(Σ).
Lemma 2. Under the same notation and assumptions as Lemma 1, additionally invoking definition for Σc, then,
Ea,b[Var(α|a, b)] ≤ 8(1 + 1
k )Tr
( Σc((1 + 1
k )Σc + 2Σ)
) . (6)
The proofs of the above lemmas are in the appendix. With the results above, we are ready to state our main theoretical result in this section.
Theorem 3. Under the conditions where Lemma 1 and 2 hold, we have:
R(φ) ≥ 4Tr(Σ) 2
8(1 + 1/k)2Tr(Σ2c) + 16(1 + 1/k)Tr(ΣΣc) + Ea,b[((µa − µb)T (µa − µb))2] . (7)
Proof. First, we use decompose the Var(α) term in Proposition 1 by Law of Total Expectation.
Var(α) = Ea,b,x,S [α2]− Ea,b,x,S [α]2 = Ea,bEx,S [α2|a, b]− Ea,b,x,S [α]2 (8) = Ea,b[Var(α|a, b) + Ex,S [α|a, b]2]− Ea,b,x,S [α]2. (9)
Hence, Proposition 1 can also be expressed as
R(φ) ≥ E[α] 2
Ea,b[Var(α|a, b) + Ex,S [α|a, b]2] . (10)
Finally, we arrive at Theorem 3 by plugging Lemma 1 and 2 into equation 10.
Several observations can be made from Theorem 3:
1. The shot number k only appears in the first two terms of the denominator, implying that the bound saturates quickly with increasing k. This is also in agreement with the empirical observation that meta-testing accuracy has diminishing improvements when more support data is added.
2. By observing the degree of terms in equation 7 (and treating the last term of the denominator as a constant), it is clear that increasing k will decrease the sensitivity (magnitude of partial derivative) of this lower bound to Σc, and increase its sensitivity to Σ.
3. If one postulates that meta-learning updates on φ are similar to gradient ascent on this accuracy lower bound, then learning with smaller k emphasizes minimizing noise, while learning with higher k emphasizes maximizing signal.
In conclusion, these observations give us a plausible reason for the performance degradation observed in mismatched shots: when an embedding function has been optimized (trained) for ktrain > ktest, the relatively high Σc is amplified by the now smaller k, resulting in degraded performance. Conversely, an embedding function trained for ktrain < ktest already has small Σc, such that increasing k during testing has further diminished improvement on performance.

heading: 3.2 INTERPRETATION IN TERMS OF VC DIMENSION
text: In any given episode, a nearest neighbour prediction is performed from the support data (with a fixed embedding function). Therefore, a PAC learnability interpretation of the relation between the number of support data and complexity of the classifier can be made. Specifically, for binary classification, classical PAC learning theory (Vapnik et al., 1994) states that with probability of at least 1− δ, the following inequality on the difference between empirical error errtrain (of the support samples) and true error errtrue holds for any classifier h:
errtrue(h)− errtrain(h) ≤
√ D(ln 4kD + 1) + ln 4 δ
2k (11)
Where D is the VC dimension, and k is the number of support samples per class 4. Under this binary classification setting, the predictions of prototypical network are equal to σ(α) as shown earlier. Denoting zc = φ(Sc) and zc′ = φ(Sc′), we can manipulate α as follows:
α = ‖φ(x)− zc‖2 − ‖φ(x)− zc′‖2 = 2(zc′ − zc)Tφ(x) + (zTc zc − zTc′zc′) (12)
From equation 12, the prototypes form a linear classifier with offset in the embedding space. The VC dimension of this type of classifier is 1 + d where d is the intrinsic dimension of the embedding space (Vapnik, 1998). In ProtoNets, the intrinsic dimension of the embedding space is not only influenced by network architecture, but more importantly determined by the parameter themselves, making it a learned property. For example, if the embedding function can be represented with a linear transformation φ(x) = Φ · x, then the intrinsic dimension of the embedding space is upper bounded by the rank of Φ (since all embeddings must lie in the column space of Φ). Thus, the number of support samples required to learn from an episode is proportional to the intrinsic dimension of the embedding space. We hypothesize that an embedding function optimal for lower shot (e.g. one-shot) classification affords fewer intrinsic dimensions than one that is optimal for higher shot (e.g. 10-shot) classification.

heading: 3.3 RECONCILING SHOT DISCREPANCY THROUGH EMBEDDING SPACE TRANSFORMATION
text: Observations in Section 3.2 reveal that an ideal φ would have an output space whose intrinsic dimension d is as small as possible to minimize the right-hand side of equation 11 but just large enough to allow low errtrain; the balance between the two objectives is dictated by k. Similarly, observations in Section 3.1 suggest that an ideal φ would balance between minimizing Σc and maximizing Σ also according to k. As a result, when there is discrepancy between meta-training shots and meta-testing shots5, accuracy at meta-test time will suffer. A naive solution is to prepare
4This considers learning of a single episode through the formation of prototypes 5In deployment, the number of support samples per class is likely random from episode to episode.
many embedding functions trained for different shots, and select the embedding function according to the availability of label data at test-time. However, this solution is computationally burdensome as it requires multiple models to be trained and stored. Instead, we want to train and store a single model, and then adapt the embedding function’s variance characteristics and the embedding space dimensionality to achieve good performance for any test shot.
Linear Discriminant Analysis (LDA) is a dimensionality reduction method suited for downstream classification (Fukunaga, 1990). Its goal is to find a maximally discriminating subspace (maximum inter-class variance and minimal intra-class variance) for a given classification task. Theoretically, performance can be maximized in each individual episode by computing the LDA transformation matrix using support samples of that episode. LDA computes the eigenvectors of the matrix S−1Sµ, where Sµ is the covariance matrix of prototypes and S is the class-conditional covariance matrix. In practice, Sµ and S cannot be stably estimated in few-shot episodes, preventing the direct application of LDA.
We propose an alternative which we call Embedding Space Transformation (EST). The purpose of EST is to perform dimensionality reduction on the features, while also improving the ratio in Theorem 3. This is a different goal from LDA because Theorem 3 demonstrates that the expected performance across many episodes can be improved by maximizing Σ and minimizing Σc. Similar to LDA, EST works by applying a linear transformation
φ(x) 7→ V ∗(φ(x)) (13)
to the outputs of the embedding function. Here, V ∗ is a linear transformation computed using Dtr after meta-training has completed. To compute V ∗, we first iterate through all classes in Dtr and compute their in-class means and covariance matrices in the embedding space. We can then find the covariance of means Σµ, and the mean of covariances Σs across Dtr. Finally, V ∗ is computed by taking the leading eigenvectors of Σµ − ρΣs - the difference between the covariance matrix of the mean and the mean covariance matrix with weight parameter ρ. The exact procedure for computing V ∗ is presented in the appendix.

heading: 4 EXPERIMENTS AND RESULTS
text: In this section, our first two experiments aim at supporting our theoretical results in Sections 3.1 and 3.2, while our third experiment demonstrates the improvement of EST on benchmark data sets over vanilla ProtoNets. To illustrate the applicability of our results to different embedding function architectures, all experiments are performed with both a vanilla 4-layer CNN (as in (Snell et al., 2017)) and a 7-layer Residual network (He et al., 2016). Detailed description of the architecture can be found in the appendix. Experiments are performed on three data sets: Omniglot (Lake et al., 2015), miniImageNet (Vinyals et al., 2016), and tieredImageNet (Ren et al., 2018). We followed standard data processing procedures which are detailed in the appendix.

heading: 4.1 TRAINING SHOTS AFFECT VARIANCE CONTRIBUTION
text: The total variance observed among embeddings of all data points can be seen as a composition of inter-class and (expected) intra-class variance based on the law of total variance (Var[x] = E[Var(x|c)] + Var(E[x|c]) = E[Σc] + Σµ). Our analysis predicts that as we increase the shot number used during training, the ratio of inter-class to intra-class variance will decrease.
To verify this hypothesis, we trained ProtoNets (vanilla and residual) with a range of shots (1 to 10 on miniImageNet and tiered imagenet, 1 to 5 on Omniglot) until convergence with 3 random initializations per group. Then, we computed the inter-class and intra-class covariance matrices across all samples in the training-set embedded by each network. To qualify the amplitude of each matrix, we take the trace of each covariance matrix. The ratio of inter-class to intra-class variance is presented in Figure 1: as we increase k used during training, the inter-class to intra-class variance ratio decreases. This trend can be observed in both vanilla and residual embeddings, and across all three data sets, lending strong support to our result in Section 3.1. Another observation can be made that the ratio between inter-class and intra-class variance is significantly higher in the Omniglot data set than the other two data sets. This may indeed be reflective of the relative difficulty of each data set and the accuracy of ProtoNet on the data sets.

heading: 4.2 TRAINING SHOTS AFFECT INTRINSIC DIMENSION
text: We consider the intrinsic dimension (id) of an embedding function with extrinsic dimension E (operated on a data set) to be defined as the minimum integer d where all embedded points of that data set lie within a d-dimensional subspace of RE (Bishop, 2006). A simple method for estimating d is through principal component analysis (PCA) of the embedded data set. By eigendecomposing the covariance matrix of embeddings, we obtain the principal components expressed as the significant eigenvalues, and the principal directions expressed as the eigenvectors corresponding to those eigenvalues. The number of significant eigenvalues approximates the intrinsic dimension of the embedding space. When the subspace is linear, this approximation is exact; otherwise, it serves as an upper bound to the true intrinsic dimension (Fukunaga & Olsen, 1971).
We determine the number of significant eigenvalues by an explained-variance over total-variance criterion. The qualifying metric is rd , ∑ i∈[1,d] λi/ ∑ i∈[1,E] λi. In our experiments, we set the threshold for rd at 0.9. Similar to the previous experiment, we train ProtoNets with different shots to convergence. The total covariance matrix is then computed on the training set and eigendecomposition is performed. The approximate id is plotted for various values of k in Figure 2. We can see a clear trend that as we increase training shot, the id of the embedding space increases.

heading: 4.3 EXPERIMENTS WITH EST
text: We evaluate the performance of EST on the three aforementioned data sets. The performance is compared against our implementation of vanilla ProtoNets as a baseline, as well as a variant of ProtoNets using principal components obtained from all embedding points (ProtoNet-PCA).
All methods in this section use the same set of trained ProtoNets. As with before, networks are trained with k ∈ {1, ..., 5} on Omniglot and k ∈ {1, ..., 10} on miniImageNet and tieredImageNet. Additionally, we also trained a mixed-shot network for each data set. This is done by randomly selecting a value for k within the specified range for each episode, and then sampling the corresponding number of support samples. Hyper-parameters for training are described in the appendix.
Each model is evaluated on the test splits of the corresponding data sets (e.g. networks trained on Omniglot are only evaluated on Omniglot). Five test runs are performed per network on Omniglot to evaluate the k-shot performance (k ∈ [1, 5]). Each run consists of 600 episodes formed by 1-5 support samples and 5 query sample per class. The performance is aggregated across runs for the combined performance. Similarly, on miniImageNet and tieredImageNet, 10 test runs are performed with support per sample k ∈ [1, 10], 600 episodes per run, and 15 query samples in each episode. Model configuration: Vanilla ProtoNet is used as our baseline. We present the performance of multiple ProtoNets trained with different shots to illustrate the performance degradation issue. ProtoNet-PCA uses principal components of the training split embeddings in place of V ∗, with components other than the d leading ones zeroed out. We carry out a parameter sweep on miniImageNet and set d = 60; the same value is used on the other two data sets. For selecting the training shot of the embedding network, we find that overall performance to be optimal using k = 5. ProtoNet-EST contains three parameters that need to be determined: ρ, d, and training shots of the embedding network. For our experiments, we set ρ = 0.001 and d = 60 based on performance on miniImageNet. For selecting the number of training shots, we use the same strategy as before by evaluating ProtoNetEST with all trained embedding networks and found the same trend to hold. As an abalation study, FC-ProtoNet adds a fully connected layer to the embedding network such that the output dimension is also 60. Results of this variant can be found in the appendix. EST performance results: Table 1 summarizes the performance of the evaluated methods on all data sets. Due to space constraints, only 1-shot, 5-shot, 10-shot and 1-10 shot average performance are included. Additional results are in the appendix. The best performing method in each evaluation is in bold. On Omniglot, there is no significant difference in performance between the best performing vanilla ProtoNet and any other methods. We attribute this to the already high accuracy of the baseline model. On miniImageNet and tieredImageNet, EST-ProtoNet significantly outperforms baseline methods and PCA-protonet in terms of average accuracy over test runs with different shots.
We observe that matching the training shot to the test shot generally provides the best performance for vanilla ProtoNets. Also importantly, training with a mixture of different values of k does not provide optimal performance when evaluated on the same mixture of k values. Instead, the resulting performance is mediocre in all test shots. ProtoNet-EST provides minor improvements over the best-performing baseline method under most test shots settings. We hypothesize that this is due to EST aligning the embedding space to the directions with high inter-class variance and low intra-class
variance. Comparison against the direct PCA approach demonstrates that the performance uplift is not entirely attributed to reducing the dimensions of the embedding space.
In conclusion, EST improves the performance of ProtoNets on the more challenging data sets when evaluated with various test shots. It successfully tackles performance degradation when testing shots and training shots are different. This improvement is vital to the deployment of ProtoNets in real world scenarios where the number of support samples cannot be determined in advance.

heading: 5 RELATED WORK
text: We summarize related work on extensions of ProtoNets, on improving the few-shot classification setup, and on analyzing theoretical properties of meta-learning methods.
Extensions of ProtoNets: Allen et al. (2019) build upon ProtoNets by allowing each class to be represented by multiple prototypes, thereby improving the representation power of ProtoNets. Oreshkin et al. (2018) use a context-conditioned embedding network to produce prototypes that are aware of the other classes. These prior works assume matched training and testing shots whereas our work focuses on setups where testing shots are not fixed (i.e. not necessarily the same as training shots). Our work is parallel to these works in that EST can be applied on the embeddings learned by these methods.
Improvement of few-shot classification setup: Chen et al. (2019) extend the few-shot learning problem setup by considering domain adaptation in addition to learning novel classes. Specifically, they look at how well models trained on miniImageNet can perform on few-shot learning in CUB200. Importantly, they still force the number of shots to be consistent between training time and testing time. While their work deals with varying the domain of the episodes at test time, our work deals with varying shots. Concurrent to our work, Triantafillou et al. (2020) further broaden the scope of few-shot learning by introducing a benchmark composed of data from various domains; methods are tested on their ability to adapt to different domains and deal with class imbalance. We extend their work with a thorough analysis of how the number of shots affects the learning outcome, and further propose a method to overcome the negative impact of mismatched shots.
Theoretical analysis of few-shot learning: Despite the myriad of methodological improvements, theoretical work on few-shot learning has been sparse. Wang et al. (2019b) provide a unifying formulation for few-shot learning methods, and clearly outline the key challenge in few-shot learning through a PAC argument, but do not introduce any new theoretical results. In contrast, our work introduces a novel bound for the accuracy of ProtoNets; this bound provides useful intuitions pertaining to how ProtoNets adapt to few-shot episodes. Additionally, we demonstrate theoretically and experimentally that the intrinsic dimension of the embedding function’s output space varies with the number of shots as a direct consequence of the challenges outlined in the PAC argument. To the best of our knowledge, Amit & Meir (2017) provide the only prior work to bound the error of a meta-learning agent. Specifically, they use the generalized PAC-Bayes framework to derive an error-rate bound for a MAML-style learning algorithm (where the hypothesis class is fixed). Their main result relates the performance of the learning algorithm to both the number of tasks encountered during meta-training and the number of shots given in any task. In contrast to our work, their result does not apply to non-parametric methods such as ProtoNets because the hypothesis class in ProtoNets can change from episode to episode depending on the number of ways.

heading: 6 CONCLUSION AND FUTURE WORK
text: We have explored how the number of support samples used during meta-training can influence the learned embedding function’s performance and intrinsic dimensions. Our proposed method transforms the embedding space to maximize inter-to-intra class variance ratio while constraining the dimensions of the space itself. In terms of applications, our method can be combined other works (Oreshkin et al., 2018; Ye et al., 2018; Rusu et al., 2019; Dong & Xing, 2018; Ren et al., 2018; Tapaswi et al., 2019) with an embedding learning component. We believe our approach is a significant step to reduce the impact of the shot number in meta-training, which is a crucial hyperparameter for few-shot classification.

heading: ACKNOWLEDGMENTS
text: We acknowledge partial support from NSERC COHESA NETGP485577-15 and Samsung. We thank Chaoqi Wang for discussion on the initial idea, and Clément Fuji Tsang, Mark Brophy and the anonymous reviewers for helpful feedback on early versions of this paper.

heading: A APPENDIX
text: A.1 ALGORITHM FOR EST
Below is the exact procedure for computing T for embedding space transformation.
Algorithm 1 Algorithm for computing the transformation T . Ln is the number of samples belonging to class n; µn and Σn are the mean and covariance of the embeddings of that class; µT and Σs are the average of mean embeddings and covariances; Σµ is the covariance of the mean embeddings; V ∗ is the matrix of eigenvectors that correspoinds to the d largest eigenvalues in Λ.
Input: Training set Dtr = {(x1, y1), ..., (xM , yM}, where yi ∈ {1, ..., N}, Dn denotes the subset of Dtr where ∀y ∈ Dn, y = n, embedding function φ, weighting parameter ρ, dimension parameter d. Output: Transformation T . Initialize µ = {0}Nn , Σ = {0}Nn , for n = 1 to N do µ[n] = µn =
1 Ln ∑ (xi,yi)∈Dn φ(xi)
Σ[n] = 1Ln ∑ (xi,yi)∈Dn(φ(xi)− µn)(φ(xi)− µn) T
end for µT = 1 M ∑ (xi,yi)∈Dtr φ(xi) Σµ = 1 N ∑ n∈[1,N ](µ[n]− µT )(µ[n]− µT )T Σs = 1 N ∑ n∈[1,N ] Σ[n] Find V , Λ such that: Σµ − ρΣs = V ΛV T V ∗ = [vj ] for j ∈ top d of Λ T (z) = V ∗(z)
A.2 NETWORK ARCHITECTURE
The vanilla CNN has the exact same architecture as the original ProtoNet (Snell et al., 2017). It consists of four convolution layers with depth of 64; each convolution layer is followed by Relu activation, max-pooling, and batch normalization (Ioffe & Szegedy, 2015). Resnet of 7 layers is constructed with one vanilla convolution layer of depth 64 followed by three residual blocks, all joined by max-pooling layers; each residual block consists of two sets of conv-batchnorm-Relu layers, of depth 128-256-256.
A.3 DATA SET DESCRIPTION AND PRE-PROCESSING
Experiments are performed on three data sets: Omniglot (Lake et al., 2015), miniImageNet (Vinyals et al., 2016), and tieredImageNet (Ren et al., 2018). For Omniglot experiments, we follow the same configuration as in the original paper where 1200 classes augmented with rotations (4800 total) are used for training, and the remaining classes are used for testing.
For miniImageNet experiments, we use the splits proposed by (Ravi & Larochelle, 2017) where 64 classes are used for training, 16 for validation, and 20 for testing. Mirroring the original paper, we resize all miniImageNet images to 84x84. No data augmentation is applied. As most state-of-art few-shot classification methods achieve saturating accuracies on Omniglot, and miniImageNet’s small number of classes make claims about generalization difficult, we also conduct experiments of tieredImageNet.
TieredImageNet is also a subset of Imagenet1000. TieredImageNet groups classes into broader categories corresponding to higher-level nodes in the ImageNet hierarchy. It includes 34 categories, with each category containing between 10 and 30 classes. These are split into 20 training, 6 validation and 8 testing categories. In total, there are 351 classes in training, 97 in validation, and 160 in testing. Preprocessing of images follow the same steps as used for miniImageNet.
A.4 PROTONET TRAINING
Training procedure of ProtoNets largely mirrors the protocol used by Snell et al. (2017). On Omniglot, we train the network to convergence after 30000 episodes. On miniImageNet and tieredImageNet, we monitor the performance of the network on the validation set and select the best performing checkpoint after training for 50000 episodes. Adam (Kingma & Ba, 2014) optimizer is used with α = 0.9, β = 0.999, = 10−8, and an initial learning rate of 0.001 that is decayed by half every 2000 episodes. On Omniglot, we train with 60 classes and 5 query points per episode. On miniImageNet and tieredImageNet, we train with 20 classes and 15 query points per episode.
A.5 DERIVATION DETAILS
Proof of Lemma 1:
Proof. First, from the definition of α, we split Ex,S|a,b[α] in to two parts and examine them separately: Ex,S|a,b[α] = E[ ∥∥∥φ(x)− φ(Sb)∥∥∥2]︸ ︷︷ ︸
i
−E[ ∥∥∥φ(x)− φ(Sa)∥∥∥2]︸ ︷︷ ︸
ii
. (14)
In general, for random vector X , the expectation of the quadratic form is E[‖X‖2] = Tr(Var(X)) + E[X]TE[X]. Hence,
i = Ex,S|a,b[ ∥∥∥φ(x)− φ(Sb)∥∥∥2] (15)
= Tr(Σ φ(x)−φ(Sb)) + E[φ(x)− φ(Sb)] TE[φ(x)− φ(Sb)], (16)
where the first term inside the trace can be expanded as:
Σ φ(x)−φ(Sb) = Var[φ(x)− φ(Sb)] (17)
= E[(φ(x)− φ(Sb))(φ(x)− φ(Sb))T ]− (µa − µb)(µa − µb)T (18)
= Σc + µaµ T a +
1 k Σc + µbµ T b − µaµTb − µbµTa − (µa − µb)(µa − µb)T (19)
= (1 + 1
k )Σc (Last terms cancel out). (20)
To go from (18) to (19), we note that Var(X) = E[XXT ] − E[X]E[X]T and Σc ∆ = Var(φ(x)). Hence (19) can be obtained by expanding out the first term and taking the expectation of each resulting item. The second term of (16) is simply:
Ex,S|a,b[φ(x)− φ(Sb)] = µa − µb. (21) Putting them together:
i = (1 + 1
k )Tr(Σc) + (µa − µb)T (µa − µb). (22)
Similarly for ii: ii = Ex,S|a,b[ ∥∥∥φ(x)− φ(Sa)∥∥∥2] (23)
= Tr(Σ φ(x)−φ(Sa)) + E[φ(x)− φ(Sa)] TE[φ(x)− φ(Sa)] (24)
= (1 + 1
k )Tr(Σc). (25)
Putting together i and ii:
Ex,S|a,b[α] = (1 + 1
k )Tr(Σc) + (µa − µb)(µa − µb)T − (1 +
1 k )Tr(Σc) (26)
= (µa − µb)T (µa − µb) (27)
Then, since Ea,b,x,S [α] = Ea,b[Ex,S|a,b[α]], we have:
Ea,b,x,S [α] = Ea,b[(µa − µb)T (µa − µb)] (28) = Ea,b[µTa µa + µTb µb − µTa µb − µTb µa] (29) = Tr(Σ) + µTµ + Tr(Σ) + µTµ− 2µTµ (30) = 2Tr(Σ) (31)
Where from the second to the third line, we note that µTa µa and µ T b µb are quadratic forms while µ T a µb describe a dot product between two independent randomly drawn samples which has expectation µTµ.
For proof of Lemma 2, we first re-state the result on quadratic forms of normally distributed random vectors by Rencher & Schaalje (2008). Theorem 4. Consider random vector y ∼ N(µ,Σ) and symmetric matrix of constants A, we have:
Var(yTAy) = 2Tr((AΣ)2) + 4µTAΣAµ.
Proof of Lemma 2:
Proof.
Var(α|a, b) = Var( ∥∥∥φ(x)− φ(Sb)∥∥∥2 − ∥∥∥φ(x)− φ(Sb)∥∥∥2) (32)
= Var( ∥∥∥φ(x)− φ(Sb)∥∥∥2) + Var(∥∥∥φ(x)− φ(Sa)∥∥∥2) (33)
− 2Cov( ∥∥∥φ(x)− φ(Sa)∥∥∥2 ,∥∥∥φ(x)− φ(Sb)∥∥∥2) (34)
≤ Var( ∥∥∥φ(x)− φ(Sb)∥∥∥2) + Var(∥∥∥φ(x)− φ(Sa)∥∥∥2) (35)
+ 2 √ Var( ∥∥∥φ(x)− φ(Sb)∥∥∥2)Var(∥∥∥φ(x)− φ(Sa)∥∥∥2) (36) ≤ 2Var(
∥∥∥φ(x)− φ(Sb)∥∥∥2) + 2Var(∥∥∥φ(x)− φ(Sa)∥∥∥2) (37) From 33 to 35, we used Cauchy Schwarz inequality. From line 35 to line 37, we use the fact that 2ab ≤ a2 + b2 for all a, b ∈ R+. By applying Theorem 4, we have:
Var( ∥∥∥φ(x)− φ(Sb)∥∥∥2) = 2(1 + 1
k )2Tr(Σ2c) + 4(1 +
1 k )(µa − µb)TΣc(µa − µb)
Var( ∥∥∥φ(x)− φ(Sa)∥∥∥2) = 2(1 + 1
k )2Tr(Σ2c)
Finally, Ea,b[Var(α|a, b)] ≤ Ea,b[2Var( ∥∥∥φ(x)− φ(Sb)∥∥∥2) + 2Var(∥∥∥φ(x)− φ(Sa)∥∥∥2)]
= Ea,b[8(1 + 1
k )2Tr(Σ2c) + 8(1 +
1 k )(µa − µb)TΣc(µa − µb)]
= 8(1 + 1
k )Ea,b[Tr{(1 +
1 k )Σ2c + Σc(µa − µb)(µa − µb)T }]
= 8(1 + 1
k )Tr{Σc[(1 +
1 k )Σc + 2Σ]}
Extending to N class: Let x, y denote the query data pair, and the set of N classes be denoted as c. Let αi = ∥∥∥φ(x)− φ(Si)∥∥∥2 − ∥∥∥φ(x)− φ(Sy)∥∥∥2. Then we have a correct prediction ŷ = y if
∀i ∈ [1, N ], i 6= y, αi > 0 . Hence: R(φ) = Prc,x,S( ⋃N i=1 i 6=y αi > 0)
By Frechet’s inequality:
R(φ) ≥ N∑ i=1 i 6=y Pr(αi > 0)− (N − 2)
Noting that Theorem 3 can be applied to each term in the summation: R(φ) ≥ N∑ i=1 i 6=y 4Tr(Σ)2 8(1 + 1/k)2Tr(Σ2c) + 16(1 + 1/k)Tr(ΣΣc) + Ei,y[((µy − µi)(µy − µi)T )2] −(N−2)
It is then clear that the observations made on the binary case also applies to the multiclass case.
A.6 ADDITIONAL RESULTS
Additionally, we experimented with directly setting the output dimension of the embedding network to 60 by adding a fully connected layer to the embedding network. This variant of protonet performs worse than both the base variant and all other methods.
Table 2: Classification Accuracy on miniImageNet-5-way, with 4 layer CNN + 1 Fully connected layer embedding network.
TRAINING TESTING SHOTS AVERAGE MODEL SHOTS 1 2 3 4 5 6 7 8 9 10 ACCURACY PROTONET + FC 5 44.77 % 53.75 % 58.04 % 61.06 % 62.26 % 64.60 % 65.19 % 66.63 % 66.65 % 67.52 % 61.05 ± 0.28 %
Figure 3: Effect of hyperparameters on k-shot testing performance on miniImageNet.
Table 3: Classification Accuracy on miniImageNet-5-way, with 4 layer CNN embedding network.
TRAINING TESTING SHOTS AVERAGE MODEL SHOTS 1 2 3 4 5 6 7 8 9 10 ACCURACY VANILLA PROTONET 1 48.89 % 56.54 % 60.31 % 63.12 % 64.70 % 66.02 % 66.62 % 67.99 % 68.41 % 68.90 % 63.15 ± 0.21 % EST PROTONET 1 49.07 % 56.49 % 60.62 % 62.67 % 64.83 % 66.23 % 66.84 % 67.90 % 67.68 % 68.73 % 63.11 ± 0.22 % PCA PROTONET 1 49.01 % 56.35 % 60.07 % 62.42 % 64.38 % 65.28 % 66.56 % 67.81 % 67.59 % 68.26 % 62.77 ± 0.22 % VANILLA PROTONET 5 44.75 % 56.61 % 61.52 % 65.32 % 67.23 % 69.04 % 70.66 % 71.47 % 71.84 % 72.36 % 65.08 ± 0.23 % EST PROTONET 5 50.22 % 59.04 % 64.14 % 66.61 % 68.25 % 69.46 % 70.80 % 71.60 % 72.61 % 73.29 % 66.60 ± 0.23 % PCA PROTONET 5 48.72 % 58.43 % 63.17 % 66.07 % 68.63 % 69.56 % 70.55 % 71.21 % 72.09 % 72.82 % 66.12 ± 0.24 % VANILLA PROTONET 10 39.99 % 52.73 % 59.71 % 63.41 % 66.23 % 68.27 % 69.86 % 71.03 % 71.72 % 72.47 % 63.54 ± 0.25 % EST PROTONET 10 48.98 % 57.83 % 63.13 % 66.39 % 68.12 % 69.82 % 70.63 % 71.85 % 72.79 % 73.22 % 66.28 ± 0.23 % PCA PROTONET 10 48.04 % 57.05 % 62.46 % 64.63 % 67.61 % 68.98 % 69.71 % 71.78 % 71.75 % 72.42 % 65.44 ± 0.24 % VANILLA PROTONET 1-10 49.36 % 58.67 % 62.77 % 65.76 % 67.96 % 69.20 % 70.05 % 70.90 % 71.34 % 72.27 % 65.83 ± 0.21 %
Table 5: Classification Accuracy on Omniglot-20-way, with 4 layer CNN embedding network.
TESTING SHOTS MODEL TRAINING SHOTS 1 2 3 4 5 AVERAGE ACCURACY
VANILLA PROTONET 1 95.07 ± 0.17 % 97.89 ± 0.09 % 98.45 ± 0.08 % 98.75 ± 0.06 % 98.89 ± 0.06 % 97.81 ± 0.06 % VANILLA PROTONET 2 94.59 ± 0.18 % 97.69 ± 0.09 % 98.44 ± 0.07 % 98.69 ± 0.06 % 98.89 ± 0.06 % 97.66 ± 0.07 % VANILLA PROTONET 3 94.19 ± 0.18 % 97.57 ± 0.09 % 98.30 ± 0.07 % 98.63 ± 0.07 % 98.79 ± 0.06 % 97.50 ± 0.07 % VANILLA PROTONET 4 93.79 ± 0.18 % 97.41 ± 0.10 % 98.19 ± 0.08 % 98.54 ± 0.07 % 98.75 ± 0.06 % 97.34 ± 0.07 % VANILLA PROTONET 5 93.42 ± 0.18 % 97.34 ± 0.10 % 98.18 ± 0.07 % 98.53 ± 0.07 % 98.78 ± 0.05 % 97.25 ± 0.07 % MIXED-k SHOT 1-5 94.84 ± 0.17 % 97.81 ± 0.09 % 98.45 ± 0.07 % 98.70 ± 0.06 % 98.92 ± 0.54 % 97.74 ± 0.06 % PCA PROTONET 1 94.94 ± 0.16 % 97.81 ± 0.09 % 98.53 ± 0.07 % 98.79 ± 0.06 % 98.85 ± 0.06 % 97.78 ± 0.06 % EST PROTONET 1 95.11 ± 0.17 % 97.95 ± 0.09 % 98.46 ± 0.07 % 98.77 ± 0.06 % 98.84 ± 0.06 % 97.83 ± 0.06 %
Table 6: Classification Accuracy on miniImageNet-5-way, with 7 layer ResNet embedding network.
TRAINING TESTING SHOTS AVERAGE MODEL SHOTS 1 2 3 4 5 6 7 8 9 10 ACCURACY VANILLA PROTONET 1 52.65 % 60.46 % 64.18 % 66.83 % 68.27 % 69.23 % 70.19 % 71.37 % 71.83 % 72.29 % 66.73 ± 0.20 % EST PROTONET 1 52.56 % 60.63 % 64.50 % 66.53 % 68.33 % 69.36 % 70.04 % 71.21 % 71.37 % 71.60 % 66.61 ± 0.22 % PCA PROTONET 1 52.78 % 60.35 % 64.05 % 66.24 % 67.51 % 69.64 % 69.85 % 71.13 % 71.88 % 71.79 % 66.52 ± 0.22 % VANILLA PROTONET 5 47.40 % 58.23 % 64.60 % 67.52 % 69.93 % 71.05 % 72.27 % 72.90 % 73.55 % 74.35 % 67.18 ± 0.23 % EST PROTONET 5 51.93 % 60.70 % 65.33 % 68.06 % 69.98 % 71.26 % 72.33 % 73.46 % 74.03 % 74.80 % 68.19 ± 0.23 % PCA PROTONET 5 50.90 % 60.38 % 64.66 % 67.23 % 69.25 % 71.30 % 71.72 % 72.75 % 73.84 % 74.24 % 67.63 ± 0.23 % VANILLA PROTONET 10 42.20 % 55.98 % 61.67 % 66.08 % 68.23 % 69.95 % 72.20 % 72.56 % 74.04 % 74.54 % 65.75 ± 0.25 % EST PROTONET 10 51.24 % 60.46 % 65.11 % 67.63 % 70.06 % 71.07 % 72.55 % 73.39 % 73.85 % 74.69 % 68.00 ± 0.23 % PCA PROTONET 10 50.52 % 59.20 % 64.44 % 66.86 % 69.36 % 71.00 % 71.73 % 73.19 % 73.73 % 73.82 % 67.38 ± 0.23 % VANILLA PROTONET 1-10 51.74 % 60.10 % 65.13 % 67.12 % 69.09 % 70.53 % 71.57 % 72.22 % 72.99 % 73.63 % 67.41 ± 0.21 %
Table 7: Classification Accuracy on tieredImageNet-5-way, with 7 layer ResNet embedding network.
TRAINING TESTING SHOTS AVERAGE MODEL SHOTS 1 2 3 4 5 6 7 8 9 10 ACCURACY VANILLA PROTONET 1 49.78 % 57.67 % 61.37 % 64.88 % 65.17 % 66.73 % 67.53 % 68.58 % 68.21 % 69.88 % 63.98 ± 0.29 % EST PROTONET 1 51.19 % 57.61 % 61.85 % 64.43 % 65.48 % 67.64 % 67.69 % 67.76 % 68.51 % 68.20 % 64.04 ± 0.30 % PCA PROTONET 1 51.38 % 57.89 % 61.68 % 64.32 % 65.96 % 66.15 % 66.83 % 68.00 % 68.58 % 68.77 % 63.95 ± 0.30 % VANILLA PROTONET 5 47.88 % 58.70 % 63.95 % 66.58 % 69.12 % 71.69 % 71.95 % 73.15 % 73.11 % 73.80 % 66.99 ± 0.31 % EST PROTONET 5 53.05 % 61.13 % 65.67 % 68.07 % 69.30 % 71.47 % 71.59 % 72.42 % 72.80 % 73.63 % 67.91 ± 0.31 % PCA PROTONET 5 51.21 % 59.86 % 63.91 % 66.92 % 68.88 % 70.38 % 71.48 % 72.77 % 73.81 % 72.17 % 67.14 ± 0.32 % VANILLA PROTONET 10 40.84 % 56.24 % 62.10 % 66.28 % 69.37 % 71.43 % 72.09 % 72.91 % 73.56 % 74.72 % 65.95 ± 0.35 % EST PROTONET 10 50.45 % 60.41 % 65.19 % 68.46 % 69.55 % 70.87 % 72.07 % 72.66 % 73.78 % 74.79 % 67.82 ± 0.32 % PCA PROTONET 10 50.18 % 59.59 % 64.24 % 67.43 % 69.52 % 70.65 % 71.78 % 72.10 % 72.78 % 73.65 % 67.19 ± 0.31 % VANILLA PROTONET 1-10 50.74 % 60.03 % 64.17 % 67.26 % 69.28 % 69.56 % 71.07 % 72.41 % 71.99 % 73.01 % 66.95 ± 0.29 %

Review summaries:
The author performs theoretical analysis of the number-of-shot problem in the case study of prototypical network which is a typical method in few-shot learning. To facilitate analysis, the paper assumes 2-way classification (binary classification) and equal covariance for all classes in the embedding space, and finally derives the lower bound of the expected accuracy with respect to the shot number k. The final formula of the lower bounding indicates that increasing k will decrease the sensitivity of this lower bound to Σc (expected intra-class variance), and increase its sensitivity to Σ (variance of class means). To reduce the meta-overfitting (when training are test shot are the same, the performance becomes better), the author designed Embedding Space Transformation (EST) to minimize Σc and maximize Σ through a transformation that lies in the space of non-dominant eigenvectors of Σc while also being aligned to the dominant eigenvectors of Σ. The experimental results on 3 commonly used datasets for few-shot learning, i.e. Omniglot, Mini-ImageNet and Tiered-ImageNet demonstrate promising results and desired properties of the method.