summaries: This paper proposes a method to detect noisy labels given good representations (e.g., ones pre-trained by contrastive learning approaches).  The proposed noisy-label detection method uses  the neighborhood information defined by a good set of representations in two ways:   1) checks the noisy label consensuses of nearby representations  2) scores each instance by its likelihood of being clean and filters out a guaranteed percentage of instances with low scores as corrupted ones   The work provide definitions for good representation and further proves a worst-case error bound for the ranking-based method given a 'good enough' representation. It also provides empirical results for its proposed method.

summaries: This paper proposed a training-free solution by using only good representations to detect noisy labels. The author designed two detection methods of voting and ranking to filter instances that are likely to be corrupted. The major contribution is proposing a training-free solution to efficiently detect noisy labels, which is different from most current methods. Also, theoretical analysis is conducted on the worst-case error bound and the choice of K.

summaries: The authors propose a training-free approach to detect samples with noisy labels by leveraging representations learned from pre-trained models. The models can be obtained by either supervised or self-supervised pre-training. The authors then argue that samples in the pre-trained manifold should be closer if they share the same clean label, therefore one can use (a) local voting or (b) ranking methods to detect samples with corrupted labels. Experiments on CIFAR10/100 show improvement over other learning-based approaches (CORES, CL, TracIn).

summaries: The paper proposes a training-free instancewise noise label detection method. The main motivation of this paper is the observation that deep models generalize poorly because memorizing noisy labels in supervised training while using only representations may avoid this issue.  The authors suppose a good representation extractor is given and generate the initial soft labels based on the clusterability of representations using kNN. Followed by that,  they perform a local voting and global ranking-based scoring system to detect the corrupted labels. The main contribution of this paper is: It introduces a representation-based method instead of directly training a deep model on the corrupted data, which is more efficient and may avoid overfitting noisy labels.

abstractText: Label noise is pervasive in real-world datasets, which encodes wrong correlation patterns and impairs the generalization of deep neural networks (DNNs). It is critical to find efficient ways to detect the corrupted patterns. Current methods primarily focus on designing robust training techniques to prevent DNNs from memorizing corrupted patterns. This approach has two outstanding caveats: 1) applying this approach to each individual dataset would often require customized training processes; 2) as long as the model is trained with noisy supervisions, overfitting to corrupted patterns is often hard to avoid, leading to performance drop in detection. In this paper, given good representations, we propose a universally applicable and training-free solution to detect noisy labels. Intuitively, good representations help define “neighbors” of each training instance, and closer instances are more likely to share the same clean label. Based on the neighborhood information, we propose two methods: the first one uses “local voting” via checking the noisy label consensuses of nearby representations. The second one is a ranking-based approach that scores each instance and filters out a guaranteed number of instances that are likely to be corrupted, again using only representations. Given good (but possibly imperfect) representations that are commonly available in practice, we theoretically analyze how they affect the local voting and provide guidelines for tuning neighborhood size. We also prove the worst-case error bound for the ranking-based method. Experiments with both synthetic and real-world label noise demonstrate our training-free solutions are consistently and significantly improving over most of the training-based baselines.

authors:
Vibhu Agarwal
Tanya Podchiyska
Juan M Banda
Veena Goel
Tiffany I Leung
Evan P Minty
Timothy E Sweeney
Elsie Gyang
Nigam H Shah

title: Learning statistical models of phenotypes using noisy labeled training data

venue: Journal of the American Medical Informatics Association,

authors:
Ehsan Amid
Manfred KK Warmuth
Rohan Anil
Tomer Koren

title: Robust bi-tempered logistic loss based on bregman divergences

venue: In Advances in Neural Information Processing Systems,

authors:
Dara Bahri
Heinrich Jiang
Maya Gupta

title: Deep k-nn for noisy labels

venue: In International Conference on Machine Learning,

authors:
David Berthelot
Nicholas Carlini
Ian Goodfellow
Nicolas Papernot
Avital Oliver
Colin Raffel

title: Mixmatch: A holistic approach to semi-supervised learning

authors:
Valerii V Buldygin
Yu V Kozachenko

title: Sub-gaussian random variables

venue: Ukrainian Mathematical Journal,

authors:
Ting Chen
Simon Kornblith
Mohammad Norouzi
Geoffrey Hinton

title: A simple framework for contrastive learning of visual representations

authors:
Hao Cheng
Zhaowei Zhu
Xingyu Li
Yifei Gong
Xing Sun
Yang Liu

title: Learning with instancedependent label noise: A sample sieve approach

venue: In International Conference on Learning Representations,

authors:
J. Deng
W. Dong
R. Socher
L.-J. Li
K. Li
L. Fei-Fei

title: ImageNet: A Large-Scale Hierarchical Image Database

venue: In CVPR09,

authors:
Jacob Devlin
Ming-Wei Chang
Kenton Lee
Kristina Toutanova. Bert

title: Pre-training of deep bidirectional transformers for language understanding

venue: arXiv preprint arXiv:1810.04805,

authors:
Wei Gao
Bin-Bin Yang
Zhi-Hua Zhou

title: On the resistance of nearest neighbor to random noisy labels

venue: arXiv preprint arXiv:1607.07526,

authors:
Aritra Ghosh
Andrew Lan

title: Contrastive learning improves model robustness under label noise

authors:
Aritra Ghosh
Himanshu Kumar
PS Sastry

title: Robust loss functions under label noise for deep neural networks

venue: In Thirty-First AAAI Conference on Artificial Intelligence,

authors:
Maoguo Gong
Hao Li
Deyu Meng
Qiguang Miao
Jia Liu

title: Decomposition-based evolutionary multiobjective optimization to self-paced learning

venue: IEEE Transactions on Evolutionary Computation,

authors:
Priya Goyal
Piotr Dollár
Ross Girshick
Pieter Noordhuis
Lukasz Wesolowski
Aapo Kyrola
Andrew Tulloch
Yangqing Jia
Kaiming He

title: Accurate, large minibatch sgd: Training imagenet in 1 hour

venue: arXiv preprint arXiv:1706.02677,

authors:
Bo Han
Quanming Yao
Xingrui Yu
Gang Niu
Miao Xu
Weihua Hu
Ivor Tsang
Masashi Sugiyama

title: Co-teaching: Robust training of deep neural networks with extremely noisy labels

venue: In Advances in neural information processing systems,

authors:
Bo Han
Quanming Yao
Tongliang Liu
Gang Niu
Ivor W Tsang
James T Kwok
Masashi Sugiyama

title: A survey of label-noise representation learning: Past, present and future

authors:
Kaiming He
Haoqi Fan
Yuxin Wu
Saining Xie
Ross Girshick

title: Momentum contrast for unsupervised visual representation learning

authors:
Xu Ji
João F Henriques
Andrea Vedaldi

title: Invariant information clustering for unsupervised image classification and segmentation

venue: In Proceedings of the IEEE/CVF International Conference on Computer Vision,

authors:
Lu Jiang
Zhengyuan Zhou
Thomas Leung
Li-Jia Li
Li Fei-Fei

title: Mentornet: Learning datadriven curriculum for very deep neural networks on corrupted labels

authors:
Lu Jiang
Di Huang
Mason Liu
Weilong Yang

title: Beyond synthetic noise: Deep learning on controlled noisy labels

