Online Unsupervised Learning of Visual Representations and Categories
Authors: Mengye Ren
Tyler R. Scott
Michael Louis Iuzzolino
Michael Curtis Mozer
Richard Zemel
Venue: ICLR 2022 Submitted (2022)
Keywords: Unsupervised learning
self-supervised learning
few-shot learning
visual representation learning
visual category learning

Abstract: Real world learning scenarios involve a nonstationary distribution of classes with sequential dependencies among the samples, in contrast to the standard machine learning formulation of drawing samples independently from a fixed, typically uniform distribution. Furthermore, real world interactions demand learning on-the-fly from few or no class labels. In this work, we propose an unsupervised model that simultaneously performs online visual representation learning and few-shot learning of new categories without relying on any class labels. Our model is a prototype-based memory network with a control component that determines when to form a new class prototype. We formulate it as an online Gaussian mixture model, where components are created online with only a single new example, and assignments do not have to be balanced, which permits an approximation to natural imbalanced distributions from uncurated raw data. Learning includes a contrastive loss that encourages different views of the same image to be assigned to the same prototype. The result is a mechanism that forms categorical representations of objects in nonstationary environments. Experiments show that our method can learn from an online stream of visual input data and is significantly better at category recognition compared to state-of-the-art self-supervised learning methods.

Under review as a conference paper at ICLR 2022
ONLINE UNSUPERVISED LEARNING OF VISUAL REPRESENTATIONS AND CATEGORIES
Anonymous authors
Paper under double-blind review
ABSTRACT
Real world learning scenarios involve nonstationary distribution of classes with sequential dependencies among the samples, in contrast to the standard machine learning formulation of drawing samples independently from a fixed, typically uniform distribution. Furthermore, real world interactions demand learning on-the-fly from few or no class labels. In this work, we propose an unsupervised model that simultancously performs online visual representation learning and few-shot learning of new categories without relying on any class labels. Our model is a prototype- based memory network with a control component that determines when to form a new class prototype. We formulate it as an online Gaussian mixture model, where components are created online with only single new example, and assignments do not have to be balanced, which permits an approximation to natural imbalanced distributions from uncurated raw data. Learning includes contrastive loss that encourages different views of the same image to be assigned to the same prototype. The result is mechanism that forms categorical representations of ob- jects in nonstationary environments. Experiments show that our method can learn from an online stream of visual input data and is significantly better at category recognition compared to state-of-the-an self-superviied learning methods.
INTRODUCTION
Human and artificial agents learn from large amounts of unlabeled data through a continuous stream of experience that has strong temporal correlations and hierarchical structure. The stream of experience is determined by the fact that individuals operate in distinct physical environments, such as home and office. Transitions between environments oceur on a coarse time scale relative to the rate of encounters with objects in a given environment. The distribution over objects is strongly conditioned on the environment: frozen pizza and milk are in the supermarket, computer monitors and desks at the office. The distribution may also be nonstationary; for example, visitor may be infrequent, but when they are around, they're re encountered frequently. And finally, the distribution can be highly unbalanced: individual may interact with their co- workers daily but the boss only occasionally.
The goal of our research is to tackle the challenging problem of online unsupervised representation learning in the setting of environments with naturalistic structure. We desire learning algorithm that will facilitate the categorization of objects encountered in the environment, with few or zero category labels. In representation learning, methods often evaluate their ability classify from the representation using either supervised linear readout or unsupervised clustering over the full dataset, both of which are typically done in a separate post-hoc evaluation phase. An important aim of our predictions throughout training and evaluation, and to allow these
work is to produce predictions to guide subsequent categorization.
Unsurprisingly, the structure of natural environments contrasts dramatically with the standard scenario typically assumed by many machine learning algorithms: mini-batches of independent and identically distributed (iid) samples from a well-curated dataset. In unsupervised visual representation learning, the most successful methods rely on iid samples. Contrastive- objectives (Chen et al., 2020a; He et al., 2020) typically assume that each instance in the mini-batch forms its own instance class, throw- ing away the potential similarity between instances. Clustering- based learning frameworks (Caron et al., 2018; Asano et al., 2020; Caron et al., 2020) often assume that the set of cluster centroids remain relatively stable and that the clusters are balanced in size. Unfortunately, none of these assumptions necessarily hold true in naturalistic online streaming setting. The performance of

---

Under review as a conference paper at ICLR 2022
methods will suffer as consequence. Contrastive approaches could eventually fail if examples of the same class are pushed upart; clustering approaches will behave erratically with nonstationary and imbalanced class distributions, two key facets of the natural online non-iid learning we focus on here.
To make progress on the challenge of unsupervised visual representation learning and categorization in naturalistic setting, we propose the online unsupervised prototypical network, which performs learning of visual representations and object categories simultaneously in a single-stage process. Class prototypes are created via an online clustering procedure, and a contrastive loss (van den Oord et al., 2018) is used to encourage different views of the same image to be assigned to the same cluster. Notably, our online clustering procedure is more flexible relative to other clustering- -based represen- tation learning algorithms, such as DeepCluster (Caron et al., 2018) and SwAV (Caron et al., 2020): our model performs learning and inference as an online Gaussian mixture model, where clusters can be created online with only a single new example, and cluster assignments do not have to be balanced, which permits an approximation to natural imbalanced distributions from uncurated raw data.
We train and evaluate our algorithm Rooms (Ren et al., 2021), I), which uses imagery collected from virtual agent walking through different rooms. Unlike the experiments in Ren et al. (2021), our training is done without using any labeled data, and hence it is online and unsupervised. We compare to of-te-of-the-ar unsupervised methods SimCLR (Chen et al., 2020a), SwAV (Caron et al., 2020), and SimSiam (Chen & He, 2021). Because they rely on sampling a large batch from an offline dataset, their performance drops significantly using smaller non-iid episodes. In contrast, our method can directly learn with online streaming data from small episodes, without requiring an example buffer, and surprisingly, we even outperform these strong methods trained offline with large batches of iid data. We also used RoamingOmniglot (Ren et al., 2021) as a benchmark to investigate the effect of imbalanced classes and we find that our method is very robust an imbalanced distribution of classes. For a version of ImageNet with non-iid structure, RoaminglmageNet, we again outperform SimCLR and SwAV when using the same batch size. Finally, qualitative visualizations confirm that our online clustering procedure can automatically discover new concepts and categories by grouping few similar instances together in the learned embedding space.
recently proposed naturalistic learning dataset, Roaming-
2 RELATED WORK
Self-supervised learning. Self-supervised learning methods discover rich and informative visual representations without class labels. Instance-based approaches aim learn invariant representations of each image under different transformations (van den Oord et al., 2018; Misra & van der Maaten, 2020; Tian al., 2020; He al., 2020; Chen al., 2020a;b; Grill et al., 2020: Chen & He, 202 They typically work well with iid data and large batch sizes, which contrasts with realistic learning scenarios. Our method is also related to clustering -bannd approaches, which obtain clusters on top of the learned embedding and use the cluster assignments to constrain the embedding network. To compute the cluster assignment, DeepCluster (Caron al., 2018; Zhan et al., 2020) and PCL (Li et al., 2021) use the k-means algorithm whereas SeLa (Asano et al., 2020) and SwAV (Caron et al., 2020) uses the Sinkhorn- Knopp algorithm (Cuturi, 2013). However, they typically assume a fixed number of clusters, and Sinkhorn- Knopp further assumes a balanced assignment an explicit constraint. In contrast, our online clustering procedure is more flexible: it can create new clusters on- mn-the-fly with only single new example and does not assume balanced cluster assignments. Self-supervised pretraining or joint training has proven beneficial for online continual learning tasks (Zhang et al., 2020; Gallardo et al., 2021: Cha et al., 2021).
Representation learning from video. There has also been a surge of interest in leveraging video data to learn visual representations (Wang & Gupta, 2015; Orhan et al., 2020; Pathak et al., 2017; Zhu et al., 2020; Xiong et al., 2021). These approaches all sample video subsequences uniformly over the entire dataset, whereas our model directly learns from online stream of data. Our model also does not have the assumption that inputs must be adjacent frames in the video.
Online and incremental representation learning. Our work is also related to online and continual representation learning (Rebuffi et al., 2017; Castro et al., 2018; Rao et al., 2019; Jerfel et al., 2019; Javed & White, 2019; Hayes et al., 2020). Continual mixture models (Rao et al., 2019; Jerfel et al., 2019) designate a categorical latent variable that can be dynamically allocated for a new environment. Our model has a similar mixture latent variable setup but one major difference is that operate on example-level rather than tese- Streaming learning (Hayes et al., 2020; 2019) aims to perform representation learning online. Most work here except Rao al. (2019) assumes a fully supervised
2

---

Under review as a conference paper at ICLR 2022
Online cistteiigg
t:
Net
Concept 1
6:2
hat
Max ngreemenn
Concept ?
tx3
Net
Concept
Net
Prototype Memory
Frame Augmentattin
Prototype Memory
Figure 1: Our proposed online unsupervised prototypical network (OUPN), Left: OUPN learns directly from online visual stream. Images processed by deep neural network to extract representations. Representations are stored and clustered in a prototype memory. Similar features aggregated in concept and new concepts vector is different from all existing concepts. Right: The network learning uses self-supervision that encourages different augmentations of the same frame to have consistent cluster assignments.
be dynamically created if the current feature
setting. Our prototype memory also resembles a replay buffer (Buzzega et al., 2020; Kim et al., 2020), but we store the feature prototypes instead of the inputs.
Latent variable modeling on sequential data. Our model also relates a family of latent variable generative models for sequential data (Johnson et al., 2016; Krishnan et al., 2015; ; He et al., 2018; Denton & Fergus, 2018; Zhu et al., 2020). Like our model, these approaches aim infer latent variables with temporal structure, but they use an input reconstruction criterion.
Online mixture models. Our clustering module is related to the literature online mixture models, e.g. Bottou & Bengio (1995); Carpenter & Grossberg (1987); Anderson 1); Hughes & Sudderth (2013); Pinto & Engel (2015); Song & Wang (2005). Typically, these are designed for fast and incremental learning of clusters without having to recompute clustering over the entire dataset. Despite presenting a similar online clustering algorithm, our goal is to jointly learn both online clusters and input representations that facilitate future online clustering episodes.
Few-shot learning. Our model can recognize new classes with only one or a few examples. Our prototype-based memory is also inspired by the Prototypical Network and its variants (Snell et al., 2017; Allen et al., 2019; Ren et al., 2021). Few-shot methods can reduce or remove reliance on class labels using semi- and sule--upe learning (Ren et al., 2018; Huang et al., 2019; Hsu et al., 2019; Gidaris et al., 2019; Antoniou & Storkey, 2019; Khodadadeh et al., 2019; Medina et al., 2020).
Classical few-shot learning, however, relies on episodes of cqual number of training and test examples from fixed number of new classes. Gidaris & Komodakis (2018); Triantafillou et al. (2020); Tao et al. (2020); Zhu et al. (2021) consider extending the standard episodes with incremental learning and varying number of examples and classes. Ren al. (2021) proposed a new setup that incrementally accumulates new classes and re-visits old classes over a sequence of inputs. We evaluate our algorithm on a similar setup; however, unlike that work, our proposed algorithm does not rely on any class labels.
Human category learning. Our work is related to human learning settings and online clustering models from cognitive science (Fisher et al., 1991; Murphy, 2004; Carpenter & Grossberg, 1987; Anderson, 1991; Love et al., 2004; Lake et al., 2009). In contrast to these human learning models, model learns both representations and categories in end-to-end fashion.
3 ONLINE UNSUPERVISED PROTOTYPICAL NETWORKS
In this section, introduce our proposed model, online unsupervised prototypical networks (OUPN). We study the online categorization setting, where the model receives an input x; at every time step f, and predicts both a categorical variable Út to indicate the object class and also a binary variable â, to indicate whether this a known (u = 0) or new (u = 1) class. OUPN uses network h to encode the input to obtain embedding 2, h(x;; 6). where 0 represents the learnable parameters of the encoder network. z is then processed by a prototype memory which predicts (jt, (z).
3.1 PROTOTYPE MEMORY
We formulate our prototype memory as probabilistic mixture model, where each cluster corresponds to Gaussian distribution f(z; p. )²), with mean p. constant isotropic variance o² shared across all clusters, and mixture weights w: p(2; P) Σ. wx (2; Pı, o2) Throughout sequence, the number of components evolves as the model makes an online decision of when to create a new cluster or remove an old one. We assume that the prior distribution for the Bernoulli variable is constant (uo = Pr(u = 1)), and the prior for a new cluster is uniform over the entire space (zo = Pr(z|u = 1)) (Lathuilière et al., 2018). In the following, we formulate our prototype memory as approximation to an online EM algorithm. The full derivation is included in the supplementary materials.
3

