Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: 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.
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. 

Despite 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. 

Referring to the experimental results from figure 4, here are a few comments:
	
- 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.
	
- 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.

- How is the query image related to the “5000 images” which I assume you are
searching? 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
the top-9 nearest neighbors using some pre-trained representation, centered on 
the provided bounding box.  If such an approach is not reasonable, it is hard to
tell from the current text. If it is reasonable, then it would be useful to compare 
against it to get a sense of what exactly is being learned. 

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

- "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?

SimCLR and other such “generic” representation-learning approaches are solving
a significantly different problem: they are typically trying to learn representations which
have a high degree of generalizability so that they can be the backbone for a system
trained to recognize general categories, with very high variability. Here, since the goal
is to learn to recognize the exact same object, it makes more sense to take a prototype
style approach, since this is very similar to say, k-nearest neighbors. 

What I’m trying to say is perhaps that SimCLR and other such methods are not the
right baselines. A more reasonable baseline is one that just looks at distances to the
training sets. 


The 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.


Other issues:

1) “we make two changes on the model inference procedure defined above.”
Why did the authors describe the changes to the model in the Experiments section?
Isn’t the right place to discuss this in Section 3, the section where the model and
methods are described? This makes it sound like a last second change….Or, perhaps
like it was a difficult-to-justify method that would be difficult to explain. What is the
motivation for putting it in experiments?

2) adjusted MI. While I follow the argument for using a max_alpha in the adjusted mutual
information, 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.

3) The function g() is introduced with no definition.

4) How is K the number of classes chosen?


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:
- data sets used and how they were sampled to produce "training" and test data
- 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.
- Given the nature of the problem, it appears as though a variety of nearest-neighbor style baselines would be appropriate.



In 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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
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$.

The 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).

The 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.

Eq. (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.

What 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}$?

What 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.

Why 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?

"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)).

In 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.

In 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).

"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.

The 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?

The 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):
1. Zhu et al. 2021, "Prototype Augmentation and Self-Supervision for Incremental Learning"
2. Gallardo et al. 2021, "Self-Supervised Training Enhances Online Continual Learning"
3. Zhang et al. 2021, "Self-Supervised Learning Aided Class-Incremental Lifelong Learning"
4. Cha et al. 2021, "Co$^2$L: Contrastive Continual Learning"

The 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.

The networks used are too small, more inline with few-shot learning and unlike most work on either self=supervised representation learning or continual learning.

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.

There 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.

Writing 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).

The 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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
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.

However, 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.

I 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.

Besides, the language, the equations, are all above the thresold of the acceptance.
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.

The 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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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. 

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

Firstly, 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.

In 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.

Secondly, 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. 

Finally, 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_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.
review_title: null

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