Title: UNSUPERVISED FEW-SHOT LEARNING VIA SELF-SUPERVISED TRAINING

Abstract: Learning from limited exemplars (few-shot learning) is a fundamental, unsolved problem that has been laboriously explored in the machine learning community. However, current few-shot learners are mostly supervised and rely heavily on a large amount of labeled examples. Unsupervised learning is a more natural procedure for cognitive mammals and has produced promising results in many machine learning tasks. In the current study, we develop a method to learn an unsupervised few-shot learner via self-supervised training (UFLST), which can effectively generalize to novel but related classes. The proposed model consists of two alternate processes, progressive clustering and episodic training. The former generates pseudo-labeled training examples for constructing episodic tasks; and the later trains the few-shot learner using the generated episodic tasks which further optimizes the feature representations of data. The two processes facilitate with each other, and eventually produce a high quality few-shot learner. Using the benchmark dataset Omniglot, we show that our model outperforms other unsupervised few-shot learning methods to a large extend and approaches to the performances of supervised methods. Using the benchmark dataset Market1501, we further demonstrate the feasibility of our model to a real-world application on person reidentification.

1. INTRODUCTION:

Few-shot learning, which aims to accomplish a learning task by using very few training examples, is receiving increasing attention in the machine learning community. The challenge of few-shot learning lies on that traditional techniques such as fine-tuning would normally incur overfitting (Wang et al., 2018) . To overcome this difficulty, a set-to-set meta-learning(episodic learning) paradigm was proposed (Vinyals et al., 2016) . In such a paradigm, the conventional mini-batch training is replaced by the episodic training, in term of that a batch of episodic tasks, each of which having the same setting as the testing environment, are presented to the learning model; and in each episodic task, the model learns to predict the classes of unlabeled points (the query set) using very few labeled examples (the support set). By this, the learning model acquires the transferable knowledge (optimized feature representations) across tasks, and due to the consistency between the training and testing environments, the model is able to generalize to novel but related tasks. Although this set-to-set few-shot learning paradigm has made great progress, in its current supervised form, it requires a large number of labeled examples for constructing episodic tasks, which is often infeasible or too expensive in practice. So, can we build up a few-shot learner in the paradigm of episodic training using only unlabeled data?

It is well-known that humans have the remarkable ability to learn a concept when given only several exposures to its instances, for example, young children can effortlessly learn and generalize the concept of "giraffe" after seeing a few pictures of giraffes. While the specifics of the human learning process are complex (trial-based, perpetual, multi-sourced, and simultaneous for multiple tasks) and yet to be solved, previous works agree that its nature is progressive and unsupervised in many cases (Dupoux, 2018) . Given a set of unlabeled items, humans are able to organize them into different clusters by comparing one with another. The comparing or associating process follows a coarse-to-fine manner. At the beginning of learning, humans tend to group items based on fuzzyrough knowledge such as color, shape or size. Subsequently, humans build up associations between items using more fine-grained knowledge, i.e., stripes of images, functions of items or other domain Figure 1 : The scheme of our model UFLST, which consists of two alternate processes: clustering and episodic training. At each round, unlabeled data points are clustered based on extracted features, and pseudo labels are assigned according to cluster identities. After clustering, a set of episodic tasks are constructed by sampling from the pseudo-labeled data, and the few-shot learner is trained, which further optimizes feature representations. The two processes are repeated.

knowledge. Furthermore, humans can extract representative representations across categories and apply this capability to learn new concepts (Wang et al., 2014b) .

In the present study, inspired by the unsupervised and progressive characteristics of human learning, we propose an unsupervised model for few-shot learning via a self-supervised training procedure (UFLST). Different from previous unsupervised learning methods, our model integrates unsupervised learning and episodic training into a unified framework, which facilitates feature extraction and model training iteratively. Basically, we adopt the episodic training paradigm, taking advantage of its capability of extracting transferable knowledge across tasks, but we use an unsupervised strategy to construct episodic tasks. Specifically, we apply progressive clustering to generate pseudo labels for unlabeled data, and this is done alternatively with feature optimization via few-shot learning in an iterative manner (Fig. 1 ). Initially, unlabeled data points are assigned into several clusters, and we sample a few training examples from each cluster together with their pseudo labels (the identities of clusters) to construct a set of episodic tasks having the same setting as the testing environment. We then train the few-shot learner using the constructed episodic tasks and obtain improved feature representations for the data. In the next round, we use the improved features to recluster data points, generating new pseudo labels and constructing new episodic tasks, and train the few-shot learner again. The above two steps are repeated till a stopping criterion is reached. After training, we expect that the few-shot learner has acquired the transferable knowledge (the optimized feature representations) suitable for a novel task of the same setting as in the episodic training. Using benchmark datasets, we demonstrate that our model outperforms other unsupervised few-shot learning methods and approaches to the performances of fully supervised models.

2. RELATED WORKS:

