Year: 2021

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.

heading: 1 INTRODUCTION
text: 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 occur 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, a visitor may be infrequent, but when they are around, they’re encountered frequently. And finally, the distribution can be highly unbalanced: an 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 a 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 to 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 work is to produce object-category predictions throughout training and evaluation, and to allow these 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-based objectives (Chen et al., 2020a; He et al., 2020) typically assume that each instance in the mini-batch forms its own instance class, throwing 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 a naturalistic online streaming setting. The performance of
methods will suffer as a consequence. Contrastive approaches could eventually fail if examples of the same class are pushed apart; 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 a 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 representation 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 on a recently proposed naturalistic learning dataset, RoamingRooms (Ren et al., 2021), which uses imagery collected from a 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 state-of-the-art 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 to an imbalanced distribution of classes. For a version of ImageNet with non-iid structure, RoamingImageNet, 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 a few similar instances together in the learned embedding space.

heading: 2 RELATED WORK
text: Self-supervised learning. Self-supervised learning methods discover rich and informative visual representations without class labels. Instance-based approaches aim to learn invariant representations of each image under different transformations (van den Oord et al., 2018; Misra & van der Maaten, 2020; Tian et al., 2020; He et al., 2020; Chen et al., 2020a;b; Grill et al., 2020; Chen & He, 2021). They typically work well with iid data and large batch sizes, which contrasts with realistic learning scenarios. Our method is also related to clustering-based 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 et 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 as an explicit constraint. In contrast, our online clustering procedure is more flexible: it can create new clusters on-the-fly with only a 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 an 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 we operate on example-level rather than task-level. Streaming learning (Hayes et al., 2020; 2019) aims to perform representation learning online. Most work here except Rao et al. (2019) assumes a fully supervised
Net
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 to 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 to infer latent variables with temporal structure, but they use an input reconstruction criterion.
Online mixture models. Our clustering module is related to the literature on online mixture models, e.g., Bottou & Bengio (1995); Carpenter & Grossberg (1987); Anderson (1991); 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 self-supervised 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 equal number of training and test examples from a 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 et 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, our model learns both representations and categories in an end-to-end fashion.

heading: 3 ONLINE UNSUPERVISED PROTOTYPICAL NETWORKS
text: In this section, we introduce our proposed model, online unsupervised prototypical networks (OUPN). We study the online categorization setting, where the model receives an input xt at every time step t, and predicts both a categorical variable ŷt to indicate the object class and also a binary variable ût to indicate whether this is a known (u = 0) or new (u = 1) class. OUPN uses a network h to encode the input to obtain embedding zt = h(xt; θ), where θ represents the learnable parameters of the encoder network. z is then processed by a prototype memory which predicts (ŷt, ût).

heading: 3.1 PROTOTYPE MEMORY
text: We formulate our prototype memory as a probabilistic mixture model, where each cluster corresponds to a Gaussian distribution f(z;p, σ2), with mean p, a constant isotropic variance σ2 shared across all clusters, and mixture weights w: p(z;P ) = ∑ k wkf(z;pk, σ
2). Throughout a 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 u is constant (u0 ≡ Pr(u = 1)), and the prior for a new cluster is uniform over the entire space (z0 ≡ Pr(z|u = 1)) (Lathuilière et al., 2018). In the following, we formulate our prototype memory as an approximation to an online EM algorithm. The full derivation is included in the supplementary materials.

