Abstract
A system of nested dichotomies is a method of decomposing a multi-class problem into a collection of binary problems. Such a system recursively splits the set of classes into two subsets, and trains a binary classifier to distinguish between each subset. Even though ensembles of nested dichotomies with random structure have been shown to perform well in practice, using a more sophisticated class subset selection method can be used to improve classification accuracy. We investigate an approach to this problem called random-pair selection, and evaluate its effectiveness compared to other published methods of subset selection. We show that our method outperforms other methods in many cases when forming ensembles of nested dichotomies, and is at least on par in all other cases.
Introduction
Many machine learning algorithms are natively binary, designed to distinguish between only two classes. To apply these algorithms to multi-class problems, researchers typically use binarization techniques such as one-vs-all or pairwise classification. Nested dichotomies represent a more sophisticated hierarchical approach. They recursively partition the set of classes into two subsets, forming a binary tree where each internal node represents a binary classifier trained to distinguish between its two child subsets.
The primary challenge in this approach is determining the optimal tree structure. For a problem with $k$ classes, the number of possible nested dichotomy structures grows exponentially. While random structures have proven effective in ensemble settings, they often create "difficult" binary problems by grouping highly dissimilar classes together. Conversely, deterministic methods like clustering class centroids often lack the diversity required for ensemble techniques like bagging or boosting to succeed.
Random-Pair Selection (RPND)
To address these limitations, we propose Random-Pair Selection (RPND). This adaptive method builds the hierarchy by leveraging the base classifier's own logic to group similar classes. The algorithm proceeds as follows at each node:
- Seed Selection: Two classes ($c_1$ and $c_2$) are selected at random from the current set of classes.
- Probe Training: A binary "probe" classifier is trained using only the data from these two seed classes.
- Similarity Grouping: All other classes at the node are passed through this probe. If the majority of instances in a class $c_n$ are classified as $c_1$, it is added to the $c_1$ subset; otherwise, it is added to the $c_2$ subset.
- Node Training: The final binary classifier for the node is trained using these two meta-subsets.
- Recursion: The process repeats for the child nodes until each leaf contains a single class.
This approach ensures that the hierarchy is tailored to what the specific base learner (e.g., Logistic Regression or C4.5) finds easy or hard to distinguish. By starting with a random pair, the method introduces sufficient stochasticity to maintain ensemble diversity while ensuring that the resulting binary problems are more intuitive than purely random splits.
Experimental Evaluation
We evaluated RPND using 18 datasets from the UCI Repository, focusing on those with at least five classes. Additionally, a case study was conducted on the CIFAR-10 dataset using Convolutional Neural Networks (CNNs). CIFAR-10, consisting of 60,000 images of animals and vehicles, highlights a weakness of centroid-based methods: in high-dimensional image space, class centroids are often uninformative "blurry blobs." RPND, by contrast, creates more meaningful hierarchies, such as naturally separating vehicles from animals.
Key Results
Our experiments yielded several key insights:
- Accuracy Improvements: In single-tree configurations, RPND significantly outperformed random structures, particularly when using Logistic Regression as the base learner.
- Ensemble Superiority: When integrated into Bagging and MultiBoost ensembles, RPND consistently matched or exceeded the performance of both random selection and centroid-based clustering.
- Robustness: The method proved effective across a range of base learners, from high-bias models like Logistic Regression to high-variance models like C4.5.
- Diversity: Unlike centroid-based methods which are often too stable, RPND provides the "diversity sweet spot" necessary for ensemble methods to thrive.
Conclusion
Random-Pair Selection offers a robust and adaptive way to build ensembles of nested dichotomies. By using the classifier itself to define the hierarchy, it creates simpler binary sub-problems without sacrificing the diversity needed for boosting and bagging. While it incurs a higher training cost due to the construction of probe classifiers, the gains in classification accuracy make it a compelling choice for complex multi-class problems. Future work will explore "best-of-N" selection strategies to further refine the initial class splits.
Summary updated