Yann Lifchitz

Yannis Avrithis

Sylvaine Picard

Local Propagation for Few-Shot Learning

The challenge in few-shot learning is that available data is not enough to capture the underlying distribution. To mitigate this, two emerging directions are (a) using local image representations, essentially multiplying the amount of data by a constant factor, and (b) using more unlabeled data, for instance by transductive inference, jointly on a number of queries. In this work, we bring these two ideas together, introducing local propagation. We treat local image features as independent examples, we build a graph on them and we use it to propagate both the features themselves and the labels, known and unknown. Interestingly, since there is a number of features per image, even a single query gives rise to transductive inference. As a result, we provide a universally safe choice for few-shot inference under both non-transductive and transductive settings, improving accuracy over corresponding methods. This is in contrast to existing solutions, where one needs to choose the method depending on the quantity of available data.

I. INTRODUCTION

Few-shot learning [START_REF] Vinyals | Matching networks for one shot learning[END_REF]- [START_REF] Wang | Low-shot learning from imaginary data[END_REF] is the problem of learning new tasks from few examples, possibly transferring knowledge from previous tasks. Against the mainstream paradigm of having lots of labeled data in deep learning, it limits not only the amount of supervision but also the amount of data. Given the variability of appearance in few-shot image classification benchmarks, learning from few examples without knowledge of the underlying distribution is truly challenging.

Few-shot learning has been little studied before deep learning [START_REF] Bart | Cross-generalization: Learning novel classes from a single example by feature replacement[END_REF]. Research on few-shot learning is recently becoming very popular, but is not very mature. On one hand, it is often connected to meta-learning [START_REF] Vilalta | A perspective view and survey of metalearning[END_REF] in the sense of learning to compare [START_REF] Vinyals | Matching networks for one shot learning[END_REF] or to optimize [START_REF] Finn | Model-agnostic meta-learning for fast adaptation of deep networks[END_REF], giving rise to complex ideas involving second-order derivatives. On the other hand, it boils down to representation learning, using e.g. metric learning [START_REF] Li | Revisiting metric learning for few-shot image classification[END_REF] or parametric classifiers [START_REF] Chen | A closer look at few-shot classification[END_REF], followed by nearest neighbor classifiers at inference [START_REF] Wang | SimpleShot: Revisiting nearest-neighbor classification for few-shot learning[END_REF].

While there are several approaches on generating more data [START_REF] Wang | Low-shot learning from imaginary data[END_REF], [START_REF] Wang | Semi-supervised learning for few-shot image-to-image translation[END_REF], global spatial pooling into compact image representations ignores the rich data that is hidden in each given example. Each image is inherently a collection of data, which has been exploited by dense classification (DC) at representation learning [START_REF] Lifchitz | Dense classification and implanting for few-shot learning[END_REF] and naïve Bayes nearest neighbor (NBNN) [START_REF] Li | Revisiting local descriptor based image-to-class measure for few-shot learning[END_REF] at inference.

Using unlabeled data is another popular direction of research, leveraging existing results from transductive inference [START_REF] Liu | Learning to propagate labels: Transductive propagation network for few-shot learning[END_REF], semi-supervised learning [START_REF] Garcia | Few-shot learning with graph neural networks[END_REF] and self-supervised representation learning [START_REF] Gidaris | Boosting few-shot visual learning with self-supervision[END_REF]. Graph-based methods are at the core of this effort, using for instance label propagation [START_REF] Liu | Learning to propagate labels: Transductive propagation network for few-shot learning[END_REF], feature propagation [START_REF] Rodríguez | Embedding propagation: Smoother manifold for few-shot classification[END_REF] and graph neural networks [START_REF] Garcia | Few-shot learning with graph neural networks[END_REF]. Fig. 1. CUB 5-way 5-shot classification accuracy vs. number of queries per novel class. Our local label propagation outperforms transductive and nontransductive baselines in all settings. By contrast, global label propagation only competes with non-trasductive methods when at least 10 unlabelled queries are available. We use spatial attention (also our contribution) and feature propagation [START_REF] Rodríguez | Embedding propagation: Smoother manifold for few-shot classification[END_REF] for all methods. We use feature pooling for local propagation. Please see section VI for more details.

This work is an attempt to bridge these two ideas, i.e., local representations [START_REF] Li | Revisiting local descriptor based image-to-class measure for few-shot learning[END_REF] and propagation [START_REF] Rodríguez | Embedding propagation: Smoother manifold for few-shot classification[END_REF], into a common framework. Essentially, NBNN [START_REF] Li | Revisiting local descriptor based image-to-class measure for few-shot learning[END_REF] measures the average similarity of local representations of a given image to local representations of all images in a class; while feature or label propagation [START_REF] Rodríguez | Embedding propagation: Smoother manifold for few-shot classification[END_REF] replaces raw (Euclidean) similarities with similarities taking into account the manifold structure of the data distribution, and measures a single manifold similarity of a given image to a class. Our local propagation combines both by measuring the average manifold similarity of local representations of a given image to local representations of all images in a class.

