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.  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. 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). 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.
references.authors: Vibhu Agarwal Tanya Podchiyska Juan M Banda Veena Goel Tiffany I Leung Evan P Minty Timothy E Sweeney Elsie Gyang Nigam H Shah
references.title: Learning statistical models of phenotypes using noisy labeled training data
references.venue: Journal of the American Medical Informatics Association,
references.authors: Ehsan Amid Manfred KK Warmuth Rohan Anil Tomer Koren
references.title: Robust bi-tempered logistic loss based on bregman divergences
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Dara Bahri Heinrich Jiang Maya Gupta
references.title: Deep k-nn for noisy labels
references.venue: In International Conference on Machine Learning,
references.authors: David Berthelot Nicholas Carlini Ian Goodfellow Nicolas Papernot Avital Oliver Colin Raffel
references.title: Mixmatch: A holistic approach to semi-supervised learning
references.authors: Valerii V Buldygin Yu V Kozachenko
references.title: Sub-gaussian random variables
references.venue: Ukrainian Mathematical Journal,
references.authors: Ting Chen Simon Kornblith Mohammad Norouzi Geoffrey Hinton
references.title: A simple framework for contrastive learning of visual representations
references.venue: In International conference on machine learning,
references.authors: Hao Cheng Zhaowei Zhu Xingyu Li Yifei Gong Xing Sun Yang Liu
references.title: Learning with instancedependent label noise: A sample sieve approach
references.venue: In International Conference on Learning Representations,
references.authors: J. Deng W. Dong R. Socher L.-J. Li K. Li L. Fei-Fei
references.title: ImageNet: A Large-Scale Hierarchical Image Database
references.venue: In CVPR09,
references.authors: Jacob Devlin Ming-Wei Chang Kenton Lee Kristina Toutanova. Bert
references.title: Pre-training of deep bidirectional transformers for language understanding
references.venue: arXiv preprint arXiv:1810.04805,
references.authors: Wei Gao Bin-Bin Yang Zhi-Hua Zhou
references.title: On the resistance of nearest neighbor to random noisy labels
references.venue: arXiv preprint arXiv:1607.07526,
references.authors: Aritra Ghosh Andrew Lan
references.title: Contrastive learning improves model robustness under label noise
references.venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,
references.authors: Aritra Ghosh Himanshu Kumar PS Sastry
references.title: Robust loss functions under label noise for deep neural networks
references.venue: In Thirty-First AAAI Conference on Artificial Intelligence,
references.authors: Maoguo Gong Hao Li Deyu Meng Qiguang Miao Jia Liu
references.title: Decomposition-based evolutionary multiobjective optimization to self-paced learning
references.venue: IEEE Transactions on Evolutionary Computation,
references.authors: Priya Goyal Piotr Dollár Ross Girshick Pieter Noordhuis Lukasz Wesolowski Aapo Kyrola Andrew Tulloch Yangqing Jia Kaiming He
references.title: Accurate, large minibatch sgd: Training imagenet in 1 hour
references.venue: arXiv preprint arXiv:1706.02677,
references.authors: Bo Han Quanming Yao Xingrui Yu Gang Niu Miao Xu Weihua Hu Ivor Tsang Masashi Sugiyama
references.title: Co-teaching: Robust training of deep neural networks with extremely noisy labels
references.venue: In Advances in neural information processing systems,
references.authors: Bo Han Quanming Yao Tongliang Liu Gang Niu Ivor W Tsang James T Kwok Masashi Sugiyama
references.title: A survey of label-noise representation learning: Past, present and future
references.authors: Kaiming He Haoqi Fan Yuxin Wu Saining Xie Ross Girshick
references.title: Momentum contrast for unsupervised visual representation learning
references.venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,
references.authors: Xu Ji João F Henriques Andrea Vedaldi
references.title: Invariant information clustering for unsupervised image classification and segmentation
references.venue: In Proceedings of the IEEE/CVF International Conference on Computer Vision,
references.authors: Lu Jiang Zhengyuan Zhou Thomas Leung Li-Jia Li Li Fei-Fei
references.title: Mentornet: Learning datadriven curriculum for very deep neural networks on corrupted labels
references.venue: In International Conference on Machine Learning,
references.authors: Lu Jiang Di Huang Mason Liu Weilong Yang
references.title: Beyond synthetic noise: Deep learning on controlled noisy labels
references.venue: In International Conference on Machine Learning,
references.authors: David R Karger Sewoong Oh Devavrat Shah
references.title: Efficient crowdsourcing for multi-class labeling
references.venue: In Proceedings of the ACM SIGMETRICS/international conference on Measurement and modeling of computer systems,
references.authors: D.R. Karger S. Oh D. Shah
references.title: Iterative learning for reliable crowdsourcing systems
references.venue: In Neural Information Processing Systems, NIPS
references.authors: Alex Krizhevsky Geoffrey Hinton
references.title: Learning multiple layers of features from tiny images
references.venue: Technical report, Citeseer,
references.authors: Alex Krizhevsky Ilya Sutskever Geoffrey E Hinton
references.title: Imagenet classification with deep convolutional neural networks
references.venue: Advances in neural information processing systems,
references.authors: Jingling Li Mozhi Zhang Keyulu Xu John P Dickerson Jimmy Ba
references.title: Noisy labels can induce good representations
references.venue: arXiv preprint arXiv:2012.12896,
references.authors: Junnan Li Richard Socher Steven C.H. Hoi
references.title: Dividemix: Learning with noisy labels as semisupervised learning
references.venue: In International Conference on Learning Representations,
references.authors: Xuefeng Li Tongliang Liu Bo Han Gang Niu Masashi Sugiyama
references.title: Provably end-to-end labelnoise learning without anchor points
references.venue: arXiv preprint arXiv:2102.02400,
references.authors: Andy T Liu Shang-Wen Li Hung-yi Lee
references.title: Tera: Self-supervised learning of transformer encoder representation for speech
references.venue: IEEE/ACM Transactions on Audio, Speech, and Language Processing,
references.authors: Qiang Liu Jian Peng Alexander Ihler
references.title: Variational inference for crowdsourcing
references.venue: In Proceedings of the 25th International Conference on Neural Information Processing Systems-Volume
references.authors: Sheng Liu Jonathan Niles-Weed Narges Razavian Carlos Fernandez-Granda
references.title: Early-learning regularization prevents memorization of noisy labels
references.venue: arXiv preprint arXiv:2007.00151,
references.authors: Tongliang Liu Dacheng Tao
references.title: Classification with noisy labels by importance reweighting
references.venue: IEEE Transactions on pattern analysis and machine intelligence,
references.authors: Yang Liu
references.title: Understanding instance-level label noise: Disparate impacts and treatments
references.venue: In International Conference on Machine Learning,
references.authors: Yang Liu Hongyi Guo
references.title: Peer loss functions: Learning from noisy labels without knowing noise rates
references.venue: In Proceedings of the 37th International Conference on Machine Learning,
references.authors: Yang Liu Mingyan Liu
references.title: An online learning approach to improving the quality of crowdsourcing
references.venue: ACM SIGMETRICS Performance Evaluation Review,
references.authors: Huixiang Luo Hao Cheng Yuting Gao Ke Li Mengdan Zhang Fanxu Meng Xiaowei Guo Feiyue Huang Xing Sun
references.title: On the consistency training for open-set semi-supervised learning, 2021
references.authors: Nagarajan Natarajan Inderjit S Dhillon Pradeep K Ravikumar Ambuj Tewari
references.title: Learning with noisy labels
references.venue: In Advances in neural information processing systems,
references.authors: Duc Tam Nguyen Chaithanya Kumar Mummadi Thi Phuong Nhung Ngo Thi Hoai Phuong Nguyen Laura Beggel Thomas Brox
references.title: Self: Learning to filter noisy labels with selfensembling
references.authors: Curtis Northcutt Lu Jiang Isaac Chuang
references.title: Confident learning: Estimating uncertainty in dataset labels
references.venue: Journal of Artificial Intelligence Research,
references.authors: Curtis G Northcutt Anish Athalye Jonas Mueller
references.title: Pervasive label errors in test sets destabilize machine learning benchmarks
references.venue: arXiv preprint arXiv:2103.14749,
references.authors: Giorgio Patrini Alessandro Rozza Aditya Krishna Menon Richard Nock Lizhen Qu
references.title: Making deep neural networks robust to label noise: A loss correction approach
references.venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Garima Pruthi Frederick Liu Satyen Kale Mukund Sundararajan
references.title: Estimating training data influence by tracing gradient descent
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Alec Radford Jong Wook Kim Chris Hallacy Aditya Ramesh Gabriel Goh Sandhini Agarwal Girish Sastry Amanda Askell Pamela Mishkin Jack Clark
references.title: Learning transferable visual models from natural language supervision
references.venue: arXiv preprint arXiv:2103.00020,
references.authors: Pierre Sermanet David Eigen Xiang Zhang Michaël Mathieu Rob Fergus Yann LeCun
references.title: Overfeat: Integrated recognition, localization and detection using convolutional networks
references.venue: arXiv preprint arXiv:1312.6229,
references.authors: Jun Shu Qian Zhao Keyu Chen Zongben Xu Deyu Meng
references.title: Learning adaptive loss for robust learning with noisy labels
references.venue: arXiv preprint arXiv:2002.06482,
references.authors: Chuanqi Tan Fuchun Sun Tao Kong Wenchang Zhang Chao Yang Chunfang Liu
references.title: A survey on deep transfer learning
references.venue: In International conference on artificial neural networks,
references.authors: Jialu Wang Yang Liu Caleb Levy
references.title: Fair classification with group-dependent label noise
references.venue: FAccT, pp. 526–536,
references.authors: Yisen Wang Xingjun Ma Zaiyi Chen Yuan Luo Jinfeng Yi James Bailey
references.title: Symmetric cross entropy for robust learning with noisy labels
references.venue: In Proceedings of the IEEE International Conference on Computer Vision,
references.authors: Hongxin Wei Lei Feng Xiangyu Chen Bo An
references.title: Combating noisy labels by agreement: A joint training method with co-regularization
references.venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,
references.authors: Jiaheng Wei Yang Liu
references.title: When optimizing f-divergence is robust with label noise
references.venue: In International Conference on Learning Representations,
references.authors: Xiaobo Xia Tongliang Liu Nannan Wang Bo Han Chen Gong Gang Niu Masashi Sugiyama
references.title: Are anchor points really indispensable in label-noise learning
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Xiaobo Xia Tongliang Liu Bo Han Nannan Wang Jiankang Deng Jiatong Li Yinian Mao
references.title: Extended T: Learning with mixed closed-set and open-set noisy labels
references.venue: arXiv preprint arXiv:2012.00932,
references.authors: Xiaobo Xia Tongliang Liu Bo Han Nannan Wang Mingming Gong Haifeng Liu Gang Niu Dacheng Tao Masashi Sugiyama
references.title: Part-dependent label noise: Towards instance-dependent label noise
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Xiaobo Xia Tongliang Liu Bo Han Chen Gong Nannan Wang Zongyuan Ge Yi Chang
references.title: Robust early-learning: Hindering the memorization of noisy labels
references.venue: In International Conference on Learning Representations,
references.authors: Tong Xiao Tian Xia Yi Yang Chang Huang Xiaogang Wang
references.title: Learning from massive noisy labeled data for image classification
references.venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Qizhe Xie Zihang Dai Eduard Hovy Minh-Thang Luong Quoc V Le
references.title: Unsupervised data augmentation
references.venue: arXiv preprint arXiv:1904.12848,
references.authors: Quanming Yao Hansi Yang Bo Han Gang Niu James T Kwok
references.title: Searching to exploit memorization effect in learning with noisy labels
references.venue: In Proceedings of the 37th International Conference on Machine Learning,
references.authors: Xingrui Yu Bo Han Jiangchao Yao Gang Niu Ivor Tsang Masashi Sugiyama
references.title: How does disagreement help generalization against label corruption
references.venue: In Proceedings of the 36th International Conference on Machine Learning,
references.authors: Matthew D Zeiler Rob Fergus
references.title: Visualizing and understanding convolutional networks
references.venue: In European conference on computer vision,
references.authors: Hongyi Zhang Moustapha Cisse Yann N. Dauphin David Lopez-Paz
references.title: mixup: Beyond empirical risk minimization
references.venue: In International Conference on Learning Representations,
references.authors: Jing Zhang Victor S Sheng Tao Li Xindong Wu
references.title: Improving crowdsourced label quality using noise correction
references.venue: IEEE transactions on neural networks and learning systems,
references.authors: Yikai Zhang Songzhu Zheng Pengxiang Wu Mayank Goswami Chao Chen
references.title: Learning with feature-dependent label noise: A progressive approach
references.venue: arXiv preprint arXiv:2103.07756,
references.authors: Yuchen Zhang Xi Chen Dengyong Zhou Michael I Jordan
references.title: Spectral methods meet em: A provably optimal algorithm for crowdsourcing
references.venue: Advances in neural information processing systems,
references.authors: Zhilu Zhang Mert Sabuncu
references.title: Generalized cross entropy loss for training deep neural networks with noisy labels
references.venue: In Advances in neural information processing systems,
references.authors: Zhaowei Zhu Tongliang Liu Yang Liu
references.title: A second-order approach to learning with instancedependent label noise
references.venue: In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR),
references.authors: Zhaowei Zhu Yiwen Song Yang Liu
references.title: Clusterability as an alternative to anchor points when learning with noisy labels
references.venue: In Proceedings of the 38th International Conference on Machine Learning,
references.authors: Zhaowei Zhu Jingxuan Zhu Ji Liu Yang Liu
references.title: Federated bandit: A gossiping approach
references.venue: In Abstract Proceedings of the 2021 ACM SIGMETRICS/International Conference on Measurement and Modeling of Computer Systems,
references.authors: 2020b Li et al Han et al loss-correction (Liu 2015 Tao Natarajan
references.title: Patrini et al., 2017), and robust loss functions (Liu & Guo, 2020
references.venue: (Zhang et al.,
sections.heading: 1 INTRODUCTION
sections.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.
sections.heading: 1.1 RELATED WORKS
sections.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.
sections.heading: 2 PRELIMINARIES
sections.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) .
sections.heading: 3 LABEL NOISE DETECTION USING SIMILAR REPRESENTATIONS
sections.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.
sections.heading: 3.1 INTUITIONS
sections.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.
sections.heading: 3.2 VOTING-BASED LOCAL DETECTION
sections.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.
sections.heading: 3.3 RANKING-BASED GLOBAL DETECTION
sections.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.
sections.heading: 4 HOW DO REPRESENTATIONS AFFECT OUR SOLUTION?
sections.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.
sections.heading: 5 EMPIRICAL RESULTS
sections.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.
sections.heading: 5.1 SUPERVISION MAY NOT BE NECESSARY
sections.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.
sections.heading: 5.2 REPRESENTATION LAYERS MAY PERFORM BETTER THAN LOGIT LAYERS
sections.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.
sections.heading: 5.3 WHAT ARE GOOD REPRESENTATIONS
sections.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.
sections.heading: 6 CONCLUSIONS
sections.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.
sections.heading: A THEORETICAL ANALYSES
sections.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.
sections.heading: B PROOF FOR THEOREM 1
sections.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− .
sections.heading: C EXPERIMENT SETTINGS ON CLOTHING1M
sections.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