authors:
David R Karger
Sewoong Oh
Devavrat Shah

title: Efficient crowdsourcing for multi-class labeling

venue: In Proceedings of the ACM SIGMETRICS/international conference on Measurement and modeling of computer systems,

authors:
D.R. Karger
S. Oh
D. Shah

title: Iterative learning for reliable crowdsourcing systems

venue: In Neural Information Processing Systems, NIPS

authors:
Alex Krizhevsky
Geoffrey Hinton

title: Learning multiple layers of features from tiny images

venue: Technical report, Citeseer,

authors:
Alex Krizhevsky
Ilya Sutskever
Geoffrey E Hinton

title: Imagenet classification with deep convolutional neural networks

venue: Advances in neural information processing systems,

authors:
Jingling Li
Mozhi Zhang
Keyulu Xu
John P Dickerson
Jimmy Ba

title: Noisy labels can induce good representations

venue: arXiv preprint arXiv:2012.12896,

authors:
Junnan Li
Richard Socher
Steven C.H. Hoi

title: Dividemix: Learning with noisy labels as semisupervised learning

authors:
Xuefeng Li
Tongliang Liu
Bo Han
Gang Niu
Masashi Sugiyama

title: Provably end-to-end labelnoise learning without anchor points

venue: arXiv preprint arXiv:2102.02400,

authors:
Andy T Liu
Shang-Wen Li
Hung-yi Lee

title: Tera: Self-supervised learning of transformer encoder representation for speech

venue: IEEE/ACM Transactions on Audio, Speech, and Language Processing,

authors:
Qiang Liu
Jian Peng
Alexander Ihler

title: Variational inference for crowdsourcing

venue: In Proceedings of the 25th International Conference on Neural Information Processing Systems-Volume

authors:
Sheng Liu
Jonathan Niles-Weed
Narges Razavian
Carlos Fernandez-Granda

title: Early-learning regularization prevents memorization of noisy labels

venue: arXiv preprint arXiv:2007.00151,

authors:
Tongliang Liu
Dacheng Tao

title: Classification with noisy labels by importance reweighting

venue: IEEE Transactions on pattern analysis and machine intelligence,

title: Understanding instance-level label noise: Disparate impacts and treatments

authors:
Yang Liu
Hongyi Guo

title: Peer loss functions: Learning from noisy labels without knowing noise rates

venue: In Proceedings of the 37th International Conference on Machine Learning,

authors:
Yang Liu
Mingyan Liu

title: An online learning approach to improving the quality of crowdsourcing

venue: ACM SIGMETRICS Performance Evaluation Review,

authors:
Huixiang Luo
Hao Cheng
Yuting Gao
Ke Li
Mengdan Zhang
Fanxu Meng
Xiaowei Guo
Feiyue Huang
Xing Sun

title: On the consistency training for open-set semi-supervised learning, 2021

authors:
Nagarajan Natarajan
Inderjit S Dhillon
Pradeep K Ravikumar
Ambuj Tewari

title: Learning with noisy labels

authors:
Duc Tam Nguyen
Chaithanya Kumar Mummadi
Thi Phuong Nhung Ngo
Thi Hoai Phuong Nguyen
Laura Beggel
Thomas Brox

title: Self: Learning to filter noisy labels with selfensembling

authors:
Curtis Northcutt
Lu Jiang
Isaac Chuang

title: Confident learning: Estimating uncertainty in dataset labels

venue: Journal of Artificial Intelligence Research,

authors:
Curtis G Northcutt
Anish Athalye
Jonas Mueller

title: Pervasive label errors in test sets destabilize machine learning benchmarks

venue: arXiv preprint arXiv:2103.14749,

authors:
Giorgio Patrini
Alessandro Rozza
Aditya Krishna Menon
Richard Nock
Lizhen Qu

title: Making deep neural networks robust to label noise: A loss correction approach

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Garima Pruthi
Frederick Liu
Satyen Kale
Mukund Sundararajan

title: Estimating training data influence by tracing gradient descent

authors:
Alec Radford
Jong Wook Kim
Chris Hallacy
Aditya Ramesh
Gabriel Goh
Sandhini Agarwal
Girish Sastry
Amanda Askell
Pamela Mishkin
Jack Clark

title: Learning transferable visual models from natural language supervision

venue: arXiv preprint arXiv:2103.00020,

authors:
Pierre Sermanet
David Eigen
Xiang Zhang
Michaël Mathieu
Rob Fergus
Yann LeCun

title: Overfeat: Integrated recognition, localization and detection using convolutional networks

venue: arXiv preprint arXiv:1312.6229,

authors:
Jun Shu
Qian Zhao
Keyu Chen
Zongben Xu
Deyu Meng

title: Learning adaptive loss for robust learning with noisy labels

venue: arXiv preprint arXiv:2002.06482,

authors:
Chuanqi Tan
Fuchun Sun
Tao Kong
Wenchang Zhang
Chao Yang
Chunfang Liu

title: A survey on deep transfer learning

venue: In International conference on artificial neural networks,

authors:
Jialu Wang
Yang Liu
Caleb Levy

title: Fair classification with group-dependent label noise

authors:
Yisen Wang
Xingjun Ma
Zaiyi Chen
Yuan Luo
Jinfeng Yi
James Bailey

title: Symmetric cross entropy for robust learning with noisy labels

authors:
Hongxin Wei
Lei Feng
Xiangyu Chen
Bo An

title: Combating noisy labels by agreement: A joint training method with co-regularization

authors:
Jiaheng Wei
Yang Liu

title: When optimizing f-divergence is robust with label noise

authors:
Xiaobo Xia
Tongliang Liu
Nannan Wang
Bo Han
Chen Gong
Gang Niu
Masashi Sugiyama

title: Are anchor points really indispensable in label-noise learning

authors:
Xiaobo Xia
Tongliang Liu
Bo Han
Nannan Wang
Jiankang Deng
Jiatong Li
Yinian Mao

title: Extended T: Learning with mixed closed-set and open-set noisy labels

venue: arXiv preprint arXiv:2012.00932,

authors:
Xiaobo Xia
Tongliang Liu
Bo Han
Nannan Wang
Mingming Gong
Haifeng Liu
Gang Niu
Dacheng Tao
Masashi Sugiyama

title: Part-dependent label noise: Towards instance-dependent label noise

authors:
Xiaobo Xia
Tongliang Liu
Bo Han
Chen Gong
Nannan Wang
Zongyuan Ge
Yi Chang

title: Robust early-learning: Hindering the memorization of noisy labels

authors:
Tong Xiao
Tian Xia
Yi Yang
Chang Huang
Xiaogang Wang

title: Learning from massive noisy labeled data for image classification

authors:
Qizhe Xie
Zihang Dai
Eduard Hovy
Minh-Thang Luong
Quoc V Le

title: Unsupervised data augmentation

venue: arXiv preprint arXiv:1904.12848,

authors:
Quanming Yao
Hansi Yang
Bo Han
Gang Niu
James T Kwok

title: Searching to exploit memorization effect in learning with noisy labels

authors:
Xingrui Yu
Bo Han
Jiangchao Yao
Gang Niu
Ivor Tsang
Masashi Sugiyama

title: How does disagreement help generalization against label corruption