---

Under review as a conference paper at ICLR 2022
3.1.1 E-STEP
Upon seeing the current input 2t, the online clustering procedure needs to predict the cluster assign- ment or initiate new cluster in the E-step.
Inferring cluster assignments. The categorical variable ÿ infers the cluster assignment of the current input example with regard to the existing clusters.
Pr(z, Mt = ki u 0) Pr(y = =k)
A Pr(ye = k/z,, u
(1)
Pr(ze, 0)
waf (r,K
[Z: f Pr,k', 02) softmax
log Wi =d(ze: P(.kk)
(2)
Ex WK/
where wa is the mixing coefficient of cluster k, -) is the distance function, and is an independent learnable temperature parameter that related to the cluster variance.
Inference on unknown classes. The binary variable á estimates the probability that the current
input belongs to new cluster:
Pr(ze 44 = 1) Pr(ut = =)
ig = Pr(u: = 1|z,) Pr(ze|u, 1) Pr(ue = 1)
(3)
Ex Pr(ze fz: 31 k, 0) Pr(pP
20
20
(4)
20yu0 + Ex wv flz k. x²) uo)
20200 + max P uo)
=iigmodd( - d(zz, pr,)) B)/r),
(5)
where 3 and y are separate learnable parameters related to 20 and ug. allowing us to predict different confidence levels for unknown and known classes.
3.1.2 M-STEP
Here we infer the posterior distribution of the prototypes Pr(pr,s (2..). We formulate an efficient recursive online update, similar to Kalman filtering, incorporating the evidence of the current input z; and avoiding re-clustering the entire input history. We define Pt. as the posterior estimate the mean of the k-th cluster at time step and & is the estimate of the inverse variance.
Updating prototypes. Suppose that in the E-step have determined that y/- k. Then the posterior distribution of the k-th cluster after observing is: Pr(Pr.e/aas R1, // = k)) x Pr(zelpaA: 31 = 1:) Pr(pp,.
(6)
/ p'
f(z;; 02,
(' ::-,,,, o2-11
= f Pi,,
oi. + )(-1)).
(8)
The transition probability distribution Pr(Pr. (P-.I.) is zero-mean Gaussian with variance of (1/p- 1) where p (0, 1] is some constant that we define be the memory decay coefficient. In fact, can be viewed as count variable for the number of elements in each estimated cluster, subject to the decay factor over time, if we further assume that o² = 1, ŌG = 1/0,, and &-1A = 1/02_1A The memory update equation can be formulated as follows:
â₂ E(cr,sly.] pê-- 1.4 + De,A ke,k),
(9)
3r
= Vr,A (1 (e.))
+ PI- (1- 0r,A(1 (1- (ec
Pi, Elpr,tly.]
(10)
pê,- +1
pê--
0.. =
ElweANyal = cc,e/ Σ C...
(11)
Adding and removing prototypes. Our prototype memory is collection of tuples (px, (x). We convert the probability of whether an observation belongs to new cluster into decision: if â exceeds threshold a, we create new cluster in our prototype memory. Due the decay factor p. our è estimaate of cluster can decay to zero over time, which is appropriate for modeling nonstationary environments. In practice, we keep a maximum number of K clusters, and if the memory full and try to add another cluster time t, we simply pop out the least relevant prototype pys where k' = arg min (.)): Pt Pt-1 {(pK, (w)) ((z,,))
4

---

Under review as a conference paper at ICLR 2022
Chair 324
Toble 320
Picture 457
Picture 457
Appliance 402
Appliance 434
Appliance 402
Appliance 402
Figure 2: An example subsequence of the RoamingRooms dataset, consisting of consecutive glimpses of an online agent roaming in an indoor environment, and the task is to recognize the object instances.
3.2 REPRESENTATION LEARNING
primary goal of our learning algorithm is learn good visual representations through this online categorization process. In the beginning. the encoder network is randomly initialized, and the prototype memory will not produce accurate class predictions since the representations are not informative. Our overall representation learning objective has three terms: L = Luelr + dent Cent Nnew This loss function drives the learning of the main network parameters 0, as well as other learnable control parameters B, 7. and т. We explain each term in detail below.
1. Self-supervised loss: Inspired by recent self-supervised representation learning approaches, apply augmentations on x,, and encourage the clustering assignments to match across different views. Self-supervision follows three steps: First, the model makes a prediction the augmented view, and obtains ÿ and û (E-step). Secondly, it updates the prototype memory according to the prediction (M-step). To create learning target, we query the original view again, and obtain to supervise the cluster assignment of the augmented view, j'. as in distillation (Hinton et al., -We He log V/-- Note that both Y, and 8/ are produced after the M-step so we can exclude the "unknown" class in the representation learning objective. We here introduce separate temperature parameter to control the entropy of the mixture assignment ÿt-
2015). Ciell 1 E.E-ih T
Entropy loss: In order to encourage more confident predictions we introduce loss function Cent that controls the entropy of the original prediction V. produced in the initial E-step: Cen
1
T - log St-
3. New cluster loss: Lastly, our learning formulation also includes a loss for initiating new clusters Loow- We define it to be Beta prior the expected û, and we introduce hyperparameter μ to control the expected number of clusters: Liew = - log Pr [[])) This acts as a regularizer on the total number of prototypes: if the system is too aggressive in creating prototypes, then it does not learn to merge instances of the same class; while if it is too conservative, the representations can collapse to a trivial solution.
We include full details of our algorithm in Algorithm in the Appendix.
Relation to Online ProtoNet. The formulation of our probabilistic prototype memory similar to Online ProtoNet (Ren et al., 2021). However, there are several main differences. First, we consider a decay term that can handle nonstationary mixtures, which is related the variance of the transition probability. Second, our new cluster creation is unsupervised, whereas in Ren et al. (2021) only labeled examples lead to new clusters. Most importantly, our representation learning objective also entirely unsupervised, whereas Ren et al. (2021) relies on a supervised loss.
EXPERIMENTS
In this section, we evaluate our proposed learning algorithm a set of visual learning tasks and evaluate the quality of the output categories. Different from prior work on visual representation learning, we focus online non-iid image sequences to highlight the merit of method, since that is the primary scenario of interest.
Implementation details. Throughout our experiments, we make two changes to the model infer- ence procedure defined above. First, we use cosine similarity instead of negative squared Euclidean distance for computing the mixture logits, because cosine similarity is bounded and found be more stable to train. Second, when we perform cluster inference, we treat the mixing coefficients Wi as con- stant and uniform as otherwise we find that the representations may collapse into a single large cluster.
Online clustering evaluation. During evaluation we present model sequence of all new images (unlabeled or labeled) and we would like to see how well it produces a successful grouping of novel inputs. The class label index starts from zero for each sequence, and the classes do not overlap with the training set. The model memory is reset at the beginning of each sequence.
In unsupervised readout, the model directly predicts the label for each image, i.e. the model g directly predicts St g(x):)). ). In supervised readout, the model has access to all labels up to time step / 1, and needs to predict the label for the 1-th image, i.e. de = g(x1tt> V1:t-1). We used the following metrics to evaluate the quality of the grouping of test sequences:
5

---

Under review as a conference paper at ICLR 2022
Table I: Instance and semantic class recognition results on RoamingRooms
Acc. (KNN %6)
Acc. (Lincar,56)
AMI
AP
Supervised
Supervised CNN
72.11
71.95
Online ProtoNet (Ren ot 2021)
79.02
89.94
Unsupervised
Random Network
26.73
SimCLR (Chen et al. 2020s)
50.03
52.98
44.84
48.83
SWAV (Caron al.
42.70
37.31
40.04
45.77
SwAV=Queue (Cazon at, 2020)
48.31
50.40
43.63
45.31
SimSiam (Chen & He, 2021)
47.58
44.15
43
48,24
OUPN (Ours)
52.28
Indtance Clttter
Superdtood Instance Clutter
Neaned Neighbor Bescnutt
Liner Saediut
Aec
05
-e-Durs
45
SwwY
-
400
220
420
200 Sequence Langth
100
#-SinGiam
Soquence Length
Seequemoe Length
Sequence Length
Figure 3: Comparison SimCLR, SwAV, and SimSiam with larger batch sizes RoamingRooms
Adjusted mutual information (AMI): In the unsupervised setting. we use the mutual information metric to evaluate the similarity between our prediction (ū.....: ûr) the groundtruth class ID) (y1.....9r) 9r) Since the online greedy clustering method admits a threshold parameter a control the number of output clusters, therefore for each model we sweep the value of a to maximize the AMI score, to make the score maximization of can be thought of as part of the readout procedure, and it is designed to particularly help other self-supervised learning baselines since their feature similarity functions are not necessarily calibrated for clustering.
AMImma = maxa ( ÿ(a)). The
Average precision (AP): In the supervised setting, we followed the evaluation procedure in Ren al. (2021) and used average precision, which combines both accuracy for predicting known classes as well as unknown ones.
Offline readout evaluation. popular protocol to evaluate self-supervised representation learning to use classifier trained offline top of the representations to perform semantic class readout. Since in RoamingRooms, AMI and AP are designed to evaluate novel instance classification, we included additional offline evaluation protocols for semantic classes. We considered the following classifiers:
kNN readout: A common protocol is to k-nearest-neighhor classifier to readout the learned representations. The hyperparameter k is chosen between and 39 for each model based on the validation performance (empirically, larger k is preferred).
Linear readout: Another popular protocol is to train linear classifier on top of the learned representations to given set semantic classes. We used the Adam optimizer with learning rate 1e-3 for 20 epochs of training.
Competitive methods. We compare our proposed model with the following state-of-the ofeece--ftheeeeeeeee supervised visual representation learning methods. For fair comparison online representation learning, of the following methods are trained on the same dataset as our model, instead of using their pretrained checkpoints from ImageNet.
art of-the-art self-
SimCLR (Chen et al., 2020a) is a contrastive learning method with an instance-based objective that tries to classify image instance among other augmented views of the same batch of instances. It relies on a large batch size and is often trained on well-curated datasets such as ImageNet (Deng
al., 2009).
SwAV (Caron et al., 2020) is a contrastive learning method with clustering-based objective. It has a stronger performance than SimCLR on ImageNet. The clustering is achieved through Sinkhorn- Knopp which assumes balanced assignment, and prototypes are learned by gradient descent. SwAV+Queut
SwAV variant with an additional example queue. This setup is proposed in (Caron et al., 2020) deal with small training batches. A feature queue that accumulates

