Unsupervised Feature Learning via Non-Parametric Instance-level Discrimination

Introduction

The rise of deep neural networks, especially convolutional neural networks (CNN), has led to several breakthroughs in computer vision benchmarks. Most successful models are trained via supervised learning, which requires large datasets that are completely annotated for a specific task. However, obtaining annotated data is often very costly or even infeasible in certain cases. In recent years, unsupervised learning has received increasing attention from the community .

Our novel approach to unsupervised learning stems from a few observations on the results of supervised learning for object recognition. On ImageNet, the top-5 classification error is significantly lower than the top-1 error , and the second highest responding class in the softmax output to an image is more likely to be visually correlated. Fig. 1 shows that an image from class leopard is rated much higher by class jaguar rather than by class bookcase . Such observations reveal that a typical discriminative learning method can automatically discover apparent similarity among semantic categories, without being explicitly guided to do so. In other words, apparent similarity is learned not from semantic annotations, but from the visual data themselves.

We take the class-wise supervision to the extreme of instance-wise supervision, and ask: Can we learn a meaningful metric that reflects apparent similarity among instances via pure discriminative learning? An image is distinctive in its own right, and each could differ significantly from other images in the same semantic category . If we learn to discriminate between individual instances, without any notion of semantic categories, we may end up with a representation that captures apparent similarity among instances, just like how class-wise supervised learning still retains apparent similarity among classes. This formulation of unsupervised learning as an instance-level discrimination is also technically appealing, as it could benefit from latest advances in discriminative supervised learning, e.g. on new network architectures.

However, we also face a major challenge, now that the number of “classes” is the size of the entire training set. For ImageNet, it would be 1.2-million instead of 1,000 classes. Simply extending softmax to many more classes becomes infeasible. We tackle this challenge by approximating the full softmax distribution with noise-contrastive estimation (NCE) , and by resorting to a proximal regularization method to stabilize the learning process.

To evaluate the effectiveness of unsupervised learning, past works such as have relied on a linear classifier, e.g. Support Vector Machine (SVM), to connect the learned feature to categories for classification at the test time. However, it is unclear why features learned via a training task could be linearly separable for an unknown testing task.

We advocate a non-parametric approach for both training and testing. We formulate instance-level discrimination as a metric learning problem, where distances (similarity) between instances are calculated directly from the features in a non-parametric way. That is, the features for each instance are stored in a discrete memory bank, rather than weights in a network. At the test time, we perform classification using k-nearest neighbors (kNN) based on the learned metric. Our training and testing are thus consistent, since both learning and evaluation of our model are concerned with the same metric space between images. We report and compare experimental results with both SVM and kNN accuracies.

Our experimental results demonstrate that, under unsupervised learning settings, our method surpasses the state-of-the-art on image classification by a large margin, with top-1 accuracy $46.5\%$ on ImageNet 1K and $41.6\%$ for Places 205 . Our method is also remarkable for consistently improving test performance with more training data and better network architectures. By fine-tuning the learned feature, we further obtain competitive results for semi-supervised learning and object detection tasks. Finally, our non-parametric model is highly compact: With $128$ features per image, our method requires only $600$MB storage for a million images, enabling fast nearest neighbour retrieval at the run time.

Related Works

There has been growing interest in unsupervised learning without human-provided labels. Previous works mainly fall into two categories: 1) generative models and 2) self-supervised approaches.

Generative Models. The primary objective of generative models is to reconstruct the distribution of data as faithfully as possible. Classical generative models include Restricted Bolztmann Machines (RBMs) , and Auto-encoders . The latent features produced by generative models could also help object recognition. Recent approaches such as generative adversarial networks and variational auto-encoder improve both generative qualities and feature learning.