Concretely, we learn a representation using DC [START_REF] Lifchitz | Dense classification and implanting for few-shot learning[END_REF] and we apply local propagation at inference, without meta-learning: We break down the convolutional activations of support and query images into pieces corresponding to different spatial positions, consider all these pieces as different examples, and then apply feature or label propagation [START_REF] Rodríguez | Embedding propagation: Smoother manifold for few-shot classification[END_REF] to these examples. Pieces originating in support examples inherit their labels as in DC [START_REF] Lifchitz | Dense classification and implanting for few-shot learning[END_REF] and NBNN [START_REF] Li | Revisiting local descriptor based image-to-class measure for few-shot learning[END_REF], while pieces originating in queries are unlabeled. Since there are a number of unlabeled pieces per image, this gives rise to transductive inference even in the case of a single query image. As shown in Figure 1, this means that our method is a universally safe choice regardless of the amount of available unlabeled data.

In summary, we make the following contributions:

• We study graph-based propagation on local (pixel) and semi-local (clusters) representations across of images for feature and label propagation for the first time. • We apply this idea to few-shot learning, effectively generating more data and propagating through it, bringing even the case of single queries into transductive inference. • We show that an extremely simple spatial attention mechanism is not only essential in our local propagation, but also brings significant gains in all baselines. • We show consistent gains in most datasets and settings, including transductive and non-transductive.

II. RELATED WORK

Few shot learning. While studies before deep learning have been scarce [START_REF] Bart | Cross-generalization: Learning novel classes from a single example by feature replacement[END_REF], [START_REF] Miller | Learning from one example through shared densities on transforms[END_REF], [START_REF] Fei-Fei | A Bayesian approach to unsupervised one-shot learning of object categories[END_REF], few-shot learning has become a very popular problem beginning mainly from matching networks [START_REF] Vinyals | Matching networks for one shot learning[END_REF] and prototypical networks [START_REF] Snell | Prototypical networks for few-shot learning[END_REF]. Seen as a metalearning problem of learning to compare in episodes, these solutions amount essentially to metric learning, and indeed such methods have been revisited in the context of fewshot learning [START_REF] Li | Revisiting metric learning for few-shot image classification[END_REF], [START_REF] Wu | Improving generalization via scalable neighborhood component analysis[END_REF]. Simpler methods have highlighted the importance of representation learning. These include for instance nearest-neighbor classifiers without meta-learning [START_REF] Wang | SimpleShot: Revisiting nearest-neighbor classification for few-shot learning[END_REF] and simple variants of supervised classifiers like a cosine classifier [START_REF] Chen | A closer look at few-shot classification[END_REF], [START_REF] Qi | Low-shot learning with imprinted weights[END_REF], [START_REF] Gidaris | Dynamic few-shot visual learning without forgetting[END_REF]. More data. Since the main challenge in few-shot learning is the lack of data, several approaches focus on finding more. These include augmentation in the feature space [START_REF] Mangla | Charting the right manifold: Manifold mixup for few-shot learning[END_REF] or by combining spatial elements of images [START_REF] Seo | Self-augmentation: Generalizing deep networks to unseen classes for few-shot learning[END_REF], [START_REF] Le | Continual local replacement for few-shot learning[END_REF], generation in the feature space [START_REF] Wang | Low-shot learning from imaginary data[END_REF] or images [START_REF] Chen | Semantic feature augmentation in few-shot learning[END_REF], [START_REF] Zhang | metagan): an adversarial approach to few-shot learning[END_REF], image-to-image translation [START_REF] Wang | Semi-supervised learning for few-shot image-to-image translation[END_REF], [START_REF] Liu | Few-shot unsupervised image-to-image translation[END_REF], using base-class data [START_REF] Li | Few-shot learning with global class representations[END_REF], [START_REF] Afrasiyabi | Associative alignment for few-shot image classification[END_REF], or even true additional data, unlabeled [START_REF] Douze | Low-shot learning with large-scale diffusion[END_REF] or weakly labeled [START_REF] Iscen | Graph convolutional networks for learning with few clean and many noisy labels[END_REF]. By contrast, we generate more data "for free" by just looking more carefully within the existing data.

Transductive inference. Another possibility is to consider multiple queries jointly and exploit their distribution, even though they are unlabeled. This gives rise to transductive inference [START_REF] Liu | Learning to propagate labels: Transductive propagation network for few-shot learning[END_REF], [START_REF] Rohrbach | Transfer learning in a transductive setting[END_REF], [START_REF] Nichol | On first-order meta-learning algorithms[END_REF]. Most well-known are transductive propagation networks (TPN) [START_REF] Liu | Learning to propagate labels: Transductive propagation network for few-shot learning[END_REF], which use label propagation [START_REF] Zhou | Learning with local and global consistency[END_REF] in a meta-learning setting. Recently, this direction is becoming very popular [START_REF] Rodríguez | Embedding propagation: Smoother manifold for few-shot classification[END_REF], [START_REF] Kim | Edge-labeling graph neural network for few-shot learning[END_REF]- [START_REF] Yang | DPGN: Distribution propagation graph network for few-shot learning[END_REF]. Most related to our work is the very recent embedding propagation [START_REF] Rodríguez | Embedding propagation: Smoother manifold for few-shot classification[END_REF], which propagates the features as well as the labels. We do the same without meta-learning and most importantly, all propagation is local.