venue: In Proceedings of the 36th International Conference on Machine Learning,

authors:
Matthew D Zeiler
Rob Fergus

title: Visualizing and understanding convolutional networks

venue: In European conference on computer vision,

authors:
Hongyi Zhang
Moustapha Cisse
Yann N. Dauphin
David Lopez-Paz

title: mixup: Beyond empirical risk minimization

authors:
Jing Zhang
Victor S Sheng
Tao Li
Xindong Wu

title: Improving crowdsourced label quality using noise correction

venue: IEEE transactions on neural networks and learning systems,

authors:
Yikai Zhang
Songzhu Zheng
Pengxiang Wu
Mayank Goswami
Chao Chen

title: Learning with feature-dependent label noise: A progressive approach

venue: arXiv preprint arXiv:2103.07756,

authors:
Yuchen Zhang
Xi Chen
Dengyong Zhou
Michael I Jordan

title: Spectral methods meet em: A provably optimal algorithm for crowdsourcing

authors:
Zhilu Zhang
Mert Sabuncu

title: Generalized cross entropy loss for training deep neural networks with noisy labels

authors:
Zhaowei Zhu
Tongliang Liu
Yang Liu

title: A second-order approach to learning with instancedependent label noise

venue: In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR),

authors:
Zhaowei Zhu
Yiwen Song
Yang Liu

title: Clusterability as an alternative to anchor points when learning with noisy labels

venue: In Proceedings of the 38th International Conference on Machine Learning,

authors:
Zhaowei Zhu
Jingxuan Zhu
Ji Liu
Yang Liu

title: Federated bandit: A gossiping approach

venue: In Abstract Proceedings of the 2021 ACM SIGMETRICS/International Conference on Measurement and Modeling of Computer Systems,

authors:
2020b Li et al
Han et al
loss-correction (Liu
2015 Tao
Natarajan

title: Patrini et al., 2017), and robust loss functions (Liu & Guo, 2020

venue: (Zhang et al.,

heading: 1 INTRODUCTION

text:
The generalization of deep neural networks (DNNs) depends on the quality and the quantity of the data. Nonetheless, in practice real-world datasets often contain label noise that challenges the above assumption (Krizhevsky et al., 2012; Zhang et al., 2017; Agarwal et al., 2016). Employing human workers to cleaning annotations is one reliable way to improve the label quality, but it is too expensive and time-consuming for a large-scale dataset. One promising way to automatically cleaning up label errors is to first algorithmically detect possible label errors from a large-scale dataset (Cheng et al., 2021; Northcutt et al., 2021a; Pruthi et al., 2020; Bahri et al., 2020), and then correct them using either algorithm or crowdsourcing (Northcutt et al., 2021b).
Almost all the algorithmic detection approaches focus on designing customized training processes to learn with noisy labels, where the idea is to train DNNs with noisy supervisions and then make decisions based on the output (Northcutt et al., 2021a) or gradients (Pruthi et al., 2020) of the last logit layer of the trained model. The high-level intuition of these methods is the memorization effects (Han et al., 2020), i.e., instances with label errors, a.k.a., corrupted instances, tend to be harder to be learned by DNNs than clean instances (Xia et al., 2021; Liu et al., 2020). By setting appropriate hyperparameters to utilize the memorization effect, corrupted instances could be identified.
The above methods suffer from two major limitations: 1) the customized training processes are task-specific and may require fine-tuning hyperparameters for different datasets/noise; 2) as long as the model is trained with noisy supervisions, the memorization of corrupted instances exists. The model will “subjectively” and wrongly treat the memorized/overfitted corrupted instances as clean. For example, some low-frequency/rare clean instances may be harder to memorize than highfrequency/common corrupted instances. Memorizing these corrupted instances lead to unexpected and disparate impacts (Liu, 2021). One way to avoid memorizing/overfitting is to drop the depen-
dency on training using the noisy supervisions, which motivates us to design a training-free method to find label errors. Intuitively, we can carefully use the information from nearby representations to infer whether one instance is corrupted or not. This observation inspired our solution of using a good representation to first identify “neighbor” instances for each training example, whose noisy labels jointly would help us perform the detection. Note the representation extractor could be fully independent of noisy supervisions by referring to unsupervised learning or self-supervised learning, or even adapting from other tasks.
Our training-free method enables more possibilities beyond a better detection result. For example, the concerns of the required assumptions and hyperparameter tuning in those training-based methods will now be released due to our training-free property. The complexity of such a solution will also be much lower, again due to the removal of the possibly involved training processes. This light detection solution also has the potential to serve as a pre-processing module to prepare data for other sophisticated tasks (e.g., semi-supervised learning (Xie et al., 2019; Berthelot et al., 2019)).
Our main contributions are: 1) New perspective: Different from current methods that train customized models on noisy datasets, we proposed a training-free solution to efficiently detect noisy labels given good representations. We believe this is the first attempt of the same kind to the best of our knowledge. 2) Efficient algorithms: Based on the neighborhood information, we propose two methods: a voting-based local detection method that only requires checking the noisy label consensuses of nearby representations, and a ranking-based global detection method that scores each instance by its likelihood of being clean and filters out a guaranteed percentage of instances with low scores as corrupted ones. 3) Theoretical analyses: We theoretically analyze how a good representation (but possibly imperfect in practice) affects the local voting and provide guidelines for tuning neighborhood size. We also prove the worst-case error bound for the ranking-based method. 4) Numerical findings: Our numerical experiments show three important messages: in label noise detection, i) training with noisy supervisions may not be necessary; ii) representation layers tend to be more useful than the logit layers; iii) representations from other tasks or domains are helpful.

heading: 1.1 RELATED WORKS

text:
Learning with noisy labels There are many other works that can detect corrupted instances (a.k.a. sample selection) in the literature, e.g., (Jiang et al., 2018; Han et al., 2018; Yu et al., 2019; Yao et al., 2020; Wei et al., 2020; Jiang et al., 2020; Zhang et al., 2021), and its combination with semi-supervised learning (Nguyen et al., 2019; Li et al., 2020b; Cheng et al., 2021). Another line of works focus on designing robust loss functions to mitigate the effect of label noise, such as numerical methods (Ghosh et al., 2017; Zhang & Sabuncu, 2018; Gong et al., 2018; Amid et al., 2019; Wang et al., 2019; Shu et al., 2020) and statistical methods (Natarajan et al., 2013; Liu & Tao, 2015; Patrini et al., 2017; Liu & Guo, 2020; Xia et al., 2019; 2021; Wei & Liu, 2021; Zhu et al., 2021a; Li et al., 2021; Liu et al., 2020). All these methods require training DNNs with noisy supervisions.
Pre-training or Self-supervised Learning Training DNNs from scratch may be time-consuming (Goyal et al., 2017). A common strategy to alleviate this issue is initializing DNN with a pre-trained model when training on new tasks (Krizhevsky et al., 2012; Zeiler & Fergus, 2014; Sermanet et al., 2013). The pre-trained model can be used for down-stream tasks due to the great transfer-ability of DNNs (Tan et al., 2018). Popular pre-trained models include BERT (Devlin et al., 2018) for language tasks or CLIP (Radford et al., 2021) for vision-language tasks. Recently, unsupervised learning (Ji et al., 2019) and self-supervised learning (Jaiswal et al., 2021; Liu et al., 2021; He et al., 2020; Chen et al., 2020) also exhibit great power when fine-tuning DNN on down-stream tasks.
Label aggregation Our work is also relevant to the literature of crowdsourcing that focuses on label aggregation (to clean the labels)(Liu et al., 2012; Karger et al., 2011; 2013; Liu & Liu, 2015; Zhang et al., 2014). Most of these works can access multiple reports (labels) for the same input feature, while our real-world datasets usually have only one noisy label for each feature.

