FEW-SHOT LEARNING AS CLUSTER-INDUCED VORONOI DIAGRAMS: A GEOMETRIC APPROACH
Year: 2022

Abstract:
Few-shot learning (FSL) is the process of rapid generalization from abundant base samples to inadequate novel samples. Despite extensive research in recent years, FSL is still not yet able to generate satisfactory solutions for a wide range of real-world applications. To confront this challenge, we study the FSL problem from a geometric point of view in this paper. One observation is that the widely embraced ProtoNet model is essentially a Voronoi Diagram (VD) in the feature space. We retrofit it by making use of a recent advance in computational geometry called Cluster-induced Voronoi Diagram (CIVD). Starting from the simplest nearest neighbor model, CIVD gradually incorporates cluster-to-point and then cluster-to-cluster relationships for space subdivision, which is used to improve the accuracy and robustness at multiple stages of FSL. Specifically, we use CIVD (1) to integrate parametric and nonparametric few-shot classifiers; (2) to combine feature representation and surrogate representation; (3) and to leverage feature-level, transformation-level, and geometry-level heterogeneities for a better ensemble. Our CIVD-based workflow enables us to achieve new state-of-the-art results on mini-ImageNet, CUB, and tiered-ImagenNet datasets, with ∼2%−5% improvements upon the next best. To summarize, CIVD provides a mathematically elegant and geometrically interpretable framework that compensates for extreme data insufficiency, prevents overfitting, and allows for fast geometric ensemble for thousands of individual VD. These together make FSL stronger.

heading: 1 INTRODUCTION
text: Recent years have witnessed a tremendous success of deep learning in a number of data-intensive applications; one critical reason for which is the vast collection of hand-annotated high-quality data, such as the millions of natural images for visual object recognition (Deng et al., 2009). However, in many real-world applications, such large-scale data acquisition might be difficult and comes at a premium, such as in rare disease diagnosis (Yoo et al., 2021) and drug discovery (Ma et al., 2021b; 2018). As a consequence, Few-shot Learning (FSL) has recently drawn growing interests (Wang et al., 2020).
Generally, few-shot learning algorithms can be categorized into two types, namely inductive and transductive, depending on whether estimating the distribution of query samples is allowed. A typical transductive FSL algorithm learns to propagate labels among a larger pool of query samples in a semi-supervised manner (Liu et al., 2019); notwithstanding its normally higher performance, in many real world scenarios a query sample (e.g. patient) also comes individually and is unique, for instance, in personalized pharmacogenomics (Sharifi-Noghabi et al., 2020). Thus, we in this paper adhere to the inductive setting and make on-the-fly prediction for each newly seen sample.
Few-shot learning is challenging and substantially different from conventional deep learning, and has been tackled by many researchers from a wide variety of angles. Despite the extensive research
All four authors are corresponding authors.
on the algorithmic aspects of FSL (see Sec. 2), two challenges still pose an obstacle to successful FSL: (1) how to sufficiently compensate for the data deficiency in FSL? and (2) how to make the most use of the base samples and the pre-trained model?
For the first question, data augmentation has been a successful approach to expand the size of data, either by Generative Adversarial Networks (GANs) (Goodfellow et al., 2014) (Li et al., 2020b; Zhang et al., 2018) or by variational autoencoders (VAEs) (Kingma & Welling, 2014) (Zhang et al., 2019; Chen et al., 2019b). However, in each way, the authenticity of either the augmented data or the feature is not guaranteed, and the out-of-distribution hallucinated samples (Ma et al., 2019) may hinder the subsequent FSL. Recently, Liu et al. (2020b) and Ni et al. (2021) investigate supportlevel, query-level, task-level, and shot-level augmentation for meta-learning, but the diversity of FSL models has not been taken into consideration. For the second question, Yang et al. (2021) borrows the top-2 nearest base classes for each novel sample to calibrate its distribution and to generate more novel samples. However, when there is no proximal base class, this calibration may utterly alter the distribution. Another line of work (Sbai et al., 2020; Zhou et al., 2020) learns to select and design base classes for a better discrimination on novel classes, which all introduce extra training burden. As a matter of fact, we still lack a method that makes full use of the base classes and the pretrained model effectively.
In this paper, we study the FSL problem from a geometric point of view. In metric-based FSL, despite being surprisingly simple, the nearest neighbor-like approaches, e.g. ProtoNet (Snell et al., 2017) and SimpleShot (Wang et al., 2019), have achieved remarkable performance that is even better than many sophisticatedly designed methods. Geometrically, what a nearest neighbor-based method does, under the hood, is to partition the feature space into a Voronoi Diagram (VD) that is induced by the feature centroids of the novel classes. Although it is highly efficient and simple, Voronoi Diagrams coarsely draw the decision boundary by linear bisectors separating two centers, and may lack the ability to subtly delineate the geometric structure arises in FSL.
To resolve this issue, we adopt a novel technique called Cluster-induced Voronoi Diagram (CIVD) (Chen et al., 2013; 2017; Huang & Xu, 2020; Huang et al., 2021), which is a recent breakthrough in computation geometry. CIVD generalizes VD from a point-to-point distance-based diagram to a cluster-to-point influence-based structure. It enables us to determine the dominating
region (or Voronoi cell) not only for a point (e.g. a class prototype) but also for a cluster of points, guaranteed to have a (1 + )-approximation with a nearly linear size of diagram for a wide range of locally dominating influence functions. CIVD provides us a mathematically elegant framework to depict the feature space and draw the decision boundary more precisely than VD without losing the resistance to overfitting.
Accordingly, in this paper, we show how CIVD is used to improve multiple stages of FSL and make several contributions as follows.
1. We first categorize different types of few-shot classifiers as different variants of Voronoi Diagram: nearest neighbor model as Voronoi Diagram, linear classifier as Power Diagram, and cosine classifier as spherical Voronoi Diagram (Table 1). We then unify them via CIVD that enjoys the advantages of multiple models, either parametric or nonparametric (denoted as DeepVoro--).
2. Going from cluster-to-point to cluster-to-cluster influence, we further propose Cluster-to-cluster Voronoi Diagram (CCVD), as a natural extension of CIVD. Based on CCVD, we present DeepVoro which enables fast geometric ensemble of a large pool of thousands of configurations for FSL.
3. Instead of using base classes for distribution calibration and data augmentation (Yang et al., 2021), we propose a novel surrogate representation, the collection of similarities to base classes, and thus promote DeepVoro to DeepVoro++ that integrates feature-level, transformation-level, and geometry-level heterogeneities in FSL.
Extensive experiments have shown that, although a fixed feature extractor is used without independently pretrained or epoch-wise models, our method achieves new state-of-the-art results on all
three benchmark datasets including mini-ImageNet, CUB, and tiered-ImageNet, and improves by up to 2.18% on 5-shot classification, 2.53% on 1-shot classification, and up to 5.55% with different network architectures.

heading: 2 RELATED WORK
text: Few-Shot Learning. There are a number of different lines of research dedicated to FSL. (1) Metricbased methods employ a certain distance function (cosine distance (Mangla et al., 2020; Xu et al., 2021), Euclidean distance (Wang et al., 2019; Snell et al., 2017), or Earth Mover’s Distance (Zhang et al., 2020a;b)) to bypass the optimization and avoid possible overfitting. (2) Optimization-based approaches (Finn et al., 2017) manages to learn a good model initialization that accelerates the optimization in the meta-testing stage. (3) Self-supervised-based (Zhang et al., 2021b; Mangla et al., 2020) methods incorporate supervision from data itself to learn a robuster feature extractor. (4) Ensemble method is another powerful technique that boosting the performance by integrating multiple models (Ma et al., 2021a). For example, Dvornik et al. (2019) trains several networks simultaneously and encourages robustness and cooperation among them. However, due to the high computation load of training deep models, this ensemble is restricted by the number of networks which is typically <20. In Liu et al. (2020c), instead, the ensemble consists of models learned at each epoch, which, may potentially limit the diversity of ensemble members.
Geometric Understanding of Deep Learning. The geometric structure of deep neural networks is first hinted at by Raghu et al. (2017) who reveals that piecewise linear activations subdivide input space into convex polytopes. Then, Balestriero et al. (2019) points out that the exact structure is a Power Diagram (Aurenhammer, 1987) which is subsequently applied upon recurrent neural network (Wang et al., 2018) and generative model (Balestriero et al., 2020). The Power/Voronoi Diagram subdivision, however, is not necessarily the optimal model for describing feature space. Recently, Chen et al. (2013; 2017); Huang et al. (2021) uses an influence function F (C, z) to measure the joint influence of all objects in C on a query z to build a Cluster-induced Voronoi Diagram (CIVD). In this paper, we utilize CIVD to magnify the expressivity of geometric modeling for FSL.

heading: 3 METHODOLOGY

heading: 3.1 PRELIMINARIES
text: Few-shot learning aims at discriminating between novel classes Cnovel with the aid of a larger amount of samples from base classes Cbase, Cnovel∩Cbase = ∅. The whole learning process usually follows the
meta-learning scheme. Formally, given a dataset of base classes D = {(xi, yi)},xi ∈ D, yi ∈ Cbase with D being an arbitrary domain e.g. natural image, a deep neural network z = φ(x), z ∈ Rn, which maps from image domain D to feature domain Rn, is trained using standard gradient descent algorithm, and after which φ is fixed as a feature extractor. This process is referred to as metatraining stage that squeezes out the commonsense knowledge from D. For a fair evaluation of the learning performance on a few samples, the meta-testing stage is typically formulated as a series of K-way N -shot tasks (episodes) {T }. Each such episode is further decomposed into a support set S = {(xi, yi)}K×Ni=1 , yi ∈ CT and a query set Q = {(xi, yi)} K×Q i=1 , yi ∈ CT , in which the episode classes CT is a randomly sampled subset of Cnovel with cardinality K, and each class contains onlyN andQ random samples in the support set and query set, respectively. For few-shot classification, we introduce here two widely used schemes as follows. For simplicity, all samples here are from S and Q, without data augmentation applied. Nearest Neighbor Classifier (Nonparametric). In Snell et al. (2017); Wang et al. (2019) etc., a prototype ck is acquired by averaging over all supporting features for a class k ∈ CT :
ck = 1
N
∑ x∈S,y=k φ(x) (1)
Then each query sample x ∈ Q is classified by finding the nearest prototype: ŷ = arg minkd(z, ck) = ||z − ck||22, in which we use Euclidean distance for distance metric d. Linear Classifier (Parametric). Another scheme uses a linear classifier with cross-entropy loss optimized on the supporting samples:
L(W , b) = ∑ (x,y)∈S − log p(y|φ(x);W , b) = ∑
(x,y)∈S − log exp(W Ty φ(x) + by)∑ k exp(W T k φ(x) + bk) (2)
in which Wk, bk are the linear weight and bias for class k, and the predicted class for query x ∈ Q is ŷ = arg maxk p(y|z;Wk, bk).