Self-supervised Learning. Self-supervised learning exploits internal structures of data and formulates predictive tasks to train a model. Specifically, the model needs to predict either an omitted aspect or component of an instance given the rest. To learn a representation of images, the tasks could be: predicting the context , counting the objects , filling in missing parts of an image , recovering colors from grayscale images , or even solving a jigsaw puzzle . For videos, self-supervision strategies include: leveraging temporal continuity via tracking , predicting future , or preserving the equivariance of egomotion . Recent work attempts to combine several self-supervised tasks to obtain better visual representations. Whereas self-supervised learning may capture relations among parts or aspects of an instance, it is unclear why a particular self supervision task should help semantic recognition and which task would be optimal.

Metric Learning. Every feature representation $F$ induces a metric between instances $x$ and $y$: $d_{F}(x,y)=\|F(x)-F(y)\|$. Feature learning can thus also be viewed as a certain form of metric learning. There have been extensive studies on metric learning . Successful application of metric learning can often result in competitive performance, e.g. on face recognition and person re-identification . In these tasks, the classes at the test time are disjoint from those at the training time. Once a network is trained, one can only infer from its feature representation, not from the subsequent linear classifier. Metric learning has been shown to be effective for few-shot learning . An important technical point on metric learning for face recognition is normalization , which we also utilize in this work. Note that all the methods mentioned here require supervision in certain ways. Our work is drastically different: It learns the feature and thus the induced metric in an unsupervised fashion, without any human annotations.

Exemplar CNN. Exemplar CNN appears similar to our work. The fundamental difference is that it adopts a parametric paradigm during both training and testing, while our method is non-parametric in nature. We study this essential difference experimentally in Sec 4.1. Exemplar CNN is computationally demanding for large-scale datasets such as ImageNet.

Approach

Our goal is to learn an embedding function $\mathbf{v}=f_{\boldsymbol{\theta}}(x)$ without supervision. $f_{\boldsymbol{\theta}}$ is a deep neural network with parameters $\boldsymbol{\theta}$, mapping image $x$ to feature $\mathbf{v}$. This embedding would induces a metric over the image space, as $d_{\boldsymbol{\theta}}(x,y)=\|f_{\boldsymbol{\theta}}(x)-f_{\boldsymbol{\theta}}(y)\|$ for instances $x$ and $y$. A good embedding should map visually similar images closer to each other.

Our novel unsupervised feature learning approach is instance-level discrimination. We treat each image instance as a distinct class of its own and train a classifier to distinguish between individual instance classes (Fig.2).

Parametric Classifier. We formulate the instance-level classification objective using the softmax criterion. Suppose we have $n$ images $x_{1},\ldots,x_{n}$ in $n$ classes and their features $\mathbf{v}_{1},\ldots,\mathbf{v}_{n}$ with $\mathbf{v}_{i}=f_{\boldsymbol{\theta}}(x_{i})$. Under the conventional parametric softmax formulation, for image $x$ with feature $\mathbf{v}=f_{\boldsymbol{\theta}}(x)$, the probability of it being recognized as $i$-th example is

where $\mathbf{w}_{j}$ is a weight vector for class $j$, and $\mathbf{w}_{j}^{T}\mathbf{v}$ measures how well $\mathbf{v}$ matches the $j$-th class i.e., instance.

Non-Parametric Classifier. The problem with the parametric softmax formulation in Eq. (1) is that the weight vector $\mathbf{w}$ serves as a class prototype, preventing explicit comparisons between instances.

We propose a non-parametric variant of Eq. (1) that replaces $\mathbf{w}_{j}^{T}\mathbf{v}$ with $\mathbf{v}_{j}^{T}\mathbf{v}$, and we enforce $\|\mathbf{v}\|=1$ via a L2-normalization layer. Then the probability $P(i|\mathbf{v})$ becomes:

where $\tau$ is a temperature parameter that controls the concentration level of the distribution . $\tau$ is important for supervised feature learning , and also necessary for tuning the concentration of $\mathbf{v}$ on our unit sphere.

The learning objective is then to maximize the joint probability $\prod_{i=1}^{n}P_{\boldsymbol{\theta}}(i|f_{\boldsymbol{\theta}}(x_{i}))$, or equivalently to minimize the negative log-likelihood over the training set, as

