Progressive Boosting for Class Imbalance

Roghayeh Soleymani, Eric Granger, Giorgio Fumera

Abstract

Pattern recognition applications often suffer from skewed data distributions between classes, which may vary during operations w.r.t. the design data. Two-class classification systems designed using skewed data tend to recognize the majority class better than the minority class of interest. Several data-level techniques have been proposed to alleviate this issue by up-sampling minority samples or under-sampling majority samples. However, some informative samples may be neglected by random under-sampling and adding synthetic positive samples through up-sampling adds to training complexity. In this paper, a new ensemble learning algorithm called Progressive Boosting (PBoost) is proposed that progressively inserts uncorrelated groups of samples into a Boosting procedure to avoid loss of information while generating a diverse pool of classifiers. Base classifiers in this ensemble are generated from one iteration to the next, using subsets from a validation set that grows gradually in size and imbalance. Consequently, PBoost is more robust to unknown and variable levels of skew in operational data, and has lower computation complexity than Boosting ensembles in literature. In PBoost, a new loss factor is proposed to avoid bias of performance towards the negative class. Using this loss factor, the weight update of samples and classifier contribution in final predictions are set based on the ability to recognize both classes. Using the proposed loss factor instead of standard accuracy can avoid biasing performance in any Boosting ensemble. The proposed approach was validated and compared using synthetic data, videos from the FIA dataset that emulates face re-identification applications, and KEEL collection of datasets. Results show that PBoost can outperform state of the art techniques in terms of both accuracy and complexity over different levels of imbalance and overlap between classes.

Introduction

In the world of machine learning, class imbalance is a persistent challenge. Whether detecting credit card fraud, diagnosing a rare disease, or identifying a specific face in a crowded environment, the "interesting" events (the minority class) are typically vastly outnumbered by the "boring" ones (the majority class). Standard algorithms often take the easy way out: they maximize overall accuracy by simply ignoring the minority class, leading to models that are ineffective for real-world applications where the minority class is of primary interest.

Class Imbalance Challenges

Most classification systems are designed to maximize standard accuracy. In imbalanced scenarios, a model can achieve 99% accuracy just by predicting the majority class every time—a result that is useless for catching the critical 1% of positive cases.

Existing solutions generally fall into two categories: data-level methods and algorithm-level methods. Data-level methods involve "up-sampling" the minority class (creating synthetic data, which is slow) or "under-sampling" the majority class (throwing away data, which loses information). Algorithm-level methods modify the learning process, often by assigning higher "costs" to missing a positive sample. However, finding the right cost values usually requires tedious trial-and-error.

Taxonomy of Boosting ensembles for class imbalance.

Furthermore, most existing methods assume the level of imbalance is fixed. In real-world applications like video surveillance, the "skew" between classes can change constantly, making static models brittle.

The Progressive Boosting (PBoost) Framework

The proposed Progressive Boosting (PBoost) algorithm evolves the training process over multiple iterations to address these limitations. Its core innovations include:

  • Progressive Partitioning: Instead of random under-sampling, PBoost divides the majority class into disjoint partitions. In each boosting iteration, a new partition is added to a "temporary design subset." This ensures the model eventually "sees" all majority data without being overwhelmed at any single step.
  • Growing Validation Set: Base classifiers are validated on this growing subset. This forces the ensemble to learn against increasing levels of imbalance, making it robust to the variable skew found in operational data.
  • $F_\beta$-Measure Loss Factor: The researchers replaced the standard accuracy-based loss factor with one based on the $F_\beta$-measure. This "cost-free" modification guides the algorithm to prioritize the minority class without needing manually tuned cost factors.
  • Intelligent Sample Selection: The algorithm ensures that "important" samples (those misclassified in previous rounds) and fresh samples from the new partition have an equally high chance of being used for training the next classifier.

Experimental Evaluation

The authors validated PBoost across three distinct types of data: synthetic 2D data for controlled environment testing, the Faces In Action (FIA) video database for face re-identification scenarios, and the KEEL collection of 21 diverse real-world imbalanced datasets.

Key Results

  • Better Accuracy: PBoost consistently outperformed state-of-the-art techniques like RUSBoost and SMOTEBoost. On the KEEL datasets, PBoost variants were frequently among the top two performing classifiers.
  • Reduced Complexity: The algorithm showed a significant reduction in computational cost during the design phase. Because PBoost validates on smaller, progressive subsets rather than the full dataset every time, it is computationally much leaner than standard Boosting or SMOTE-based approaches.
  • Handling Skew: PBoost remained stable and accurate even as the imbalance ratio reached 1:100, whereas baseline methods often saw a sharp decline in precision.

Conclusion

PBoost offers a smarter way to handle class imbalance by progressively incorporating data and utilizing a balanced loss factor. While its performance is somewhat sensitive to the partitioning technique used, it provides a significant advancement in both accuracy and efficiency. Future research directions include extending PBoost to multi-class problems and exploring more sophisticated clustering methods to define the initial partitions.

Summary updated

Abstract

Pattern recognition applications often suffer from skewed data distributions between classes, which may vary during operations w.r.t. the design data. Two-class classification systems designed using skewed data tend to recognize the majority class better than the minority class of interest. Several data-level techniques have been proposed to alleviate this issue by up-sampling minority samples or under-sampling majority samples. However, some informative samples may be neglected by random under-sampling and adding synthetic positive samples through up-sampling adds to training complexity. In this paper, a new ensemble learning algorithm called Progressive Boosting (PBoost) is proposed that progressively inserts uncorrelated groups of samples into a Boosting procedure to avoid loss of information while generating a diverse pool of classifiers. Base classifiers in this ensemble are generated from one iteration to the next, using subsets from a validation set that grows gradually in size and imbalance. Consequently, PBoost is more robust to unknown and variable levels of skew in operational data, and has lower computation complexity than Boosting ensembles in literature. In PBoost, a new loss factor is proposed to avoid bias of performance towards the negative class. Using this loss factor, the weight update of samples and classifier contribution in final predictions are set based on the ability to recognize both classes. Using the proposed loss factor instead of standard accuracy can avoid biasing performance in any Boosting ensemble. The proposed approach was validated and compared using synthetic data, videos from the FIA dataset that emulates face re-identification applications, and KEEL collection of datasets. Results show that PBoost can outperform state of the art techniques in terms of both accuracy and complexity over different levels of imbalance and overlap between classes.
BibTeX
@article{soleymani2018progressive,
  author = {Roghayeh Soleymani and Eric Granger and Giorgio Fumera},
  title = {{Progressive Boosting for Class Imbalance}},
  journal = {Expert Systems with Applications},
  year = {2018},
  doi = {10.1016/j.eswa.2018.01.023},
}
Figure