Semi/self-supervised learning. Using unlabeled data in an inductive setting gives rise to semi-supervised learning by using pseudo-labels [START_REF] Ren | Meta-learning for semi-supervised fewshot classification[END_REF], graph-based methods [START_REF] Garcia | Few-shot learning with graph neural networks[END_REF], or feature-space augmentation [START_REF] Mangla | Charting the right manifold: Manifold mixup for few-shot learning[END_REF], [START_REF] Yu | TransMatch: A transferlearning scheme for semi-supervised few-shot learning[END_REF]. It is also common to use auxiliary unsupervised objectives like rotation [START_REF] Gidaris | Boosting few-shot visual learning with self-supervision[END_REF], [START_REF] Mangla | Charting the right manifold: Manifold mixup for few-shot learning[END_REF]. While we do not address an inductive setting, our work is a direct extension of graph-based methods, hence it can be applied to an inductive setting too, much like label propagation itself [START_REF] Iscen | Label propagation for deep semi-supervised learning[END_REF], or combined with any other objective. Attention. It is common to use attention and adaptation mechanisms in the feature space [START_REF] Vinyals | Matching networks for one shot learning[END_REF], [START_REF] Gidaris | Dynamic few-shot visual learning without forgetting[END_REF], [START_REF] Mishra | A simple neural attentive meta-learner[END_REF]- [START_REF] Li | Finding taskrelevant features for few-shot learning by category traversal[END_REF]. However, despite being the subject of a pioneering work in 2005 [START_REF] Bart | Cross-generalization: Learning novel classes from a single example by feature replacement[END_REF], looking at local information in images has not been studied more recently in few-shot learning, until dense classification (DC) [START_REF] Lifchitz | Dense classification and implanting for few-shot learning[END_REF] and naïve Bayes nearest neighbor (NBNN) [START_REF] Li | Revisiting local descriptor based image-to-class measure for few-shot learning[END_REF]. We use the former for representation learning. The latter is similar to our work in using local representations at inference, the difference being that we apply propagation. These works have been followed by studies on spatial attention [START_REF] Wertheimer | Few-shot learning with localization in realistic settings[END_REF]- [START_REF] Lifchitz | Few-shot few-shot learning and the role of spatial attention[END_REF] and alignment [START_REF] Hou | Cross attention network for few-shot classification[END_REF]- [START_REF] Zhang | DeepEMD: Few-shot image classification with differentiable earth mover's distance and structured classifiers[END_REF]. We experiment with an extremely simple spatial attention mechanism in this work, which requires no learning and boosts significantly all baselines.

Local propagation. Whatever is propagated (similarities, features, or labels), there are two extremes in graph-based propagation. At one extreme, vertices are global representations of images, and the graph represents a dataset. This can be used e.g. for similarity search [START_REF] Zhou | Ranking on data manifolds[END_REF] or semi-supervised classification [START_REF] Zhou | Learning with local and global consistency[END_REF], [START_REF] Zhu | Learning from labeled and unlabeled data with label propagation[END_REF]. At the other extreme, vertices are local representations of pixels in an image, which can be used e.g.

for interactive [START_REF] Grady | Random walks for image segmentation[END_REF], [START_REF] Kim | Generative image segmentation using random walks with restart[END_REF] or semantic [START_REF] Bertasius | Convolutional random walk networks for semantic image segmentation[END_REF] segmentation, or both [START_REF] Vernaza | Learning random-walk label propagation for weakly-supervised semantic segmentation[END_REF]. Regional representations across images have been used for similarity search [START_REF] Iscen | Efficient diffusion on region manifolds: Recovering small objects with compact cnn representations[END_REF], but we believe we are the first to use local (pixel) or semi-local (clusters) representations across images for feature or label propagation.

III. PRELIMINARIES

Problem. A few-shot classification task comprises a dataset D := {(x i , y i )} n i=1 of support examples x i ∈ X and labels y i , where X is an input space. Each label is represented by a one-hot vector y i := e i , where {e j } c j=1 is the standard basis of R c , i ∈ C is a label index and C := [c] := {1, . . . , c} is a set of novel (unseen) classes. The number n of support examples is assumed to be small. The most common setting is s examples per novel class, with e.g. s ∈ {1, 5, 10}, so that n = cs, referred to as c-way, s-shot classification. The objective of the task is to learn a classifier f : X → R c + on the support data D. This classifier maps a new query example x from X to a probability distribution p = f (x). A discrete prediction π(p) in C follows, where

π(p) := arg max j∈[c] p j (1)
is the class of of maximum probability and p j is the j-th element of p.

Before we are presented with few-shot classification tasks, we are given a dataset

Ḋ := {( ẋi , ẏi )} ṅ i=1 of training examples ẋi ∈ X and labels ẏi := e ˙ i , where ˙ i ∈ Ċ and Ċ := [ ċ] is a set of base classes, disjoint from C. The number ṅ of
training examples is assumed to be large enough to learn a representation of data in X , or otherwise accumulate knowledge that facilitates solving new tasks. We call this process base training. The problem of few-shot classification amounts to designing both the base training process given Ḋ and how to solve new tasks given D. Transductive setting. It is possible that in each few-shot classification task we are given a set Q := {q i } q i=1 of query examples and a prediction is required for all queries in Q.

