Multi-class classification in the presence of labelling errors

Jakramate Bootkrajang, Ata KabánESANN 2011 · OpenReview

Abstract

Supervised learning typically assumes training labels are perfectly accurate. However, real-world datasets frequently contain "noisy" labels due to human error or subjective judgment. This paper presents robust Normal Discriminant Analysis (rNDA), a generative framework that explicitly models the mislabeling process. By treating true labels as latent variables and employing the Expectation-Maximization (EM) algorithm, rNDA maintains accurate decision boundaries even under high noise conditions, significantly outperforming traditional "noise-blind" classifiers.

Introduction

The reliability of supervised learning models is fundamentally tied to the quality of training data. Standard classifiers, such as Normal Discriminant Analysis (NDA), operate under the assumption that observed labels are ground truth. When labels are corrupted, these models often suffer from "covariance bloat," where class distributions expand to encompass mislabeled outliers, leading to degraded classification performance. While heuristic preprocessing methods like "depuration" exist, they often lack a rigorous probabilistic basis. This work introduces rNDA to provide a principled, model-based solution for multi-class classification with noisy labels.

Methodology

The rNDA approach extends multi-class quadratic normal discriminant analysis by incorporating a hidden variable for the true label.

  • Generative Framework: The model represents the joint probability of features and labels as a mixture model, where the observed label is a noisy version of a latent true label.
  • Transition Model: A "flip" model is introduced via transition probabilities $\gamma_{jk}$, representing the likelihood that a sample truly belonging to class $k$ is observed as class $j$.
  • Optimization: Parameters are estimated using the Expectation-Maximization (EM) algorithm. The E-step computes the posterior probability of the true label, while the M-step updates class means, covariances, and transition probabilities to maximize expected log-likelihood.
  • Inference: For new data, the model marginalizes over potential observed labels to determine the most probable class.

Key Insights: Preventing Covariance Bloat

A primary advantage of rNDA is its ability to resist the distorting effects of outliers. In standard NDA, mislabeled points pull the estimated class means and stretch the covariance ellipses. rNDA identifies these points as likely errors, effectively downweighting their influence on the distribution parameters. This prevents the "bloat" that typically compromises decision boundaries in high-noise scenarios.

Visualizing rNDA's ability to recover true class distributions and decision boundaries despite label noise.

Experimental Results

The authors evaluated rNDA against standard NDA, k-Nearest Neighbors (k-NN), and depuration-based methods using both synthetic and UCI repository datasets (Iris and Wine).

Synthetic Performance

In synthetic tests, rNDA demonstrated remarkable resilience, maintaining high accuracy even when label noise reached 70%. Notably, the performance gap between rNDA and other methods widened as the dimensionality of the feature space increased, suggesting that the model-based approach is particularly effective for complex data.

Accuracy comparison across varying levels of label noise for a 5-class synthetic problem.

Real-world Benchmarks

On real-world benchmarks like the Iris (4D) and Wine (13D) datasets, rNDA consistently achieved top-tier performance. While depuration was competitive on the Wine dataset, rNDA's generative nature provided more stable results across different noise levels.

Conclusion and Future Work

rNDA offers a robust alternative to traditional discriminant analysis by explicitly accounting for labeling errors. By integrating the noise process into the generative model, it recovers more accurate class parameters than heuristic methods. A current limitation is the assumption of Gaussian class distributions. Future work will focus on relaxing this assumption to accommodate non-normal or multimodal data, further broadening the applicability of this noise-aware framework.

Summary updated

BibTeX
@inproceedings{bootkrajang2011multi,
  author = {Jakramate Bootkrajang and Ata Kabán},
  title = {{Multi-class classification in the presence of labelling errors}},
  booktitle = {ESANN},
  year = {2011},
  url = {https://openreview.net/forum?id=g773giuGKf0O},
}
Figure