heading: 3.2 FEW-SHOT LEARNING AS CLUSTER-INDUCED VORONOI DIAGRAMS
text: In this section, we first introduce the basic concepts of Voronoi Tessellations, and then show how parametric/nonparametric classifier heads can be unified by VD.
Definition 3.1 (Power Diagram and Voronoi Diagram). Let Ω = {ω1, ..., ωK} be a partition of the space Rn, and C = {c1, ..., cK} be a set of centers such that ∪Kr=1ωr = Rn,∩Kr=1ωr = ∅. Additionally, each center is associated with a weight νr ∈ {ν1, ..., νK} ⊆ R+. Then the set of pairs {(ω1, c1, ν1), ..., (ωK , cL, νK)} is a Power Diagram (PD), where each cell is obtained via ωr = {z ∈ Rn : r(z) = r}, r ∈ {1, ..,K}, with
r(z) = arg min k∈{1,...,K}
d(z, ck) 2 − νk. (3)
If the weights are equal for all k, i.e. νk = νk′ ,∀k, k′ ∈ {1, ...,K}, then a PD collapses to a Voronoi Diagram (VD).
By definition, it is easy to see that the nearest neighbor classifier naturally partitions the space into K cells with centers {c1, ..., cK}. Here we show that the linear classifier is also a VD under a mild condition.
Theorem 3.1 (Voronoi Diagram Reduction). The linear classifier parameterized by W , b partitions the input space Rn to a Voronoi Diagram with centers {c̃1, ..., c̃K} given by c̃k = 12Wk if bk = − 14 ||Wk|| 2 2, k = 1, ...,K.
Proof. See Appendix B for details.

heading: 3.2.1 FROM VORONOI DIAGRAM TO CLUSTER-INDUCED VORONOI DIAGRAM
text: Now that both nearest neighbor and linear classifier have been unified by VD, a natural idea is to integrate them together. Cluster-induced Voronoi Diagram (CIVD) (Chen et al., 2017; Huang et al.,
2021) is a generalization of VD which allows multiple centers in a cell, and is successfully used for clinical diagnosis from biomedical images (Wang et al., 2015), providing an ideal tool for the integration of parametric/nonparametric classifier for FSL. Formally: Definition 3.2 (Cluster-induced Voronoi Diagram (CIVD) (Chen et al., 2017; Huang et al., 2021)). Let Ω = {ω1, ..., ωK} be a partition of the space Rn, and C = {C1, ..., CK} be a set (possibly a multiset) of clusters. The set of pairs {(ω1, C1), ..., (ωK , CK)} is a Cluster-induced Voronoi Diagram (CIVD) with respect to the influence function F (Ck, z), where each cell is obtained via ωr = {z ∈ Rn : r(z) = r}, r ∈ {1, ..,K}, with
r(z) = arg max k∈{1,...,K}
F (Ck, z). (4)
Here C can be either a given set of clusters or even the whole power set of a given point set, and the influence function is defined as a function over the collection of distances from each member in a cluster Ck to a query point z: Definition 3.3 (Influence Function). The influence from Ck, k ∈ {1, ...,K} to z /∈ Ck is F (Ck, z) = F ({d(c(i)k , z)|c (i) k ∈ Ck} |Ck| i=1). In this paper F is assumed to have the following form
F (Ck, z) = − sign(α) ∑|Ck| i=0 d(c (i) k , z) α. (5)
The sign function here makes sure that F is a monotonically decreasing function with respect to distance d. The hyperparameter α controls the magnitude of the influence, for example, in gravity force α = −(n− 1) in n-dimensional space and in electric force α = −2. Since the nearest neighbor centers {ck}Kk=1 and the centers introduced by linear classifier {c̃k}Kk=1 are obtained from different schemes and could both be informative, we merge the corresponding centers for a novel class k to be a new cluster Ck = {ck, c̃k}, and use the resulting C = {C1, ..., CK} to establish a CIVD. In such a way, the final partition may enjoy the advantages of both parametric and nonparametric classifier heads. We name this approach as DeepVoro--.

heading: 3.3 FEW-SHOT CLASSIFICATION VIA SURROGATE REPRESENTATION
text: In nearest neighbor classifier head, the distance from a query feature z to each of the prototypes {ck}Kk=1 is the key discrimination criterion for classification. We rewrite {d(z, ck)}Kk=1 to be a vector d ∈ RK such that dk = d(z, ck). These distances are acquired by measure the distance between two points in high dimension: z, ck ∈ Rn. However, the notorious behavior of high dimension is that the ratio between the nearest and farthest points in a point set P approaches 1 (Aggarwal et al., 2001), making {d(z, ck)}Kk=1 less discriminative for classification, especially for FSL problem with sample size N ·K n. Hence, in this paper, we seek for a surrogate representation. In human perception and learning system, similarity among familiar and unfamiliar objects play a key role for object categorization and classification (Murray et al., 2002), and it has been experimentally verified by functional magnetic resonance imaging (fMRI) that a large region in occipitotemporal cortex processes the shape of both meaningful and unfamiliar objects (Op de Beeck et al., 2008). In our method, a connection will be built between each unfamiliar novel class in Cnovel and each related well-perceived familiar class in Cbase. So the first step is to identify the most relevant base classes for a specific task T . Concretely: Definition 3.4 (Surrogate Classes). In episode T , given the set of prototypes {ck}Kk=1 for the support set S and the set of prototypes {c′t} |Cbase| t=1 for the base set D, the surrogate classes for episode classes CT is given as:
Csurrogate(T ) = K⋃ k=1 Top-R t∈{1,...,|Cbase|} d(ck, c ′ t) (6)
in which the top-R function returnsR base class indices with smallest distances to ck, and the center for a base class t is given as c′t = 1 |{(x,y)|x∈D,y=t}| ∑ x∈D,y=tφ(x). Here R is a hyperparameter.
The rationale behind this selection instead of simply using the whole base classes Cbase is that, the episode classes CT are only overlapped with a portion of base classes (Zhang et al., 2021a), and
discriminative similarities are likely to be overwhelmed by the background signal especially when the number of base classes is large. After the surrogate classes are found, we re-index their feature centers to be {c′j}R̃j=1, R̃ ≤ R · K. Then, both support centers {ck}Kk=1 and query feature z are represented by the collection of similarities to these surrogate centers:
d′k = (d(ck, c ′ 1), ..., d(ck, c ′ R̃ )), k = 1, ...,K
d′ = (d(z, c′1), ..., d(z, c ′ R̃
)) (7)
where d′k,d ′ ∈ RR̃ are the surrogate representation for novel class k and query feature z, respectively. By surrogate representation, the prediction is found through ŷ = arg minkd(d ′,d′k) = arg mink||d′ − d′k||22. This set of discriminative distances is rewritten as d′′ ∈ RK such that d′′k = d(d
′,d′k). An illustration of the surrogate representation is shown in Figure 1 on MultiDigitMNIST, a demonstrative dataset.
Integrating Feature Representation and Surrogate Representation. Until now, we have two discriminative systems, i.e., feature-based d ∈ RK and surrogate-based d′′ ∈ RK . A natural idea is to combine them to form the following final criterion:
d̃ = β d
||d||1 + γ
d′′
||d′′||1 , (8)
where d and d′′ are normalized by their Manhattan norm, ||d||1 = ∑K k=1dk and ||d′′||1 = ∑K k=1d ′′ k , respectively, and β and γ are two hyperparameters adjusting the weights for feature representation and surrogate representation.