Learning with A Memory Bank. To compute the probability $P(i|\mathbf{v})$ in Eq. (2), $\{\mathbf{v}_{j}\}$ for all the images are needed. Instead of exhaustively computing these representations every time, we maintain a feature memory bank $V$ for storing them . In the following, we introduce separate notations for the memory bank and features forwarded from the network. Let $V=\{\mathbf{v}_{j}\}$ be the memory bank and $\mathbf{f}_{i}=f_{\boldsymbol{\theta}}(x_{i})$ be the feature of $x_{i}$. During each learning iteration, the representation $\mathbf{f}_{i}$ as well as the network parameters $\theta$ are optimized via stochastic gradient descend. Then $\mathbf{f}_{i}$ is updated to $V$ at the corresponding instance entry $\mathbf{f}_{i}\to\mathbf{v}_{i}$. We initialize all the representations in the memory bank $V$ as unit random vectors.

Discussions. The conceptual change from class weight vector $\mathbf{w}_{j}$ to feature representation $\mathbf{v}_{j}$ directly is significant. The weight vectors $\{\mathbf{w}_{j}\}$ in the original softmax formulation are only valid for training classes. Consequently, they are not generalized to new classes, or in our setting, new instances. When we get rid of these weight vectors, our learning objective focuses entirely on the feature representation and its induced metric, which can be applied everywhere in the space and to any new instances at the test time.

Computationally, our non-parametric formulation eliminates the need for computing and storing the gradients for $\{\mathbf{w}_{j}\}$, making it more scalable for big data applications.

2 Noise-Contrastive Estimation

Computing the non-parametric softmax in Eq.(2) is cost prohibitive when the number of classes $n$ is very large, e.g. at the scale of millions. Similar problems have been well addressed in the literature for learning word embeddings , where the number of words can also scale to millions. Popular techniques to reduce computation include hierarchical softmax , noise-contrastive estimation (NCE) , and negative sampling . We use NCE to approximate the full softmax.

We adapt NCE to our problem, in order to tackle the difficulty of computing the similarity to all the instances in the training set. The basic idea is to cast the multi-class classification problem into a set of binary classification problems, where the binary classification task is to discriminate between data samples and noise samples. Specifically, the probability that feature representation $\mathbf{v}$ in the memory bank corresponds to the $i$-th example under our model is,

where $Z_{i}$ is the normalizing constant. We formalize the noise distribution as a uniform distribution: $P_{n}=1/n$. Following prior work, we assume that noise samples are $m$ times more frequent than data samples. Then the posterior probability of sample $i$ with feature $\mathbf{v}$ being from the data distribution (denoted by $D=1$) is:

Our approximated training objective is to minimize the negative log-posterior distribution of data and noise samples,

Here, $P_{d}$ denotes the actual data distribution. For $P_{d}$, $\mathbf{v}$ is the feature corresponding to $x_{i}$; whereas for $P_{n}$, $\mathbf{v}^{\prime}$ is the feature from another image, randomly sampled according to noise distribution $P_{n}$. In our model, both $\mathbf{v}$ and $\mathbf{v}^{\prime}$ are sampled from the non-parametric memory bank $V$.

Computing normalizing constant $Z_{i}$ according to Eq. (4) is expensive. We follow , treating it as a constant and estimating its value via Monte Carlo approximation:

where $\{j_{k}\}$ is a random subset of indices. Empirically, we find the approximation derived from initial batches sufficient to work well in practice.

NCE reduces the computational complexity from $O(n)$ to $O(1)$ per sample. With such drastic reduction, our experiments still yield competitive performance.

3 Proximal Regularization