In this case, although query examples are unlabeled, we can take advantage of this additional data and learn a classifier f that is a function of both the labeled support data D and the unlabeled queries Q. This transductive setting implies semisupervised learning. Representation. The classifier is built on top of an embedding function φ θ : X → R r×d , with parameters θ that are learned at base training. Given an example x ∈ X , this function yields a r × d feature tensor φ θ (x), where r represents the dimensions of a spatial domain Ω and d the feature dimensions. For X comprising 2D images, the feature is a w × h × d tensor that is the activation of the last convolutional layer, r := w × h is the spatial resolution and Ω := [w] × [h] is the spatial domain. The feature can still be a vector in R d in the special case r = 1, e.g. using global spatial pooling. The feature tensor

F := φ θ (x) contains a feature vector F (r) = φ θ (x)(r) ∈ R d for each spatial position r ∈ Ω.

IV. BACKGROUND

Cosine classifier. Initially used in face verification [START_REF] Ranjan | L2-constrained softmax loss for discriminative face verification[END_REF], [START_REF] Wang | Normface: L2 hypersphere embedding for face verification[END_REF], a simple form of base training that was introduced to fewshot learning independently by Qi et al. [START_REF] Qi | Low-shot learning with imprinted weights[END_REF] and Gidaris and Komodakis [START_REF] Gidaris | Dynamic few-shot visual learning without forgetting[END_REF], is to learn a parametric linear classifier that consists of a fully-connected layer without bias on top of the embedding function φ θ , followed by softmax and crossentropy. If W := ( ẇj ) ċ j=1 is the collection of class weights with ẇj ∈ R r×d , the classifier is defined by

f θ,W (x) := σ ρ[cos(φ θ (x), ẇj )] ċ j=1 , (2)
for x ∈ X , where cos is cosine similarity, ρ ∈ R + is a trainable scale parameter and σ : R m → R m + is the softmax function σ(a) := (e a1 , . . . , e a ċ )/ j e aj for a ∈ R ċ. The representations (features and class weights) either retain resolution r > 1 and are flattened to vectors of length rd, or are pooled to vectors of length d (r = 1), by global spatial pooling. Base training amounts to minimizing the cost function

J( Ḋ; θ, W ) := n i=1 (f θ,W ( ẋi ), ẏi ) (3)
over θ, W , where (p, y) := -log y, p for y ∈ {0, 1} ċ and p ∈ R ċ + , is the cross-entropy loss. Prototypes. A popular classifier for few-shot classification tasks is the prototype classifier, introduced by Snell et al. [START_REF] Snell | Prototypical networks for few-shot learning[END_REF]. If I j := {i ∈ [n] : y i = e j } denotes the indices of support examples labeled in class j, then the prototype of this class j is given by the average features

µ j := 1 |I j | i∈Ij φ θ (x i ) (4)
of those examples for j ∈ C. Again, features are either flattened or pooled to vectors first. Then, denoting by M := (µ j ) c j=1 the collection of prototypes, a query x ∈ X is mapped to f θ,M (x), as defined by [START_REF] Snell | Prototypical networks for few-shot learning[END_REF]. Naïve Bayes nearest neighbor (NBNN). In the revival [START_REF] Li | Revisiting local descriptor based image-to-class measure for few-shot learning[END_REF] of the classic image-to-class approach [START_REF] Boiman | In defense of nearest-neighbor based image classification[END_REF], one collects, for each class j ∈ [c], the features V j := {φ θ (x i )(r)} i∈Ij ,r∈Ω of all spatial positions of all support examples labeled in class j. Then, given a query x ∈ X with feature tensor F := φ θ (x), for each class j, a score

s j (F ) := r∈Ω v∈NN V j (F (r)) cos(F (r), v) (5)
is defined as the average cosine similarity over the features F (r) at all spatial positions r ∈ Ω and their k-nearest neighbors NN Vj (F (r)) in V j . Then, the prediction for x is the class of maximum score.

V. LOCAL PROPAGATION

A. Base training

Dense classifier. We use a dense classifier for base training, introduced by Lifchitz et al. [START_REF] Lifchitz | Dense classification and implanting for few-shot learning[END_REF]. Rather than flattening or pooling, the classifier f θ,W : X → R r× ċ + maps an example x to a tensor of probabilities over spatial positions, by applying a cosine classifier (2) densely at each position

f θ,W (x) := σ ρ[cos(φ θ (x)(r), ẇj )] ċ j=1 r∈Ω , (6)
where the class weights W are shared over locations with ẇj ∈ R d . Cross-entropy applies to all spatial positions using the same class label, and cost function (3) becomes

J( Ḋ; θ, W ) := n i=1 r∈Ω (f θ,W ( ẋi )(r), ẏi ). (7)
Local spatial pooling. Dense classification avoids global spatial pooling by going to the other extreme of applying the loss to every position. This happens regardless of whether the effective receptive field is large enough to represent the class at hand, so it assumes an appropriate resolution of the feature tensor. However, it has been observed that it helps to use input images of higher resolution than the standard benchmarks [START_REF] Dvornik | Diversity with cooperation: Ensemble methods for few-shot classification[END_REF], which we follow. This results in features of accordingly higher resolution, where each position corresponds to small details. We solve this by applying local spatial pooling on the feature tensor, both before dense classification at base training as well as at new classification tasks.

B. Few-shot classification