heading: 2 PRELIMINARIES

text:
Instances Traditional classification problems with perfect supervisions build on a clean dataset D := {(xn, yn)}n∈[N ], where [N ] := {1, 2, · · · , N}. Each clean instance (xn, yn) includes feature xn and clean label yn, which is drawn according to random variables (X,Y ) ∼ D. In a more practical case, the clean labels are likely to be unavailable and the learner could only observe a noisy
dataset denoted by D̃ := {(xn, ỹn)}n∈[N ], where (xn, ỹn) is a noisy instance and the noisy label ỹn may or may not be identical to yn. We call ỹn is corrupted if ỹn 6= yn and clean otherwise. The instance (xn, ỹn) is a corrupted instance if ỹn is corrupted. The noisy data distribution corresponds to D̃ is (X, Ỹ ) ∼ D̃. We focus on the closed-set label noise that Y and Ỹ are assumed to be in the same label space, e.g., Y, Ỹ ∈ [K] for a K-class classification task. Explorations on open-set data (Xia et al., 2020a; Luo et al., 2021) are deferred to future works.
Representations The representation of feature xn is denoted by x̄n := g(xn), where g(·) denotes a representation extractor. Feature xn could be in any shape and representation x̄n is generally a high-dimensional vector. In this paper, we focus on a setting where the distances between two representations should be comparable or clusterable (Zhu et al., 2021b), i.e., nearby representations should belong to the same true class with a high probability (Gao et al., 2016), which could be defined as (k, δk) label clusterability in Definition 1. Definition 1 ((k, δk) label clusterability). Given a representation extractor g(·), a dataset D satisfies (k, δk) label clusterability if: ∀n ∈ [N ], the representation x̄n := g(xn) and its k-NearestNeighbors (k-NN) x̄n1 , · · · , x̄nk belong to the same true class with probability at least 1− δk. Note δk captures two types of randomnesses: one comes from a probabilistic Y |X , i.e., ∃i ∈ [K],P(Y = i|X) /∈ {0, 1}; the other depends on the quality of representation and the value of k, which will be further illustrated in Figure 2. The (k, 0) label clusterability is also known as k-NN label clusterability (Zhu et al., 2021b). It has been shown in (Zhu et al., 2021b) that k-NN label clusterability can often be satisfied for a reasonable representation when k is moderate to small. We define k perfect extractors/representations in Definition 2. Definition 2 (k perfect extractor/representation). A representation extractor g(·) is called k perfect extractor if it induces k-NN label clusterability. Its outputs are called k perfect representations.
Label noise detection Our paper aims to improve the performance of the label noise detection (a.k.a, detecting noisy/corrupted labels, finding label errors) which is measured by the F1-score of the detected corrupted instances, which is the harmonic mean of the precision and recall, i.e. F1 = 2/(Precision
−1 + Recall−1). Let 1(·) be the indicator function that takes value 1 when the specified condition is satisfied and 0 otherwise. Let vn = 1 indicate that ỹn is detected as a corrupted label, and vn = 0 if ỹn is detected to be clean. Then the precision and recall can be calculated as Precision = ∑ n∈[N] 1(vn=1,ỹn 6=yn)∑
n∈[N] 1(vn=1) , Recall =
∑ n∈[N] 1(vn=1,ỹn 6=yn)∑
n∈[N] 1(ỹn 6=yn) .

heading: 3 LABEL NOISE DETECTION USING SIMILAR REPRESENTATIONS

text: Different from most methods that detect noisy labels based on the logit layer or model predictions (Northcutt et al., 2021a; Cheng et al., 2021; Pruthi et al., 2020), we focus on representations of features. Particularly we are interested in the possibility of detecting noisy labels in a training-free way, once given good representations. In this section, we will first introduce intuitions, and then provide two efficient algorithms to detect label noise with similar representations.

heading: 3.1 INTUITIONS

text:
The training-based detection methods often make decisions by comparing model predictions with noisy labels (Cheng et al., 2021; Northcutt et al., 2021a). However, the representation g(xn) cannot be directly compared with the noisy label ỹn since g(xn) is not directly categorical, i.e., the output of a single g(xn) rarely corresponds to any label class. Thus the first step of our training-free solution should be establishing an auxiliary categorical information using only representations.
As illustrated in Figure 1, the high-level intuition is to check label consensuses of nearby representations. With k perfect representations as defined in Definition 2, we know the true labels of x̄n and its k-NN x̄n1 , · · · , x̄nk should be the same. If the label noise across these instances are groupdependent (Wang et al., 2021), we can treat their noisy labels as k + 1 independent observations of P(Ỹ |X = xn, Y = yn), then estimate the probability by counting the frequency or weighted frequency1 of each class in the k-NN label estimator, and get k-NN labels ŷn. The i-th element ŷn[i] can be interpreted as the estimated probability of predicting class-i.
Representations could be better than model predictions During supervised training, memorizing noisy labels makes the model generalizes poorly (Li et al., 2020a; Han et al., 2020), while using only representations may effectively avoid this issue. This is because representations often come from techniques beyond memorization such as unsupervised learning or self-supervised learning where the noisy labels are not referred in representation learning. On the other hand, the extractor g(·) has great potential in domain adaption or transfer, which makes representations more flexible than the specific model predictions. We will demonstrate this point in Section 5.

heading: 3.2 VOTING-BASED LOCAL DETECTION

text: Inspired by the idea implemented in model decisions, i.e., selecting the most likely class as the true class, we can simply “predict” the index that corresponds to the largest element in ŷn with random tie-breaking, i.e., yvoten = arg maxi∈[K] ŷn[i]. To further detect whether ỹn is corrupted or not, we only need to check vn := 1(yvoten 6= ỹn). Recall vn = 1 indicates a corrupted label. This voting method relies only on the local information within each k-NN label ŷn, which may not be robust with imperfect representations. Intuitively, when the gap between the true class probability and the wrong class probability is small, the majority vote will be likely to make mistakes due to sampling errors in ŷn. Thus only using local information within each ŷn may not be sufficient. It is important to leverage more information such as some global statistics, which will be discussed later.

heading: 3.3 RANKING-BASED GLOBAL DETECTION