In the paradigm of episodic training, few-shot learning algorithms can be divided into two main categories: "learning to optimize" and "learning to compare". The former aims to develop a learning algorithm which can adapt to a new task efficiently using only few labeled examples or with few steps of parameter updating (Finn et al., 2017; Ravi & Larochelle, 2016; Mishra et al., 2017; Rusu et al., 2018; Nichol & Schulman, 2018; Andrychowicz et al., 2016) , and the latter aims to learn a proper embedding function, so that prediction is based on the distance (metric) of a novel example to the labeled instances (Vinyals et al., 2016; Snell et al., 2017; Ren et al., 2018; Sung et al., 2018; Liu et al., 2018) . In the present study, we focus on the "learning to compare" framework, although the other framework can also be integrated into our model.

Only very recently, people have tried to develop unsupervised few-shot learning models. Hsu et al. (2018) proposed a method called CACTUs, which uses progressive clustering to leverage feature representations before carrying out episodic training. This is different from our model, in term of that we carry out progressive clustering and episodic training concurrently, and the two processes facilitate with each other. Khodadadeh et al. (2018) proposed a method called UMTRA, which uti-lizes the statistical diversity properties and domain-specific augmentations to generate training and validation data. Antoniou & Storkey (2019) proposed a similar model called AAL, which uses data augmentations of the unlabeled support set to generate the query data. Both methods are different from our model, in term of that we use a progressive clustering strategy to generate pseudo labels for constructing episodic tasks.

The idea of self-supervised training is to artificially generate pseudo labels for unlabeled data, which is useful when supervisory signals are not available or too expensive (de Sa, 1994) . Progressive (deep) clustering is a promising method for self-supervised training, which aims to optimize feature representations and pseudo labels (cluster assignments) in an iterative manner. This idea was first applied in NLP tasks, which tries to self-train a two-phase parser-reranker system using unlabeled data (McClosky et al., 2006) . Xie et al. (2016) proposed a Deep Embedded Clustering network to jointly learn cluster centers and network parameters. Caron et al. (2018) further proposed strategies to solve the degenerated solution problem in progressive clustering. Fan et al. (2018) and Song et al. (2018) applied the progressive clustering idea to the person re-identification task, both of which aim to transfer the extracted feature representations to an unseen domain. None of these studies have integrated progressive clustering and episodic training in few-shot learning as we do in this work.

3. METHOD:

In this section, we describe the model UFLST in detail. Let us first introduce some notations. Denote the model at the training round t as M t , {x i } the unlabeled dataset with the number of examples N , and {z i } t is the corresponded feature vector with dimentionality D, which is given by f θ t : x M t --→ z, where f θ t representing the feature extracter and θ t the training parameters of M t . { z i } t and { x i } t represent, respectively, the selected features and unlabeled data after removing outliers from the clustering results, and { y i } t the corresponding pseudo labels.

3.1. PROGRESSIVE CLUSTERING:



3.1.1. K-RECIPROCAL JACCARD DISTANCE:

To cluster unlabeled data points, we adopt the k-reciprocal Jaccard distance (KRJD) metric to measure the distance between data points (Qin et al., 2011; Zhong et al., 2017) , and it is done in the feature space rather than the raw pixel space. First, we calculate the k-reciprocal nearest neighbours of each feature point, which are given by,

EQUATION

where N (z, k) denotes the k nearest neighbours of z. R(z, k) imposes that z and each element of R(z, k) are mutually k nearest neighbours of each other. Second, we compute KRJD between two feature points, which is given by

EQUATION

)

Compared to the Euclidean distance, KRJD takes into account the reciprocal relationship between data points, and hence is a stricter rule measuring whether two feature points matches or not. We find that KRJD is crucial to our model, which outperforms the Euclidean metric as demonstrated in Fig. 2 (more comparisons of two metrics are given in Appendix A).

3.1.2. DENSITY-BASED SPATIAL CLUSTERING ALGORITHM:

For the clustering strategy, we choose the density-based spatial clustering algorithm (DBSCAN) (Ester et al., 1996) , which performs better than other methods in our model. The reasons are: 1) other clustering methods such as k-means and hierarchical clustering are useful to find spherical shaped or convex clusters in the embedding space, while DBSCAN works well for arbitrarily shaped clusters; 2) DBSCAN can detect outliers as noise points, which is very useful at the beginning of training when the distribution of data points in the embedding space is highly noisy; 3) DBSCAN does not need to specify the number of clusters to be generated, which is appealing for unsupervised learning. After removing noisy points (outliers) as done in DBSCAN, pseudo labels (i.e., cluster identities) of data points { x i } t can be expressed as,

EQUATION

where denotes the maximum distance for two points to be considered as in the same neighborhood, ms the minimum number of points huddled together for a region to be considered as dense, and J the KRJD matrix. The value of relies on the cluster density of feature points, which is set to be the mean distance of top P minimum distances in KRJD in this study (see Appendix B).

3.2. EPISODIC TRAINING:



3.2.1. CONSTRUCTING EPISODIC TASKS:

After each round of clustering, we construct a number of episodic tasks, denoted as T = {T 1 , T 2 , ..., T S } with S the number of tasks, from the pseudo-labeled data set { x i , y i } t . For each episodic task, we randomly sample N C classes and N E examples per class. Notably, the setting of each episodic task follows that of the test environment to be performed after training.

