Back to paper library
arXiv 2019CVPR 2019Contrastive learningPaper notes

InvaSpread

Traces Under Difficulties

Original paper

Unsupervised Embedding Learning via Invariant and Spreading Instance Feature

Paper authors

Mang Ye · Xu Zhang · Pong C. Yuen · Shih-Fu Chang

Publication
CVPR 2019Conference
First submitted to arXiv
arXiv:1904.03436
Cite this paper · BibTeX

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

@misc{contrastivelearninginvaspread2019,
  title = {{Unsupervised Embedding Learning via Invariant and Spreading Instance Feature}},
  author = {Mang Ye and Xu Zhang and Pong C. Yuen and Shih-Fu Chang},
  year = {2019},
  eprint = {1904.03436},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1904.03436}
}
On this page

The main comparative targets of this paper are the Exemplar CNN and InstDisc papers.

Defining the Problem

To find universal features, one approach is to use the classifier weight's Softmax embedding, as proposed by Exemplar CNN: treat each image as an independent class.

Exemplar CNN defines a matrix W=[w1,w2,…,wn]T∈Rn×dW = [w_1, w_2, \dots, w_n]^T \in \mathbb{R}^{n \times d}, where wjw_j corresponds to the classifier weight for the jj-th instance.

During training, based on the Softmax function, the probability of sample xjx_j being recognized as the ii-th instance is:

P(i∣xj)=exp⁡(wiTfj)∑k=1nexp⁡(wkTfj)P(i|x_j) = \frac{\exp(w_i^T f_j)}{\sum_{k=1}^n \exp(w_k^T f_j)}

At each step, the network pulls feature fif_i closer to its corresponding classifier weight wiw_i, and pushes it away from other classifier weights wkw_k.

However, this method’s classifier weights restrict explicit comparisons between features, ultimately leading to poor efficiency and recognition power.

Next, InstDisc discarded the classifier weights and proposed the Memory Bank method, storing the instance features fif_i calculated the last time each instance was encountered as viv_i.

These stored features are then "directly" used as the classifier weights for corresponding instances, with the probability of sample xjx_j being recognized as the ii-th instance:

P(i∣xj)=exp⁡(viTfj/τ)∑k=1nexp⁡(vkTfj/τ)P(i|x_j) = \frac{\exp(v_i^T f_j / \tau)}{\sum_{k=1}^n \exp(v_k^T f_j / \tau)}

Here, τ\tau is a temperature parameter controlling the concentration of the distribution. With both features L2-normalized, viTfjv_i^T f_j represents the cosine similarity between feature fjf_j and memory feature viv_i.

The drawback is that memory features are updated less frequently, and comparisons between the real-time feature fif_i and outdated memory feature viv_i reduce training efficiency.

Since using parameterized Softmax is ineffective and the Memory Bank method is not very efficient, is there a way to directly optimize the features themselves, instead of the classifier weights or memory features?

The authors argue that we should abandon the Memory Bank and directly optimize the features themselves!

Solving the Problem

Model Architecture

The figure above shows the framework of the method proposed by the authors, which seems quite simple. First, a batch of images is input, which undergoes random data augmentation.

  • Original images: A set of unlabeled images serves as the data source.
  • Data augmentation: Random resized cropping, grayscale conversion, color jitter, and horizontal flipping create another view of each image. These transformations are intended to preserve useful instance information; very aggressive augmentation can still remove semantic content.

Each image and another augmented version enter CNN branches with shared weights to produce the corresponding features. The first branch may also use augmentation. We denote the two features by fif_i and f^i\hat{f}_i and L2-normalize them.

Finally, there is feature alignment and spreading:

  • Feature alignment for the same image (Invariance): For the same instance (i.e., the original image and its augmented version), the embedded features fif_i and f^i\hat{f}_i should be consistent (features are close). This encourages features to become less sensitive to the selected augmentations.
  • Feature spreading for different images (Spread-out): The embedded features of different instances in the batch should be separated to help distinguish the images. Unlabeled data may contain images of the same category, so some of these apparent negatives can be false negatives.