Unlike typical classification settings where each class has many instances, we only have one instance per class. During each training epoch, each class is only visited once. Therefore, the learning process oscillates a lot from random sampling fluctuation. We employ the proximal optimization method and introduce an additional term to encourage the smoothness of the training dynamics. At current iteration $t$, the feature representation for data $x_{i}$ is computed from the network $\mathbf{v}_{i}^{(t)}=f_{\boldsymbol{\theta}}(x_{i})$. The memory bank of all the representation are stored at previous iteration $V=\{\mathbf{v}^{(t-1)}\}$. The loss function for a positive sample from $P_{d}$ is:

As learning converges, the difference between iterations, i.e. $\mathbf{v}_{i}^{(t)}-\mathbf{v}_{i}^{(t-1)}$, gradually vanishes, and the augmented loss is reduced to the original one. With proximal regularization, our final objective becomes:

Fig. 3 shows that, empirically, proximal regularization helps stabilize training, speed up convergence, and improve the learned representation, with negligible extra cost.

4 Weighted k-Nearest Neighbor Classifier

To classify test image $\hat{x}$, we first compute its feature $\hat{\mathbf{f}}=f_{\boldsymbol{\theta}}(\hat{x})$, and then compare it against the embeddings of all the images in the memory bank, using the cosine similarity $s_{i}=\cos(\mathbf{v}_{i},\hat{\mathbf{f}})$. The top $k$ nearest neighbors, denoted by $\mathcal{N}_{k}$, would then be used to make the prediction via weighted voting. Specifically, the class $c$ would get a total weight $w_{c}=\sum_{i\in\mathcal{N}_{k}}\alpha_{i}\cdot 1(c_{i}=c)$. Here, $\alpha_{i}$ is the contributing weight of neighbor $x_{i}$, which depends on the similarity as $\alpha_{i}=\exp(s_{i}/\tau)$. We choose $\tau=0.07$ as in training and we set $k=200$.

Experiments

We conduct 4 sets of experiments to evaluate our approach. The first set is on CIFAR-10 to compare our non-parametric softmax with parametric softmax. The second set is on ImageNet to compare our method with other unsupervised learning methods. The last two sets of experiments investigate two different tasks, semi-supervised learning and object detection, to show the generalization ability of our learned feature representation.

A key novelty of our approach is the non-parametric softmax function. Compared to the conventional parametric softmax, our softmax allows a non-parametric metric to transfer to supervised tasks.

We compare both parametric and non-parametric formulations on CIFAR-10 , a dataset with $50,000$ training instances in $10$ classes. This size allows us to compute the non-parametric softmax in Eq.(2) without any approximation. We use ResNet18 as the backbone network and its output features mapped into $128$-dimensional vectors.

We evaluate the classification effectiveness based on the learned feature representation. A common practice is to train an SVM on the learned feature over the training set, and to then classify test instances based on the feature extracted from the trained network. In addition, we also use nearest neighbor classifiers to assess the learned feature. The latter directly relies on the feature metric and may better reflect the quality of the representation.

Table 1 shows top-1 classification accuracy on CIFAR10. On the features learned with parametric softmax, we obtain accuracy of $60.3\%$ and $63.0\%$ with linear SVM and kNN classifiers respectively. On the features learned with non-parametric softmax, the accuracy rises to $75.4\%$ and $80.8\%$ for the linear and nearest neighbour classifiers, a remarkable $18\%$ boost for the latter.

We also study the quality of NCE approximating non-parametric softmax (Sec. 3.2). The approximation is controlled by $m$, the number of negatives drawn for each instance. With $m=1$, the accuracy with kNN drops significantly to $42.5\%$. As $m$ increases, the performance improves steadily. When $m=4,096$, the accuracy approaches that at $m=49,999$ – full form evaluation without any approximation. This result provides assurance that NCE is an efficient approximation.

2 Image Classification

We learn a feature representation on ImageNet ILSVRC , and compare our method with representative unsupervised learning methods.

