Source-linked AI summary
Online Ensemble Learning for Imbalanced Data Streams
Boyu Wang, Joelle Pineau
TL;DR
The paper tackles the limited integration of cost-sensitive learning with online learning for imbalanced data streams. It develops online cost-sensitive bagging and boosting by extending batch ensemble methods, and reports theoretical and experimental consistency with their batch counterparts, with bagging performing better overall than boosting. The framework has a scope boundary for online SMOTE and uses a straightforward, demonstrative treatment of non-stationarity.
Problem
Imbalanced online streams contain rare, costly-to-miss positive examples, while existing cost-sensitive and online-learning research has addressed these issues together only to a limited extent.
Method
The paper fuses online ensemble learning with batch cost-sensitive bagging and boosting to derive online extensions of six cost-sensitive ensemble algorithms.
Results
Overall, bagging-based algorithms achieve better performance and consistency than boosting-based algorithms, while AdaC2 and CSB2 achieve comparable performance.
Takeaways & Limitations
The framework bridges cost-sensitive and online learning, provides convergence guarantees under certain conditions, and can convert cost-insensitive online learners into cost-sensitive ones.
Takeaways & Limitations
Online SMOTE cannot match batch SMOTE’s synthetic-example distribution unless many minority examples are available from the beginning, although experiments show reasonably good consistency.
Abstract
from arXiv · showhide
While both cost-sensitive learning and online learning have been studied extensively, the effort in simultaneously dealing with these two issues is limited. Aiming at this challenge task, a novel learning framework is proposed in this paper. The key idea is based on the fusion of online ensemble algorithms and the state of the art batch mode cost-sensitive bagging/boosting algorithms. Within this framework, two separately developed research areas are bridged together, and a batch of theoretically sound online cost-sensitive bagging and online cost-sensitive boosting algorithms are first proposed. Unlike other online cost-sensitive learning algorithms lacking theoretical analysis of asymptotic properties, the convergence of the proposed algorithms is guaranteed under certain conditions, and the experimental evidence with benchmark data sets also validates the effectiveness and efficiency of the proposed methods.
1 INTRODUCTION
The paper addresses the limited research on simultaneously handling class imbalance and online learning, where minority examples may be rare, costly to miss, and too numerous for batch training. It proposes an online cost-sensitive ensemble framework combining online ensembles with batch cost-sensitive bagging and boosting.
- Motivation: Imbalanced classification can favor majority-class predictions because conventional learners minimize overall error while treating misclassification costs equally.This is especially problematic when minority examples, such as intrusions or seizures, are more important or costly to miss.
- Motivation: Data streams intensify imbalance challenges because rare positive examples arrive incrementally and systems must respond in real time.Online adaptation also helps when data are too large for memory or batch training and when distributions change across time or subjects.
- Research gap: Class-imbalance methods and online-learning methods have been studied extensively but rarely addressed together.The paper frames this gap as the motivation for an online learning with class imbalance framework.
- Contributions: The framework generalizes cost-sensitive bagging and boosting algorithms to online versions and analyzes their convergence to batch counterparts under certain conditions.It also supports converting cost-insensitive online learners into cost-sensitive ones and can be modified for concept drift.
2 RELATED WORK
Related work separates cost-sensitive imbalance handling into algorithm-level modifications and data-level rebalancing, while online learning extends classifiers to process streams incrementally. These lines of work provide the ingredients for combining imbalance handling with stream learning.
- Imbalance learning: Algorithm-level approaches incorporate misclassification costs into model design so classifiers minimize cost rather than classification error.Examples include modified kernels, penalties, loss functions, probability calibration, and pruning methods.
- Imbalance learning: Data-level approaches rebalance classes by undersampling the majority class, oversampling the minority class, or generating synthetic minority examples.These methods alter the training data before classification.
- Online learning: Incremental and online learning has been developed for both basic classifiers and more sophisticated models such as decision trees, random forests, LDA, and logistic regression.The cited literature establishes a broad stream-learning foundation for the paper’s framework.
3 TECHNICAL BACKGROUND
The technical background reviews ensemble learning, online bagging and boosting, and cost-sensitive resampling strategies. It motivates the proposed framework by showing how sampling, reweighting, and Poisson approximation connect batch and online ensembles.
- Standard ensembles: Ensemble learning combines multiple base learners trained on different data to improve generalization through diversity and bias-variance reduction.Bagging and boosting are presented as representative ensemble techniques.
- Bagging: Bagging creates bootstrap replicas of the training set, trains one base learner per replica, and introduces diversity through independent resampling.The algorithm samples N examples with replacement for each of M learners.
- Boosting: Boosting sequentially emphasizes examples misclassified by the current learner and reduces the emphasis on correctly classified examples.Its update rule avoids normalization, which is important when normalization factors are unavailable online.
- Online ensembles: Online bagging and boosting approximate batch resampling using Poisson draws, with λ determined by sampling probabilities or tracked boosting weights.Online bagging uses Poisson(1), while online boosting updates λ from correct and incorrect classifications.
- Cost-sensitive ensembles: Cost-sensitive ensemble learning applies biased resampling or reweighting before bagging or boosting to incorporate different misclassification costs.The reviewed methods include UnderOverBagging, SMOTEBagging, AdaC2, CSB2, RUSBoost, and SMOTEBoost.
- Cost-sensitive bagging: UnderOverBagging gradually switches from majority undersampling to minority oversampling, while SMOTEBagging combines negative-class resampling with resampled or synthetic positive examples.SMOTE generates additional minority examples by interpolation, and varying the resampling rate increases ensemble diversity.
- Cost-sensitive boosting: RUSBoost and SMOTEBoost rebalance training data before presenting it to base learners while measuring base-learner error on the original data.Their implementations differ in how class ratios and synthetic examples are generated.
4 METHODS
The framework extends online ensemble learning with cost-sensitive resampling and boosting updates, using Poisson parameters to represent class-specific sampling and avoiding normalization during online updates. It derives online versions of several bagging and boosting methods, while noting that online SMOTE cannot exactly reproduce batch SMOTE.
- Framework: Online cost-sensitive ensembles combine batch resampling mechanisms with class-specific Poisson parameters in online learning.Cost sensitivity is introduced through resampling in batch methods and through Poisson-parameter manipulation in online ensembles.
- Online cost-sensitive bagging: Online UnderOverBagging presents minority examples with Poisson mean aC and majority examples with mean a, implementing cost-sensitive sampling online.The algorithm trains each base learner according to class-dependent Poisson draws.
- Online cost-sensitive bagging: Online SMOTEBagging uses separate Poisson draws for original and synthetic minority examples, generating synthetic instances from stored positive examples and nearest neighbors.The method applies online SMOTE after sampling and trains on both original and synthetic examples.
- Scope and limitation: Online SMOTE cannot converge to batch SMOTE because early online streams contain too few positive examples, although experiments show reasonably good consistency.The resulting synthetic-example distributions can differ substantially at the beginning of learning.
- Online cost-sensitive boosting: Online cost-sensitive boosting reformulates batch weight updates without normalization, then estimates the quantities needed to set Poisson parameters incrementally.This reformulation is required because normalization factors are unavailable during online learning.
- Online cost-sensitive boosting: Online AdaC2 tracks weighted and unweighted contributions from true-positive, true-negative, false-positive, and false-negative examples to update each learner’s Poisson parameter.The implementation uses four category-specific parameters to calculate weighted accuracy and error.
5 THEORETICAL ANALYSIS
The theoretical analysis establishes asymptotic consistency for several online cost-sensitive ensembles under conditions analogous to cost-insensitive online methods. Under stated conditions, online UnderOverBagging, AdaC2, CSB2, and RUSBoost converge to their batch counterparts, whereas online SMOTE methods cannot achieve this exact convergence.
- Convergence limits: Online SMOTEBagging and SMOTEBoost cannot theoretically converge to their batch counterparts because online SMOTE cannot converge to batch SMOTE.The analysis distinguishes these methods from UnderOverBagging, AdaC2, CSB2, and RUSBoost.
- Convergence results: Online UnderOverBagging converges to its batch counterpart as positive and negative sample counts and the ensemble size approach infinity, assuming proportional base learners that converge in probability.The convergence result is stated under the conditions of Theorem 1.
- Convergence results: Online AdaC2 and CSB2 converge to their batch counterparts when positive and negative sample counts approach infinity and the base learners are naive Bayes classifiers.This is the condition stated in Theorem 2.
- Convergence results: Online RUSBoost converges to its batch counterpart as positive and negative sample counts approach infinity when the base learners are naive Bayes classifiers.This is the condition stated in Theorem 3.
- Proof strategy: The proofs generalize prior asymptotic analyses of cost-insensitive online bagging and boosting to different cost settings.The paper states that proof details are provided in supplementary materials.
6 EXPERIMENTS
The experiments compare online cost-sensitive ensemble algorithms with batch counterparts on benchmark data, measuring AUC and consistency across base learners. Results show stronger performance and convergence for online bagging methods, while base-learner choice has little evident effect.
- Experimental Setup: AUC was measured using five-fold cross-validation to compare proposed online algorithms with batch counterparts.The experiments focus primarily on online algorithm performance because batch ensemble comparisons were previously studied.
- Experimental Setup: LDA, QDA, and Gaussian naive Bayes served as base learners, with incremental and lossless parameter estimation isolating ensemble effects.All algorithms used ten base learners.
- Experimental Setup: Eighteen UCI data sets with different class ratios were used, converting multiclass data into binary problems for comparison.The data-set summaries include examples, features, positive and negative percentages, and class ratio.
- Overall Performance: Online algorithms formed three AUC groups: above 0.87, between 0.84 and 0.87, and oRUS1 at 0.81.The highest group included oUOB, oSB, oAC2, and oCSB2; the middle group included oRUS2, oRUS3, oSBO1, oSBO2, and oSBO3.
- Consistency with Batch Methods: oUOB and oSB were closest to their batch counterparts, with batch and online bagging ROC curves almost overlapping across data sets and base learners.This consistency was assessed using absolute AUC differences and ROC comparisons.
- Base Learners and Convergence: LDA and QDA had slightly higher average AUC than NB, while NB showed slightly better consistency and base-learner choice lacked strong effects on performance or consistency.oUOB and oSB converged more consistently, whereas oRUS1 performed worse across base learners.
- Convergence Speed: oUOB converged to bUOB with very little training data, while online boosting approached batch performance especially beyond 70% of training examples.The convergence experiment varied the training portion of satimage from 5% to 90% and repeated each algorithm five times.
7 DISCUSSION OF THE RESULTS
The discussion attributes algorithm performance primarily to consistency with batch counterparts and the quality of the underlying batch ensembles. Bagging methods generally outperform boosting methods, while AdaC2 and CSB2 are comparable.
- AdaC2 converges faster and better than RUSBoost1 on satimage with QDA base learners, explaining its higher consistency in this setting.The comparison uses werr and wacc for AdaC2 and error for RUSBoost1 during training.
- Online ensemble performance is largely determined by consistency with batch counterparts and the performance of the corresponding batch ensembles.
- Bagging algorithms outperform boosting algorithms in both performance and consistency.
- AdaC2 and CSB2 achieve comparable performance.
- RUSBoost and SMOTEBoost perform worse because their weight-update approximations are less reliable and they more often violate boosting requirements.
8 LEARNING IN NON-STATIONARY ENVIRON-
The framework is extended to non-stationary imbalanced streams by combining it with concept-drift techniques at the data, ensemble, and base-learner levels. A simple forgetting-factor modification of online AdaC2 gives encouraging preliminary results across abrupt, gradual, and mixed drift scenarios.
- Non-stationary imbalanced streams are difficult because successive minority examples may be widely separated and drawn from different distributions.
- The framework can incorporate concept-drift methods at the data, ensemble, and base-learner levels.These methods select or reuse instances, replace poorly performing base learners, or adapt the online base learners themselves.
- The illustrative non-stationary extension gives recent examples greater weight than past examples through forgetting factors.
- The extension updates weighted Poisson parameters using the forgetting factor β in the online AdaC2 procedure.The update is applied to λ_TP, λ_TN, λ_FP, and λ_FN.
- Across artificial streams with abrupt, gradual, and mixed drift, the modified online AdaC2 improves overall performance, especially on SINE1.The experiments report average online AUC over ten repetitions, with β = 0.9 for non-stationary variants.
9 CONCLUSIONS
The paper proposes an online cost-sensitive ensemble framework that generalizes batch cost-sensitive ensembles and theoretically and experimentally matches their behavior. Bagging performs best overall, while the framework also extends naturally to non-stationary streams with encouraging preliminary results.
- The framework generalizes UnderOverBagging, SMOTEBagging, AdaC2, CSB2, RUSBoost, and SMOTEBoost to online cost-sensitive learning.
- The proposed online algorithms perform comparably with their batch counterparts in theoretical and experimental analyses.
- Bagging algorithms outperform boosting algorithms in both consistency and AUC, while AdaC2 and CSB2 achieve comparable performance.
- The framework combines naturally with concept-drift algorithms and accommodates abrupt, gradual, and mixed drift scenarios after simple extensions.