We will apply two different ways to implement few-shot learning (see below). One uses the prototype loss, which aims to learn the prototypes of each class and discriminate a novel example based on its distances to the prototypes. In this case, we further split N E into a support set S and a query set Q, i.e., N E = N S + N Q . Following Snell et al. (2017) , we choose a larger value of N C in training than that in testing, but keeps N S the same. The other way to implement few-shot learning is to use the triplet loss or the hardtriplet loss, which separates examples from different classes with a positive margin m. In this case, no splitting support and query data is needed. To mine hard negative examples in triplets, we also use a larger N C in training than that in testing.

3.2.2. LOSS FUNCTIONS:

Two types of loss functions are used in the present study, and both of them are in the framework of "learning to compare" and contribute to simple inductive bias of our model. One is the prototype loss, which is written as

EQUATION

where c k is the prototype of class k given by c k = zi∈S k (z i )/S k , and z a query point. In implementation, we choose to minimize the negative log value of Eq. 4, i.e., L log proto (z, c k ; θ) = -log L proto (z, c k ; θ), as the log value better reflects the geometry of the loss function, making it easy to select a learning rate to minimize the loss function. Clustering:

4:

Extracting features {z i } t of {x i } using the feature extractor f θ t .

5::

Computing K-reciprocal nearest neighbours R(z i , k) t of each z i .

6::

Calculating Jaccard distance matrix J based on {R(z i , k)} t .

7:

Clustering data using DBSCAN and generating pseudo labels {y i } t .

8::

Removing outliers and obtaining the pseudo-labeled dataset { x i , y i } t . 9:

Episodic Training:

10:

s = 0 11: repeat 12:

Constructing a episodic task T s by randomly sampling

N C classes with N E examples per class from { x i , y i } t .

13:

Updating model parameters θ t by training the few-shot learner on T s .

14:

s = s + 1 15:

until s = S 16:

t = t + 1 17: until t = T

The other is the triplet loss (Weinberger & Saul, 2009) , which has been widely used in face recognition and image retrieval. The triplet loss L triplet consists of several triplets, each of which includes a query feature z, a positive feature z + and a negative feature z -, and is written as

EQUATION

where m controls the margin of two classes, and the hinge term plays the role of correcting triplets, so that the difference between the similarities of positive and negative examples to the query point is larger than a margin m. However, in the above form, positive pairs in those "already correct" triplets will no longer be pulled together due to the hard cutoff. We therefore replace the hinge term by a soft-margin formulation, which gives

EQUATION

Eq. 6 is similar to Eq. 5, but it decays exponentially instead of having a hard cutoff and tends to be numerically more stable (Hermans et al., 2017) (see Appendix C for more details).

We find that in general our model achieves a better performance using the prototype loss than using the triplet loss. However, by including hard example mining when constructing triplets, referred to as the hardtriplet loss hereafter, the model performance is improved significantly and becomes better that using the prototype loss. The relationships between these loss functions are analyzed in Appendix D. The pseudo code of our model is summarized in Algorithm 1. 

4. EXPERIMENTS:



4.3. PERFORMANCE OF PROGRESSIVE CLUSTERING:

We first check the behavior of progressive clustering via visualizing 10 hand-written characters from the Futurama alphabets in the Omniglot dataset using T-SNE (Maaten & Hinton, 2008) . Overall, we observe that as learning progresses, the organization of data points is improved continuously, indicating that our model "discovers" the underlying structure of data gradually. As illustrated in Fig. 3A , initially, all data points are intertwined with each other and no structure exists. Over training, clusters gradually emerge, in the sense of that data points from the same class are grouped together and the margins between different classes are enlarged. Appendix E presents a more detailed illustration of the clustering process. We quantitatively measure the clustering quality by computing the Normalized Mutual Information (NMI) between real labels {ŷ i } t (i.e., the ground truth) and pseudo labels { y i } t , which is given by,

EQUATION

where I(•, •) is the mutual information between {ŷ i } t and { y i } t , and H(•) the entropy. The value of NMI lies in [0, 1], with 1 standing for perfect alignment between two sets. Note that NMI is independent of the permutation of labeling orders. As shown in Fig. 3B , the value of NMI increases with the training round and gradually reaches to a high value close to 1. Remarkably, the value of NMI well predicts the classification accuracy of the learning model (comparing Fig. 3B and 3C ).

These results strongly suggest that the combination of progressive clustering and episodic training in our model is able to discover the underlying structure of data manifold and extract the representative features of data points necessary for the few-shot classification task.

4.4. RESULTS ON OMNIGLOT:

Table 1 presents the performances of our model on the Omniglot dataset compared with other methods. We note that using the triplet loss, our model already outperforms other state-of-the-art unsupervised few-shot learning methods, including CACTUs (Hsu et al., 2018) , UMTRA (Khodadadeh et al., 2018) , and AAL (Antoniou & Storkey, 2019) , to a large extend. Using the prototype loss, the performance of our model is further improved. The best performance of our model is achieved when using the hardtriplet loss. Remarkably, the best performance of our model approaches to that of two supervised models, which are the upper bounds for unsupervised methods.

5-way Acc. 20-way Acc. 1-shot 5-shot 1-shot 5-shot UMTRA (Khodadadeh et al., 2018) 77 

4.5. RESULTS ON MARKET1501:

We also applied our model to a real-world application on person Re-ID. In reality, labeled data is extremely lacking for person Re-ID, and unsupervised learning becomes crucial. Table 2 presents the performances of our model on the benchmark datset Market1501. There is no reported unsupervised few-shot learning result on this dataset in the literature. Rahimpour & Qi (2018) report the supervised results under the 100-way 1-shot scenario. To evaluate our model, we trained a supervised model adapted from Xiong et al. (2018) . We find that the model performance using the hardtriplet loss is much better than that using the prototype loss. This is due to that large variations in the appearance and environment of detected pedestrians lead to that noisy samples may be chosen as the prototypes, which deteriorates learning; while the hardtriplet loss focuses on correcting highly noisy examples that violate the margin and hence alleviates the problem. Overall, we observe that our model achieves encouraging performances compared to the supervised method, in particular, Under review as a conference paper at ICLR 2020 in the scenario of low-way classification, which suggest that our model is feasible in practice for person Re-ID when annotated labels are not unavailable. 

5-way:



5. DISCUSSION:

In this study, we have proposed an unsupervised model UFLST for few-shot learning via selftraining. The model consists of two processes, progressive clustering and episodic training, which are executed iteratively. Other unsupervised methods also consider the two processes, but they are performed separately, in term of that unsupervised clustering for feature extraction is accomplished before applying episodic learning. This separation has a shortcoming, since there is no guarantee that the extract features by unsupervised clustering are suitable for the followed few-shot learning.

Here, our model carries out the two processes in an alternate manner, which allows them to facilitate with each other, such that feature representation and model generalization are optimized concurrently, and eventually it produces a high quality few-shot learner. To our knowledge, our work is the first one that integrates progressive clustering and episodic training for unsupervised few-shot learning.

On the Omniglot dataset, our model outperforms other state-of-the-art unsupervised few-shot learning methods to large extend and approaches to the performances of supervised modes. On the Market1501 dataset, our model also achieves encouraging performances compared to a supervised method. The high effectiveness of our model makes us think about why it works. Few-shot learning in essence is to extract good representations of data suitable for prediction by using very few training examples. To resolve this challenge, the episodic learning paradigm aims to create a set of episodic few-shot learning scenarios having the same setting as the testing environment, so that the model learns to extract good feature representations that are transferable to novel but related tasks. To this end, the real labels of data are helpful but not essential, and we can construct pseudolabeled examples to train the model. But crucially, as demonstrated by this study, the construction of pseudo-labeled examples must go along with the episodic training, so that the extracted features of data really matches the few-shot learning task. Notably, this unsupervised and progressive way of learning agrees with the nature of human on few-shot learning. 

A K-RECIPROCAL JACCARD DISTANCE (KRJD):

A clustering algorithm operating on the raw data space or a shallow linear embedded space is known to be ineffective when the dimensionality of data is high, suffering from the so called "curse of dimensionality" problem (Steinbach et al., 2004) . Recent studies on learning representations with deep neural networks have made promising progress for clustering algorithms (Xie et al., 2016; Caron et al., 2018; Yang et al., 2017; Shaham et al., 2018) . Although these studies alleviate the problem of choosing data representations, it still needs to choose a suitable distance metric. For some datasets, such as MNIST (LeCun et al., 1998) and STL (Coates et al., 2011) , it is adequate to use the Euclidean distance in the feature space to cluster data well. However, for other datasets, such as Omniglot (Lake et al., 2015) and Market1501 (Zheng et al., 2015) , where the number of classes is large but the number of examples in each class is small, the distribution of data points in the feature space is quite uneven. In such a case, the Euclidean or Cosine distance does not work well. To solve this problem, we adopt to use the k-reciprocal Jaccard distance (KRJD) metric originally proposed for object retrieval Qin et al. (2011) to measure the distance between two data points..

The Jaccard distance compares the members of two sets to judge which elements are shared or distinct. For two sets A and B, the Jaccard distance is calculated to be,

EQUATION

where the numerator is the number of elements shared by two sets, and the denominator the number of elements in either set. The Jaccard distance is a measurement of the similarity between two sets of data and is in the range of [0, 1], where the lower its value, the more similar two sets are.

The Jaccard distance is originally used for two sets with discrete elements. To apply to a group of data points in the feature space, we adopt KRJD from Zhong et al. (2017) . Denote the group of data points as Z, where each row is the feature of a data point. KRJD transfers Z into a discrete k-reciprocal ranking list R by first calculating the k nearest neighbours (KNN) of each element in Z and then re-ranking them. Once R is available, we apply Eq. 8 to calculate the Jaccard distance of Z. Denote the k nearest neighbours of the feature point z i to be

N (z i , k) = {z 0 i , z 1 i , ..., z k i }.

(9) Then, the k-reciprocal nearest neighbours (KRNN) of z i is obtained by re-ranking the KNN list, which is written as,

EQUATION

Compared to KNN, KRNN is a more strict and accurate measurement of ranking, so that more positive examples appear in the top k ranking list, as demonstrated in Fig. 4 and Fig. 5 . After obtaining KRNN of each point, we calculate KRJD between two points by 

EQUATION

) (A) (B) (C)

B THE PARAMETER OF IN DBSCAN:

The parameter in DBSCAN specifies how close two points should be for them to be considered as in the same cluster, and its value relies heavily on the underlying cluster density of feature points.

