Introduction
Multilabel classification involves assigning a subset of labels to an instance, such as categorizing a news article into multiple topics like "Sports" and "Finance." Traditional approaches typically rely on ranking labels by relevance or decomposing the problem into independent binary classification tasks (e.g., AdaBoost.MH). However, these methods often fail to account for label correlations or specific user-defined error costs. This paper introduces AdaBoost.LC, a flexible boosting framework that utilizes a "label covering" mechanism to optimize for complex, interdependent error metrics.
The Label Covering Mechanism
The core innovation of AdaBoost.LC is the concept of a "cover"—a collection of label subsets defined by the user. Instead of penalizing every label mistake equally, the algorithm counts an error if any label within a specific subset (cover-element) is mispredicted. This allows for highly customizable loss functions. For instance, if every label is its own subset, the algorithm reduces to standard Hamming loss optimization. If all labels are grouped into one subset, it optimizes for zero-one error.
The algorithm iteratively assigns weights to training examples based on their contribution to a global covering loss. It then selects weak hypotheses to minimize a smooth, convex upper bound of this error, ensuring a reduction in training loss at each iteration.
Experimental Evaluation
The researchers evaluated AdaBoost.LC using the Reuters Corpus Volume 1 (RCV1) dataset, comprising approximately 800,000 news articles across 103 labels. Five distinct covering strategies were tested:
- Zero-One (ZO): All-or-nothing error.
- Hamming-Distance (HM): Independent label errors (equivalent to AdaBoost.MH).
- Two-Sets (TS): Labels split into two broad groups.
- Weighted-Positive (WP): Higher penalty for missing positive labels.
- Weighted-Negative (WN): Higher penalty for false positives.
Results and Discussion
The experiments confirmed a "diagonal effect": models trained to minimize a specific covering error consistently outperformed models trained on different coverings when evaluated on that same metric.
As shown in the results table, the model trained on the WN metric achieved a test loss of 2.314, significantly lower than the results achieved by models trained on other coverings (such as the 2.407 achieved by the ZO-trained model). Furthermore, the "Weighted-Positive" (WP) covering outperformed standard Hamming distance on Information Retrieval (IR) metrics like Average Precision and Coverage, suggesting that the standard independent-label assumption is often sub-optimal for real-world tasks.
Conclusion
AdaBoost.LC provides a robust framework for tailoring multilabel classification to specific application needs through customizable loss functions. While the algorithm excels at optimizing covering-based losses, future work will focus on improving scalability for large label covers and developing better proxies for non-linear IR metrics.
Summary updated