Incremental False Negative Detection for Contrastive Learning
Authors: Tsai-Shien Chen
Wei-Chih Hung
Hung-Yu Tseng
Shao-Yi Chien
Ming-Hsuan Yang
Venue: ICLR 2022 Poster (2022)
Keywords: Self-supervised learning
Contrastive learning
Representation learning
Clustering-based learning

Abstract: Self-supervised learning has recently shown great potential in vision tasks through contrastive learning, which aims to discriminate each image, or instance, in the dataset. However, such instance-level learning ignores the semantic relationship among instances and sometimes undesirably repels the anchor from the semantically similar samples, termed as "false negatives". In this work, we show that the unfavorable effect from false negatives is more significant for the large-scale datasets with more semantic concepts. To address the issue, we propose a novel self-supervised contrastive learning framework that incrementally detects and explicitly removes the false negative samples. Specifically, following the training process, our method dynamically detects increasing high-quality false negatives considering that the encoder gradually improves and the embedding space becomes more semantically structural. Next, we discuss two strategies to explicitly remove the detected false negatives during contrastive learning. Extensive experiments show that our framework outperforms other self-supervised contrastive learning methods on multiple benchmarks in a limited resource setup.

Published as a conference paper at ICLR 2022
INCREMENTAL FALSE NEGATIVE DETECTION FOR CONTRASTIVE LEARNING
Tsai-Shien Chen', Wei-Chih Hung", Hung-Yu Yu Tseng", "eeng",hao-YYs Chien', Ming- Hsuan Yang
1 National Taiwan University
Waymo LLC
3 University of California, Merced
4 Yonsei University
5 'Google Research
t.s tschen@medi a
ee.. ee. ntu. edu.tw
ABSTRACT
Self-supervised learning has recently shown great potential in vision tasks through contrastive learning, which aims to discriminate each image, or instance, the dataset. However, such instance-level learning ignores the semantic relationship among instances and sometimes undesirably repels the anchor from the seman- tically similar samples, termed as "false negatives". In this work, we show that the unfavorable effect from false negatives more significant for the large-scale datasets with more semantic concepts. To address the issue, propose a novel sulf-suue contrastive learning framework that incrementally detects and ex- plicitly removes the false negative samples. Specifically, following the training process, our method dynamically detects increasing high-quality false negatives considering that the encoder gradually improves and the embedding space be- comes more semantically structural. Next, we discuss two strategies to explicitly remove the detected false negatives during contrastive learning. Extensive ex- periments show that our framework outperforms other self-supervised contrastive learning methods on multiple benchmarks in a limited resource setup. The source chen/ IFND.
code is available at https: / /iithub. com/tsaaaaaaao
INTRODUCTION
Self-supervised learning of visual representation (Doersch al., 2015; Pathak et al., 2016; Noroozi & Favaro, 2016; Oord et al., 2018; Gidaris et al., 2018; Chen et al., 2020a) aims to learn semantic- aware embedding space based on the image data without the supervision of human-labeled anno- tations. Recently, significant advances have been made by contrastive learning approaches (Hjelm et al., 2019; Tian et al., 2019; Chen al., 2020b;e; He et al., 2020; Chen et al., 2020d) to reduce the performance gap with the supervised counterparts. Most unsupervised contrastive learning methods are developed based on the instance discrimination assumption. These approaches treat each training image individual instance and learn the representations that discriminate every single sample. Specifically, considering an arbitrary image as an anchor, the only positive sample is generated by applying different data augmentation the anchor image, while all other images are treated as negative samples. The training objective is to attract the positive to the anchor while repelling the negative samples from the anchor.
While instance-level contrastive learning has shown impressive performance, these methods do not take the semantic relationship among images into consideration. Although some images share simi- lar semantic concepts with the anchor, they are still considered as negative samples and are equally pushed away from the anchor with all other negatives. We define these samples as "false negatives" in self-supervised contrastive learning, which would adversely affect the representation learning (Saunshi et al., 2019). One might argue that such undesirable effects might be minor for the datasets with diverse semantic concepts since the probabilities of drawing false negatives are relatively low. However, as shown in Figure 1, we empirically find the opposite results that the performance drops due to training with false negative samples more significant large-scale datasets with more semantic categories. These results bring up the issue instance-level contrastive learning when is applied to datasets with more complex semantic contents.

---

Published as a conference paper at ICLR 2022
100
Figure 1: Effect of false negative for con- trastive learning. To study the effect of false negatives, we compare two frameworks: Sim- CLR (Chen et al. (2020b), blue) represent- ing instance-level contrastive learning which is trained with false negatives, and SupCon (Khosla et al. (2020), red) benefiting from human-labeled annotations to exclude false negatives. We observe that training with false negatives leads to larger performance gaps (orange) on the datasets with more semantic categories. The proposed approach (green) effectively alleviates such adverse effects by explicitly removing the detected false nega- tives for self-supervised contrastive learning, See Section 4.3 for experimental details.
95
Top- Ciassilication Accuracy (%)
90
A:-2.2
86
4:2
80
75
-20
70
A:-4.7
65
Falio Nagative (SmMLLR)
Wo Fatse Negative (SupCon)
-6.6
60
Negalive Detection (Oura)
55
9
36
206
466
1000
Number Training Categories
To handle the false negative issue, we propose a novel framework to incrementally detect and ex- plicitly remove false negatives for sule-supe contrastive learning. During training, we cluster samples in the embedding space and assign the cluster indices as the pseudo labels to the training images. Instances with an identical label to the anchor are then detected false negatives. However, we notice that the pseudo labels generated in the earlier training stages are comparably unreliable to represent the semantic relationship among instances since the semantic structure of the embedding space is still under development. Therefore, we propose a novel strategy to assign the pscudo labels in an incremental manner. In the early training stage, we only use small portion of pseudo labels with higher confidence while treating other samples as individual instances. In the later training stage, as the pseudo labels become more reliable, we dynamically include more confident labels to detect and remove false negatives and hence, can benefit semantic-aware representation learning.
Furthermore, we discuss two types of training objectives to explicitly address the detected false negatives during contrastive learning: elimination and attraction. We theoretically show that they are the generalization of triplet loss (Schroff et al., 2015). While both objectives avoid discriminating the anchor and its false negatives, the attraction objective further minimizes the distances between them. Empirically, we find that such a more aggressive strategy is less tolerant to noisy pseudo labels and unsuitable to our self-supervised framework. The main contributions of this paper summarized as follows:
We highlight the issue of false negatives in contrastive learning, especially on the large- scale datasets with more diverse semantic contents.
We propose a novel contrastive learning framework with incremental false negative detec- tion (IFND) that smoothly bridges instance-level and semantic-aware contrastive learning. Our approach explicitly detects and incrementally removes false negatives as the embed- ding space becomes more semantically structural through the training process.
Our approach performs favorably against the existing self-supervised contrastive learning frameworks on multiple benchmarks under limited training resource setup. Besides, we introduce two metrics: mean true positive/negative rates to evaluate the clustering quality.
2 RELATED WORK
Instance-level contrastive learning. Learning semantic-aware visual representation without hu- man supervision is an essential but challenging task. Numerous approaches are developed based on the instance discrimination task (Dosovitskiy et al., 2015; Wu et al., 2018; Ye al., 2019; Misra & Maaten, 2020), where each instance in the dataset is treated as individual sample and rep- resentation is learned to classify or contrastively separate samples. Recently, with the contrastive loss (Gutmann & Hyvärinen, 2010) and set of image transformations or augmentations (Chen et al., 2020b), the instance-lewe level contrastive learning methods (Hjelm et al., 2019; Tian et al., 2019; Chen et al., 2020b;c; He et al., 2020; Chen et al., 2020d) achieve state-of of-the--rtttttt- results and even outperform some supervised pre- pre-training approaches. While significant improvement is achieved, instance-level contrastive learning frameworks typically do not take high-level semantics into
2

---

