OBoW: Online Bag-of-Visual-Words Generation for Self-Supervised Learning

Learning image representations without human supervision is an important and active research field. Several recent approaches have successfully leveraged the idea of making such a representation invariant under different types of perturbations, especially via contrastive-based instance discrimination training. Although effective visual representations should indeed exhibit such invariances, there are other important characteristics, such as encoding contextual reasoning skills, for which alternative reconstruction-based approaches might be better suited. With this in mind, we propose a teacher-student scheme to learn representations by training a convolutional net to reconstruct a bag-of-visual-words (BoW) representation of an image, given as input a perturbed version of that same image. Our strategy performs an online training of both the teacher network (whose role is to generate the BoW targets) and the student network (whose role is to learn representations), along with an online update of the visual-words vocabulary (used for the BoW targets). This idea effectively enables fully online BoW-guided unsupervised learning. Extensive experiments demonstrate the interest of our BoW-based strategy which surpasses previous state-of-the-art methods (including contrastive-based ones) in several applications. For instance, in downstream tasks such Pascal object detection, Pascal classification and Places205 classification, our method improves over all prior unsupervised approaches, thus establishing new state-of-the-art results that are also significantly better even than those of supervised pre-training. We provide the implementation code at https://github.com/valeoai/obow.


Introduction
Learning unsupervised image representations based on convolutional neural nets (convnets) has attracted a significant amount of attention recently. Many different types of convnet-based methods have been proposed in this regard, including methods that rely on using annotation-free pretext tasks [16,28,46,53,57,85], generative methods that model the image data distribution [17,18,21], as well as clustering-based approaches [4,6,7].
Several recent methods opt to learn representations via instance-discrimination training [9,20,35,80], typically implemented in a contrastive learning framework [12,34]. The primary focus here is to learn low-dimensional image / instance embeddings that are invariant to intra-image variations while being discriminative among different images. Although these methods manage to achieve impressive results, they focus less on other important aspects in representation learning, such as contextual reasoning, for which alternative reconstruction-based approaches [15,57,85,86] might be better suited. For instance, the task of predicting from an image region the contents of the entire image requires to recognize the visual concepts depicted in the provided region and then to infer from them the structure of the entire scene. So, training for such a task has the potential of squeezing out more information from the training images and of learning richer and more powerful representations.
However, reconstructing image pixels is an ambiguous and hard-to-optimize task that forces the convnet to spend a lot of capacity on modeling low-level pixel details. It is all the more unnecessary when the final goal deals with highlevel image understanding, such as image classification. To leverage the advantages of the reconstruction principle without focusing on unimportant pixel details, one can focus on reconstruction over high-level visual concepts, referred to as visual words. For instance, BoWNet [26] derived a teacherstudent learning scheme following this principle. In this teacher-student setting, given an image, the teacher extracts feature maps that are then quantized in a spatially-dense way over a vocabulary of visual words. Then, the resulting visual words-based image description is exploited for training the student on the self-supervised task of reconstructing the distribution of the visual words of an image, i.e., its bag-ofwords (BoW) representation [81], given as input a perturbed version of that same image. By solving this reconstruction task the student is forced to learn perturbation-invariant and context-aware representations while "ignoring" pixel details.
Despite its advantages, the BoWNet approach exhibits some important limitations that do not allow it to fully exploit the potential of the BoW-based reconstruction task. One of them is that it relies on the availability of an already pre-trained teacher network. More importantly, it assumes that this teacher remains static throughout training. However, due to the fact that during the training process the quality of the student's representations will surpass the teacher's ones, a static teacher is prone to offer a suboptimal supervisory signal to the student and to lead to an inefficient usage of the computational budget for training.
In this paper, we propose a BoW-based self-supervised approach that overcomes the aforementioned limitations. To that end, our main technical contributions are three-fold: 1. We design a novel fully online teacher-student learning scheme for BoW-based self-supervised training (Fig. 1). This is achieved by online training of the teacher and the student networks.
2. We significantly revisit key elements of the BoWguided reconstruction task. This includes the proposal of a dynamic BoW prediction module used for reconstructing the BoW representation of the student image. This module is carefully combined with adequate online updates of the visual-words vocabulary used for the BoW targets.
3. We enforce the learning of powerful contextual reasoning skills in our image representations. Revisiting data augmentation with aggressive cropping and spatial image perturbations, and exploiting multi-scale BoW reconstruction targets, we equip our student network with a powerful feature representation.
Overall, the proposed method leads to a simpler and much more efficient training methodology for the BoW-guided reconstruction task that manages to learn significantly better image representations and therefore achieves or even surpasses the state of the art in several unsupervised learning benchmarks. We call our method OBoW after the online BoW generation mechanism that it uses.

