Building Ensembles of Adaptive Nested Dichotomies with Random-Pair Selection

Tim Leathart, Bernhard Pfahringer, Eibe Frank

TL;DR

This paper introduces Random-Pair Selection, a novel method for decomposing multi-class classification problems into a hierarchy of binary ones (nested dichotomies). By using the base classifier itself to adaptively group similar classes together, the method creates more intuitive and easier-to-learn hierarchies that significantly improve accuracy when used in ensemble techniques like bagging and boosting.

What Problem Does This Paper Address?

Many machine learning algorithms are natively binary (designed for two classes). To handle multi-class problems, researchers use "binarization" techniques like one-vs-all or pairwise classification. Nested dichotomies are a more sophisticated approach that recursively splits the set of classes into two subsets, forming a binary tree where each node is a binary classifier.

The challenge lies in the "structure" of this tree. For a 10-class problem, there are over 34 million possible tree structures. While picking trees at random works surprisingly well in ensembles, it often creates "difficult" binary problems where very different classes are lumped together. Conversely, existing "intelligent" methods (like clustering class centroids) are often deterministic, which is bad for ensembles because they lack the diversity needed to improve performance through bagging or boosting.

Methods

The authors propose Random-Pair Selection (RPND). The algorithm builds the hierarchy as follows:

  1. Pick a Seed Pair: At any given node, select two classes ($c_1$ and $c_2$) at random from the available classes.
  2. Train a "Probe": Train a binary classifier using only the data from these two classes.
  3. Group by Similarity: Take all other classes at that node and pass them through this probe classifier. If the majority of instances in class $c_n$ are classified as $c_1$, add $c_n$ to the $c_1$ subset; otherwise, add it to the $c_2$ subset.
  4. Final Training: Train the actual node classifier using these two newly formed meta-subsets.
  5. Recurse: Repeat the process for the child nodes until only one class remains in each subset.

This approach is adaptive because the hierarchy is built based on what the specific base classifier (e.g., Logistic Regression or C4.5) finds easy or hard to distinguish.

Datasets

The researchers evaluated their method using:

  • 18 UCI Repository Datasets: Including well-known benchmarks like letter, optdigits, segment, vowel, and yeast. They specifically chose datasets with at least five classes.
  • CIFAR-10: A dataset of 60,000 small natural images (animals and vehicles) used for a case study involving Convolutional Neural Networks (CNNs).

Key Insights and Ideas

  • The "Classifier's Eye" View: Unlike previous methods that used geometric distance (centroids) to group classes, RPND uses the classifier's own logic. If a classifier thinks a '5' looks like a '6', RPND keeps them together in the hierarchy as long as possible, allowing the model to focus on high-level features at the root and fine-grained differences at the leaves.
  • The Diversity Sweet Spot: Centroid-based methods are often too stable; they produce the same tree every time. RPND introduces just enough randomness (via the initial pair selection) to ensure that an ensemble of trees remains diverse, which is critical for the success of Bagging and AdaBoost.
  • Centroids Can Lie: In complex data like images (CIFAR-10), the "average" image (centroid) of a class is often a blurry, meaningless gray blob. The paper shows that RPND creates much more intuitive hierarchies (e.g., separating all vehicles from all animals) than centroid-based methods.

Key Results

  • Superior Accuracy: In single-tree experiments, RPND significantly outperformed random structures in most cases when using Logistic Regression.
  • Ensemble Performance: When used in Bagging and MultiBoost ensembles, RPND consistently outperformed or matched both random selection and centroid-based clustering.
  • Robustness: The method proved effective across different base learners, from high-bias models (Logistic Regression) to high-variance models (C4.5).
  • Computational Trade-off: While RPND is slower than random selection (because it requires training "probe" classifiers during tree construction), the authors show the overhead is manageable and the scaling is predictable.

Limitations and Future Work

  • Training Time: The primary downside is the increased runtime during the training phase due to the extra binary models needed to determine class splits.
  • Sensitivity to Initial Pair: The quality of a specific tree depends on the first two classes picked at the root. If two very similar classes are picked as the initial pair, the resulting split might be less intuitive.
  • Future Directions: The authors suggest exploring a "best-of-N" approach—selecting several random pairs at each node and choosing the one that produces the most balanced or separable split—to further improve accuracy for small ensembles.

Summary updated

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 applies binary splits to divide the set of classes into two subsets, and trains a binary classifier for each split. Although 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. The software related to this paper is available at https://svn.cms.waikato.ac.nz/svn/weka/trunk/packages/internal/ensemblesOfNestedDichotomies/ .
BibTeX
@inproceedings{leathart2016building,
  author = {Tim Leathart and Bernhard Pfahringer and Eibe Frank},
  title = {{Building Ensembles of Adaptive Nested Dichotomies with Random-Pair Selection}},
  booktitle = {ECML/PKDD},
  year = {2016},
  url = {https://openreview.net/forum?id=k9GMTcJU7x},
}

Loading related content...

Figure