---

Under review as a conference paper at ICLR 2022
Guary
Top-l Imagen specaden)
Missed Examples
1L.00
0.04
0227
0.19
D47
0.97
0.04
0.92
0.10
Figure 4: Image retrieval results on RoamingRooms In each row, the leftmost image is the query image, and top-9 retrieved images are shown to its right. For each retrieval cosine similarity score is in the top left; green border signifies correct retrieval (matching the query instance), red is false positive, yellow a miss. Recall the proportion of instances retrieved within the top-9.
Figure 5: An example subsequence of an episode sampled from the RoamingOmniglor dataset
instances across batches allows the clustering process to access more data points. The queue size is set to 2000.
SimSiam (Chen & He, 2021) is self-supervised learning method that does not require negative samples. It uses a stop-gradient mechanism and a predictor network to make sure the representations do not collapse. Through not using negative samples, SimSiam could be immune to treating images of the same instances as negative samples.
Since none of these competitive methods are designed to output classes with a few examples, we need additional clustering-based readout procedure to compute AMI and AP scores. We use simple online greedy clustering procedure for these methods. For each timestep. it searches for the closest prototype; in unsupervised mode, if it fails with sigmoid greater than a, it will create new prototype, and otherwise it will aggregate the current embedding to the cluster centroid. As explained above, the parameter is maximized on test scores to calibrate for each model.
4.1 INDOOR HOME ENVIRONMENTS
We first evaluate the algorithm using the RoaningRooms dataset (Ren et al., 2021) where the images are collected from indoor environments (Chang et al., 2017) using a random walking agent. The dataset contains 1.22M image frames and 7K instance classes from 6.9K random walk episodes. Fach frame has an object annotation with its segmentation mask and the task here is to recognize the object instance IDs. Since our task is classification, we also send the segmentation mask as an additional channel in the input. An example episode is shown in Fig. 2. The dataset is split into different home environments (60 training. 10 val, and 20 test). Each training itcration consists of a sequence of images from one of the homes. At test time, for the instance classification task, ask the model to recognize novel objects in a new sequence of images in one of the test homes. For the semantic classification task, we ask the model to classify among 21 semantic categories including "picture", "chair", "lighting", "cushion", "table", etc.
SimCLR, SWAV and SimSiam varying batch sizes (50, 100, 200, and 400). For online (non-III) settings, the notion of batch size can be understood as "sequence length". Learning rate is scaled based on batch size /256 x 0.3 using the default LARS optimizer with cosine learning rate decay. We trained for a total of 10,240,000 examples. So the total number of training steps is 10,240,00 22400000 batch size. For our proposed model, we used the batch size of 50 and trained for total of 80,000 steps (4,000,000 examples), using the Adam optimizer and staircase learning rate decay starting from 1e-3. All data augmentation parameters are the same as the original SimCLR paper, except that in RoamingRooms the minimum crop area is changed to 0.2 instead of the default 0.08.
Results. Our main results are shown in Table 1. Although self-supervised methods, such as SimCLR, SwAV and SimSiam, have shown promising results on large batch learning on ImageNet, their performances here are relatively weak compared to the supervised baseline. Adding a queue slightly improves SwAV; however, since the examples in the queue cannot be used to compute gradients, the nonstationary distribution still hampers gradient updates. In contrast, our method OUPN shows impressive performance this benchmark: it almost matches the supervised learner in AMI, and reached almost 95% of the performance of the supervised learner in AP. OUPN also outperforms the competitive methods in terms of kNN and linear readout accuracy.
7

---

Under review as a conference paper at ICLR 2022
Table 2: Results on RoamingOmmiglon
Table 3: Results on RoominglmugeNet
AMT
AP
Supervised
Supervised
Pretrain Pntrain-Supervisel
84.48
93.83
Pretrain Supervised
29.44
24.39
Online ProtoNet (Ren et al., 2021)
89.64
92.58
Online ProtoNet (Ren et al., 2021)
29.73
25.38
Unsupervised
Unsuperiisd
Random Network
17.66
17.01
Random Network
4.55
2.65
SimCI. R.R (Chen et al., 2020s)
59.06
73.50
SinCLR R (Chen al. 2020s)
6.87
12.25
SWAV (Caron 2020)
62.09
75.93
SWAV (Caron al., 2020)
9.87
5.23
Sw.AV+O Queue (Caron et al., 2020)
67.25
81.96
SwAV+Queue (Caron et al., 2020)
10.61
4.83
OUPN (Ours)
84.42
92.84
OUPN (Ours)
19.03
15.05
Uroup, Instance Clustor
Supervsed instance Custer
Nearust hoighbor Roacout
Unsor Roadout
Azi
-e- Ours
45
SimCLR
SWAV
SWAAV +
32
300
200
400
10
100
100
400
90
100
700
430
50
120
700
600
#-SmmStom
Batch Size
Tatch Stre
Tutch Stre
Figure 6: Comparison IID-trained versions of SimCLR, SwAV, and SimSiam with larger batch sizes on RoomingRooms.
To illustrate the impact of our small batch episodes, we increase the batch size for SimCLR and SwAV, from 50 to 400, at the cost of using multiple GPUs training in parallel. The results are shown in Fig. 3. Results indicate that increasing the batch size can improve these baselines, which matches expectation. Nevertheless, and SWAV using a batch size of 400, which takes 8x computational resource compared to ours. Note that the large batch experiments are designed to provide the best setting for other self-supervised methods to succeed. We do not intend to run our model with larger batch size since our prototype memory sequential module. Moreover, keeping the batch size smaller allows quicker online adaptation and less memory consumption.
method using batch size of 50 is still able to outperform SimCLR
Comparison iid modes of Sim SwAV, and SimSiam. The original SimCLR, SWAV, and SimSiam were designed to train on iid data. To study the effects of this assumption, we implemented an approximation to an iid distribution by using a large random queue that shuffles the image frames. As in the study shown in Fig. 6, we again vary the batch size for these competitive methods. All of these self-super baselines thrive with iid data; the gains of iid over non-iid can be seen by comparing Fig. 6 to Fig. 3. Larger batches help both methods again here. Interestingly, our method using a batch size of 50 non-iid data again outperforms both methods using a batch size of 400 of iid data in terms of AMI and AP. The only case where our method is inferior SimCLR is when SimCLR is trained with large batches under IID setting on semantic classification readout. This reasonable since semantic classification and IID large batch training the setting SimCLR was originally developed for. Again, IID large batch training is not what we aim to solve in this paper, and we include the IID experiments in the paper simply to better understand the failure points of existing algorithms.
Visualization on image retrieval. To verify the usefulness of the Iearned representation, we ran an image retrieval visualization using the first 5000 images in the first 100 test sequences of length 50 and perform retrieval in a leave-one-out procedure. This only aims to visualize the similarity and is different from our evaluation procedure that requires the model to predict the class labels. The results are shown in Fig. 4, and the cosine similarity scores are also provided. The top retrieved images are all from the same instance of the query image, and our model sometimes achieves perfect recall. This confirms that our model can handle a certain level of view angle changes. We also investigated the missed examples and we found that these are taken from more distinct view angles. However, note that we only computed the pairwise similarity score for retrieval, and therefore it is possible that the actual clusters are more inclusive as the model incrementally computes the average embedding as the prototype. More visualizations are provided in Appendix E.
4.2 HANDWRITTEN CHARACTERS
We also evaluated our method on a different task: recognizing handwritten characters from Om- niglot (Lake et al., 2015). In this experiment, images not organized in video-like sequence, and
8

---

