A Theoretical Analysis of the Number of Shots in Few-Shot Learning
Authors: Tianshi Cao
Marc T Law
Sanja Fidler
Venue:  (2020)
Keywords: Few shot learning
Meta Learning
Performance Bounds

Abstract: Few-shot classification is the task of predicting the category of an example from a set of 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 meta-learning, 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.

Published as a conference paper at ICLR 2020
A THEORETICAL ANALYSIS OF THE NUMBER OF SHOTS IN FEW-SHOT LEARNING
Tianshi Caol Mare T. Law!.2.3 Sanja Fidler
1 Department of Computer Science, University of Toronto
2 Vector Institute
3 NVIDIA
{jcao, law, fidler didler/@cs.torronto.em toronto..duu
ABSTRACT
Few-shot classification is the task of predicting the category of an example from few labeled examples. The number labeled examples per category called the number of shots (or shot number). Recent works tackle this task through meta- learning, where a meta-leamer 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 meta-test time. Generally, the shot number used in meta-training should match the one used in meta- meta-testing to obtain the best performance. We introduce thcoretical analysis of the impact of the shot number Prototypical Networks, a state-of-the--e few-shot classification method. From our analysis, we propose simple method that is robust the choice of shot number used during meta-training, which is a crucial hyperparameter. The performance of our model trained for 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.
INTRODUCTION
Human cognition has the impressive ability of grasping new concepts from exposure to 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-efficinncy gap between deep learning and human learning in fields such as computer vision, reinforeement learning and speech recognition (Santoro et al.. 2016 Ravi & Larochelle| 2017] Finn et al. [2077] Vinyals et al., 2016: Wang et al. (2019)). These methods fall under the framework of mneta-learnnng 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, task is drawn from some population and limited amount of support and query data from that task is made available. The meta- heta-leamer 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 phase called meta- meta-testing) also carried out in episodes in similar fashion, except that the meta-learner is no longer updated and the performance 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 the task-specific learner as the danger of overfitting is high. contrast, support data is expected to be abundant, then the meta-leamner can provide generally more relaxed biases the task-specific learner to achieve better fitting the task

---

Published as a conference paper at ICLR 2020
data. Therefore it is plausible that meta- meta-leamer trained with one k value can be suboptimal at adapting to tasks with a different & value and thus exhibit meta-overfitinng to k. In experiments, 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 Prototypical networks (Snell 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 and N. However, ProtoNet exhibits performance degradation when the & used in training does not match the used in testing.' First, we will undertake a theoretical investigation lower bound of expected performance, as well to the intrinsic
elicit the connection from 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 cases. Our contributions are threefold:
We provide performance bounds for ProtoNets given embedding function. From which, argue that & 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 new method that improves upon vanilla ProtoNets by eliminating the performance degradation in cases where the 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.
2 BACKGROUND
2.1 PROBLEM SETUP
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 T, N classes с = {ci, CN are sampled i.i.d. from to form N-way classification problem. For each class c; l support data are sampled from
class-conditional distribution S; {aXi,.., . sid ~ (x) = c;). where x E RP, 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 label "cat" will always have the label "cat"), in contrast to y defined below.
Additionally, the set Q = (xx1,.... & D P. For each x, let y E {1, N) denote its label in the context of the few-shot classification task. Define S, = f(x),,/ = i),. (xxx, U/ = +)} as the augmented set of supports for class and denote the union of support sets for N classes as S = U S, The few-shot classification task is to predict y for each x in Q given S. During meta- meeaattaininn,, the ground truth label for Q is also available to the learner.
x containing query data is sampled from the joint distribution
2.2 META-LEARNING SETUP
Meta-learning approaches train on a distribution of tasks to obtain information that generalizes to unseen tasks. For few-shot classification, task is determined by which classes involved in the N-way classification task. During meta-training, the meta-learner observes episodes of few-shot classification tasks consisting of N classes, & labelled samples per class, and unlabelled samples, as previously described. The collection of all classes observed during meta-training forms the meta- training split D,,
Critically, we assume that every unseen class that the learner evaluated upon (during meta-testing) is also drawn from the same distribution
For example, 1-shot accuracy a 10-shot trained network performs 9% (ahsolute) worse than 1-shot trained network
We assume equal likelihood of drawing from each class for simplicity
2

---