Related Work
Bags of visual words. Bag-of-visual-words representations are powerful image models able to encode image statistics from hundreds of local features. Thanks to that, they were used extensively in the past [13,42,58,66,71] and continue to be a key ingredient of several recent deep learning approaches [2,26,29,40]. Among them, BoWNet [26] was the first work to use BoWs as reconstruction targets for unsupervised representation learning. Inspired by it, we propose a novel BoW-based self-supervised method with a more simple and effective training methodology that includes generating BoW targets in a fully online manner and further enforcing the learning of context-aware representations.
Self-supervised learning. A prominent paradigm for unsupervised representation learning is to train a convnet on an artificially designed annotation-free pretext task, e.g., [3,10,16,28,47,52,53,76,78,84,88]. Many works rely on pretext reconstruction tasks [1,30,46,57,59,74,85,86,88], where the reconstruction target is defined at image pixel level. This is in stark contrast with our method, which uses a reconstruction task defined over high-level visual concepts (i.e., visual words) that are learnt with a teacher-student scheme in a fully online manner.
Instance discrimination and contrastive objectives. Recently, unsupervised methods based on contrastive learning objectives [8,9,23,24,35,38,41,51,54,69,77,80] have shown great results. Among them, contrastive-based instance discrimination training [9,19,35,43,80] is the most prominent example. In this case, a convnet is trained to learn image representations that are invariant to several perturbations and at the same time discriminative among different images (instances). Our method also learns intra-image invariant representations, since the convnet must predict the same BoW target (computed from the original image) regardless of the applied perturbation. More than that however, our work also places emphasis on learning context-aware representations, which, we believe, is another important characteristic that effective representations should have. In that respect, it is closer to contrastive-based approaches that target to learn context-aware representations by predicting (in a contrastive way) the state of missing image patches [38,54,72].
Teacher-student approaches. This paradigm has a long research history [25,65] and it is frequently used for distilling a single large network or an ensemble, the teacher, into a smaller network, the student [5,39,44,56]. This setting has been revisited in the context of semi-supervised learning where the teacher is no longer fixed but evolves during training [45,68,73]. In self-supervised learning, BowNet [26] trains a student to match the BoW representations produced by a self-supervised pre-trained teacher. MoCo [35] relies on a slow-moving momentum-updated teacher to generate up-to-date representations to fill a memory bank of negative images. BYOL [33], which is a method concurrent to our work, also uses a momentum-updated teacher and trains the student to predict features generated by the teacher. However, BYOL, similar to contrastive-based instance discrimination methods, uses low-dimensional global image embeddings as targets (produced from the final convnet output) and primarily focuses on making them intra-image invariant. On the contrary, our training targets are produced by converting the intermediate teacher feature maps to high-dimensional BoW vectors that capture multiple local visual concepts, thus constituting a richer target representation. Moreover, they are built over an online-updated vocabulary from randomly sampled local features, expressing the current image as statistics over this vocabulary (see § 3.1). Therefore, our BoW targets expose fewer learning "shortcuts" (a critical aspect in self-supervised learning [3,16,53,78]), thus preventing to a larger extent teacher-student collapse and overfitting. An image x is passed through the encoder T and its output feature maps T (x) are embedded into a BoW representation yT(x) over a vocabulary V of features from T. The vocabulary V is updated at each step. The encoder S aims to reconstruct yT(x) from data-augmented instancesx. A dynamic BoW-prediction head learns to leverage the continuously updated vocabulary V to compute the BoW representation from the features S(x). T follows slowly the learning trajectory of S via momentum updates.
Relation to SwAV [8]. OBoW presents some similarity (e.g., using online vocabularies) with SwAV [8]. However, the prediction tasks fundamentally differ: OBoW exploits a BoW prediction task while SwAV uses an image-cluster prediction task [4,6,7]. BoW targets are much richer representations than image-cluster assignments: a BoW encodes all the local-feature statistics of an image whereas an imagecluster assignment encodes only one global image feature.