heading: 3.1.1 E-STEP
text: Upon seeing the current input zt, the online clustering procedure needs to predict the cluster assignment or initiate a new cluster in the E-step.
Inferring cluster assignments. The categorical variable ŷ infers the cluster assignment of the current input example with regard to the existing clusters.
ŷt,k = Pr(yt = k|zt, u = 0) = Pr(zt|yt = k, u = 0) Pr(yt = k)
Pr(zt, u = 0) (1)
= wkf(zt;pt,k, σ 2)∑ k′ wk′f(zt;pt,k′ , σ 2) = softmax
( logwk − 1
τ d(zt,pt,k)
) , (2)
where wk is the mixing coefficient of cluster k, d(·, ·) is the distance function, and τ is an independent learnable temperature parameter that is related to the cluster variance.
Inference on unknown classes. The binary variable û estimates the probability that the current input belongs to a new cluster:
ût = Pr(ut = 1|zt) = Pr(zt|ut = 1) Pr(ut = 1) Pr(zt|ut = 1) Pr(ut = 1) + ∑ k Pr(zt|yt = k, u = 0) Pr(u = 0) (3)
= z0u0 z0u0 + ∑ k wkf(zt;pt,k, σ 2)(1− u0) ≥ z0u0 z0u0 + maxk f(zt;pt,k, σ2)(1− u0)
(4)
= sigmoid((min k
1 τ d(zt,pt,k)− β)/γ), (5)
where β and γ are separate learnable parameters related to z0 and u0, allowing us to predict different confidence levels for unknown and known classes.

heading: 3.1.2 M-STEP
text: Here we infer the posterior distribution of the prototypes Pr(pt,k|z1:t). We formulate an efficient recursive online update, similar to Kalman filtering, incorporating the evidence of the current input zt and avoiding re-clustering the entire input history. We define p̂t,k as the posterior estimate of the mean of the k-th cluster at time step t, and ĉt,k is the estimate of the inverse variance.
Updating prototypes. Suppose that in the E-step we have determined that yt = k. Then the posterior distribution of the k-th cluster after observing zt is:
Pr(pt,k|z1:t, yt = k) ∝ Pr(zt|pt,k, yt = k) Pr(pt,k|z1:t−1) (6) ≈ f(zt;pt,k, σ2) ∫ p′ f(pt,k;p ′, σ2t,d)f(p ′; p̂t−1,k, σ̂ 2 t−1,k) (7)
= f(zt;pt,k, σ 2)f(pt,k; p̂t−1,k, σ 2 t,d + σ̂ 2 t−1,k). (8)
The transition probability distribution Pr(pt,k|pt−1,k) is a zero-mean Gaussian with variance σ̂2t,d = (1/ρ− 1)σ̂2t−1,k, where ρ ∈ (0, 1] is some constant that we define to be the memory decay coefficient. In fact, ĉ can be viewed as a count variable for the number of elements in each estimated cluster, subject to the decay factor ρ over time, if we further assume that σ2 = 1, ĉt,k ≡ 1/σ̂2t,k, and ĉt−1,k ≡ 1/σ̂2t−1,k. The memory update equation can be formulated as follows:
ĉt,k = E yt [ĉt,k|yt ] = ρĉt−1,k + ŷt,k(1− ût,k), (9)
p̂t,k = E yt [p̂t,k|yt ] = zt ŷt,k(1− ût,k) ρĉt−1,k + 1 + p̂t−1,k
( 1− ŷt,k(1− ût,k)
ρĉt−1,k + 1
) . (10)
ŵt,k = E yt [ŵt,k|yt ] = ĉt,k/ ∑ l ĉt,l. (11)
Adding and removing prototypes. Our prototype memory is a collection of tuples (p̂k, ĉk). We convert the probability of whether an observation belongs to a new cluster into a decision: if ût exceeds a threshold α, we create a new cluster in our prototype memory. Due to the decay factor ρ, our ĉ estimate of a 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 is full and we try to add another cluster at time t, we simply pop out the least relevant prototype pk′ , where k′ = arg min(ŵk): Pt = Pt−1 \ {(p̂k′ , ĉk′)} ∪ {(zt, 1)}.