Loss Function

At the end of the methodology, let's look at the loss function designed in this paper.

First, for the positive sample classification probability, the probability of the augmented sample x^i\hat{x}_i being correctly classified as instance ii is:

P(i∣x^i)=exp⁡(fiTf^i/τ)∑k=1mexp⁡(fkTf^i/τ)P(i|\hat{x}_i) = \frac{\exp(f_i^T \hat{f}_i / \tau)}{\sum_{k=1}^m \exp(f_k^T \hat{f}_i / \tau)}

Where:

  • fif_i: The embedding feature of the original image xix_i.
  • f^i\hat{f}_i: The embedding feature of the augmented image x^i\hat{x}_i.
  • τ\tau: The temperature parameter, which adjusts the concentration of the probability distribution.

Then, for the misclassification probability, the probability of other instances xj,j≠ix_j, j \neq i being misclassified as instance ii is:

P(i∣xj)=exp⁡(fiTfj/τ)∑k=1mexp⁡(fkTfj/τ)P(i|x_j) = \frac{\exp(f_i^T f_j / \tau)}{\sum_{k=1}^m \exp(f_k^T f_j / \tau)}

The probability that xjx_j is not misclassified as instance ii is:

1−P(i∣xj)1 - P(i|x_j)

Assuming the classification of different instances as instance ii is independent, the joint probability is:

Pi=P(i∣x^i)∏j≠i(1−P(i∣xj))P_i = P(i|\hat{x}_i) \prod_{j \neq i} (1 - P(i|x_j))

Where:

  • P(i∣x^i)P(i|\hat{x}_i): The probability that the augmented sample x^i\hat{x}_i is correctly classified as instance ii.
  • 1−P(i∣xj)1 - P(i|x_j): The probability that other instances xj,j≠ix_j, j \neq i are not misclassified as instance ii.

Based on maximum likelihood estimation, we can take the negative logarithm of the joint probability to obtain the loss function:

Ji=−log⁡P(i∣x^i)−∑j≠ilog⁡(1−P(i∣xj))J_i = -\log P(i|\hat{x}_i) - \sum_{j \neq i} \log(1 - P(i|x_j))

Here, the loss function consists of two parts:

  1. The loss from correctly classifying the augmented sample x^i\hat{x}_i (the first term).
  2. The loss from not misclassifying other samples (the second term).

The final total loss function is defined by summing over all instances in the batch:

J=−∑ilog⁡P(i∣x^i)−∑i∑j≠ilog⁡(1−P(i∣xj))J = -\sum_i \log P(i|\hat{x}_i) - \sum_i \sum_{j \neq i} \log(1 - P(i|x_j))

In implementation, each of the mm instances in a batch has one augmented counterpart: one corresponding positive and 2m−22m-2 other features used as negatives. The loss uses current batch features instead of per-instance classifier weights or a memory bank. The efficiency and discriminability gains are evaluated in the experiments below.

Discussion

Comparison with Other Methods

The authors first follow the experimental design of InstDisc, conducting experiments on the CIFAR-10 and STL-10 datasets, using ResNet18 as the backbone network, with the output dimension of the embedding features set to 128. Evaluation retrieves the k=200k=200 nearest neighbors by cosine similarity and then uses weighted kNN voting.

The table above shows the CIFAR-10 results. The authors compare their method with DeepCluster, Exemplar CNN, NPSoftmax, NCE, and Triplet loss methods. Their 83.6% kNN accuracy is highest among the methods shown, compared with 80.8% for NPSoftmax and 80.4% for NCE.

In different epochs, the authors plot the learning curves of other methods as shown below:

In this CIFAR-10 experiment, the proposed method reaches about 60% kNN accuracy in 2 epochs, whereas NCE needs about 25 and Exemplar about 45 epochs to reach the same threshold.

