On Imbalanced Regression with Hoeffding Trees

AI summary

Overview

• Research area: Online machine learning and data stream mining, specifically imbalanced regression with incremental (Hoeffding-style) decision trees.
• Technical level: Intermediate. Readers should know what decision trees, data streams, kernel density estimation, and regularization are; the paper's own derivation of the streaming KDE update requires comfort with simple algebra.
• Scope: The paper ports two batch-learning ideas — kernel density estimation (KDE) for skewed label distributions and hierarchical shrinkage (HS) for tree regularization — into streaming incremental decision trees and measures whether they help on five benchmark datasets.

What This Paper Is About

Real-world sensors produce continuous streams of data where the target values are unevenly distributed: some value ranges occur constantly, others almost never. Standard incremental decision trees such as Hoeffding Trees, which learn one example at a time, tend to predict the frequent ranges well and the rare ones poorly. The paper asks whether two recently proposed fixes from batch learning — smoothing predictions with KDE over binned labels, and regularizing tree predictions with hierarchical shrinkage — can be reformulated so they work incrementally on a stream, and whether they actually improve predictions.

Key Contributions

1. Hierarchical shrinkage on incremental trees. The authors implement HS, previously a post-hoc regularizer for batch decision trees, inside the incremental decision trees available in the scikit-multiflow library. They state they are the first to integrate HS into incremental decision trees and evaluate its impact on predictive accuracy.
2. A streaming formulation of KDE. Because the KDE estimate is an average, the authors derive a telescoping update (Equation 2) that computes the smoothed density from the previous estimate plus the newest observation, and package it as Algorithm 1 (Incremental KDE) over tumbling windows and label bins.
3. An online tuning protocol. They adopt a variation of Follow-the-Leader (Algorithm 2), in which a pool of model/hyper-parameter configurations trains in parallel on the stream and the best configuration is selected periodically using non-weighted RMSE, then used for a predict-then-train phase.
4. Evaluation across two libraries. Experiments with scikit-multiflow test HT and HAT with HS, KDE, and KDE+HS under Algorithm 2; additional experiments with the River library test KDE only on HT, HAT, iSOUP, and SGT. Code is public at https://github.com/marinaAlchirch/DSFA_2026.

Main Findings

• KDE is the main source of improvement. In the scikit-multiflow results (Table 2), in all datasets except E-Power the KDE variants (with or without HS) outperform the original HT and HAT models.
• Hierarchical shrinkage gives limited gains. The authors report that HS provides minimal gains, if any. In the scikit-multiflow table, HT+HS and HAT+HS often match their unregularized counterparts on most metrics.
• E-Power is the exception. For E-Power the plain HT performs even better than the KDE-enhanced variants (HT R² of 0.977 versus 0.959 for HT+KDE), while the KDE variants still beat the base HAT (HAT R² 0.756 versus 0.872 for HAT+KDE).
• HS helps in at least one streamed case. On Abalone, the KDE+HS version of HAT performs best, with MAE 1.560 versus 1.648 for HAT+KDE and 1.979 for plain HT/HAT, and R² 0.271 versus 0.192.
• Selective wins on individual datasets (scikit-multiflow). California: R² 0.512 for HT+KDE+HS versus 0.380 for HT. NY Taxi: R² 0.577 for HT+KDE versus 0.333 for HT.
• River results favor KDE on aggregate. Across the River experiments (Table 3), KDE-enhanced models are better in 17 of 24 cases for MAE, 18 of 24 for RMSE and INVWRMSE, 15 of 24 for WRMSE, and 16 of 24 for R².
• Dataset-level wins in River. Depending on the metric, KDE-enhanced models produce the best model in six of six datasets (MAE), five of six (RMSE), four of six (WRMSE), five of six (INVWRMSE), and five of six (R²).
• KDE is not universally better in River. On Semi-L4, HAT+KDE has MAE 74.1 versus 72.9 for plain HAT, and in the Semi-L4 plot the KDE variant underperforms during most of the stream before becoming equivalent to plain HT near the end.
• Large gains on the hardest semiconductor layers. On Semi-L3, HAT+KDE reaches MAE 27.5 versus 66.9 for plain HAT, and HT+KDE reaches MAE 62.6 versus 97.3 for HT.
• The base-model differences between libraries are explained, not hidden. The authors attribute differing HT and HAT numbers across Tables 2 and 3 to tuning-phase stream bypassing, differing metric weights (since the sequences used to derive weights differ), minor implementation differences such as using mean for leaf prediction, and the absence of tuning in the River runs.
• No label-distribution leakage into learning. The authors state that knowledge of the full distribution is used only to compute the evaluation penalties, and that the KDE-enhanced models use a tumbling window over examples actually seen.

Methodology in Plain English