heading: 3.4 DEEPVORO: INTEGRATING MULTI-LEVEL HETEROGENEITY OF FSL
text: In this section we present DeepVoro, a fast geometric ensemble framework that unites our contributions to multiple stages of FSL, and show how it can be promoted to DeepVoro++ by incorporating surrogate representation.
Compositional Feature Transformation. It is believed that FSL algorithms favor features with more Gaussian-like distributions, and thus various kinds of transformations are used to improve the normality of feature distribution, including power transformation (Hu et al., 2021), Tukey’s Ladder of Powers Transformation (Yang et al., 2021), and L2 normalization (Wang et al., 2019). While these transformations are normally used independently, here we propose to combine several transformations sequentially in order to enlarge the expressivity of transformation function and to increase the polymorphism of the FSL process. Specifically, for a feature vector z, three kinds of transformations are considered: (I) L2 Normalization. By projection onto the unit sphere in Rn, the feature is normalized as: f(z) = z||z||2 . (II) Linear Transformation. Now since all the features are located on the unit sphere, we then can do scaling and shifting via a linear transformation: gw,b(z) = wz + b. (III) Tukey’s Ladder of Powers Transformation. Finally, Tukey’s Ladder of Powers Transformation
is applied on the feature: hλ(z) = { zλ if λ 6= 0 log(z) if λ = 0 . By the composition of L2 normalization, linear transformation, and Tukey’s Ladder of Powers Transformation, now the transformation function becomes (hλ ◦ gw,b ◦ f)(z) parameterized by w, b, λ. Multi-level Heterogeneities in FSL. Now we are ready to articulate the hierarchical heterogeneity existing in different stages of FSL. (I) Feature-level Heterogeneity: Data augmentation has been exhaustively explored for expanding the data size of FSL (Ni et al., 2021), including but not limited to rotation, flipping, cropping, erasing, solarization, color jitter, MixUp (Zhang et al., 2017), etc. The modification of image x will change the position of feature z in the feature space. We denote all possible translations of image as a set of functions {T}. (II) Transformation-level Heterogeneity: After obtaining the feature z, a parameterized transformation is applied to it, and the resulting features can be quite different for these parameters (see Figure F.1). We denote the set of all possible transformations to be {Pw,b,λ}. (III) Geometry-level Heterogeneity: Even with the provided feature, the few-shot classification model can still be diverse: whether a VD or PD-based model is used, whether the feature or the surrogate representation is adopted, and the setting of R will also change the degree of locality. We denote all possible models as {M}.
DeepVoro for Fast Geometric Ensemble of VDs. With the above three-layer heterogeneity, the FSL process can be encapsulated as (M◦Pw,b,λ◦φ◦T )(x), and all possible configurations of a given episode T with a fixed φ is the Cartesian product of these three sets: {T}×{Pw,b,λ}×{M}. Indeed, when a hold-out validation dataset is available, it can be used to find the optimal combination, but by virtue of ensemble learning, multiple models can still contribute positively to FSL (Dvornik et al., 2019). Since the cardinality of the resulting configuration set could be very large, the FSL model M as well as the ensemble algorithm is required to be highly efficient. The VD is a nonparametric model and no training is needed during the meta-testing stage, making it suitable for fast geometric ensemble. While CIVD models the cluster-to-point relationship via an influence function, here we further extend it so that cluster-to-cluster relationship can be considered. This motivates us to define Cluster-to-cluster Voronoi Diagram (CCVD): Definition 3.5 (Cluster-to-cluster Voronoi Diagram). Let Ω = {ω1, ..., ωK} be a partition of the space Rn, and C = {C1, ..., CK} be a set of totally ordered sets with the same cardinality L (i.e. |C1| = |C2| = ... = |CK | = L). The set of pairs {(ω1, C1), ..., (ωK , CK)} is a Cluster-to-cluster Voronoi Diagram (CCVD) with respect to the influence function F (Ck, C(z)), and each cell is obtained via ωr = {z ∈ Rn : r(z) = r}, r ∈ {1, ..,K}, with
r(z) = arg max k∈{1,...,K}
F (Ck, C(z)) (9)
where C(z) is the cluster (also a totally ordered set with cardinality L) that query point z belongs, which is to say, all points in this cluster (query cluster) will be assigned to the same cell. Similarly, the Influence Function is defined upon two totally ordered sets Ck = {c(i)k }Li=1 and C(z) = {z(i)}Li=1:
F (Ck, C(z)) = − sign(α) ∑L i=0 d(c (i) k , z (i))α. (10)
With this definition, now we are able to streamline our aforementioned novel approaches into a single ensemble model. Suppose there are totally L possible settings in our configuration pool {T} × {Pw,b,λ} × {M}, for all configurations {ρi}Li=1, we apply them onto the support set S to generate the K totally ordered clusters {{c(ρi)k }Li=1}Kk=1 including each center c (ρi) k derived through configuration ρi, and onto a query sample x to generate the query cluster C(z) = {z(ρ1), ...,z(ρL)}, and then plug these two into Definition 3.5 to construct the final Voronoi Diagram.
When only the feature representation is considered in the configuration pool, i.e. ρi ∈ {T} × {Pw,b,λ}, our FSL process is named as DeepVoro; if surrogate representation is also incorporated, i.e. ρi ∈ {T} × {Pw,b,λ} × {M}, DeepVoro is promoted to DeepVoro++ that allows for higher geometric diversity. See Appendix A for a summary of the notations and acronyms
4 EXPERIMENTS
The main goals of our experiments are to: (1) validate the strength of CIVD to integrate parametric and nonparametric classifiers and confirm the necessity of Voronoi reduc-
tion; (2) investigate how different levels of heterogeneity individually or collaboratively contribute to the overall result, and compare them with the state-of-art method; (3) reanalyze this ensemble when the surrogate representation comes into play, and see how it could ameliorate the extreme shortage of support samples. See Table 2 for a summary and Appendix D for the detailed descriptions of mini-ImageNet (Vinyals et al., 2016), CUB (Welinder et al., 2010), and tiered-ImageNet (Ren et al., 2018), that are used in this paper.
DeepVoro--: Integrating Parametric and Nonparametric Methods via CIVD. To verify our proposed CIVD model for the integration of parameter/nonparametric FSL classifiers, we first run three standalone models: Logistic Regressions with Power/Voronoi Diagrams as the underlining geometric structure (Power-LR/Voronoi-LR), and vanilla Voronoi Diagram (VD, i.e. nearest neighbor model), and then integrate VD with either Power/Voronoi-LR (see Appendix E for details). Interestingly, VD with the Power-LR has never reached the best result, suggesting that ordinary LR cannot
be integrated with VD due to their intrinsic distinct geometric structures. After the proposed Voronoi reduction (Theorem 3.1), however, VD+Voronoi-LR is able to improve upon both models in most cases, suggesting that CIVD can ideally integrate parameter and nonparametric models for better FSL.
DeepVoro: Improving FSL by Hierarchical Heterogeneities. In this section, we only consider two levels of heterogeneities for ensemble: feature-level and transformation-level. For feature-level ensemble, we utilize three kinds of image augmentations: rotation, flipping, and central cropping summing up to 64 distinct ways of data augmentation (Appendix F). For transformation-level ensemble, we use the proposed compositional transformations with 8 different combinations of λ and b that encourage a diverse feature transformations (Appendix F.1) without loss of accuracy (Figure 2). The size of the resulting configuration pool becomes 512 and DeepVoro’s performance is shown in Table 3. Clearly, DeepVoro outperforms all previous methods especially on 5-way 5-shot FSL. Specifically, DeepVoro is better than the next best by 2.18% (than Ni et al. (2021)) on miniImageNet, by 1.47% (than Hu et al. (2021)) on CUB, and by 1.02% (than Yang et al. (2021)) on tiered-ImageNet. Note that this is an estimated improvement because not all competitive methods here are tested with the same random seed and the number of episodes. More detailed results can be found in Appendix F. By virtue of CCVD and using the simplest VD as the building block, DeepVoro is arguably able to yield a consistently better result by the ensemble of a massive pool of independent VD. DeepVoro also exhibits high resistance to outliers, as shown in Figure K.16.
DeepVoro++: Further Improvement of FSL via Surrogate Representation. In surrogate representation, the number of neighbors R for each novel class and the weight β balancing surrogate/feature representations are two hyperparameters. With the help of an available validation set, a natural question is that whether the hyperparameter can be found through the optimization on the validation set, which requires a good generalization of the hyperparameters across different novel classes. From Figure K.13, the accuracy of VD with varying hyperparameter shows a good agreement between testing and validation sets. With this in mind, we select 10 combinations of β and R, guided by the validation set, in conjunction with 2 different feature transformations and 64 different image augmentations, adding up to a large pool of 1280 configurations for ensemble (denoted by DeepVoro++). As shown in Table 3, DeepVoro++ achieves best results for 1-shot FSL — 2.53%

heading: Methods Geometric Structures Feat. Trans. Geo. L 5-way 1-shot 5-way 5-shot
text: A. mini-ImageNet 5-way 5-shot
B. mini-ImageNet 5-way 1-shot
C. CUB 5-way 5-shot
D. CUB 5-way 1-shot
higher than Zhang et al. (2020b), 2.38% higher than Hu et al. (2021), and 1.09% higher than Zhang et al. (2020b), on three datasets, respectively, justifying the efficacy of our surrogate representation. See Appendix G for more detailed analysis.
Ablation Experiments and Running Time. Table 4 varies the level of heterogeneity (see Table F.4 and G.5 for all datasets). The average accuracy of VDs without CCVD integration is marked by ], and is significantly lower than the fully-fledged ensemble. Table 5 presents the running time of DeepVoro(++) benchmarked in a 20-core Intel© CoreTM i7 CPU with NumPy (v1.20.3), whose efficiency is comparable to DC/S2M2 2, even with >1000× diversity.
Experiments with Different Backbones, Meta-training Protocols, and Domains. Because different feature extraction backbones, meta-training losses, and degree of discrepancy between the source/target domains will all affect the downstream FSL, we here examine the robustness of DeepVoro/DeepVoro++ under a number of different circumstances, and details are shown in Appendices H, I, J. Notably, DeepVoro/DeepVoro++ attains the best performance by up to 5.55%, and is therefore corroborated as a superior method for FSL, regardless of the backbone, training loss, or domain.

heading: 5 CONCLUSION
text: In this paper, our contribution is threefold. We first theoretically unify parametric and nonparametric few-shot classifiers into a general geometric framework (VD) and show an improved result by virtue of this integration (CIVD). By extending CIVD to CCVD, we present a fast geometric ensemble method (DeepVoro) that takes into consideration thousands of FSL configurations with high efficiency. To deal with the extreme data insufficiency in one-shot learning, we further propose a novel surrogate representation which, when incorporated into DeepVoro, promotes the performance of one-shot learning to a higher level (DeepVoro++). In future studies, we plan to extend our geometric approach to meta-learning-based FSL and lifelong FSL.

heading: ACKNOWLEDGMENTS
text: This research was supported in part by NSF through grant IIS-1910492.

heading: REPRODUCIBILITY STATEMENT
text: Our code as well as data split, random seeds, hyperparameters, scripts for reproducing the results in the paper are available at https://github.com/horsepurve/DeepVoro.

heading: A NOTATIONS AND ACRONYMS
text: Parameters for feature-level , transformation-level , and geometry-level heterogeneity are shown
in yellow , blue , and red , respectively. See Sec. F for implementation details. †Here PD is reduced to VD by Theorem 3.1. ‡For every λ (or R), the b (or β) value with the highest validation accuracy is introduced into the configuration pool.
Methods GeometricStructures Centers Tunable Param. # Description
DeepVoro-- CIVD Ck = {ck, c̃k} ck from VD c̃k from PD†
− − −
DeepVoro CCVD Ck = {c (ρi) k }Li=1
ρi ∈ {T} × {Pw,b,λ}
angle of rotation 4 − flipping or not 2 − scaling & cropping 8 − w = 1 − scale factor in linear transformation b 4 shift factor in linear transformation λ 2 exponent in powers transformation
#configurations L = 512
DeepVoro++ CCVD Ck = {c (ρi) k }Li=1
ρi ∈ {T} × {Pw,b,λ} × {M}
angle of rotation 4 − flipping or not 2 − scaling & cropping 8 − w = 1 − scale factor in linear transformation b 1‡ shift factor in linear transformation λ 2 exponent in powers transformation R 10 the number of top-R nearest baseprototypes for a novel prototype γ = 1 − weight for surrogate representation β 1‡ weight for feature representation
#configurations L = 1280

heading: B POWER DIAGRAM SUBDIVISION AND VORONOI REDUCTION