heading: 3.2 REPRESENTATION LEARNING
text: A primary goal of our learning algorithm is to 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 = Lself + λentLent + λnewLnew. This loss function drives the learning of the main network parameters θ, as well as other learnable control parameters β, γ, and τ . We explain each term in detail below.
1. Self-supervised loss: Inspired by recent self-supervised representation learning approaches, we apply augmentations on xt, and encourage the clustering assignments to match across different views. Self-supervision follows three steps: First, the model makes a prediction on the augmented view, and obtains ŷ and û (E-step). Secondly, it updates the prototype memory according to the prediction (M-step). To create a learning target, we query the original view again, and obtain ỹ to supervise the cluster assignment of the augmented view, ŷ′, as in distillation (Hinton et al., 2015). Lself = 1T ∑ t−ỹt log ŷ′t. Note that both ỹt and ŷ′t are produced after the M-step so we
can exclude the “unknown” class in the representation learning objective. We here introduce a separate temperature parameter τ̃ to control the entropy of the mixture assignment ỹt. 2. Entropy loss: In order to encourage more confident predictions we introduce a loss function Lent that controls the entropy of the original prediction ŷ, produced in the initial E-step: Lent = 1 T ∑ t−ŷt log ŷt. 3. New cluster loss: Lastly, our learning formulation also includes a loss for initiating new clusters Lnew. We define it to be a Beta prior on the expected û, and we introduce a hyperparameter µ to control the expected number of clusters: Lnew = − log Pr(E[û]). 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 1 in the Appendix.
Relation to Online ProtoNet. The formulation of our probabilistic prototype memory is 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 to 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 is also entirely unsupervised, whereas Ren et al. (2021) relies on a supervised loss.

heading: 4 EXPERIMENTS
text: In this section, we evaluate our proposed learning algorithm on a set of visual learning tasks and evaluate the quality of the output categories. Different from prior work on visual representation learning, we focus on 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 inference 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 is found to be more stable to train. Second, when we perform cluster inference, we treat the mixing coefficients wk as constant and uniform as otherwise we find that the representations may collapse into a single large cluster.
Online clustering evaluation. During evaluation we present our model a 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 ŷt = g(x1:t). In supervised readout, the model has access to all labels up to time step t− 1, and needs to predict the label for the t-th image, i.e. ŷt = g(x1:t, y1:t−1). We used the following metrics to evaluate the quality of the grouping of test sequences:
40
50
60
70
50 20 0
AM I
Sequence Length
• Adjusted mutual information (AMI): In the unsupervised setting, we use the mutual information metric to evaluate the similarity between our prediction {ŷ1, . . . , ŷT } the groundtruth class ID {y1, . . . , yT }. Since the online greedy clustering method admits a threshold parameter α to control the number of output clusters, therefore for each model we sweep the value of α to maximize the AMI score, to make the score threshold-invariant: AMImax = maxα AMI(y, ŷ(α)). The 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. • Average precision (AP): In the supervised setting, we followed the evaluation procedure in Ren et al. (2021) and used average precision, which combines both accuracy for predicting known classes as well as unknown ones.
Offline readout evaluation. A popular protocol to evaluate self-supervised representation learning is to use a classifier trained offline on 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 use a k-nearest-neighbor classifier to readout the learned
representations. The hyperparameter k is chosen between 1 and 39 for each model based on the validation set performance (empirically, larger k is preferred).
• Linear readout: Another popular protocol is to train a linear classifier on top of the learned representations to a given set of 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-art selfsupervised visual representation learning methods. For fair comparison on online representation learning, ll of the following methods are trained on the same dataset as our model, instead of using their pretrained checkpoints from ImageNet. • SimCLR (Chen et al., 2020a) is a contrastive learning method with an instance-based objective
that tries to classify an 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 et al., 2009). • SwAV (Caron et al., 2020) is a contrastive learning method with a clustering-based objective. It has a stronger performance than SimCLR on ImageNet. The clustering is achieved through SinkhornKnopp which assumes balanced assignment, and prototypes are learned by gradient descent. • SwAV+Queue is a SwAV variant with an additional example queue. This setup is proposed in (Caron et al., 2020) to deal with small training batches. A feature queue that accumulates
Recall: 0.18
instances across batches allows the clustering process to access more data points. The queue size is set to 2000. • SimSiam (Chen & He, 2021) is a 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 a 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 α, it will create a 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.