Published as a conference paper at ICLR 2020
2.3 PROTOTYPICAL NETWORKS
ProtoNets (Snell et al. 2017 compute E-dimensional embeddings for all samples in S and Q. The embedding function @ R- R is usually deep network. The prototype representation for each class formed by averaging the embeddings for all supports of said class: ((S)) = 2े2 Exes, d(x). Classification of any input (e.g. x Q) is performed by computing the softmax over squared Euclidean distances of the imput point's embedding to the prototypes. Let ý denote the prediction of the classifier for one of the categories j E {1,- N}:
((5))1
Po = j(
where
l|vl
Σ - -(s))
d=1
The parameters of the embedding functions are learned through meta-training. Negative log-likelihowe ( = log (p(ū = y y)x)) of the correct class is minimized on the query points through SGD.
As explained (Law al., 2019), ProtoNets can be seen as metrie 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 E We propose in this paper a subsequent metric learning step which learns linear transformation that maximizes inter-to-intes class variance ratio.
3 PROPOSED METHOD
We first present theoretical results explaining the effect 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 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- veta-training phase). With / denoting the indicator function, we define the expected accuracy R as:
R(Ø)= = E.EEs.x. Jarg max (p = j|x, =
(2)
Throughout this section, we will use the following symbols to denote the means and variances of embeddings under different expectations:
Definitions:
Ex(o(x) (x)) = cl E.
De Ex[(o(x) (.)()()) - - l
E.
=H)
Remark. H. is the expectation of the embedding conditioned class is the (full) expectation of the embedding, which can be expressed as the expectation of H. over classes. 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. Eg is the expected intra-class variance 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 equivalent to a mixture density estimation on the support set with spherical Gaussian densities (Snell et al.) 2017). Specifically, adopt the modelling assumptions that the distribution of Φ(x) given any class assignment is normally distributed (o(o())(((s = c) = (u,, Ee)). with equal covariance for all classes in the embedding space (v(c, c'), -
We present the analysis for the special of episodes with binary classification (i.e. with N = 2) for ease of presentation, but the conclusion can be generalized to arbitrary > 2 (see appendix).
"The second assumption is more general than the one used in the original paper we do not require Σ, to be diagonal
3

---

Published as a conference paper at ICLR 2020
assume equal likelihood between the classes. We would like to emphasize that the assignment of labels can be permuted freely and the classifier's s prediction would not be affected due symmetry. Hence, only need to consider one case for the ground truth label without loss of generality. Let a and denote any pair classes sampled from т. Let x be drawn from a, and overload and b to also indicate the ground truth label in the context of that episode, then equation 2 can be written as:
Also, noted in Section 2.1
R( Ex.
(3)
Additionally, noting that p(ğ a) can be expressed as a sigmoid function a:
10(x)
p(ū = a|x) - -[16(())0((s)) (6-11((x)0(())
o((((xx) - ((S))
- | - ((Saa
(aa)
where a - [(xx) o(Sb)
- -|((()) )(S.)
We express equation probability:
R(ő)
Pr a.b.x.5
(9 =
Pr (a> a,b.x,8
(4)
We will introduce a few auxiliary results before stating the main result for this section.
Proposition 1. From the one-sided Chebyshev's 's inequality, it immediately follows that:
B[a]²
R( = Pr(a > 0) Var(a) + B[a]²
(5)
we derive the expectation and variance of a when conditioned on the classes sampled in episode. Then, in Theorem we compose them into the RIIS of Proposition 1 through law of total expectation.
In Lemma D and Lemma 2
Lemma 1, Consider space of classes O' with sampling distribution T, a, sid т. Let {Sa, S S. (ox1,.... S₁ {,x1,... {x k E N is the shot number, and Yx)) Define (SS)) Nt Exes, 6(x) and ((Sb) A R. Exes, d(x). Consider E as defined earlier. Assume p(o(x)) (x) c) =N(H Me) and Ee Ee' for any choice of c, E C, then,
Ex,Sta,t(al = (m,- - m²))² (H, (16)
andd
Ea,. = 2Tr(E).
Lemma 2. Under the same notation and assumptions as Lemmal 7 additionally invoking defiitiin for E., then,
1 1 + 2x2) (aar(aa b)] < 8(1 + yT Ex((1 +
(6)
The proof' of the above lemmas are the appendix. With the results above, we are ready to state our main theoretical result in this section.
Theorem 3. Under the conditions where Lemmal 7 aadd2 hold, we have:
4Tr(E)²
R(Φ)= 2 8(1 101+1/A)T((33)+ 1661
(/2)) 1/ + En,,(((H, 1² 11)))
Proof. First, we use decompose the Var(a) term in Proposition 1 by Law of Total Expectation.
Var(a) E,,,, [aa] Fn..x..saa En, Ex. E |a, ss,,
(8)
E., [ar((a a. + Ex,s/ala, b] Eo,xx.
(9)
Hence, Proposition 1 can also be expressed
E[a}²
R(d) Ea (..[Vaa(aaa,, b) + Ex, |a]a, b
(10)
Finally, arrive at Theorem 3 by plugging Lemma and 2 into equation T0
4

---

Published as a conference paper at ICLR 2020
Several observations can be made from Theorem
The shot number & 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 constant), is clear that increasing will decrease the sensitivity (magnitude partial derivative) of this lower bound to Eg, and increase its sensitivity to E.
3. If one postulates that meta- veta-lcarning updates on ø are similar to gradient ascent on this accuracy lower bound, then learning with smaller k emphasizes minimizing noise, while learning with higher emphasizes maximizing signal.
In conclusion, these observations give plausible reason for the performance degradation observed in mismatched shots: when an embedding function has been optimized (trained) for ktrain > keest, the relatively high E. is amplified by the now smaller k, resulting degraded performance. Conversely. an embedding function trained for kerein < keest already has small Σe, such that increasing during testing has further diminished improvement on performance.
3.2 INTERPRETATION IN TERMS OF VC DIMENSION
In any given episode, a nearest neighbour prediction is performed from the support data (with 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 - 6, the following inequality on the difference between empirical error elTtrain (of the support samples) and true error erftrae holds for any classifier h:
D(n
4k D + 1) + In
erTtrue (h) erTtrain (h)
(1I)
2k
Where D is the VC dimension, and is the number of support samples per class 4, Under this binary classification setting, the predictions of prototypical network are equal to (aa)) as shown earlier. Denoting (S.) and z o(Se),
manipulate as follows:
a = [ zell [1x(x)
le = =2( - 2z)² o(x) + (z. zz.
(12)
From equation 12, the prototypes form a linear classifier with offset the embedding space. The VC dimension of this type of classifier is + d where d is the intrinsic dimension of the embedding space (Vapnik 1998).
ProtoNets, the intrinsic dimension of the embedding space not only influenced by network architecture, but more importantly determined by the parameter themselves, making a learned property. For example, if the embedding function can be represented with a linear transformation d(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 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.
3.3 RECONCILING SHOT DISCREPANCY THRROUGHI EMBEDDING SPACE TRANSFORMATION
Observations in Section 3.2 reveal that an ideal 6 would have an output space whose intrinsic dimension d is as small as possible minimize the right-hand side of equation I1 but just large enough to allow low eTTinain: the balance between the two objectives is dictated by k. Similarly, observations in Section 3.1 suggest that an ideal é would balance between minimizing E. and maximizing Σ also according to k. As a result, when there is discrepancy between meta-training shots and meta-testing shots". accuracy meta-test time will suffer. A naive solution is prepare
"This considers learning of a single episode through the formation of prototypes 'In deployment, the number of support samples per class likely random from episode episode.
5

---

Published as a conference paper at ICLR 2020
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, want to train and store a single model, and then adapt the embedding function's variance characteristics and the embedding space dimensionality achieve good performance for any test shot.
Linear Discriminant Analysis (LDA) is a dimensionality reduction method suited for downstream classification (Fukunaga [990). Its goal is 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 S where Sp the covariance matrix of prototypes and S is the class-conditional covariance matrix. In practice, Sy and S cannot be stably estimated in few-shot episodes, preventing the direct application of L.D..
We propose 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 8 This is a different goal from LDA because 3 demonstrates that the expected performance across many episodes can be improved by maximizing Σ and minimizing Σg. Similar to LDA, EST works by applying linear transformation
(xx + V (ő(())
(13)
to the outputs of the embedding function. Here, V is a linear transformation computed using Der after meta-training has completed. To compute V*, we first iterate through all classes in Dty and compute their in-class means and covariance matrices in the embedding space. We can then find the covariance of means En. and the mean of covariances Σ, across Der- Finally, V is computed by taking the leading eigenvectors of Σn ph,, the difference between the covariance matrix of the mean and the mean covariance matrix with weight parameter p. The exact procedure for computing V* is presented in the appendix.
4 EXPERIMENTS AND RESULTS
In this section, our first two experiments aim at supporting theoretical results in Sections 3.] 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.. 2017h) 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 riered (Ren et al. 2018). We followed standard data processing procedures which are detailed in the appendix.
4.1 TRAINING SHOTS AFFECT VARIANCE CONTRIBUTION
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] [[Var(x[c]] + Var(IE(x = E[E,] + ), 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 miniImageNeet and tiered imagenet, 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 I 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.
on Omniglot) until convergence with random

---

Published as a conference paper at ICLR 2020
130
omnigiac ChN Ornrigis Rhoifed
min Imagene:. CAN
2.43
Bered: magenst, CNN
0.00
Beeed: maguost, Reshert
13
6:33
Interclass aatrasintaaassss
0:2
0.29
0:3
14
training shots
tre traininn shots
Figure 1: IIteer-llass Intra-class variance ratios of embedding space varies with &s used in training.
Left: Omniglot. Right: minilmageNeet and tieredImageNet.
4.2 TRAINING SHOTS AFFECT INTRINSIC DIMENSION
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 IR_ (Bishop 2006). A simple method for estimating d through principal component analysis (PCA) of the embedded data set. By eigendecomposing the covariance matrix of embeddings, 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 ra - Eie[,.g A ΣiE(1, [) A;- In our experiments, we set the threshold for тa 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 eigendeconposition is performed. The approximate id is plotted for various values of k in Figure 2 trend that as we increase training shot, the id of the embedding space increases.
We can see clear
Omniglor.
120
1279
Approx te ID. Resfett
maggnet
Approxemate ID. CNN
Approximate
122
230
training shots
# training shots
Figure Intrinsic dimension approximated by the number of significant eigenvalues varies with l: used in training. Left: Omniglot. Right: minilmageNet and tieredlmageNet
4.3 EXPERIMENTS WITH EST
We evaluate the performance of EST on the three aforementioned data sets. The performance is compared against our implementation of vanilla ProtoNets as baseline, as well variant of ProtoNets using principal components obtained from all embedding points (ProtoNet-PCAA.
All methods in this section use the same set of trained ProtoNets. As with before, networks are trained with & E [1....,5] 5} on Omniglot and k E (1,..., 10] on minilmageNet and fieredImageNet. Additionally, ing a value for & within the specified range for each episode, and then sampling the corresponding number of support samples. Hyper-parrmeetes for training described in the appendix.
also trained mixed-shot network for each data set. This is done by randomly select-
7

---

Published as a conference paper at ICLR 2020
Table I: Classification accuracies of ProtoNet variants. Best performing methods and any other runs within 95% confidence margin is in bold
(a) Ommiglot-20-way, with layer CNN.
(b) Omniglot-20-wayy with layer ResNet.
TRAINING SHOTS
TESTING SHOTS
AVERAGE ACCURACY
TRAINING SHOTS
TESTING SHOTS
AVERAGE
Monea
5
MonEI
ACCURACY
VANILA PROTONET
I
95.07 %
98.89 56
97.81 5
VANILLA PROTONET
96.46
99.07 %
98.35 %
V NET
93.42 %%
97.25 %
VANILLA PROTONET
42
98.99 %
97.75
1-5
97.74
MIXED-& PROTONET
PCA PROTONET
94.94 9
98.85 56
97.78 %
PCA PROTONET
96.02
98.99 36
98.19
EST PROTONET
1
95.11 9
98.84 56
97.83 %
EST PROTONET
95.55 %
99.02 %
98.19 %
(c) minilmageNet-S-way with 4 layer CNN.
(d) mindImageNet-S-wag with 7 layer ResNet.
TRAINING SHots
TESTING SHOTTS
AVERAGE ADCURACY
TRAINING
TESTING SHOTS
AVERAGE
MoDeL
10
MOURL
SHOTS
10
ACCUKACY
PHoTONez
48.39
64.70 %
68.90 56
63.15 %
PactoNar
$2.653 1
68.27 %
72.29
66.73 %
PROTONEz
44.25
67.23 %
72.36 %6
65.08 %
PacroNar
5
47.00 36
69.93 %
74.35
67.18 %
PROTONEz
10
19:99
65.23 %
72.47% 56
63.54 %
PscroNar
10
42:20
68.25 %
74.54 5
65. 05.75:0 %
Mixep-e SHor
1-10
49.10 9
67.96 96965 %
22.27% 5g
65.83% %
MIXEn-E Swor
1-10
51.74 96
69. 09.09:0 %
73. 63
67:68 %
PCA PROTONEs
49.36 9
68.63 %
71.82% 55
66.12 %
PCA ParmnNr
5
50.00 06
69.25 96
74.34 9
67.65 %
EST PRotoNer
50.22% %
68.25 %
73.29%
66.60 %
EST PRoroNer
5
51.93%
69.98 %
74.80 %
68.19 %
(c) Sire with layer CNN.
(l) fieredmageNett--wayy with layer ResNet.
TRAINING Smors
TESTING SHOrT
AVERAGE ACCURACY
TRAINING
TISTING SHOTS
AVERAGE
MoreL
10
Moom
SmOrrs
5
10
ACCURACY
PROTONET
47.37
63.70 %
67.99% 55
61.85 %
PaoTONeT
I
49.78% 96
65:17
69. 03.88
63.
PROTONET
42.33
66.51 %
71.85% 55
64.05 %
PRoTONar
5.
47.88
69.12
73. 10.30-
66. 66.99-0
PROTONET
10
35.38
64.56 %
71.03 95
61.24 %
PaorTNNT
10
40.86
69.37
74.72
65
Mixen-A Smor
1-10
47.67%
66.34 %
70.96 96.
64.33 %
MIxED & Snow
1:10
50.74
69.28
73.01
66.95
PCA PRoFONET
48.34
67.07 %
71.65% %
64.96 %
PCA PRoroNer
5
51.21 96
08.38
72.17
67.14
EST PROIoNeT
48.88
67.24%
71.09% %
68.46 %
PROTONET
5
$3.05 96
69.30
73.63 %
67.91 %
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 evaluate the k-shot performance (k E 5l. Each 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, minilmageNeet and fieredImageNet, 10 test runs performed with support per sample & E [1, 10), 600 episodes per run, and 15 query samples in each episode.
Model configuration: Vanilla ProtoNet used as our baseline. We present the performance of multiple ProtoNets trained with different shots to illustrate the performance degradation issue. ProtoNer-PPA uses principal components of the training split embeddings in place of V*, with com- ponents other than the d leading ones zeroed out. We carry out a parameter sweep on minilmageNee and set 60; the same value 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: p. d, and training shots of the embedding network. For our experiments, For selecting the number of training shots, we use the same strategy as before by evaluating ProtoNet- EST with all trained embedding networks and found the same trend hold. As an abalation study, FC-ProtoNe adds a fully connected layer to the embedding network such that the output dimension also 60. Results of this variant can be found in the appendix.
set p 0.001 and d 60 based on performance minilmageNet.
EST performance results: Table | summarizes the performance of the evaluated methods on all data sets. Due to space constraints, only I-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 riere/ImageNeet, EST-ProtoNet significantly outperforms baseline methods and ICA-protonel 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. PrST provides minor improvements best- pesfforrfomin baseline method under most test shots settings. We hypothesize that this is due to EST aligning the embedding space the directions with high inter-class variance and low intra-class
the
8

---

Published as a conference paper at ICLR 2020
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 the more challenging data sets when evaluated with various test shots. 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.
RELATED WORK
We summarize related work on extensions of ProtoNets, on improving the few-shot classification setup, and on analyzing theoretical properties of meta-lcarning 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 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 minilmageNeet can perform 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 benchmark composed of data from various domains; methods 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. WWan et al. (2019b) provide unifying formulation for few-shot learning methods, and clearly outline the key challenge in few-shot learning through 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 's output space varies with the number of shots To the best of our knowledge, Ammt & Meir (0177) provide the only prior work to bound the error of meta-learning agent. Specifically, they 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 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- con-aaraettri methods such as ProtoNets because the hypothesis class in ProtoNets can change from episode to episode depending on the number of ways.
direct consequence of the challenges outlined in the PAC argument.
6 CONCLUSION AND FUTURE WORK
We have explored how the number of support samples used during meta-training can influence the learned embedding function's '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 2019) with an embedding learning component. We believe approach is significant
step to reduce the impact of the shot number in meta-traine meta-training, which is a crucial hyperparameter for few-shot classification.

---

Published as a conference paper at ICLR 2020
ACKNOWLEDGMENTS
We acknowledge partial support from NSERC COHESA NETGP485577-15 and Samsung. We thank Chaoqi Wang for discussion on the initial idea, and Clément Fuji Tsang, Mark Brophy and the anonymous reviewers for helpful feedback on early versions of this paper.
REFERENCES
Kelsey R. Allen, Evan Shelhamer, Hamul Shin, and Joshua B. Tenenbaum, Infinite mixture prototypes for few-shot learning. CoRR, 1bs//1902.0455,, 2019. /LRp::t/://rx wwtp:///ggaabaa/aa/ee 04552
Ron Amit and Ron Meir. Meta-learning by adjusting priors based on extended pac-bayes theory. In ICML, 2017.
Christopher M. Bishop. Pattern Recognition and Machine Learning (Information Science and Statistics). Springer-Verlag, Verlag, Berlin, Heidelberg, 2006. ISBN 0387310738.
Wei- Yu Chen, Yen-Cheng Liu, Zsolt Kira, Yu-Chiang Frank Wang, and Jia-Bin Huang. closer look at few-shot classification. ArXiv, abs/1904.0420 2019.
Nanqing Dong and Eric Xing. Few-shot semantic segmentation with prototype learning. British Machine Vision Conference (BMVC), 2018.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta- weaanne for fast adaptation of deep networks. In Doina Precup and Yee Whye Teh (eds.). Proceedings of the 34th International Conference on Machine Learning (ICML), volume 70 of Proceedings of Machine Learning Research, pp. 1126-1135, International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR. URL http:::ppproceeeengaaa mir. http:///ii.............r////a//a
Keinosuke Fukunaga. Introduction to Statistical Pattern Recognition (2Nd Ed.). Academic Press Professional, Inc., San Diego, CA, USA, 1990. ISBN 0-12-269851-7.
Keinosuke Fukunaga and David R. Olsen. An algorithm for finding intrinsic dimensionality of data. IEEE Transactions on Computers, C-20:176-183, 1971.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition (CVPR), pp. 770-778, 2016.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. Francis Bach and David Blei (eds.), Proceedings of the 32nd International Conference Machine Learning (ICML), volume 37 of Proceedings
of Machine Learning Research, pp. 448 456, Lille, France, 07-09 Jul 2015. PMLR. URL http://proceedingg .llr...........m......mm... prwss / htt/:ooffel..... html
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations (ICLR), 2014.
Brenden M. Lake, Ruslan Salakhutdinov, and Joshua Tenenbaum. Human-level concept learn- ing through probabilistic program induction. Science, 35066266) 2015. ISSN 0036-8075. doi: 10. 1126/sccence.uua30551 Contentt/30/626///
URL httt::t//ciieneeee www.ncemag.ccooommm org/
Mare T. Law, Yaoliang Yu, Matthieu Cord, and Eric P. Xing. Closed-form training of mahalanobis distance for supervised clustering. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 3909-3917, 2016.
Marc Law, Jake Snell, Amir massoud Farahmand, Raquel Urtasun, and Richard Zemel. Di- mensionality reduction for representing the knowledge of probabilistic models. In International Conference on Learning Representations (ICLR), 2019. URL https:/: htttt:::////peeeeieee wwwp//eeeeeeee.eeeooee net/
forumm forum??d==Syp--hccFF
10

---

Published as a conference paper at ICLR 2020
Boris Oreshkin, Pau Rodríguez López, and Alexandre Lacoste. Tadam: Task dependent adaptive metric for improved few-shot learning. In Advances in Neural Information Processing Systems (NeurlPS), pp. 721-731, 2018.
Sachin Ravi and Hugo Larochelle. Optimization model for few-shot learning. In In International Conference on Learning Representations (ICLR), 2017.
Mengye Ren, Eleni Triantafillou, Sachin Ravi, Jake Snell, Kevin Swersky, Joshua B. Tenenbaum, Hugo Larochelle, and Richard S. Zemel. Meta-learning for semi- sumi-sseeeiseed few-shot classification. In Proceedings of 6th International Conference on Learning Representations (ICLR), 2018.
Alvin C. Rencher and G. Bruce Schaalje. Linear Models in Statistics. John Wiley & Sons, Inc., 2nd edition, 2008.
Andrei A. Rusu, Dushyant Rao, Jakub Sygnowski, Oriol Vinyals, Razvan Pascanu, Simon Osindero, and Raia Hadsell. Meta-learning with latent embedding optimization. CoRR, abs/ hos//887..00 05960, 2019.
Adam Santoro, Sergey Bartunov, Matthew Botvinick, Daan Wierstra, and Timothy Lillicrap. Meta- learning with memory-auggennt neural networks. In Maria Florina Balcan and Kilian Q. Wein- berger (eds.), Proceedings of The 33rd International Conference on Machine Learning (ICML), volume 48 of Proceedings of Machine Learning Research, pp. 1842-1850, New York, New York, USA, 20-22 Jun 2016. PMLR. URL http::/procecccngg wtt.:/iss......r../eeeeeeeee
santoro16 html
Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning. In Advances in Neural Information Processing Systems (NIPS), pp. 4077-4087, 2017.
Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. In Computer Vision and Pattern Recognition (CVPR). 2015.
org/abs 1409. 4842
Makarand Tapaswi, Mare T. Law, and Sanja Fidler. Video face clustering with unknown number of clusters. In The IEEE International Conference on Computer Vision (ICCV), October 2019.
Eleni Triantafillou, Tyler Zhu, Vincent Dumoulin, Pascal Lamblin, Utku Evei, Kelvin Xu, Ross Goroshin, Carles Gelada, Kevin Swersky, Pierre-Antoine Manzagol, and Hugo Larochelle. Meta- dataset: dataset of datasets for learning to learn from few examples. International Conference Learming Representations, 2020.
Vladimir Vapnik, Esther Levin, and Yann Le Cun. Measuring the vc-dimension of learning machine. Neural Computation, 6(5):851-876 1994. doi: 10. 1661neo/oo 1994.6.5.811. URL
www.rr/.0.... https::/doi http///doo.oo///////// (errg/..1112//eeee 11w.11122nncccoo 1994. 6.5.95. 955
Vladimir N. Vapnik. Statistical Machine Learning. JOHN WILEY & SONS, INC., 1998.
Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Koray Kavukcuoglu, and Daan Wierstra. Match- ing networks for shot learning. In Proceedings of the 30th International Conference Neural Information Processing Systems (NIPS), NIPS' 16, pp. 3637-3645, USA, 2016. Curran Associates Inc. ISBN 978-1-5108-3881-9 URL http: / acm. wwt////gaatttooooo eegg/iitaion ffm
id-3157382.3155 3157500
Jixuan Wang. Kuan-Chich Wang, Mare T. Law, Frank Rudzicz, and Michael Brudno. Centroid-basee deep metric learning for speaker recognition. In ICASSP 2019-2019 JEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3652-3656. IEEE, 2019a
Yaqing Wang. Quamming Yao, James T. Kwok, and Lionel M. Ni. Generalizing from a few examples: A survey on few-shot learning. 2019b.
Han-Jia Ye, Hexiang Hu, De-Chuan Zhan, and Fei Sha. Learning embedding adaptation for few-shot learning. CoRR, abs/1812.036644, 2018. URL http: hhttt://aaxivv org/ abs htab///81// 1812. 63664
Pierre Yger, Marcel Stimberg, and Romain Brette. Fast learning with weak synaptic plasticity.
Journal of Neuroscience, 35(39) 2015. ISSN 0270-6474, doi: 10. 10.1123//NEUROSCC
0607-15.200 URL http///////////////ooooooooootor

---

Published as a conference paper at ICLR 2020
A APPENDIX
A.1 ALGORITHM FOR EST
Below is the exact procedure for computing T for embedding space transformation.
Algorithm Algorithm for computing the transformation T.
Ln is the number of samples belonging class n: Ma, and Σn the mean and covariance of the embeddings of that class, frT and E, are the average of mean embeddings and covariances; En is the covariance of the mean embeddings; V is the matrix of eigenvectors that correspoinds to the d largest eigenvalues in A.
Input: Training set Der = {(x1, Vi). (XM, y.s where E NJ, D, denotes the subset of Dr, where Vy E Da, y n, embedding function é weighting parameter p. dimension parameter d.
Output: Transformation T.
Initialize μ = [0] Σ = [0).0
for n = to N do
p|n] Pn - (Xx,)ED, d(x,)
Σ[n] = J Exx,,i)DD (0(x;) - (o(x)) -Ma)
end for
PT Σ (X..))DD ((x:)
Σ. a = EmE(L.N) (H[n) pT (M[[]]] HT)
E, N EnE[INN] Σ[n]
Find V, such that: En -pp VAVT
V = [v,] for j E top d of
T(z) (2)
A.2 NETWORK ARCHITECTURE
The vanilla CNN has the exact same architecture as the original ProtoNet (Snell al. 2017). consists of four convolution layers with depth of 64; each convolution layer is followed by Relu activation, max-pooling, and batch normalization (loffe & Szegedy 2015). Resnet of layers is constructed with one vanilla convolution layer of depth 64 followed by three residual blocks, all joined by max- max-pooling layers; each residual block consists of two sets of Nony-batchnorm-Bee layers, of depth 128-256-256.
A.3 DATA SET DESCRIPTION AND PRE- PRE-PROCESSING
Experiments are performed on three data sets: Omniglot (Lake et al. 2015), minilmageNet (Vinyals) al. (016)) and rieredImageNet (Ren et al. 2018 For Omniglot experiments, we follow the same conliguration as in the original paper where 100 classes augmented with rotations (4800 total) are used for training, and the remaining classes are used for testing.
For minilmageNeet 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 minilmageNee images to 84x84. No data augmentation is applied. As most state-of-art few-shot classification methods achieve saturating accuracies on Omniglot, and minilmageNet's small number of classes make claims about generalization difficult, also conduct experiments of tieredImageNet.
TieredImageNet is also subset of Imagenet TieredImageNet groups classes into broader categories corresponding to higher-level nodes in the ImageNet hierarchy. includes 34 categories, with each category containing between 10 and 30 classes. These are split into 20 training, 6 validation and testing categories. In total, there are 351 classes in training, 97 in validation, and 160 in testing. Preprocessing of images follow the same steps used for minilmgeeNet.
12

---

Published as a conference paper at ICLR 2020
A.4 PROTONET TRAINING
Training procedure of ProtoNets largely mirrors the protocol used by Snell et al. (0117). On Omniglot, train the network convergence after 30000 episodes. On minil and mageee, we monitor the performance of the network on the validation set and select the best performing checkpoint after training for 50000 episodes. Adam (Kingma & Bal 2014) optimizer is used with = 0.9, _ = 0.999, = 10 10 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 minilmageNet and fieredlmageNet, we train with 20 classes and 15 query points per episode.
A.5 DERIVATION DETAILS
Proof of Lemmal)
Proof. First, from the definition of a, we split Sx, [[x] in two parts and examine them separately:
Ex [x [0|(((x) (Sa)) Ei||o o(S.)
(14)
In general, for random vector X, the expectation of the quadratic form is x Tr(Var(X))
+
E[X]" Hence,
i = Ex,s a. a
(0x)) o(xx
- [(S) |
(15)
-T o(x) -(x))))(s)) Blo(x) - ((S))) - ((S)).,
(16)
where the first term inside the trace can be expanded as:
Σ
=0(x)-((5) Varlø(x) - ((S6)
(17)
= =][(o(x)
((5)))) - (H, (1) - -Mb)²
(18)
Ee + HaHt 1 D. HoHg MaH1 HoHH (Ho (Ho)(H -H6)7
(19)
k
= +1 - (Last terms cancel out).
(20)
To go from (18) to (19), we note that Var(X) = B[xx*] [[ and E. A Var(d(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:
E Ex, - (SS)). = =#a 1b.
(21)
Putting them together:
i= (1 (1+ A TT(())) + (Ha - 7T) Mb)-
(22)
Similarly for it:
i Ex [[x) -
(23)
= -Tr(E ((( + E(((x) - ((S.)) [((x)) - ((S.))
(24)
= =11+ (T(Ec)-
(25)
Putting together and ii:
Ex, [a] = (1 + F Tr((E))) + -66-4) -m6)=- - (1+ 1 I
(26)
(Ma mb))²² (H, -Hb)
(27)
13

---

Published as a conference paper at ICLR 2020
Then, since Babx.,s/a] Ba, [Bx /a,b//a)] we have:
I Ba, [ax
Baa H₂)² (Ho Ho)l
(28)
Eu,blyy Ma + mg My Ma 14 14 [t -Tr(2)) 4² n Tr(2.) + 4" H 2u μ
(29)
(30)
-2Tr(z)
(31)
Where from the second the third line, we note that μ H, and ug Ms are quadratic forms while μ Hb describe a dot product between two independent randomly drawn samples which has expectation μ² μ.
For proof of Lemma 2 first re-state the result quadratic forms of normally distributed random vectors by Rencher & Schaalje 2008).
Theorem 4. Consider random vector y (H, Σ) and symmetric matrix of constants A, we have:
Varly" Ay) = 2TT((1E)²) + 4u AEAu.
Proof of Lemma
Proof.
Var(ala,b) Var[[ ((S))
[x(x) - o(5b) //
(32)
VVr[((o(x) - ((5)
+ Var( o(xx -Ø(Sa)
(33)
-2Cov( - (5.))
[ - T(Sb)] |
(34)
Var( - -0(()) 1/ Var ((x)) 2(Sa))
|3
(35)
2/ Var( [(xx) o(Sb) Var( (xxx) [(Sa)
(36)
2Varl| ((Sb) 1² +Var( [((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 < a² + for all a, b E R
By applying Theorem we have:
Var( far[]((xx) ((S))
2
= 2(1 =2(1
- (T()) 4(1 + EE 14)
Var[ o(x) ē(Sa)
) 2(1
k
Finally,
E,, (ar((aaa, b)] < En, ( (2 o(x) o(Sa) 12 2varr ((xx) ((S.)
= 18(1 + 22++(2)) + 8(1 + + ) - T2 - Hb)1
= 8(1 + (T((1 + - + EclHa mm) - - 1 } + 22i}
k
1
8(1 yIrEE,((1
Extending to N class: Let x, y denote the query data pair, and the set of N classes be denoted as
c. Let o, [xxx - ((S.) - ||x(x)) d(Ss)) Then we have a correct prediction ý = y
Vi E N y, > 0. Hence: R(Ø) Pre.x.
S 0)
(U
14

---

Published as a conference paper at ICLR 2020
By Frechet's inequality:
N
R(6) >
Σ
Pr(as > 0) (N 22)
Noting that Theorem 3 can be applied each term in the summation:
N
{T)
R(O) 8(1 11++1/)9TTE3) + 16(1 (/E,) + E,y(((H, -u) - )2) -NN-2)
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 minllmageNeet--wwyy with 4 layer CNN + Fully connected layer embedding network.
TRAINING SHOTS
TESTING SHOTS
AVERAGE ACCURACY
MODEL
2
PROTONET FC
44.77 %
$3.75 %
55.04 %
61,06 7
62.26 %
64.60 15
65.19 %
66.63 %
66.65 %
67.52 %
61.05 0.28
2.0
055
655
0.5
Figure 3: Effect of hyperparamoters on k-shot testing performance on minilmageNet.
Table 3: Classification Accuracy minllmageNet-5-wayy with layer CNN embedding network.
TRAINING
TESTING SHOTS
AVERAGE
PRotoNer
PRotoNer
56.35
64.38
66.56
68.26
PRofoNis
56.61
PHOTONEY
64.14%
70.80
PROtUNET
63.17 %
08.63
70.55
VANILA PRorONsT
10
30.99 5
52.2% 96
50.71 %
63.41
66.23%
68.22
69.85 50
71.03 36
71.72.55
12.47 96
63.54
0.25%
EST PHotoNeT
10
48.99 %
$7.83
63.13 %
66.39
68.12 %
69.82
70.63
71.85 36
72.79 9g
73.22 06
66 06.28
0.25 %
PCA PROTNNEY
10
48.01 %
$7.05
62.46 %
64.63
67.61 %
08.98
69.71 %6
71.78 36
71.75 9
72.42 06
65.44
0.24 %
VANILLA PRorONet
1-10
$9.36 5c
59.67
62.77 %
65.76 %
67.96 %
69 29.20 %
70.05
70.90 36
71.34 %4
72.27 %
65.83
0.21 %
15

---

Published as a conference paper at ICLR 2020
Lower bound
Adtual performaree
0.755
0375
0.33
6.799
0.700
9
Teeting shobe
Tetting shote
Figure Comparison between estimated accuracy lower bound empirical accuracy for various training and test shots. Experiment is 2-way few-shot classification performed on miniImageNet.
Table 4: Classification Accuracy on tieredlmageNNet55wwyy with 4 layer CNN embedding network.
TRAINING
STOTT
AVERAGE
PRoroNet PROTONET
$5.05
PROTONET
$4.60
65.88
66.11
ProroNet
42.33 56
9
64.57
06.51
72.05
64.05
0.33
EST PRotoNst
48.85 5g
98.
%
67.24
69.89
70.57
72.09
63.40
PCA PROTONET
48.34 9
$7.44
0.79
64.96
67.07 95
67.93
69.08
70.40 96
70.385
71.65 56
64.96
VANILL PRoroNet
10
35.38 5
49. au
50.76 9
61.25
04.56 76
60.56 5
68.05
09.31
36
70.12.
71.03 96
61.24
0.36
EST PhotoNst
10
07.31 5g
56. 75
622 %
65.78
66.89 9
59
69 98
70.82 36
71 19.99 96
71. 96
65 26
0.32%
PCA PROTONET
10
46.55
$6.61
60.51 9
64.01
66.53
67.70
69.18
69.83
70.62
71.22
64.31
0.33
VANELA PROTONeT
1-10
47.65 96
56.23
62.11%%
63.92
66.34 95
67.94
68.44
68.93
70.50
70.96
64.33
0.30
Table 5: Classification Accuracy on Omniglot-20-way, with 4 layer CNN embedding network.
TESTING SHots
MODEL
TRAINING SHOTS
AVERAGE ACCURACY
VANILLA PRoTONet
93.07 à:
97.59
0.09
98.45
0.00
98.75
0.06
0.06 9
97.81
0.06
VANILLA PRoTONeT
94.39
0.18
91.69
95.64
0.00
98.69
0.06
0.06
91.56
0.07
VANILLA PRoTONet
94.19
0.18%
91.57
98.30
0.00
98.63
0.07
98.77
0.06
00
VASILLA PROTONeT
93.79 2 0.18
97.41
0.10
98.19
0.0.8
98.54
0.37
95.75
0.06
97.34
0.07
VASILLA PROTONer
93.42 0.18
97.34
0.10
98.18 0.0.
98.53
0.37
98.75
0.05
97.25
0.07
MIXED SHoT
L.
94.34
0.17
97.51
0.09
98.65
0.00
98.70
0.06
98.95
0.54
97.74
PCA PacroNer
94.04
0.16
97.61
0.09
98.53 0.07
98. 79
0.06
85
0.06
97.
0.06
EST PRovONEE
95.11
97.95
0.09
98:46
98.77
0.36
95
54
0.06
97.83
0.06
Table Classification Accuracy on minilmageNet-5-wayy with 7 layer ResNet embedding network.
TRAINING SHOTs
TESTING SHOTS
AVERAGE
MOBEL
10
ACCURACY
VANELA PRoTONeT
52.65 5
60.46
64.18 9
66.83
68.27 95
69:23
70.19%
31.37
71.5315
72.29
66.73
0.20
EST PROTONET
$2.56 5
60.63
64.50
66.53
68.35
69.33
70.04
71.21
71.37%
71.60
66.61
0.22
FCA PhoToNeT
52.78 %
60.35
64.05 9
66.24
67.51 95
69.64
69.85
71.13 36
71.58
71.79
66.52
PRotoNst
64 9%
01.03
72.21
72.90 36
74.35
PHotONEr
69.25
71.72%
74.24
ProroNss
PRoroNET
PROTONET
69.36
71.73
PRotoNer
60.10
09.09
16

---

Published as a conference paper at ICLR 2020
Table 7: Classification Accuracy on fieredlmageeett--wwwyyy with 7 layer ResNet embedding network.
TRAINING
AVERAGE
PRoFONiS
PROTONET
PROtONET
57.89
66.83
68.58
68.77
VANILL PRoTONET
47.88 5g
$8.20
61.95% %
66.58
69.12%
71.69
71,9555
73.15 96
73.11 18
75.80 56
66
EST PROTONET
53.05 5g
61.13 96
65.67 9
68.07
69.30
71.43
71,59
72.42 36
72.80 90
73.63 56
67.91
PCA PROTONET
51.21 5
$9.86
63.91 9
66.92
68.88 55
70.38
71,485 53
72.77 8
73.81
72.17 55
67.14
0.52%
VANILLA PRoroNet
10
40.54 5
56.24
62.00
66.28 %
09.37 06
71.43
72.09%
72.91 76
73.56 9
74.72 96
65.95
0.35
EST PROTONET
50.4555 %
60.41
63.19 %
68.46
69.55 95
70.87
72.07 50
72.66 9
73.78
74.79
67.42
0.32%
PCA PROTONET
10
50.18 5
59.59
64.24 9
67.43
69.52 95
70.63
71.78%
72.10 10 35
72.78
73.65
67.19
0.31
VANILLA PRotONet
1-10
50.74 5g
00.03
64.17 %
67.26
04.28 9
69
71.07
72.41
71.99
75.01
66.95
Table 8: Classification Accuracy on Ommiglot-20-way, with 7 layer ResNet embedding network.
TESTING SHOTs
MODEL
TRAINING SHOTS
AVERAGI ACCURACY
VANILLA PROTONET
98.39 %
98.82
99.01 %
99.07
98.35 + 0.05
VANILLA PROTONET
2
95.85 %
98.32 %
98.80
98.95 %
99.07 %
98.20 + 0.05 %
VANILLA PROTONET
3
95.35 %
98.15 %
98.73
98.91 %
99.03 %
98.03 + 0.06
%
VANILLA PROTONET
5
94.42 %
97.98 %
98.60 %
98.77 %
99.99.6 %
97.75 + 0.06 %
VANILLA PROTONET
1-5
96.53 %
98.53 %
98.90
99.06 %
99.15 %
98.43 4: 0.05 %
EST PROTONET
96.
98.23 %
98.68
98.87 %
98. %
98.19
%
PCA PROTONET
96.02 %
98.22 %
98.76
98.93 %
99.02 %
98.19 - 0.05
17


Reviews:
[{"review_id": "rygYKpMVcB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "A Theoretical Analysis of the Number of Shots in Few-Shot Learning\n\nThis paper considers the problem of meta-learning a representation that is suitable for few-shot classification using the distance from class centroids. In particular, it investigates the sensitivity of this approach to the number of shots from the perspective of generalization error. This seems to be a valuable and novel analysis of the problem, and the problem is important since the number of shots might not be known a-priori. The paper proposes a transformation (a dimensionality-reducing linear projection) that is based on the covariance of the within-class and between-class variance in the training set. It is shown that this makes the procedure relatively robust to the number of shots during training. The technique is compared to an informative set of baselines: PCA, adding a fully-connected layer and mixed-shot training.\n\nI liked the explanation for the harmfulness of training and testing with different shots: with few shots, the priority is to minimize the within-class variance, whereas with many shots, it's OK to have some examples that are further from the true mean as their effect on the empirical mean will be mitigated. Furthermore, the hypothesis that the ratio of within-class to between-class variance depends on the number of shots was empirically verified on several datasets. This was great to see. The paper additionally argues that, with fewer shots, the meta-learner in Prototypical Networks might reduce the intrinsic dimension of the embedding to improve generalization error (by effectively reducing the VC dimension). This was verified experimentally by examining the dimensionality of a subspace that approximately represents the embedding vectors.\n\nUnfortunately, I had difficulty following the theoretical analysis. Admittedly, I don't often work with generalization bounds. Nevertheless, to make the paper accessible to a wider audience, I believe it's necessary to improve the clarity (see points below). I spent quite a lot of time trying to understand the proof of Lemma 1 and I did not have time to closely assess the remaining proofs. I have given the benefit of the doubt for now, but I might have to downgrade my rating depending on the response of the authors and the feedback of other commenters.\n\nHigh-level concerns:\n\n(1.1) The approach closely resembles (multi-class) Linear Discriminant Analysis, yet this connection was not discussed in the paper.\n\n(1.2) The improvement of EST-ProtoNet over PCA-ProtoNet is often marginal in Table 1. It would have been better to provide an estimate of the variance over several trials. Nevertheless, it's an interesting result that simply applying PCA improves the robustness of ProtoNet to the training shots.\n\n(1.3) I wonder whether whitening would be more effective than dimensionality reduction? This could also avoid the need to specify $d$.  To be clear, by \"whitening\" I mean incorporating a factor of $\\Lambda^{-1/2}$ into the transform to make the covariance matrix equal to identity.\n\nIssues with mathematical clarity:\n\n(2.1) I could not figure out how equation 5 follows from Chebyshev's inequality. I understand that Chebyshev's inequality establishes a bound on the likelihood of a sample being some distance from the mean, and this bound depends on the variance. I do not see how this can be used to bound $\\operatorname{Pr}(\\alpha > 0)$. I also investigated Markov's inequality (sometimes referred to as Chebyshev's inequality) and Cantelli's inequality (sometimes referred to as the one-sided Chebyshev's inequality), but I could not see how either of these could be applied. Please clarify.\n\n(2.2) The notation of vector inner and outer products did not seem to be consistent throughout the paper (i.e. whether vectors are treated as a row or a column). For example, in Lemma 1, it seems that $x y^T$ denotes an inner product, since $\\alpha$ is a scalar. Then in equation 12, it seems that $x^T y$ denotes an inner product. This is particularly bad in the appendix. The multi-line equation at the end of page 12 seems to mix the two notations. If I have misunderstood, please correct me. I feel that the column-vector notation is more widespread ($x^T y$ for inner product and $x y^T$ for outer product), but the important thing is to be explicit and consistent.\n\n(2.3) I found the proof of Lemma 1 difficult to follow. Maybe I am being slow, but it would be helpful to explain the steps more clearly. (Side note: for the purpose of discussion, it would have been good to enable equation numbering here.) I did not understand the step from the 1st to the 2nd line of \"i = …\". I also could not follow the step from the 2nd to the 3rd line of the equation for $\\Sigma_{\\phi(x) - \\bar{\\phi}(S_b)}$. Nevertheless, I feel that the \"1/k\" term feels plausible, because as the number of sample increases, the estimate of the mean will be more accurate. I also could not follow the step from the 2nd to the 3rd line of the equation for $\\mathbb{E}_{a, b, x, S}[\\alpha]$. Please clarify these points or I may need to reduce my score.\n\nMinor errors:\n\n(3.1) Equation 2 should probably be \"arg max p(...) = y\" rather than just \"p(...) = y\"?\n\n(3.2) In the definition of \\Sigma_c, it is not clear what it means to square a vector. I think this should be written as a vector outer product (x x^T) or at least add a note to explain the notation.\n\n(3.3) There might be some small errors in appendix A.5 that don't affect the outcome:\n- Shouldn't the expression for (ii) include a term which depends on $\\mu_a - \\mu_b$, like the expression for (i)?\n- I wondered whether the expression for $\\mathbb{E}_{x,S|a,b}[\\phi(x) - \\bar{\\phi}(S_b)]$ should be $0.5 (\\mu_a - \\mu_b)$, since $x$ has a 0.5 chance of being from class $a$ and 0.5 chance of being from class $b$?\n\n(3.4) In the statement of Theorem 4 in the appendix, there should be something after \"Var\"?\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "H1g-Zyvc5B", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Update 11/21\nWith the additional experiments and text clarifications, I'm happy to raise my score to accept.\n\nSummary: This paper addresses the dependence of few-shot classification with Prototypical Networks on “shot”, or the number of examples given per class. Typically, performance suffers if the algorithm is tested on a task with different shot than it was trained on. The paper derives a bound for few-shot performance that depends on the shot. The bound is used to motivate an algorithm which maximizes the inter-intra class variance of the embedded samples. Experiments show that the proposed method generalizes better to different test-time shot, though not significantly better than simply training prototypical networks across different shot numbers.\n\nProblem importance: I think reducing the dependence of few-shot algorithms on rather arbitrary parameters like “shot” is an important and interesting problem. In realistic applications, it’s unlikely that the number of examples for each new class will be the same.\n\nComments:\n- I think this paper is a rather nice reminder not to forget our linear algebra while engaged in deep learning. \n- One main concern is that the method derives quite easily from intuition (low intra-class variance implies tight clusters, and high inter-class variance implies well-separated clusters), and right now I don’t feel that the derivation of the bound is adding much to the paper. Perhaps this bound could be investigated a bit more. For example, is there a way to characterize the tightness of this bound empirically? Perhaps with a linearly separable classification problem where we know R(\\phi) is 1? Alternatively, can the lower bound be directly optimized to find “optimal” intra and inter class variance? Would this be equivalent to the proposed method?\n- Another main concern is that the paper is narrowly focused on one few-shot method, ProtoNets, though it seems like the intuitions and the method could extend to other methods. Could you explain what other few-shot algorithms can use this transformation in addition to ProtoNets? \n- The discussion of VC dimension in Section 3.2 seems quite disconnected from the main idea of the paper, and I don’t see how the conclusion from the VC analysis is used in designing the proposed algorithm. \n- It might be interesting to see how this method fares compared to the “Mixed-k” baseline as the number of shots increase even more.\n- Could you discuss how the number of classes (“way”) might interact with this analysis of shot?\n\nWriting Suggestions\n- I believe Equation (2) is incorrect, it doesn’t make sense that p_\\phi = y since p_\\phi is a probability and y is the ground truth label. Perhaps the right parenthesis is in the wrong place, but then it doesn’t make sense to have an indicator of a probability either. \n- There is occasional sloppiness e.g., “[The presence of k in the first two terms of the denominator of the bound] implies diminishing returns in expected accuracy when more support data is added without altering \\phi.” I think it should say the *bound* is lowered, not necessarily R(\\phi).\n- I suggest adding a related work section\n- Consider moving Lemmas 1 and 2 to the appendix, they don’t add much understanding in my view.\n\nI assumed the correctness of the proofs - it would be good to make these easier to follow for a general audience. I'd consider raising my score if the method was put in more context, if the bound could be analyzed further, and if the paper could be more focused. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "ByeLxCR1qB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThe 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.\n\n+Strengths:\n1. The paper focuses on an important problem: number of shots in few-shot learning, and chooses prototypical network which is a very famous and widely used method for detailed analysis. \n2. The paper provides relatively solid theoretical analysis with careful derivation. The final upperbound of expected accuracy matches our intuition to certain degree. Although some of the assumptions (such as 2-way classification and equal covariance for all classes) are not so realistic, the work is meaningful and very inspiring.\n3. The proposed modification over prototypical network inspired by the formula is reasonable and the experimental results demonstrate its effectiveness.\n\n-Weaknesses:\n1. The first observation says that \"diminishing returns in expected accuracy when more support data is added without altering \\phi\". Does it mean that the accuracy of prototypical network deteriorates with more support data? Will the accuracy saturate and no longer diminish from certain k?\n2. Some of the accuracy improvements are not so significant from the results (even for Mini-ImageNet and Tiered-ImageNet). I was wondering if it is due to the prototypical network itself (the intrinsic property of the prototypical network limits its improvement upperbound) or something else? Please clarify.\n3. Some unclear descriptions.  How is the formulation derived between Eq. 3 and Eq. 4? More details should be given here. The descriptions about EST (Embedding Space Transformation) is insufficient, which makes it hard to understand why such operations are conducted. Moreover, it seems that the proposed approach need to compute the covariance mean and mean covariance of each class. Would it be computed in each iteration? If so, it seems to be very slow.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers generally found the paper's contribution to be valuable and informative, and I believe that this paper should be accepted for publication and a poster presentation. I would strongly recommend to the authors to carefully read over the reviews and address any comments or concerns that were not yet addressed in the rebuttal.
Decision: Accept (Poster)