Attribute noise robust binary classification

Aditya Petety, Sandhya Tripathi, N. Hemachandra

Introduction

In machine learning, the assumption of "clean" data is often a luxury. While significant research has focused on label noise (incorrectly categorized instances), attribute noise—errors within the features themselves—remains a critical yet under-explored challenge, particularly for categorical data. For binary features, such as a sensor reporting "high" or "low," a single bit flip can drastically alter a data point's position in feature space, potentially leading a classifier to erroneous conclusions.

This paper investigates how binary attribute noise affects linear classification. The authors explore two specific noise models:

  1. Symmetric Dependent (Sy-De): All features flip simultaneously with the same probability, simulating systemic failures like a total power loss.
  2. Asymmetric Independent (Asy-In): Each feature flips independently with its own probability, representing individual component failures.

Theoretical Framework and Insights

The study utilizes the Empirical Risk Minimization (ERM) framework to compare the robustness of two primary loss functions: the standard 0-1 loss ($l_{0-1}$) and the squared loss ($l_{sq}$).

A central finding is the Robustness Paradox: counter-intuitively, the standard 0-1 loss is fragile under symmetric dependent noise, whereas the squared loss proves theoretically robust. The authors demonstrate that under Sy-De noise, the optimal weight vector for noisy data is simply a scaled version of the clean optimal vector. Because linear classification boundaries depend only on the sign of the function, this scaling preserves the decision boundary, allowing for accurate classification without needing to estimate noise rates or perform complex cross-validation.

However, robustness is highly sensitive to the noise structure. While 0-1 loss was proven robust to independent noise (Asy-In) in 2D spaces, squared loss failed this test, suggesting that the choice of surrogate loss must be carefully matched to the expected noise model.

Empirical Evaluation and Key Results

The theoretical findings were validated using three binary classification datasets from the UCI Machine Learning Repository: Vote (congressional records), SPECT (cardiac imaging), and KR-vs-KP (chess endgame positions).

Average accuracy and AM metrics across UCI datasets under varying noise rates.

The experiments confirmed that squared loss maintains high performance under Sy-De noise. As shown in the figure above, metrics like Average Accuracy and Average AM (Arithmetic Mean of sensitivity and specificity) remain relatively stable across different datasets as noise rates increase. For instance, on the Vote dataset, performance holds steady until noise rates approach 0.3. The eventual degradation at very high noise levels (0.4) is attributed to finite sample sizes, where the noise signal begins to overwhelm the available data.

Limitations and Future Directions

While providing a strong theoretical foundation for attribute noise robustness, the work has several limitations:

  • Binary Constraint: The proofs are currently limited to binary-valued attributes. Extending these results to general discrete or continuous features is a primary area for future work.
  • Dimensionality: The robustness of 0-1 loss under independent noise was only proven for 2D spaces; its behavior in higher-dimensional real-world scenarios remains an open question.
  • Surrogate Search: Since squared loss is not robust to independent noise, the search continues for other convex surrogate losses (e.g., logistic or hinge loss) that might offer broader resilience.

By identifying that simple squared loss can inherently handle systemic attribute noise, this research offers a practical, computationally efficient path for building more resilient machine learning systems.

Summary updated

BibTeX
@inproceedings{petety2020attribute,
  author = {Aditya Petety and Sandhya Tripathi and N. Hemachandra},
  title = {{Attribute noise robust binary classification}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i10.7221},
}
Figure