Under review as a conference paper at ICLR 2022
-t-Sncit4d
-p- SwARNas -U-DUP (tund)
-0-5 B4id
-p-SwAt-ed -U-D (oirs)
100%
100%
Poladvee Parfamanes
Rolatve Parfarmacee
40%
40%
2074
055
2055
40.
50NS
1826
100.%
074
2016
-00%
192%
300%
Distractor class
Dittrcttoo proportion
Figure 7: Robustness to imbalanced distributions by adding distractors (Omniglot mixed with MNIST images). Performance is relative to the original performance and a random baseline.
models have to reason more about conceptual similarity between images in order to learn grouping. test our hypothesis concerning sensitivity
Furthermore, since this is more controllable setup, to class imbalance by performing manipulations on the episode distribution.
Our episodes sampled from the RoaningOmmigg several different contexts, each consisting of a set of classes, and in each context, classes are sampled from Chinese restaurant process. We use 1500frame episodes with 5 contexts.
dataset (Ren et al., 2021). An episode involves
Results. The results are reported in Table 2. Our model is able to significantly reduce the gap between supervised and unsupervised models, outperforming SimCLR and SwAV.
Effect of imbalanced distribution. We further study the effect of imbalanced cluster sizes by manipulating the class distribution in the training episodes. In the first setting, we randomly replace Omniglot images with MNIST digits, with probability from 0% to 100%. For example, 50% rate, an MNIST digit is over 300 times more likely to appear compared to any Omniglot character class, so the episodes are composed of half frequent classes and half infrequent classes. In the second setting, randomly replace Omniglot images with MNIST digit I images, which makes the imbalance even greater. We compared our method to SimCLR and SWAV in the iid setup, since this is the scenario they were designed for. Results of the two settings is shown to be more robust under imbalanced distribution than SimCLR and SwAV. Compared to clustering-basee -rasei methods like SwAV, our prototypes can be dynamically created and updated with no constraints on the number of elements per cluster. Compared to instance-based methods like SimCLR, our prototypes also samples the contrastive pairs more equally during learning, We hypothesize that these model aspects contribute to the differences in robustness.
shown in Fig. 7, and method
Visualization of learned categories. We visualize the learned categories in Roaming RoamingOmmiglon using t-SNE (Van der Maaten & Hinton, 2008), and the results are shown in the Appendix E.
4.3 IMAGENET IMAGES
Lastly, we evaluate on episodes composed of ImageNet images, and using the RoamingImageNer dataset (Ren et al., 2021), which has a structure analogous to RoamingOmniglot. This dataset's scale resembles RoamingRooms (around 1.3 million images), but here we focus semantic object classes instead of instance classes. We use this benchmark as a stress test: it does not fit the target scenario of an natural online exploration, but it still provides test whether method can learn semantic concepts with a large intra-class variance. We developed a form of non-iid episodes, consisting of 48 frames drawn with temporal dependence from 3 contexts. Results are shown in Table 3. Although ImageNet is a more challenging benchmark, our model is still considerably better than SimCLR and SwAV.
CONCLUSION
Our goal is develop learning procedures for real-world agents who operate online and in structured, nonstationary environments. Toward this goal, we develop an online unsupervised algorithm for discovering visual representations and categories. Unlike standard self-supervised learning, our algorithm embeds category formation in a probabilistic clustering module that is jointly learned with the representation encoder. Our clustering categories with very few examples. At the same time, we leverage self-supervised learning to acquire semantically meaningful representations. Our method is evaluated both synthetic and realistic image sequences and it outperforms state-of-the-art self-supervised learning algorithms for both the non-iid sequences we are interested in as well as sequences transformed to be iid to better match assumptions of the learning algorithms.
more flexible and supports learning of new

---

Under review as a conference paper at ICLR 2022
REFERENCES
Kelsey R. Allen, Evan Shelhamer, Hanul Shin, and Joshua B. Tenenbaum. Infinite mixture prototypes for fhw-shot learning. In ICML., 2019.
John Anderson. The adaptive nature of human categorization. Psychological review, 98(3):409, 1991.
Antreas Antoniou and Amos Storkey. Assume, augment and learn: Unsupervised few-shot meta-learning via random labels and data augmentation. CoRR, abs/ 0bs/1992.,0984, 2019. 3
Yuki Markus Asano, Christian Rupprecht, and Andrea Vedaldi. Self-labelling via simultaneous
clustering and representation learning. In /CLR, 2020. 1, 1,2
Leon Bottou and Yoshua Bengio. Convergence properties of the k-means algorithms. In NIPS, 1995.
Pietro Buzzega, Matteo Boschini, Angelo Porrello, Davide Abati, and Simone Calderara. Dark experience for general continual learning: a strong, simple baseline. NeurlPS, 2020.
Mathilde Caron, Piotr Bojanowski, Armand Joulin, and Matthijs Douze. Deep clustering for unsuper- vised learning of visual features. In ECCV, 2018. 1,2
Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin. Unsupervised learning of visual features by contrasting cluster assignments. In NeurlPS, 2020. 1, 2, 6, 8, 18
Gail A Carpenter and Stephen Grossberg, A massively parallel architecture for a self-organizing neural pattern recognition machine. Computer vision, graphics, and image processing, 37(1): 54-115, 1987. 3
Francisco M. Castro, Manuel J. Marín-Jiménez, Nicolás Guil, Cordelia Schmid, and Karteek Alahari. End-to-end incremental learning. In ECCV, 2018. 2
Hyuntak Cha, Jaeho Lee, and Jinwoo Shin. abs/2106. 14413, 2021. 2
Co21: Contrastive continual learning. CoRR,
Angel X. Chang, Angela Dai, Thomas A. Funkhouser, Maciej Halber, Matthias Nießner, Manolis Savva, Shuran Song, Andy Zeng, and Yinda Zhang. Matterport3d: Learning from RGB-D data in indoor environments. 3DV, 2017.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey E. Hinton. A simple framework for contrastive learning of visual representations. ICML, 2020a. 1, 2, 8, 14, 18
Xinlei Chen and Kaiming He. Exploring simple siamese representation learning. 2021. 2, 6,
Xinlei Chen, Haoqi Fan, Ross B. Girshick, and Kaiming He. Improved baselines with momentum contrastive learning. CoRR, abs/2003.04297, 2020b.
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. In NIPS, 2013. 2
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Fei-Fei Li. Imagenet: A large-scale hierarchical image database. CVPR, 2009.
Emily Denton and Rob Fergus. Stochastic video generation with a learned prior. In ICML, 2018. 3
Douglas H Fisher, Michael Pazzani, and Pat Langley. Conceptformation: Knowledge and experience in unsupervised learning. Morgan Kaufmann, 1991. 3
Jhair Gallardo, Tyler L. Hayes, and Christopher Kanan. Self-supervised training enhances online continual learning. CoRR, abs/2103. 14010, 2021.
Spyros Gidaris and Nikos Komodakis. Dynamic few-shot visual learning without forgetting. In
CVPR, 2018.
10

---

Under review as a conference paper at ICLR 2022
Spyros Gidaris, Andrei Bursuc, Nikos Komodakis, Patrick Pérez, and Matthieu Cord. Boosting few-shot visual learning with self superviupriisonn. In ICCV, 2019. 3
Lean-Bastiens Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre H. Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Ávila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, Bilal Piot, Koray Kavukcuoglu, Rémi Munos, and Michal Valko. Bootstrap your own latent A new approach self-supervised learning. In NeurIPS, 2020.
Tyler Hayes, Nathan D. Cahill, and Christopher Kanan. Memory efficient experience replay for streaming learning. In ICRA, 2019. 2
Tyler L.. Hayes, Kushal Kafle, Robik Shrestha, Manoj Acharya, and Christopher Kanan. REMIND your neural network to prevent catastrophic forgetting. ECCV, 2020.
Jiawei He, Andreas M. Lehrmann, Joseph Marino, Greg Mori, and Leonid Sigal. Probabilistic video generation using holistic attribute control. In ECCV, 2018. 3
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross B. Girshick. Momentum contrast for unsupervised visual representation learning. In CVPR, 2020. 1, 2, 14
Geoffrey E. Hinton, Oriol Vinyals, and Jeffrey Dean. Distilling the knowledge in a neural network. CoRR, 5bs/1503.02531, 2015. 5
Kyle Hsu, Sergey Levine, and Chelsea Finn. Unsupervised learning via meta-learning ICLR. 2019. 3
Gabriel Huang, Hugo Larochelle, and Simon Lacoste-Julien. Centroid networks for few-shot clustering and unsupervised few-shot classification. CoRR, abs/1902.086055 2019.
Michael C. Hughes and Erik Sudderth. Memoized online variational inference for dirichlet process mixture models. In NIPS, 2013.
Khurram Javed and Martha White. Meta-learning representations for continual learning. In NeurIPS, 2019. 2
Ghassen Jerfel, Erin Grant, Tom Griffiths, and Katherine A. Heller. Reconciling meta-learning and continual learning with online mixtures of tasks. NeurlPS, 2019.
Matthew J. Johnson, David Duvenaud, Alexander Wiltschko, Ryan P. Adams, and Sandeep R. Datta. Composing graphical models with neural networks for structured representations and fast inference. In NIPS, 2016.
Weonyoung Joo, Wonsung Lee, Sungrae Park, and II-Chul Moon. Dirichlet variational autoencoder. Puttern Recognit. 107:107514, 2020. 18
Siavash Khodadadeh, Ladislau Bölöni, and Mubarak Shah. Unsupervised meta-learning for few-shot image classification. NeurlPS, 2019.
Chris Dongjoo Kim, Jinseo Jeong, and Gunhee Kim. Imbalanced continual learning with partitioning reservoir sampling. In ECCV, 2020. 3
Rahul G. Krishnan, Uri Shalit, and David A. Sontag. Deep kalman filters. CoRR, abs/1511.00 15.0112,,, 2015. 3
Brenden M. Lake, Gautam K. Vallabha, and James L. McClelland. Modeling unsupervised perceptual category learning. IEEE Trans. Auton. Ment. Dev., 1(1):35 43, 2009.
Brenden M Lake, Ruslan Salakhutdinov, and Joshua B Tenenbaum. Human-level concept learning through probabilistic program induction. Science, (5006266):1332-1111
2015. 8
Stéphane Lathuilière, Pablo Mesejo, Xavier Alameda-Pineed and Radu Horaud. Deepgum: Learning deep robust regression with gaussian-unifonn mixture model. ECCV, 2018.
Junnan Li, Pan Zhou, Caiming Xiong, Richard Socher, and Steven C. H. Hoi. Prototypical contrastive learning of unsupervised representations. In ICLR, 2021. 2
11