heading: B.1 PROOF OF THEOREM 3.1
text: Lemma B.1. The vertical projection from the lower envelope of the hyperplanes {Πk(z) : W Tk z+ bk}Kk=1 onto the input space Rn defines the cells of a PD.
Theorem 3.1 (Voronoi Diagram Reduction). The linear classifier parameterized by W , b partitions the input space Rn to a Voronoi Diagram with centers {c̃1, ..., c̃K} given by c̃k = 12Wk if bk = − 14 ||Wk|| 2 2, k = 1, ...,K.
Proof. We first articulate Lemma B.1 and find the exact relationship between the hyperplane Πk(z) and the center of its associated cell in Rn. By Definition 3.1, the cell for a point z ∈ Rn is found by comparing d(z, ck)2 − νk for different k, so we define the power function p(z, S) expressing this value
p(z, S) = (z − u)2 − r2 (11)
in which S ⊆ Rn is a sphere with center u and radius r. In fact, the weight ν associated with a center in Definition 3.1 can be intepreted as the square of the radius r2. Next, let U denote a paraboloid y = z2, let Π(S) be the transform that maps sphere S with center u and radius r into hyperplane
Π(S) : y = 2z · u− u · u + r2. (12)
It can be proved that Π is a bijective mapping between arbitrary spheres in Rn and nonvertical hyperplanes in Rn+1 that intersect U (Aurenhammer, 1987). Further, let z′ denote the vertical projection of z onto U and z′′ denote its vertical projection onto Π(S), then the power function can be written as
p(z, S) = d(z, z′)− d(z, z′′), (13)
which implies the following relationships between a sphere in Rn and an associated hyperplane in Rn+1 (Lemma 4 in Aurenhammer (1987)): let S1 and S2 be nonco-centeric spheres in Rn, then the bisector of their Power cells is the vertical projection of Π(S1) ∩ Π(S2) onto Rn. Now, we have a direct relationship between sphere S, and hyperplane Π(S), and comparing equation (12) with the hyperplanes used in logistic regression {Πk(z) : W Tk z + bk}Kk=1 gives us
u = 1
2 Wk
r2 = bk + 1
4 ||Wk||22.
(14)
Although there is no guarantee that bk + 14 ||Wk|| 2 2 is always positive for an arbitrary logistic regression model, we can impose a constraint on r2 to keep it be zero during the optimization, which implies
bk = − 1
4 ||Wk||22. (15)
By this way, the radii for allK spheres become identical (all zero). After the optimization of logistic regression model, the centers { 12Wk} K k=1 will be used for CIVD integration.

heading: C DETAILS ABOUT THE DEMONSTRATIVE EXAMPLE ON MULTIDIGITMNIST DATASET
text: MultiDigitMNIST (Sun, 2019) dataset is created by concatenating two (or three) digits of different classes from MNIST for few-shot image classification. Here we use DoubleMNIST Datasets (i.e. two digits in an image) consisting of 100 classes (00 to 09), 1000 images of size 64 × 64 × 1 per class, and the classes are further split into 64, 20, and 16 classes for training, testing, and validation, respectively. To better embed into the R2 space, we pick a ten-classes subset (00, 01, 12, 13, 04, 05, 06, 77, 08, and 09) as the base classes for meta-training, and another five-class subset (02, 49, 83, 17, and 36) for one episode. The feature extractor is a 4-layer convolutional network with an additional fully-connected layer for 2D embedding. In Figure 1 left panel, the VD is obtained by setting the centroid of each base class as the Voronoi center. For each novel class, the Voronoi center is simply the 1-shot support sample (Figure 1 central panel). The surrogate representation is computed as the collection of distances from a support/query sample to each of the base classes, as shown in Figure 1 right panel. Interestingly, the surrogate representations for a novel class, no matter if it is a support sample (dotted line) or a query sample (colored line) generally follow a certain pattern — akin within a class, distinct cross class — make them ideal surrogates for distinguishing between different novel classes. In our paper, we design a series of algorithms answering multiple questions regarding this surrogate representation: how to select base classes for the calculation of surrogate representation, how to combine it with feature representation, and how to integrate it into the overall ensemble workflow.

heading: D MAIN DATASETS
text: For a fair and thorough comparison with previous works, three widely-adopted benchmark datasets are used throughout this paper.
(1) mini-ImageNet (Vinyals et al., 2016) is a shrunk subset of ILSVRC-12 (Russakovsky et al., 2015), consists of 100 classes in which 64 classes for training, 20 classes for testing and 16 classes for validation. Each class has 600 images of size 84× 84× 3. (2) CUB (Welinder et al., 2010) is another benchmark dataset for FSL, especially fine-grained FSL, including 200 species (classes) of birds. CUB is an unbalanced dataset with 58 images in average per class, also of size 84 × 84 × 3. We split all classes into 100 base classes, 50 novel classes, and 50 validation classes, following previous works (Chen et al., 2019a).
(3) tiered-ImageNet (Ren et al., 2018) is another subset of ILSVRC-12 (Russakovsky et al., 2015) but has more images, 779,165 images in total. All images are categorized into 351 base classes, 97 validation classes, and 160 novel classes. The number of images in each class is not always the same, 1281 in average. The image size is also 84× 84× 3.
E DEEPVORO--: INTEGRATING PARAMETRIC AND NONPARAMETRIC METHODS VIA CIVD
Table E.3: Cluster-induced Voronoi Diagram (CIVD) for the integration of parametric Logistic Regression (LR) and nonparametric nearest neighbor (i.e. Voronoi Diagram, VD) methods. The results from S2M2 R and DC are also included in this table but excluded for comparison. Best result is marked in bold.
Methods mini-Imagenet CUB tiered-ImageNet
5-way 1-shot 5-way 5-shot 5-way 1-shot 5-way 5-shot 5-way 1-shot 5-way 5-shot
S2M2 R 64.65 ± 0.45 83.20 ± 0.30 80.14 ± 0.45 90.99 ± 0.23 68.12 ± 0.52 86.71 ± 0.34 DC 67.79 ± 0.45 83.69 ± 0.31 79.93 ± 0.46 90.77 ± 0.24 74.24 ± 0.50 88.38 ± 0.31 Power-LR 65.45 ± 0.44 84.47 ± 0.29 79.66 ± 0.44 91.62 ± 0.22 73.57 ± 0.48 89.07 ± 0.29 Voronoi-LR 65.58 ± 0.44 84.51 ± 0.29 79.63 ± 0.44 91.61 ± 0.22 73.65 ± 0.48 89.15 ± 0.29 VD 65.37 ± 0.44 84.37 ± 0.29 78.57 ± 0.44 91.31 ± 0.23 72.83 ± 0.49 88.58 ± 0.29
CIVD-based DeepVoro--
VD + Power-LR 65.63 ± 0.44 84.25 ± 0.30 79.52 ± 0.43 91.52 ± 0.22 73.68 ± 0.48 88.71 ± 0.29 VD + Voronoi-LR 65.85 ± 0.43 84.66 ± 0.29 79.40 ± 0.44 91.57 ± 0.22 73.78 ± 0.48 89.02 ± 0.29

heading: E.1 EXPERIMENTAL SETUP AND IMPLEMENTATION DETAILS
text: In this section, we first establish three few-shot classification models with different underlying geometric structures, two logistic regression (LR) models and one nearest neighbor model: (1) Power Diagram-based LR (Power-LR), (2) Voronoi Diagram-based LR (Voronoi-LR), and (3) Voronoi Diagram (VD). Then, the main purposes of our analysis are (1) to examine how the performance is affected by the proposed Voronoi Reduction method in Sec. 3.2, and (2) to inspect whether VD can be integrated with Power/Voronoi Diagram-based LRs.
The feature transformation used throughout this section is Pw,b,λ with w = 1.0, b = 0.0, λ = 0.5. For Power-LR, we train it directly on the transformedK-wayN -shot support samples using PyTorch library with an Adam optimizer with batch size at 64 and learning rate at 0.01. For Voronoi-LR, the vanilla LR is retrofitted as shown in Algorithm 1, in which the bias is given by Theorem 3.1 to make sure that the parameters induce a VD in each iteration.
In our CIVD model in Definition 3.2, we use a cluster instead of a single prototype to stand for a novel class. Here this cluster contains two points, i.e. Ck = {ck, c̃k}, in which ck is obtained from VD, and c̃k is acquired from Power-LR or Voronoi-LR. The question we intend to answer here is that whether Power-LR or Voronoi-LR is the suitable model for the integration.
Algorithm 1: Voronoi Diagram-based Logistic Regression. Data: Support Set S Result: W 1 Initialize W ←W (0); 2 for epoch← 1, ..., #epoch do 3 bk ← − 14 ||Wk|| 2 2,∀k = 1, ...,K ; / Apply Theorem 3.1 4 Compute loss L(W , b) ; / forward propagation 5 Update W ; / backward propagation 6 end 7 return W
40 20 0 20
60
40
20
0
20
40
60
80 A. No Transformation
40 20 0 20 60
40
20
0
20
40
60
80 B. L2 Normalization
100 50 0
40
20
0
20
40
C. Power Transformation
40 60 80
40
20
0
20
40
D. Log Transformation
Figure F.1: The t-SNE visualizations of (A) original features, (B) L2 normalization, (C) Tukey’s Ladder of Powers Transformation with λ = 0.5, and (D) compositional transformation with λ = 0, w = 1, b = 0.04 of 5 novel classes from mini-ImageNet dataset.

heading: E.2 RESULTS
text: The results are shown in Table E.3. Interestingly, when integrated with VD, Power-LR never reaches the best result, suggesting that VD and LR are intrinsic different geometric models, and cannot be simply integrated together without additional effort. On mini-ImageNet and tiered-ImageNet datasets, the best results are achieved by either Voronoi-LR or VD+Voronoi-LR, showing that CIVD coupled with the proposed Voronoi reduction can ideally integrate parametric and nonparametric few-shot models. Notably, on these two datasets, when Power-LR is reduced to Voronoi-LR, although the number of parameters is decreased (b is directly given by Theorem 3.1, not involved in the optimization), the performance is always better, for example, increases from 65.45% to 65.58% on 5-way 1-shot mini-ImageNet data. On CUB dataset, results of different models are similar, probably because CUB is a fine-grained dataset and all classes are similar to each other (all birds).

heading: F DEEPVORO: IMPROVING FSL VIA HIERARCHICAL HETEROGENEITIES

