Classifier Learning from Noisy Data as Probabilistic Evidence Combination

Steven W. Norton, Haym HirshAAAI 1992

Abstract

This paper reframes the challenge of learning from noisy data as a Bayesian inference problem. By combining Mitchell’s "version spaces" with a probabilistic noise model, the authors develop an incremental algorithm that significantly outperforms standard methods like C4.5 when training data is limited.

Introduction

In the early 1990s, machine learning algorithms typically handled noise by either assuming perfect data or employing heuristics like tree pruning. Norton and Hirsh propose a more robust alternative: exploiting explicit knowledge about noise. By integrating probabilistic information (e.g., a known 10% sensor error rate) into a symbolic learning framework, they aim to maintain a set of plausible "true" classifiers despite corrupted observations.

Methodology: MAP and Evidence Combination

The authors propose a Maximum A Posteriori (MAP) approach. Rather than seeking a single classifier to fit noisy data, the algorithm identifies the classifier most likely to be correct given the observations and a known noise model.

The algorithm distinguishes between "observed" noisy sequences and "supposed" hypothetical true sequences. As each example arrives, it performs incremental evidence combination, updating a list of version spaces—sets of classifiers consistent with specific hypotheses. Each version space is assigned a probability based on the noise model.

Probabilistic evidence combination for observed examples.

To manage computational complexity and prevent a "combinatoric explosion," the algorithm employs a pruning strategy, discarding any hypothesis at least 1000 times less likely than the current leader. It utilizes the "boundary-set" representation (S and G sets) to handle symbolic and generalized attributes efficiently.

Experimental Setup

The algorithm was evaluated across several domains:

  • Synthetic Conjunctive Concepts: Datasets with 6 to 10 binary attributes and label noise ranging from 0% to 25%.
  • Iris Flower Database: A standard real-world classification benchmark.
  • DNA Promoter Sequences: A biological dataset used to test performance on complex symbolic data.

Key Results and Discussion

The MAP approach demonstrates a significant "early learning advantage." While heuristic learners like C4.5 require substantial data to average out noise, this probabilistic method leverages the noise model to make high-quality inferences from the very first examples.

Learning curve showing generalization scores over 500 samples.

In experiments with 25% label noise, the MAP approach showed a statistically significant advantage over C4.5 during the first 100 examples. While both methods eventually converge to similar accuracy levels on large datasets, the MAP approach reaches high accuracy much faster. Furthermore, the algorithm proved robust even when the assumed noise model did not perfectly match the actual environmental noise.

Limitations and Future Work

The primary limitation is the requirement for a pre-defined noise model, which is often unavailable in real-world scenarios. Future research should focus on learning noise model parameters concurrently with the classifier. Additionally, while pruning manages overhead, the growth of boundary sets in complex hypothesis languages remains a challenge, and further testing is needed for non-conjunctive concepts like Disjunctive Normal Form (DNF).

Summary updated

BibTeX
@inproceedings{norton1992classifier,
  author = {Steven W. Norton and Haym Hirsh},
  title = {{Classifier Learning from Noisy Data as Probabilistic Evidence Combination}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1992},
}
Figure