In the present study, we choose to be the mean of top P minimum distances of the KRJD matrix J, which is given by,

EQUATION

To determine the value of P , we set P = ρ|{ x i }|, where ρ is a hyper-parameter representing the portion of points selected over the whole set { x i }. Increasing ρ equals to increasing , which implies that more points will be assigned into a single cluster, and consequently this decreases the number of clusters obtained. Decreasing ρ has the opposite effect.

Table 4 presents the effects of different values of ρ on the model performances. We see that when ρ is small, the performance is not good, since there are too many clusters and the number of examples in each cluster is small, which makes it hard to construct episodic tasks having enough examples to train the model; when the value of ρ is too large, the model performance is also bad, since in this case, it is hard to generate sufficiently different episodic tasks. For large ρ, we may reduce the value of N C to alleviate the problem (note that in our model, the learning scenario affects the clustering behavior). 



C COMPARING THE TRIPLET LOSS AND THE SOFT-MARGIN TRIPLET LOSS:

In Sec. 3.2.2, we propose to use the soft-margin version of the triplet loss to replace the conventional one with the hard cutoff. This concerns that when the hard cutoff triplet loss stops to pull together those "already correct" positive pairs, the soft-margin triplet loss continues to optimize those pairs. We also empirically find that the soft-margin triplet loss tends to be numerically more stable during training. Table 5 presents the model performances using the two loss functions.

D RELATIONSHIPS BETWEEN THE LOSS FUNCTIONS:

In Sec. 4.4 and 4.5, we observe that the model trained with the prototype loss has a better performance than that with triplet loss, and by mining hard examples in the triplets, using the hardtriplet loss, the model achieves the best performance. Here, we give analysis on the relationships between these loss functions. Table 5 : Comparison of the soft-margin triplet loss and the hard cutoff triplet loss on two datasets with margin m = 0.5 and m = 1.0.

Consider a N C -way 1-shot episodic learning scenario, where a prototype c k is the support point z k , the prototypical loss is written as

EQUATION

During training, we construct each episodic task by randomly sampling N C classes and N E examples per class. When using the prototype loss (Eq. 13), a query point z is pulled towards the corresponded support point z p , and meanwhile, z is pushed away from all other support points {z k } k =p ; whereas, when using the triplet soft-margin loss (Eq. 6), the query point z is only pushed away from one of other support points z -. This implies that in each update, L triplet-SM only interacts with a single negative example from one of other classes and ignores many other negative examples. When N C is small, optimizing the model with the two loss functions has no big difference. For example, when N C = 2 and m = 0, Eq. 6 and 13 become exactly the same. However, when N C becomes larger, the possible number of triplets grows cubically with N E and linearly with N C , which makes it difficult to select non-trivial triplets. In such a situation, optimizing on these uninformative triplets leads to the problem that the model gets stuck into a local optimum and suffers slow convergence. This justifies why the model has a inferior performance using the triplet loss compared to using the prototype loss.

The inefficiency of the conventional triplet loss motivate us to mine hard triplets to alleviate its shortcomings (Wang et al., 2014a; Cui et al., 2016; Hermans et al., 2017) . Mining hard negative examples across the whole dataset is infeasible, since it is too time-costing to evaluate all embedding vectors in the deep learning framework. So, we choose to do hard negative example mining within a batch, i.e., we select the hardest positive and the hardest negative examples when forming the triplets, and obtain

EQUATION

Compared to Eq. 13 which pushes a query point away from all other support points from different classes, Eq. 14 focuses on pulling the hardest positive example closer and pushing the hardest negative example away at the same time. By this, we get a better performance than that using the prototype loss.

Another improvement can be made by using m > 0, as a positive margin makes different classes become more separable. At the beginning of training, when data points are intertwined with each other, a positive margin push points belonging to different pseudo classes away quicker than m = 0.

Table 6 shows the effect of m value on the model performance. Experiments are carried out on Omniglot dataset, under the 5-way 1-shot learning scenario.

Here we investigate the effect of clustering frequency during training. That is, how many epochs are taken before updating the clustering in each round? We find that our model is very robust to learning algorithm to provide a statistical likelihood of difference and sameness in the training and validation data of T i . The choice of the right augmentation function for UMTRA and AAL, the right feature embedding approach for CACTUs, and the other hyper-parameters have a strong impact on the performance.

The model architecture trained on the Mini-ImageNet dataset is exactly the same as on the Omniglot dataset, i.e., the 4-layer convnet described in Sec.4.2. We only report the results by training without any data augmentation. We achieve 33.77% and 44.03% under the 5-way 1-shot and 5-way 5-shot scenario respectively. Compare to the model training from scratch (25.17% under the 5-way 1-shot scenario), our model has a gain of 8.6%. The best 5-way 1-shot accuracy in the CACTUs model is 39.18%. However, comparing to the CACTUs model is unfair because they used the AlexNet or the VGG16 to first learn a very good feature embedder for downstream feature clustering process, while our model is only composed of a 4-layer convenet. Both of the best results in the UMTRA model and the ALL model are acquired by using fancy data augmentations, such as shifting, random flipping, color distortions, image-Warping and image-pixel dropout (see Khodadadeh et al. (2018) ; Antoniou & Storkey (2019) for more details) while we don't use any data augmentation tricks here.