text:
From a global perspective, if the likelihood for each instance being clean could be evaluated by some scoring functions, we can sort the scores in an increasing order and filter out the low-score instances as corrupted ones. Based on this intuition, there are two critical components: the scoring function and the threshold to differentiate the low-score part (corrupted) and the high-score part (clean).
Scoring function A good scoring function should be able to give clean instances higher scores than corrupted instances. We adopt cosine similarity defined as: Score(ŷn, j) = ŷ>n ej ‖ŷn‖2‖ej‖2 , where ej is the one-hot encoding of label j. To evaluate whether the soft label ŷn informs us a clean instance or not, we compare Score(ŷn, ỹn) with other instances that have the same noisy label. This scoring function captures more information than majority votes, which is summarized as follows. Property 1 (Relative score). Within the same instance, the score of the majority class is higher than the others, i.e. Score(ŷn, yvoten ) > Score(ŷn, j),∀j 6= yvoten , j ∈ [K],∀n ∈ [N ]. Property 2 (Absolute score). Score(ŷn, j) is jointly determined by both ŷn[j] and ŷn[j′],∀j′ 6= j.
The first property guarantees that the corrupted labels would have lower scores than clean labels for the same instance when the vote is correct. However, although solely relying on Property 1 may work well in the voting-based method which makes decisions individually for each instance, it is not sufficient to be trustworthy in the ranking-based global detection. The main reason is that, across different instances, the non-majority classes of some instances may have higher absolute scores than the majority classes of the other instances, which is especially true for general instance-dependent label noise with heterogeneous noise rates (Cheng et al., 2021). Property 2 helps make it less likely to happen. Consider an example as follows.
Example Suppose ŷn1 = ŷn2 = [0.6, 0.4, 0.0] >, ŷn3 = [0.34, 0.33, 0.33] >, yn1 = yn2 = yn3 = 1, ỹn1 = ỹn3 = 1, ỹn2 = 2. We can use the majority vote to get perfect detection in this case, i.e., yvoten1 = y vote n2 = y vote n3 = 1 = yn1 , since the first class of each instance has the largest value. However, if we directly use a single value in soft label yn to score them, e.g., Score ′(ŷn, j) =
1One can weight instances by the similarity to the center instance.
Algorithm 1 Detection with Similar Representations (The SimiRep Detector) 1: Input: Number of epochs: M . k-NN parameter: k. Noisy dataset: D̃ = {(xn, ỹn)}n∈[N ].
Representation extractor: g(·). Method: Vote or Rank. Epoch counter m = 0. 2: repeat 3: x′n ← RandPreProcess(xn),∀n; # Initialize & Standard data augmentations 4: x̄n ← g(x′n),∀n; # Extract representations with g(·) 5: ŷn ← kNNLabel({x̄n}n∈[N ], k) # Get soft labels based on the clusterability of representations 6: if Vote then 7: yvoten ← arg maxi∈[K] ŷn[i]; # Apply local majority vote 8: vn ← 1(yvoten 6= ỹn),∀n ∈ [N ]; # Treat as corrupted if majority votes agree with noisy labels 9: else
10: P(Y ),P(Ỹ |Y )← HOC({(x̄n, ỹn)}n∈[N ]); # Estimate clean priors P(Y ) and noise transitions P(Ỹ |Y ) by the HOC estimator
11: P(Y |Ỹ ) = P(Ỹ |Y ) · P(Y )/P(Ỹ ); # Estimate thresholds by Bayes’ rule 12: for j in [K] do 13: Nj := {n|ỹn = j}; # Detect corrupted labels in each setNj 14: I ← argsort{Score(ŷn, j)}n∈Nj ; # I records the raw index of each sorted value 15: vn ← 1 ( Loc(n, I) ≤ b(1− P(Y = j|Ỹ = j)) ·Njc ) ; # Select low-score (head) instances as corrupted ones 16: end for 17: end if 18: Vm = {vn}n∈[N ]; # Record detection results in the m-th epoch 19: until M times 20: V =Vote(Vm,∀m ∈ [M ]); # Do majority vote based on results from M epochs 21: Output: [N ] \ V .
ŷn[j], we will have ŷn1 [ỹn1 ] = 0.6 > ŷn2 [ỹn2 ] = 0.4 > ŷn3 [ỹn3 ] = 0.33, where the ranking is n3 ≺ n2 ≺ n1. Ideally, we know instance n2 is corrupted and the true ranking should be n2 ≺ n3 ≺ n1 or n2 ≺ n1 ≺ n3. To mitigate this problem, we choose the cosine similarity as our scoring function. The three instances could be scored as 0.83, 0.55, 0.59, corresponding to an ideal ranking n2 ≺ n3 ≺ n1. We formally introduce the detailed ranking approach as follows. Ranking Suppose we have a group of instances with the same noisy class j, i.e. {(xn, ỹn)}n∈Nj , where Nj := {n|ỹn = j} are the set of indices that correspond to noisy class j. Let Nj be the number of indices in Nj (counted from noisy labels). Intuitively, we can first sort all instances in Nj in an increasing order by argsort and obtain the original indices for the sorted scores as: I = argsort{Score(ŷn, j)}n∈Nj , where the low-score head is supposed to consist of corrupted instances (Northcutt et al., 2021a). Then we can simply select the first Ñj instances with low scores as corrupted instances: vn = 1(Loc(n, I) ≤ Ñj), where Loc(n, I) returns the index of n in I. Instead of manually tuning Ñj , we discuss how to determine it algorithmically.
Threshold The number of corrupted instances in Nj is approximately P(Y 6= j|Ỹ = j) · Nj when Nj is sufficiently large. Therefore if all the corrupted instances have lower scores than any clean instance, we can set Ñj = P(Y 6= j|Ỹ = j) · Nj to obtain the ideal division. Note Nj can be obtained by directing counting the number of instances with noisy label j. To calculate the probability P(Y 6= j|Ỹ = j) = 1 − P(Y = j|Ỹ = j), we borrow the results from the HOC estimator (Zhu et al., 2021b), where the noise transition probability P(Ỹ = j|Y = j) and the marginal distribution of clean label P(Y = j) can be estimated with only representations and the corresponding noisy labels. Then we can calculated our needed probability by Bayes’ rule P(Y = j|Ỹ = j) = P(Ỹ = j|Y = j) · P(Y = j)/P(Ỹ = j), where P(Ỹ = j) can be estimated by counting the frequency of noisy label j in D̃. Technically other methods exist in the literature to estimate P(Ỹ |Y ) (Liu & Tao, 2015; Patrini et al., 2017; Northcutt et al., 2021a; Li et al., 2021). But they often require training a model to fit the data distribution, which conflict with our goal of a training-free solution; instead, HOC fits us perfectly.
3.4 ALGORITHM: DETECTION WITH SIMILAR REPRESENTATIONS (SIMIREP)
Algorithm 1 summarizes our solution. The main computation complexity is obtaining representations with extractor g(·), which is less than the cost of evaluating the model compared with the training-based methods. Thus SimiRep can filter out corrupted instances efficiently. In Algorithm 1, we run either voting-based local detection as Lines 7, 8, or ranking-based global detection as Lines 14, 15. The detection is run multiple times with random standard data augmentations to reduce the variance of estimation. The majority of results from different epochs is adopted as the final detection output as Line 20, i.e., flag as corrupted if vn = 1 in more than half of the epochs.

heading: 4 HOW DO REPRESENTATIONS AFFECT OUR SOLUTION?

