Back to paper library
arXiv 2018CVPR 2018Contrastive learningPaper notes

InstDisc

More is better

Original paper

Unsupervised Feature Learning via Non-Parametric Instance-level Discrimination

Paper authors

Zhirong Wu · Yuanjun Xiong · Stella Yu · Dahua Lin

Publication
CVPR 2018Conference
First submitted to arXiv
arXiv:1805.01978
Cite this paper · BibTeX

The citation identifies the linked source version. It cites the original paper and its authors.

@misc{contrastivelearninginstdisc2018,
  title = {{Unsupervised Feature Learning via Non-Parametric Instance-level Discrimination}},
  author = {Zhirong Wu and Yuanjun Xiong and Stella Yu and Dahua Lin},
  year = {2018},
  eprint = {1805.01978},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1805.01978}
}
On this page

Seizing a break in development, I quickly dive into some papers related to contrastive learning.

Although I’ve already listened to the master class before, reading through it myself feels more solid.

Before the concept of contrastive learning became popular, metric learning had already been widely used in the industry. The most well-known application is face recognition, with no exceptions.

The core of metric learning lies in learning feature representations FF, which establish a measure between samples xx and yy:

dF(x,y)=∥F(x)−F(y)∥d_F(x, y)=\|F(x)-F(y)\|

For open-set identity matching, inference usually compares learned embeddings rather than relying on the training identities’ classifier. A linear classifier can still be trained on these features for an appropriate downstream task.

Defining the Problem

The supervised metric-learning examples above rely on identity or class labels.

With only unlabeled data, we need another signal for learning similarity. Metric learning itself is not restricted to supervised methods.

Thus, researchers have come up with various solutions:

Generative Models

Another route is to learn how to generate or reconstruct data. Autoencoders and VAEs use encoders and decoders; GANs train a generator against a discriminator and need not include an image-encoding and reconstruction path.

The advantage is that no labels are required; as long as images are available, training can begin. However, the downside is the high computational cost. As the resolution of the reconstructed image increases, the computational cost also increases.

Generation or reconstruction quality and recognition-feature quality require separate evaluation. Some GAN training can also suffer mode collapse. These limitations depend on the model, objective, and data.

Self-Supervised Structural Learning

Self-supervised learning leverages the internal structure of the data to create a prediction task and then trains the model.

Let’s look at some interesting examples:


After seeing so many proxy tasks, they all seem reasonable, but their usefulness for semantic recognition and the choice of task still need experimental justification.

Since there’s no consensus, let’s create one. Inspired by metric learning, the authors propose a novel feature learning training method, aiming to work without artificial labels.

Solving the Problem

To obtain a "good" feature representation, the authors adopt an "instance-level discrimination" strategy: treating each image as an independent "class" and training a classifier to determine whether each image belongs to its own "class."

Let’s take a look at the model architecture.

Model Architecture

As shown in the diagram above, on the left is a deep convolutional neural network labeled "Backbone CNN." Its function is to transform the input image xx (e.g., a 224×\times224 image) into higher-level semantic features. For common CNN networks, this might involve several layers of convolution, batch normalization, pooling, and other operations. The final layer typically outputs a high-dimensional vector, which serves as the "visual feature representation."

The high-level features output from the Backbone CNN are usually still of large dimensionality (e.g., 2048 dimensions). To run efficiently with large datasets, more compressed and abstract feature descriptions are needed, so the authors add a "Projection Head" to project the CNN output vector into a 128-dimensional vector space.

After projection, the 128-dimensional vector is then subjected to L2 Normalization (∥v∥2=1\|\mathbf{v}\|_2 = 1), which means each sample is constrained to unit length. This is especially useful when computing similarity because, at this point, the dot product viTvj\mathbf{v}_i^T \mathbf{v}_j represents the cosine of the angle between the two vectors on the hypersphere, with values ranging from [−1,1][-1, 1]. This makes the calculation more intuitive and stable.

The Problem with Traditional Classifiers

