Unsupervised Few Shot Learning via Self-supervised Training
Authors: Zilong Ji
Xiaolong Zou
Tiejun Huang
Si Wu
Venue:  (2020)
Keywords: few shot learning
self-supervised learning
meta-learning

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 re-identification.

Under review as a conference paper at ICLR 2020
UNSUPERVISED FEW-SHOT LEARNING VIA SELF- SUPERVISED TRAINING
Anonymous authors Paper under double-blind review
ABSTRACT
Learning from limited exemplars (few-shot learning) is 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 more natural proce- dure for cognitive mammals and has produced promising results in many machine learning tasks. In the current study, we develop method to learn unsupervised few-shot learner via self-supervised training (UFLST), which can effectively gen- eralize to novel but related classes. The proposed model consists of two alter- nate 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 opti- mizes the feature representations of data. The two processes facilitate with each other, and eventually produce high quality few-shot learner. Using the bench- mark dataset Omniglot, we show that our model outperforms other unsupervised few-shot learning methods to large extend and approaches to the performances of supervised methods. Using the benchmark dataset Market150f 1501 we further demonstrate the feasibility of our model to real-world application on person re- identification.
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 learn- ing lies on that traditional techniques such as fine-tuning would normally incur overfitting (Wang et al. 2018). To overcome this difficulty, a set-to-ser meta-learning(eper proposed (Vinyals et al.) (0166). In such a paradigm, the conventional mini-batch training 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 each episodic task, model learns to predict the classes of unlabeled points (the query set) using very few labeled exam- ples (the support set). By this, the learning model acquires the transferable knowledge (optimized feature representations) across tasks, and due 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, requires large number of labeled examples for constructing episodic tasks, which is often infeasible or too expensive in practice. So, can we build up few-shot learner in the paradigm of episodic training using only unlabeled data?
learning) paradigm was
is well-known that humans have the remarkable ability 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 set of unlabeled items, humans are able to organize them into different clusters by comparing one with another. The comparing or associating process follows coarse-to-fine fo- manner. At the beginning of learning, humans tend to group items based fuzzy- rough knowledge such as color, shape or size. Subsequently. humans build up associations between items using more fine- grainnd knowledge, i.e., stripes of images, functions of items other domain

---

Under review as a conference paper at ICLR 2020
Raw Data
Features
Clusters
Episodic Tasks
task1
task2
Pseudo Labeled set
Feature Extractor
Clustering
task3
Clustering Block
Episodic Training Block
Clustering Episodic Training
Few-shot Learner@T
Learner@T++
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 extracted features, and pseudo labels are assigned according to cluster identities. After clustering, a set of episodic tasks 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 categorics and apply this capability learn concepts (Wang al. 2014b).
In the present study, inspired by the unsupervised and progressive characteristics human learning, propose an unsupervised model for few-shot learning via self-supervised training procedure (UFLST). Different from previous unsupervised learning methods, our model integrates unsuper- vised learning and episodic training into unified framework, which facilitates feature extraction and model training iteratively. Basically, we adopt the episodic training paradigm, taking advan- tage 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 done alternatively with feature optimization via few-shot learn- ing in an iterative manner (Fig.)) [ 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 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, use the improved features to cluster data points, generating new pseudo labels and constructing new episodic tasks, and train the few-shot learner again. The above steps repeated till stopping criterion is reached. After training, we expect that the few-shot learner has acquired the transferable knowledge (the optimized feature representations) suitable for novel task of the same setting as in the episodic training. Us- ing benchmark datasets, we demonstrate that our model outperforms other unsupervised few-shot learning methods and approaches the performances of fully supervised models.
2 RELATED WORKS
In the paradigm of episodic training, few-shot learning algorithms can be divided into main categories: "learning to optimize" and "learning to compare". The former aims to develop learning algorithm which can adapt new task efficiently using only few labeled examples with few steps of parameter updating (Finn et al. 2017 Ravi & Larochelle 2016 Mishra et al. 2017 Rusu al. 2018: Nichol & Schulman, 2018 Andrychowiez et al.J (2066), and the latter aims learn 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 al., 2018,, Sung et al. 2018 Liu et al.) 2018). In the present study, focus 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 model, in term of that we carry out progressive clustering and episodic training concurrently, and the two processes facilitate with each other. Khodadadeh al. (2018) proposed method called UMTRA, which uti-
2

---