It is noteworthy that our model outperforms the UMTRA trained without any data augmentation to a large extent (33.77% vs. 26.49%).

Compared to the results on Omniglot and Market1501, the results on the Mini-ImageNet is not the state-of-the-art. The underline reason may come from three aspects. (1) For a fair comparison to other unsupervised few-shot learning models, we use the 4-layer convnet. However, the in-class variations of the Mini-ImageNet is very large, which is hard for such a small network to capture the semantic meanings of images.

(2) In unsupervised learning, it is hard to choose suitable hyperparameters, such as the clustering frequency, DBSCAN-related parameters, and the learning rate.

(3) The ground truth for the class number of Mini-ImageNet is small 1(64 for training, 16 for validating and 20 for testing). But, for constructing episodic tasks, we prefer to over-segment the dataset, and this over-segmentation tend to assign data belonging to the same class into different clusters, leading to a degenerate performance. Our model performs very well on Omniglot and Maket1501, which may be attributed to that both datasets have large class numbers and the number of examples in each class is small. This type of dataset is very suitable for constructing episodic tasks to learn a few-shot learner. In our future work, we will explore more domain specific knowledge and data augmentation strategies to improve the accuracy on the MiniImageNet dataset and extend our model to more datasets.

:



Figures and Tables:

Figure 2: Comparing the performances of KRJD and the Euclidean metric. Top 10 neighbours of a chosen query character from Omniglot are shown. Black box: the query character. Green box: the positive characters in the neighbourhood of the query character. Red box: the negative characters in the neighbourhood of query character. (A) The ranking result using Euclidean metric. (B) The ranking result using KRJD. The number under each image represents its true class. KRJD outperforms the Euclidean metric, in term of it includes more positive examples in the ranking list.

Unsupervised Few-shot Learning via Self-supervised Training (UFLST) Input: Unlabeled dataset {x i }, initialized model parameters θ 0 Output: Trained model parameters θ T 1:

When training with the triplet loss, we set the margin between positive and negative examples to be 0.5, and the number of training rounds T = 20. To avoid overfitting, the model is fine-tuned for only 50 epochs in each round. We used Adam with momentum to update the model parameters, and the learning rate is set to 0.005 with an exponential decay after 25 epochs. The mini-batch size is 128, which consists of 32 classes and 4 examples per class in each episodic task. When constructing triplets with hard example mining, we didn't mine hard negative examples across the whole dataset which is infeasible, rather we did only in the current episodic task. When training with the prototype loss, we used more classes (higher way) during training (N C = 60 in Omniglot and N C = 30 in Market1501), which leads to better performances as empirically observed inSnell et al. (2017). Other hyper-parameters are set to be the same as training with the triplet loss.

Figure 3: Behaviors of progressive clustering. (A) Visualizing clustering results over training rounds by T-SNE. 10 characters from the Futurama alphabets in the Omniglot dataset were selected. (B) NMI vs. training round. (C) Classification accuracy vs. training round.

Figure 4: Top 10 neighbours of a chosen query character from Omniglot dataset. Black box: the query character. Green box: the positive characters in the neighbourhood of the query character. Red box: the negative characters in the neighbourhood of query character. The number under each image represents its true class. Upper panels in (A), (B) and (C): the ranking result using the Euclidean metric. Lower panels in (A), (B) and (C): the ranking result using KRJD. The KRJD metric outperforms the Euclidean metric, in term of it includes more positive examples in the ranking list.

Figure 5: Top 10 neighbours of a chosen query image from the Market1501 dataset. Black box: the query image. Green box: the positive images in the neighbourhood of the query image. Red box: the negative images in the neighbourhood of query image. The number under each image represents its true class. Upper panels in (A), (B) and (C): the ranking results using the Euclidean metric. Lower panels in (A), (B) and (C): the ranking results using KRJD.

Figure 6: Clusters generated by DBSCAN over training rounds. The results of the first 5 rounds are shown. For the convenience of visualization, we only display 50 clusters and the number of data points in each of them.

set, 19732  images with 750 identities forming the gallery set, and another 3368 images forming the query set. All images were resized to 256 × 128. Except normalization, no other pre-processing was applied.4.2 IMPLEMENTATION DETAILSWhen training on the Omniglot dataset, we chose the model architecture to be the same as that inVinyals et al. (2016) , which consists of four stacked layers. Each layer comprises 64-filter 3 × 3 convolution, followed by a batch normalization, a ReLU nonlinearity, and 2 × 2 max-pooling. When training on the market1501 dataset, due to high variances of pose and luminance, we chose to use a highly expressive model(Xiong et al., 2018), which consists of a Resnet50 pretrained on ImageNet as a backbone, and a batch normalization layer after the global max-pooling layer to prevent overfitting. Our evaluation protocol on market1501 is different from that inZheng et al. (2015), where they reported Cumulative Matching Characteristic (CMC) and the mean average precision (mAPs); while we consider the performance of 1-shot learning, which mimics the typical single query condition in a person Re-ID task.