heading: F.1 EXPERIMENTAL SETUP AND IMPLEMENTATION DETAILS
text: In this section we describe feature-level and transformation-level heterogeneities that are used for ensemble in order to improve FSL. See the next section for geometry-level heterogeneity.
Feature-level heterogeneity. Considering the reproducibility of the methodology, we only employ deterministic data augmentation upon the images without randomness involved. Specifically, three kinds of data augmentation techniques are used. (1) Rotation is an important augmentation method widely used in self-supervised learning (Mangla et al., 2020). Rotating the original images by 0°, 90°, 180°, and 270°gives us four ways of augmentation. (2) After rotation, we can flip the images horizontally, giving rise to additional two choices after each rotation degree. (3) Central cropping after scaling can alter the resolution and focus area of the image. Scaling the original images to (84+B)×(84+B),B increasing from 0 to 70 with step 10, bringing us eight ways of augmentation.
Finally, different combinations of the three types result in 64 kinds of augmentation methods (i.e. |{T}| = 64). Transformation-level heterogeneity. In our compositional transformation, the function (hλ◦gw,b◦ f)(z) is parameterized by w, b, λ. Since g is appended after the L2 normalization f , the vector comes into g is always a unit vector, so we simply set w = 1. For the different combinations of λ and b, we test different values with either λ = 0 or λ 6= 0 on the hold-out validation set (as shown in Figure 2 and K.12), and pick top-8 combinations with the best performance on the validation set.
Ensemble Schemes. Now, in our configuration pool {T} × {Pw,b,λ}, there are 512 possible configurations {ρ(i)}512i=1. For each ρ, we apply it on both the testing and the validation sets. With this large pool of ensemble candidates, how and whether to select a subset {ρ(i)}L′i=1 ⊆ {ρ(i)}512i=1 is still a nontrivial problem. Here we explore three different schemes. (1) Full (vanilla) ensemble. All candidates in {ρ(i)}512i=1 are taken into consideration and then plugged into Definition 3.5 to build the CIVD for space partition. (2) Random ensemble. A randomly selected subset with size L′ < L is used for ensemble. (3) Guided ensemble. We expect the performance for {ρ(i)}512i=1 on the validation set can be used to guide the selection of {ρ(i)}L′i=1 from the testing set, provided that there is good correlation between the testing set and the validation set. Specifically, we rank the configurations in the validation set with regard to their performance, and add them sequentially into {ρ(i)}L′i=1 until a maximum ensemble performance is reached on the validation set, then we use this configuration set for the final ensemble. Since VD is nonparametric and fast, we adopt VD as the building block and only use VD for each ρ for the remaining part of the paper. The α value in the influence function (Definition 3.3) is set at 1 throughout the paper, for the simplicity of computation.
For a fair comparison, we downloaded the trained models1 used by Mangla et al. (2020) and Yang et al. (2021). The performance of FSL algorithms is typically evaluated by a sequence of independent episodes, so the data split and random seed for the selection of novel classes as well as support/query set in each episode will all lead to different result. To ensure the fairness of our evaluation, DC (Yang et al., 2021), and S2M2 R (Mangla et al., 2020) are reevaluated with the same data split and random seed as DeepVoro. The results are obtained by running 2000 episodes and the average accuracy as well as 95% confidence intervals are reported.

heading: F.2 RESULTS
text: Table F.4: Ablation study of DeepVoro’s performance with different levels of ensemble. The number of ensemble members are given in parentheses.
Methods Feature-level Transformation-level mini-ImageNet CUB tiered-ImageNet
1-shot 5-shot 1-shot 5-shot 1-shot 5-shot
No Ensemble 8 8 65.37 ± 0.44 84.37 ± 0.29 78.57 ± 0.44 91.31 ± 0.23 72.83 ± 0.49 88.58 ± 0.29 Vanilla Ensemble (8) 8 4 66.45 ± 0.44 84.55 ± 0.29 80.98 ± 0.44 91.47 ± 0.22 74.02 ± 0.49 88.90 ± 0.29 Vanilla Ensemble (64) 4 8 67.88 ± 0.45 86.39 ± 0.29 77.30 ± 0.43 91.26 ± 0.23 73.74 ± 0.49 88.67 ± 0.29 Vanilla Ensemble (512) 4 4 69.23 ± 0.45 86.70 ± 0.28 79.90 ± 0.43 91.70 ± 0.22 74.51 ± 0.48 89.11 ± 0.29 Random Ensemble (512) 4 4 69.30 ± 0.45 86.74 ± 0.28 80.40 ± 0.43 91.94 ± 0.22 74.64 ± 0.48 89.15 ± 0.29 Guided Ensemble (512) 4 4 69.48 ± 0.45 86.75 ± 0.28 82.99 ± 0.43 92.62 ± 0.22 74.98 ± 0.48 89.40 ± 0.29
Our proposed compositional transformation enlarges the expressivity of the transformation function. When the Tukey’s ladder of powers transformation is used individually, as reported in Yang et al. (2021), the optimal λ is not 0, but if an additional linear transformation g is inserted between f and h, λ = 0 coupled with a proper b can give even better result, as shown in Figure 2 and K.12. Importantly, from Figure 2, a combination of λ and b with good performance on the validation set can also produce satisfactory result on the testing set, suggesting that it is possible to optimize the hyperparameters on the validation set and generalize well on the testing set. In terms of the polymorphism induced by various transformations in the feature space, Figure F.1 exhibits the t-SNE visualizations of the original features and the features after three different kinds of transformations, showing that the relative positions of different novel classes is largely changes especially after compositional transformation (as shown in D). Besides commonly used data augmentation, this transformation provides another level of diversity that may be beneficial to the subsequent ensemble.
The results for different levels of ensemble are shown in Table F.4, in which the number of ensemble member are also indicated. Although transformation ensemble does not involve any change to the feature, it can largely improve the results for 1-shot FSL, from 65.37% to 66.45% on mini-ImageNet,
1downloaded from https://github.com/nupurkmr9/S2M2_fewshot
from 78.57% to 80.98% on CUB, and from 72.83% to 74.02% on tiered-ImageNet, respectively, probably because 1-shot FSL is more prone to overfitting due to its severe data deficiency. Featurelevel ensemble, on the other hand, is more important for 5-shot FSL, especially for mini-ImageNet. When combining the two levels together, the number of ensemble members increases to 512 and the performance significantly surpasses each individual level. On all three datasets, the guided ensemble scheme always achieves the best result for both single-shot and multi-shot cases, showing that the validation set can indeed be used for the guidance of subset selection and our method is robust cross classes in the same domain. When there is no such validation set available, the full ensemble and random ensemble schemes can also give comparable result.
To inspect how performance changes with different number of ensemble members, we exhibit the distribution of accuracy at three ensemble levels for mini-ImageNet in Figure F.2 and F.3 , for CUB in Figure F.4 and F.5, and for tiered-ImageNet in Figure F.6 and F.7. Figure (b) in each of them also exhibits the correlation between the testing and validation sets for all 512 configurations. Clearly, better result is often reached when there are more configurations for the ensemble, validating the efficacy of our method for improving the performance and robustness for better FSL. Algorithm 2: VD with Surrogate Representation for Episode T .
Data: Base classes D, Support Set S = {(xi, yi)}K×Ni=1 , yi ∈ CT , query sample x Result: d̃
1 D′ ← (Pw,b,λ ◦ φ ◦ T )(D) ; / Extract and transform feature 2 S ′ ← (Pw,b,λ ◦ φ ◦ T )(S); 3 z ← (Pw,b,λ ◦ φ ◦ T )(x); 4 for t← 1, ..., |Cbase|; / Compute prototypes of base classes 5 do 6 c′t ← 1|{(z′,y)|z′∈D′,y=t}| ∑ z′∈D′,y=tz ′ 7 end 8 for k ← 1, ...,K; / Compute prototypes from support samples 9 do
10 ck ← 1N ∑ z′∈S′,y=k z ′; 11 dk ← d(z, ck) 12 end 13 Csurrogate ← ∅; 14 for k ← 1, ...,K; / Find surrogate classes 15 do 16 Csurrogate ← Csurrogate ⋃ Top-R
t∈{1,...,|Cbase|} d(ck, c
′ t)
17 end 18 R̃← |Csurrogate|; 19 d′ ← (d(z, c′1), ..., d(z, c′R̃)) ; / Compute surrogate representation for query sample 20 for k ← 1, ...,K; / Compute surrogate representations for support samples 21 do 22 d′k ← (d(ck, c′1), ..., d(ck, c′R̃)); 23 d′′k ← d(d′,d′k) 24 end 25 d̃← β d||d||1 + γ d′′ ||d′′||1 ; / Compute final criterion 26 return d̃
1 2 3 4 5 6 7 8 Number of Ensemble Members
84.35
84.40
84.45
84.50
84.55
84.60
Ac cu
ra cy
mini-ImageNet transformation-level Ensemble Full Ensemble
(a) Transformation-level Ensemble
82 83 84 85 86 87 Testing Set Accuracy
85.0
85.5
86.0
86.5
87.0
87.5
88.0
88.5
Va lid
at io
n Se
t A cc
ur ac
y
Transformation-level Feature-level Dirichlet Tessellation Ensemble DC S2M2-R
mini-ImageNet 5-way 5-shot
Ensemble Ensemble
eepVoro
(b) Testing/Validation Sets Correlation
1 2 3 4 5 6 7 8 9 10111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364 Number of Ensemble Members
84.0
84.5
85.0
85.5
86.0
86.5
Ac cu
ra cy
mini-ImageNet feature-level Ensemble
Full Ensemble
(c) Feature-level Ensemble on 5-way 5-shot mini-ImageNet Dataset
0 100 200 300 400 500 Number of Ensemble Members
84.5
85.0
85.5
86.0
86.5
Ac cu
ra cy
mini-ImageNet Dirichlet Tessellation Ensemble
Random Ensemble Guided Ensemble Full Ensemble
(d) DeepVoro on 5-way 5-shot mini-ImageNet Dataset
Figure F.2: Three levels of ensemble and the correlation between testing and validation sets with different configurations in the configuration pool.
1 2 3 4 5 6 7 8 Number of Ensemble Members
65.4
65.6
65.8
66.0
66.2
66.4
66.6
66.8
Ac cu
ra cy
mini-ImageNet transformation-level Ensemble
Full Ensemble
(a) Transformation-level Ensemble
63 64 65 66 67 68 69 Testing Set Accuracy
66
67
68
69
70
71
72
Va lid
at io
n Se
t A cc
ur ac
y
Transformation-level Feature-level Dirichlet Tessellation Ensemble DC S2M2-R
mini-ImageNet 5-way 1-shot
Ensemble Ensemble
eepVoro
(b) Testing/Validation Sets Correlation
1 2 3 4 5 6 7 8 9 10111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364 Number of Ensemble Members
65.0
65.5
66.0
66.5
67.0
67.5
68.0
Ac cu
ra cy
mini-ImageNet feature-level Ensemble
Full Ensemble
(c) Feature-level Ensemble on 5-way 1-shot mini-ImageNet Dataset
0 100 200 300 400 500 Number of Ensemble Members
66.0
66.5
67.0
67.5
68.0
68.5
69.0
69.5
Ac cu
ra cy
mini-ImageNet Dirichlet Tessellation Ensemble
Random Ensemble Guided Ensemble Full Ensemble
(d) DeepVoro on 5-way 1-shot mini-ImageNet Dataset
Figure F.3: Three levels of ensemble and the correlation between testing and validation sets with different configurations in the configuration pool.
1 2 3 4 5 6 7 8 Number of Ensemble Members
90.6
90.8
91.0
91.2
91.4
91.6
Ac cu
ra cy
CUB transformation-level Ensemble Full Ensemble
(a) Transformation-level Ensemble
82 84 86 88 90 92 Testing Set Accuracy
80
82
84
86
88
90
92
Va lid
at io
n Se
t A cc
ur ac
y
Transformation-level Feature-level Dirichlet Tessellation Ensemble DC S2M2-R
CUB 5-way 5-shot
Ensemble Ensemble
eepVoro
(b) Testing/Validation Sets Correlation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 Number of Ensemble Members
84
86
88
90
92
Ac cu
ra cy
CUB feature-level Ensemble Full Ensemble
(c) Feature-level Ensemble on 5-way 5-shot CUB Dataset
0 100 200 300 400 500 Number of Ensemble Members
86
88
90
92
Ac cu
ra cy
CUB Dirichlet Tessellation Ensemble
Random Ensemble Guided Ensemble Full Ensemble
(d) DeepVoro on 5-way 5-shot CUB Dataset
Figure F.4: Three levels of ensemble and the correlation between testing and validation sets with different configurations in the configuration pool.
1 2 3 4 5 6 7 8 Number of Ensemble Members
79.50
79.75
80.00
80.25
80.50
80.75
81.00
81.25
81.50
Ac cu
ra cy
CUB transformation-level Ensemble Full Ensemble
(a) Transformation-level Ensemble
62.5 65.0 67.5 70.0 72.5 75.0 77.5 80.0 82.5 Testing Set Accuracy
62.5
65.0
67.5
70.0
72.5
75.0
77.5
80.0
82.5
Va lid
at io
n Se
t A cc
ur ac
y
Transformation-level Feature-level Dirichlet Tessellation Ensemble DC S2M2-R
CUB 5-way 1-shot
Ensemble Ensemble
eepVoro
(b) Testing/Validation Sets Correlation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 Number of Ensemble Members
68
70
72
74
76
78
80
Ac cu
ra cy
CUB feature-level Ensemble Full Ensemble
(c) Feature-level Ensemble on 5-way 1-shot CUB Dataset
0 100 200 300 400 500 Number of Ensemble Members
67.5
70.0
72.5
75.0
77.5
80.0
82.5
Ac cu
ra cy
CUB Dirichlet Tessellation Ensemble
Random Ensemble Guided Ensemble Full Ensemble
(d) DeepVoro on 5-way 1-shot CUB Dataset
Figure F.5: Three levels of ensemble and the correlation between testing and validation sets with different configurations in the configuration pool.
1 2 3 4 5 6 7 8 Number of Ensemble Members
88.65
88.70
88.75
88.80
88.85
88.90
88.95
Ac cu
ra cy
tiered-ImageNet transformation-level Ensemble
Full Ensemble
(a) Transformation-level Ensemble
85 86 87 88 89 90 Testing Set Accuracy
83
84
85
86
87
Va lid
at io
n Se
t A cc
ur ac
y
Transformation-level Feature-level Dirichlet Tessellation Ensemble DC S2M2-R
tiered-ImageNet 5-way 5-shot
Ensemble Ensemble
eepVoro
(b) Testing/Validation Sets Correlation
1 2 3 4 5 6 7 8 9 10111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364 Number of Ensemble Members
86.5
87.0
87.5
88.0
88.5
89.0
Ac cu
ra cy
tiered-ImageNet feature-level Ensemble
Full Ensemble
(c) Feature-level Ensemble on 5-way 5-shot tiered-ImageNet Dataset
0 100 200 300 400 500 Number of Ensemble Members
85
86
87
88
89
Ac cu
ra cy
tiered-ImageNet Dirichlet Tessellation Ensemble
Random Ensemble Guided Ensemble Full Ensemble
(d) DeepVoro on 5-way 5-shot tiered-ImageNet Dataset
Figure F.6: Three levels of ensemble and the correlation between testing and validation sets with different configurations in the configuration pool.
1 2 3 4 5 6 7 8 Number of Ensemble Members
73.2
73.4
73.6
73.8
74.0
Ac cu
ra cy
tiered-ImageNet transformation-level Ensemble
Full Ensemble
(a) Transformation-level Ensemble
68 69 70 71 72 73 74 75 Testing Set Accuracy
65
66
67
68
69
70
71
72
73
Va lid
at io
n Se
t A cc
ur ac
y
Transformation-level Feature-level Dirichlet Tessellation Ensemble DC S2M2-R
tiered-ImageNet 5-way 1-shot
Ensemble Ensemble
eepVoro
(b) Testing/Validation Sets Correlation
1 2 3 4 5 6 7 8 9 10111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364 Number of Ensemble Members
71.0
71.5
72.0
72.5
73.0
73.5
74.0
Ac cu
ra cy
tiered-ImageNet feature-level Ensemble
Full Ensemble
(c) Feature-level Ensemble on 5-way 1-shot tiered-ImageNet Dataset
0 100 200 300 400 500 Number of Ensemble Members
70
71
72
73
74
75
Ac cu
ra cy
tiered-ImageNet Dirichlet Tessellation Ensemble
Random Ensemble Guided Ensemble Full Ensemble
(d) DeepVoro on 5-way 1-shot tiered-ImageNet Dataset
Figure F.7: Three levels of ensemble and the correlation between testing and validation sets with different configurations in the configuration pool.
0 100 200 300 400 Number of Shots
65
70
75
80
85
90
Ac cu
ra cy
1: 65.31%
3: 80.12%
5: 84.05% 7: 85.95% 10: 87.60% 15: 88.91%20: 89.75%
40: 90.63% 100: 91.18% 200: 91.22% 400: 91.55%
Effect of the number of shots on mini-ImageNet dataset
Figure G.8: The accuracy of VD with increasing number of shots on mini-ImageNet dataset.