Our approach
Here we explain our proposed approach for learning image representations by reconstructing bags of visual words. We start with an overview of our method. Overview. The bag-of-words reconstruction task involves a student convnet S(·) that learns image representations, and a teacher convnet T(·) that generates BoW targets used for training the student network. The student S(·) is parameterized by θ S and the teacher T(·) by θ T .
To generate a BoW representation y T (x) out of an image x, the teacher first extracts the feature map T (x) ∈ R c ×h ×w , of spatial size h × w with c channels, from its th layer (in our experiments is either the last L or penultimate L − 1 convolutional layer of T(·)). It quantizes the c -dimensional feature vectors T (x)[u] at each location u ∈ {1, · · · , h × w } of the feature map over a vocabulary V = [v 1 , . . . , v K ] of K visual words of dimension c . This quantization process produces for each location u a K-dimensional code vector q(x)[u] that encodes the assignment of T(x)[u] to its closest (in terms of squared Euclidean distance) visual word(s). Then, the teacher reduces the quantized feature maps q(x) to a Kdimensional BoW,ỹ T (x), by channel-wise max-pooling, i.e., is the assignment value of the code q(x)[u] for the k th word. Finally,ỹ T (x) is converted into a probability distribution over the visual words by L 1 -normalization, i.e., . To learn image representations, the student gets as input a perturbed version of the image x, denoted asx, and is trained to reconstruct the BoW representation y T (x), produced by the teacher, of the original unperturbed image x. To that end, it first extracts a global vector representation S(x) ∈ R c (with c channels) from the entire imagex and then applies a linear-plus-softmax layer to S(x), as follows: where W = [w 1 , · · · , w K ] are the c-dimensional weight vectors (one per word) of the linear layer. The Kdimensional vector y S (x) is the predicted softmax probability of the target y T (x). Hence, the training loss that is minimized for a single image x is the cross-entropy loss between the softmax distribution y S (x) predicted by the student from the perturbed imagex, and the BoW distribution y T (x) of the unperturbed image x given by the teacher. Our technical contributions. In the following, we explain (i) in § 3.1, how to construct a fully online training methodology for the teacher, the student and the visual-words vocabulary, (ii) in § 3.2, how to implement a dynamic approach for the BoW prediction that can adapt to continuously-changing vocabularies of visual words, and finally (iii) in § 3.3, how to significantly enhance the learning of contextual reasoning skills by utilizing multi-scale BoW reconstruction targets and by revisiting the image augmentation schemes.