Table content: <table><tr><td>4.1 DATASETS</td></tr><tr><td>We evaluate our model on two benchmark datasets, which are Omniglot (Lake et al., 2015) and</td></tr><tr><td>Market1501 (Zheng et al., 2015).</td></tr></table>

Performances of different unsupervised few-shot learning models on Omniglot under different settings.

Table content: <table><tr><td>.80</td><td>92.74</td><td>62.20</td><td>77.50</td></tr></table>

Performances of our model on Market1501 with different settings. The supervised model is adapted fromXiong et al. (2018). Only 1-shot learning is considered to mimic the typical single query condition in person Re-ID applications.4.6 EFFECT OF THE SIZE OF THE UNLABELED DATASETWe also evaluate how our model relies on the number of unlabeled examples. Table 3 presents the results on the Omniglot dataset with varying number of training examples. Overall, the model performance is improved when the number of training examples increases. Notably, by using only a quarter of the unlabeled data, our model already achieves performances comparable to other unsupervised few-shot learning methods (comparing UFLST-300 with those in Table1). This demonstrates the feasibility of our model when the number of unlabeled examples is not large.

Table content: <table><tr><td>10-way</td><td>15-way</td><td>20-way</td><td>50-way</td><td>100-way</td></tr></table>

Performances of our model on Omniglot using different numbers of unlabeled training examples. The hardtriplet loss is used.

Table content: <table/>

Junyuan Xie, Ross Girshick, and Ali Farhadi. Unsupervised deep embedding for clustering analysis.In International conference on machine learning, pp. 478-487, 2016.Fu Xiong, Yang Xiao, Zhiguo Cao, Kaicheng Gong, Zhiwen Fang, and Joey Tianyi Zhou. Towards good practices on building effective cnn baseline model for person re-identification. arXiv preprint arXiv:1807.11042, 2018.

Table content: <table><tr><td>Bo Yang, Xiao Fu, Nicholas D Sidiropoulos, and Mingyi Hong. Towards k-means-friendly spaces:</td></tr><tr><td>Simultaneous deep learning and clustering. In Proceedings of the 34th International Conference</td></tr><tr><td>on Machine Learning-Volume 70, pp. 3861-3870. JMLR. org, 2017.</td></tr><tr><td>Liang Zheng, Liyue Shen, Lu Tian, Shengjin Wang, Jingdong Wang, and Qi Tian. Scalable person</td></tr><tr><td>re-identification: A benchmark. In Proceedings of the IEEE international conference on computer</td></tr><tr><td>vision, pp. 1116-1124, 2015.</td></tr><tr><td>Zhun Zhong, Liang Zheng, Cao, and Shaozi Li. Re-ranking person re-identification with</td></tr><tr><td>k-reciprocal encoding. In Proceedings of the IEEE Conference on Computer Vision and Pattern</td></tr><tr><td>Recognition, pp. 1318-1327, 2017.</td></tr></table>

Effects of the ρ value in DBSCAN on model performances. The hyper-parameters are given in Sec. 4.2.

Table content: <table><tr><td/><td/><td>Acc.</td><td colspan="2">20-way Acc.</td></tr><tr><td/><td>1-shot</td><td>5-shot</td><td>1-shot</td><td>5-shot</td></tr><tr><td>ρ = 1 × 10 -5 , N C = 60</td><td>78.88</td><td>92.73</td><td>59.49</td><td>81.50</td></tr><tr><td>ρ = 2 × 10 -5 , N C = 60</td><td>82.85</td><td>94.82</td><td>64.83</td><td>85.61</td></tr><tr><td>ρ = 3 × 10 -5 , N C = 60</td><td>91.43</td><td>97.79</td><td>78.48</td><td>93.04</td></tr><tr><td>ρ = 4 × 10 -5 , N C = 60</td><td>97.57</td><td>99.35</td><td>92.62</td><td>97.82</td></tr><tr><td>ρ = 5 × 10 -5 , N C = 60</td><td>97.03</td><td>99.19</td><td>91.28</td><td>97.37</td></tr><tr><td>ρ = 6 × 10 -5 , N C -60</td><td>97.64</td><td>99.34</td><td>93.39</td><td>98.06</td></tr><tr><td>ρ = 7 × 10 -5 , N C = 60</td><td>58.35</td><td>79.24</td><td>34.17</td><td>58.33</td></tr><tr><td>ρ = 8 × 10 -5 , N C = 60</td><td>58.10</td><td>78.95</td><td>33.90</td><td>58.12</td></tr><tr><td>ρ = 7 × 10 -5 , N C = 30</td><td>97.16</td><td>99.12</td><td>91.28</td><td>97.48</td></tr><tr><td>ρ = 8 × 10 -5 , N C = 20</td><td>97.49</td><td>99.25</td><td>92.14</td><td>97.72</td></tr></table>

The model performances using the hardtriplet loss with different m values on Omniglot.

Table content: <table><tr><td/><td>5-way Acc.</td><td/><td colspan="2">20-way Acc.</td></tr><tr><td>margin</td><td>1-shot</td><td>5-shot</td><td>1-shot</td><td>5-shot</td></tr><tr><td>m = 0</td><td>96.59</td><td>99.14</td><td>90.35</td><td>97.11</td></tr><tr><td>m = 0.3</td><td>96.09</td><td>98.95</td><td>89.43</td><td>96.65</td></tr><tr><td>m = 0.5</td><td>96.60</td><td>99.15</td><td>90.19</td><td>97.14</td></tr><tr><td>m = 1.0</td><td>97.03</td><td>99.19</td><td>91.28</td><td>97.37</td></tr><tr><td>m = 3.0</td><td>96.00</td><td>98.96</td><td>88.30</td><td>96.56</td></tr></table>

