Error Correlation and Error Reduction in Ensemble Classifiers

Kagan Tumer, Joydeep GhoshConnect. Sci 1996 · DOI

TL;DR

This paper investigates how the correlation between individual classifiers in an ensemble affects the overall error reduction. The authors propose and evaluate several methods to reduce this correlation, demonstrating that while reducing correlation can improve performance, it's crucial to balance this with maintaining individual classifier accuracy, especially with limited data.

What Problem Does This Paper Address?

Ensemble methods, which combine multiple classifiers, are known to improve generalization performance over single classifiers. However, the effectiveness of combining is heavily influenced by the characteristics of the individual classifiers being combined, particularly the correlation between their errors. If classifiers make similar mistakes, combining them offers little benefit. This paper addresses the challenge of preparing classifiers for effective combination by focusing on methods that reduce the correlation among them, thereby maximizing the potential for error reduction. The authors highlight that the choice of combining method is often less critical than how the individual classifiers are trained and selected.

Methods

The paper explores four primary methods for reducing correlation among ensemble classifiers:

  • k-1-of-k Trained Classifiers: This method leverages k-fold cross-validation. The training data is split into k subsets. For each classifier, k-1 subsets are used for training, and the remaining subset is held out. By rotating which subset is held out, k classifiers are trained on slightly different data partitions, leading to reduced correlation.
  • Input Decimation Combining: This feature-level approach aims to reduce correlation by selectively pruning input features. For each of the L output classes, a subset of inputs that have low correlation with that class is removed. This results in L classifiers, each trained on a slightly different feature set, potentially reducing inter-classifier correlation.
  • Resampled Set Combining (Bagging): This technique involves generating different training sets for each classifier by resampling the original dataset. This is commonly known as bootstrapping. The paper notes that Breiman popularized this for improving predictor performance, calling it "bagging." For classification, bagging typically uses a majority vote, but here it's adapted for linear combiners.
  • Weighted Experts: This method is based on the mixture of experts framework. A gating network determines the weights for individual "expert" networks (classifiers) based on the input. This effectively partitions the input space, allowing different experts to specialize in different regions, which can lead to reduced correlation.

Datasets

The paper uses the following datasets for evaluation:

  • Underwater Sonar Data: A 25-dimensional dataset extracted from underwater acoustic signals, chosen for its complexity, high dimensionality, and an estimated Bayes error rate of ~3.61%. It contains 496 training patterns and 823 test patterns.
  • Proben1 Benchmarks: This includes three datasets:
  • CANCER1: Based on breast cancer data, with 9 inputs, 2 outputs, and 350 training patterns out of 699 total.
  • GLASS1: Based on chemical analysis of glass splinters, with 9 inputs, 6 classes, and 107 training patterns out of 214 total.
  • GENE1: Based on intron/exon boundary detection in DNA sequences, with 120 inputs, and 1588 training patterns out of 3175 total.

Key Insights and Ideas

  • Correlation is Key: The paper strongly emphasizes that reducing the correlation among individual classifiers is as, if not more, important than the choice of the combining method itself for achieving significant error reduction.
  • Data Limitation is a Bottleneck: When training data is scarce, methods that reduce classifier correlation by using smaller subsets of the data (like k-1-of-k or resampling) can lead to a significant drop in individual classifier performance, negating the benefits of reduced correlation.
  • RBF Networks Benefit More: The authors observed that Radial Basis Function (RBF) networks, due to their more localized tuning, often showed more significant improvements when combined using correlation-reducing techniques compared to Multi-Layer Perceptrons (MLPs).
  • Input Decimation is Tricky: Feature space partitioning (input decimation) proved difficult to fine-tune, with small changes leading to large performance shifts.
  • Weighted Experts Offer a Different Approach: The weighted expert method, by spatially partitioning patterns, showed promise by allowing experts to specialize without necessarily disrupting the combiner's performance, even with varying expert expertise.

Key Results

  • k-1-of-k Training: For the sonar dataset, combining three MLPs trained using 2-of-3 training yielded a 12.4% improvement over individual classifiers, significantly better than the 3.75% improvement from combining MLPs trained on the full dataset. However, using k=3 with limited data proved insufficient. When k=7 (6-of-7 training), performance improved for RBF networks.
  • Input Decimation: This method showed some performance improvements, but the gains were often offset by a drop in individual classifier performance.
  • Resampled Set Combining: With sufficient data (doubled resampled set size), this method showed promising results, particularly for RBF ensembles, leading to mild improvements.
  • Weighted Experts: Combining seven MLP experts provided satisfactory results, while RBF experts showed less consistent gains.
  • Proben1 Benchmarks:
    • CANCER1: Combining MLPs reduced the error rate from 0.69% to 0.60%, primarily increasing reliability by reducing standard deviation.
  • GLASS1: Combining improved performance, but correlation reduction methods failed due to the extremely small sample size.
  • GENE1: Combining improved results, with RBF ensembles showing significant gains after resampling, especially for N=5 and N=10.

Limitations and Future Work

  • Data Scarcity: The most significant limitation identified is the trade-off between reduced correlation and individual classifier performance, especially when training data is limited. Methods that reduce training set size can lead to poor individual classifier accuracy, negating ensemble benefits.
  • Fine-tuning Complexity: Methods like input decimation are noted as being difficult to fine-tune.
  • Future Work: The paper suggests that if data is not a constraint, k-1-of-k training or resampling are promising avenues. An exception is when cross-validation is already used for model selection, as it naturally provides multiple trained classifiers as a byproduct. The authors also implicitly suggest further exploration into the weighted expert framework and finding the optimal balance between correlation reduction and individual classifier performance.

Summary updated

BibTeX
@article{tumer1996error,
  author = {Kagan Tumer and Joydeep Ghosh},
  title = {{Error Correlation and Error Reduction in Ensemble Classifiers}},
  journal = {Connect. Sci.},
  year = {1996},
  doi = {10.1080/095400996116839},
}
Figure