We choose design parameters via empirical validation. In particular, we set temperature $\tau=0.07$ and use NCE with $m=4,096$ to balance performance and computing cost. The model is trained for $200$ epochs using SGD with momentum. The batch size is 256. The learning rate is initialized to $0.03$, scaled down with coefficient $0.1$ every 40 epochs after the first $120$ epochs. Our code is available at: http://github.com/zhirongw/lemniscate.pytorch.

Comparisons.

We compare our method with a randomly initialized network (as a lower bound) and various unsupervised learning methods, including self-supervised learning , adversarial learning , and Exemplar CNN . The split-brain autoencoder serves a strong baseline that represents the state of the art. The results of these methods are reported with AlexNet architecture in their original papers, except for exemplar CNN , whose results are reported with ResNet-101 . As the network architecture has a big impact on the performance, we consider a few typical architectures: AlexNet , VGG16 , ResNet-18, and ResNet-50 .

We evaluate the performance with two different protocols: (1) Perform linear SVM on the intermediate features from conv1 to conv5. Note that there are also corresponding layers in VGG16 and ResNet . (2) Perform kNN on the output features. Table 2 shows that:

With AlexNet and linear classification on intermediate features, our method achieves an accuracy of $35.6\%$, outperforming all baselines, including the state-of-the-art. Our method can readily scale up to deeper networks. As we move from AlexNet to ResNet-50, our accuracy is raised to $54.0\%$, whereas the accuracy with exemplar CNN is only $31.5\%$ even with ResNet-101.

Using nearest neighbor classification on the final 128 dimensional features, our method achieves $31.3\%$, $33.9\%$, $41.0\%$ and $46.5\%$ accuracies with AlexNet, VGG16, ResNet-18 and ResNet-50, not much lower than the linear classification results, demonstrating that our learned feature induces a reasonably good metric. As a comparison, for Split-brain, the accuracy drops to $8.9\%$ with nearest neighbor classification on conv3 features, and to $11.8\%$ after projecting the features to 128 dimensions.

With our method, the performance gradually increases as we examine the learned feature representation from earlier to later layers, which is generally desirable. With all other methods, the performance decreases beyond conv3 or conv4.

It is important to note that the features from intermediate convolutional layers can be over $10,000$ dimensions. Hence, for other methods, using the features from the best-performing layers can incur significant storage and computation costs. Our method produces a $128$-dimensional representation at the last layer, which is very efficient to work with. The encoded features of all $1.28M$ images in ImageNet only take about $600$ MB of storage. Exhaustive nearest neighbor search over this dataset only takes $20$ ms per image on a Titan X GPU.

Feature generalization.

We also study how the learned feature representations can generalize to other datasets. With the same settings, we conduct another large-scale experiment on Places , a large dataset for scene classification, which contains $2.45M$ training images in $205$ categories. In this experiment, we directly use the feature extraction networks trained on ImageNet without finetuning. Table 3 compares the results obtained with different methods and under different evaluation policies. Again, with linear classifier on conv5 features, our method achieves competitive performance of top-1 accuracy $34.5\%$ with AlexNet, and $45.5\%$ with ResNet-50. With nearest neighbors on the last layer which is much smaller than intermediate layers, we achieve an accuracy of $41.6\%$ with ResNet-50. These results show remarkable generalization ability of the representations learned using our method.

Consistency of training and testing objectives.

Unsupervised feature learning is difficult because the training objective is agnostic about the testing objective. A good training objective should be reflected in consistent improvement in the testing performance. We investigate the relation between the training loss and the testing accuracy across iterations. Fig. 4 shows that our testing accuracy continues to improve as training proceeds, with no sign of overfitting. It also suggests that better optimization of the training objective may further improve our testing accuracy.

The embedding feature size.

We study how the performance changes as we vary the embedding size from 32 to 256. Table 4 shows that the performance increases from 32, plateaus at 128, and appears to saturate towards 256.

Training set size.

To study how our method scales with the data size, we train different representations with various proportions of ImageNet data, and evaluate the classification performance on the full labeled set using nearest neighbors. Table 5 shows that our feature learning method benefits from larger training sets, and the testing accuracy improves as the training set grows. This property is crucial for successful unsupervised learning, as there is no shortage of unlabeled data in the wild.

