An Eager Splitting Strategy for Online Decision Trees
This work addresses the need for more effective online learning algorithms in ensemble methods, though it is incremental as it builds on existing strategies.
The paper tackled the problem of improving online decision tree ensembles by replacing the split strategy of Hoeffding Tree with a more eager one from Hoeffding AnyTime Tree (HATT), which allows revision and converges to the ideal batch tree. The result showed that HATT outperformed Hoeffding Tree in most ensemble settings on UCI and synthetic streams, with statistical significance at a 0.05 level.
Decision tree ensembles are widely used in practice. In this work, we study in ensemble settings the effectiveness of replacing the split strategy for the state-of-the-art online tree learner, Hoeffding Tree, with a rigorous but more eager splitting strategy that we had previously published as Hoeffding AnyTime Tree. Hoeffding AnyTime Tree (HATT), uses the Hoeffding Test to determine whether the current best candidate split is superior to the current split, with the possibility of revision, while Hoeffding Tree aims to determine whether the top candidate is better than the second best and if a test is selected, fixes it for all posterity. HATT converges to the ideal batch tree while Hoeffding Tree does not. We find that HATT is an efficacious base learner for online bagging and online boosting ensembles. On UCI and synthetic streams, HATT as a base learner outperforms HT within a 0.05 significance level for the majority of tested ensembles on what we believe is the largest and most comprehensive set of testbenches in the online learning literature. Our results indicate that HATT is a superior alternative to Hoeffding Tree in a large number of ensemble settings.