In traditional Softmax classification models, each class jj corresponds to a weight vector wj\mathbf{w}_j. Suppose we have nn images (equivalent to nn "classes"), with corresponding weight vectors w1,w2,…,wn\mathbf{w}_1, \mathbf{w}_2, \dots, \mathbf{w}_n. For a given image xx, the feature vector produced by the neural network is v=fθ(x)\mathbf{v} = f_\theta(x). The conditional probability of the image being classified as the ii-th image (i.e., the ii-th "class") can be written as:

P(i∣v)  =  exp⁡(wiTv)∑j=1nexp⁡(wjTv)P(i \mid \mathbf{v}) \;=\; \frac{\exp(\mathbf{w}_i^T \mathbf{v})}{\sum_{j=1}^{n} \exp(\mathbf{w}_j^T \mathbf{v})}

In this equation, wiTv\mathbf{w}_i^T \mathbf{v} is used to measure the alignment between the feature v\mathbf{v} and class ii; the denominator is the sum of the exponentiated values of all class comparisons (from 1 to nn), ensuring that the total probability across all classes sums to 1.

In typical classification problems, the number of classes is fixed and not too large, so this parameterized Softmax is commonly used. However, here, since "each image" is treated as a new class, the number of classes can be enormous (tens of thousands, millions, or more). As a result, each class requires an independent weight vector wj\mathbf{w}_j, which not only requires significant storage space but also results in high computational costs.

Simply put, it becomes too computationally expensive.

Non-Parametric Classifier

To address the above problem, the authors propose a "non-parametric" approach:

  • Replace the formula's wj\mathbf{w}_j with the feature vector vj\mathbf{v}_j stored in a memory bank.

In other words, the "class weight" for the jj-th image is no longer an independent wj\mathbf{w}_j, but instead, it directly uses the feature vector vj\mathbf{v}_j of the jj-th image itself. Additionally, the authors enforce normalization of these feature vectors to unit vectors (i.e., length 1) for ease of similarity calculation.

Thus, the Softmax formula can be rewritten as:

P(i∣v)=exp⁡ ⁣(viTv/τ)∑j=1nexp⁡ ⁣(vjTv/τ)P(i \mid \mathbf{v}) = \frac{\exp\!\bigl(\mathbf{v}_i^T \mathbf{v} / \tau\bigr)}{\sum_{j=1}^{n} \exp\!\bigl(\mathbf{v}_j^T \mathbf{v} / \tau\bigr)}

Here, τ\tau is the "temperature parameter," which can adjust the "sharpness" of the Softmax distribution; v\mathbf{v} is the feature vector of the current image xx produced by forward propagation; vi\mathbf{v}_i is the feature vector of the ii-th image stored in the "memory bank" (also a unit vector), and viTv\mathbf{v}_i^T \mathbf{v} is the dot product of the two unit vectors, ranging from -1 to 1, which represents their similarity.

Memory Bank

The training objective for the non-parametric softmax is similar to that of typical classification problems: to maximize the probability of each training image being "correctly identified as itself," or equivalently, to minimize the negative log-likelihood over the entire training set:

J(θ)=−∑i=1nlog⁡P(i∣fθ(xi))J(\theta) = - \sum_{i=1}^{n} \log P\bigl(i \mid f_\theta(x_i)\bigr)

Here, fθ(xi)f_\theta(x_i) is denoted as fi\mathbf{f}_i. When computing P(i∣fi)P(i \mid \mathbf{f}_i), theoretically, the features of all images {vj}\{\mathbf{v}_j\} are needed. However, if every backpropagation requires passing all images through the neural network, the computational cost would be very high.

Thus, in practice, the authors maintain a "Memory Bank" (V={vj}\mathbf{V} = \{\mathbf{v}_j\}) holding each image's most recently computed feature. It starts with random unit vectors, and after each training iteration, the entries for the images in that iteration are updated using their current forward-pass features fi\mathbf{f}_i.

Since each image has a corresponding position in memory, the previous features can be quickly retrieved to reduce computational cost when dealing with large datasets. If the total number of images nn is large, calculating the denominator ∑j=1nexp⁡(vjTv/τ)\sum_{j=1}^{n} \exp(\mathbf{v}_j^T \mathbf{v} / \tau) would be prohibitively expensive. For every image, this computation would be O(n)O(n), and when nn reaches millions or more, it becomes almost unmanageable.