heading: G DEEPVORO++: FURTHER IMPROVEMENT OF FSL VIA SURROGATE REPRESENTATION

heading: G.1 EXPERIMENTAL SETUP AND IMPLEMENTATION DETAILS
text: In this section, we introduce another layer of heterogeneity, that is, geometry-level, that exists in our surrogate representation. In Definition 3.4, increasing R will enlarge the degree of locality when searching for the top-R surrogate classes. In equation (8), if we set γ = 1 then increasing β will make the model rely more on the feature representation and less on the surrogate representation. In order to weigh up R and β, we perform a grid search for different combinations of R and β on the validation set, as shown in Figure K.13, K.14, and K.15. For each R, we select the β that gives rise to the best result on the validation set, and use this (R, β) on the testing set, resulting in 10 such pairs in total. So there are 10 models in the geometry-level heterogeneity, standing for different degrees of locality. In conjunction with feature-level (64 kinds of augmentations) and transformation-level (here only the top-2 best transformations are used) heterogeneities, now there are 1280 different kinds of configurations in our configuration pool that will be used by the CCVD model. In conclusion, there are overall 512 + 1280 = 1792 configurations for a few-shot episode. Generating∼1800 ensemble candidates is nearly intractable for parametric methods like logistic regression or cosine classifier, which may consume e.g. months for thousands of episodes. However, the VD model is nonparametric and highly efficient, making it empirically possible to collect all the combinations and integrate them all together via CCVD. The complete algorithm for the computation of surrogate representation is shown in Algorithm 2.

heading: G.2 RESULTS
text: The heatmaps for different (R, β) pairs on testing/validation sets are shown in Figure K.13 for miniImageNet, in Figure K.14 for CUB, and in Figure K.15 for tiered-ImageNet, respectively. Basically, the testing and validation set follow the same pattern. When R is small, i.e. only a small number of base classes are used for surrogate, then a higher weight should be placed on feature representation. With a fixed β, increasing R beyond a certain threshold will potentially cause a drop in accuracy, probably because the meaningful similarities is likely to be overwhelmed by the signals from the large volume of irrelevant base classes.
Table G.5: Ablation study of DeepVoro++’s performance with different levels of ensemble. The number of ensemble members are given in parentheses.
Methods Feature-level Transformation-level Geometry-level mini-ImageNet CUB tiered-ImageNet
No Ensemble 8 8 8 65.37 ± 0.44 78.57 ± 0.44 72.83 ± 0.49 Vanilla Ensemble (20) 8 4 4 68.38 ± 0.46 80.70 ± 0.45 74.48 ± 0.50 Vanilla Ensemble (64) 4 8 8 70.95 ± 0.46 81.04 ± 0.44 74.87 ± 0.49 Vanilla Ensemble (1280) 4 4 4 71.24 ± 0.46 81.18 ± 0.44 74.75 ± 0.49 Random Ensemble (1280) 4 4 4 71.34 ± 0.46 81.98 ± 0.43 75.07 ± 0.48 Guided Ensemble (1280) 4 4 4 71.30 ± 0.46 82.95 ± 0.43 75.38 ± 0.48
As shown in Table 3 and G.5, DeepVoro++ further improves upon DeepVoro for 5-way 1-shot FSL by 1.82% and 0.4% on mini-ImageNet and tiered-ImageNet, respectively, and is comparable with DeepVoro on CUB dataset (82.95% vs. 82.99%). Notably, on 5-shot FSL, DeepVoro++ usually causes a drop of accuracy from DeepVoro. To inspect the underlying reason for this behavior, we apply VD on 5-way K-shot FSL with K increasing from 1 to 400 and report the average accuracy in Figure G.8. It can be observed that, in extreme low-shot learning, i.e. K ∈ [1, 5], simply adding one shot makes more prominent contribution to the accuracy, suggesting that the centers obtained from 5-shot samples are much better that those from only 1 sample, so there is no necessity to resort to surrogate representation for multi-shot FSL and we only adopt DeepVoro for 5-shot episodes in the remaining part of this paper.
Ablation study of DeepVoro++ with different levels of ensemble is shown in Table G.5, Figure G.9, G.10, and G.11. All three layers of heterogeneities collaboratively contribute towards the final result. The fully-fledged DeepVoro++ establishes new state-of-the-art performance on all three datasets for 1-shot FSL.
1 2 3 4 5 6 7 8 9 1011121314151617181920 Number of Ensemble Members
67.6
67.8
68.0
68.2
68.4
68.6
Ac cu
ra cy
Surrogate Representation mini-ImageNet transformation/geometry-level Ensemble
Full Ensemble
(a) Transformation-level Ensemble
65 66 67 68 69 70 71 Testing Set Accuracy
74.0
74.5
75.0
75.5
76.0
76.5
77.0
77.5
78.0
Va lid
at io
n Se
t A cc
ur ac
y
Transformation-level Feature-level Dirichlet Tessellation Ensemble
Surrogate Representation mini-ImageNet 5-way 1-shot
Ensemble & G ometry-level Ensemble
eepVoro++
(b) Testing/Validation Sets Correlation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 Number of Ensemble Members
67
68
69
70
71
Ac cu
ra cy
Surrogate Representation mini-ImageNet feature-level Ensemble
Full Ensemble
(c) Feature-level Ensemble on 5-way 1-shot mini-ImageNet Dataset
0 200 400 600 800 1000 1200 Number of Ensemble Members
68.5
69.0
69.5
70.0
70.5
71.0
71.5
Ac cu
ra cy
Surrogate Representation mini-ImageNet Dirichlet Tessellation Ensemble
Random Ensemble Guided Ensemble Full Ensemble
(d) DeepVoro++ on 5-way 1-shot mini-ImageNet Dataset
Figure G.9: Three levels of ensemble and the correlation between testing and validation sets with different configurations in the configuration pool.
1 2 3 4 5 6 7 8 9 1011121314151617181920 Number of Ensemble Members
79.5
80.0
80.5
81.0
Ac cu
ra cy
Surrogate Representation CUB transformation/geometry-level Ensemble
Full Ensemble
(a) Transformation-level Ensemble
65.0 67.5 70.0 72.5 75.0 77.5 80.0 82.5 Testing Set Accuracy
65.0
67.5
70.0
72.5
75.0
77.5
80.0
82.5
85.0
Va lid
at io
n Se
t A cc
ur ac
y
Transformation-level Feature-level Dirichlet Tessellation Ensemble
Surrogate Representation CUB 5-way 1-shot
eepVoro++ Ensemble
& Geometry-level Ensemble
(b) Testing/Validation Sets Correlation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 Number of Ensemble Members
67.5
70.0
72.5
75.0
77.5
80.0
82.5
Ac cu
ra cy
Surrogate Representation CUB feature-level Ensemble
Full Ensemble
(c) Feature-level Ensemble on 5-way 1-shot CUB Dataset
0 200 400 600 800 1000 1200 Number of Ensemble Members
72
74
76
78
80
82
Ac cu
ra cy
Surrogate Representation CUB Dirichlet Tessellation Ensemble
Random Ensemble Guided Ensemble Full Ensemble
(d) DeepVoro++ on 5-way 1-shot CUB Dataset
Figure G.10: Three levels of ensemble and the correlation between testing and validation sets with different configurations in the configuration pool.
1 2 3 4 5 6 7 8 9 1011121314151617181920 Number of Ensemble Members
74.40
74.45
74.50
74.55
74.60
Ac cu
ra cy
Surrogate Representation tiered-ImageNet transformation/geometry-level Ensemble
Full Ensemble
(a) Transformation-level Ensemble
71 72 73 74 75 Testing Set Accuracy
68
69
70
71
72
73
74
Va lid
at io
n Se
t A cc
ur ac
y
Transformation-level Feature-level Dirichlet Tessellation Ensemble
Surrogate Representation tiered-ImageNet 5-way 1-shot
Ensemble eepVoro++
& Geometry-level Ensemble
(b) Testing/Validation Sets Correlation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 Number of Ensemble Members
71
72
73
74
75
Ac cu
ra cy
Surrogate Representation tiered-ImageNet feature-level Ensemble
Full Ensemble
(c) Feature-level Ensemble on 5-way 1-shot tiered-ImageNet Dataset
0 200 400 600 800 1000 1200 Number of Ensemble Members
73.0
73.5
74.0
74.5
75.0
75.5
Ac cu
ra cy
Surrogate Representation tiered-ImageNet Dirichlet Tessellation Ensemble
Random Ensemble Guided Ensemble Full Ensemble
(d) DeepVoro++ on 5-way 1-shot tiered-ImageNet Dataset
Figure G.11: Three levels of ensemble and the correlation between testing and validation sets with different configurations in the configuration pool.