Spatial attention. Before we can use features of all spatial positions as data, it is important to suppress the background, which appears frequently across positions and images, without being discriminative for the classification task. There are different approaches, such as learning a class-agnostic spatial attention mechanism [START_REF] Wertheimer | Few-shot learning with localization in realistic settings[END_REF], [START_REF] Zhang | Few-shot learning via saliencyguided hallucination of samples[END_REF] or simply by a form of pooling over feature channels [START_REF] Kalantidis | Cross-dimensional weighting for aggregated deep convolutional features[END_REF]. We follow the latter approach.

In particular, given an example x ∈ X with feature tensor F := φ θ (x), we select a subset of feature vectors a(F ) ⊂ R d at spatial positions r ∈ Ω where the 2 -norm is at least τ > 0 relative to the maximum over the domain: Examples are shown in Figure 2. We find this mechanism particularly effective for its simplicity, not only for our method, but also for all baselines. No spatial attention is a special case where τ = 0.

a(F ) := {F (r) : F (r) ≥ τ max t∈Ω F (t) , r ∈ Ω}. (8)
Feature pooling. Propagation tends to amplify elements that appear frequently in a dataset. Local propagation does the same for elements originating from different spatial positions, which in turn depends on the scale of objects relative to the spatial resolution. This can be particularly harmful with elements originating from background clutter and bypass condition [START_REF] Chen | A closer look at few-shot classification[END_REF], exactly because they appear frequently.

To obtain a fixed-size representation that only depends on the content, we perform pooling in the feature space into a fixed number of vectors per example. We do so by clustering: given an example x ∈ X with selected feature vectors a(φ θ (x)) (8), we obtain m clusters by k-means. We represent the corresponding m feature centroids as columns in the d×m matrix g θ (x). Examples are shown in Figure 2. We use this representation only for local propagation. Global propagation and no feature pooling are special cases where m = 1 and m = w × h respectively.

Local propagation. We develop this idea under the transductive setting because it is more general: The non-transductive is the special case where q = 1, the set of queries Q = {q 1 } is singleton and we are making a prediction for q 1 . Given the support examples in D and queries Q, we represent the feature centroids of both as columns in the d × t matrix

V := g θ (x 1 ) . . . g θ (x n ) g θ (q 1 ) . . . g θ (q q ) ( 9
)
where t := (n + q)m. Following [START_REF] Iscen | Efficient diffusion on region manifolds: Recovering small objects with compact cnn representations[END_REF], we use the pairwise similarity function s(v 1 , v 2 ) := [cos(v 1 , v 2 )] γ + where γ > 1, and construct the reciprocal k-nearest neighbor graph of the columns of V , represented by the t × t symmetric nonnegative adjacency matrix W V with zero diagonal. Following [START_REF] Zhou | Learning with local and global consistency[END_REF], this matrix is symmetrically normalized as W

V := D -1/2 V W V D -1/2 V
, where D V := W V 1 t is the degree matrix of the graph and 1 t is the t × 1 all-ones vector.

Extending [START_REF] Zhou | Learning with local and global consistency[END_REF], given any matrix A ∈ R u×t (or row vector for u = 1), its propagation on V is defined as

p V (A) := A(1 -α)(I -αW V ) -1 . ( 10
)
This is a smoothing operation on the graph of V , where parameter α ∈ [0, 1) controls the amount of smoothing: Columns of A corresponding to similar columns of V are averaged together. It is infinitely-recursive, as revealed by the series expansion of the matrix inverse [START_REF] Zhou | Learning with local and global consistency[END_REF].

The operation ( 10) is called local propagation because the graph is defined on local representations originating from different spatial positions of the given images. Global propagation is the special case of having m = 1 cluster per image. This is the same as global average pooling (GAP), with or without spatial attention. Local feature propagation. Using A = V , u = d in [START_REF] Wang | Semi-supervised learning for few-shot image-to-image translation[END_REF], local feature propagation amounts to propagating V on itself:

V := p V (V ), (11)
in the sense that similar feature vectors in columns of V are averaged together, becoming even more similar. No feature propagation is a special case where α = 0, V = V .

Local label propagation. Given the propagated features V (11), we form a new graph with normalized adjacency matrix W V . Extending [START_REF] Zhou | Learning with local and global consistency[END_REF], we form the c × t zero-one label matrix Y with one row per class and one column per spatial position over support examples and queries. A column corresponding to a spatial position of a support example x i is defined as the one-hot label vector y i ; a column corresponding to a position of a query q i is zero:

Y := y 1 1 m . . . y n 1 m 0 c×m . . . 0 c×m ( 12
)
where 0 c×m is the c × m zero matrix and there are q such matrices. Using A = Y , u = c in [START_REF] Wang | Semi-supervised learning for few-shot image-to-image translation[END_REF], local label propagation then amounts to propagating Y on V :

Y := p V (Y ), (13)
such that spatial positions with similar feature vectors obtain similar class scores. This may make little difference on labeled Inference. In c × t matrix Y (13), there is one row per class and one column per spatial position over support examples and queries. Y is nonnegative; by column-wise 1 -normalizing it into c × t matrix Ŷ , we can interpret columns as probability distributions over classes per position. For each query example q i , if Ŷi is the corresponding c × m submatrix of Ŷ , we average these distributions over positions, obtaining a distribution p i := Ŷi 1 m /m. Finally, as in (1), we make a discrete prediction π(p i ) = arg max j∈[c] p ij as the class of maximum probability. This operation is similar to NBNN ( 5), but the quantities being averaged have undergone propagation rather than being direct similarities. Figure 3 shows examples of predicted probability for the correct class per spatial location.