Fully online BoW-based learning
To make the BoW targets encode more high-level features, BoWNet pre-trains the teacher convnet T(·) with another unsupervised method, such as RotNet [28], and computes the vocabulary V for quantizing the teacher feature maps offline by applying k-means on a set of teacher feature maps extracted from training images. After the end of the student training, during which the teacher's parameters remain frozen, the student becomes the new teacher T(·) ← S(·), a new vocabulary V is learned off-line from the new teacher, and a new student is trained, starting a new training cycle. In this case however, (a) the final success depends on the quality of the first pre-trained teacher, (b) the teacher and the BoW reconstruction targets y T (x) remain frozen for long periods of time, which, as already explained, results in a suboptimal training signal, and (c) multiple training cycles are required, making the overall training time consuming.
To address these important limitations, in this work we propose a fully online training methodology that allows the teacher to be continuously updated as the student training progresses, with no need for off-line k-means stages. This requires an online updating scheme for the teacher as well as for the vocabulary of visual words used for generating the BoW targets, both of which are detailed below. Updating the teacher network. Inspired by MoCo [35], the parameters θ T of the teacher convnet are an exponential moving average of the student parameters. Specifically, at each training iteration the parameters θ T are updated as where α ∈ [0, 1] is a momentum coefficient. Note that, as a consequence, the teacher has to share exactly the same architecture as the student. With a proper tuning of α, e.g., α = 0.99, this update rule allows slow and continuous updates of the teacher, avoiding rapid changes of its parameters, such as with α = 0, which would make the training unstable. As in MoCo, for its batch-norm units, the teacher maintains different batch-norm statistics from the student.
Updating the visual-words vocabulary. Since the teacher is continuously updated, off-line learning of V is not a viable option. Instead, we explore two solutions for computing V, online k-means and a queue-based vocabulary.
Online k-means. One possible choice for updating the vocabulary is to apply online k-means clustering after each training step. Specifically, as proposed in VQ-VAE [55,62], we use exponential moving average for vocabulary updates. A critical issue that arises in this case is that, as training progresses, the features distribution changes over time. The visual words computed by online k-means do not adapt to this distribution shift leading to extremely unbalanced cluster assignments and even to assignments that collapse to a single cluster. In order to counter this effect, we investigate For each input image x to T, "local" features are pooled from T (x) by averaging over 3 × 3 sliding windows. One of the resulting vectors is selected randomly and added as visual word to the vocabulary queue, replacing the oldest word in the vocabulary. different strategies: (a) detection of rarely used visual words over several mini-batches and replacement of these words with a randomly sampled feature vector from the current mini-batch; (b) enforcing uniform assignments to each cluster thanks to the Sinkhorn optimization as in, e.g., [4,8]. For more details see §D.
A queue-based vocabulary. In this case, the vocabulary V of visual words is a K-sized queue of random features. At each step, after computing the assignment codes over the current vocabulary V, we update V by selecting one feature vector per image from the current mini-batch, inserting it to the queue, and removing the oldest item in the queue if its size exceeds K. Hence, the visual words in V are always feature vectors from past mini-batches. We explore three different ways to select these local feature vectors: (a) uniform random sampling of one feature vector in T (x); (b) global average pooling of T (x) (average feature vector of each image); (c) an intermediate approach between (a) and (b) which consists of a local average pooling with a 3 × 3 kernel (stride 1, padding 0) of the feature map T (x) followed by a uniform random sampling of one of the resulting feature vectors (Fig. 2). Our intuition for option (c) is that, assuming that the local features in a 3 × 3 neighborhood belong to one common visual concept, then local averaging selects a more representative visual-word feature from this neighborhood than simply sampling at random one local feature (option (a)). Likewise, the global averaging option (b) produces a representative feature from an entire image, which however, might result in overly coarse visual word features.
The advantage of the queue-based solution over online k-means is that it is simpler to implement and it does not require any extra mechanism for avoiding unbalanced clusters, since at each step the queue is updated with new randomly sampled features. Indeed, in our experiments, the queuebased vocabulary with option (c) provided the best results.
Generating BoW targets with soft-assignment codes.
For generating the BoW targets, we use soft-assignments instead of the hard-assignments used in BoWNet. This is preferable from an optimization perspective due to the fact that the vocabulary of visual words is continuously evolving. We thus compute the assignment codes q( . The parameter δ is a temperature value that controls the softness of the assignment. We use δ = δ base ·μ MSD , where δ base > 0 andμ MSD is the exponential moving average (with momentum 0.99) of the mean squared distance of the feature vectors in T (x) from their closest visual words. The reason for using an adaptive temperature instead of a constant one is due to the change of magnitude of the feature activations during training, which induces a change of scale of the distances between the feature vectors and the words.

Dynamic bag-of-visual-word prediction
To learn effective image representations, the student must predict the BoW distribution over V of an image using as input a perturbed version of that same image. However, in our method the vocabulary is constantly updated and the visual words are changing or being replaced from one step to the next. Therefore, predicting the BoW distribution over a continuously updating vocabulary V with a fixed linear layer would make training unstable, if not impossible. To address this issue we propose to use a dynamic BoW-prediction head that can adapt to the evolving nature of the vocabulary. To that end, instead of using fixed weights as in (1), we employ a generation network G(·) that takes as input the current vocabulary of visual words V = [v 1 , . . . , v K ] and produces prediction weights for them as represents the prediction weight vector for the k th visual word. Therefore, Equation 1 becomes where κ is a fixed coefficient that equally scales the magnitudes of all the predicted weights , which by design are L 2 -normalized. We implement G(·) with a 2-layer perceptron whose input and output vectors are L 2 -normalized (see Fig. 3). Its hidden layer has size 2 × c.
We highlight that dynamic weight-generation modules are extensively used in the context of few-shot learning for producing classification weight vectors of novel classes using as input a limited set of training examples [27,31,61]. The advantages of using G(·) instead of fixed weights, which BoWNet uses, are the equivariance to permutations of the visual words, the increased stability to the frequent and abrupt updates of the visual words, a number of parameters |θ G | independent from the number of visual words K, hence requiring fewer parameters than a fixed-weights linear layer for large vocabularies.

Representation learning based on enhanced
contextual reasoning Data augmentation. The key factor for the success of many recent self-supervised representation learning methods [8,9,11,33,70] is to leverage several image augmentation/perturbation techniques, such as Gaussian blur [9], color jittering and random cropping techniques, as cutmix [82] that substitutes one random-size patch of an image with that of another. In our method, we want to fully exploit the possibility of building strong image representations by hiding local information. As the teacher is randomly initialised, it is important to hide large regions of the original image from the student so as to prevent the student from relying only on low-level image statistics for reconstructing the distributions y T (x) over the teacher visual words, which capture lowlevel visual cues at the beginning of the training. Therefore, we carefully design our image perturbations scheme to make sure that the student has access to only a very small portion of the original image. Specifically, similar to [8,51], we extract from a training image multiple crops with two different mechanisms: one that outputs 160 × 160-sized crops that cover less than 60% of the original image and one with 96 × 96-sized crops that cover less than 14% of the original image (see Fig. 4). Given those image crops, the student must reconstruct the full bags of visual words from each of them independently. Therefore, our cropping strategy definitively forces the student network to understand and learn spatial dependency between visual parts. Multi-scale BoW reconstruction targets. We also consider reconstructing BoW from multiple network layers that correspond to different scale levels. In particular, we experiment with using both the last scale level L (i.e., layer conv5 in ResNet) and the penultimate scale level L − 1 (i.e., layer conv4 in ResNet). The reasoning behind this is that the features of level L−1 still encode semantically , we extract two types of image crops. The first type (middle) is obtained by randomly sampling an image region whose area covers no more than 60% of the entire image, resizing it to 160 × 160 and then giving it as input to the student as part of the reconstruction task. The second type (right) is obtained by randomly selecting an area that covers between 60% to 100% of the entire image, resizing it to a 256 × 256 image, dividing it into 3 × 3 overlapping patches of size 96 × 96, and randomly choosing 5 out of these 9 patches (indicated with red rectangles) that are given as 5 separate inputs to the student. The student must then reconstruct the original BoW target independently for each patch. The blue rectangle on the left image indicates the central 224 × 224 crop from which the teacher produces the BoW target. Note that, except from horizontal flipping, no other perturbation is applied on the teacher's inputs.
important concepts but have a smaller receptive field than those in the last level. As a result, the visual words of level L−1 that belong to image regions hidden to the student are less likely to be influenced by pixels of image regions the student is given as input. Therefore, by using BoW from this extra feature level, the student is further enforced to learn contextual reasoning skills (and in fact, at a level with higher spatial details due to the higher resolution of level L−1), thus learning richer and more powerful representations. When using BoW extracted from two layers, our method includes a separate vocabulary for each layer, denoted by V L and V L−1 for layers L and L−1 respectively, and two different weight generators, denoted by G L (·) and G L−1 (·) for layers L and L−1, respectively. Regardless of what layer the BoW target comes from, the student uses a single global image representation S(x), typically coming from the global average pooling layer after the last convolutional layer (i.e., layer pool5 in ResNet), to perform the reconstruction task. We show empirically in Section 4.1 that the contextual reasoning skills implicitly developed via using the above two schemes are decisive to learn effective image representations with the BoW-reconstruction task.

Experiments and results
We evaluate our method (OBoW) on the ImageNet [64], Places205 [87] and VOC07 [22] classification datasets as well as on the V0C07+12 detection dataset. Implementation details. For our models, the vocabulary size is set to K = 8192 words and, as in BoWNet, when computing the BoW targets we ignore the visual words that correspond to the feature vectors on the edge of the teacher

Analysis
Here we perform a detailed analysis of our method. Due to the computationally intensive nature of pre-training on ImageNet, we use a smaller but still representative version created by keeping only 20% of its images and we implement our model with the light-weight ResNet18 architecture. For training we use SGD for 80 epochs with cosine learning rate initialized at 0.05, batch size 128 and weight decay 5e−4. We evaluate models trained with two versions of our method, the vanilla version that uses single-scale BoWs and from each training image extracts one 160 × 160-sized crop (with which it trains the student), and the full version that uses multi-scale BoWs and extracts from each training image two 160 × 160-sized crops plus five 96 × 96-sized patches.
Evaluation protocols. After pre-training, we freeze the learned representations and use two evaluation protocols. (1) The first one consists in training 1000-way linear classifiers for the ImageNet classification task.

Results
Online vocabulary updates. In Tab. 1, we compare the approaches for online vocabulary updates described § 3.1. The   Table 3: Ablation of dynamic BoW prediction and softquantization. For these results, we used the vanilla version of our method. "Soft": soft assignment instead of hard assignment. "Dyn": dynamic weight generation instead of fixed weights.
queue-based solutions achieve in general better results than online k-means. Among the queue-based options, random sampling of locally averaged features, opt. (c), provides the best results. Its advantage over option (b) with global averaging is more evident with multi-scale BoWs where an extra feature level with a higher resolution and more localized features is used, in which case global averaging produces visual words that are too coarse. In all remaining experiments, we use a queue-based vocabulary with option (c).
Momentum for teacher updates. In Table 2, we study the sensitivity of our method w.r.t. the momentum α for the teacher updates (Equation 3). We notice a strong drop in performance when decreasing α from 0.9 to 0.5 (a rapidlychanging teacher), and to 0 (the teacher and student have identical parameters), while keeping the initial learning rate fixed (lr = 0.05). However, we noticed that this was not due to any cluster/mode collapse issue. The issue is that the teacher signal is more noisy at low α because of the rapid change of its parameters. This prevents the student to converge when keeping the learning rate as high as 0.05. We notice in Table 2 that a reduction of the learning rate to adapt to the reduction of α reduces the performance gap. This indicates that our method is not as sensitive to the choice of the momentum as MoCo and BYOL were shown to be.  Dynamic BoW prediction and soft quantization. In Table 3, we study the impact of the dynamic BoW prediction and of using soft assignment for the codes instead of hard assignment. We see that (1), as expected, the network is unable to learn useful features without the proposed dynamic BoW prediction, i.e., when using fixed weights; (2) soft assignment indeed provides a performance boost.
Enforcing context-aware representations. In Table 4 we study different types of image crops for the BoW reconstruction tasks, as well as the impact of multi-scale BoW targets. We observe that: (1) as we discussed in § 3.3, smaller crops that hide significant portions of the original image are better suited for our reconstruction task thus leading to dramatic increase in performance (compare entries 1 × 224 2 with the 1 × 160 2 and 5 × 96 2 entries).
(3) Finally, employing multi-scale BoWs improves the performance even further.
BoW-like comparison.
In Table 5, we compare our method with the reference BoW-like method BoWNet. For a fair comparison, we implemented BoWNet both with its proposed augmentations, i.e., using one 224 × 224-sized crop with cutmix ("BoWNet" row), and with the image augmentation we propose in the vanilla version of our method, i.e., one 160 × 160-sized crop ("BoWNet (160 2 crops)").  Table 6: Evaluation of ImageNet pre-trained ResNet50 models. The "Epochs" and "Batch" columns provide the number of pre-training epochs and the batch size of each model respectively. The first section includes models pre-trained with a similar number of epochs as our model (second section). We boldfaced the best results among all sections as well as of only the top two. For the linear classification tasks, we provide the top-1 accuracy. For object detection, we fine-tuned Faster R-CNN (R50-C4) on VOC trainval07+12 and report detection AP scores by testing on test07. For semi-supervised learning, we fine-tune the pre-trained models on 1% and 10% of ImageNet and report the top-5 accuracy. Note that, in this case the "Supervised" entry results come from [83] and are obtained by supervised training using only 1% or 10% of the labelled data. All the classification results are computed with single-crop testing. † : results computed by us.
We see that our method, even in its vanilla version, achieves significantly better results, while using at least two times fewer training epochs, which validates the efficiency of our proposed fully-online training methodology.

Self-supervised training on ImageNet
Here we evaluate our method by pre-training with it convnet-based representations on the full ImageNet dataset. We implement the full solution of our method (as described in § 4.1) using the ResNet50 (v1) [37] architecture. We evaluate the learned representations on ImageNet, Places205, and VOC07 classification tasks as well as on VOC07+12 detection task and provide results in Table 6. On the Ima-geNet classification we evaluate on two settings: (1) training linear classifiers with 100% of the data, and (2) fine-tuning the model using 1% or 10% of the data, which is referred to as semi-supervised learning.
Results. Pre-training on the full ImageNet and then transferring to downstream tasks is the most popular benchmark for unsupervised representations and thus many methods have configurations specifically tuned on it. In our case, due to the computational intensive nature of pre-training on ImageNet, no full tuning of OBoW took place. Nevertheless, it achieves very strong empirical results across the board. Its classification performance on ImageNet is 73.8%, which is substantially better than instance discrimination methods MoCo v2 and SimCLR, and even improves over the recently proposed BYOL and SwAV methods when considering a similar amount of pre-training epochs. Moreover, in VOC07 classification and Places205 classification, it achieves a new state of the art despite using significantly fewer pre-training epochs than related methods. On the semi-supervised Ima-geNet ResNet50 setting, it significantly surpasses the state of the art for 1% labels, and is also better for 10% labels using again much fewer epochs. On VOC detection, it outperforms previous state-of-the-art methods while demonstrating strong performance improvements over supervised pre-training.

Conclusion
In this work, we introduce OBoW, a novel unsupervised teacher-student scheme that learns convnet-based representations with a BoW-guided reconstruction task. By employing an efficient fully-online training strategy and promoting the learning of context-aware representations, it delivers strong results that surpass prior state-of-the-art approaches on most evaluation protocols. For instance, when evaluating the derived unsupervised representations on the Places205 classification, Pascal classification or Pascal object detection tasks, OBoW attains a new state of the art, surpassing prior methods while demonstrating significant improvements over supervised representations.

A. Comparing with MoCo for the same image augmentations
In the main paper we saw that the image augmentation techniques that we designed for our method have a strong positive impact on the quality of the learned representations. However, we stress that the performance improvement of our method over state-of-the-art instance-discrimination methods is not simply due a better mix of augmentations.
For example, in Table 7 we compare OBoW with MoCo v2, when the latter is implemented with the same image augmentations as those in the full solution of OBoW. We see that indeed, although the proposed augmentations also improve MoCo v2, our method is still significantly better, even in its vanilla version that employs simpler augmentations (i.e., only a single 160 × 160-sized crop). Therefore, the ability of OBoW to learn state-of-the-art representations is mainly due to its BoW-guided reconstruction formulation.  Table 7: Comparison with MoCo v2 for the same image augmentations. "EP": total number of epochs used for pre-training. The results are obtained by training ResNet18-based models on 20% of ImageNet, similar to Sections 4.1 and 4.2 of the main paper. "MoCo v2 (our aug.) " is a MoCo v2 model implemented with the same augmentations that we use in the full version of our work, i.e., two 160 × 160-sized crops plus five 96 × 96-sized patches.

B. Visualization of the vocabulary features
In Figures 5 and 6 we illustrate visual words from the conv5 and conv4 teacher feature maps of a ResNet50 OBoW model trained on ImageNet. Since we use a queuebased vocabulary that is constantly updated, for the visualizations we used the state of the vocabulary at the end of training. In order to visualize a visual word, we retrieve multiple image patches from images in the ImageNet training set and depict the 8 patches with the highest assignment score for that visual word. As it can be noticed, visual words encode high level visual concepts.
C. Implementation details C.1. Image augmentation during pre-training In Section 3.3 of the main paper, we described the two types of image crops that we extract from a training image in order to train the student network with them. In addition, beyond image cropping, similar to SimCLR [9], we also applied color jittering, color-to-grayscale conversion, Gaussian blurring and horizontal flipping as augmentation techniques. All implementation details are provided in Section G in the form of PyTorch code.

C.2. Evaluation protocols in Section 4.1
To evaluate the quality of the learned representations, we use two protocols. (1) The first protocol consists in freezing the convnet and then training on its features 1000-way linear classifiers for the ImageNet classification task. The classifier is applied on top of the 512-dimensional feature vectors produced from the final global pooling layer of ResNet18. It is trained with SGD for 50 epochs using a learning rate of 10 that is divided by a factor of 10 every 15 epochs. The batch size is 256 and the weight decay 2e−6. For fast experimentation, we train the linear classifier with precached features extracted from the 224 × 224 central crop of the image and its horizontally flipped version. (2) For the second protocol, we use a few-shot episodic setting [75]. We choose 300 classes from ImageNet and run 200 episodes of 50-way fewshot classification tasks. Essentially, for each episode, we randomly select 50 classes from the 300 ones and, for each of these selected classes, n training examples and m = 1 test example (both randomly sampled from the validation images of ImageNet). For n, we use 1 and 5 examples corresponding to 1-shot and 5-shot classification settings, respectively. The m test examples per class are classified using a cosinedistance Prototypical-Networks [67] classifier applied on top of the frozen self-supervised representations. We report the mean accuracy over the 200 episodes. The purpose of this metric is to analyze the ability of the representations to be used for learning with few training examples. Furthermore, it has the advantage of not requiring tuning of any hyperparameters, such as the learning rate of a linear classifier, the number of training steps, etc.

C.3. Self-supervised training on ImageNet
Here we provide implementation details for the pretraining of the ResNet50-based OBoW model that we use in Section 4.3 of the main paper. We present the full implementation of our method, which includes multi-scale BoWs from the conv4 and conv5 layers of ResNet50, and extraction of two crops of size 160 × 160 plus five patches of size 96 × 96 per training image. To extract BoW targets, we use K = 8192 as vocabulary size and we ignore the local feature vectors on the edge / border of the teacher's feature maps. The momentum coefficient α for the teacher updates is initialized at 0.99 and is annealed to 1.0 during training with a cosine schedule. Finally, the hyper-parameters κ and δ base are set to 8 and 1/15 respectively. We train the model for 200 training epochs with SGD using 1e−4 weight decay and 256-sized mini-batches. As a learning-rate schedule, we warm up the learning rate from 0 to 0.03 with linear annealing during the first 10 epochs and then, for the remaining 190 epochs, we decrease it from 0.03 to 0.00003 with cosine-based schedule. To train the model we use 4 Tesla V100 GPUs with data-distributed training (i.e., the mini-batch is divided across the 4 GPUs) while keeping the batch-norm statistics synchronized across all GPUs (i.e., use the SyncBatchNorm units of PyTorch).

C.4. Evaluation protocols in Section 4.3
Here we describe the evaluation protocols that we use in Section 4.3 of the main paper. ImageNet linear classification. In this case, we evaluate the performance on the 1000-way ImageNet classification task by applying a linear classifier on top of the 2048dimensional frozen features of the pool5 layer of ResNet50. We train the linear classifier using SGD for 100 training epochs with 0.9 momentum, 0 weight decay, 1024-sized mini-batches and cosine learning-rate schedule initialized at 10.0. We use the typical image augmentations used for the fully-supervised training of ResNet50 models on this dataset.

Places205 linear classification.
For this protocol, we evaluate the performance on the 205-way Places classification task by applying a linear classifier on top of the 2048dimensional frozen features of the pool5 layer of ResNet50. We follow the guidelines of [32] and train the linear classifier using SGD for 14 training epochs and a learning rate of 0.01 that is multiplied by 0.1 after 5 and 10 epochs. The batch size is 256 and the weight decay is 1e−4.
VOC07 linear classification with SVMs. Here we evaluate on the VOC07 classification task by training and testing linear SVMs on top of the 2048-dimensional frozen features of the pool5 layer. To this end, we use the publicly available code for benchmarking self-supervised methods provided in [32] that trains the SVMs using the VOC07 train+val splits and tests them using the VOC07 test split.
Semi-supervised learning setting on ImageNet. For this semi-supervised setting, we fine-tune the self-supervised ResNet50 model (pre-trained on all ImageNet unlabelled images) on 1% or 10% of ImageNet labelled images. We use the same 1% and 10% splits as in SimCLR (i.e., we downloaded and use the split files of their official code release). We train using SGD with 256-sized mini-batches, 0 weight decay, and two distinct learning rates for the classification head and the feature extractor trunk network components respectively. Specifically, in the 1% setting, we use 40 epochs and the initial learning rates 0.5 and 0.0002 for the classification head and feature extractor trunk components, respectively, which are then multiplied by a factor of 0.2 after 24 and 32 epochs. In the 10% setting, we use 20 epochs and the initial learning rates 0.5 and 0.0002 for the classification head and feature extractor trunk components, respectively, which are multiplied by a factor of 0.2 after 12 and 16 epochs.

VOC object detection.
Here we evaluate the utility of OBoW on a complex downstream task: object detection. We follow the setup considered in prior works [8,26,32,35,51]: we fine-tune the pre-trained OBoW with a Faster R-CNN [63] model using a ResNet50 backbone [36] (R50-C4 in Detectron2 [79]). We use the fine-tuning protocol and most hyper-parameters from He et al. [35]: fine-tune on trainval07+12 and evaluate on test07.
In detail, we train with mini-batches of size 16 across 4 GPUs for 24K steps, using SyncBatchNorm to finetune BatchNorm parameters, as well as inserting an additional BatchNorm layer for the RoI head after conv5, i.e., Res5ROIHeadsExtraNorm layer in Detectron2. The initial learning rate 0.01 is warmed-up with a slope of 1e−3 for 100 steps and then reduced by a factor of 10 after 18K and 22K steps. We report results for the final checkpoint averaged over 3 different runs.

D. On-line k-means vocabulary updates
As explained in the main paper, one of the explored choices for updating the vocabulary is to use online k-means after each training step. Specifically, as proposed in VQ-VAE [55,62], we use exponential moving average for vocabulary updates. In this case, for each mini-batch, we compute the number n k of feature vectors assigned to each cluster k and m k the element-wise sum of all feature vectors assigned to cluster k and update with γ = 0.99. The k th visual word of the vocabulary V satisfies v k = M k /N k . A critical issue that arises in this case is that, as training progresses, the features distribution changes over time. The visual words computed by online k-means do not adapt to this distribution shift leading to extremely unbalanced cluster assignments and even to assignments that collapse to a single cluster. In order to counter this effect, we investigate two different strategies: (a) Detection and replacement of rare visual words. In this case, for each visual word we keep track of the time of its most recent assignment as closest cluster centroid to a feature vector. If more than 1000 training steps have passed since then, then we replace it with a local feature vector randomly sampled with uniform distribution from the current mini-batch.
(b) Enforcing uniform assignments via Sinkhorn optimization. Let x 1 , . . . , x b be the b images of the current mini-batch and D be the K × B matrix (B = h × w × b) whose i th row D i contains the squared distances between all the local features in the mini-batch (across all images and spatial dimensions) and the i th visual word: , . Similarly to [4,8], we compute the assignment codes by solving the regularised optimal transport problem min Q∈Q i,j Q i,j D i,j + ε Q i,j log Q i,j , where ε is a coefficient that controls the softness of the assignments. The set Q permits us to enforce uniform assignments among all the visual words and satisfies Q = {Q ∈ R K×B where 1 K and 1 B are vectors of length K and B, respectively, with all entries equal to 1. We compute Q with the Sinkhorn algorithm [14] and use the resulting assignment codes for the on-line k-means updates and for the computation of the BoW targets.

E. Time and memory consumption
In Table 8, we provide the time and memory consumption of our method as well as of MoCo v2 and BYOL. We observe that OBoW achieves state-of-the-art results in less time ("Training time" row) than the competing methods. In terms of GPU memory consumption, with 256-sized mini-batches our method requires 15775Mb per GPU in a 4-GPU machine (or 8901Mb per GPU in a 8-GPU machine).

F. COCO detection and instance segmentation
In Table 9 we evaluate the learned representations on the downstream tasks of object detection and instance segmentation on COCO [50]. To this end, we fine-tune the pretrained representations with a Mask R-CNN [36] model with a ResNet50 backbone and feature pyramid networks [49] (Mask R-CNN R50-FPN) implemented in Detectron2. We train the Mask R-CNN model on train2017 for 12 epochs (1× schedule) and report the box detection AP (AP bb ) and instance segmentation AP (AP mk ) on COCO val2017. Similar to VOC detection experiments, BatchNorm layers are fine-tuned and synchronized. We see that OBoW achieves better or comparable results to prior methods despite the fact that it used only 200 pre-training epochs.  . We also provide the projected time for the full training of a method ("Training time"), which is estimated based on the specified number of training epochs ("Epochs"). For OBoW, we used its full implementation. † : for BYOL we provide the time and memory consumption w.r.t. 256-sized mini-batches, but BYOL uses 4096-sized mini-batches to achieve the reported ImageNet classification accuracy. So, in reality BYOL has higher total GPU memory requirements.  Table 9: Results of object detection and instance segmentation on COCO. We report the box detection AP (AP bb ) and instance segmentation AP (AP mk ) on val2017. All methods are pretrained on ImageNet and then fined-tuned on COCO for 12 epochs (1× schedule). We use the ResNet50-based Mask-RCNN model equipped with feature pyramid networks (Mask R-CNN R50-FPN). The "Epochs" and "Batch" columns provide the number of pre-training epochs and the batch size of each model respectively.