Noise Tolerance of EP-Based Classifiers

Qun Sun, Xiuzhen Zhang, Kotagiri RamamohanaraoAustralian Conference on Artificial Intelligence 2003 · DOI

TL;DR

This paper investigates the noise tolerance of Emerging Pattern (EP)-based classifiers, specifically focusing on whether they overfit. The authors demonstrate that EP-based classifiers, due to their aggregating approach, are surprisingly robust to noise and do not exhibit overfitting, even with perfect training accuracy.

What Problem Does This Paper Address?

In machine learning, classifiers are often susceptible to noise in the training data, which can lead to overfitting. Overfitting occurs when a model learns the training data too well, including its noise, resulting in poor performance on unseen data. While many classifiers are sensitive to noise, this paper specifically examines EP-based classifiers, a promising class of algorithms that leverage itemsets with significant occurrence differences between datasets. A key concern for these classifiers is whether their potential for perfect training accuracy (especially for JEP classifiers) makes them prone to overfitting and thus less tolerant to noisy data.

Methods

The paper proposes a new EP-based classifier called CAEEP (Classification by Aggregating Essential EPs), which builds upon the CAEP classifier by introducing consistency and generality controls during the EP mining phase. These controls aim to regulate the quality of mined EPs. The core classification mechanism for both CAEP and CAEEP, as well as the JEP classifier, relies on an aggregating approach. This means that individual EPs (or JEPs) are weak classifiers, and their collective contribution to an aggregate score determines the final class prediction.

The study employs two main experiments:

  1. Experiment One: Compares CAEEP with CAEP on various datasets with different types of noise (attribute, label, and mixed) to assess the impact of consistency and generality controls and to observe their noise tolerance.
  2. Experiment Two: Systematically compares the noise tolerance of six classifiers (JEP, CAEP, CAEEP, C5.0, kNN, and NB) by analyzing their learning curves under different noise conditions. Learning ability is measured by the area under the learning curve.

Datasets

The experiments utilize datasets from the UCI Repository. While specific dataset names are not listed in the provided text, the paper mentions using 23 datasets for Experiment One and 22 datasets for Experiment Two. The "ionosphere" dataset is used as an example for illustrating learning curves in Experiment Two.

Key Insights and Ideas

  • Aggregating Approach as an Overfitting Antidote: The most significant finding is that the aggregating approach used in EP-based classifiers (CAEP, CAEEP, JEP) effectively prevents overfitting, even when achieving perfect training accuracy. This challenges the conventional wisdom that perfect training accuracy is a direct indicator of overfitting.
  • JEP Classifier's Robustness: Despite its guarantee of 100% training accuracy, the JEP classifier demonstrates good noise tolerance, contrary to initial expectations. The paper attributes this to the aggregating nature of JEPs, where individual noisy JEPs have minimal impact on the overall aggregated score.
  • Consistency and Generality Controls: While CAEEP's consistency and generality controls improve accuracy on clean datasets compared to CAEP, their impact on noisy datasets is less pronounced, suggesting that both CAEP and CAEEP are inherently noise-tolerant.
  • Noise Tolerance Hierarchy: Classifiers generally exhibit better tolerance to attribute noise than label noise, and better tolerance to label noise than mixed noise.
  • Impact of Class Labels: The impact of label noise is more pronounced in datasets with a larger number of class labels.

Key Results

  • Experiment One: CAEEP outperforms CAEP on clean datasets, but their performance is similar on noisy datasets, indicating that both are noise-tolerant.
  • Experiment Two (Learning Curves):
    • EP-based classifiers (CAEP, CAEEP, JEP) generally show good noise tolerance.
  • NB (Naive Bayesian) performs best overall with noise.
  • kNN performs worst under noise, likely due to its reliance on closest instances that can be contaminated.
  • JEP, C5.0, and CAE(E)P are ranked in between NB and kNN in terms of noise tolerance.
  • Noise Levels: The study uses 40% attribute noise, 40% label noise, and 40% mixed noise for training datasets.

Limitations and Future Work

  • Computational Cost: The paper mentions that the experiments, particularly the learning curve analysis, take a very long time to finish, necessitating the use of 10-fold Generalised Cross Validation only once for plotting learning curves.
  • Future Work: Not explicitly detailed, but the findings suggest further exploration into the mechanisms of aggregating approaches for noise tolerance in other classifier types. The paper also implicitly suggests that the consistency and generality controls in CAEEP could be further refined.

Summary updated

BibTeX
@inproceedings{sun2003noise,
  author = {Qun Sun and Xiuzhen Zhang and Kotagiri Ramamohanarao},
  title = {{Noise Tolerance of EP-Based Classifiers}},
  booktitle = {Australian Conference on Artificial Intelligence},
  year = {2003},
  doi = {10.1007/978-3-540-24581-0\_68},
}
Figure