Local label propagation results in spatially smooth predictions that covers a large portion of the object.

VI. EXPERIMENTS

A. Experimental setup

Datasets. We evaluate our method on two datasets that are common in few-shot learning. The first, MiniImageNet, is a subset of ImageNet ILSVRC-12 [START_REF] Russakovsky | Imagenet large scale visual recognition challenge[END_REF]. It contains 600 images for each of its 100 classes. Following the work of Ravi and Larochelle [START_REF] Ravi | Optimization as a model for few-shot learning[END_REF], we use 64 classes for base training, 16 classes for validation and 20 classes for test. We resample all images to 224×224, similarily to [START_REF] Chen | A closer look at few-shot classification[END_REF], [START_REF] Dvornik | Diversity with cooperation: Ensemble methods for few-shot classification[END_REF]. The second dataset, CUB-200-2011 [START_REF] Wah | The Caltech-UCSD Birds-200-2011 Dataset[END_REF], referred to as CUB below, was introduced to few-shot learning by Hilliard et al. [START_REF] Hilliard | Few-shot learning with metric-agnostic conditional embeddings[END_REF]. It contains 11,788 images from 200 distinct bird species. Following the splits of Ye et al. [START_REF] Ye | Learning embedding adaptation for few-shot learning[END_REF], we use 100 classes for base training, 50 for validation and 50 for testing. We crop images using bounding box annotations and resample them to 224×224.

Network. We test our method on a ResNet-12 embedding network. Introduced in [START_REF] Oreshkin | TADAM: Task dependent adaptive metric for improved few-shot learning[END_REF], this network is now commonly used in the few-shot learning community. With input images of size 224×224, the embedding features are tensors of resolution 14×14. To adapt the the larger images before applying a dense classifier [START_REF] Lifchitz | Dense classification and implanting for few-shot learning[END_REF], we apply average pooling on these feature tensors, with kernel size 3×3 and stride 1 without padding. The resulting tensors are of resolution 12×12.

Base Training. We train the network from scratch using stochastic gradient descent with Nesterov momentum on minibatches of size 32. The learning rate schedule is set according to the 5-way 5-shot validation accuracy.

Evaluation protocol. For each dataset, we obtain a unique embedding network resulting from base training. All methods are then applied to the same features. For all experiments, we sample 2000 5-way few-shot tasks from the test set, each with 15 queries per class. We report average accuracy as well as 95% confidence interval. We evaluate two different settings: In the non-transductive setting, queries are treated as 75 distinct sets Q with only one query each, whereas in the transductive setting, there is a single set Q with all 75 queries.

Baselines. In the non-transductive setting, we compare our method with variants of four existing few-shot inference methods. The first, referred to as GAP+Proto, applies global average pooling (GAP) on feature tensors and then uses a prototype classifier [START_REF] Snell | Prototypical networks for few-shot learning[END_REF] on the support set (4). The second is the inference mechanism of the matching network [START_REF] Vinyals | Matching networks for one shot learning[END_REF], while the third, referred to as Local Match, is a modified version as follows. For each support example x with feature tensor F := φ θ (x), we use local feature vectors F (r) at all positions r ∈ Ω as independent support examples, with the same label as x. We do the same on queries and average the class score vectors over positions. The fourth is the inference mechanism of NBNN [START_REF] Li | Revisiting local descriptor based image-to-class measure for few-shot learning[END_REF] (5). For each method, we experiment with and without our spatial attention mechanism [START_REF] Chen | A closer look at few-shot classification[END_REF]. For Local Match and NBNN, we select a subset of local features per image. For GAP+Proto and Matching Net, we apply GAP to the selected subset only.

In the transductive setting, we compare with the inference mechanism of global label propagation [START_REF] Liu | Learning to propagate labels: Transductive propagation network for few-shot learning[END_REF], [START_REF] Rodríguez | Embedding propagation: Smoother manifold for few-shot classification[END_REF], with and without global embedding propagation [START_REF] Rodríguez | Embedding propagation: Smoother manifold for few-shot classification[END_REF]. These baselines are again evaluated with and without spatial attention. We always include spatial attention in our local propagation, but we experiment with and without feature pooling, with and without feature propagation.

B. Ablation studies

Overall, our method has five parameters. Two refer to optional components related to local information: the threshold τ for spatial attention and the number of clusters m for feature pooling. The other three refer to propagation, like all related methods dating back to [START_REF] Zhou | Learning with local and global consistency[END_REF]: the number of neighbors k in the graph, the exponent γ in the feature similarity function and α, controlling the amount of the smoothing. For all experiments, we perform a fairly exhaustive parameter search over a small set of possible values per parameter and we make choices according to validation accuracy. We present a summary of parameter search independently for τ and m, keeping other parameters fixed to the optimal. Spatial Attention. As shown in Figure 4, referring to GAP+Proto baseline, there is an optimal range of τ in [0.3, 0.5], such that we filter out the uniformative local feature without removing too much information. The same behavior appears in Figure 5, referring to our best method for each setting. For the remaining of the experiments, we fix τ to 0.3.