---

Under review as a conference paper at ICLR 2022
Bradley C Love, Douglas L Medin, and Todd M Gureckis. Sustain: network model of category learning. Psychological review, 111(2):309, 2004. 3
Carlos Medina, Arnout Devos, and Matthias Grossglauser. Self-supervised prototypical transfer learning for few-shot classification. CoRR, abs/2006. 11325, 2020. 3
Ishan Misra and Laurens van der Maaten. Self-supervised learning of rereextriivariiaatteereeeeetttt In CVPR, 2020. 2
Gregory Murphy. The big book of concepts. MIT press, 2004. 3
Boris Oreshkin, Pau Rodríguez López, and Alexandre Lacoste. TADAM: task dependent adaptive metric for improved few-shot learning. In NIPS, 2018. 17, 18
A. Emin Orhan, Vaibhav V. Gupta, and Brenden M. Lake. Self-supervised learning through the eyes of a child. In NewrIPS, 2020. 2
Deepak Pathak, Ross Girshick, Piotr Dollár, Trevor Darrell, and Bharath Hariharan. Learning features by watching objects move. In CVPR, 2017. 2
Rafael C. Pinto and Paulo Martins Engel. A fast incremental gaussian mixture model. CoRR, abs/1506.04422, 2015. 3
Dushyant Rao, Francesco Visin, Andrei A. Rusu, Razvan Pascanu, Yee Whye Teh, and Raia Hadsell. Continual unsupervised representation learning. In NeurlPS, 2019. 2, 18, 19
Sylvestre-Alvies Alvise Rebuffi, Alexander Kolesnikov, Georg Sperl, and Christoph H. Lampert. icarl: Incremental classifier and representation learning. CVPR, 2017.
Mengye Ren, Eleni Triantafillou, Sachin Ravi, Jake Snell, Kevin Swersky, Joshua B. Tenenbaum, Hugo Larochelle, and Richard Zemel. Meta-learning for cemi-supervised few-shot classification. In ICLR, 2018.
Mengye Ren, Michael L. luzzolino, Michael C. Mozer, and Richard Zemel. Wandering within world: Online contextualized few-shot learning. In ICLR, 2021. 2, 5, 6, 7, 8, 9,
Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning. In NIPS, 2017. 3
Mingzhou Song and Honghin Wang. Highly efficient incremental estimation of gaussian mixture models for online data stream clustering. In Intelligent Computing: Theory and Applications III, volume 5803, pp. 174-183. International Society for Optics and Photonics, 2005. 3
Xiaoyu Tao, Xiaopeng Hong, Xinyuan Chang, Songlin Dong, Xing Wei, and Yihong Gong. Few-shot class-incremental learning. In CVPR, 2020. 3
Yonglong Tian, Dilip Krishnan, and Phillip Isola. Contrastive multiview coding. In ECCV, 2020.
Eleni Triantafillou, Tyler Zhu, Vincent Dumoulin, Pascal Lamblin, Utku Evci, Kelvin Xu, Ross Goroshin, Carles Gelada, Kevin Swersky, Pierre-Antoine Manzagol, and Hugo Larochelle. Meta- dataset: dataset of datasets for learning to learn from few examples. In ICLR, 2020. 3
Aäron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. CoRR, 0tss/887.03377 2018. 2
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. JMLR, 9(11), 2008. 9, 20, 21
Oriol Vinyals, Charles Blundell, Tim Lillicrap, Koray Kavukcuoglu, and Daan Wierstra. Matching networks for one shot learning. In NIPS, 2016. 17
Xiaolong Wang and Abhinav Gupta. Unsupervised learning of visual representations using videos. In ICCV, 2015. 2
12

---

Under review as a conference paper at ICLR 2022
Yuwen Xiong, Mengye Ren, Wenyuan Zeng, and Raquel Urtasun. Self-supervised representation learning from flow equivariance. In ICCV, 2021.
Xiaohang Zhan, Jiahao Xie, Ziwei Liu, Yew-Soon Ong, and Chen Change Loy. Online deep clustering for unsupervised representation learning. In CVPR, 2020. 2
Song Zhang, Gehui Shen, and Zhi-Hong Deng. Self Self-supervised learning aided class-incremental lifelong learning. CoRR, abs/2006.05882, 2020.
Fei Zhu, Yao Zhang, Chuang Wang, Fei Yin, and Cheng- Lin Liu. Prototype augmentation and self-supervision for incremental learning. CVPR, 2021.
Yizhe Zhu, Martin Renqiang Min, Asim Kadav, and Hans Peter Graf. S3VAE: self-supervised sequential VAE for representation disentanglement and data generation. In CVPR, 2020. 2,
13

---

