An Online Boosting Algorithm with Theoretical Justifications

Shang-Tse Chen, Hsuan-Tien Lin, Chi-Jen Lu

TL;DR

This paper bridges the gap between the theoretical rigor of batch boosting and the practical needs of online learning. The authors introduce a novel online boosting algorithm (OSBoost) that utilizes a "smoothness" assumption for weak learners and employs Online Convex Programming to dynamically determine voting weights, achieving strong theoretical error guarantees and superior performance on real-world datasets.

The Challenge of Online Boosting

Boosting is a powerhouse in machine learning, famously exemplified by AdaBoost, which combines many "weak" learners (slightly better than random guessing) into one "strong" learner. While this is well-understood for batch learning (where you have all data upfront), it’s much harder for online learning (where data arrives in a continuous stream).

The core challenge is that in an online setting, you cannot see the entire dataset to calculate the optimal importance weights for each example. Previous attempts at online boosting often tried to mimic AdaBoost's heuristics but lacked solid theoretical foundations. Specifically, the standard "weak learning assumption"—that a learner can beat random guessing on any distribution—is often unrealistic in a streaming environment where early examples might receive disproportionately high weights.

A New Framework: OSBoost

To address these challenges, the authors propose a new framework based on three key pillars:

  1. The Smoothness Assumption: Instead of requiring weak learners to perform well on any distribution, they assume the learner only needs to succeed on "smooth" distributions—those where no single example carries too much weight. This makes the assumption more realistic for online streams.
  2. Conservative Weighting: They adapt the weighting scheme from an offline algorithm called SmoothBoost. Examples that are predicted incorrectly by the current ensemble of weak learners gain weight, but this weight is capped to maintain the "smoothness" required for the weak learners to function effectively.
  3. Dynamic Voting Weights (OCP & EXP): To combine the weak learners, the authors don't just use a simple average. They propose two variants to dynamically adjust weights:
  4. OSBoost.OCP: Uses Online Convex Programming to iteratively update the voting weight of each weak learner based on its performance.
  5. OSBoost.EXP: Uses the Predicting with Expert Advice framework (specifically the Weighted Majority algorithm) to treat each sub-ensemble as an "expert" and learn which ones to trust.

Experimental Setup

The algorithm was evaluated on 12 binary classification benchmark datasets sourced from the LIBSVM repository (originally from the UCI machine learning repository). These include:

  • Small-scale: Heart, Breast-Cancer, Australian, Diabetes, German.
  • Medium-scale: Splice, Mushrooms.
  • Large-scale: Adult, Ijcnn1, WebPage, Cod-RNA, Covertype.

Key Insights and Results

By forcing the algorithm to ignore "extreme" distributions, the authors ensure that the online weak learners aren't overwhelmed by outliers or noisy early samples. Furthermore, the authors prove that their algorithm achieves an error rate of $O(\delta)$, where $\delta$ is a user-defined parameter. This provides a mathematical guarantee that the online strong learner will eventually converge to a low error rate, provided the weak learners meet the smoothness assumption.

In batch boosting, you can stop adding learners when the error is low enough. In online boosting, you usually have to fix the number of learners ($N$) in advance. By using OCP or EXP to weight these learners, the algorithm can effectively "ignore" redundant or poor-performing learners by giving them near-zero voting weights.

Error rates comparing Perceptron, OzaBoost, OGBoost, and OSBoost.

Empirically, OSBoost consistently improved the performance of single weak learners (Perceptron and Naive Bayes) across all 12 datasets. Notably, OSBoost outperformed existing popular methods like OzaBoost (Online AdaBoost) and Online GradientBoost (OGBoost) in 8 out of 12 datasets when using a Perceptron weak learner.

Error rates of OSBoost variants (Base, OCP, EXP) using Perceptron.

The performance gains were particularly evident on larger datasets (e.g., Adult, WebPage, Cod-RNA), where the theoretical advantages of the OCP weighting scheme had enough time to manifest. Despite the added complexity of OCP, the algorithm remains computationally efficient, running in $O(N)$ or $O(N \log N)$ time per example, making it suitable for high-speed data streams.

Limitations and Future Work

  • Parameter Sensitivity: While the authors note that the algorithm is relatively stable, the parameters $\gamma$ (the advantage of the weak learner) and $\theta$ (an internal threshold) still need to be estimated or tuned.
  • Binary Focus: The current work is strictly focused on binary classification. Extending this framework to multi-class or multi-label classification is a primary direction for future research.
  • Fixed N: Although OCP helps manage redundant learners, the user still needs to provide an upper bound for the total number of weak learners ($N$) to instantiate. Finding a way to dynamically grow or shrink the ensemble size online remains an open challenge.

Summary updated

Abstract

We study the task of online boosting -- combining online weak learners into an online strong learner. While batch boosting has a sound theoretical foundation, online boosting deserves more study from the theoretical perspective. In this paper, we carefully compare the differences between online and batch boosting, and propose a novel and reasonable assumption for the online weak learner. Based on the assumption, we design an online boosting algorithm with a strong theoretical guarantee by adapting from the offline SmoothBoost algorithm that matches the assumption closely. We further tackle the task of deciding the number of weak learners using established theoretical results for online convex programming and predicting with expert advice. Experiments on real-world data sets demonstrate that the proposed algorithm compares favorably with existing online boosting algorithms.
BibTeX
@inproceedings{chen2012online,
  author = {Shang-Tse Chen and Hsuan-Tien Lin and Chi-Jen Lu},
  title = {{An Online Boosting Algorithm with Theoretical Justifications}},
  booktitle = {International Conference on Machine Learning},
  year = {2012},
  url = {https://openreview.net/forum?id=Syb26i-ObS},
}
Figure