The curve supports faster convergence at the same accuracy threshold. The authors attribute this to directly optimizing current batch features rather than depending on classifier weights or a memory bank; the epoch count alone is not a wall-clock comparison.

Experiments with Unknown Classes

Based on existing work in supervised deep embedding learning, the authors evaluated the following metrics on the test set:

  • Retrieval Performance (R@K): Measures the fraction of queries with at least one same-class match among their top kk retrieved results.
  • Clustering Performance (NMI): Measures the clustering quality of the test set using Normalized Mutual Information (NMI).

Next, to assess the discriminative ability of the learned feature embeddings when there is no overlap in semantic classes between the training and test samples, the authors conducted experiments on the CUB200, Product, and Car196 datasets:

  • CUB200 (Bird Dataset): The first 100 classes (5,864 images) were used for training, and the remaining 100 classes (5,924 images) were used for testing.
  • Product (Product Dataset): The first 11,318 classes (59,551 images) were used for training, and the remaining 11,316 classes (60,502 images) were used for testing.
  • Car196 (Car Dataset): The first 98 classes (8,054 images) were used for training, and the remaining 98 classes (8,131 images) were used for testing.

These experiments use an ImageNet-pretrained Inception-V1 backbone by default; the target datasets' category labels are not used to train the embeddings. For CUB200, the method also uses pretrained features to find a nearest neighbor as an additional positive. The paper separately reports a Product experiment without pretrained weights, so the following table should not be read as a wholly from-scratch comparison.

In the CUB200 table, the method reaches 46.2% R@1 and 55.4% NMI, above the other unsupervised methods shown. Its R@1 also exceeds some listed supervised methods, though it remains below the best listed 49.8%. These results need to be read with the ImageNet-pretraining condition in mind.

Ablation Study

The proposed method introduces two key properties in instance feature learning: data augmentation invariance and instance dispersion.

To verify the impact of these properties on performance, the authors conducted an ablation study on the CIFAR-10 dataset.

  • Impact of Data Augmentation Invariance

    The table above shows the results, where:

    • w/o: Indicates the removal of a specific augmentation operation.
    • R: Indicates random cropping (RandomResizedCrop).
    • G: Indicates random grayscale (RandomGrayscale).
    • C: Indicates color jittering (ColorJitter).
    • F: Indicates random horizontal flipping (RandomHorizontalFlip).

    Removing each listed augmentation reduces accuracy: from the full model's 83.6% to 56.2% without random cropping, 79.3% without grayscale, 75.7% without color jitter, or 82.6% without horizontal flipping. Random cropping has the largest effect in this table. The authors also tested using no data augmentation (No DA), shown below:

    The classification accuracy dropped sharply from 83.6% to 37.4%, which is quite astonishing!

    The authors argue that without augmented views, the model lacks different versions of the same instance to form positive pairs and cannot learn the intended invariance. Table 8's accuracy drop supports the importance of augmentation in this setup.

  • Impact of Instance Dispersion

    To study the effect of instance dispersion, the authors tested two negative sample selection strategies:

    1. Hard Negative: Select the top 50% most similar features to the query instance as negative samples.
    2. Easy Negative: Select the top 50% least similar features to the query instance as negative samples.

    The same table shows that using only easy negatives drops accuracy from the full model's 83.6% to 57.5%, whereas using only hard negatives reaches 83.2%, close to the full model.

    This means that separating difficult negative samples helps improve the discriminative power of the learned embedding features. In contrast, easy negative samples provide almost no challenge to the model and do not effectively help the model learn instance dispersion.

Conclusion

This paper emphasizes two key points: data augmentation invariance and instance dispersion.

These experiments support diverse, suitable augmentations and informative negative samples. Hard negatives can be useful, but some may be false negatives from the same semantic class; selecting only the hardest examples is not a universal rule.

These two conclusions continue to appear in subsequent research and can be regarded as important observations in the field of unsupervised learning.