Under review as a conference paper at ICLR 2022
A FULL ALGORITHM.
7, Let (0, 2, denote the union of the learnable parameters. Algorithm outlines our proposed learning algorithm. The full list of hyperparameters are included in Appendix C.
Algorithm 1 Online Unsupervised Prototypical Learning
repeat
Sser t- 0, Pnew t- O. for 1.... do Observe new input Xt- Encode imput, 2, <- 0)-
Compare to existing prototypes: [ūz, Dr] + E-step zr, P;3, T) if úi then
Assign to existing prototypes: P + M-step(z,, P. 31). else
Recycle the least used prototype if P full.
Create new prototype <- P ((z,. 1)}.
end if
Compute pseudo-labels: [_ W/] + E-step(z,, P:B.
Augment view: x f- augment(x:).
Encode the augmented view: zi t- 0)
Compare the augmented view existing prototypes: L. V11 +- E-step(z), P:B,7,T)
Compute the self-supervision loss: Luelf t- Lielf T log V/-
Compute the entropy loss: Lent + Lem U log Dt.
Compute the average probability of creating new prototypes, Prew f- Dnew + T ut. end for
Compute the new cluster loss: Lnew f- - log Pr(pnew). Sum up losses: t- Luelt + Aent + >new Lnew. Update parameters: θ <- aptimize(C,,)) until convergence return +
It worth noting that if we create new prototype every time step. then OUPN is similar standard contrastive learning with an instance-based InfoNCE loss (Chen et al., 2020a; He et al., 2020); therefore be viewed generalization of this approach. Additionally, all the losses can be computed online without having to store any examples beyond the collection of prototypes.
B METHOD DERIVATION
B.1
E-STEP
Inferring cluster assignments. The categorical variable ý infers the cluster assignment of the current input example with regard to the existing clusters.
01. Pr(ye k/z,, 0)
(12)
Pr(zelu: = k, = 0) Pr(ye = k)
(13)
Pr(ze: 0)
wk Wi](Zt: Pt,k, x²)
(14)
Σn wy f(z Pi,k' ,
exp(log wh dl Uz Pt. Dt.k) 1/2022
(15)
Σn exp(log w/. d(zz, Pi,k() /202)
softmax (log wn d(z, kt. (TT)
(16)
softmax(Pv,k),
(17)
where Wi is the mixing coefficient of cluster and d(-,)) is the distance function, and 0r is the logits. In our experiments, wi," 's are kept constant and is independent learnable parameter.
14

---

Under review as a conference paper at ICLR 2022
Inference unknown classes. input belongs to a new cluster:
The binary variable á estimates the probability that the current
Pr(u =1 1/2e)
(18)
M0
(19)
2040 + Σx wk/ wk Zri Pi.k: 02) (1)1111))) 20)
f
(20)
1 S00la En wkk (uti 02) up)
(21)
exp(log( 1 Ex wkJ Veri o (1 un)))
1
(22)
+ exp(-llo((a)) - log(un) + log(1 - -uo) + +log(2 Wk J Pt,k,
(23)
exp( log
>x exp(log(wx) d(zi, Pt,k)/ pr.x)/2022)
sigmoid(s log(
exp(log(wx) - d(zi, / 20)))
(24)
sigmoid - log( exp(vt,x))),
(25)
where log(=0) + log log(1 uo) + m log(o) + m log(2x) (2T) /2 and m is the input dimension. In our implementation, we use max here instead of logsumexp since we found max leads to better and more stable training performance empirically. It can be derived as a lower bound:
ût sigmoid log( exp(log(wx) d(zr, pr,x)/20")
(26)
2 sigmoid(s - log (max exp( - d(z,, Pt.,)) Pt.x)/2001)
(27)
sigmoid( + min d(z,, pt,x) 20
(28)
sigmoid d(z,, Pt,k) 3)/7),
(29)
where B = - 2s0
20 To make learning more flexible, we directly make 3 and as independent learnable parameters so that we can control the confidence level for predicting unknown classes.
B.2 M-STEP
Here we infer the posterior distribution of the prototypes Pr(Pr,s ZT.). We formulate an efficient recursive online update, similar to Kalman filtering. by incorporating the evidence of the current input z; and avoiding re-clustering the entire input history. We define Pt, as the estimate of the posterior mean of the k-th cluster at time step 1, and o2,, is the estimate the posterior variance.
Updating prototypes. Suppose that the E-step we have determined that y k. Then the posterior distribution of the k-th cluster after observing is:
Pr(pIa Di = k) Pr(ze|pe.a. D1 k)) Pr(pr
(30)
(31)
-Pr(zolpa.. yc= kk) /
=
=p'lzu-1)
(32)
~ f(zn 02) / S.P...i''.o,.l F') ( 12
(33)
f(zz Pt.k o² p o o2-
(34)
If assume that the transition probability distribution Pr (P:-1.k) is a zero-mean Gaussian with variance of (1/p 1)0f-1.9 where p E (0, 1] is some constant that defined to be the
15

---

Under review as a conference paper at ICLR 2022
memory decay coefficient, then the posterior estimates are:
2,0 1- P1-1A02
00 00 02 + 0
Dr, b
(35)
0² + 0 0
If of = and C1,: 1/0 11-1 = 1 it turns
formulate the update equation follows, and &r be viewed count variable for the number of elements in each estimated cluster, subject to the decay factor p over time:
0, = 1,c-1,k
(36)
1
pā Pi-1,k
pr.klu
(37)
If * k. then the prototype posterior distribution simply gets diffused at timestep t:
Pr(Pus|21a D1 + k) == P -
(38)
Gclluus = pê2-1,6
(39)
Pe,blys P1-1,k-
(40)
Finally, our posterior estimates at time are computed by taking the expectation over ys:
&. E (e
(41)
= Pr(y: k/2z)= + t..auu Pr(yt klze) (pê,-1,x + x1 - (e,N) + pê - Dr. (),
(42)
(43)
pêc-1,1 1,1 + (1, (e,,),
(44)
P..
(45)
Pr. Pr(yt- = k/zz) + Pe Pr(ye # klzz)
(46)
p
Ze G,
+ 11-1,
De.k -(,x)) + 1:- - Dr. (1 - 0c,)))
(47)
21 (1 (c,6))
- 11, - ((.x)) + (1 - (0,)) pêL-1,k
+ P1-1.6
(48)
pê.- +
p +
(1, ûr,e)
Me, (t.x))
21 p +
+ 11
(49)
1 +1
Since & is also our estimate on the number of elements each cluster, we can use to estimate mixture weights,
Gt ΣN E,,b
wr.k
(50)
Note that in our experiments the mixture weights are not used we assume that each cluster has an equal mixture probability.
C EXPERIMENT DETAILS
We provide additional implementation details in Tab. 5 and 6.
16

---

Under review as a conference paper at ICLR 2022
Table 4: Hyperparameter settings for RoamingRooms
Hyperparameter
Values
Random crop range
0.08 1.0
Random color strength
0.5
Backbone
ResNet-12 (Oreshkin et al., 2018)
Num channels
[32. 64, 128, 256]
init
0.1
init
-12.0
init
1.0
Num prototypes K
150
Memory decay
0.995
Sequence length / batch size
50 (100 eval)
Beta mean
0.5
Entropy loss Aenr
0,0
New cluster loss Anew
0.5
Threshold a
0.5
Pscudo label temperature ratio f/7
0.1
Learning rate schedule
[40k, 60k, 80k]
Learning rate
[1c-3, Ic-4, 1e-5]
Optimizer
Adam
Table 5: Hyperparameter settings for RoamingOmmigloot
Hyperparameter
Values
Random crop area range
0.08 1.0
Random color
None
Backbone
Conv-4 (Vinyals et al., 2016)
Num channels
[64, 64, 64, 64]
T init
0.1
(9 init
-12.0
Ty init
1.0
Num prototypes K
150
Memory decay p
0.995
Sequence length batch size
150
Beta mean
0.5
Entropy loss Aex
1.0
New cluster loss Auew
1.0
Threshold a
0.5
Pscudo label temperature ratio 7/7
0.2
Learning rate schedule
[40k, 60k, 80k]
Learning
[1c-3, le-4, le-5]
Optimizer
Adam
17

---

Under review as a conference paper at ICLR 2022
Table 7: Unsupervised iid learning on Omniglot using an MLP
Method
3-NN Error
5-NN Error
10-NN Error
VAE (Joo et al., 2020)
92.34=0.25
91.21=0.18
88.79:10.35
SBVAE (Joo et al., 2020)
86.90=0.82
85.10
82.96:10.64
DirVAE (Joo et al., 2020)
76.55
73.81=0.29
70.95:10299
CURL (Rao et al., 2019)
78.18
75.41=0.34
72.5110.46
SimCLR RR (Chen al., 2020a)
44.35
0.55
44.93+-0.55
SwAV (Caron et al., 2020)
42.66=0.55
0.55
44.78:+0.55
OUPN (Ours)
43.55=0.55
02.1
03.88:10.55
Table 6: Hyperparameter settings for RoaminglmageNer
Hyperparameter
Values
Random crop area range
0.08 1.0
Random color strength
0.5
Backbone
ResNet-13 12 (Oreshkin et al., 2018)
Num channels
[32, 64, 128, 256]
init
0.1
init
-12.0
init
1.0
Num prototypes K
600
Memory decay p
0,99
Sequence length batch size
48
Beta mean
0.5
Entropy loss Aent
0.5
New cluster loss Anow
0.5
Threshold a
0.5
Pseudo label temperature ratio 7/7
0.0 (i.e. one-hot pseudo labels)
Learning rate schedule
[40k, 60k, 80k]
Learning rate Optimizer
[1e-3, Ic-4, le-5]
Adam
C.1 METRIC DETAILS
For each method, used the same nearest centroid algorithm for online clustering. For unsupervised readout, at each timestep, if the closest centroid within threshold a then we assign the new example the cluster, otherwise we create new cluster. For supervised readout, we assign examples based on the class label, and we create a new cluster if and only if the label is a new class. Both readout procedures will provide our predicted class IDs and groundtruth class IDs. Both metrics are designed to be threshold invariant.
sequence of class IDs, and we will use the following metries compare
For unsupervised evaluation, we consider the adjusted mutual information score. Suppose we have two clustering U = (U.) and V = (Vj). and U, and V, are set of example IDs, and N is the total number of examples. U and V can viewed as discrete probability distribution over cluster IDs. Therefore, the mutual information score between U and V is:
AMI:
V
U UnV
NUNIVI
MI(U
log N
(51)
R
maj
Nnij a&b;
log
(52)
N
1=1 ==
18

---

Under review as a conference paper at ICLR 2022
Table 8: Effect of mem. size K Table 9: Effect of decay rate p
Table 10: Effect of Anew
RrusiinOnusigie
Reaming Rovons
OommigoO AP
RoamingRooms
RoaningOmnigiaa
Roaming
K
AMI
AP
AMI
AP
AM1
AMI
AP
Aure
AMI
AP
AMI
AP
75.33
0.9
14.19
65.07
0.0
38.26
19.49
73.93
100
90.54
95.83
76.70
83.51
0.95
79.78
89.30
74.33
81.92
0.1
86.60
93.50
67.25
71.69
150
90.24
95.92
77.07
84.00
0.99
89.43
95. 54
76.97
84,05
0.5
89.89
95.28
78.04
84.85
250
89.87
95.69
77.83
84.33
0.999
86.27
93.69
38.89
39.37
2.0
88.74
95.73
77.62
84.72
The adjusted MI score' normalizes the range between 0 and I, and subtracts the baseline from random chance:
- V)I
AMI(U,V) =
(53)
2 (H + B[MI(U, V)
where H-) denotes the entropy function, and [UM V)] is the expected mutual information by chance Finally, for each model, we sweep the threshold a to get threshold invariant score:
AMImax max AMl(y, (())).
(54)
For supervised evaluation, we used the AP metric. The AP metric is also threshold invariant, and it takes both output à and ý into account. First sorts all the prediction based on its unknown score in ascending order. Then it checks whether makes the correct prediction. For the N top ranked instances in the sorted list, computes: precision @ and recall @ among the known instances.
AP:
precision @ N Σn 10 = Vnl. recall@ N k Σ. [0n- = yn).
where K is the true number of known instances among the top N instances. Finally, AP is computed as the area under the curve of (y=precision @N, x=recall @N.. For more details, see Appendix A.3 of Ren al. (2021).
D ADDITIONAL EXPERIMENTAL RESULTS
D.1 COMPARISON TO RECONSTRUCTION-B..E METHODS
We additionally provide Tab. show comparison with CURL (Rao al., 2019) in the iid setting. We used the same MLP architecture and applied it on the Omniglot dataset using the same data split. Reconstruction-ben based methods lag far behind self supervied learning methods. Our method on par with SimCLR and SwAV.
D.2 ADDITIONAL STUDIES HYPERPARAMETERS
In Table 8, we investigate the effect of the size of the prototype memory, and whether the model would benefit from a larger memory. It turns out that as long as the size of the memory is larger than the length of the input sequence for each gradient update step, it can learn good representations and the size is not major determining factor.
In Table 9, we examine whether the memory forgetting parameter is important to the model. We found that the forgetting rate between 0.99 and 0.995 is the best. 0.999 (closer to no forgetting) results in worse performance.
In Table 10, we investigated the effect of various values for the new cluster loss coefficient. The optimal value is between 0.5 and 1.0.
hhttps://ccikit--eeaa hhttps://en.wiiiipddii httppp/paa...g///////a/aa/aeeeee
e/modut es es/generated/sk /at///kkeaarrrra ie
_informationn
19

---

Under review as a conference paper at ICLR 2022
Table 11: Effect of threshold
Table 12: Effect of F
RoamingOmnighh
RoamingRooms AMI
Roaming
RoamingRooms
AMI
AP
f/T
AMI
AP
AMI
AP
0.3
82.75
90.57
52.60
58.71
0.05
89.23
95.01
77.44
84.38
0.4
81.59
90.94
59.69
66.11
0.10
89.71
95.21
77.89
84.99
0.5
89.65
95.22
77.96
84.34
0.20
89.78
95.31
77.82
84.57
0.6
87.01
93.87
64.65
69.49
0.50
89.40
95.13
76.81
83,90
0.7
86.08
92.94
66.60
73.54
1.00
89.62
95.16
0.00
19.91
Table 13: Effect of Aeat
Table 14: Effect of mean μ of the Beta prior
RoomingOnmniglot
RoamingRooms
Omniglot AP
RoamingRooms
Aent
AMI
AP
AMI
AP
AMI
AMI AP
0.00
82,45
90.66
76,64
84.11
0.3
84.14
93.19
68.75
72.58
0.25
87.31
93.85
76.61
83.16
0.4
86.59
93.10
69.19
73.86
0.50
87.98
94.21
75.46
81.78
0.5
89.89
95.24
77.61
84.64
0.75
88.77
94.74
74.76
79.91
85.93
93.81
64.21
73.23
1.00
89.70
95.14
75.32
80.29
0.7
26.22
92.08
48.58
64.28
In Table 11, the threshold parameter is found to be the best at 0.5. However, this could be correlated with how frequently the frames are sampled.
In Table 12, we found that the soft distillation loss is beneficial and slightly improves the performance compared to hard distillation.
In Table 13, the entropy loss introduced leads significant improvement on the Omniglot dataset but not on the RoamingRooms dataset.
The Beta mean distribution, and is the mean. We fix a = 4ya and - a. In Table 14, we found that the mean of the Beta prior is the best at 0.5. It has more impact the RoamingRooms dataset, and has less impact on the RoamingOmniglo dataset. This parameter could influenced by the total number of clusters in each sequence.
computed as the following: Suppose and are the parameters of the Beta
E ADDITIONAL VISUALIZATION RESULTS
We visualize the clustering mechanism and the learned image embeddings RoamingRooms in Fig. 8 and 9. The results suggest that our model can handle a certain level of view point changes by grouping different view points of the same object into a single cluster. It also shows that our model is instance-eensitvee for example, the headboard, pillows, and the blanket are successfully separated.
In Fig. 10 and 11, we visualize the learned categories in RoamingOmniglo using t-SNE (Van der Maaten & Hinton, 2008). Different colors represent different ground-truth -ruth classes. Our method is able learn meaningful embeddings and roughly group items of similar semantic meanings together.
20

---

Under review as a conference paper at ICLR 2022
Figure 8: Embeddings and clustering outputs of an example episode (1). Embeddings are extracted from the trained CNN and projected to 2D space using t-SNE (Van der Maaten & Hinton, 2008). The main object in each image highlighted in a red mask. The nearest example to each cluster centroid enlarged. Image border colors indicate the cluster assignment.
21

---

Under review as a conference paper at ICLR 2022
Figure 9: Embeddings and clustering outputs of another example episode (2).
22

---

Under review as a conference paper at ICLR 2022
2
GUT
EAST
1
EE
Figure 10: Embedding visualization of an unsupervised training episode of KoamingOmnighe Different colors denote the ground-trute -ruth class IDs.
23

---

Under review as a conference paper at ICLR 2022
99
Figure 11: Embedding visualization of an test episode of Omniglot.
24


Reviews:
[{"review_id": "qhflwo46Euf", "reviewer": "Reviewer_LjvY", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "Why is the standard deviation $\\sigma$ constant and not learned per component (cluster) of the mixture? Since $\\sigma$ is a scalar (isotropic), this wouldn't add much complexity to the model and it would help in deciding when to add or remove prototypes, potentially getting rid of (or learning) hyperparameters $u_0$ and $\\mu$.\n\nThe uniform prior distribution for a new cluster is an improper distribution over continuous space. In fact, the overall distribution is a Gaussian-uniform mixture (GUM) (Lathuilière et al. 2018, \"DeepGUM: Learning Deep Robust Regression with a Gaussian-Uniform Mixture Model\"). In the original GUM model, the prior probability of an inlier is learned like all mixing coefficients (weights), whereas here $z_0$ is a fixed hyperparameter and $\\alpha$ is yet another unnecessary threshold hyperparameter (the new cluster probability could be simply compared to existing cluster probabilities).\n\nThe RHS of (2) is incorrect. Softmax is mapping a vector to a vector, while here only a scalar is shown (the numerator of the LHS). One should map the whole vector through softmax, then take the $k$-th element.\n\nEq. (5) is unclear unless one reads the Appendices. Overall, section 3.1 is written as a summary of sections A.1 and A.2, which is hard to follow. For example, $y_{t,k}$ and $u_{t,k}$ in (9,10) are not defined. One should provide a clear motivation for the model and all choices (which is missing), definitions all quantities (some of which are missing) and clear pointers to Appendices for all missing steps in the derivation. The formulation is overall very similar to (Ren et al., 2021), so the derivation is not new (e.g. compare (3) of Ren et al. with (5) of this work.) The connection is missing, both in section 3.1 and in A.1, A.2.\n\nWhat does inverse variance have to do with the count of examples per cluster? Why estimate variance since variance is assumed constant? This remains unclear even after reading section A.2. Shouldn't symbol $\\sigma_{t,d}$ (e.g. in (7,8) be $\\sigma_{t,k}$?\n\nWhat is really missing is citing and discussing Bottou and Bengio 1995, \"Convergence Properties of the K-Means Algorithms,\" which defines an online $k$-means algorithm by means of gradient descent on an error function. One would expect a generalization to a Gaussian mixture basically by preserving the same formulation and adding mixing coefficients and variances per component (cluster), but this is not done. Bottou and Bengio have a similar definition of count of examples per cluster (Eq. (7)), but which has nothing to do with variance.\n\nWhy use decay (hyperparameter $\\rho$)? Well, there is the argument of nonstationary environments but how about forgetting? The entire problem of incremental and online learning is to learn without forgetting. Here, not only nothing is done to avoid forgetting; decay is actually explicit forgetting. Is this justified by the unsupervised setting? Or is there another reason?\n\n\"Popping out\" the prototype with the least weight is too simplistic, because it does not consider interaction or redundancy among clusters. An little populated, isolated cluster may be more important than a highly populated cluster with many neighboring/overlapping clusters. Avrithis and Kalantidis 2012, \"Approximate Gaussian Mixtures for Large Scale Vocabularies\" develop an offline but dynamic (in terms of components) EM algorithm that removes mixture components based on pairwise interaction. Tao et al. 2020, \"Few-Shot Class-Incremental Learning\" also uses a graph over prototypes and has a similar online update of prototypes (Eq. (3)).\n\nIn Eq. (13), it is not clear if target labels are soft, as is standard in distillation. They should be, since there is a temperature parameter, but (13) should have a sum over $k$ that is missing. Similarly, (14) should have a sum over $k$ if this expression is meant to be an entropy. Eq. (15) is too abstract and unclear.\n\nIn computing AMI, is the number of classes known? What is $T$? Sweeping over hyperparameter $\\alpha$ is not realistic, especially if $\\alpha$ is unnecessary (see above).\n\n\"Since none of [SimCLR, SwaV] are designed to output classes with a few examples, we use our online clustering procedure to readout from these learned representations:\" This is unclear. As a result, the protocol of comparisons to offline methods it is unclear. A formal description is in order.\n\nThe entire argument against methods assuming iid batch sampling is reliance on iid for contrastive learning (SimCLR) or prototypes (SwaV). How about self-supervised representation learning without prototypes (e.g. BYOL: Grill et al., 2020) and without negatives (e.g. SimSiam: Chen & He, 2021)? Whouldn't such simple alternatives be much easier to adapt to online? Wouldn't those online versions be more suitable as baselines to compare with?\n\nThe following works should be discussed. Although I believe they are not directly comparable, one may still consider additional baselines, e.g. self-supervised offline pretraining followed by online learning (supervised or not):\n1. Zhu et al. 2021, \"Prototype Augmentation and Self-Supervision for Incremental Learning\"\n2. Gallardo et al. 2021, \"Self-Supervised Training Enhances Online Continual Learning\"\n3. Zhang et al. 2021, \"Self-Supervised Learning Aided Class-Incremental Lifelong Learning\"\n4. Cha et al. 2021, \"Co$^2$L: Contrastive Continual Learning\"\n\nThe list of hyperparameters (e.g. Tables 4-6) is daunting. One should at least separate the method-specific hyperparameters (e.g. $K, \\rho, \\alpha$) from standard hyperparameters (like backbone and learning rate). From Tables 8-14, there are at least 7 hyperparameters in the ablation. What are the default values of remaining hyperparameters when studying each one? Is this search optimal, what is the cost, and to what extent could same values be used across datasets? Merging Tables 4-6 into one would help compare.\n\nThe networks used are too small, more inline with few-shot learning and unlike most work on either self=supervised representation learning or continual learning.\n", "summary_of_the_paper": "This work studies an online version of self-supervised representation learning. It uses Gaussian mixture  of constant isotropic variance as a prototype memory as well as a uniform distribution to handle new unknown classes. The overall distribution evolves using an online EM algorithm that supports adding and removing prototypes. Using this memory, representation learning follows standard unsupervised losses, primalrily a distillation loss over predicted prototype assignment probabilities.", "summary_of_the_review": "Online self-supervised learning is a very interesting and realistic setting. The online EM algorithm that maintains a set of prototypes makes a lot of sense.\n\nThere are a number of papers that are very related, most notably Bottou and Bengio 1995 (online $k$-means) and Lathuilière et al. 2018 (Gaussian-uniform mixture). Not only one would expect them to be cited and discussed, but rather the method formulation should be based on the formulation of this prior work. This would improve positioning of this work, make the formulation more elegant/better motivated and dispense the need for certain hyperparameters. The related work section needs improvement in general.\n\nWriting is good in general, but the formulation in unclear at several points, relying on Appendices. Pointers to prior work are also missing in the formulation, primarily (Ren et al., 2021).\n\nThe protocol of comparisons to non-online methods is unclear. The choice of competitors is not well justified: there are simpler methods that are easier to adapt to online. There may be more baselines to consider e.g. on pretraining. There are too many hyperparameters. The networks used are too small.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "NBiEi25P7nH", "reviewer": "Reviewer_hYzM", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "Part of the successes of deep learning comes from the well collected dataset, e.g., ImageNet10K. To study some area, someone should first to collect enough high quality data. However, this is different from the cognitive process of human being. This paper questions the standard machine learning formulation of drawing i.i.d. samples and claims that the real world scenario should be nonstationary. This is very interesting and encourging.\n\nHowever, my main concern is that should we train our models in an online stream scenario just because the real world scenario nonstationary? You see, the tranditional learning formulation has its assumption that all samples are drawn in an i.i.d. way. But it doesn't violate the eventual performance. It works quite well.\n\nI could understand that the author tries to mimic the learning process of human kind, just like lifelong learning. But the authors are encouraged to concentrate the necessity of this behaviour.\n\nBesides, the language, the equations, are all above the thresold of the acceptance.", "summary_of_the_paper": "This paper claims that in real world the data distribution is nonstationary, which is different from the current standard machine learning formulation. To solve this problem, the authors design an online unsupervised learning algorithm with Gaussian mixture model and EM algorithm. The experiment shows that the method can learn the online stream of visual input data.", "summary_of_the_review": "In this paper, the author assumes a new scenario of nonstationary distribution. To solve the unsupervised and online setting, they design a novel online unsupervised prototypical networks (OUPN). By introducting the Gaussian mixture model and EM, the method could add or drop the cluster in an online way.\n\nThe idea is interesting and encouring, but the necessity is not well claimed. The difference between this method and life-long learning / incremental learning is encouraged. Also, the hyper-parameter of maximum number of K clusters should pay much more attention.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "6Cd3CyJiTBt", "reviewer": "Reviewer_cvrN", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "The proposed approach is novel to the best of my knowledge. It also seems sound. The experimental evaluation on the task of unsupervised, instance-based clustering in the online, non-iid setting clearly demonstrates the superiority of the proposed method compared to the baselines. However, I have two main concerns with this paper.\n\nFirstly, although it is well written, the presentation is quite dense and many details have to be inferred from the context. I understand that it's hard to pack so much content into 9 pages, but I would argue that the authors could make significantly more effort to better explain the results. The content could be densified by putting some equations in the text, for example, and the whole Omniglot evaluation can be moved to the supplementary material, since it's not that important for the story.\n\nIn fact, the main issue with the presentation is that no ablation analysis is provided. There are several tables in the supplementary material which compare the values of the many hyper parameters in the method, but the accompanying text literally just takes 9 lines. This is not sufficient to understand what actually makes this relatively complex method work better than the baselines. After all, the goal of a research  paper in not to report strong numbers on a benchmark, but to provided some knowledge about the problem being studied. The ablation analysis needs to be moved to the main text and the discussion needs to be expanded to 1-2 pages with clear conclusions about the importance of various components of the approach.\n\nSecondly, and more importantly, the claims in the introduction are not supported by the experimental results. The proposed approach learns a representation that clusters different views of the same instance in an online manner (character classes are also more akin to instances than semantic categories), and this is the task on which it is evaluated (aside from Table 3). But is this an actual task that many people care about? I would argue that it's not, and the authors agree with me, since all the claims are made in terms of semantic classification/categorization. But instance ids are not categories. In fact, its natural that a method trained with a contrastive learning objective will cluster different views of the same object together, but does it learn a semantic representation? Or is the learned representation at least useful for downstream semantic tasks? The only evidence for that provided in the paper are in Table 3 with experiments on an online version of ImageNet, but the explanation of these results is not sufficient and no qualitative examples of discovered clusters are provided. To address these issues, the authors should either demonstrate that their method is capable of discovering categories, or show that the learned representation is superior to the baselines on downstream semantic tasks (supervised image classification, object detection, semantic segmentation) or remove any claims on learning category information, and focus on the instance classification story, providing some justification for its importance. \n\nFinally, it would be interesting to see which batch size is sufficient for the baselines to reach the performance of the proposed approach both in iid and non-iid setting, extrapolating the curves in Figures 3 and 6.", "summary_of_the_paper": "The authors propose a method for unsupervised learning of instance-based clustering which is more robust to data imbalance and non-iid distributions than existing approaches, such as SwAW. In particular, they propose an Expectation Maximization algorithm that operates in temporal episodes (supposed to correspond to an agent moving through an environment).  At every step an observation (image with an overplayed instance segmentation mask) is first encoded with a CNN and the resulting vector is assigned to one of the existing clusters based on the distance in the feature space, or a new cluster is created (E-step). This is formulated in a probabilistic framework. The cluster prototypes are then updated accordingly (M-step). The loss, computed after a sequence of such steps, consists of a standard contrastive loss (encourages assigning similar images to the same clusters) + entropy (encouraging confident assignments) + a term encouraging the creation of new clusters. \n\nThe method is mainly evaluated on RoamingRooms - a dataset with an agent moving through indoor environments with instance labels assigned to objects. The task is then to cluster different view points of the same object together. The main challenge is that the distribution of examples is non-iid, since in every episode mostly the same objects are seen. Additional evaluation on online variants of Omniglot and ImageNet is also provided.\n\nWhen compared to offline and online contrastive learning algorithms the proposed approach demonstrates stronger performance especially with low batch size and non-iid distribution of examples.", "summary_of_the_review": "The proposed approach is original and clearly shows strong results for the task of unsupervised, online, non-iid instance classification. However, there are major issues with the presentation, and the unsupervised categorization claims made in the introduction are not supported by the experimental results. If the authors can address both concerns in the rebuttal, I'd be happy to recommend an acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "350tDj4IWI", "reviewer": "Reviewer_bgm4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "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": "First of all, I am very enthusiastic about the general topic that is being addressed: unsupervised (or self-supervised) learning in more realistic environments--specifically those in which we may see a large number of examples of a small set of objects, and perhaps a few examples of some other classes. Thus, the topic is highly relevant and important at this time. \n\nDespite trying my best to understand the specifics of the experimental settings, I found it very difficult to tell exactly what was going on. I found several aspects of the paper difficult to follow. One major issue was trying to understand the exact setting of the RoamingRooms data set task. \n\nReferring to the experimental results from figure 4, here are a few comments:\n\t\n- Only when I finally looked at the title of the figure in figure 4 was I able to discern some of the parameters of the experiments on the RoamingRoom data set such as the 5000 images that retrieval was done across.\n\t\n- I could not ascertain whether the bounding box of the object was given at test time, or only at training time. If it is provided at test time, this makes the task much much easier. Either way, it is a critical detail, and should be described clearly and unambiguously.\n\n- How is the query image related to the “5000 images” which I assume you are\nsearching? How close can they be in time? Could it actually be at the exact same time?  If it is just a frame or two away from the current frame, we would expect the similarity of the same object across these close views in time to be very very similar.  If this is the case, then I would expect to see other types of baselines that leverage this kind of information, such as simple nearest neighbor methods. In other words, if I give a query, just return\nthe top-9 nearest neighbors using some pre-trained representation, centered on \nthe provided bounding box.  If such an approach is not reasonable, it is hard to\ntell from the current text. If it is reasonable, then it would be useful to compare \nagainst it to get a sense of what exactly is being learned. \n\n- I couldn't even tell if SimCLR was trained on the same data, or trained on some other data. If it is trained on the current data, could you give details about how this training is done? It is possible that if I had read all of the referenced papers I would understand these details, but a reviewer should not have to wade back through papers to understand these details. \n\n- \"we use our online clustering procedure to readout from these learned representations\". Why not just do nearest neighbor retrieval using the learned representations, and see how that works?\n\nSimCLR and other such “generic” representation-learning approaches are solving\na significantly different problem: they are typically trying to learn representations which\nhave a high degree of generalizability so that they can be the backbone for a system\ntrained to recognize general categories, with very high variability. Here, since the goal\nis to learn to recognize the exact same object, it makes more sense to take a prototype\nstyle approach, since this is very similar to say, k-nearest neighbors. \n\nWhat I’m trying to say is perhaps that SimCLR and other such methods are not the\nright baselines. A more reasonable baseline is one that just looks at distances to the\ntraining sets. \n\n\nThe authors may feel that I have completely misunderstood the paper. That may be true, but it is not for lack of trying. I have worked with many of the cited self-supervised methods, and have published in self-supervised learning as well. I found a general lack of detail about the exact settings made it very hard to evaluate what was going on.\n\n\nOther issues:\n\n1) “we make two changes on the model inference procedure defined above.”\nWhy did the authors describe the changes to the model in the Experiments section?\nIsn’t the right place to discuss this in Section 3, the section where the model and\nmethods are described? This makes it sound like a last second change….Or, perhaps\nlike it was a difficult-to-justify method that would be difficult to explain. What is the\nmotivation for putting it in experiments?\n\n2) adjusted MI. While I follow the argument for using a max_alpha in the adjusted mutual\ninformation, I’m not sure I agree with it.  For one, this is not something one can do in practice; therefore it gives an over-optimistic view of the output. Second, it is not clear if this procedure favors the current algorithm. By knowing that you are going to optimize over the number of clusters, one can adjust one’s algorithm to take advantage of this. I do not claim to understand whether this procedure favors your algorithm, but in general, such a procedure is not “neutral” to two different algorithms.\n\n3) The function g() is introduced with no definition.\n\n4) How is K the number of classes chosen?\n\n", "summary_of_the_paper": "This paper addresses the problem of doing unsupervised learning of visual representations, including clustering these representations to infer the existence of new categories. The paper focuses on more \"un-curated\" settings in which the data comes from samples of an environment that a real agent is passing through. This gives object distributions that are very different from typical, curated data sets, like ImageNet without labels. The authors compare their method with other popular self-supervised learning techniques like SimCLR.", "summary_of_the_review": "Despite being enthusiastic about this general area, I found it too difficult to follow the experiments. Not enough detail was given about:\n- data sets used and how they were sampled to produce \"training\" and test data\n- exactly what the experimental setting was. What problem, exactly, are these systems trying to solve? I think, but am not sure, that given many instances of objects with unique ids at \"training time\", they are simply trying to retrieve objects with the same ID as a query image at test time. However, not enough details are given about the details of this problem.\n- Given the nature of the problem, it appears as though a variety of nearest-neighbor style baselines would be appropriate.\n\n\n\nIn my assessment about \"confidence\", I have said that I am fairly confident of my review. Ironically, I didn't understand the paper well, but this is the problem with the paper. It should be easier to understand what was done. Thus, I am confident in my assessment that the paper should have been more understandable. In particular, I am not someone coming from far outside the area; thus, the paper should have laid out the details more clearly so that someone with my background would understand it.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper tackles a small-batch online unsupervised learning problem, specifically proposing an online unsupervised prototypical network architecture that leverages an online mixture-based clustering algorithm and corresponding EM algorithm. Special features are added to deal specifically with the non-stationary distributions that are induced. Results are shown on more realistic streams of data, namely from the RoamingRooms dataset, and compared to existing self-supervised learning algorithms including ones based on clustering principles e.g. SWaV. 

Overall, the reviewers were positive about the problem setting and method, but had some concerns about hyper-parameters (hYzM, cvrN, LjvY) and motivation for the specific setting where the method excels compared to other methods not designed for such a setting (hYzM, cvrN), i.e. small-batch setting, where it is not clear where the line should be drawn in terms of batch size and memory requirements with respect to performance differences between the proposed approach and existing self-supervised methods. Importantly, all reviewers had significant confusions about all aspects of the work ranging from low-level details of the proposed method to the empirical setting and evaluation (including for competing methods). After a long discussion, the authors provided a large amount of details about their work, which the reviewers and AC highly appreciate. However, in the end incorporating all of the feedback requires a major revision of the entire paper. Even the reviewers that were more on the positive side (cvrN and LjvY) mentioned it would be extremely beneficial for this paper to be significantly revised and go through another review. Since so many aspects were confusing, it is not clear to the AC that the underlying method, technical contributions, and other aspects of the works had a sufficient chance to be evaluated fairly, given that much of the review period was spent on clearing up such confusion. 

In summary, while the paper is definitely promising and tackles an important area for the community, it requires a major revision and should go through the review process when it is more clearly presented. As a result, I recommend rejection at this point, since it is not ready for publication in its current form.
Decision: Reject