heading: H EXPERIMENTS WITH DIFFERENT BACKBONES
text: H.1 IMPLEMENTATION DETAILS
In order to test the robustness of DeepVoro/DeeoVoro++ with various deep learning architectures, we downloaded the trained models2 used by Wang et al. (2019). We evaluated DC, S2M2 R, DeepVoro, and DeepVoro++ using the same random seed. The results are obtained by running 500 episodes and the average accuracy as well as 95% confidence intervals are reported.

heading: H.2 EXPERIMENTAL RESULTS
text: Table H.6: Comparison of FSL algorithms with different network architectures. WRN-28-10§ was trained with rotation loss and MixUp loss (Mangla et al., 2020) instead of using ordinary softmax loss (WRN-28-10†).
Methods WRN-28-10§ WRN-28-10† 1-shot 5-shot 1-shot 5-shot
DC 67.79 ± 0.45 83.69 ± 0.31 62.09 ± 0.95 78.47 ± 0.67 S2M2 R 64.65 ± 0.45 83.20 ± 0.30 61.11 ± 0.92 79.83 ± 0.64 DeepVoro 69.48 ± 0.45 86.75 ± 0.28 62.26 ± 0.94 82.02 ± 0.63 DeepVoro++ 71.30 ± 0.46 − 65.01 ± 0.98 −
DenseNet-121 ResNet-34
1-shot 5-shot 1-shot 5-shot
DC 62.68 ± 0.96 79.96 ± 0.60 59.10 ± 0.90 74.95 ± 0.67 S2M2 R 60.33 ± 0.92 80.33 ± 0.62 58.92 ± 0.92 77.99 ± 0.64 DeepVoro 60.66 ± 0.91 82.25 ± 0.59 61.61 ± 0.92 81.81 ± 0.60 DeepVoro++ 65.18 ± 0.95 − 64.65 ± 0.96 −
ResNet-18 ResNet-10
1-shot 5-shot 1-shot 5-shot
DC 60.20 ± 0.96 75.59 ± 0.69 59.01 ± 0.92 74.27 ± 0.69 S2M2 R 59.57 ± 0.93 78.69 ± 0.69 57.59 ± 0.92 77.10 ± 0.67 DeepVoro 61.50 ± 0.93 81.58 ± 0.64 58.34 ± 0.93 79.05 ± 0.63 DeepVoro++ 64.79 ± 0.97 − 61.75 ± 0.95 −
MobileNet Conv-4
1-shot 5-shot 1-shot 5-shot
DC 59.41 ± 0.91 76.07 ± 0.66 49.32 ± 0.87 62.89 ± 0.71 S2M2 R 58.36 ± 0.93 76.75 ± 0.68 45.19 ± 0.87 64.56 ± 0.74 DeepVoro 60.91 ± 0.93 80.14 ± 0.65 48.47 ± 0.86 65.86 ± 0.73 DeepVoro++ 63.37 ± 0.95 − 52.15 ± 0.98 −
On Wide residual networks (WRN-28-10) (Zagoruyko & Komodakis, 2016), Residual networks (ResNet-10/18/34) (He et al., 2016), Dense convolutional networks (DenseNet-121) (Huang et al., 2017), and MobileNet (Howard et al., 2017), DeepVoro/DeepVoro++ shows a consistent improvement upon DC and S2M2 R. Excluding DeepVoro/DeepVoro++, there is no such a method that is always better for both 5-shot and 1-shot FSL. Generally, DC is expert in 1-shot while S2M2 2 favors 5-shot. According to Table 3, we do not apply DeepVoro++ on 5-shot FSL since DeepVoro usually outperforms DeepVoro++ with more shots available.

heading: I EXPERIMENTS WITH DIFFERENT TRAINING PROCEDURES

heading: I.1 EXPERIMENTAL SETUP AND IMPLEMENTATION DETAILS
text: Our geometric space partition model is built on top of a pretrained feature extractor, and the quality of the feature extractor will significantly affect the downstream FSL (Mangla et al., 2020). Here we used another two feature extractors trained with different schemes. (1) Manifold Mixup training employs an additional Mixup loss that interpolates the data and the label simultaneously and can
2downloaded from https://github.com/mileyan/simple_shot
help deep neural network generalize better. (2) Rotation loss is widely used especially in selfsupervised learning in which the network learns to predict the degree by which an image is rotated. We downloaded the corresponding pretrained models used by Mangla et al. (2020) and Yang et al. (2021) and evaluate the four methods by 500 episodes.

heading: I.2 RESULTS
text: As shown in Table I.7, DeepVoro/DeepVoro++ achieves best results for both rotation loss and Mixup loss. Interestingly, there is a substantial gap between the two training schemes when they are used out-of-the-box for downstream FSL (4accuracy = 10.22% for 1-shot and 4accuracy = 6.52% for 5-shot), but after DeepVoro/DeepVoro++, this gap becomes narrowed (4accuracy = 3.98% for 1-shot and 4accuracy = 2.51% for 5-shot), suggesting the strength of DeepVoro/DeepVoro++ to make the most of the pretrained models

heading: J CROSS DOMAIN FEW-SHOT LEARNING

heading: J.1 EXPERIMENTAL SETUP AND IMPLEMENTATION DETAILS
text: Cross-domain FSL is more challenging than FSL in which base classes and novel classes come from essentially distinct domains. To examine the ability of our method for cross-domain FSL, we apply the feature extractor trained on mini-ImageNet (CUB) on the few-shot data in CUB (mini-ImageNet) for coarse-to-fine (fine-to-coarse) domain shifting.

