Empirical comparisons of various voting methods in bagging

Kelvin T. Leung, Douglas Stott Parker Jr.KDD 2003 · DOI

TL;DR

This paper investigates how different voting methods, beyond the standard plurality, impact the performance of bagging ensembles for classification. They found that plurality isn't always the best, and factors like the number of classes and dataset noise significantly influence which voting method performs optimally.

What Problem Does This Paper Address?

In machine learning, especially with large datasets, ensembles of models (like bagging) are used to improve prediction accuracy by combining multiple individual models. A crucial step in these ensembles is "model reconciliation," where the predictions from individual models are combined into a single final prediction. The most common method for this is plurality voting, where the class with the most votes wins. However, this method is simple but can be suboptimal, especially when dealing with more than two classes or when the "strength" of a vote (i.e., how preferred a class is) is important. This paper explores whether other, more sophisticated voting methods from social choice theory can lead to better classification performance in bagging.

Methods

The authors compare several preferential voting methods for model reconciliation within a bagging framework. These methods include:

  • Plurality Voting: The standard method where the class with the most first-place votes wins.
  • Anti-Plurality Voting: Each expert votes against their least preferred class.
  • Borda Count Method: A positional scoring system where classes are awarded points based on their rank in an expert's preference order (e.g., k-1 points for first choice, k-2 for second, etc., in a k-class problem).
  • Plurality with Elimination: A multi-round process where the candidate with the fewest votes is eliminated in each round until a winner emerges.
  • Condorcet's Pairwise Comparison: Each candidate is compared head-to-head with every other candidate, and the one who wins all pairwise comparisons is the winner.

They implement these methods within a bagging ensemble, where base classifiers (decision trees) are trained on bootstrapped samples of the data. For each test instance, the ensemble's predictions are collected, and then one of the voting methods is used to reconcile these predictions into a final class label.

Datasets

The experiments were conducted on 39 datasets from the UCI repository. The paper provides a table detailing the number of training instances, testing instances, attributes, whether missing data was present, and the number of classes for each dataset. No new benchmarks were introduced; existing datasets were used.

Key Insights and Ideas

  • Plurality is Not Always King: The most surprising finding is that the commonly used plurality voting method did not consistently perform the best. This suggests that simpler methods might be leaving valuable information on the table.
  • The Number of Classes Matters: The performance of voting methods can be significantly influenced by the number of classes in the problem. Two-class problems behave differently from multi-class problems, and methods that leverage preference information might gain an advantage in more complex, multi-class scenarios.
  • Noise Resilience: The Borda Count method showed a surprising resilience to noise in the data, performing better than other methods on noisy datasets. This hints that methods that consider the full preference order might be more robust to imperfect data.
  • Voting Theory's Relevance: The paper strongly suggests that the rich theory of voting, developed over centuries, has direct and valuable applications in machine learning, particularly in ensemble methods and model reconciliation.

Key Results

Table 4 summarizes the performance of the voting methods across the 39 datasets. The "wins" and "losses" refer to the number of times a voting method achieved the lowest or highest generalization error, respectively.

  • Borda Count had the best performance with 19 wins and a win/loss ratio of 1.900.
  • Condorcet's Pairwise Comparison was second with 14 wins and a ratio of 1.400.
  • Anti-Plurality followed with 17 wins but a lower ratio of 1.063.
  • Plurality performed poorly, with only 10 wins and a ratio of 0.769.
  • Plurality with Elimination had the worst performance, with 9 wins and a ratio of 0.563.

Limitations and Future Work

The authors acknowledge that their findings are preliminary and that it's premature to make definitive judgments about specific voting methods. They suggest several avenues for future work:

  • Broader Success Criteria: Extending the evaluation to include implementation performance and scalability of voting methods.
  • Domain and Data Characteristics: Investigating how different types of domains and varying degrees of noise in datasets affect voting method performance.
  • Noise Resilience Hypothesis: Further exploring the hypothesis that methods incorporating preference information (like Borda Count) might be more resilient to noise.
  • Stacking Voting Methods: Considering if combining multiple voting methods could yield even better results.
  • Classification Theory Integration: Encouraging further integration of voting theory concepts into classification theory.

Summary updated

BibTeX
@inproceedings{leung2003empirical,
  author = {Kelvin T. Leung and Douglas Stott Parker Jr.},
  title = {{Empirical comparisons of various voting methods in bagging}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2003},
  doi = {10.1145/956750.956825},
}
Figure