Extremely Fast Hoeffding Adaptive Tree

Many real-world data streams are non-stationary. Subject to concept drift, the distributions change over time. To retain accuracy in the face of such drift, online decision tree learners must discard parts of the tree that are no longer accurate and replace them by new subtrees that reflect the new distribution. The longstanding state-of-the-art online decision tree learner for non-stationary streams is Hoeffding Adaptive Tree (HAT), which adds a drift detection and response mechanism to the classic Very Fast Decision Tree (VFDT) online decision tree learner. However, for stationary distributions, VFDT has been superseded by Extremely Fast Decision Tree (EFDT), which uses a statistically more efficient learning mechanism than VFDT. This learning mechanism needs to be coupled with a compensatory revision mechanism that can compensate for circumstances where the learning mechanism is too eager. The current work develops a strategy to combine the best of both these state-of-the-art approaches, exploiting both the statistically efficient learning mechanism from EFDT and the highly effective drift detection and response mechanism of HAT. To do so requires decoupling of the EFDT splitting and revision mechanisms, as the latter incorrectly triggers the HAT drift detection mechanism. The resulting learner, Extremely Fast Hoeffding Adaptive Tree, responds to drift more rapidly and effectively than either HAT or EFDT, and attains a statistically significant advantage in accuracy even on stationary streams.

I. Introduction

Data streams are often subject to concept drift [1]. Such non-stationary streams pose a challenge for online learning systems that must adapt their models as the distributions generating the data evolve [2]. Hoeffding Adaptive Tree (HAT) [3] is the current state of the art algorithm for online decision tree learning under drift. It is based on the Hoeffding Tree, an online decision tree algorithm designed for learning from stationary distributions. The Hoeffding Tree [4] employs a conservative learning mechanism. It only adds a new branch to a tree when the risk is negligible that any alternative split could be better.