The frequency of clustering during training. Experiments are carried on the Omniglot dataset. "Number of Update Epochs" means how many epochs are taken before the clustering.

Table content: <table><tr><td colspan="5">F THE FREQUENCY OF CLUSTERING DURING TRAINING</td><td/><td/><td/></tr><tr><td>Number of Update Epochs</td><td>1</td><td>2</td><td>5</td><td>10</td><td>20</td><td>30</td><td>40</td></tr><tr><td>UFLST-Tripetloss</td><td>97.43</td><td>97.51</td><td>96.91</td><td>97.03</td><td>97.44</td><td>97.80</td><td>97.93</td></tr></table>

Peer review (iclr2020):
This paper considers the problem of learning an image representation for few-shot learning without using image labels during training. This is a well-motivated problem since (as the paper points out) learning such a representation using *episodes* of low-shot learning problems as examples may require a large amount of annotated data. The paper proposes an iterative algorithm which alternates between clustering the images using the current model and updating the model using the clusters as *pseudo-labels*. This approach is not particularly elegant as there is no clear objective being optimized, but it may nevertheless be effective. One main claim of the paper is that the iterative nature of this process is key to the success of the algorithm. The choice of model is a multi-layer conv-net which is trained using SGD (Adam). The paper investigates both triplet (with and without hard negatives) and *prototype* losses for learning the model parameters. To find clusters, the paper adopts the DBSCAN algorithm using the Jaccard similarity of the k-reciprocal neighbour sets. I am not aware of other papers that use self-supervised learning to obtain a representation which is specifically suitable for few-shot learning via nearest-neighbour classification. As is noted in the paper, the absence of supervision during training more closely resembles the scenario of few-shot learning in biological systems. The design decisions are well motivated throughout the paper. The appendices are high quality and make the paper much more complete. In particular: the method for choosing epsilon, the empirical study of the effect of epsilon and the discussion of the behaviour of the cluster sizes as training proceeds. Principal concerns: (1.1) The proposed approach is particularly similar to DeepCluster (Caron et al.). Besides the use of a different clustering algorithm, it seems that the main high-level difference is the use of *episodic training*, in which the algorithm is trained to compare examples to a query example, rather than to classify single examples. I would have preferred to see a comparison to non-episodic training. (It might be necessary to train a linear classifier on top of the final feature representation rather than simply build a nearest-neighbour classifier, but still this is convex, cheap and even closed-form in the case of least-squares regression.) (1.2) While the algorithm has been demonstrated on real images in the Market1501 dataset, it would have been much more convincing to see it demonstrated on a more widely-used dataset for few-shot learning such as Mini-ImageNet. (1.3) There are several recent papers on unsupervised feature learning using self supervision, especially as an alternative to ImageNet-classification pre-training. There is no discussion of these approaches, yet they might perform better than the proposed algorithm, especially for tasks with real images. Some examples of such papers are: - *Discriminative Unsupervised Feature Learning with Exemplar Convolutional Neural Networks* - *Representation Learning with Contrastive Predictive Coding* - *Unsupervised representation learning by predicting image rotations* The literature on using auto-encoders to learn feature representations is also relevant. Issues with details in the paper: (2.1) The DeepCluster paper observed that non-negligible accuracy could be achieved using a randomly-initialized conv-net (12% when chance is 0.1%). This enabled the use of clusters as pseudo-labels. Is a similar effect observed with your datasets and random initialization? (2.2) For large datasets, the clustering algorithm might be prohibitively expensive? It would be useful to discuss the complexity of this algorithm. (2.3) It would be interesting to see the effect of varying the frequency of the clustering during training (i.e. how many gradient steps are taken before updating the clustering). (2.4) It is concerning that the accuracy drops sharply as ho increases [6, 7, 8]*10^-5 in Table 4. (2.5) It is stated that batch-normalization at the network output helps prevent over-fitting. Why? My intuition is that it would be more helpful for avoiding regions of the loss function which have a small gradient magnitude. What happens if you remove it? (2.6) What is the test time procedure? Do you use the mean feature when there are k > 1 shots (even for the network trained with the hinge loss)? Do you L2-normalize the representation vectors? (2.7) It seems potentially brittle to use hard negatives in the triplet loss with pseudo-labels? If the labels were wrong, then the hard negatives might not really be negatives. Nevertheless, this does not seem to be an issue, at least with these datasets. (2.8) There are no error-bars anywhere in the paper. Minor comments: (3.1) Tables 3 and 4 would be easier to interpret if plotted on an axis. (3.2) The word *concurrently* suggests that the clustering and the training are performed simultaneously. I would prefer *alternating*. (3.3) A grammatical review of the paper is required. For example in the abstract: *to a large extent (extend) and approaches the performance of (to the performances of) supervised methods*. (3.4) Remember to use log and max in latex to improve the appearance.