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 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.
A Theoretical Analysis of the Number of Shots in Few-Shot Learning
This 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.
I 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.
Unfortunately, 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.
High-level concerns:
(1.1) The approach closely resembles (multi-class) Linear Discriminant Analysis, yet this connection was not discussed in the paper.
(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.
(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.
Issues with mathematical clarity:
(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.
(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.
(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.
Minor errors:
(3.1) Equation 2 should probably be "arg max p(...) = y" rather than just "p(...) = y"?
(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.
(3.3) There might be some small errors in appendix A.5 that don't affect the outcome:
- Shouldn't the expression for (ii) include a term which depends on $\mu_a - \mu_b$, like the expression for (i)?
- 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$?
(3.4) In the statement of Theorem 4 in the appendix, there should be something after "Var"?