Under review as a conference paper at ICLR 2020
lizes the statistical diversity properties and domain-specific augmentations to generate training and validation data. Antoniouu Storkey (2019) proposed a similar model called AAL, which uses data augmentations of the unlabeled support set 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 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. (20T6) 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 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 these studies have integrated progressive clustering and episodic training in few-shot learning as we do in this work.
METHOD
In this section, we describe the model UFLST in detail. Let us first introduce some notations. Denote the model at the training round as M (x:) the unlabeled dataset with the number of examples N, and {2;}' the corresponded feature vector with dimentionality D, which given by fo: : x where for representing the feature extracter and 0 the training parameters of M'. { and { represent, respectively, the selected features and unlabeled data after removing outliers from the clustering results, and { the corresponding pseudo labels.
M² 2,
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 mea- sure the distance between data points (Qin et al.) 2011 Zhong et al. (017)) 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,
R(2, k) {2, ((2 E (2)
where N (2, k) denotes the k nearest neighbours z. R(z,, k) imposes that z and each element of R(2, k) are mutually k nearest neighbours of each other. Second, we compute KRJD between two feature points, which given by
Ju = 1 R(2, R(2,, k)
R[ k) R( k)]
Compared to the Euclidean distance, KRJD takes into account the reciprocal relationship between data points, and hence is stricter rule measuring whether two feature points matches or not. We find that KRJD is crucial to our model, which outperforms the Euclidean metric demonstrated in Fig. (more comparisons of two metrics are given in Appendix(A]
3.1.2 DENSITY-BASER SPATIAL CLUSTERING ALGORITHM
For the clustering strategy, we choose the density- baased spatial clustering algorithm (DBSCAN) (Es- ter 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 detect outliers noise points, which is very useful the beginning of training when the distribution of data points in the embedding space is highly noisy; 3) DBSCAN does not need specify the number of clusters to be generated, which is appealing for unsupervised learning.
3

---

Under review as a conference paper at ICLR 2020
(A)
TT
2
2
327
327
(B)
2
2
2
6
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 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 class. KRJD outperforms the Euclidean metric, in term of it includes more positive examples in the ranking list.
After removing noisy points (outliers) as done DBSCAN, pseudo labels (i.e., cluster identities) of data points {T:} can be expressed as,
J DBSCAN(e, (,,
where denotes the maximum distance for two points to be considered 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 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, construct number of episodic tasks, denoted T TT.,,....,'ss } with S the number of tasks, from the pseudo-labeled data set { M. For each episodic task, we randomly sample No classes and Næ 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 proto- type loss, which aims to learn the prototypes of each class and discriminate a novel example based on its distances the prototypes. In this case, we further split Ng into support set and query set Q, i.e., Ng Ns + No. Following Snell et al. (2017), we choose larger value of Nc in train- ing than that in testing, but keeps Ng the same. The other way implement few-shot learning is to use the triplet loss the hardtriplet loss, which separates examples from different classes with positive margin m. In this case, no splitting support and query data needed. To mine hard negative examples in triplets, we also use larger No in training than that in testing.
3.2.2 LOSS FUNCTIONS
Two types of loss functions are used 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
exp(-1l= cp.13)
Lz = Ee expl exxp<ll== Ch -cx113)
(4)
where C2 is the prototype of class k given by Cs Exes,, (zi)/Sn, Sr. and query point. In implementation, we choose to minimize the negative log value Eq. i.e., 12, c;; 0) - log (2, cx: f); as the log value better reflects the geometry of the loss function, making easy to select learning rate to minimize the loss function.
4

---

Under review as a conference paper at ICLR 2020
Algorithm Unsupervised Few-shot Learning via Self-supervised Training (UFLST)
Input: Unlabeled dataset {a;}, initialized model parameters 6"
Output: Trained model parameters 0²"
1: t=0
2: repeat
3: Clustering:
4: Extracting features { {ar} using the feature extractor foe.
5:
Computing K-reciprocal nearest neighbours R(z;, k) of each 2j. Calculating Jaccard distance matrix J based on (R, k))*
6:
7:
Clustering data using DBSCAN and generating pseudo labels {wr Removing outliers and obtaining the pseudo-labeled dataset (7,, Di
8:
9:
Episodic Training:
10: s =
11:
repeat
12:
Constructing episodic task T by randomly sampling No classes with Ng examples per class from { 3.
13:
Updating model parameters 0 by training the few-shot learner on T
15:
until = S
f t
17:
until / = T
The other is the triplet loss (Weinberger & Saul 2009), which has been widely used in face recogni- tion and image retrieval. The triplet loss Ltriplet consists of several triplets, each of which includes query feature 2, positive feature 2 and negative feature 2 and is written
Leriplec(2, 2 ;0) = max(0, || 2
++1 - ||| +12
(5)
where m controls the margin of two classes, and the hinge term plays the role of correcting triplets, that the difference between the similarities of positive and negative examples to the query point is larger than a margin m. However, the above form, positive pairs in those "already correct" triplets will longer be pulled together due the hard cutoff. We therefore replace the hinge term by soft-margin formulation, which gives
SM a ; ;0) = log [1 exp(1I= - =+11 - ||> - 11 m)]
(6)
Eq. 6 is similar Eq. but it decays exponentially instead of having hard cutoff and tends 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 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 [
EXPERIMENTS
4.1 DATASETS
We evaluate our model on two benchmark datasets, which are Omniglot (Lake et al. M5rket1501 (Zheng et al. 2015).
2015 and
Omniglot contains 1623 different handwritten characters from 50 different alphabets. There 20 examples in each class and each of them was drawn by a different human subject via Amazon's split data into two parts: 1200 characters for
Mechanical Turk. Following Vinyals et al. (2016), training and 423 for testing, but we did not augment data with rotations (this is unnecessary in our model), and instead of resizing images to 28 28, resized them to 32 32.
Market-1500 is person re-identification (Re-ID) dataset containing 32668 images with 1501 iden- tities captured from 6 cameras. The dataset is split into three parts: 12936 images with 751 identities
5

---

Under review as a conference paper at ICLR 2020
forming the training 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 DETAILS
When training on the Omniglot dataset, we chose the model architecture to be the same as that in Vinyals al. (2016), which consists of four stacked layers. Each layer comprises 64-filter 3 convolution, followed by a batch normalization, a ReLU nonlinearity, and 2 2 max max--ooling. When training on the market1501 dataset, due high variances pose and luminance, we chose use highly expressive model (Xiong et al. 2018), which consists of Resnet50 pretrained on ImageNet as backbone, and a batch normalization layer after the global max max- poolloooin layer to prevent overfit- ting. Our evaluation protocol on market 501 is different from that in Zheng et al. (2015), where they reported Cumulative Matching Characteristic (CMC) and the mean average precision (mAPs); while consider the performance of 1-shot learning, which mimics the typical single query condition in a person Re-ID task.
When training with the triplet loss, set the margin between positive and negative examples to be 0.5, and the number of training rounds only 50 epochs in each round. We used Adam with momentum 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 examples per class in each episodic task. When constructing triplets with hard example mining, we didn't '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 (Nc = 60 in Omniglot and Ne 30 in M5rket1501), which leads better performances as empirically observed in [nell al. (2017). Other parameees are set to be the same training with the triplet loss.
20. To avoid overfitting, the model fine-tuned for
(A)
3u Seee
Round1
Round2
Round3
(B) 1.0
(C)
1.0
0.9
0.8
Accuracy
NM1
0.8
0.6
0.7
Triplttass
TripiatLoss
0.4
Hard ettoss PrototypeLoss
0.6
Protetypoloss
ripeeti
10 Training Round
20
10 Training Round
20
Figure 3: Behaviors of progressive clustering. (A) Visualizing clustering results 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.
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, observe that as learning progresses, the organization of data points is improved continuously, indicat- ing that model "discovers" the underlying structure of data gradually. As illustrated in Fig. 3

---

Under review as a conference paper at ICLR 2020
initially, all data points are intertwined with each other and structure exists. Over training, clus- ters gradually emerge, in the sense of that data points from the same class are grouped together and the margins between different classes enlarged. Appendix presents more detailed illustra- tion of the clustering process. We quantitatively measure the clustering quality by computing the Normalized Mutual Information (NMJ) between real labels {ūr}* (i.e., the ground truth) and pseudo labels { which is given by,
NMI (10.), (0.)) = I(10. (8E1)
VH( H
where / -(:-) is the mutual information between { and {. and (-) the entropy. The value of NMI lies in [0, 1], with 1 standing for perfect aligmment between two sets. Note that NMI is independent of the permutation of labeling orders. As shown Fig. BB, the value NMI increases with the training round and gradually reaches to high value close 1. Remarkably, the value of NMI well predicts the classification accuracy of the learning model (comparing Fig. 33 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
the performances of model on the Omniglot dataset compared with other meth- ods. We note that using the triplet loss, our model already outperforms other state-of-the-att unsu- pervised few-shot learning methods, including CACTUs (Hsu al. 2018), UMTRA (Khodadadehi ct al. 2018), and AAL (Antoniou & Storkey 2019). to large extend. Using the prototype loss, the performance of our model is further improved. The best performance of our model is achieved when
Table I presents Presentssstss
using the hardtriplet loss. Remarkably, the best performance of our model approaches to that of two supervised models, which 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.80
92.74 74
62.20
77.50
CACTUS-MAMIL Hsu et al.
2018
68.84
87.78
48.09
73.36
CACTUS-ProtNee ProtNets Hsu et al. 2018
68.12
83.58
47.75
66.27
AAL-MAML+H (Antoniou Storkey
2019
88.40
97.96
70.21
88.32
AAL-ProtoNets (Antomou & Storkey
2019
84.66
89.14
68.79
74.28
UFLST-Trppeeloo
88.68
96.65
73.21
90.11
Prottyyoooosypelosss
96.51
99.23
90.27
97.22
UFL Tard
97.03
99.19
91.28
97.37
MAML (Finn al. 2017) (Supervised)
98.7
99.9
95.8
98.9
ProtoNets (Snell al. 2017) (Supervised)
98.8
99.7
96.0
98.9
Table 1: Performances of different unsupervised few-shot learning models on Omniglot under dif- ferent settings.
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 unsu- pervised few-shot learning result on this dataset the literature. Rahimpour Qi (2018) report the supervised results under the 100-way 1-shot scenario. To evaluate our model, we trained su- pervised 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 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 model achieves encouraging performances compared to the supervised method, in particular,
7

---

Under review as a conference paper at ICLR 2020
in the scenario of low-way classification, which suggest that model is feasible in practice for person Re-ID when annotated labels are not unavailable.
5-way
10-way
15-way
20-way
50-way
100-way
UFLST- UFLST-Proute SwS.T---Pootttllosss......
72.8
63.0
56.2
53.4
42.5
35.4
88.3
81.2
75.8
73.0
62.5
54.0
HILST-HardTriiplee Our supervised model
91.4
86.9
81.6
80.4
70.1
62.1
96.8
94.7
92.5
91.1
83.7
77.3
ARM (Rahimpour & Qi 2018)
76.99
Table 2: Performances of our model on Market1.001 with different settings. The supervised model adapted from Xiong 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 DATASET
We also evaluate how our model relies on the number of unlabeled examples. Table presents the results on the Omniglot dataset with varying number of training examples. Overall, the model per- formance improved when the number of training examples increases. Notably, by using only quarter of the unlabeled data, model already achieves performances comparable other unsu- pervised few-shot learning methods (comparing UFLST-300 with those in Table T. This demon- strates the feasibility of our model when the number of unlabeled examples is not large.
5-way Acc.
20-way Acc.
Number of Classes
I-shot
5-shot
1-shot
5-shot
UFLST-200
82,83
92.97
65,85
83,73
UFLST-300
86.03
95.05
70.52
87.60
UFLST-400
91.30
97.27
78.64
92.50
UFLST-500
95.27
98.86
87.02
96.05
UFLST-1200
97.03
99.19
91.28
97.37
Table 3: Performances of model Omniglot using different numbers of unlabeled training examples. The hardtriplet loss is used.
DISCUSSION
In this study, we have proposed an unsupervised model UFLST for few-shot learning self- training. 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 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 rently, 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.
optimized concur-
On the Omniglot dataset, our model outperforms other state-of-the-art unsupervised few-shot learn- ing methods to large extend and approaches to the performances of supervised modes. On the M50 dataset, our model also achieves encouraging performances compared to a supervised method. The high effectivvness of our model makes us think about why it works. Few-shot learn- ing 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 extract good feature representations that are transferable to novel but related
8

---

Under review as a conference paper at ICLR 2020
tasks. To this end, the real labels of data are helpful but not essential, and construct pseudo- labeled 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, 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.
REFERENCES
Marcin Andrychowicz, Misha Denil, Sergio Gomez, Matthew Hoffmann, David Pfau, Tom Schaul, Brendan Shillingford, and Nando De Freitas. Learning to learn by gradient descent by gradient descent. Advances neural information processing systems, pp. 3981-3989, 2016.
Antreas Antoniou and Amos Storkey. Assume, augment and learn: Unsupervised few-shot meta- learning via random labels and data augmentation. arXiv preprint arXiv:1902.09884, 2019.
Mathilde Caron, Piotr Bojanowski, Armand Joulin, and Matthijs Douze. Deep clustering for unsu- pervised learning of visual features. In Proceedings of the European Conference on Computer
Vision (ECCV), pp. 132-149, 2018.
Adam Coates, Andrew Ng, and Honglak Lec. An analysis of single-layer networks in unsuper- vised feature learning. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pp. 215-223, 2011.
Yin Cui, Feng Zhou, Yuanqing Lin, and Serge Belongie. Fine-grained categorization and dataset bootstrapping using deep metric learning with humans in the loop. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1153-1162, 2016.
Virginia R de Sa. Learning classification with unlabeled data. In Advances in neural information processing systems, pp. 112-119, 1994.
Emmanuel Dupoux. Cognitive science in the of artificial intelligence: A roadmap for reverse- engineering the infant language-learner. Cognition, 173:43-59, 2018.
Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu, et al. A density-based algorithm for discovering clusters in large spatial databases with noise. In Kdd, volume 96, pp. 226-231, 1996.
Hehe Fan, Liang Zheng, Chenggang Yan, and Yi Yang. Unsupervised person re-identification: Clustering and fine-tuning. ACM Transactions on Multimedia Computing, Communications, and Applications (TOMM), 14(4):83, 2018.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 1135. JMLR. org, 2017.
Alexander Hermans, Lucas Beyer, and Bastian Leibe. In defense the triplet loss for person re- identification. arXiv preprint arxiv: MixXiii1003.000 703.07737, 2017.
Kyle Hsu, Sergey Levine, and Chelsea Finn. Unsupervised learning via meta-learning. arXiv preprint utXiv11810.0233. 2018.
Siavash Khodadadeh, Ladislau Bölöni, and Mubarak Shah, Unsupervised meta-learning for few- shot image and video classification. arXiv preprint 1 181.11889,, 2018.
Brenden M Lake, Ruslan Salakhutdinov, and Joshua B Tenenbaum. Human-level concept learning through probabilistic program induction. Science, (8006266):1332-1333 2015,
Yann LeCun, Léon Bottou, Yoshua Bengio, Patrick Haffner, al. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 2::27727782222 1998.
Yanbin Liu, Juho Lee, Minseop Park. Sachoon Kim, Eunho Yang, Sung Ju Hwang, and Yi Yang. Learning to propagate labels: Transductive propagation network for sho- learning. arXiv preprint aivi 10002, 2018.

---

Under review as a conference paper at ICLR 2020
Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9Nov):2579-2666 2008.
David McClosky, Eugene Charniak, and Mark Johnson. Effective self-training for parsing, In Proceedings of the main conference human language technology conference of the North American Chapter of the Association of Computational Linguistics, pp. 152-159. Association for Computational Linguisties, 2006.
Nikhil Mishra, Mostafa Rohaninejad, Xi Chen, and Pieter Abbeel. A simple neural attentive meta- learner. arXiv preprint arXiv: 1707003111, 2017.
Alex Nichol and John Schulman. Reptile: a scalable metalearning algorithm. arXiv preprint urXiv:180300299: 2, 2018.
Danfeng Qin, Stephan Gammeter, Lukas Bossard, Till Quack, and Luc Van Gool. Hello neighbor: Accurate object retrieval with k-reciprocal nearest neighbors. In CVPR 2011, pp. 777-784. IEEE, 2011.
Alireza Rahimpour and Hairong Qi. Attention-based few-shot person re-ienetiiiidntt using meta learning. CoRR, 0td//800.096133 2018. URLL/ttt:///axxxv.rr///ab////// 09611
Sachin Ravi and Hugo Larochelle. Optimization as a model for few-shot learning. 2016.
Mengye Ren, Eleni Triantafillou, Sachin Ravi, Jake Snell, Kevin Swersky, Joshua Tenenbaum, Hugo Larochelle, and Richard S Zemel. Meta-leaming for semi-supervised few-shot classifica- tion. arXiv preprint ww..vv1803.000.
2018.
Andrei A Rusu, Dushyant Rao, Jakub Sygnowski, Oriol Vinyals, Razvan Pascanu, Simon Osin- dero, and Raia Hadsell. Meta-leariing with latent embedding optimization. arXiv preprint arXiv:1807. 100600, 2018.
Uri Shaham, Kelly Stanton, Henry Li, Boaz Nadler, Ronen Basri, and Yuval Kluger. Spectralnet: Spectral clustering using deep neural networks. arXiv preprint 1801 1001:1880100187, 2018.
Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning. In Advances in Neural Information Processing Systems, pp. 4077-4087, 2017.
Liangchen Song, Cheng Wang, Lefei Zhang, Bo Du, Qian Zhang, Chang Huang, and Xinggang Wang. Unsupervised domain adaptive re-identification: Theory and practice. arXiv preprint arXiw.1807.11334, 2018
Michael Steinbach, Levent Ertöz, and Vipin Kumar. The challenges of clustering high dimensional data. In New directions in statistical physies, pp. 273-309. Springer, 2004.
Flood Sung, Yongxin Yang, Li Zhang, Tao Xiang, Philip HS Torr, and Timothy M Hospedales. Learning to compare: Relation network for few-shot learning. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 1199-1200s 2018.
Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Daan Wierstra, et al. Matching networks for one shot learning. In Advances in neural information processing systems, pp. 3630-3638, 2016.
Jiang Wang, Yang Song, Thomas Leung, Chuck Rosenberg. Jingbin Wang. James Philbin, Bo Chen, and Ying Wu. Learning fine- ine-ggrined image similarity with deep ranking. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp.
2014a.
Rui Wang, Jun-Yun Zhang, Stanley A Klein, Dennis M Levi, and Cong Yu. Vernier perceptual learning transfers to completely untrained retinal locations after double training: A piggybacking effect. Journal of Vision, 14( 14(13):12-12, 2014b.
Yu-Xiong Wang, Ross Girshick, Martial Hebert, and Bharath Hariharan. Low-shot learning from imaginary data. In Proceedings of the IEEE Conference Computer Vision and Pattern 2018.
Recognition, pp.
Kilian Q Weinberger and Lawrence K Saul. Distance metric learning for large margin nearest neigh- bor classification. Journal of Machine Leaming Research, 10(Feb):207-244 2009.
10

---

Under review as a conference paper at ICLR 2020
Junyuan Xie, Ross Girshick, and Ali Farhadi. Unsupervised deep embedding for clustering analysis. In International conference on machine learning, pp. 478 1778-877.4 2016.
Fu Xiong, Yang Xiao, Zhiguo Cao, Kaicheng Gong, Zhiwen Fang, and Joey Tianyi Zhou. Towards good practices on building effective enn baseline model for person re-identification arXiv preprint arXiv:1807. 1042, 2018.
Bo Yang, Xiao Fu, Nicholas D Sidiropoulos, and Mingyi Hong. Towards k-means-friendly spaces: Simultaneous deep learning and clustering. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 3861-3870. JMLR. org, 2017.
Liang Zheng, Liyue Shen, Lu Tian, Shengjin Wang, Jingdong Wang, and Qi Tian. Scalable person re-identification: A benchmark. In Proceedings of the IEEE international conference on computer vision, pp. 1116-1124, 2015.
Zhun Zhong, Liang Zheng, Donglin Cao, and Shaozi Li. Re-ranking person re-identification with k-reciprocal encoding. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1318-1327, 2017.
A K-RECIPROCAL JACCARD JACCARR DISTANCE (KRJD)
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 dimensionalityy" problem (Steinbach et al., 2004). Recent studies on learning representations with deep neural networks have made promising progress for clustering algorithms (Xie et al. [0166] 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 suitable distance metric. For some datasets, such as MNIST (LeCun et al. 1998) and STL (Coates et al., 201T), it is adequate to use the Euclidean distance in the feature space cluster data well. However, for other datasets, such as Omniglot (Lake et al.) 2015) and Market 551 (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 use the k-reciprocal Jaccard distance (KRJD) metric originally proposed for object retrieval Qin et al. (201T) 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,
B) |An B
AAUBI
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 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 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 data point. KRJD transfers Z into discrete k-reciprocal ranking list R by first calculating the nearest neighbours (KNN) of each element in Z and then re- re-ranking them. Once R is available, Z. Denote the nearest neighbours the feature point 24 to be
apply Eq. 8 to calculate the Jaccard distance of
N2z, k) {2] 2 ...,, 2 Then, the k-reciprocal nearest neighbours (KRNN) of 2; is obtained by re-ranking the KNN list, which is written as,
R(= k) = {2, 1(z, E N(2,, k)) (2) E (22,,))))
(10)
Compared to KNN, KRNN is a more strict and accurate measurement of ranking, so that more positive examples appear in the top l ranking list, as demonstrated in Fig. and Fig. obtaining KRNN of each point, we calculate KRJD between two points by
After
[[ k) R(z R( k) U R(z,k))
J
(11)
11

---

Under review as a conference paper at ICLR 2020
(A)
m
62
6U
MU
MHU
2
53
40
51
33
33
51
m
6TU
2
612
MY
MHU
m
K-U
(B)
2
U
2
2
2
2
252
252
306
252
252
252
306
306
306
306
2
U
2
U
2
2
U
2
252
252
252
252
252
252
306
306
252
306
(C)
6tG
GTU
6TU
6721
660T
ano
600T
X
61U
894
690
GTU
6721
atv
6TU
61U
6TU
O
GOUT
Figure 4: Top 10 neighbours of 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 (A), (B) and (C): the ranking result using the Eu- clidean metric. Lower panels in (A), (B) and (C): the ranking result using KRJD. The KRJD metric outperforms the Fuclidean metric,
of includes more positive examples in the ranking list.
12

---

Under review as a conference paper at ICLR 2020
(A)
118
118
558
118
118
558
118
1173
1111
118
118
118
118
558
118
558
118
558
1078
(B)
127
1292
127
266
266
127
127
1292
266
(C)
636
636
636
939
1048
633
636
942
892
636
/1
636
636
636
636
636
942
1048
633
1081
942
Figure 5: Top 10 neighbours of chosen query image from the Market1501 dataset. Black box: the query image. Green box: the positive images 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.
13

---

Under review as a conference paper at ICLR 2020
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 feature points. In the present study, choose be the mean of top P minimum distances of the KRJD matrix J, which is given by,
Etop(J,P) P)
(12)
To determine the value of P. we set p= p pl{ ). where p is prperr-rrameter representing the portion of points selected over the whole set { Increasing P 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 p has the opposite effect.
Table 4 presents the effects different values of p on the model performances. We see that when many clusters and the number of examples
small, the performance is not good, since there in each cluster is small, which makes it hard to construct episodic tasks having enough examples to train the model; when the value of p is large, the model performance is also bad, since this case, it is hard to generate sufficiently different episodic tasks. For large we may reduce the value of Nc to alleviate the problem (note that in our model, the learning scenario affects the clustering behavior).
5-way Acc.
20-way Acc.
1-shot
5-shot
1-shot
5-shot
= 1 10 10 No 60
78.88
92.73
59.49
81.50
P 10
Nc 60
82.85
94.82
64.83
85,61
3 x 10-5,
NC 60
91.43
97.79
78.48
93.04
= x 10-5, Nc 60
97.57
99.35
92.62
97.82
P 10-5" Nc 60
97.03
99.19
91.28
97.37
P 6 10-5 Nc 60
97.64
99.34
93.39
98.06
7 X 10-5 Nc 60
58.35
79.24
34.17
58.33
P 10 NN 60
58.10
78.95
33.90
58.12
0 7 X 10 NC 30
97.16
99.12
91.28
97.48
8 X 10 NN = 20
97.49
99.25
92.14
97.72
Table Effects of the p value in DBSCAN model performances. The hyper-parameters are given
in Sec.
C COMPARING THE TRIPLET LOSS AND THE SOFT-MARGIN TRIPLET LOSS
In Sec. 3.2.2 S.c.3 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 mart-margin triplet loss tends to be numerically more stable during training. Table presents presents the model performances using the two loss functions.
D RELATIONSHIPS BETWEEN THE LOSS FUNCTIONS
In Sec. and 4.5 we observe that the model trained with the prototype loss has better perfor- mance 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.
14

---

Under review as a conference paper at ICLR 2020
5-way Acc.
20-way Acc.
1-shot
5-shot
1-shot
5-shot
Omniglot
(ard-cutof(m==O.5)
95.22
99.00
88.14
96.48
Hard-cutpf(m=11.0)
96.44
99.15
89.80
96.99
Soft-margin(m=0.5)
96.60
99.15
90.19
97.14
Soft-margin(m=
97.03
99.19
91.28
97.37
M5r
Hard-cutoff(m=O05)
91.00
98.07
77.84
93,88
Hard-cutoof(m==1.0)
91.91
98.10
79.70
93.78
Soft-marginmm=0.5)
93.70
98.49
82.70
95.00
(aft-maarin(m=110)
92.34
98.32
80.95
94.41
Table 5: Comparison of the soft-margin triplet loss and the hard cutoff triplet loss two datasets with margin m = 0.5 and m 1.0.
Consider Ne- I-shot episodic learning scenario, where prototype eg is the support point zg. the prototypical loss is written
expl exp(-11== -2p13)
proto =x;0) log
Σx exp(pplpp (ol--012220 2x12)
- log
1 - Ekep exp(112 - 2pl12 24 1x1
(13)
loog
1 +
exp(11> 2zp
|| z 12)
During training. we construct each episodic task by randomly sampling No classes and Ng exam- ples per class. When using the prototype loss (Eq. 13). a query point is pulled towards the corre- sponded support point Ep, and meanwhile, is pushed away from all other support points {=x {=x) whereas, when using the triplet soft-margin loss (Eq, (6). the query point = only pushed away from one of other support points z This implies that in each update, Ltriplet-SM only interacts with single negative example from one of other classes and ignores many other negative examples. When Ne is small, optimizing the model with the two loss functions has no big difference. For example, when Nc = 2 and m = 0, Eq. and T3 become exactly the same. However, when Nc becomes larger, the possible number of triplets grows cubically with Ng and linearly with Nc. which makes it difficult to select non-trivial triplets. In such situation, optimizing on these uninformative triplets leads the problem that the model gets stuck into a local optimum and suffers slow convergence. This justifies why the model has inferior performance using the triplet loss compared to using the prototype loss.
The inefficiency of the conventional triplet loss motivate to mine hard triplets to alleviate its shortcomings (Wang al. 40 Cui 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 batch, i.e., we select the hardest positive and the hardest negative examples when forming the triplets, and obtain
Irtrppltt-Si Seoplett-SM. SM = log exp( max
-1222 min -,,((=)
-|=- 1112-z,, =n + m))
(14)
-,E(++)
Compared to Eq. 13 which pushes a query point away from all other support points from differ- ent classes, Eq. 14 focuses 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 value the model performance.
15

---

Under review as a conference paper at ICLR 2020
5-way Acc.
20-way Acc.
margin
1-shot
5-shot
1-shot
5-shot
m = 0
96.59
99.14
90.35
97.11
m 0.3
96.09
98.95
89.43
96.65
m = 0.5
96.60
99.15
90.19
97.14
m 1.0
97.03
99.19
91.28
97.37
m 3.0
96.00
98.96
88.30
96.56
Table 6: The model performances using the hardtriplet loss with different values on Omniglot.
E CLUSTERING BEHAVIORS OF DBSCAN
Following Fig. in the main text, we further illustrate the clustering behavior of DBSCAN on Om- niglot in more detail. As shown in Fig. 6 at the first few rounds of learning, feature points { are unstructured and noisy, they are intertwined with each other, and DBSCAN tends to cluster all data points into few dominant clusters. Along with learning, the number of clusters keeps increasing, and the number of data points in each cluster becomes more evenly distributed. Eventually, the number of clusters generated the final training round around 1100, which is close the the real number of 1200 in the Ominglot dataset, indicating that our model, which combining progressive clustering and episodic learning, is able discover the underlying structure of the data manifold.
6648
Round1, clusters: 586
1541
Round2, # of clusters: 709
Counts
188
Round3, clusters: 790
117
Round4, of clusters: 832
Round5, of clusters: 895
Clusters
50
Figure 6: Clusters generated by DBSCAN over training rounds. The results of the first rounds are shown. For the convenience of visualization, we only display 50 clusters and the number of data points in each them.
F THE FREQUENCY OF CLUSTERING DURING TRAINING
Number of Update Epochs UFLST-Tripetloss
5
10
20
30
40
97.43
97.51
96.91
97.03
97.44
97.80
97.93
Table 7: 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. Experiments carried out 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 taken before updating the clustering in each round? We find that model is very robust to
16

---

Under review as a conference paper at ICLR 2020
the frequency term. We get 97.43% accuracy under the 5-way 1-shot scenario when the model is trained with an extremely low clustering frequency value, c.g., only trained with one epoch before clustering. Also, get 97.93% when trained with 40 epoch before clustering (Table 7
G RESULTS ON MINI-MMAGENET
(5.1)
(5,5)
(5,20)
(5, 50)
Training fram scratch
25.17
33.90
39.56
41.45
BiGAN knn-nearest neighbors
25.56
31.10
37.31
43.60
BiGAN linear classifier
27.08
33.91
44.00
50.41
BiGAN MLP with dropout
22.91
29.06
40.06
48.36
BiGAN cluster matching
24.63
29.49
33.89
36.13
BiGAN CACTUs MAML
36.24
51.28
61.33
66.91
BiGAN CACTUs ProtoNets
36.62
50.16
59.56
63.27
DeepCluster knn-nearest neighbors
28.90 42.25
56.44
63.90
DeepCluster linear classifier
29.44 39.79
56.19
65.28
DeepCluster MLP with dropout
29.03 39.67
52.71
60.95
DeepCluster cluster matching
22.20 23.50
24.97
26.87
DeepCluster CACTUs MAML
39.90
53.97
63.84
69.64
DeepCluster CACTUs ProtoNets
39.18
53.36
61.54
63.55
UMTRA without data Augmentation
26.49
UMTTA-SShif-randon, flip
30.16
UMTRA-SShif-rrandom flip +randomly change to grayscale
32.80
UMTRA+Shift+randoo flip+random rotation+color distortions
35.09
UMTRA+AuroAugmenn
39,93 50.73
61.11 67.15
AAL-MAML+++ CHV
33.06 40.75
AAL-MAML+++ CHVR
33.21 40.34
AAL-MAML+++ CHV + CUT
33.34 39.44
AAL-MAML++ CHV DROP
30.86 40.41
AAL-MAMI+++ CHVW
33.30 46.98
AAL-MAML+++ CHVWG
34.57
49.18
AAL-MAML+++ CHV + CUT
33.09
40.11
AAL-MAML+++ CHVR DROP
31.70
39.38
AAL-MAML+++ CHV DROP + CUT
31.55
38.76
AAL-MAML+++ CHVR DROP + CUT
31.44
39.87
AAL-ProtoNets+ CHV
37.67
40.29
AAL-ProtoNets+ CHV + CUT
36.38 40.89
AAL-ProtoNets+ CHV CUT DROP
33.13 36.64
AAL-ProtoNets+ CHVR + CUT + DROP
31.93 36.45
AAL-ProtoNets+ CHVR CUT
33.92 39.87
AAL-ProtoNens+ CHV + DROP
32.12 36.12
AAL-ProtoNeus+ CHVR DROP
31.13 36.83
AAL-ProtoNeis+ CHVR
34.28
39.83
UFLST without data Augmentation
33.77
45.03
53.35
56.72
MAML. (Finn et al. 2017) (Supervised)
46.81
62.13
71.03
75.54
ProtoNets (Snell et al.
2017) (Supervised)
46.56
62.29
70.05
72.04
Table 8: Performances of different unsupervised few-shot learning models Mini-ImageNet under different settings. The accuracy with std of our model is :33.77% + 0.70%, 45.03% + 0.73%, 53.35% + 0.59%, 56.72% 0.67% 5-way I-shot, 5-way 5-shot, 5-way 20-shot, 5-way 50-shot, respectively.
Overall, training few shot learner the Mini-ImageNet dataset under the unsupervised setting very tricky. All the three aforementioned approaches adopt domain specific knowledge and data augmentation tricks in their training. For example, UMTRA uses the statistical likelihood of picking different classes for the training data of T, in case of K and large number of classes, and augmentation function 7 fors the validation data. CACTUs relies unsupervised feature
17

---

Under review as a conference paper at ICLR 2020
learning algorithm provide statistical likelihood of difference and sameness in the training and validation data T. The choice of the right augmentation function for UMTRA and AAL, the right feature embedding approach for CACTUs, and the other hyper-parameee have strong impact the performance.
The model architecture trained on the Mini-ImageNet dataset is exactly the same the Omniglot dataset, i.e., the 4-layer convnet described in Sec 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 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 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-Wart 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 model outperforms the UMTRA trained without any data augmentation to a large extent (33.77% vs. 26.49%)
Compared to the results Omniglot and M5rket1501, the results the Mini- 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,
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 hard choose suitable hyper- parameters, such as the clustering frequency,
parameters, and the learning rate. (3) The ground truth for the class number of Mini- ImaieNet 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 assign data belonging to the same class into different clusters, leading to a degenerate performance. Our model performs very well on Omniglot and Maket 501, 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 the MinilmageNet dataset and extend model to more datasets.
18


Reviews:
[{"review_id": "rkxqIg4jFr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nI 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.\n\nThe design decisions are well motivated throughout the paper.\n\nThe 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.\n\nPrincipal concerns:\n\n(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.)\n\n(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.\n\n(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:\n- \"Discriminative Unsupervised Feature Learning with Exemplar Convolutional Neural Networks\"\n- \"Representation Learning with Contrastive Predictive Coding\"\n- \"Unsupervised representation learning by predicting image rotations\"\nThe literature on using auto-encoders to learn feature representations is also relevant.\n\nIssues with details in the paper:\n\n(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?\n\n(2.2) For large datasets, the clustering algorithm might be prohibitively expensive? It would be useful to discuss the complexity of this algorithm.\n\n(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).\n\n(2.4) It is concerning that the accuracy drops sharply as \\rho increases [6, 7, 8]*10^-5 in Table 4.\n\n(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?\n\n(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?\n\n(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.\n\n(2.8) There are no error-bars anywhere in the paper.\n\nMinor comments:\n\n(3.1) Tables 3 and 4 would be easier to interpret if plotted on an axis.\n\n(3.2) The word \"concurrently\" suggests that the clustering and the training are performed simultaneously. I would prefer \"alternating\".\n\n(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\".\n\n(3.4) Remember to use \\log and \\max in latex to improve the appearance.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SyekRlaTKB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors have investigated the unsupervised few shot learning problem. They have proposed a method to learn an unsupervised few-shot learner via self-supervised training (UFLST), which consists of two alternate processes, progressive clustering and episodic training. Experimental results on several benchmark data sets validate the effectiveness. Overall, I think it is an interesting scenario and have the following comments.\n(1) The first one the about the method. The authors have tried to describe their methods in a concrete way. Nevertheless, it is better to give some justifications from the theoretical aspect. It is vital for readers to convince the superiority.\n(2) The second one is about the description. I suggest the authors to express as accurately as possible. For example, in the abstract, the authors state that ‘However, current few-shot learners are mostly supervised and rely heavily on a large amount of labeled examples.’ I do not agree with this statement since in few shot learning, there are only limited exemplars. There is a conflict between them and it will confuse the readers.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "N/A", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "H1ec-5optr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper aims to conduct few-shot learning on unlabeled data (instead of on training tasks with few-shot labeled data per task). The proposed algorithm is a trivial combination of existing clustering method and a few-shot learning method, i.e., the clustering provides pseudo labels, from which a series of few-shot training tasks are generated, and then traditional few-shot learning method can be applied afterward. Many existing techniques are integrated, e.g., k-reciprocal Jaccard distance, DBSCAN clustering, prototypical network, triplet loss, etc. The paper reported the experimental results on Omniglot and Market1501.\n\nThe paper suffers from several drawbacks: 1) lack of novelty and originality; 2) problem setting is not convincing enough; 3) only a comparison on a very easy and small dataset (Omniglot) is shown, while the comparison on Market1501 is missing; 4) lack of comparison and discussion of other related works.\n\nDetailed comments:\n\n1. A simple combination of two existing techniques (clustering followed by few-shot learning) without any in-depth analysis cannot be justified as a reasonable contribution for an ICLR paper.\n\n2. The unsupervised few-shot learning setting does not make much sense in practice: we can usually collect many labeled data to generate few-shot learning tasks since these labeled data is not required to be drawn from the same distribution as the target few-shot task (e.g., the test tasks). For example, for few-shot image classification, we can always generate training tasks from ImageNet data. In practice, we only suffer from few-shot labeled data on test tasks. Assuming that none of labeled data is available can lead to unnecessary degrade on few-shot learning performance. The authors need to present more evidence or practical application scenarios to support the practical value of this problem setting.\n\n3. Omniglot is too easy and too small for most of the recent few-shot learning methods. More challenging datasets such as ImageNet or at least its easier subsets (e.g., miniImageNet, tiredImageNet) should be considered.\n\n4. No comparison to any baseline is shown on the other dataset Market1501.\n\n5. More related works need to be compared and discussed: \n\n-Constructing learning tasks via clustering has been studies in “Hsu, K., Levine, S. and Finn, C., 2018. Unsupervised learning via meta-learning. arXiv preprint arXiv:1810.02334.” This paper shares the same idea when constructing the unsupervised episode training tasks. \n\n-Self-supervised techniques to boost the performance of few-shot learning has also been studies in “Su, J.C., Maji, S. and Hariharan, B., 2019. Boosting Supervision with Self-Supervision for Few-shot Learning. arXiv preprint arXiv:1906.07079.” and “Gidaris, S., Bursuc, A., Komodakis, N., Pérez, P. and Cord, M., 2019. Boosting Few-Shot Visual Learning with Self-Supervision. arXiv preprint arXiv:1906.05186.” This paper uses a self-supervised method called “pseudo labeling”, but other self-supervised methods should also be compared.\n\n----------------------\n\nUpdate after rebuttal:\n\nThanks for the new experiments on miniImageNet! However, I still have concerns about the novelty of the proposed idea (clustering+few-shot learning) and its similarity to previous works. In addition, the new results on miniImageNet is not very encouraging (it is necessary to provide a fair comparison). Hence, I will keep my rating unchanged. \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes an approach for unsupervised meta-learning for few-shot learning that iteratively combines clustering and episodic learning. The approach is interesting, and the topic is of interest to the ICLR community. Further, it is nice to see experiments on a more real world setting with the Market1501 dataset.
However, the paper lacks any meaningful comparison to prior works on unsupervised meta-learning. While it is accurate that the architecture used and/or assumptions used in this paper are somewhat different from those in prior works, it's important to find a way to compare to at least one of these prior methods in a meaningful way (e.g. by setting up a controlled comparison by running these prior methods in the experimental set-up considered in this work). Without such as comparison, it's impossible to judge the significance of this work in the context of prior papers.
The paper isn't ready for publication at ICLR.
Decision: Reject