Abstract
Practically, we often face the dilemma that some of the examples for training a classifier are incorrectly labeled due to various subjective and objective factors. Although intensive efforts have been put to design classifiers that are robust to label noise, most of the previous methods have not fully utilized data distribution information. To address this issue, this paper introduces a bi-level learning paradigm termed “Spectral Cluster Discovery'' (SCD) for combating with noisy labels. Namely, we simultaneously learn a robust classifier (Learning stage) by discovering the low-rank approximation to the ground-truth label matrix and learn an ideal affinity graph (Clustering stage). Specifically, we use the learned classifier to assign the examples with similar label to a mutual cluster. Based on the cluster membership, we utilize the learned affinity graph to explore the noisy examples based on the cluster membership. Both stages will reinforce each other iteratively. Experimental results on typical benchmark and real-world datasets verify the superiority of SCD to other label noise learning methods.
Introduction
Supervised learning models generally rely on the assumption that training labels represent the "ground truth." However, real-world datasets are frequently corrupted by noise stemming from human error, sensor inaccuracies, or inherent ambiguity. Standard models, particularly Deep Neural Networks, are prone to overfitting this noise, which severely degrades their generalization performance.
Existing approaches to mitigate label noise typically involve data cleansing heuristics or the design of robust loss functions. While useful, these methods often lack theoretical guarantees or require prior knowledge of the noise rate—a parameter rarely known in practice. This paper proposes Spectral Cluster Discovery (SCD), a framework that leverages the underlying data distribution to identify and correct noisy labels. The central intuition is that data points within the same natural cluster should share the same label; labels that contradict this local structure are likely erroneous.
Methodology: Spectral Cluster Discovery
SCD operates through a bi-level optimization paradigm that alternates between two interconnected stages: the Learning stage and the Clustering stage.
The Learning Stage (Upper Level)
The goal of this stage is to train a robust classifier by assuming that the true label matrix possesses a low-rank structure. The observed noisy labels are decomposed into a "clean" component, predicted by the model, and a sparse error component. By employing matrix factorization ($W = UV$), the model enforces this low-rank constraint, effectively filtering out random noise that does not align with the global structure of the data.
The Clustering Stage (Lower Level)
Simultaneously, the model constructs an "ideal" affinity graph constrained to have exactly $c$ connected components, where $c$ corresponds to the number of classes. This stage identifies clusters of similar examples. If an example's label deviates from the majority of its cluster companions, it is flagged as noisy and subsequently re-annotated.
These two stages reinforce each other iteratively: the classifier's predictions help refine the cluster structure, while the discovered clusters provide the structural evidence required to correct the classifier's training labels. This "self-correction" mechanism allows SCD to function effectively without a pre-defined noise rate.
Experimental Evaluation
The authors validated SCD across several benchmarks, including classic UCI datasets (Zoo, Seed, Haberman, Ionosphere, and German), the ISOLET speech recognition dataset, and the CIFAR-10 image classification dataset. To test the algorithm's limits, symmetric noise was manually injected at rates ranging from 0% to 60%.
Key Results
SCD consistently outperformed state-of-the-art baselines, such as Label Noise handling via Side Information (LNSI) and Rank Pruning.
- Robustness to High Noise: On the ISOLET dataset with 60% noise, SCD maintained an accuracy of 88.4%, significantly higher than LNSI (80.5%) and other methods which fell below 50%.
- Image Classification: On CIFAR-10, SCD achieved the highest accuracy across all noise levels, reaching 77.3% accuracy at 60% noise, compared to 71.6% for $\mu$SGD.
- Performance Stability: As shown in the UCI benchmarks, SCD maintains superior performance even as the noise rate increases, demonstrating its robustness.
Discussion and Conclusion
The success of SCD is rooted in its ability to maintain structural consistency. By treating label noise as a sparse error matrix added to a low-rank "true" label matrix, the problem is transformed into a well-defined matrix recovery task. Furthermore, the authors provide a theoretical upper bound on the generalization error using Rademacher complexity, ensuring that the empirical risk converges to the expected risk as sample size increases.
While SCD shows great promise, its computational complexity—specifically the $O(n^3)$ requirement for computing eigenvectors—may pose challenges for massive datasets. Future research could focus on integrating this bi-level spectral approach into end-to-end deep learning architectures and exploring its performance against instance-dependent noise.
Summary updated