A Classifier Ensemble of Binary Classifier Ensembles

Hamïd Parvïn, Hamid Alinejad‐Rokny, Sajad ParvinInternational Journal of Learning Management Systems 2013 · DOI

TL;DR

This paper introduces a novel ensemble method for multiclass classification that leverages the power of specialized binary classifiers to improve overall accuracy. By identifying and addressing "error-prone" class pairs with dedicated binary classifier ensembles, and then using Genetic Algorithms to optimally weight these ensembles and the main classifier, the authors achieve significant performance gains, particularly for complex datasets like handwritten digit recognition.

What Problem Does This Paper Address?

In multiclass classification, achieving high accuracy can be challenging, especially when dealing with datasets where certain classes are frequently confused. While improving individual classifier accuracy is a common goal, this paper explores an alternative: building a more robust ensemble by combining multiple, potentially less accurate, but specialized classifiers. The core problem is how to effectively combine these diverse classifiers to overcome the limitations of a single, monolithic classifier, particularly in error-prone regions of the feature space. The authors aim to create a system that can better handle complex decision boundaries and inter-class confusions.

Methods

The proposed method, "A Classifier Ensemble of Binary Classifier Ensembles," employs a hierarchical approach:

  1. Main Multiclass Classifier: A primary multiclass classifier (e.g., MLP or Decision Tree) is trained on the entire dataset. Its confusion matrix on a validation set is crucial for identifying problematic class pairs.
  2. Error-Prone Pair-Class (EPPC) Identification: The confusion matrix from the main classifier is analyzed to pinpoint pairs of classes that are frequently misclassified. These are termed "Error-Prone Pair-Classes" (EPPCs).
  3. Binary Classifier Ensembles for EPPCs: For each identified EPPC, a separate ensemble of binary classifiers is trained. Each binary classifier within this ensemble is specialized to distinguish between the two classes of the EPPC. These binary classifiers are trained on subsets of the data belonging to their respective EPPC.
  4. Weighted Fusion with Genetic Algorithms (GA): The outputs from the main multiclass classifier and all the EPPC binary classifier ensembles are then fed into a final fusion stage. This stage uses multiple Genetic Algorithms (one for each class) to learn optimal weights for combining these diverse classifier outputs. The GA aims to find weights that maximize the certainty of correctly classifying each digit.

The key novelty lies in the hierarchical structure: using a main classifier to guide the creation of specialized binary ensembles for difficult class pairs, and then using GAs for sophisticated, class-specific weighting of all contributing classifiers.

Datasets

The primary dataset used for evaluation is the Persian handwritten digit recognition (PHDR) dataset, specifically the Hoda dataset. This dataset is described as "very large scale" and contains 102,364 instances of digits 0-9. It was divided into training (60,000 instances), validation (20,000 instances), and test sets (22,364 instances). The paper notes that this dataset was standardized in 2006, making comparisons with prior work on this specific dataset meaningful.

Key Insights and Ideas

  • Diversity through Specialization: The paper champions the idea that diversity in an ensemble can be achieved not just by using different classifier types, but by creating specialized sub-ensembles that focus on specific, difficult classification tasks (i.e., confusing class pairs).
  • Leveraging Confusion: Instead of treating misclassifications as pure errors, the method actively uses the confusion matrix to identify and address these weaknesses by creating dedicated binary classifiers.
  • GA for Optimal Weighting: Genetic Algorithms are employed as a powerful, adaptive mechanism to find the optimal combination weights for a large number of diverse classifiers, going beyond simple averaging or fixed weighting schemes.
  • Unstable Classifiers are Beneficial: The authors observe that unstable classifiers like Decision Trees (DT) and Multi-Layer Perceptrons (MLP) are more beneficial in ensemble settings compared to stable classifiers like k-Nearest Neighbors (k-NN). This is attributed to their inherent variability, which can contribute to ensemble diversity.

Key Results

The proposed "Weighted fusion with GA" method demonstrated significant improvements in classification accuracy across different base classifiers:

  • MLP Base Classifier: Achieved an accuracy of 99.04%.
  • DT Base Classifier: Achieved an accuracy of 98.99%.
  • 3-NN Base Classifier: Achieved an accuracy of 97.14%.

These results are compared to other methods, including a simple multiclass classifier and previously proposed methods [18, 19, 20]. The proposed method consistently outperformed these benchmarks, especially when using DT and MLP as base classifiers. The authors highlight that using DT as the base classifier yielded the most significant improvement.

Limitations and Future Work

  • Computational Cost: While the paper doesn't explicitly detail computational costs, training multiple binary classifier ensembles and running multiple GAs for weighting can be computationally intensive. The paper does mention that the method reduces the complexity order from O(c^2) to O(1) for problems with a large number of classes, suggesting an efficiency gain in terms of the number of pairwise classifiers considered, but not necessarily overall training time.
  • Parameter Sensitivity: The selection of parameters like k (number of EPPCs) and m (number of binary classifiers per EPPC) is mentioned to be determined by "try and error" or set to specific values (k=11, m=9). The optimal choice of these parameters might be dataset-dependent.
  • Future Work: The paper suggests that the framework is flexible and can accommodate an arbitrary number of pairwise classifier ensembles. Future work could explore more sophisticated methods for EPPC selection and potentially investigate other optimization algorithms beyond GA for the weighting stage. The authors also imply that the method's applicability to problems with a large number of classes is a key advantage for future research.

Summary updated

Abstract

This paper proposes an innovative combinational algorithm to improve the performance in multiclass classification domains. Because the more accurate classifier the better performance of classification, the researchers in computer communities have been tended to improve the accuracies of classifiers. Although obtaining the more accurate classifier is often aimed, there is an alternative option to reach for it. Indeed one can use many inaccurate classifiers each of which is specialized for a subspace in the problem space and then s/he can consider their consensus vote as the classification. This paper proposes a new ensembles methodology that uses ensemble of binary classifiers as elements of an ensemble. These ensembles of binary classifiers jointly work using majority weighted voting. The results of these ensembles are in weighted manner combined to decide the final vote of the classification. In empirical result, these weights in final classifier are determined with using a series of genetic algorithms. We evaluate the proposed framework on a very large scale Persian digit handwritten dataset and the results show effectiveness of the algorithm.
BibTeX
@article{parvin2013classifier,
  author = {Hamïd Parvïn and Hamid Alinejad‐Rokny and Sajad Parvin},
  title = {{A Classifier Ensemble of Binary Classifier Ensembles}},
  journal = {International Journal of Learning Management Systems},
  year = {2013},
  doi = {10.12785/ijlms/010204},
}
Figure