Principle:Online ml River Adaptive Hoeffding Tree
| Knowledge Sources | Domains | Last Updated |
|---|---|---|
| River River Docs Adaptive Learning from Evolving Data Streams | Online Machine Learning, Concept Drift, Decision Trees | 2026-02-08 16:00 GMT |
Overview
The Adaptive Hoeffding Tree is an extension of the Hoeffding Tree that incorporates per-node drift detection via ADWIN to adapt the tree structure when concept drift occurs.
Description
A standard Hoeffding Tree grows incrementally by using the Hoeffding bound to decide when a leaf has seen enough data to warrant a split. However, once a split is made, it is permanent -- the tree cannot adapt if the data distribution changes. The Adaptive Hoeffding Tree (also called the Hoeffding Adaptive Tree or HAT) addresses this limitation by attaching an ADWIN drift detector to each node in the tree.
When ADWIN detects a statistically significant change in the local error rate at a node, the node is considered to have drifted. At that point, an alternate subtree is grown on the post-drift data. Once the alternate subtree has observed enough instances (controlled by the drift_window_threshold parameter) and demonstrates statistically better performance (determined by the switch_significance parameter), it replaces the original subtree. If the alternate subtree does not prove superior, it is pruned.
Additionally, bootstrap sampling (enabled by default) adds diversity to the learning process by resampling instances with a Poisson(1) distribution, which generally improves the tree's adaptability.
Usage
Use the Adaptive Hoeffding Tree when:
- The data stream is expected to exhibit concept drift over time.
- You need a single-tree classifier that can automatically adapt its structure to distributional changes.
- You want the interpretability of a decision tree combined with drift adaptation.
- You need a balance between the stability of a full tree and the reactivity of a fresh model.
Theoretical Basis
The Adaptive Hoeffding Tree combines two foundational concepts:
1. Hoeffding Bound for Splitting:
At each leaf, the Hoeffding bound determines when enough evidence has accumulated to make a statistically sound split decision. Given observations, the bound states that the true mean of a random variable bounded in differs from the sample mean by at most:
where is the confidence parameter. A split is performed when the difference in splitting criterion between the best and second-best attributes exceeds .
2. ADWIN for Per-Node Drift Detection:
Each node maintains an ADWIN (ADaptive WINdowing) instance that monitors the local classification error. ADWIN maintains a variable-length window of recent error values and tests whether any partition of this window into two sub-windows yields significantly different means. When drift is detected:
For each node with ADWIN detector:
1. Feed classification error (0 or 1) to ADWIN
2. If ADWIN signals drift:
a. Create an alternate subtree rooted at this node
b. Train the alternate subtree on new data
3. If alternate subtree has seen >= drift_window_threshold instances:
a. Compare error rates using binomial test at switch_significance level
b. If alternate is significantly better: replace original subtree
c. Otherwise: prune the alternate subtree
3. Bootstrap Sampling:
When bootstrap_sampling=True, each training instance is weighted by a value drawn from a Poisson(1) distribution. This introduces diversity analogous to bagging, which helps the tree adapt more robustly by preventing overfitting to individual observations.
The combination of these mechanisms allows the tree to maintain stable performance on stationary regions of the stream while selectively adapting subtrees that are affected by concept drift.