AdaBoost.C2: Boosting Classifiers Chains for Multi-Label Classification

Jiaxuan Li, Xiaoyan Zhu, Jiayin WangAAAI 2023 · OpenReview

Multi-Label Classification (MLC) is a fundamental task in machine learning where an instance can be associated with multiple labels simultaneously. For example, a news article might be tagged with "Politics," "Economics," and "Europe" all at once. Effectively handling MLC requires addressing two primary challenges: capturing label correlations and mitigating error propagation.

At AAAI-23, researchers from Xi’an Jiaotong University introduced AdaBoost.C2, a framework that integrates AdaBoost and Classifier Chains (CC) to solve these long-standing issues through a multi-path boosting approach and dynamic chain ordering.

The Limitations of Traditional MLC

Existing MLC methods generally fall into two categories, each with inherent drawbacks:

  1. Binary Relevance (BR): Treats each label as an independent problem, failing to capture dependencies (e.g., the correlation between "Rainy" and "Umbrella").
  2. Classifier Chains (CC): Captures correlations by sequencing classifiers where each prediction depends on previous ones. However, it suffers from error propagation, where an early mistake in the chain cascades through subsequent predictions.

Furthermore, standard boosting methods like AdaBoost.MH treat the entire label set as a single block. This is inefficient because labels vary in difficulty; forcing the model to iterate on "easy" labels to fix "hard" ones leads to computational waste and potential overfitting.

The AdaBoost.C2 Framework

AdaBoost.C2 addresses these inefficiencies through a two-pronged strategy: a multi-path boosting framework and heuristic classifier chains.

1. Multi-Path AdaBoost Framework

Instead of a monolithic boosting process, AdaBoost.C2 employs $Q$ separate boosting paths, one for each label. This allows for asynchronous learning, where each label maintains its own data distribution and weights.

Comparison between traditional monolithic boosting and the proposed multi-path AdaBoost.C2 with early stopping.

A critical feature of this framework is asynchronous early stopping. If a specific label reaches a target accuracy, its boosting path terminates early (represented by the grey circles in the figure above). This ensures that computational resources are focused only on the labels that still require optimization.

2. Heuristic Classifier Chains with Dynamic Ordering

To capture dependencies without the risk of error propagation, AdaBoost.C2 uses a Classifier Chain as the base learner in each iteration. The "secret sauce" is dynamic ordering: in every round, the algorithm evaluates error rates from the previous iteration and places the "easiest" labels (those with the lowest error) at the beginning of the chain.

Illustration of how classifier structures and label dependencies evolve across different iterations (C1 to C4).

By prioritizing high-confidence predictions, the information passed down the chain is more likely to be accurate, effectively neutralizing the error propagation problem. As shown in the figure above, the dependency structure ($C_t$) adapts over time to optimize the learning process for the remaining active labels.

Experimental Evaluation

The researchers evaluated AdaBoost.C2 across 26 benchmark datasets from diverse domains, including text (Reuters), biology (Yeast), multimedia (Corel5k), and medicine (CHD_49). These datasets ranged from a few hundred to over 10,000 instances and up to 374 labels.

Key Results

AdaBoost.C2 was compared against four state-of-the-art MLC ensemble methods (DECC, ACkEL, MLWSE, and BOOMER). The results demonstrated significant advantages:

  • Superior Accuracy: Across 104 experimental cases, AdaBoost.C2 ranked first in 65 cases.
  • Metric Gains: Compared to the next-best algorithm (MLWSE), it achieved average improvements of 2.63% in Hamming Loss and 12.56% in Ranking Loss.
  • Efficiency: Due to asynchronous early stopping, AdaBoost.C2 converged much faster than traditional methods. On many large-scale datasets, most labels reached convergence in just 1–3 rounds, whereas traditional methods required 10 or more.

Conclusion

AdaBoost.C2 represents a significant step forward in multi-label classification by recognizing that labels are not equal. By decoupling the boosting process and dynamically ordering classifier chains, the framework achieves higher accuracy with lower computational overhead. Future research may explore parallelization for chain construction and applying this multi-path logic to other boosting variants like Gradient Boosting Decision Trees (GBDT).

Summary updated

Abstract

During the last decades, multi-label classification (MLC) has attracted the attention of more and more researchers due to its wide real-world applications. Many boosting methods for MLC have been proposed and achieved great successes. However, these methods only extend existing boosting frameworks to MLC and take loss functions in multi-label version to guide the iteration. These loss functions generally give a comprehensive evaluation on the label set entirety, and thus the characteristics of different labels are ignored. In this paper, we propose a multi-path AdaBoost framework specific to MLC, where each boosting path is established for distinct label and the combination of them is able to provide a maximum optimization to Hamming Loss. In each iteration, classifiers chain is taken as the base classifier to strengthen the connection between multiple AdaBoost paths and exploit the label correlation. Extensive experiments demonstrate the effectiveness of the proposed method.
BibTeX
@inproceedings{li2023adaboost,
  author = {Jiaxuan Li and Xiaoyan Zhu and Jiayin Wang},
  title = {{AdaBoost.C2: Boosting Classifiers Chains for Multi-Label Classification}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  url = {https://openreview.net/forum?id=IyGxcLi60H},
}
Figure