The authors take incremental decision trees that decide splits using Hoeffding's inequality and add two things on top. First, instead of predicting a raw leaf value, the tree's output is smoothed using kernel density estimation: label values are grouped into bins of range r, a Gaussian or Epanechnikov kernel with bandwidth h spreads each observed label's influence onto nearby bins, and the density estimate is updated incrementally with a running-average formula over a tumbling window of recent examples. Second, hierarchical shrinkage changes the prediction so that every node on the root-to-leaf path contributes, with each node's contribution divided by 1 + λ/N(t), where N(t) is the number of samples at the parent node and λ is a regularization hyper-parameter; the tree structure itself is never modified, so this is cheap for a stream.

To choose hyper-parameters fairly, they use a Follow-the-Leader setup: several configurations train side by side, and after a tuning phase of fixed length the configuration with the lowest non-weighted RMSE is applied to the next block of examples before retraining resumes. They evaluate with MAE, RMSE, WRMSE (which up-weights frequent label bins), INVWRMSE (which up-weights rare label bins), and R².

Experiments run on Abalone, Semi (semiconductor film thickness, layers 3 and 4), California Housing, NY Taxi, and E-Power. Datasets are preprocessed: outliers removed in all but Abalone, constructed features for NY Taxi and E-Power, and stream prefixes used (first 20,000 of NY Taxi's 1,458,644 examples, first 100,000 of E-Power's 2,075,259 examples, first 20,000 of Semi's 810,000 examples, leaving 19,452 after outlier removal; California retains 20,635 examples after removing 5 extremes). Tuning windows are sized min(⌊|S|/8⌋, 3000), and searched values include r ∈ {0, 0.1, 0.2, 0.5, 1}, λ ∈ {0, 0.1, 1, 10, 15, 25}, h ∈ {10, 50, 100}, and window size |W| ∈ {50, 100, 200}. The River experiments skip tuning and use fixed h = 10, r = 0.2, |W| = 50. All experiments ran on a macOS laptop with an Apple Silicon M2 processor and 16 GB of RAM.

Why This Matters

• Impact on research. The paper shows that a batch-learning idea as simple as KDE can be reformulated for a one-pass stream with a cheap telescoping update, while a second popular idea (hierarchical shrinkage) transfers much less convincingly. It provides a clear negative result alongside a positive one, and it introduces streaming-aware metrics (WRMSE and INVWRMSE) for judging imbalanced regression.
• Real-world applications (drawn from the paper's framing of continuous sensor streams):
  • Credit scoring and fraud detection, where unusual transactions are by definition rare.
  • Human activity recognition from continuous sensor feeds.
  • Clinical decision support on patient streams.
  • Weather prediction of phenomena such as hail size or wind intensity, where extreme values are rare but high-stakes.
• Industry relevance. Incremental trees are common base learners in streaming ensembles, so improving their behavior on skewed targets is directly useful in deployment settings where models must learn as data arrives and cannot be retrained from scratch. The authors also publish their implementation, reducing the cost of adoption.

Future Directions

1. Ensembles. The authors anticipate that the observed benefits will translate to random forests and other ensembles of incremental tree-based models.
2. Classification. They note that KDE does not naturally extend to pure classification problems and raise the question of whether a new method can improve incremental models there, with or without HS.
3. Concept drift. Drift is explicitly not the focus of this work, and coupling drift with imbalanced data and potentially KDE is described as an exciting direction.
4. Tuning coverage. Semi could not be run with the full Algorithm 2 tuning due to time constraints, and the River experiments had no hyper-parameter tuning at all, so closing that gap is a natural follow-up.

Target Audience

Researchers and practitioners in streaming machine learning and data stream mining who work with regression on skewed targets; engineers using scikit-multiflow or River who need incremental models to predict rare value ranges; and anyone studying imbalanced learning outside classification, since the paper supplies both a transfer recipe and metrics (WRMSE, INVWRMSE) for measuring performance on frequent versus rare label ranges.

Authors’ abstract

Many real-world applications provide a continuous stream of data that is subsequently used by machine learning models to solve regression tasks of interest. Hoeffding trees and their variants have a long-standing tradition due to their effectiveness, either alone or as base models in broader ensembles. At the same time a recent line of work in batch learning has shown that kernel density estimation (KDE) is an effective approach for smoothed predictions in imbalanced regression tasks [Yang et al., 2021]. Moreover, another recent line of work for batch learning, called hierarchical shrinkage (HS) [Agarwal et al., 2022], has introduced a post-hoc regularization method for decision trees that does not alter the structure of the learned tree. Using a telescoping argument we cast KDE to streaming environments and extend the implementation of HS to incremental decision tree models. Armed with these extensions we investigate the performance of decision trees that may enjoy such options in datasets commonly used for regression in online settings. We conclude that KDE is beneficial in the early parts of the stream, while HS hardly, if ever, offers performance benefits. Our code is publicly available at: https://github.com/marinaAlchirch/DSFA_2026.