heading: 4.1 INDOOR HOME ENVIRONMENTS
text: We first evaluate the algorithm using the RoamingRooms 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. Each 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 iteration consists of a sequence of images from one of the homes. At test time, for the instance classification task, we 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 use varying batch sizes (50, 100, 200, and 400). For online (non-IID) settings, the notion of batch size can be understood as “sequence length”. Learning rate is scaled based on batch size /256× 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,000 / batch size. For our proposed model, we used the batch size of 50 and trained for a 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 on 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.
Table 2: Results on RoamingOmniglot
Table 3: Results on RoamingImageNet
40
50
60
70
50 20 0
AM I
Sequence Length
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 our expectation. Nevertheless, our method using a batch size of 50 is still able to outperform SimCLR and SwAV using a batch size of 400, which takes 8× 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 is a sequential module. Moreover, keeping the batch size smaller allows quicker online adaptation and less memory consumption.
Comparison to iid modes of SimCLR, 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-supervised 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 to SimCLR is when SimCLR is trained with large batches under IID setting on semantic classification readout. This is reasonable since semantic classification and IID large batch training is 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 learned 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.

heading: 4.2 HANDWRITTEN CHARACTERS
text: We also evaluated our method on a different task: recognizing handwritten characters from Omniglot (Lake et al., 2015). In this experiment, images are not organized in a video-like sequence, and
models have to reason more about conceptual similarity between images in order to learn grouping. Furthermore, since this is a more controllable setup, we can test our hypothesis concerning sensitivity to class imbalance by performing manipulations on the episode distribution.
Our episodes are sampled from the RoamingOmniglot dataset (Ren et al., 2021). An episode involves several different contexts, each consisting of a set of classes, and in each context, classes are sampled from a Chinese restaurant process. We use 150-frame episodes with 5 contexts.
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, at 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, we randomly replace Omniglot images with MNIST digit 1 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 are shown in Fig. 7, and our method is shown to be more robust under imbalanced distribution than SimCLR and SwAV. Compared to clustering-based 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.
Visualization of learned categories. We visualize the learned categories in RoamingOmniglot using t-SNE (Van der Maaten & Hinton, 2008), and the results are shown in the Appendix E.

heading: 4.3 IMAGENET IMAGES
text: Lastly, we evaluate on episodes composed of ImageNet images, and using the RoamingImageNet 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 on 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 a test whether a 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.

heading: 5 CONCLUSION
text: Our goal is to 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 is more flexible and supports learning of new categories with very few examples. At the same time, we leverage self-supervised learning to acquire semantically meaningful representations. Our method is evaluated in 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.

heading: A FULL ALGORITHM.
text: Let Θ = {θ, β, γ, τ} denote the union of the learnable parameters. Algorithm 1 outlines our proposed learning algorithm. The full list of hyperparameters are included in Appendix C.
Algorithm 1 Online Unsupervised Prototypical Learning repeat Lself ← 0, pnew ← 0. for t← 1 . . . T do
Observe new input xt. Encode input, zt ← h(xt; θ). Compare to existing prototypes: [ût, ŷt]← E-step(zt, P ;β, γ, τ). if û0t < α then
Assign zt to existing prototypes: P ← M-step(zt, P, ût, ŷt). else
Recycle the least used prototype if P is full. Create a new prototype P ← P ∪ {(zt, 1)}.
end if Compute pseudo-labels: [_, ỹt]← E-step(zt, P ;β, γ, τ̃). Augment a view: x′t ← augment(xt). Encode the augmented view: z′t ← h(x′t; θ). Compare the augmented view to existing prototypes: [_, ŷ′t]← E-step(z′t, P ;β, γ, τ). Compute the self-supervision loss: Lself ← Lself − 1T ỹt log ŷ ′ t. Compute the entropy loss: Lent ← Lent − 1T ŷt log ŷt. Compute the average probability of creating new prototypes, pnew ← pnew + 1T ût.
end for Compute the new cluster loss: Lnew ← − log Pr(pnew). Sum up losses: L ← Lself + λentLent + λnewLnew. Update parameters: Θ← optimize(L,Θ).
until convergence return Θ
It is worth noting that if we create a new prototype every time step, then OUPN is similar to a standard contrastive learning with an instance-based InfoNCE loss (Chen et al., 2020a; He et al., 2020); therefore it can be viewed as a generalization of this approach. Additionally, all the losses can be computed online without having to store any examples beyond the collection of prototypes.