text:
In this section, we will first show how a good but imperfect representation2 affects the selection of the hyperparameter k. We then offer an analysis of the error upper bound for the ranking-based method given a representation extractor g(·).
4.1 HOW DO REPRESENTATIONS AFFECT THE CHOICE OF k?
Recall k is used as illustrated in Figure 1. On one hand, the k-NN label estimator will be more accurate if there is stronger clusterability that more neighbor representations belong to the same true class (Liu & Liu, 2015; Zhu et al., 2021b), which helps improve the performance of later algorithms. On the other hand, with good but imperfect representations, stronger clusterability with a larger k is less likely to satisfy, thus the violation probability δk increases with k for a given extractor g(·). We take the voting-based method as an example and analyze this tradeoff. For a clean presentation, we focus on a binary classification with instance-dependent label noise where P(Y = 1) = p, P(Ỹ = 2|X,Y = 1) = e1(X), P(Ỹ = 1|X,Y = 2) = e2(X). Suppose the instance-dependent noise rate is upper-bounded by e, i.e., e1(X) ≤ e, e2(X) ≤ e. With δk as in Definition 1, we calculate the lower bound of the probability that the vote is correct in Proposition 1. Proposition 1. The lower bound for the probability of getting true detection with majority vote is
P(Vote is correct|k) ≥ (1− δk) · I1−e1(k + 1− k′, k′ + 1),
where k′ = d(k + 1)/2e − 1, I1−e1(k + 1− k′, k′ + 1) is the regularized incomplete beta function defined as I1−e(k + 1− k′, k′ + 1) = (k + 1− k′) ( k+1 k′ ) ∫ 1−e 0 tk−k ′ (1− t)k′dt.
Proposition 1 shows the tradeoff between a reliable k-NN label and an accurate vote. When k is increasing, Term-1 (1 − δk) (quality of representations) decreases but Term-2 I1−e1(k + 1− k′, k′ + 1) (result of pure majority vote) increases. With Proposition 1, we are ready to answer the question: when do we need more labels? See Remark 1. Remark 1. Consider the lower bounds with k1 and k2 (k1 < k2). Supposing the first lower bound is lower than the second lower bound, based on Proposition 1, we roughly study the trend with an increasing k by comparing two bounds and get
1− δk1 1− δk2 < I1−e(k2 + 1− k′2, k′2 + 1) I1−e(k1 + 1− k′1, k′1 + 1) .
For example, when k1 = 5, k2 = 20, e = 0.4, we can calculate the incomplete beta function and 1−δ5 1−δ20 < 1.52. Supposing δ5 = 0.2, we have δ20 < 0.47. This indicates increasing k from 5 to 20 would not improve the lower bound with imperfect representations with δ20 > 0.47. This observation helps us set k with a practical and imperfect g(·). We set k = 10 in all of our experiments.
Remark 1 indicates that: with imperfect representations, a small k may achieve the best (highest) probability lower bound. To further consolidate this claim, we numerically calculate δk with different g(·) and the corresponding probability lower bound in Figure 2. We find most of the probability lower bounds first increase then decrease except for the perfect g(·) which is trained using groundtruth labels. Note the perfect g(·) has memorized all clean instances so that δk → 0 since k 5000 (the number of instances in the same label class).
2Note the voting-based method achieves an F1-score of 1 given k perfect representations, k → +∞.
4.2 HOW DO REPRESENTATIONS AFFECT F1-SCORE?
We next prove the probability bound for the performance of the ranking-based method. Consider a K-class classification problem with informative instance-dependent label noise (Cheng et al., 2021). Denote random variable S by the score of each instance being clean. A higher score S indicates the instance is more likely to be clean. Then for instances in Nj , we have two set of random variables S truej := {Strue|n ∈ Nj , ỹn = yn} and S falsej := {Sfalse|n ∈ Nj , ỹn 6= yn}. Intuitively, the score Struej should be greater than Sfalsej . Suppose their means, which depend on noise rates, are bounded, i.e., E[Struej ] ≥ µtruej , E[Sfalsej ] ≤ µfalsej . Assume there exists a feasible v such that both Struej and Sfalsej follow sub-Gaussian distributions with variance proxy ∆ 2
2v (Buldygin & Kozachenko, 1980; Zhu et al., 2021c) such that: P(µtruej − Struej ≥ t) ≤ e−v(t/∆) 2 , and P(Sfalsej − µfalsej ≥ t) ≤ e−v(t/∆) 2
, where 1/∆ is the “height” of both distributions, i.e., P(Struej = µtruej ) = P(Sfalsej = µfalsej ) = 1/∆, v is the decay rate of tails. Let N−j (N + j ) be the number of indices in S falsej (S truej ). Theorem 1 summarizes the performance bound of the ranking-based method. See Appendix for the proof.
Theorem 1. With probability at least p, the F1-score of detecting corrupted instances inNj with the rank-based method by threshold NjP(Y = j|Ỹ = j) is at least 1− e
−v max(N−,N+)+α N− , where p =∫ µtrue−µfalse−∆
−1 f(t)dt, f(t) is the probability density function of the difference of two independent beta-distributed random variables β1−β2, where β1 ∼ Beta(N−, 1), β2 ∼ Beta(α+1, N+−α).
Theorem 1 shows the performance of detection depends on 1) the concentration of Struej and S false j (denoted by variance proxy ∆ 2
2v ); 2) the distance between S true j and S false j (denoted by µ true − µfalse). Intuitively, with proper scoring function and good representations, we have small variance proxy (small ∆ and large v) and F1-score approximates to 1.

heading: 5 EMPIRICAL RESULTS

text:
We present experimental evidence in this section. The performance is measured by the F1-score of the detected corrupted labels as defined in Section 2. Note there is no any training procedure in our method. The only hyperparameters in our methods are the number of epochs M and the k-NN parameter k. Intuitively, a larger M returns a collective result from more times of detection, which should be more accurate. The hyperparameter k cannot be set too large as demonstrated in Figure 2. In CIFAR (Krizhevsky et al., 2009) experiments, rather than fine-tuneM and k for different settings, we fix M = 21 and k = 10. We also test on Clothing1M (Xiao et al., 2015). Detailed experiment settings on Clothing1M are in Appendix C.
Synthetic label noise We experiment with three popular synthetic label noise models: the symmetric label noise, the asymmetric label noise, and the instance-dependent label noise. Denote the ratio of instances with corrupted labels in the whole dataset by η. Both the symmetric and the asymmetric noise models follow the class-dependent assumption (Liu & Tao, 2015), i.e., the label noise only depends only on the clean class: P(Ỹ |X,Y ) = P(Ỹ |Y ). Specially, the symmetric noise is generated by uniform flipping, i.e., randomly flipping a true label to the other possible classes w.p. η (Cheng et al., 2021). The asymmetric noise is generated by pair-wise flipping, i.e., randomly
flipping true label i to the next class (i mod K) + 1. Denote by d the dimension of features. The instance-dependent label noise is synthesized by randomly generating a d×K projection matrix wi for each class i and project each incoming feature with true class yn onto each column of wyn (Xia et al., 2020b). Instance n is more likely to be flipped to class j if the projection value of xn on the j-th column of wyn is high. See Appendix B in Xia et al. (2020b) and Appendix D.1 in Zhu et al. (2021b) for more details. We use symmetric noise with η = 0.6 (Symm. 0.6), asymmetric noise with η = 0.3 (Asym. 0.3), and instance-dependent noise with η = 0.4 (Inst. 0.4) in experiments.
Real-world label noise The real-world label noise comes from human annotations or weakly labeled web data. We use the 50, 000 noisy training labels (η ≈ 0.16) for CIFAR-10 collected by Zhu et al. (2021b), and our self-collected 50, 000 noisy training labels (η ≈ 0.40) for CIFAR-100 (data will be released in the non-anonymous version). Both sets of noisy labels are crowd-sourced from Amazon Mechanical Turk. For Clothing1M (Xiao et al., 2015), we could not calculate the F1-scores due to the lack of ground-truth labels. We firstly perform noise detection on 1 million noisy training instances then train only with the selected clean data to check the effectiveness.