Noise-Contrastive Estimation

The core idea of NCE is:

  1. Transform a multi-class classification problem into multiple binary classification problems.
  2. The goal of the binary classification: distinguish between "real data samples" and "noise samples."

In the multi-class scenario, each image is treated as a "class." With NCE, for a given image, we only need to distinguish "whether it is this image" versus "not this image (noise)."

The approach is to treat "other images" as noise, or sample negative examples from a noise distribution (PnP_n), and let the model learn to differentiate between positive and negative examples.

For example, to calculate the "probability that feature v\mathbf{v} comes from the ii-th image," we can write:

P(i∣v)=exp⁡(vTfi/τ)ZiP(i \mid \mathbf{v}) = \frac{\exp(\mathbf{v}^T \mathbf{f}_i/\tau)}{Z_i}

Where:

Zi=∑j=1nexp⁡(vjTfi/τ)Z_i = \sum_{j=1}^n \exp\bigl(\mathbf{v}_j^T \mathbf{f}_i/\tau\bigr)
  • fi\mathbf{f}_i is the current forward-pass feature of image xix_i; v\mathbf{v} is a candidate feature retrieved from the memory bank.
  • ZiZ_i is the normalization constant: with fi\mathbf{f}_i fixed, it makes probabilities over the candidate memory features vj\mathbf{v}_j sum to one. The paper's notation P(i∣v)P(i\mid\mathbf{v}) uses v\mathbf{v} differently from the preceding softmax section.
  • Computing all nn terms is costly for a large dataset.

The cleverness of NCE is that, in the case of "a large number of possible classes," it does not directly compute the full denominator of the formula. Instead, it separates the "positive sample" corresponding to the "class ii" and the "negative sample" corresponding to the "noise distribution."

Let the noise distribution PnP_n be uniform (Pn(i)=1nP_n(i) = \frac{1}{n}).

The paper introduces a hyperparameter mm, which represents that "there are mm times more noise samples than real samples," and then defines a "posterior probability":

h(i,v):=P(D=1∣i,v)=P(i∣v)P(i∣v)+mPn(i)h(i, \mathbf{v}) := P(D=1 \mid i, \mathbf{v})= \frac{P(i \mid \mathbf{v})}{P(i \mid \mathbf{v}) + m P_n(i)}

The meaning of h(⋅)h(\cdot) is that, given feature v\mathbf{v} and class ii, it is the probability that "v\mathbf{v} comes from the ii-th image (real data), rather than from noise." P(i∣v)P(i \mid \mathbf{v}) is the output of the above formula, and mPn(i)m P_n(i) is the relative probability of selecting a noise sample corresponding to class ii.

The next key point is:

  1. Take the negative log-likelihood for positive samples (positive samples are correctly classified as positive).
  2. Take the negative log-likelihood for negative samples (negative samples are correctly classified as negative).

Thus, we have:

JNCE(θ)=−EPd[log⁡h(i,v)]  −  m EPn[log⁡(1−h(i,v′))]J_{\text{NCE}}(\theta) = - \mathbb{E}_{P_d}\bigl[\log h(i, \mathbf{v})\bigr] \;-\; m \,\mathbb{E}_{P_n}\bigl[\log \bigl(1 - h(i, \mathbf{v}')\bigr)\bigr]
  • Where PdP_d represents the "real data distribution," i.e., the actual images (positive examples).
  • PnP_n represents the "noise distribution," i.e., the noise samples (negative examples).
  • v\mathbf{v} and v′\mathbf{v}' are feature vectors retrieved from the Memory Bank (V\mathbf{V}); one corresponds to the "positive sample" (xix_i), and the other is a randomly selected noise sample.

Intuitively, a larger log⁡h(i,v)\log h(i, \mathbf{v}) means the model is more confident that "v\mathbf{v} belongs to the ii-th image" (good); whereas a larger log⁡(1−h(⋅))\log(1 - h(\cdot)) means the model correctly rejects the noise.

Approximation of ZiZ_i

Although we have discussed many aspects, the biggest challenge remains unsolved.

We still need to calculate ZiZ_i, which involves ∑j=1nexp⁡(vjTfi/τ)\sum_{j=1}^{n} \exp(\mathbf{v}_j^T \mathbf{f}_i/\tau), and when nn is large, this is still a bottleneck.

A common approach in NCE is to treat ZiZ_i as a "constant" for estimation or approximation, and not involve it in gradient updates. In this paper, the authors refer to the following work:

They use Monte Carlo approximation to estimate:

Z≃Zi≃n Ej∈subset[exp⁡(vjTfi/τ)]=nm∑k=1mexp⁡(vjkTfi/τ)Z \simeq Z_i \simeq n \,\mathbb{E}_{j \in \text{subset}} \bigl[\exp(\mathbf{v}_j^T \mathbf{f}_i / \tau)\bigr] = \frac{n}{m} \sum_{k=1}^{m} \exp\bigl(\mathbf{v}_{j_k}^T \mathbf{f}_i / \tau\bigr)

Here, {jk}\{j_k\} is a set of randomly selected indices used to approximate the average value of the entire set.

Instead of summing all nn terms to calculate ZiZ_i, now we only sample mm negative examples, perform the exponential operation on them, sum them up, and then multiply by the factor nm\frac{n}{m} to approximate the full sum.

The paper also mentions that experimentally, a good estimate can be obtained with just a few batches early in training, and this estimate can be fixed for the remainder of the training, which works well.

Proximal Regularization

Unlike typical classification problems, here each "class" has only one training sample. Each class is visited just once per epoch, and the authors observe that the original training objective oscillates more and converges slowly.

To mitigate this instability caused by random sampling, the authors introduce Proximal Regularization. A smoothness constraint penalizes a large change from the image's stored feature at its last update. This helps stabilize training and accelerate convergence.

Specifically, we assume two variables:

  • Current iteration (iteration tt): For training data xix_i, compute the feature vector vi(t)=fθ(xi)\mathbf{v}_i^{(t)} = f_\theta(x_i).
  • Memory Bank: Stores the feature from the last time this image was encountered, denoted here as vi(t−1)\mathbf{v}_i^{(t-1)}; this need not be the immediately preceding global training iteration.

In the original NCE loss, an additional term λ∥vi(t)−vi(t−1)∥2\lambda \|\mathbf{v}_i^{(t)} - \mathbf{v}_i^{(t-1)}\|^2 is added.

Thus, the objective function becomes:

−log⁡h(i,vi(t−1))  +  λ ∥vi(t)−vi(t−1)∥22- \log h\bigl(i, \mathbf{v}_i^{(t-1)}\bigr) \;+\; \lambda \,\bigl\|\mathbf{v}_i^{(t)} - \mathbf{v}_i^{(t-1)}\bigr\|_2^2
  • The first term (−log⁡h(i,vi(t−1))- \log h(i, \mathbf{v}_i^{(t-1)})) is the original positive example loss in NCE.
  • The second term (λ∥vi(t)−vi(t−1)∥2\lambda \|\mathbf{v}_i^{(t)} - \mathbf{v}_i^{(t-1)}\|^2) keeps the new feature vi(t)\mathbf{v}_i^{(t)} close to that image's previously stored feature vi(t−1)\mathbf{v}_i^{(t-1)}.

Through this proximal term, if the feature vector changes too drastically during each update, it will be penalized. As training progresses and the model converges, the ideal scenario is vi(t)≈vi(t−1)\mathbf{v}_i^{(t)} \approx \mathbf{v}_i^{(t-1)}, and the penalty term gradually diminishes, eventually returning to the original objective function.

After incorporating this, the authors present the final objective function with Proximal Regularization:

JNCE(θ)J_{\text{NCE}}(\theta) =−EPd[log⁡h(i,vi(t−1))  −  λ ∥vi(t)−vi(t−1)∥2]  −  m EPn[log⁡(1−h(i,v′(t−1)))].= - \mathbb{E}_{P_d} \Bigl[ \log h\bigl(i, \mathbf{v}_i^{(t-1)}\bigr) \;-\; \lambda \,\bigl\|\mathbf{v}_i^{(t)} - \mathbf{v}_i^{(t-1)}\bigr\|^2 \Bigr] \;-\; m \,\mathbb{E}_{P_n} \Bigl[ \log\bigl(1 - h\bigl(i, \mathbf{v}'^{(t-1)}\bigr)\bigr) \Bigr].

This version retains the original NCE components for "positive example log⁡h(⋅)\log h(\cdot)" and "negative example log⁡(1−h(⋅))\log(1 - h(\cdot))" while adding the term −λ∥vi(t)−vi(t−1)∥2- \lambda \|\mathbf{v}_i^{(t)} - \mathbf{v}_i^{(t-1)}\|^2 to suppress drastic changes in feature vectors.

To verify the effectiveness of Proximal Regularization, the authors compare the impact of different λ\lambda values (such as 0, 10, 30, 50) on training:

As shown in the figure above, when λ=0\lambda = 0 (i.e., no proximal term), the training loss oscillates more and falls more slowly. With an appropriately sized λ\lambda, its curve is smoother. The authors also report better learned features.

At test time, the authors find the k=200k=200 nearest neighbors by cosine similarity in the feature space. They predict a class by weighting each neighbor's vote with exp⁡(si/τ)\exp(s_i/\tau), using τ=0.07\tau=0.07 as in training.

Discussion

Parametric vs Non-Parametric Softmax

Since the core of this paper is the "non-parametric Softmax," the authors first conducted an experiment on CIFAR-10 to compare the performance of "parametric Softmax" and "non-parametric Softmax."

Since the CIFAR-10 dataset is relatively small, the non-parametric Softmax denominator can be directly computed, allowing a direct comparison of the two approaches. The evaluation methods used were Linear SVM and k-NN classifiers, applied to "parametric" and "non-parametric" features, and their accuracy rates were compared.

The results, shown in the table above, reveal that the parametric Softmax achieved accuracy rates of 60.3% for SVM and 63.0% for k-NN, while the non-parametric Softmax achieved 75.4% and 80.8%, respectively. This demonstrates a significant improvement in performance with the non-parametric Softmax, validating the authors' approach.

Additionally, the authors explored the effects of using NCE approximation in the non-parametric setting, as shown in the table. The hyperparameter mm in NCE indicates how many negative samples are drawn for each positive sample:

  • When m=1m = 1 (only 1 negative sample), the k-NN accuracy dropped drastically to 42.5%, indicating excessive approximation (too few negative examples).
  • As mm increases, k-NN accuracy rises from 42.5% to 80.4% at m=4,096m = 4,096, close to the full non-parametric Softmax's 80.8%. The same row's linear SVM result, 70.2%, is still below the full version's 75.4%. The m=49,999m = 49,999 mentioned in the prose means comparing with all the other CIFAR-10 training images, not an additional row in this table.

Performance in Image Classification Tasks

The authors then conducted larger-scale experiments on ImageNet to compare the performance of different methods across various network architectures.

The experimental setup was as follows:

  • Dataset: ImageNet, approximately 1.28 million images, 1,000 categories.
  • Temperature parameter τ\tau: Set to 0.07.
  • NCE negative samples mm: 4,096. The authors balanced "computational cost" and "feature quality."
  • Training:
    • Trained for 200 epochs using Momentum SGD.
    • Batch size = 256.
    • Initial learning rate of 0.03, maintained for the first 120 epochs, then decayed every 40 epochs by a factor of 0.1.

The authors listed several representative unsupervised (or self-supervised) learning methods, including:

  • Random initialization (random initialization, as a lower bound).
  • Self-supervised
  • Adversarial learning
  • Exemplar CNN
  • Split-brain autoencoder: One of the recent self-supervised benchmark methods.

The authors used several backbones—AlexNet, VGG16, ResNet-18, and ResNet-50—to see how their method changes with architecture. Most other methods in the table come from separate papers, with different backbones or evaluation settings.

The evaluation methods were as follows:

  1. Linear SVM (conv1 ~ conv5): Trained a linear classifier on the intermediate features from different convolutional layers (such as conv1, conv2, conv3, ...) and tested the classification performance on the ImageNet validation set.
  2. k-NN (final 128-dimensional output): Directly applied nearest neighbor classification on the final 128-dimensional feature output.

The experimental results are shown in the table below:

With AlexNet, their conv5 features reach 35.6% top-1 accuracy with a linear classifier, above the other AlexNet results listed in the table.

With ResNet-50, their conv5 linear result reaches 54.0%; the listed Exemplar CNN result is 31.5% with ResNet-101. Their training and evaluation conditions differ. Across the four backbones used for this method, the conv5 value rises with architecture size.

The final 128-dimensional features yield k-NN accuracies of 31.3%, 33.9%, 41.0%, and 46.5% from AlexNet through ResNet-50. Each is below its own conv5 linear result, but the features still support classification. In this table, the method's later convolutional features are generally more useful to a linear classifier than the earlier ones.

Finally, some methods in the table use around 10,000-dimensional intermediate features. This method's final embedding has only 128 dimensions. The authors report about 600 MB to store features for all 1.28 million ImageNet training images and about 20 ms per image for a full-bank nearest-neighbor search on a Titan X GPU.

Cross-Dataset Generalization

The authors then tested the features learned on ImageNet, directly applied to another large dataset, Places (2.45 million images, 205 categories), without fine-tuning, only feature extraction, and then trained a linear classifier or performed k-NN on Places.

In the table above, ResNet-50 reaches 45.5% with a linear classifier on conv5 and 41.6% with k-NN on the final embedding. These exceed the listed methods in the corresponding columns, though the backbones and evaluated features differ across rows.

These results demonstrate that the features learned on ImageNet can maintain good performance even in different domains (scene classification), showing the method's cross-domain generalization ability.

Ablation Experiment - Feature Dimension

After confirming that the model architecture is effective, the authors conducted some ablation experiments.

The first explores the impact of feature dimension. The authors compared feature dimensions of 32, 64, 128, and 256, with results shown in the table above.

For ResNet-18, k-NN top-1 accuracy rises from 34.0% at 32 dimensions to 41.0% at 128 dimensions, then falls to 40.1% at 256 dimensions. In this tested setup, 128 dimensions give the best result in the table.

Ablation Experiment - Training Set Size

Next, the authors explored the impact of "training set size" on model performance. The experimental setup was as follows:

  • ImageNet training set: Used 0.1%, 1%, 10%, 30%, and 100% of the images for feature learning.
  • Evaluation: Used nearest-neighbor classification on the full labeled set to evaluate the learned features.

As the training share rises from 0.1% to 100%, accuracy in the table rises from 3.9% to 41.0%. Within this tested range, more unlabeled training images improve the learned features.

Visualization Analysis

Finally, the authors presented some feature visualization results, which demonstrate the "image search by image" functionality. By comparing image features, the model finds the closest images to the "query."

The experimental results are shown in the figure above:

  • Best case (top four rows): The top 10 retrieved images are all from the same category as the query image (selected successful examples).
  • Worst case (bottom four rows): None of the top 10 is in the query's true class. Some retrieved images still look similar in shape, color, or background; for others, the relationship is hard to judge from the figure.

The authors use these examples to suggest that the instance-level embedding can capture visual similarity beyond class labels. The figure provides qualitative examples.

Conclusion

The paper also includes experiments applied to "semi-supervised classification" and "object detection," but we won't go into detail here. Interested readers can refer to the original paper.

Overall, these experiments thoroughly validate the versatility and scalability of the authors' approach: it is effective not only for classification and retrieval but also demonstrates good generalization across different network architectures, data scales, and downstream tasks (semi-supervised classification, detection).

After the paper's release, the unsupervised learning framework based on NCE loss quickly achieved impressive results on large-scale datasets and demonstrated strong performance in practical applications.

There are still several classic papers to follow up on, so let’s continue reading.