Qualitative case study.

To illustrate the learned features, Figure 5 shows the results of image retrieval using the learned features. The upper four rows show the best cases where all top 10 results are in the same categories as the queries. The lower four rows show the worst cases where none of the top 10 are in the same categories. However, even for the failure cases, the retrieved images are still visually similar to the queries, a testament to the power of our unsupervised learning objective.

3 Semi-supervised Learning

We now study how the learned feature extraction network can benefit other tasks, and whether it can provide a good basis for transfer learning to other tasks. A common scenario that can benefit from unsupervised learning is when we have a large amount of data of which only a small fraction are labeled. A natural semi-supervised learning approach is to first learn from the big unlabeled data and then fine-tune the model on the small labeled data.

We randomly choose a subset of ImageNet as labeled and treat others as unlabeled. We perform the above semi-supervised learning and measure the classification accuracy on the validation set. In order to compare with , we report the top-5 accuracy here.

We compare our method with three baselines: (1) Scratch, i.e. fully supervised training on the small labeled subsets, (2) Split-brain for pre-training, and (3) Colorization for pre-training. Finetuning on the labeled subset takes $70$ epochs with initial learning rate $0.01$ and a decay rate of 10 every 30 epochs. We vary the proportion of labeled subset from $1\%$ to $20\%$ of the entire dataset.

Fig. 6 shows that our method significantly outperforms all other approaches, and ours is the only one outperforming supervised learning from limited labeled data. When only $1\%$ of data is labeled, we outperform by a large $10\%$ margin, demonstrating that our feature learned from unlabeled data is effective for task adaptation.

4 Object Detection

To further assess the generalization capacity of the learned features, we transfer the learned networks to the new task of object detection on PASCAL VOC 2007 . Training object detection model from scratch is often difficult, and a prevalent practice is to pretrain the underlying CNN on ImageNet and fine-tune it for the detection task.

We experiment with Fast R-CNN with AlexNet and VGG16 architectures, and Faster R-CNN with ResNet-50. When fine-tuning Fast R-CNN, the learning rate is initialized to $0.001$ and scaled down by $10$ times after every $50K$ iterations. When fine-tuning AlexNet and VGG16, we follow the standard practice, fixing the conv1 model weights. When fine-tuning Faster R-CNN, we fix the model weights below the 3rd type of residual blocks, only updating the layers above and freezing all batch normalization layers. We follow the standard pipeline for finetuning and do not use the rescaling method proposed in . We use the standard trainval set in VOC 2007 for training and testing.

We compare three settings: 1) directly training from scratch (lower bound), 2) pretraining on ImageNet in a supervised way (upper bound), and 3) pretraining on ImageNet or other data using various unsupervised methods.

Table 6 lists detection performance in terms of mean average precision (mAP). With AlexNet and VGG16, our method achieves an mAP of $48.1\%$ and $60.5\%$, on par with the state-of-the-art unsupervised methods. With Resnet-50, our method achieves an mAP of $65.4\%$, surpassing all existing unsupervised learning approaches. It also shows that our method scales well as the network gets deeper. There remains a significant gap of $11\%$ to be narrowed towards mAP $76.2\%$ from supervised pretraining.

Summary

We present an unsupervised feature learning approach by maximizing distinction between instances via a novel non-parametric softmax formulation. It is motivated by the observation that supervised learning results in apparent image similarity. Our experimental results show that our method outperforms the state-of-the-art on image classification on ImageNet and Places, with a compact $128$-dimensional representation that scales well with more data and deeper networks. It also delivers competitive generalization results on semi-supervised learning and object detection tasks.

Acknowledgements. This work was supported in part by Berkeley Deep Drive, Big Data Collaboration Research grant from SenseTime Group (CUHK Agreement No. TS1610626), and the General Research Fund (GRF) of Hong Kong (No. 14236516).

References