TL;DR
This paper introduces LexiBoost, a novel boosting algorithm that addresses class imbalance without requiring expensive cost tuning. By framing component weight assignment as a "Tug of War" in the margin space, LexiBoost uses a two-stage lexicographic linear programming approach to find a balanced compromise between rare and abundant classes, proving effective across various imbalanced datasets.
What Problem Does This Paper Address?
Class imbalance, where one or more classes have significantly fewer samples than others, is a pervasive problem in machine learning, particularly in critical applications like medical diagnosis and fraud detection. Boosting algorithms, while powerful, often struggle with this imbalance, especially in multi-class scenarios. Existing solutions typically rely on costly "cost set tuning" to determine appropriate compensation levels for minority classes. This tuning process is sensitive to dataset characteristics and can be computationally expensive, particularly for multi-class problems where multiple cost matrices or relative costs need to be estimated. The paper aims to bridge this gap by developing a boosting method that effectively handles class imbalance without this burdensome tuning step.
Methods
The core of the proposed solution, LexiBoost, is a two-stage lexicographic linear programming (LxLP) framework.
- Stage 1: Class-Specific Optimization: For each class, a separate linear program (LP) is solved. These LPs aim to minimize the hinge loss individually for each class. This step finds component weight combinations that are optimal for each class in isolation.
- Stage 2: Global Optimization (Tug of War): A final LP is solved to determine the overall component weights. This LP minimizes the maximum deviation from the class-specific minimum losses found in Stage 1. This stage effectively models the "Tug of War" between classes in the margin space, seeking a balanced compromise where improvements in one class's margin don't excessively harm the other.
The authors also introduce a dual formulation, Dual-LexiBoost, which not only selects optimal component weights but also adapts point-specific weights over boosting rounds to further counter class imbalance. The framework is designed to be applicable to both two-class and multi-class problems.
Datasets
The paper evaluates LexiBoost and its dual on a diverse set of datasets:
- Artificial Datasets: 27 two-class datasets with varying imbalance ratios (IR), sizes, and overlap levels, plus analogous datasets with outliers.
- Real-world Datasets: 15 two-class and 10 multi-class datasets from the KEEL repository.
- Hyperspectral Image Classification: Samson, Jasper ridge, Kennedy Space Center (KSC), Salinas A, and Indian Pines scenes.
- ImageNet Classification: Three imbalanced subsets (ImageNet8, ImageNet9, ImageNet12) derived from the ImageNet dataset, featuring complex class distributions.
Key Insights and Ideas
- "Tug of War" Analogy: The assignment of component weights in boosting can be viewed as a "Tug of War" in the margin space. Increasing the margin for minority class instances often comes at the expense of majority class instances, and vice versa. This insight is crucial for understanding how to achieve a balanced compromise.
- Lexicographic Programming for Balance: LxP provides a natural framework for handling multi-objective problems (maximizing performance on each class) where objectives have different priorities. By first optimizing for each class individually and then finding a compromise, LxP effectively addresses the inherent conflict in imbalanced classification.
- Eliminating Cost Tuning: The proposed method bypasses the need for expensive and often difficult cost set tuning, a major bottleneck in existing imbalanced learning approaches. This is achieved through a novel hinge loss-based regularization that implicitly handles class balance.
- Dual Formulation's Advantage: The dual formulation (Dual-LexiBoost) not only finds optimal component weights but also adapts instance weights, leading to improved performance, particularly in multi-class scenarios.
Key Results
- Superior Performance: LexiBoost and Dual-LexiBoost consistently outperformed baseline methods (AdaBoost, AdaMEC-Calib, AdaBoost.NC) and existing LP-based methods (LPUBoost, Dual-LPUBoost) across various artificial and real-world imbalanced datasets, including challenging hyperspectral and ImageNet classification tasks.
- Best Ranks: Dual-LexiBoost consistently achieved the best average ranks and often demonstrated statistically equivalent or superior performance compared to other methods, especially in multi-class settings.
- Efficiency: The proposed methods showed comparable or lower training times than their closest rivals, despite achieving better performance, indicating their computational efficiency.
- Multi-class Applicability: The framework was successfully generalized and demonstrated strong performance on multi-class imbalanced problems.
Limitations and Future Work
- Computational Complexity: While the paper claims lower complexity than some LP-based methods, the time complexity of the primal and dual LexiBoost LPs is still noted as O(n⁵) in the worst case.
- Future Work: The authors plan to extend the proposed framework to single-class classification problems.
Summary updated