Abstract
Ensemble algorithms are general methods for improving the performance of a given learning algorithm. This is achieved by the combination of multiple base classifiers into an ensemble. In this paper, the idea of using an adaptive policy for training and combining the base classifiers is put forward. The effectiveness of this approach for online learning is demonstrated by experimental results.
Introduction
Ensemble methods, such as Bagging and Boosting, leverage the "wisdom of the crowd" by combining multiple base classifiers to achieve higher accuracy than any single model. Traditionally, these methods rely on fixed or heuristic-based rules, such as weighted voting, to aggregate outputs. However, these static approaches often fail to account for the fact that certain experts may be better suited for specific regions of the input space. This paper addresses the gap in online learning—where data arrives sequentially—by proposing a framework that dynamically learns a policy to select the most appropriate expert for each input.
The OLAP Framework
The authors introduce OnLine Adaptive Policy (OLAP), which frames ensemble selection as a reinforcement learning problem. The framework consists of several key components:
- The Ensemble: A set of base classifiers (experts), implemented as Multi-Layer Perceptrons (MLPs).
- Q-Value Predictors: For every expert, a corresponding MLP predictor estimates the expected future reward (Q-value) of selecting that expert for a given input $x$.
- Action Selection: The system employs an $\epsilon$-greedy policy. It typically selects the expert with the highest predicted Q-value but occasionally chooses a random expert to facilitate exploration.
- Reward Signal: To minimize error, the system uses a negative-only reward structure: a reward of 0 for correct classification and -1 for incorrect classification.
- Learning Mechanism: Predictors are updated via standard Q-learning equations, while base classifiers are trained specifically on the data points they were selected to handle.
Experimental Evaluation
The OLAP framework was evaluated using two benchmarks from the UCI Machine Learning Repository: OptDigits (handwritten digits 0-9) and Letters (handwritten letters A-Z). The latter represents a significantly more complex task due to the higher number of classes and greater variation in input patterns.
Key Results
The performance of OLAP varied based on task complexity:
- Letters Dataset: OLAP demonstrated a substantial advantage over AdaBoost. With 32 experts, OLAP achieved a test error of 3.4%, while AdaBoost remained at 15.2%. This suggests that OLAP's ability to divide a complex 26-class problem among specialized experts is highly effective.
- OptDigits Dataset: On this simpler task, AdaBoost performed slightly better (1.4% error) than OLAP (3.0% error). However, OLAP still significantly outperformed a single MLP (4.0% error).
- Scaling: Performance consistently improved as more experts were added, indicating that the Q-learning policy effectively coordinates larger ensembles.
Specialization and Margin Distribution
A core insight of OLAP is its promotion of specialization over generalization. Unlike AdaBoost, which forces all classifiers to focus on "hard" examples missed by previous iterations, OLAP encourages experts to partition the input space. Because the predictors are MLPs, the boundaries between these specialized regions are smooth, allowing the model to handle overlapping data gracefully.
Analysis of the margin distributions reveals that as the number of experts increases, the distribution shifts toward higher margins. This indicates that the ensemble not only becomes more accurate but also more confident in its classifications as experts become more specialized.
Conclusion and Future Work
OLAP demonstrates that reinforcement learning can effectively manage the trade-off between utilizing known experts and training new ones in an online setting. While successful, the authors note that scaling the action space remains a challenge; as the number of experts grows, efficient exploration becomes more difficult. Future research may explore policy gradient methods to allow for more sophisticated combinations of multiple experts rather than selecting a single winner-take-all specialist.
Summary updated