Published as a conference paper at ICLR 2022
count. For example, any two samples in the dataset would be considered negative pair and be pushed apart by the contrastive loss although some of them are semantically similar and should be nearby in the embedding space. Especially when the huge amounts of negative samples (8192 for Chen et al. (2020b), 65536 for He et al. (2020)) play a critical role in the success of contrastive learning, these instance-level approaches inevitably draw some "false negatives" and learn less ef- fective representation models as shown by recent study (Saunshi et al., 2019). In this paper, we further show that the performance gap between the contrastive learning trained with and without false negatives is more significant on the datasets with more semantic classes.
Semantic-aware contrastive learning. To address the limitation of instance-level contrastive learn- ing, several methods are developed to exploit the semantic relationship among images. Chuang et al. (2020) show that the original instance-level sampling strategy includes a sampling bias and propose debiased contrastive loss. However, this method does not explicitly handle false negative sam- ples. Huynh et al. (2020) determine false negatives of an anchor by finding top l similar samples without referring to global embedding distribution. Khosla et al. (2020) propose supervised con- trastive loss that utilizes label information and treats images of the same class (i.e., false negatives) as positives. However, manually annotated labels cannot be acquired in the unsupervised setting. Closely related to our method, PCL (Li et al., 2021) discovers the representative prototypes for each semantic concept and encourages an image embedding be closer its belonging prototype. There are two fundamental differences between PCL. and the proposed method: a) PCL uses all assigned prototypes regardless of inferior clustering results in early stages, which cannot properly reflect the semantic relationship among images, b) without treating semantically similar samples as false nega- tives, PCL applies instance-level InfoNCE loss (Oord al., 2018) as the primary supervision, which fails to avoid the images within the same prototype being pushed apart. In contrast, leveraging the progressive detection and explicit removal of false negatives, our framework achieves greater clus- tering quality and representation learning. More comparisons are in Section 4.2 and Appendix E.
Clustering for deep unsupervised learning. A few unsupervised learning methods have recently benefited from clustering techniques to construct more effective representation models (Caron et al., 2018: Yang et al., 2016; Xie et al., 2016: Caron et al., 2019; Zhuang et al., 2019; Asano et al., 2020). The main idea is to use cluster indices as pseudo labels and learn visual representations in a supervised manner. However, most existing methods require all pseudo labels to optimize the supervised loss, e.g., cross-entropy. In this work, we show that the pseudo labels obtained in earlier training processes are relatively unreliable, and the full adoption of pseudo labels in the early stage would further disrupt the representation learning. To handle this issue, we incorporate instance-level learning with clustering which allows us to only use a set of pseudo labels with sufficient confidence while treating the others as individual instances.
3 METHODOLOGGY
3.1 INSTANCE-LEVER CONTRASTIVE LEARNING
An instance-level contrastive learning method learns representation that discriminates one sample from every other. Given M randomly sampled images from a training set X', a contrastive training mini-hatch I consists of 2M images obtained by applying two sets of data augmentation on each sampled image. For any anchor image E I, the only positive sample is another view (or transfor- mation) of the same image, denoted as i', while the other 2(M 1) images jointly constitute the set of negative samples (i). The instance-level discrimination is then optimized by the following contrastive loss:
sim(zi, 2v) log Σ Sim(,,,2.) 2,)'
Linst
S(i) (nnneN())))
SE
+ES(S)
where z; = s(((i)) is the embedding of the image from an encoder f and a projection head g, sim(u, v) = exp( (w-v) [all| wll is the similarity of two input vectors, and represents temperature hyper-parameter. For instance-level contrastive learning, the negative sample set M(ii) inevitably includes some samples with similar semantic content the anchor i, which term as false nega- tives, especially when a larger M is commonly used. Consequently, it would separate semantically similar image pairs, which is suboptimal for learning good semantic-awan visual representations.
3

---

Published as a conference paper at ICLR 2022
Incremental False Negative Detection
CNN
CNN
Backward Propagation
Pseudo label
Training Process
Contrastive Learning without Faise Negative
Figure 2: Algorithmic overview. (a) Our method uses pseudo labels in an incremental manner with respect to the gradually better-trained encoder and embedding space. (b) The proposed contrastive learning framework uses pseudo labels to explicitly detect and eliminate false negatives from self- supervised contrastive learning.
3.2 INCREMENTAL FALSE NEGATIVE DETECTION
To learn an effective semantic-aware representation by self-supervised contrastive learning, our method explicitly detects and removes the false negative samples. Specifically, we follow the same procedure in PCL (Li et al., 2021) to perform k-means clustering on the features f(i) of all train- ing images {i X} and cluster the features into groups. We use the centroids to represent the embeddings of the discovered semantic concepts and denote the centroid representation of k-th cluster as Cg. The pseudo label Yí of the image is assigned based on the closest centroid, formally arg min (i) c&ll- In the learning process, two images with an identical assigned pseudo label would be treated as a false negative pair.
Nonetheless, as illustrated in the lefimost of Figure 2(a) (or Figure 3 for realistic case), we observe that the semantic structure of early embedding space is less reliable and could generate noisy pseudo labels, which would disrupt the representation learning. We provide a quantitative analysis of this effect in Section 4.4 and Appendix F. To tackle this problem, in early training stages, we only adopt the pseudo labels with higher confidence while treating the other images individual samples. For an arbitrary image i, the desired confidence K; should be larger when the image embedding f'ii) is not only closer the centroid of the belonging group, i.e., Cyis but also farther to the other centroids. To this end, we measure the confidence of an assigned pscudo label by:
sim(zi, Cys)
K2 Σラ sim 22, Cj)
which is the softmax of cosine similarities between the image representation and every centroid. We then only assign a specific rate (termed as acceptance rate) of pseudo labels with larger confidence. As plotted in the rest part of Figure 2 (or Figure 3), following the training process, the encoder is better trained and the semantic structure of embedding space is more clear which can generate more reliable pseudo labels. Hence, we propose to incrementally increase the acceptance rate and leverage semantic-award representation learning. In Section 4.4, we demonstrate that a simple strategy that linearly increases the acceptance rate from 0% to 100% throughout the whole training process can achieve significant improvement.
Hierarchical semantic definition. an unsupervised setting, the precise class number of a dataset is usually unknown, and also, different number of classes can be selected by choosing different level of granularity. To enhance the flexibility and robustness of our method, we incorporate hier- archical clustering techniques (Johnson, 1967; Corpet, 1988; Murtagh & Legendre, 2014; Li et al., 2021) 1) into our framework. Specifically, we perform multiple times of k-means with different cluster numbers to define the false negatives in the different levels of granularity. As such, the objective function (will be introduced in Section 3.3) is revised as the average of the original ones computed by the false negatives defined in different levels of granularity.
4

---

Published as a conference paper at ICLR 2022
3.3 CONTRASTIVE LEARNING WITHOUT FALSE NEGATIVE
Given the assigned pseudo labels, our next goal is to revise the objective of instance-level contrastive learning, i.e., Linst in Equation 1, explicitly deal with the detected false negatives. We discuss two strategies to exploit false negatives. First, false negative elimination approach excludes the false negatives from the negative sample set (i)):
sim (z,, 2v)
Celsm
log
S(i) = [i'n|InEN()) Un #V)
sim 22 =.) 8ES(()
iEI
Second, considering that the anchor and its false negatives are assigned with the same pseudo label, view the false negatives additional positive samples:
sim( xp)
((() {i', N())
Catt Σ
log
(4)
Σ #ES(()
sim (Z,, 2.)
P(i) = {i', I NEN - y.
(E
Behaviors of elimination and attraction strategies. Compared to the original contrastive learning objective Linst, Lelim removes the similarities between the anchor and its false negatives from the denominator while on the other hand, Lattr places them the numerator. They both show great capability to enlarge the similarities between the anchor and the false negatives when the objective is minimized. To further explore and compare their behaviors, we derive the gradients with regard to the embedding of the anchor 2; as:
dLotim, Ozi
Datttr Oz,
Σ (E)()) Fo
2n
ZF
and
12
Zn
2p
(5)
mEN(
PEP(()
where the weighted coefficient. The detailed formulation and derivation are in Appendix A. Based on their gradients in Equation 5, Letim and Lattr are the generalization of triplet loss' (Schroff et al., 2015) which would intrinsically repel the negatives and attract the positive(s) to the anchor. While both of them fully eliminate the detected false negatives (i.e., {n n E N(i). Vn. yı from the negative samples and avoid them being pushed apart from the anchor, Lattr further minimizes the distances between the anchor and its false negatives. Such more aggressive strategy results in less tolerance to noisy pseudo labels which are inevitably generated from an unsupervised clustering. Hence, although SupCon (Khosla et al., 2020) presents the effectiveness of Lattr with manual label annotations, we find Letim is more stable and suitable to our self-supervised framework.
Finally, we illustrate the framework in Figure 2(b) and present the pseudo code in Appendix B.
4 EXPERIMENTS
We validate and analyze our framework on several benchmarks. We train the model on 8 Nvidia V100 GPUs for all experiments. For fair comparisons, we group prior self cuff-super algorithms with a similar setting demonstrate the efficacy of our proposed method.
4.1 IMPLEMENTATION DETAILS
We use ResNet-50 (He et al., 2016) as the encoder, followed by a 3-layer MLP as the projection head to obtain 128-D features We apply the proposed method to ImageNet (Deng et al., 2009) and CIFAR (Krizhevsky et al., 2009). For ImageNet pre- training, we follow the same setting in MoCo v2 (Chen al., 2020d) and PCL. (Li et al., 2021) for fair comparisons. Specifically, we train the encoder for 200 epochs with a mini-batch size of 256 and use the memory-based method (He al., 2020) to increase the number of contrastive samples in default. For pseudo label assignment, we employ k-means clustering implemented by Johnson et al. (2019) to re-assign the pseudo labels after every training epoch and use three cluster numbers (1000, 3000, 10000) define semantic concepts. In default, we linearly increase the pseudo label acceptance rate from 0% to 100% through the whole training process and use the elimination loss Catim as the objective. The training lasts for 60 hours of which 3.5 hours is spent on pseudo label assignment. More details and the setting for CIFAR pre-training are provided in Appendix C.
Thee gradient of triplet loss
2pl1 2 || zn 21. a] w.r.t z; is (2z.. 22y).
5

---

Published as a conference paper at ICLR 2022
Table 1: Linear evaluation and transfer learning three benchmarks. We report the Top-1 classification accuracy (%). The upper group uses more compact backbone (AlexNet (Krizhevsky al., 2012) or ResNet-50 (He al., 2016)), and smaller pre-training batchsize (< 256).
Pre-training
Datasets
Method
Architecture
batchsize
epochs
ImageNet
VOC
Places
Jigsaw (Noroozi & Favaro, 2016)
AlexNet
256
34.6
67.6
Rotation (Gidaris al., 2018)
AlexNet.
128
100
38.7
73.0
35.1
DeepCluster (Caron et al., 2018)
AlexNet
256
500
41.0
73.7
InstDisc (Wu et al., 2018)
ResNet-50
256
200
54.0
45.5
LocalAgg (Zhuang et al., 2019)
ResNet-50
128
200
60.2
50.1
CMC (Tian et al., 2019)
ResNet-50
200
66.2
SimCLR (Chen al., 2020b)
ResNet-50
MoCo (He et al., 2020)
ResNet-50
256
200
60.6
79.2
48.9
MoCo v2 (Chen et al., 2020d)
ResNct-50
256
200
67.5
84.0
50.1
PCL (Li et al., 2021)
ResNet-50
256
200
67.6
85.4
50.3
IFND (Ours)
ResNet-50
256
200
69.7
87.3
51.9
CPC (Oord al., 2018)
ResNet-101
512
48.7
ScLa (Asano al., 2020)
ResNet-50
1024
400
61.5
PIRL (Misra Maaten, 2020)
ResNet-50
1024
800
81.8
49.8
SimCLR (Chen et al., 2020h)
ResNet-50
4096
1000
69.3
BYOL (Grill al., 2020)
ResNet-50
4096
1000
74.3
SwAV (Caron et al., 2020)
ResNet-50
4096
800
75.3
88.9
56.7
Table Semi-supervised learning on ImageNet. We report the Top-5 classification accuracy (%)
The numbers of MoCo and MoCo v2 are computed from the official pretrained models.
Pre-training
Label fraction
Method
Architecture
batchsize
epochs
1%
10%
InstDise (Wu et al., 2018)
ResNet-50
256
120
39.2
77.4
MoCo (He et al., 2020)
ResNet-50
256
200
56.9
83.0
MoCo v2 (Chen et al., 2020d)
ResNet-50
256
200
66.3
84.4
PCL (Li et al., 102
ResNet-50
256
200
75.3
85.6
IFND (Ours)
ResNet-50
256
200
77.0
86.5
S4L((OAM) (Zhai et al., 2019)
ResNet-50 (1x)
256
1000
91.2
PIRL (Misra & Maaten, 2020)
ResNet-50
1024
800
57.2
83.8
SimCLR (Chen et al., 2020b)
ResNet-50
4096
1000
75.5
87.8
BYOL (Grill et al., 2020)
ResNet-50
4096
1000
78.4
89.0
SwAV (Caron al., 2020)
ResNet-50
4096
78.5
89.9
4.2 COMPARISON WITH THE STATE-OF-THE-ARE
Linear evaluation and transfer learning on image classification benchmarks. We first assess the performance of the image representations after pre-training ImageNet. We train linear classifier with the fixed representations as input on three benchmarks: ImageNet (Deng et al., 2009), VOC2007 (Everingham et al., 2010) and Places205 (Zhou al., 2014) and report the results in Table 1. IFND obtains consistent improvements compared to previous self-supervised contrastive learning approaches with similar experiment setting. The direct comparison PCL (Li al., 2021) emphasizes the advantages of incrementally detecting and explicitly removing the false negatives in contrastive learning. We provide a more in-depth ablation study with PCL in Appendix E.
Semi-supervised learning on ImageNet. Next, we evaluate the embeddings pre-training on Im- ageNet in the semi-supervised setting. We follow the protocol described SimCLR (Chen et al., 2020b) and use the same 1% 10% fraction of ImageNet labeled training set to finetune the pre- trained encoder. The results are shown in Table 2. IFND outperforms the prior approaches within similar setup; notably, when using the 1% label, it achieve more superior performance than SimCLR with 16 times larger batchsize and times more training epochs.
Object detection and instance segmentation COCO. We evaluate representation the tasks of object detection and semantic segmentation. Following the experiment setting in MoCo (He al., 2020) and PCI., finetune all layers end-to-end the COCO (Lin al., 2014) train2017

---

Published as a conference paper at ICLR 2022
Table 3: Object detection and instance segmentation on COCO. We report bounding-box AP (APb) and mask AP (APmk) on val2017 (Lin et al., 2014) (%). We use Mask R-CNN (He et al., 2017) with C4 backbone the model, and the schedule is the default 2x in Girshick et al. (2018). Supervise represents the pre-trained model through the supervised training scheme.
Method
Ap
AP
AP
Ap
APm
AP
Supervise
40.0
59.9
43.1
34.7
56.5
36.9
MoCo (He et al., 2020)
40.7
60.5
44.1
35,4
57.3
37.6
PCL (Li et al., 2021)
41.0
60.8
44.2
35,6
57.4
37.8
IFND (Ours)
41.8
61.2
44.5
36.1
57.6
38.5
We compare k-means clustering (k: 1000) perfor- mance for different algorithms (mostly for deep clustering -baeed methods) using Normalized Mutual Information (Strehl & Ghosh, 2002) (%) for evaluation. We run k-means five times and report the average score with the standard deviation. All results are from the official pre-trained models.
Table 4: Clustering quality ImageNet.
Method
NMI
DeepCluster (Caron et al., 2018)
43.2 + 2,9
MoCo (Chen al., 2020d)
57.9 2.2
SWAV (Caron et al., 2020)
63.8 + 1.6
PCL (Li et al., 2021)
65.0 + 1.9
IEND (Ours)
67.5 + 1.7
Table 5: Effect of false negatives on self-supervised learning. We report the Top-1 classifica- tion accuracy (%) and use the results of SupCon as the oracle performance with no effect of false negative. A represents the performance drop due training with false negatives.
Class label
CIFAR
CIFAR
ImageNet Depth 7
Method
10
100
Depth 3
Depth 5
Depth 9
Depth 18
SimCLR
x
94.2
71.5
93.9
86.0
75.3
71.6
65.1
IFND (Ours)
x
95.1
74.0
95.2
87.5
77.2
73.8
68.4
SupCon
95.9
76.2
96.1
89.2
79.3
76.3
71.5
Number of categories
10
100
9
36
206
486
1000
ASSupCon, SimCLR)
-1.7
-4.7
-2.2
-3.2
-4.0
-4.7
-6.4
ASSupCon, IFND)
-0.8
-2.2
-0.9
-1.7
-2.1
-2.5
-3.1
and evaluate on val2017 dataset. We report the results in Table 3. IFND outperforms MoCo, PCL, and supervised pre-training in all metrics.
Clustering quality ImageNet. We also measure the clustering quality the ImageNet pre- training representations and report the results in Table 4. Compared to MoCo v2, our method lever- ages semantic-aware learning and shows significant improvement of 9.6% on NMI. Moreover, contrastive
IFND achieves the best clustering quality compared to existing deep clustering- learning frameworks. In Appendix we analyze the clusterings during the training process to bet- ter study our incremental manner to apply the clustering assignments.
4.3 EFFECT OF FALSE NEGATIVE SAMPLES
Experimental Setup. To study the effect of false negatives self-supervised contrastive learning. we compare three representative frameworks, including SimCLR (Chen et al., 2020b) as instance- level learning, SupCon (Khosla et al., 2020) as supervised learning using label information com- pletely exclude the false negatives, and our method. For a fair comparison, we reproduce SimCLR and SupCon by using the same data augmentations and network architecture (i.e., ResNet-50 with 3-layer MLP). We also apply momentum feature bank in this section. Considering that the probability of sampling false negatives in training mini-batch I is largely determined by the number of semantic classes, we conduct the experiments on CIFAR (Krizhevsky et al., 2009) and ImageNet (Deng et al., 2009) with different WordNet (Miller, 1 1998) lexical hierarchy to
M-CCR--basee implementation for our method without maintaining
numbers of object categories. For ImageNet, define the semantic classes in different depths, as detailed in Appendix D. We then train and perform the linear evaluation for three frameworks on each dataset and report the results in Table 5.

---

Published as a conference paper at ICLR 2022
Table 6: Different strategies for pseudo label assignment and false negative removal on CIFAR- 100. We report MTPR (%, f) and MTNR (%, 1) of k-means clustering (k = 100) and the Top-1 classification accuracy (%). Note that, [a] the instance-level learning: [b] and [c] uses the strategy in DeepCluster (Caron et al., 201 8) and PCL (Li et al., 2021) (Step scheme starts to use the pseudo labels after 100th epoch over 1000 training epochs); [g] is the final setting of the proposed method.
Acceptance Rate of Pseudo Label
Index
Objective
MTPR
MTNR
Top- Acc.
Scheme
Initial
Final
[a]
Constant
0% 100%
0%
Linst
0
100
71.5
[b]
Constant
100%
Lelem
31.7
99.09
71.3
[c]
Step
0%
100%
Litim
40.0
99.42
73.1
[d]
Linear
0%
25%
Celim
15.3
99.98
72.5
[e]
Linear
0%
50%
Lisem
26.2
99.89
73.0
[f]
Linear
0%
75%
Cetim
36.0
99.78
73.5
[g]
Linear
0%
100%
Letem
43.3
99.65
74.0
[h]
Linear
0%
100%
Catte
28.6
98.91
70.2
Based on the performance drops of SimCLR compared to SupCon (A(SupCon, SimCLR) in Ta- ble 5), we observe that the adverse effect of false negatives is more sigmificant on the datasets with more object categories, although they are less likely to sample false negatives during contrastive learning. Similar results are observed on both CIFAR and ImageNet. The results convey an issue of vanilla instance-level contrastive learning when it applied to datasets with more complex semantic concepts. With the explicit elimination of the detected false negatives, IFND effectively narrows the gap between self-supervised and supervised frameworks, numerically reducing 51.7% of the gap between SimCLR and SupCon ImageNet with original labels (i.e., Depth 18).
4.4 STRATEGY FOR FALSE NEGATIVE DETECTION AND REMOVAL
In this section, we first introduce comprehensible evaluation metric for clustering assignment and then present the quantitative study on different strategies to utilize the clustering labels to remove the detected false negatives. The results on CIFAR- 100 are shown in Table 6.
More interpretable metric for clustering performance. Considering that the pseudo labels are used to detect false negatives, we propose Mean True Positive/Negative Rate (MTPR/MTNR) to evaluate the clustering. MTPR the average probability that an actual false negative (i.e., an actual positive) will be detected as a false negative sample, while MTNR indicates the average probability that an actual negative is still treated as a negative sample. Taking the instance-lewe contrastive learning as toy example, it does not perform false negative detection, so MTPR is 0% while MTNR 100%. The goal is to increase MTPR of the clustering but keep MTNR as high as possible.
Strategies for pseudo label assignment. First, compare three schemes determine the accep- tance rate of the pseudo labels, including constant ([b], as in DeepCluster (Caron et al., 2018)), step ([c). as in PCL (Li al., 2021)), and linear (Ig), Ours) schemes. The linear strategy achieves both higher MTPR and MTNR. The results validate that using the clustering indices in an incremental manner can find the false negatives more effectively and further improve the performance of con- trastive learning. Next, we analyze the effect of using different final acceptance rates for the linear strategy (ld.e.f.g)). Intuitively, higher acceptance rates indicate more false negatives can be detected (MTPR increases), but more true negatives are also improperly treated as false negative samples and removed (MTNR decreases). However, we find that using the 100% final acceptance rate ([g]) can averagely detect nearly half (43.3%) of the actual false negatives with only slight drop (0.35% of MTNR compared to the lestance-level approach ([a]). Along with the elimination loss, we improve the downstream Top-1 classification accuracy from 71.5% to 74.0%.
Strategies for false negative removal. Finally, we compare the elimination and attraction losses ([g.h)). We find that the representation learning through minimizing Lattr are unstable and rely on the high-quality pseudo labels at the early training stages. This observation can be explained by the theoretical analysis in Section 3.3 indicating that Lattr applies more aggressive strategy that would be more sensitive to noisy pseudo labels. Empirically, we observe that the model supervised by Lutte performs even worse than the instance-level learning.
8

---

Published as a conference paper at ICLR 2022
100th epoch
500 epoch
1000 epoch
Figure 3: Visualization of embedding spaces and pseudo label assignments in different training stages on CIFAR-10. The samples in the upper and lower row are respectively colored with the ground truth labels and the assigned pseudo labels. * marks are the cluster centroids, and light grey dots represent the instances without the assigned pseudo labels.
(a) SimCLR
IFND (Ours)
(c) SupCon
Figure 4: Visualization the embedding spaces learned by different methods on CIFAR- R-10.
4.5 VISUALIZATION EMBEDDING SPACE
In Figure 3, we visualize the embedding spaces and corresponding pseudo label assignments in dif- ferent training stages using t-SNE (Van der Maaten & Hinton, 2008). In the early stages (c.g., 100th epoch), the semantic structure of the embedding space is still under-developed. Hence, IFND only adopts a small portion of pseudo labels with higher confidence scores. Later in the training process, with the better-trained encoder and more semantically structural embedding space, incrementally including more high-quality pseudo labels can benefit the semantic-aware representation learning. Finally, compare the embedding spaces learned through SimCLR, SupCon, and approach in Figure 4. IFND can learn the embedding space with more compact clusters than the instance-level learning and is also more similar the supervised framework. We present quantitative analysis in Appendix F and also provide more visualizations and discussions in Appendix G.
5 CONCLUSION
In this work, we analyze the undesired effects of false negatives for self-supervised contrastive learning. To mitigate such adverse effects, we then introduce an incremental false negative detection approach to progressively detect and remove the false negatives through the training stage. Extensive experiment results validate the effectiveness of the proposed framework on several benchmarks and also demonstrate the capability reduce the gap from the supervised framework.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENTS
This work is supported in part by the NSF CAREER grant 1149783.
REFERENCES
Yuki Markus Asano, Christian Rupprecht, and Andrea Vedaldi. Self-labelling via simultaneous clustering and representation learning, In International Conference on Learning Representations, 2020. 3,
Mathilde Caron, Piotr Bojanowski, Armand Joulin, and Matthijs Douze. Deep clustering for unsu- pervised learning of visual features. In European Conference on Computer Vision, 2018. 3, 6, 7,
Mathilde Caron, Piotr Bojanowski, Julien Mairal, and Armand Joulin. Unsupervised pre-training of image features on non-curated data. In IEEE International Conference on Computer Vision, 2019. 3
Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin. Un- supervised learning of visual features by contrasting cluster assignments. In Advances in Neural Information Processing Systems, 2020. 6,
Mark Chen, Alec Radford, Rewon Child, Jeffrey Wu, Heewoo Jun, David Luan, and llya Sutskever. Generative pretraining from pixels. In International Conference Machine Learning. 2020a. I
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International Conference Machine Learning, 2020b. 1, 2, 3, 7, 15, 16, 17
Ting Chen, Simon Kornblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey E Hinton. Big supe-supe models are strong semi-supervised learners. In Advances in Neural Information Processing Systems, 2020c. 1,2
Xinlei Chen, Haoqi Fan, Ross Girshick, and Kaiming He. Improved baselines with momentum contrastive learning. arXiv preprint arXiv:2003.0429) 2020d. 1, 2, 5, 6, 7, 15
Ching-Yae Chuang, Joshua Robinson, Yen-Chen Lin, Antonio Torralba, and Stefanic Jegelka. De- biased contrastive learning. In Advances in Neural Information Processing Systems, 2020.
Florence Corpet. Multiple sequence alignment with hierarchical clustering, Nucleic Acids Research, pp. 10881-10890, 1988. 4
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In IEEE Conference on Computer Vision and Pattern Recognition, 2009. 5, 6, 7, 15
Carl Doersch, Abhinav Gupta, and Alexei A Efros. Unsupervised visual representation learning by context prediction. In JEEE International Conference on Computer Vision, 2015. 1
Alexey Dosovitskiy, Philipp Fischer, Jost Tobias Springenberg. Martin Riedmiller, and Thomas Brox. Discriminative unsupervised feature learning with exemplar convolutional neural networks. IEEE Transactions Pattern Analysis and Machine Intelligence, pp. 1734-1747, 2015. 2
Mark Everingham, Lue Van Gool, Christopher KI Williams, John Winn, and Andrew Zisserman. The pascal visual object classes (voc) challenge. International Journal of Computer Vision, pp- 303-338, 2010.
Spyros Gidaris. Praveer Singh, and Nikos Komodakis. Unsupervised representation learning by predicting image rotations. In International Conference on Learning Representations, 2018. 1,
Ross Girshick, Ilija Radosavovic, Georgia Gkioxari, Piotr Dollár, and Kaiming He. Detectron. com/ cotm///ccbboooeeeerrceeeeeeee
2018. 7
10

---

Published as a conference paper at ICLR 2022
Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, Elena Buchatskaya, Carl Doersch, Beraardo Avila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, Bilal Piot, koray kavukcuoglu, Remi Munos, and Michal Valko. Bootstrap your own latent: A new approach to self-supervised learning. In Advances in Neural Information Processing Systems, 2020. 6
Michael Gutmann and Aapo Hyvärinen. for unnormalized statistical models. In International Conference on Artificial Intelligence and Statistics, 2010. 16
estimation: new estimation principle
Ben Harwood, Vijay Kumar BG, Gustavo Cameiro, Ian Reid, and Tom Drummond. Smart mining for deep metric learning. In IEEE International Conference Computer Vision, 2017. 13
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In IEEE Conference on Computer Vision and Pattern Recognition, 2016. 5, 6, 15
Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick. Mask r-cnn. In IEEE International Conference on Computer Vision, 2017.
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In IEEE Conference on Computer Vision and Pattern Recognition, 2020. 1, 3, 5, 6, 15
R Devon Hjelm, Alex Fedorov, Samuel Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. In International Conference on Learning Representations, 2019. 1,2
Karan Grewal, Phil Bachman, Adam
Tri Huynh, Simon Korbblith, Matthew R Walter, Michael Maire, and Maryam Khademi. Boost- ing contrastive self-supervised learning with false negative cancellation. arXiv preprint arXiv:2011.11765. 2020. 3
Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with gpus. IEEE Transactions on Big Data, 2019. 5
Stephen Johnson. Hierarchical clustering schemes. Psychometrika, pp. 241-254, 1967. 4
Prannay Khosla, Piotr Teterwak, Chen Wang, Aaron Sarna, Yonglong Tian, Phillip Isola, Aaron Maschinot, Ce Liu, and Dilip Krishnan. Supervised contrastive learning. In Advances in Neural Information Processing Systems, 2020. 2, 3. 7.
Jack Kiefer, Jacob Wolfowitz, et al. Stochastic estimation of the maximum of regression function. The Annals of Mathematical Statistics, 1952. 15
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009. 5, 7, 15, 16
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in Neural Information Processing Systems, 2012. 6
Junnan Li, Pan Zhou, Caiming Xiong, and Steven Hoi. Prototypical contrastive learning of unsuper- vised representations. In International Conference on Learning Representations, 2021. 3, 4, 5, 6, 7, 15, 16
Tsung- Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick. Microsoft coco: Common objects in context. In European Conference on Computer Vision, 2014. 6,7
Ilya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts. arXiv preprint arXiv:1608.0394 2016. 15
George A Miller. WordNet: An electronic lexical database. MIT press, 1998. 7, 15
Ishan Misra and Laurens van der Maaten. Self-supervised learning of pretext-invarian representa- tions. In IEEE Conference Computer Vision and Pattern Recognition, 2020. 2,

---

Published as a conference paper at ICLR 2022
Fionn Murtagh and Pierre Legendre. Ward's hierarchical agglomerative clustering method: which algorithms implement ward's criterion? Journal of Classification, pp. 274-295, 2014. 4
Mehdi Noroozi and Paolo Favaro. Unsupervised learning of visual representations by solving jigsaw puzzles. In European Conference on Computer Vision, 2016. 1,
Hyun Oh Song. Yu Xiang, Stefanie Jegelka, and Silvio Savarese. Deep metric learning via lifted
structured feature embedding. In IEEE Conference on Computer Vision and Pattern Recognition, 2016. 13
Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predic- tive coding. arXiv preprint arXiv: 2018. 1,
Deepak Pathak, Philipp Krahenbuhl, Jeff Donahue, Trevor Darrell, and Alexei A Efros. Context encoders: Feature learning by inpainting. In IEEE Conference on Computer Vision and Pattern Recognition, 2016. 1
Nikunj Saunshi, Orestis Plevrakis, Sanjeev Arora, Mikhail Khodak, and Hrishikesh Khandeparkar. A theoretical analysis of contrastive unsupervised representation learning. In International Con- ference on Machine Learning, 2019. 1,3
Florian Schroff, Dmitry Kalenichenko, and James Philbin. Facenet: A unified embedding for face recognition and clustering. In IEEE Conference on Computer Vision and Pattern Recognition, 2015. 5,5
Alexander Strehl and Joydeep Ghosh. Cluster ensembles-a knowledge reuse framework for com- bining multiple partitions. Journal of Machine Learning Research, 2002. 7. 17
Yonglong Tian, Dilip Krishnan, and Phillip Isola. Contrastive multiview coding. arXiv preprint
1eX1::1906.0589, 2019. 1. 2. 6
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of Machine
Learning Research, 2008. 9
Chao- Yuao Wu, R Manmatha, Alexander J Smola, and Philipp Krahenbuhl. Sampling matters in deep embedding learning. IEEE International Conference on Computer Vision, 2017. 13
Zhirong Wu, Yuanjun Xiong, Stella X Yu, and Dahua Lin. Unsupervised feature learning via non- parametric instance discrimination. In IEEE Conference Computer Vision and Pattern Recog- nition, 2018. 2,
Junyuan Xie, Ross Girshick, and Ali Farhadi. Unsupervised deep embedding for clustering analysis. In International Conference on Machine Learning, 2016. 3
Jianwei Yang, Devi Parikh, and Dhruv Batra. Joint unsupervised learning of deep representations and image clusters. In JEEE Conference on Computer Vision and Pattern Recognition, 2016. 3
Mang Ye, Xu Zhang, Pong C Yuen, and Shih-Fu Chang. Unsupervised embedding learning via invariant and spreading instance feature. In IEEE Conference on Computer Vision and Pattern Recognition, 2019. 2
Xiaohua Zhai, Avital Oliver, Alexander Kolesnikov, and Lucas Beyer. S41: Self-supervised semi- supervised learning. In IEEE International Conference on Computer Vision, 2019. 6
Bolei Zhou, Agata Lapedriza, Jianxiong Xiao, Antonio Torralba, and Aude Oliva. Learning deep features for scene recognition using places database. In Advances Neural Information Process- ing Systems, 2014. 6
Chengxu Zhuang, Alex Lin Zhai, and Daniel Yamins. Local aggregation for unsupervised learning of visual embeddings. IEEE International Conference on Computer Vision 2019. 3,
12

---

Published as a conference paper at ICLR 2022
A THEORETICAL ANALYSIS FOR ELIMINATION AND ATTRACTION LOSSES
In this section, we show the derivation of the gradients of two discussed objective functions: elimi- nation loss Letim (Equation 3) and attraction loss Lattr (Equation 4). Furthermore, we demonstrate that they have the inherent capability hard sample mining (Oh Song al., 2016; Harwood al., 2017; Wu et al., 2017). Without loss of generality, we use to represent an arbitrary anchor image, and re- ve-write the two losses as:
exp(z; ZT/T) Lelim,i log Σ explz1 : 2,/T)²
S(i) = (i'm n E (V), Ua + vii and (6)
#ES(()
exp(zi 2p/T)
S(i) = (V,n n N()) P(i) = (i,n n (f)1. yi
Lattr. =
Σ
log Σ exp(z; 2x/T)
[P(1)
PEP(()
+ES(()
We then derive the gradient of Letim, with regard to the embedding of the anchor image 2;:
exp(z, Z2/T)
log
Ozi
0z:
Σ exp(2i 2x/T)
sES(1)
log Σ
exp(zi 2x/T)
log log(exp(2z: 22/ 2x/T))
Oz:
0z.
+ES(()
Σ
exp(z; 2//T)
2
Zi'
Σ exp(zi: 23/T)
#ES(i)
(8)
(ES(()
Σ
explzi Tx/T)
Zn
1
exp(zi 22 22/T)
2e
Σ exp(2; 2x/T)
Σ exp(zi 2z/T)
())
BES(()
sES(()
Σ
Zn
2i1
T
(EN
where
exp(zi Zz/T)
$im, Z,, 2x)
0 Σ exp(z; 23/T)
and
sim [2) 2a)
8ES(1)
+ES(()
exp(z: #x/T)
sim (x)
1
Σ
exp(zi 2z/T)
Σ sim (zi 2a)
SES(6)
$ES())
the coefficient terms respectively for the negative positive sample r.
13

---

Published as a conference paper at ICLR 2022
Next, the gradient of Lattr, is derived in similar way:
1atttri
0
exp(z; 2p/T)
Σ
log
Ozi
Oz:
IP(i)
Σ exp(zi 2z/T)
PEP(1)
SES(1)
0
log Σ RES(1)
exp(z; : 23/T)
log exp(z; 2p/T)
P(t)
Ozi
Oz:
pEP(i)
1
Σ PEP(1)
Σ
exp(zi 2z/T)
2
2p
P(()
Σ exp(zi 2g/T)
7
$ES())
8ES(L)
Σ
exp(zi 2,/T) Σ exp(z; 2s/T) (ES(()
2s
Σ
1 [(()]
2p
(10)
+ES())
PEP())
exp(zi 2n/T)
Σ
Σ exp(z; 2x/T) #ES(1)
(t)()).
Σ
1
exp(2; xp/T
32
[P(i)
Σ expl2i 2s/T)
7
PEP(O)
SES(1)
Σ
Tn 2n
p 2p.
IE)())
PEP(()
He, #th
where
0 = exp(zi 2x/T)
sim Zi, zz)
and
Σ
exp(z: 20/T)
Σ
sim(2i 20)
SES(I)
sES(1)
(11)
exp(z; /x/TT)
sim Zi, 2n.
at
P(()
exp(z: (2) 2x/T)
IP(1)]
Σ
sim [2 2.)
SES())
sES(()
Note that the coefficient terms of and o. in Equation 9 and 11 are determined by sim(z;; 2n). Larger coefficients are given when negative/positive samples are relatively more similar/dissimilar to the anchor. This observation indicates that these two loss functions have the implicit capability of hard sample mining, i.c., focusing on differentiating the "hard negatives" that are near the anchor and attracting the "hard positives" which are far away from the anchor.
14

---

Published as a conference paper at ICLR 2022
B PSEUDO CODE
Algorithm 1: Contrastive Learning with Incremental False Negative Detection
Input: encoder f. projection head g, training samples X, and number of clusters k // cesstanneelevve contrastin
learning at the beginning
Initialize completely different pseudo labels y" for each sample while Epoch E Training Epoch do
// contrastive learning with false se negative elimination
for mini-batch I do
= = g(f(ti~) ~ I})
update encoder f and projection head g minimize Letim (z,1") end
Epoch E Clustering Epoch then
// pseudo label assignment
5(1x X))
y. = k-means( v. k)
simm2, cy)/ Ej si)
11
determine the acceptance rate of the pscudo label as (Epoch Training Epoch) update pseudo labels y" by a part of y with larger
12
13
end
14 end
C PRE-TRAINING AND EVALUATION DETAILS
As described in Section 4.1, we use the proposed method pre-train ResNet-50 (He al., 2016) on ImageNet (Deng et al., 2009), CIFAR-I0, and CIFAR-100 (Krizhevsky et al., 2009). For ImageNet pre-training, we follow the setting of previous work (He et al., 2020; Chen et al., 2020d) that uses SGD optimizer (Kiefer et al., 1952) with a weight decay of 0.0001 and a momentum of 0.9. The learning rate is set to 0.03 initially and then multiplied by 0.1 120 and 160 epochs. For CIFAR-10 and CIFAR- 100 pre-training, we train the encoder for 1000 epochs with mini-batch size of 1024. Because of the larger mini-batch size, we implement our framework based on SimCLR (Chen et al., 2020b) structure without maintaining memory bank for the momentum instance features. We also use SGD optimizer with the same weight decay and momentum. But, we set the initial learning rate 0.5 and
linear warm-up strategy for the first 10 epochs. In the rest of the training, decay the learning rate with the cosine annealing schedule (Loshchilov & Hutter, 2016). For pseudo label assignment, we re-assign the pseudo labels after every 20 training epochs (due to more training epochs and fewer training images) for CIFAR and also use three cluster numbers, {10, 30, 100) for CIFAR-10 10 and {100, 300, 1000) for CIFAR-100. to hierarchically define semantic concepts.
For linear evaluation on ImageNet, we train the classifier (a fully connected layer followed by soft- max) with the fixed pre-trained representations for 100 epochs. Following the same hyper-pal prrrm-par setting used in MoCo v2 (Chen et al., 2020d) and PCL (Li et al., 2021), we optimize the model by SGD optimizer with batch size of 256, an initial learning rate of 10, momentum of 0.9, and weight decay of O. As for semi-supervised learning, we fine-tune the pre-trained ResNet-50 model and the classifier using the subsets 1% or 10% ImageNet labeled training data (note that we use the same subsets of ImageNet training data as in SimCLR). The model is trained using SGD opti- mizer for 20 epochs, a batch size of 256, a momentum of 0.9, and a weight decay of 0.0005. The learning rate for ResNet-50 is 0.01 while the one for the linear classifier is 0.1 (for 10% ImageNet) or (for 1% ImageNet). All learning rates are multiplied by 0.2 at 12nd and 16th epochs.
D HIERARCHICAL CLASS DEFINITION FOR IMAGENET
Based on WordNet (Miller, 1998) lexical database, we use the corresponding synset IDs to represent original 1000 classes in ImageNet and recursively trace the "hypernyms" (parent synset) for each class until the coarsest synset, "entity", in WordNet. Then, synset as the root, the synsets original classes as the leaves, and the relations of hypernym or hyponym the edges. We then re-define the semantic class with different granularities in different
construct the tree structure with entity
15

---

Published as a conference paper at ICLR 2022
Whole
Whole
Whole
Whole
Whole
Sign
Organism
Organism
Organism
Organism
Instrumentality
Street Sign
Chordate
Chordate
Chordate
Invertebrate
Vehicle
Street Sign
Mammal
Mammal
Aquatic Vertebrate
Gastropod
Warship
Street Sign
French Bulldog
Shetland Sheepdog
Goldfish
Snail
Aircraft Carrier
Street Sign
Figure 5: Hierarchical semantic concepts for ImageNet. We show six images and their respective class labels hierarchically defined Depth {3, 5, 7, 9, 18} from top bottom. Depth 18 (the bottommost) uses original class labels in ImageNet.
Table 7: Ablation comparison with PCL (Li et al., 2021) on CIFAR-100. indicates the baseline model. We mark the component which is different from the baseline in red and compute the perfor- mance gaps to the baseline. The implementation of ProtoNCE and confidence estimation in PCL are directly from the official repository.
Pseudo Label Assignment
Numbers of Clusters (x 100)
Confidence Estimation
Top-1 Acc. (%)
Method
Objective
SimCLR
Linet
Constant
71.5
PCL.
ProsONCE
Step
[25, 50, 50, 100} {1,3, 10)
Eq. 9 in PCL.
72.8
IFND (Ours)
Letim
Linear
Eq.
74.0
PCL IFND
Lesim
Step
50, 100}
Eq. in PCL
73.1 (0.31)
CrrotoNCE
Linear
{1,3, 10)
Eq.
73.4 (0.6.)
PCL IEND
LProtNNCE Letim
Linear
{25,50, 50, 100} {1,3,
Eq. 9 in PCL Eq.
73.5 (0.71)
Step
73.1 (0.94)
PCLÍ
LProtONCE
Step
{1,3, 10} (25,50, 100}
Eq. 9 in PCL
69.9 (2.94)
IFND
Letim
Linear
Eq.
73.2 (0.84)
IFND
Ledimm
Linear
{1,3, 10)
Eq. 9 in PCL.
71.2 (2.84)
depths of the tree. In Section 4.3, we employ the datasets defined in Depth (, 5, 7, 18). Here, we show some example images with the semantic classes defined these depths Figure 5.
E IN-DEPTH ABLATION COMPARISON WITH PCL
Here, we provide an ablation comparison with PCL (Li et al., 2021) in terms of objective function, 2) pseudo label assignment, 3) numbers of clusters, and 4) confidence estimation. The experimental setup is the same as in Section 4.3. Briefly, we re-implement PCL and our IFND with SimCLR (Chen et al., 2020b) based implementation and evaluate the frameworks on CIFAR-100 (Krizhevsky et al., 2009). The results are reported in Table 7.
Objective function. applies LProtoNCE which includes instance-level infoNCE, loss (Gutmann & Hyvärinen, 2010), i.c., Linsts and would suffer from the false negative effect. In contrast, IFND applics Letim that explicitly climinates the detected false negatives from negative sample set (as proven in Section 3.3) and performs favorably against LriotoNCE.
Pseudo label assignment. For the utilization of clustering indices, PCL uses Step scheme that first warms up the framework by instance-level learning and adopts all indices afterward. On the other hand, IFND progressively includes increasing confident labels, which better fits the gradually well-trained encoder (as demonstrated in Appendix F).
16

---

Published as a conference paper at ICLR 2022
75
Normalized Mutual Information
65
55
Linear (0%%-000%
45
Constant (0%)
Constant (100%)
35
100
200
300
400
500
600
700
800
900
1000
Epoch
Figure 6: Clustering quality in different training stages on CIFAR-100. We train the model with three different strategies to determine the acceptance rate of pseudo labels and measure the quality of h-mmans clusterings (k: 100) on the embedding spaces during the training process.
Numbers of clusters. The performance of the PCL approach degrades significantly when the num- ber of clusters becomes smaller while the proposed method is more robust to the number of clusters. It worth mentioning that with smaller numbers clusters, PCL performs similarly to the attraction strategy (69.9% versus 70.2% as in Table 6).
Confidence estimation. PCL estimates a single confidence score for the instances within the same cluster. On the contrary, method computes the confidence score for each individual instance and also refers to the centroids of other clusters for the estimation. As result, the representation learning with confidence estimation performs more favorably.
F CLUSTERING QUALITY THROUGH TRAINING PROCESS
In this section, we measure the clustering results in different training stages to first verify the claim that the clusterings comparably unreliable in the early training stages and also study the practi- cal effect of our incremental manner to adopt clustering indices. We compute Normalized Mutual Information (Strehl & Ghosh, 2002) between the ground truth labels and the clustering indices of all training images and plot the results in Figure 6.
We can observe that following the training, the clustering is gradually improved and becomes better to reflect the semantic relationship among images. Hence, for the model that consistently uses all pseudo labels (green line in Figure 6), the earlier inferior labels would disturb the training. In con- trast, the proposed model (blue line in Figure 6) progressively applies increasing high-quality labels that can benefit semantic-an aware learning and finally achieve both better representation learning and clustering as in Table 6 and Figure 6.
G VISUALIZATION OF EMBEDDING SPACE THROUGH TRAINING PROCESS
In this section, we visualize and compare the embedding spaces learned by four contrastive learning frameworks, including (a) SimCIR (Chen et al., 2020b), (b) IFND (trained by Letim), (c) IFND (trained by Lattr), and (d) SupCon (Khosla al., 2020), through the training process in Figure
Compared to IFND trained by Letim, the one trained by Latte learns the embedding space with more concentrated clusters, which are more similar SupCon due to using similar attraction objective function. However, during training, the unsupervised clustering would inevitably produce some noisy pseudo labels (as supported by the MTNR Table 6 being less than 100%). Consequently. the attraction loss may inappropriately pull actual negative samples closer to the anchor. We can then find that although the embedding space in the rightmost of Figure 7(c) shows more concentrated clusters, nonetheless, cluster is not constituted by the image embeddings of the semantic
17

---

Published as a conference paper at ICLR 2022
(a) SimCLR (Linst
(b) IFND (Celim)
(c) IFND (Cartr)
(d) SupCon (Caur)
100th epoch
500 epoch
1000 epoch
Figure 7: Visualization of embedding spaces CIFAR-10. We compare four contrastive learning frameworks based on their embedding spaces through the training process. We list their objective functions in the bracket.
content. Also, as shown in Table 6, the attraction loss leads to inferior representation performance compared to the elimination objective.
For the final proposed method, i.e., IFND trained by Latim. it learns similar embedding space as SimCLR in the early stage since the acceptance rate for assigning the pseudo label is still low. Following the training process, with increasing reliable pseudo labels, the proposed framework ef- fectively bridges the instance-level and semantic-aware representation learning and learns a more favorable embedding space against SimCLR.
18


Reviews:
[{"review_id": "urcnYCQAOkM", "reviewer": "Reviewer_T8CE", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Pros\n\n- Clear motivation over the prior work and a simple yet effective solution.\n- Nice details on the method, e.g., linear scheduling of the acceptance rate, to be hyperparameter-free.\n- Nice experimental setup, e.g., comparing with SimCLR and SupCon to provide lower and upper bounds.\n\n\n### Cons/concerns\n\n1. Limited novelty and inappropriate credit for PCL\n\nThe proposed method is somewhat incremental over the prior work, PCL. As PCL develops the core concept of pseudo-label-based contrastive learning, the paper should clearly illustrate the contribution of prior work and its novel innovations. While the paper briefly introduces PCL in the related work section, the paper should clearly state PCL as the preliminary in the main method section.\n\nFor example, the \"hierarchical semantic definition\" part of the paper (page 4) suggests using multiple clusters to consider the different hierarchy levels. However, this technique was already introduced in the original PCL paper (Eq. (11)).\n\n\n2. Ablation study on the difference from PCL\n\nPutting aside omitting uncertain pseudo-labels, IFND has several minor differences from the PCL. After clearly stating the differences, the paper could provide the ablation study for each modified component, e.g.,\n- Confidence of pseudo-label: One may use Eq. (9) of PCL instead of the proposed Eq. (2), although the latter seems to be better as the former does not consider different classes.\n- Number of clusters: The original PCL used {25000,50000,100000} but INFD uses {1000,3000,10000}. It can be unfair since the desired number of clusters are 1000 for ImageNet.\n\n\n3. Comparison with other cluster-based (and other self-supervised) methods\n\nTable 1 suggests that SwAV, another cluster-based method, performs the best. While the paper only verifies the merit over its predecessor, PCL, the empirical contribution could be limited if it underperforms than other self-supervised methods. Thus, the paper should compare IFND with SwAV for all experiments, under the same setup (e.g., 200 epochs).\n\nWhile BYOL is not cluster-based method, it does not suffer from the suggested false negative issue, which weaken the motivation of this work. The paper could also verify the advantages over the BYOL to strengthen the desirability of proposed method.\n\n\nMinor comments:\n- While the paper introduces two losses: elimination and attraction, the paper concludes that elimination is better for considered scenarios. The paper could mainly introduce the single final method and leave the inferior one for the discussion.\n- The definition of false negative $\\mathcal{N}(i)$ could be introduced before it is used in Eq. (3).", "summary_of_the_paper": "The paper proposes incremental false-negative detection (IFND), which has several improvements over prototypical contrastive learning (PCL). The key idea of PCL is to alternatively update (a) the pseudo-labels based on the current encoder and (b) update the encoder based on the current pseudo-labels. However, PCL often converges to the local minima since the bad encoder produces falsy pseudo-labels, further harming the encoder. To tackle the issue, INFD suggests including the confident pseudo-labels while uncertain ones incrementally. IFND consistently improves the PCL in all considered scenarios.", "summary_of_the_review": "The paper proposes a solid yet somewhat incremental modification from the prior work, PCL. Overall, I think the paper is on the boarderline. I'm willing to raise my score if my concerns: (a) improper credit for PCL, (b) ablation study over PCL, amd (c) comparison with SwAV/BYOL are addressed.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "hw0g1V0WZPg", "reviewer": "Reviewer_7ZtC", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1) The paper is easy to follow with clear motivation. The discussion and analysis about “false negatives” on contrastive learning in Fig1 is quite valuable. \n2) The authors justify the effectiveness of the proposed method according to the extensive evaluations. Besides, the ablation study also validates the contribution of the main component of the proposed IFND.\n\nWeaknesses:\n1) The technical novelty of the proposed method is somewhat marginal since some of its main components (i.e., hierarchical semantic definition) have already been mentioned in PCL (Li et al., 2021). The authors should present more detailed analyses and discussions to highlight the difference between PCL and their proposed IFND. For instance, it will be better if the authors can conduct experiments on the object detection task to demonstrate the consistently superior performance of IFND over PCL. \n2) The acceptance rate of the pseudo label is determined without careful consideration. According to Appendix B, the authors empirically set the acceptance rate in a hyperparameter-free manner (i.e., Epoch / Training Epoch). This might make the learning process unstable due to the accumulated pseudo-labeling errors. It might be better if the authors can explore some robust learning techniques (e.g., self-paced learning) to improve learning efficiency.\n3) It seems that the experiment results do not validate the effectiveness of the introduced attraction strategy according to Table 5.", "summary_of_the_paper": "Briefly, this paper presents a simple yet effective method (i.e., IFND) for self-supervised contrastive learning by effectively handling the false-negative samples. Specifically, the authors propose to cluster samples in the embedding space and assign the cluster indices as pseudo labels in an incremental manner during training. The experimental results are extensive and demonstrate the effectiveness of the proposed method.", "summary_of_the_review": "This paper introduces some interesting insights for contrastive learning. However, its presentation and experiment design could be improved. I will raise my rating if most of my concerns have been well addressed.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "I2FmeR4KrUt", "reviewer": "Reviewer_qg7u", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: \n1) Well written and easy to follow paper with a very solid hypothesis and analysis of effects of “false negatives” on contrastive learning.\n2) They have shown good results specially under classification settings in both supervised learning and semi-supervised learning setups.\n3) Table4 shows really good analysis and shows how increasing the depth results in more and more poor performances. \n4) Better clustering results than SWaV: Table 3 results are very promising as they show that IFND achieves better NMI results than SWaV and MoCo-V2. This means that IFND is really able to form better clusters and show improved performances.\n\nWeakness:\n1) Results on BYOL and other non-contrastive methods: The method would be much more comprehensive if this method can be extended to other non-contrastive methods such BYOL as well. Recently BYOL and other non-contrastive methods are showing much more promise than contrastive methods. Hence changing the loss function using similar motivation from IFND would be really good to see. \n2) Object-Detection and Semantic Segmentation results on COCO/VOC: I couldn't find any results on object detection or segmentation. Adding those results would make the paper more complete.\n3) Another interesting result would be to see the performance of IFND by pre-training on the COCO dataset. ImageNet in a way is already clustered and finding close “false negatives” would be easier on ImageNEt as compared to COCO. Results by pre-training on COCO would make the method much more convincing.\n", "summary_of_the_paper": "This paper deals with the very important topic of “false negatives” in SSL and shows that “false negatives” have a huge impact on performance of SSL methods. One of the most interesting experiments they show is that as they increase the number of classes in the dataset the performance drops more and more. They propose a clustering based method which reduces the  “false negatives” and shows improved performances as compared to other state-of-the-art baselines.\n", "summary_of_the_review": "I like the idea used in the paper and analysis shown in the paper. However lack of results on object detection and semantic segmentation coupled with lack of results using BYOL method, I'm leaning towards borderline rejection. Adding these results would make the paper stronger.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: While the reviewers were somewhat split on this paper, they all found some strengths, and pointed out some weaknesses. Among these the main seems to be the somewhat incremental nature of the work, in particular with respect to PCL. As the authors point out, the differences w.r.t. PCL are meaningful and include the main thrust of the paper (removal of false negatives), and the results do indicate usefulness of the proposed approach. Given the wide interest in self-supervision I think the paper is above bar for acceptance.
Decision: Accept (Poster)