Feature pooling. This is a compromise between global pooling and a full set of local features per image, which brings a consistent small improvement compared to both, while making local propagation more efficient by limiting the graph size.

According to Figure 6, referring again to our best method for each setting, there is an optimal number m of clusters that depends on the dataset and setting (transductive or not, 1/5shot). On CUB, we use m = 40 for 1-shot and m = 60 for 5-shot. On miniImageNet, we use m = 60 in both cases.

Propagation parameters. Propagation has been extensively researched in the past, so we do not report the study of its parameters. It is known for instance that α should be close to 1 and there is a local maximum with respect to k, which depends on the quantity of the data [START_REF] Iscen | Efficient diffusion on region manifolds: Recovering small objects with compact cnn representations[END_REF]. After parameter search, for most experiments we set α = 0.9, γ = 4, and k = 5, k = 50 respectively for global and local propagation.

C. Results

Table I presents a complete set of results our method and baselines in different settings, using different options. We discuss the effect of our contributions below. Spatial attention. We use spatial attention with our method but we also combine it with baselines for fair comparison. It is an extremely simple mechanism that consistently improves few-shot classification accuracy in most cases, including global or local, with propagation or not, transductive or not. The only exception is Local Match on miniImageNet. The gain is more pronounced on 1-shot tasks, which is expected as information selection is more important when information is scarce. It reaches 3% for the baselines and 2% for propagation on CUB, as well as 1% on miniImageNet. Feature pooling. Clustering the set of local features into a given number of clusters for each image is bringing small accuracy improvements when combined with propagation, local or global. In particular, spatial attention and feature pooling brings a 0.30% to 0.75% increase of accuracy compared to spatial attention alone on CUB (transductive and nontransductive). An exception is miniImageNet non-transductive where feature pooling gives slightly worse accuracy by an insignificant margin.

Label propagation. In the non-transductive setting, global label propagation fails. Its performance is similar or inferior to GAP+Protonet. This is to be expected, as this is method a transductive method, so it is not a natural choice given only one query. By contrast, our local label propagation succeeds even in this setting, with up to 2.7% improvement on CUB 5-way 1-shot compared to GAP+Proto. One exception is miniImageNet 5-way 1-shot, where GAP+Proto is better by a small margin; in this case however, the other local baselines (Local Match and NBNN) are worse than both GAP+Proto and our local label propagation, by a larger margin.

In the transductive setting, label propagation, global or local, always helps by using unlabeled data. Our local label propagation with spatial attention and feature pooling improves 5-way 1-shot accuracy over the non-transductive setting by 6% and 5.5%, on CUB and miniImageNet respectively. This improvement is lower for 5-shot tasks as more labeled data are used. Compared with global label propagation, it improves by up to 1.5% on 5-shot, CUB and miniImageNet.

Feature propagation. In the non-transductive setting, feature propagation is mostly harmful, especially when used with our local label propagation, which remains the best option, together with feature pooling. In the transductive setting however, it helps both global and local label propagation, the only exception being 5-shot, miniImageNet. In the case of local label propagation with feature pooling, the gain is up to 2% and 1.5% on 1-shot, CUB and miniImageNet respectively. Therefore this combination is the most effective, improving over our best non transductive result by 8% and 6.5% on 1shot, CUB and miniImageNet respectively.

Universality. As shown in Figure 1, our local label propagation is a universally safe choice for few-shot inference under both transductive and non-transductive settings. This is in contrast to existing methods such as global label propagation, where the user needs to make decisions depending on the amount of unlabeled data that is available.

Comparison to existing methods. Table I also includes a number of recent few-shot learning methods. For fair comparison, all reported results are using the same ResNet12 as embedding network. We observe that our baseline GAP+Proto is better than these models on non-transductive 5-shot classification on miniImageNet. Our method is then outperforming those models as well. In the transductive setting, global propagation is weaker than existing methods, but our best setting of local propagation (including spatial attention, feature pooling, feature propagation and label propagation) is stronger in general. The only exception is 1-shot classification on CUB, where LR+ICI [START_REF] Liu | Learning to propagate labels: Transductive propagation network for few-shot learning[END_REF] is stronger by a small margin.

In parallel with this work, two methods appeared very recently, which are stronger than our solution on miniImageNet but weaker on CUB: (1) DGPN [START_REF] Yang | DPGN: Distribution propagation graph network for few-shot learning[END_REF], which is yet another graph-based method and could be easily integrated with our local propagation. (2) DeepEMD [START_REF] Zhang | DeepEMD: Few-shot image classification with differentiable earth mover's distance and structured classifiers[END_REF], which is based on pairwise image alignment. This is more challenging to integrate, for instance one would need to use alignment in the definition of the graph itself. This can be interesting future work.

VII. CONCLUSION

Our local propagation framework takes the best of both worlds: more data from local representations and better use of this data from propagation. It provides a unified solution that works well given few labeled data and an arbitrary number of unlabeled data. As a result, it works better that solutions meant for the standard few-shot inference and at the same time better than solutions meant for transductive few-shot inference. Two secondary contributions are extremely simple and effective: (a) our feature pooling helps control the additional cost related to local features, while improving performance in most cases; (b) our spatial attention helps not only our method but all baselines too, by a significant margin on 1-shot classification. Our solution only affects inference, so it can easily be plugged into any alternative representation learning method. It is general enough to integrate other state-of-the-art solutions, like pairwise image alignment, other forms of propagation and propagation on several layers.