heading: J.2 RESULTS
text: Table J.8: Comparison of performance on cross-domain FSL. Methods CUB⇒ mini-ImageNet mini-ImageNet⇒ CUB
1-shot 5-shot 1-shot 5-shot
DC 46.25 ± 0.93 62.99 ± 0.81 54.64 ± 0.87 72.83 ± 0.71 S2M2 R 41.15 ± 0.84 58.09 ± 0.79 49.01 ± 0.88 69.99 ± 0.71 DeepVoro 46.15 ± 0.90 64.60 ± 0.80 49.03 ± 0.87 72.30 ± 0.74 DeepVoro++ 47.83 ± 0.97 − 54.88 ± 0.92 −
Basically, DeepVoro/DeepVoro++ is more stable than the other two method with a shifting domain, especially on fine-to-coarse FSL (CUB to mini-ImageNet), with an improvement of 6.68% for 1- shot and 6.51% for 5-shot than S2M2 R, and is comparable with DC on coarse-to-fine FSL (miniImageNet to CUB).
K ADDITIONAL FIGURES
0.5 1.0 0
83
84
85
86
87
88
89
0.05 0.10 b ( = 0)
Validation Testing
tiered-ImageNet 5-way 5-shot
0.5 1.0 0
62
64
66
68
70
72
74
0.05 0.10 b ( = 0)
Validation Testing
tiered-ImageNet 5-way 1-shot
Figure K.12: The 5-way few-shot accuracy of VD with different λ and b values on tiered-ImageNet datasets.
1 2 3 4 5 6 7 8 9 10 R
0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 4.5 5.0 5.5 6.0 6.5 7.0
66.43 66.69 66.91 67.01 67.15 67.25 66.28 66.78 67.17 67.39 67.56 67.62 67.72 67.75 66.93 67.27 67.58 67.71 67.88 67.93 68.01 68.00 66.59 67.28 67.54 67.76 67.92 68.05 68.10 68.10 68.11 66.95 67.49 67.73 67.87 68.02 68.07 68.13 68.16 68.14 67.21 67.68 67.80 67.93 68.06 68.08 68.08 68.09 68.09 67.39 67.78 67.83 67.94 68.02 68.05 68.05 68.04 68.04 66.40 67.47 67.82 67.83 67.93 67.98 68.01 67.99 67.98 67.97 66.61 67.54 67.82 67.82 67.90 67.94 67.99 67.92 67.90 67.89 66.76 67.57 67.76 67.83 67.87 67.90 67.92 67.87 67.85 67.84 66.92 67.54 67.78 67.82 67.82 67.84 67.86 67.80 67.79 67.75 67.01 67.57 67.73 67.80 67.78 67.78 67.79 67.74 67.73 67.71 67.07 67.56 67.72 67.76 67.71 67.74 67.70 67.66 67.66 67.62
mini-ImageNet 5-way 1-shot Test Set
1 2 3 4 5 6 7 8 9 10 R
69.75 69.77 69.74 70.21 70.41 70.53 70.58 70.63 70.69 70.68 70.53 70.93 70.99 71.08 71.11 71.14 71.15 71.12 70.37 70.98 71.29 71.34 71.36 71.37 71.35 71.37 71.32 70.83 71.28 71.45 71.46 71.50 71.49 71.52 71.47 71.41 71.05 71.40 71.52 71.55 71.55 71.55 71.52 71.46 71.41 69.83 71.19 71.46 71.59 71.60 71.57 71.53 71.47 71.41 71.36 70.12 71.25 71.49 71.56 71.56 71.52 71.45 71.40 71.34 71.28 70.39 71.31 71.48 71.50 71.49 71.43 71.38 71.30 71.26 71.21 70.51 71.31 71.44 71.46 71.45 71.38 71.29 71.22 71.21 71.14 70.62 71.33 71.39 71.39 71.38 71.28 71.20 71.12 71.11 71.05 70.68 71.29 71.37 71.29 71.30 71.19 71.10 71.02 71.01 70.95 70.73 71.27 71.29 71.22 71.20 71.12 71.01 70.96 70.91 70.86 70.77 71.25 71.22 71.19 71.11 71.02 70.94 70.87 70.83 70.78
mini-ImageNet 5-way 1-shot Validation Set
Figure K.13: The 5-way 1-shot accuracy with different β and R values on mini-ImageNet testing (left) and validation (right) datasets.
1 2 3 4 5 6 7 8 9 10 R
0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 4.5 5.0 5.5 6.0 6.5 7.0
79.78 79.87 80.03 80.11 80.18 80.18 80.20
79.72 80.04 80.28 80.32 80.39 80.36 80.37 80.36 80.08 80.32 80.45 80.46 80.52 80.48 80.46 80.44 79.84 80.29 80.45 80.52 80.52 80.51 80.47 80.49 80.43 80.11 80.46 80.53 80.56 80.52 80.52 80.46 80.45 80.40 80.23 80.50 80.51 80.54 80.50 80.45 80.45 80.42 80.36 80.32 80.48 80.50 80.50 80.43 80.42 80.42 80.38 80.32 80.32 80.47 80.48 80.46 80.40 80.39 80.35 80.30 80.25 79.79 80.34 80.46 80.44 80.40 80.37 80.32 80.30 80.24 80.19 79.90 80.35 80.40 80.38 80.34 80.32 80.26 80.23 80.19 80.13 79.96 80.36 80.36 80.34 80.28 80.23 80.20 80.18 80.14 80.09 80.02 80.34 80.31 80.30 80.22 80.16 80.13 80.10 80.07 80.02 80.06 80.31 80.28 80.24 80.16 80.13 80.08 80.06 80.01 79.95
CUB 5-way 1-shot Test Set
1 2 3 4 5 6 7 8 9 10 R
77.09 77.11 77.45 77.54 77.70 77.74 77.79 77.31 77.63 77.88 77.96 78.07 78.13 78.13 77.32 77.69 77.96 78.15 78.20 78.26 78.25 78.30 77.10 77.67 77.93 78.13 78.28 78.28 78.35 78.32 78.36 77.48 77.91 78.10 78.22 78.31 78.30 78.36 78.35 78.36 77.74 78.03 78.20 78.29 78.34 78.33 78.36 78.34 78.31 77.87 78.10 78.23 78.29 78.32 78.31 78.30 78.27 78.25 77.07 78.00 78.14 78.21 78.26 78.29 78.24 78.25 78.23 78.17 77.23 78.06 78.14 78.21 78.22 78.24 78.20 78.19 78.16 78.12 77.40 78.12 78.15 78.18 78.19 78.20 78.14 78.12 78.09 78.07 77.51 78.12 78.17 78.14 78.14 78.14 78.11 78.08 78.02 78.01 77.59 78.12 78.15 78.12 78.10 78.11 78.07 78.04 77.97 77.95 77.67 78.14 78.10 78.09 78.07 78.07 78.04 77.99 77.93 77.93
CUB 5-way 1-shot Validation Set
Figure K.14: The 5-way 1-shot accuracy with different β and R values on CUB testing (left) and validation (right) datasets.
1 2 3 4 5 6 7 8 9 10 R
0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 4.5 5.0 5.5 6.0 6.5 7.0 72.04 73.41 73.30 73.04 72.81 72.64 72.42 72.28 72.12 72.04 73.62 73.62 73.51 73.39 73.32 73.21 73.13 72.99 72.91 72.83 73.64 73.72 73.68 73.60 73.53 73.49 73.43 73.35 73.29 73.24 73.62 73.72 73.72 73.66 73.62 73.59 73.57 73.50 73.47 73.43 73.55 73.66 73.67 73.67 73.66 73.67 73.64 73.62 73.59 73.54 73.52 73.59 73.63 73.66 73.64 73.65 73.66 73.65 73.63 73.60 73.46 73.53 73.57 73.60 73.62 73.62 73.63 73.63 73.60 73.58 73.43 73.49 73.53 73.54 73.57 73.61 73.59 73.59 73.60 73.58 73.39 73.46 73.49 73.52 73.55 73.56 73.58 73.57 73.58 73.56 73.34 73.45 73.46 73.49 73.50 73.53 73.53 73.54 73.56 73.55 73.33 73.41 73.42 73.47 73.49 73.49 73.51 73.52 73.52 73.52 73.30 73.39 73.40 73.43 73.47 73.47 73.48 73.49 73.49 73.51 73.26 73.36 73.38 73.41 73.44 73.43 73.44 73.46 73.45 73.46
tiered-ImageNet 5-way 1-shot Test Set
1 2 3 4 5 6 7 8 9 10 R
74.17 73.34 72.59 71.93 71.42 70.95 70.57 70.24 73.43 73.29 73.01 72.68 72.40 72.11 71.87 71.65 71.43 71.25 72.60 72.82 72.72 72.55 72.42 72.21 72.11 71.96 71.82 71.70 71.97 72.26 72.28 72.24 72.14 72.06 72.00 71.91 71.83 71.72 71.49 71.82 71.90 71.92 71.89 71.83 71.78 71.74 71.69 71.62 71.09 71.45 71.58 71.62 71.64 71.64 71.60 71.57 71.50 71.47 70.81 71.17 71.31 71.38 71.40 71.42 71.41 71.40 71.36 71.35 70.56 70.90 71.07 71.15 71.19 71.20 71.22 71.20 71.18 71.18 70.36 70.67 70.86 70.95 71.00 70.98 71.01 71.02 71.01 71.00 70.20 70.50 70.68 70.75 70.80 70.82 70.83 70.84 70.86 70.84 70.07 70.35 70.52 70.60 70.66 70.67 70.71 70.71 70.73 70.70
70.24 70.38 70.45 70.52 70.55 70.57 70.60 70.61 70.60 70.12 70.24 70.36 70.41 70.44 70.44 70.48 70.49 70.49 70.02 70.14 70.24 70.30 70.31 70.34 70.37 70.40 70.41
tiered-ImageNet 5-way 1-shot Validation Set
Figure K.15: The 5-way 1-shot accuracy with different β and R values on tiered-ImageNet testing (left) and validation (right) datasets.
1.4 1.5 1.6 1.7 1.8 1.9 2.0 Geometric Variance of Support Set
70
75
80
85
90
95
Av er
ag e
Ac cu
ra cy
S2M2_R DC DeepVoro
Episode Accuracy as a Function of Geometric Variance
Figure K.16: Outlier Analysis. In order to investigate the resistance to outlier for various methods, we here define Geometric Variance (GV ) as a reflection of the possibility that a support set contains an outlier, due to the difficulty of inferring out-of-distribution sample from merely 1 or 5 samples. Formally, for a support set S = {(zi, yi)}K×Ni=1 , its Geometric Variance is defined as GV (S) = 1 K ∑K k=1 1
(N2 )
∑ i∈{1,...,N},j∈{1,...,N} ||zi − zj ||2, measuring the average point-to-point distance in
this support set. The larger GV is, with higher probability S contains an outlier. For every episode in 2000 episodes from 5-way 5-shot mini-ImageNet data, GV is computed as well as the episode accuracy. As shown in Figure K.16, very highGV causes a significant decrease of episode accuracy, but our method DeepVoro is more resistant to the presence of outliers.

Review summaries:
The paper proposes a CIVD-based approach to few-shot learning. CIVD, cluster-induced Voronoi diagrams, are a known technique that is used to categorize / describe different types of few-shot classifiers. In the experiment section DeepVoro(++) is shown to perform superior to other methods on three datasets.

The paper presents an approach for few-shot (FS) learning using Voronoi Diagrams (VD). In particular, it relates the objectives of existing FS approaches to VD, and shows how Cluster-induced Voronoi Diagrams (CIVD), a variant of VD that allows multiple centers in a cell, can be used in for FS learning ensemble method (DeepVoro). Extensive quantitative evaluations show improvements over prior work  on three public datasets.  

This paper provides a new geometric point of view for few-shot learning (FSL). In this view, the widely used ProtoNet can be regarded as a Dirichlet Tessellation (Voronoi Diagram) in the feature space. Furthermore, the authors use the recent Cluster-induced Voronoi Diagram (CIVD) for FSL and propose an ensemble approach to achieve a stronger FSL model. Extensive experimental results on three standard benchmarks demonstrate the effectiveness of the proposed method.