heading: 5.1 SUPERVISION MAY NOT BE NECESSARY

text:
Our first experiment aims to show that training with noisy supervisions may not be necessary in detecting corrupted labels. To this end, we compare our methods, i.e., voting-based local detection (SimiRep-V) and ranking-based global detection (SimiRep-R), with three recent noise detection works: CORES (Cheng et al., 2021), confident learning (CL) (Northcutt et al., 2021a), and TracIn (Pruthi et al., 2020). We use ResNet34 as the backbone network in this experiment.
Baseline settings All these three baselines require training a model with the noisy supervision. Specifically, CORES (Cheng et al., 2021) trains ResNet34 on the noisy dataset and uses its proposed sample sieve to filter out the corrupted instances. We adopt its default setting during training and calculate the F1-score of the sieved out corrupted instances. Confident learning (CL) (Northcutt et al., 2021a) detects corrupted labels by firstly estimating probabilistic thresholds to characterize label noise, ranking instances based on model predictions, then filtering out corrupted instances based on ranking and thresholds. We adopt its default hyper-parameter setting to train ResNet34. TracIn (Pruthi et al., 2020) detects corrupted labels by evaluating the self-influence of each instance, where the corrupted instances tend to have a high influence score. The influence scores are calculated based on gradients of the last layer of ResNet34 at epoch 40, 50, 60, 100, where the model is trained with a batch size of 128. The initial learning rate is 0.1 and decays to 0.01 at epoch 50. Note TracIn only provides ranking for instances. To exactly detect corrupted instances, thresholds are required. For a fair comparison, we refer to the thresholds learned by confident learning (Northcutt et al., 2021a). Thus the corrupted instances selected by TracIn are based on the ranking from its selfinfluence and thresholds from CL. To highlight that our solutions work well without any supervision, our representation extractor g(·) comes from the ResNet34 pre-trained by SimCLR (Chen et al., 2020) where contrastive learning is applied and no supervision is required. Extractor g(·) is obtained with only in-distribution features, e.g., for experiments with CIFAR-10, g(·) is pre-trained with features only from CIFAR-10.
Performance Table 1 compares the results obtained with or without supervisions. We can see both the voting-based and the ranking-based method achieve overall higher F1-scores compared with the
other three results that require learning with noisy supervisions. Moreover, in detecting the realworld human-level noisy labels, our solution outperforms baselines around 20% on CIFAR-10 and 10% on CIFAR-100, which indicates the training-free solution are more robust to complicated noise patterns. One might also note that CORES achieves exceptionally low F1-scores on CIFAR-10/100 with asymmetric noise and CIFAR-100 with human noise. This observation also informs us that customized training processes might not always be universally applicable.

heading: 5.2 REPRESENTATION LAYERS MAY PERFORM BETTER THAN LOGIT LAYERS

text: Table 2 shows the detection using either representation layers or logit layers of DNNs. In addition to the baselines compared in Section 5.1, we also compare to CE Sieve (Cheng et al., 2021) which follows the same sieving process as CORES but uses CE loss without regularizer. All methods adopt ViT-B/32 pre-trained by CLIP (Radford et al., 2021). Specifically, the training-based methods further fine-tune a linear logit layer on noisy supervisions, while our solution directly sets this pretrained model as g(·). Other settings are the same as those in Section 5.1. By counting the frequency of reaching top-2F1-scores, we find SimiRep-R wins 1st place, SimiRep-V and CORES are tied for 2nd place. However, similar to Table 2, we find the training process of CORES to be unstable. For instance, it almost fails for CIFAR-100 with asymmetric noise. It is therefore reasonable to believe both methods with only representations achieve an overall higher F1-score than other methods with logit layers. In other words, compared with our methods, the extra fine-tuning of logit layers with noisy supervisions cannot always help improve the performance of detecting corrupted labels.

heading: 5.3 WHAT ARE GOOD REPRESENTATIONS

text:
Previous experiments demonstrate our methods overall outperform baselines given representations from contrastive pre-training. It is interesting to see how other representations perform. We summarize results of SimiRep-R in Table 3. There are several interesting findings: 1) The ImageNet pre-trained models perform well, indicating
the traditional supervised training on out-of-distribution data helps; 2) For CIFAR-100, extractor g(·) obtained with only features from CIFAR-10 (R34-C10-SSL) performs better than the extractor with clean CIFAR-10 (R34-C10-Clean), indicating that contrastive pre-training has better generalization ability to out-of-distribution data than supervised learning; 3) The F1-scores achieved by g(·) trained with the corresponding clean dataset are close to 1, indicating our solution can give perfect detection with ideal representations. Besides, we test the performance of training only with the clean instances selected by our approach in Table 4. Standard training with Cross-Entropy loss is adopted. The only difference between the first row and other rows of Table 4 is that some training instances are filtered out by our approach. Table 4 shows simply filtering out corrupted instances based on our approach distinctively outperforms the baseline. We also observe that slightly tuning g(·) in the fine-grained Clothing1M dataset would be helpful. See more details in Appendix C.

heading: 6 CONCLUSIONS

text: This paper proposed a new and universally applicable training-free solution to detect noisy labels by using the neighborhood information defined by a good set of representations. We have also demonstrated that good representations are reasonable assumptions with pre-training or self-supervised learning. Future works will explore other tasks that could benefit from label cleaning.

heading: A THEORETICAL ANALYSES

text:
A.1 PROOF FOR PROPOSITION 1
Now we derive a lower bound for the probability of getting true detection with majority vote: P(Vote is correct|k) ≥(1− δk) · [ p
d(k+1)/2e−1∑ l=0 ( k + 1 l ) el1(1− e1)k+1−l
+ (1− p) d(k+1)/2e−1∑
l=0
( k + 1
l
) el2(1− e2)k+1−l ] =(1− δk) · [p · I1−e1(k + 1− k′, k′ + 1) + (1− p) · I1−e2(k + 1− k′, k′ + 1)]
where I1−e1(k + 1− k′, k′ + 1) is the regularized incomplete beta function defined as I1−e(k + 1− k′, k′ + 1) = (k + 1− k′) ( k + 1
k′ )∫ 1−e 0 tk−k ′ (1− t)k ′ dt,
and k′ = d(k + 1)/2e − 1.

heading: B PROOF FOR THEOREM 1