Fig. 2 .

 2 Fig. 2. Examples of images, each with the corresponding spatial attention heatmap and clusters used in feature pooling (black indicates regions below threshold in the heatmap). The first two lines correspond to CUB, the last two to miniImageNet. We use τ = 0.3 for spatial attention and m = 10 for feature pooling.

Fig. 3 .

 3 Fig. 3. Examples of CUB query images in 5-way 5-shot non-transductive tasks, each followed by the heatmap of predicted probability for the correct class using a prototype classifier, then using local label propagation. (a), (b) Local label propagation helps classifying to the correct class. (c) Both give a correct prediction. (d) Local label propagation fails.

(

  support) examples, but is a mechanism for spatial positions of unlabeled (query) examples to obtain label information as propagated from spatial positions of labeled examples with similar features.

Fig. 4 .

 4 Fig. 4. Spatial attention on GAP+Proto [2]: 5-way few-shot classification accuracy vs. threshold τ , relative to τ = 0 (no attention).

Fig. 5 .

 5 Fig. 5. Spatial attention on our local label propagation, including feature pooling and feature propagation: 5-way few-shot classification accuracy vs. threshold τ , relative to τ = 0 (no attention). All other parameters fixed to optimal.

Fig. 6 .

 6 Fig. 6. Feature pooling on our local propagation: 5-way few-shot classification accuracy vs. number of clusters m, relative to m = 10 for better visualization. TR: transductive. We use spatial attention in all settings and feature propagation only in transductive. All other parameters fixed to optimal.

  85±0.48 90.38±0.27 63.39±0.46 81.21±0.32 GAP+Proto [2] 77.10±0.47 91.24±0.26 64.22±0.45 81.71±0.31 Matching Net [1] 74.85±0.48 89.23±0.29 63.39±0.46 78.14±0.33 Matching Net [1] 77.10±0.47 89.95±0.28 64.22±0.45 78.70±0.33 Local Match [1] 75.92±0.46 89.16±0.28 64.05±0.46 78.45±0.34 Local Match [1] 78.29±0.45 90.60±0.26 63.58±0.46 78.01±0.35 NBNN [12] 76.21±0.45 89.59±0.27 64.90±0.45 79.74±0.32 NBNN [12] 79.14±0.44 91.40±0.25 65.18±0.45 80.00±0.31 GLOBAL LABEL PROPAGATION, NON-TRANSDUCTIVE Propagation 74.69±0.48 87.96±0.30 63.39±0.46 75.89±0.36 76.94±0.47 89.14±0.30 64.22±0.45 76.40±0.36 77.23±0.46 88.78±0.31 63.41±0.45 77.04±0.37 LOCAL LABEL PROPAGATION (THIS WORK), NON-TRANSDUCTIVE Propagation 78.24±0.44 91.07±0.26 65.52±0.45 80.49±0.31 79.02±0.44 91.81±0.25 65.74±0.45 81.13±0.31 79.77±0.44 92.07±0.25 65.59±0.45 80.73±0.31 79.32±0.44 91.52±0.25 64.43±0.45 80.26±0.32 GLOBAL LABEL PROPAGATION, TRANSDUCTIVE Propagation 83.64±0.48 90.63±0.27 70.07±0.51 80.96±0.34 85.52±0.46 91.67±0.27 70.67±0.51 81.44±0.33 87.18±0.46 91.88±0.27 72.54±0.54 81.38±0.35 LOCAL LABEL PROPAGATION (THIS WORK), TRANSDUCTIVE Propagation 83.04±0.43 91.89±0.25 69.95±0.48 82.13±0.31 85.33±0.42 92.50±0.25 71.00±0.48 82.87±0.30 85.80±0.41 92.92±0.24 71.12±0.48 82.83±0.31 87.77±0.41 93.35±0.23 72.57±0.51 82.76±0.33

	METHOD	A P	F	1-SHOT	CUB	5-SHOT	miniIMAGENET 1-SHOT 5-SHOT
	GAP+Proto [2]	74.OTHER MODELS, NON-TRANSDUCTIVE
	SNAIL [44]			-		-	55.71±0.99 68.88±0.92
	TADAM [46]			-		-	58.50±0.30 76.70±0.30
	DC+IMP [11]			-		-	62.53±0.19 79.77±0.19
	Neg-Cosine [73]			-		-	62.33±0.82 80.94±0.59
		OTHER MODELS, TRANSDUCTIVE
	TPN [13]			-		-	59.46±0.00 75.65±0.00
	LR+ICI [39]			88.06±0.00 92.53±0.00 66.80±0.00 79.26±0.00
	EPNet [16]			82.85±0.81 91.32±0.41 66.50±0.89 81.06±0.60

TABLE I 5

 I -WAY FEW-SHOT CLASSIFICATION ACCURACY, COMPARING OUR LOCAL (FEATURE AND LABEL) PROPAGATION TO BASELINES AND EXISTING WORK. A: SPATIAL ATTENTION (OUR WORK, ALSO APPLIED TO BASELINES). P: FEATURE POOLING (CLUSTERING) (OUR WORK). F: FEATURE PROPAGATION [16].