heading: B METHOD DERIVATION
text: B.1 E-STEP
Inferring cluster assignments. The categorical variable ŷ infers the cluster assignment of the current input example with regard to the existing clusters.
ŷt,k = Pr(yt = k|zt, u = 0) (12)
= Pr(zt|yt = k, u = 0) Pr(yt = k)
Pr(zt, u = 0) (13)
= wkf(zt;pt,k, σ 2)∑ k′ wk′f(zt;pt,k′ , σ 2) (14) = exp(logwk − d(zt,pt,k)/2σ2)∑ k′ exp(logw ′ k − d(zt,pt,k′)/2σ2) (15) = softmax (logwk − d(zt,pt,k)/τ) , (16) = softmax(vt,k), (17)
where wk is the mixing coefficient of cluster k and d(·, ·) is the distance function, and vt,k is the logits. In our experiments, wk’s are kept as constant and τ is an independent learnable parameter.
Inference on unknown classes. The binary variable û estimates the probability that the current input belongs to a new cluster:
ût = Pr(ut = 1|zt) (18)
= z0u0 z0u0 + ∑ k wkf(zt;pt,k, σ 2)(1− u0) (19) = 1
1 + 1z0u0 ∑ k wkf(zt;pt,k, σ 2)(1− u0) (20)
= 1 1 + exp(log( 1z0u0 ∑ k wkf(zt;pt,k, σ 2)(1− u0))) (21) = 1
1 + exp(− log(z0)− log(u0) + log(1− u0) + log( ∑ k wkf(zt;pt,k, σ 2)) (22)
= 1 1 + exp(−s+ log( ∑ k exp(log(wk)− d(zt,pt,k)/2σ2)))
(23)
= sigmoid(s− log( ∑ k exp(log(wk)− d(zt,pt,k)/2σ2))) (24)
= sigmoid(s− log( ∑ k exp(vt,k))), (25)
where s = log(z0)+log(u0)− log(1−u0)+m log(σ)+m log(2π)/2 andm 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:
ût = sigmoid(s− log( ∑ k exp(log(wk)− d(zt,pt,k)/2σ2))) (26)
≥ sigmoid(s− log(max k exp(−d(zt,pt,k)/2σ2))) (27)
= sigmoid(s+ min k d(zt,pt,k)/2σ
2) (28)
= sigmoid((min k d(zt,pt,k)− β)/γ), (29)
where β = −2sσ2, γ = 2σ2. To make learning more flexible, we directly make β 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(pt,k|z1:t). We formulate an efficient recursive online update, similar to Kalman filtering, by incorporating the evidence of the current input zt and avoiding re-clustering the entire input history. We define p̂t,k as the estimate of the posterior mean of the k-th cluster at time step t, and σ̂2t,k is the estimate of the posterior variance.
Updating prototypes. Suppose that in the E-step we have determined that yt = k. Then the posterior distribution of the k-th cluster after observing zt is:
Pr(pt,k|z1:t, yt = k) (30) ∝ Pr(zt|pt,k, yt = k) Pr(pt,k|z1:t−1) (31)
= Pr(zt|pt,k, yt = k) ∫ p′ Pr(pt,k|pt−1,k = p′) Pr(pt−1,k = p′|z1:t−1) (32)
≈ f(zt;pt,k, σ2) ∫ p′ f(pt,k;p ′, σ2t,d)f(p ′; p̂t−1,k, σ̂ 2 t−1,k) (33)
= f(zt;pt,k, σ 2)f(pt,k; p̂t−1,k, σ 2 t,d + σ̂ 2 t−1,k). (34)
If we assume that the transition probability distribution Pr(pt,k|pt−1,k) is a zero-mean Gaussian with variance σ2t,d = (1/ρ− 1)σ̂2t−1,k, where ρ ∈ (0, 1] is some constant that we defined to be the
memory decay coefficient, then the posterior estimates are:
p̂t,k|yt=k = ztσ̂
2 t−1,k/ρ+ p̂t−1,kσ 2
σ2 + σ̂2t−1,k/ρ , σ̂2t,k|yt=k =
σ2σ̂2t−1,k/ρ
σ2 + σ̂2t−1,k/ρ . (35)
If σ2 = 1, and ĉt,k ≡ 1/σ̂2t,k, ĉt−1,k ≡ 1/σ̂2t−1,k, it turns out we can formulate the update equation as follows, and ĉt,k can be viewed as a count variable for the number of elements in each estimated cluster, subject to the decay factor ρ over time:
ĉt,k|yt=k = ρĉt−1,k + 1, (36)
p̂t,k|yt=k = zt 1
ĉt,k|yt=k + p̂t−1,k ρĉt−1,k ĉt,k|yt=k . (37)
If yt 6= k, then the prototype posterior distribution simply gets diffused at timestep t:
Pr(pt,k|z1:t, yt 6= k) ≈ f(pt,k; p̂t−1,k, σ̂2t−1,k/ρ) (38) ĉt,k|yt 6=k = ρĉt−1,k, (39) p̂t,k|yt 6=k = p̂t−1,k. (40)
Finally, our posterior estimates at time t are computed by taking the expectation over yt:
ĉt,k = E yt [ĉt,k|yt ] (41)
= ĉt,k|yt=k Pr(yt = k|zt) + ĉt,k|yt 6=k Pr(yt 6= k|zt) (42) = (ρĉt−1,k + 1)ŷt,k(1− ût,k) + ρĉt−1,k(1− ŷt,k(1− ût,k)), (43) = ρĉt−1,k + ŷt,k(1− ût,k), (44)
p̂t,k = E yt [p̂t,k|yt ] (45)
= p̂t,k|yt=k Pr(yt = k|zt) + p̂t,k|yt 6=k Pr(yt 6= k|zt) (46)
= ( zt
1
ĉt,k|yt=k + p̂t−1,k ρĉt−1,k ĉt,k|yt=k
) ŷt,k(1− ût,k) + p̂t−1,k(1− ŷt,k(1− ût,k)) (47)
= zt ŷt,k(1− ût,k) ρĉt−1,k + 1 + p̂t−1,k
( 1− ŷt,k(1− ût,k) + ŷt,k(1− ût,k)
ρĉt−1,k ρĉt−1,k + 1
) (48)
= zt ŷt,k(1− ût,k) ρĉt−1,k + 1 + p̂t−1,k
( 1− ŷt,k(1− ût,k)
ρĉt−1,k + 1
) . (49)
Since ĉt,k is also our estimate on the number of elements in each cluster, we can use it to estimate the mixture weights,
ŵt,k = ĉt,k∑ k′ ĉt,k . (50)
Note that in our experiments the mixture weights are not used and we assume that each cluster has an equal mixture probability.

heading: C EXPERIMENT DETAILS
text: We provide additional implementation details in Tab. 4, 5 and 6.
C.1 METRIC DETAILS
For each method, we used the same nearest centroid algorithm for online clustering. For unsupervised readout, at each timestep, if the closest centroid is within threshold α, then we assign the new example to the cluster, otherwise we create a 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 us a sequence of class IDs, and we will use the following metrics to compare our predicted class IDs and groundtruth class IDs. Both metrics are designed to be threshold invariant.
AMI: For unsupervised evaluation, we consider the adjusted mutual information score. Suppose we have two clustering U = {Ui} and V = {Vj}, and Ui and Vj are set of example IDs, and N is the total number of examples. U and V can be viewed as discrete probability distribution over cluster IDs. Therefore, the mutual information score between U and V is:
MI(U, V ) = |U |∑ i=1 |V |∑ j=1 |Ui ∩ Vj | N log ( N |Ui ∩ Vj | |Ui||Vj | ) (51)
= R∑ i=1 C∑ j=1 nij N log ( Nnij aibj ) . (52)
Table 9: Effect of decay rate ρ
RoamingOmniglot RoamingRooms ρ AMI AP AMI AP
0.9 51.12 64.19 65.07 75.50 0.95 79.78 89.30 74.33 81.92 0.99 89.43 95.54 76.97 84.05 0.995 90.80 95.90 77.78 85.02 0.999 86.27 93.69 38.89 39.37
Table 10: Effect of λnew
RoamingOmniglot RoamingRooms λnew AMI AP AMI AP
0.0 38.26 93.40 19.49 73.93 0.1 86.60 93.50 67.25 71.69 0.5 89.89 95.28 78.04 84.85 1.0 90.06 95.81 77.59 84.36 2.0 88.74 95.73 77.62 84.72
The adjusted MI score1 normalizes the range between 0 and 1, and subtracts the baseline from random chance:
AMI(U, V ) = MI(U, V )− E[MI(U, V )]
1 2 (H(U) +H(V ))− E[MI(U, V )]
, (53)
where H(·) denotes the entropy function, and E[MI(U, V )] is the expected mutual information by chance 2. Finally, for each model, we sweep the threshold α to get a threshold invariant score:
AMImax = max α AMI(y, ŷ(α)). (54)
AP: For supervised evaluation, we used the AP metric. The AP metric is also threshold invariant, and it takes both output û and ŷ into account. First it sorts all the prediction based on its unknown score û in ascending order. Then it checks whether ŷ makes the correct prediction. For the N top ranked instances in the sorted list, it computes: precision@N and recall@N among the known instances.
• precision@N = 1N ∑ n 1[ŷn = yn],
• recall@N = 1K ∑ n 1[ŷn = 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 et al. (2021).

heading: D ADDITIONAL EXPERIMENTAL RESULTS
text: D.1 COMPARISON TO RECONSTRUCTION-BASED METHODS
We additionally provide Tab. 7 to show a comparison with CURL (Rao et 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-based methods lag far behind self-supervised learning methods. Our method is on par with SimCLR and SwAV.
D.2 ADDITIONAL STUDIES ON 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 a 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.
1https://scikit-learn.org/stable/modules/generated/sklearn.metrics. adjusted_mutual_info_score.html
2https://en.wikipedia.org/wiki/Adjusted_mutual_information
Table 12: Effect of τ̃
RoamingOmniglot RoamingRooms τ̃ / τ AMI AP AMI AP
0.05 89.23 95.01 77.44 84.38 0.10 89.71 95.21 77.89 84.99 0.20 89.78 95.31 77.82 84.57 0.50 89.40 95.13 76.81 83.90 1.00 89.62 95.16 0.00 19.91
Table 14: Effect of mean µ of the Beta prior
RoamingOmniglot RoamingRooms µ AMI AP AMI AP
0.3 84.14 93.19 68.75 72.58 0.4 86.59 93.10 69.19 73.86 0.5 89.89 95.24 77.61 84.64 0.6 85.93 93.81 64.21 73.23 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 we introduced leads to a significant improvement on the Omniglot dataset but not on the RoamingRooms dataset.
The Beta mean µ is computed as the following: Suppose a and b are the parameters of the Beta distribution, and µ is the mean. We fix a = 4µ and b = 4− a. In Table 14, we found that the mean of the Beta prior is the best at 0.5. It has more impact on the RoamingRooms dataset, and has less impact on the RoamingOmniglot dataset. This parameter could be influenced by the total number of clusters in each sequence.

heading: E ADDITIONAL VISUALIZATION RESULTS
text: We visualize the clustering mechanism and the learned image embeddings on 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-sensitive: for example, the headboard, pillows, and the blanket are successfully separated.
In Fig. 10 and 11, we visualize the learned categories in RoamingOmniglot using t-SNE (Van der Maaten & Hinton, 2008). Different colors represent different ground-truth classes. Our method is able to learn meaningful embeddings and roughly group items of similar semantic meanings together.

Review summaries:
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.   The 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.  When 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.

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.

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.

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.