text:
Proof. Now we derive the worst-case error bound. We first repeat the notations defined in Section 4.2 as follows.
Denote random variable S by the score of each instance being clean. A higher score S indicates the instance is more likely to be clean. Then for instances in Nj , we have two set of random variables S truej := {Strue|n ∈ Nj , ỹn = yn} and S falsej := {Sfalse|n ∈ Nj , ỹn 6= yn}. Intuitively, the score Struej should be greater than Sfalsej . Suppose their means, which depend on noise rates, are bounded, i.e., E[Struej ] ≥ µtruej , E[Sfalsej ] ≤ µfalsej . Assume there exists a feasible v such that both Struej and Sfalsej follow sub-Gaussian distributions with variance proxy ∆ 2
2v (Buldygin & Kozachenko, 1980; Zhu et al., 2021c) such that: P(µtruej − Struej ≥ t) ≤ e−v(t/∆) 2 , and P(Sfalsej − µfalsej ≥ t) ≤ e−v(t/∆) 2
, where 1/∆ is the “height” of both distributions, i.e., P(Struej = µtruej ) = P(Sfalsej = µfalsej ) = 1/∆, v is the decay rate of tails. Let N−j (N + j ) be the number of indices in S falsej (S truej ). For ease of notations, we omit the subscript j in this proof since the detection is performed on each j individually.
Denote the order statistics of random variables in S false by Sfalse(1) , · · ·S false (N−), where S false (1) is the smallest order statistic and Sfalse(N−) is the largest order statistic. The following lemma motivates the performance of the rank-based method.
Lemma 1. The F1-score of detecting corrupted labels in Nj by the rank-based method will be no less than 1− α/N− when the true probability P(Y = j|Ỹ = j) is known and Sfalse(N−) < S true (α+1).
Lemma 1 connects the upper bound for the number of wrongly detected corrupted instances with order statistics. There are two cases that can cause detection errors: Case-1:
0 ≤ µtrue − Strue < ∆ and 0 ≤ Sfalse − µfalse < ∆ : at most α errors when Sfalse(N−) < S true (α+1).
and Case-2:
µtrue − Strue ≥ ∆ or Sfalse − µfalse ≥ ∆ : at most max(N−, N+) errors
We analyze each case as follows.
Case-1: When Case-1 holds, we have
P(µtrue − Strue = x) ≤ 1/∆, x ∈ [0,∆]
and P(Sfalse − µtrue = x) ≤ 1/∆, x ∈ [0,∆].
The above two inequalities show that the left tail of Strue and the right tail of Sfalse can be upper bounded by uniform distributions. Denote the corresponding uniform distribution by U true ∼ Unif(µtrue −∆, µtrue) and U false ∼ Unif(µfalse, µfalse + ∆).
With true P(Y = j|Ỹ = j), the detection errors only exist in the cases when the left tail of Strue and the right tail of Sfalse are overlapped. When the tails are upper bounded by uniform distributions, we have
P(Sfalse(N−) < S true (α+1)) ≥ P(U false (N−) < U true (α+1)) =P ([ U false − µfalse ] (N−) + µfalse < [ U true − (µtrue −∆) ] (α+1) + (µtrue −∆) )
=P ([ U false − µfalse ] (N−) − [ U true − (µtrue −∆) ] (α+1) < µtrue − µfalse −∆ ) .
Note [ U false − µfalse ] (N−) ∼ Beta(N−, 1), and [ U true − (µtrue −∆) ] (α+1) ∼ Beta(α+ 1, N+ − α),
where Beta denotes the Beta distribution. Both variables are independent. Thus the PDF of the difference is
f(p) =  B(N+ − α, 1)pN +−α(1 − p)α+1F (1, N− +N+, 1 −N−;α + 2; 1 − p, 1 − p2)/A, 0 < p ≤ 1 B(N−−, N+ − α)(−p)N +−α(1 + p)N −+N+−α−1F (N+ − α,−α,N− +N+;N− +N+ − α; 1 − p2, 1 + p)/A, −1 ≤ p < 0 B(N− + α,N+ − α)/A, p = 0,
where A = B(N−, 1)B(α+ 1, N+ − α), B(a, b) = ∫ 1
0 ta−1(1− t)b−1dt
F (a, b1, b2; c;x, y) = Γ(c)
Γ(a)Γ(c− a) ∫ 1 0 ta−1(1− t)c−a−1(1− xt)−b1(1− yt)−b2 dt.
Therefore, we have
P(Sfalse(N−) < S true (α+1)) ≥ ∫ µtrue−µfalse−∆ −1 f(p)dp.
Case-2 The other part, we have no more than e−v ·max(N−, N+) corrupted instances that may have higher scores than one clean instance. Wrap-up From the above analyses, we know, w.p. at least ∫ µtrue−µfalse−∆ −1 f(p)dp, there are at most e−v max(N−, N+) + α errors in detection corrupted instances. Note Precision = Recall if we detect with the best threshold NjP(Y = j|Ỹ = j). Therefore, the corresponding F1-score would be at least 1− e
−v max(N−,N+)+α N− .

heading: C EXPERIMENT SETTINGS ON CLOTHING1M

text:
We firstly perform noise detection on 1 million noisy training instances then train only with the selected clean data to check the effectiveness. Particularly, in each epoch of the noisy detection, we use a batch size of 32 and sample 1,000 mini-batches from 1M training instances while ensuring the (noisy) labels are balanced. We repeat noisy detection for 600 epochs to ensure a full coverage of 1 million training instances. Parameter k is set to 10.
Representation Extractor: We tested three different representation extractors in Table 4: R50Img, ViT-B/32-CLIP, and R50-Img Warmup-1. The former two representation extractors are the same as the ones used in Table 3. Particularly, R50-Img means the representation extractor is the standard ResNet50 encoder (removing the last linear layer) pre-trained on ImageNet (Deng et al., 2009). ViT-B/32-CLIP indicates the representation extractor is a vision transformer pre-trained by CLIP (Radford et al., 2021). Noting that Clothing1M is a fine-grained dataset. To get better domain-specific fine-grained visual representations, we slightly train the ResNet50 pre-trained with ImageNet for one epoch, i.e., 1,000 mini-batches (batch size 32) randomly sampled from 1M training instances while ensuring the (noisy) labels are balanced. The learning rate is 0.002.
Training with the selected clean instances: Given the selected clean instances from our approach, we directly apply the Cross-Entropy loss to train a ResNet50 initialized by standard ImageNet pre-trained parameters. We did not apply any sophisticated training techniques, e.g., mixup (Zhang et al., 2018), dual networks (Li et al., 2020b; Han et al., 2018), loss-correction (Liu & Tao, 2015; Natarajan et al., 2013; Patrini et al., 2017), and robust loss functions (Liu & Guo, 2020; Cheng et al., 2021; Zhu et al., 2021a; Wei & Liu, 2021). We train the model for 80 epochs with a batch size of 32. We sample 1, 000 mini-batches per epoch randomly selected from 1M training instances. Note Table 4 does not apply balanced sampling. Only the pure cross-entropy loss is applied. We also test the performance with balanced training, i.e., in each epoch, ensure the noisy labels from each class are balanced. Our approach can be consistently benefited by balanced training, and achieves an accuracy of 73.97 in the best epoch, outperforming many baselines such as HOC 73.39% (Zhu et al., 2021b), GCE+SimCLR 73.35% (Ghosh & Lan, 2021), CORES 73.24% (Cheng et al., 2021), GCE 69.75% (Zhang & Sabuncu, 2018). We believe the performance could be further improved by using some sophisticated training techniques mentioned above.

title: A GOOD REPRESENTATION DETECTS NOISY LABELS