Hoeffding Trees and Streaming Decision Trees

A batch decision tree sorts every example at a node before it picks a split. On a stream of a billion events that is impossible twice over: the data does not fit in memory, and by the time one pass finished the generating process would have moved. The Hoeffding tree takes a different route. It decides each split from a prefix of the data, and it refuses to decide until the prefix is long enough to make the decision statistically safe.

The split decision as a statistical test

A leaf stores sufficient statistics, not examples: per-attribute, per-value, per-class counts. Every \(n_{\min}\) arrivals it scores the candidate attributes with information gain or Gini, and takes \(\Delta G\), the gap between the best attribute and the runner-up. Hoeffding's inequality bounds how far the empirical mean of a quantity with range \(R\) can sit from its true value after \(n\) independent observations:

If \(\Delta G > \epsilon\), the observed winner is the true winner with probability \(1 - \delta\) and the leaf splits. Otherwise it waits for more examples. Since \(\epsilon\) decays as \(1/\sqrt{n}\), any genuine gap is eventually resolved, and the probability of selecting a different test than a batch learner would have selected falls exponentially in the number of examples (Domingos and Hulten, 2000, Mining High-Speed Data Streams, KDD). That paper's VFDT system took the KDD 2015 test-of-time award, and the reason is this one trick: the stopping rule is derived rather than tuned.

Memory per leaf is \(O(\text{attributes} \times \text{values} \times \text{classes})\) and does not grow with the number of examples seen. Cost per example is a handful of counter increments, with scoring amortised over \(n_{\min}\) arrivals.

The tie that stalls the tree

Two attributes carrying nearly the same information produce a \(\Delta G\) that never exceeds \(\epsilon\), so the leaf waits forever and the subtree below it is never built. The standard patch is a tie threshold \(\tau\): once \(\epsilon < \tau\), declare the top two equivalent and split on either. Common defaults are \(\delta = 10^{-6}\), \(\tau = 0.05\) and \(n_{\min}\) in the low hundreds (García-Martín et al., 2018, Hoeffding Trees with nmin Adaptation, arXiv:1808.01145). Worth being honest about what \(\tau\) is: a heuristic bolted onto a derived rule, with no guarantee attached, and the original formulation did not specify it.

Drift: alternate subtrees

A split is close to permanent once made, which is a problem when the relationship changes under it. CVFDT keeps a sliding window of recent examples, grows alternate subtrees in the background, and promotes an alternate once the incumbent becomes less accurate, at \(O(1)\) cost per example (Hulten, Spencer and Domingos, 2001, Mining Time-Changing Data Streams, KDD, pp. 97-106).

The Hoeffding Adaptive Tree removes the window. It attaches an ADWIN change detector to each node, starts an alternate branch when a node's error estimate shifts, and swaps when the alternate measures better. Nothing has to be guessed about how fast or how often the stream drifts, and the authors report it never doing worse than CVFDT and sometimes much better (Bifet and Gavaldà, Adaptive Learning from Evolving Data Streams, IDA 2009).

Splitting early and repairing later

VFDT is deliberately cautious: it splits only when confident, and never revisits. Hoeffding Anytime Tree inverts that. It splits as soon as a split looks better than no split, then replaces the split if a better attribute later emerges, which gives higher prequential accuracy on most of the largest UCI classification datasets (Manapragada, Webb and Salehi, 2018, Extremely Fast Decision Tree, KDD, arXiv:1802.08780). The cost is paid when the top two attributes are genuinely close: an early wrong split produces an error spike that takes many examples to undo.

When it breaks

The bound does not cover what it is used for. Hoeffding's inequality bounds the deviation of an average of independent bounded variables. Information gain and the Gini index are nonlinear functions of those counts, not averages of them. Rutkowski and colleagues argue the usual derivation is therefore invalid and prove McDiarmid-based replacements for both criteria (Decision Trees for Mining Data Streams Based on the McDiarmid's Bound, IEEE TKDE 25(6):1272-1279, 2013). The trees work well in practice; the guarantee quoted for them is softer than the citation makes it sound.

Numeric attributes need their own approximation. Counts work for discrete values. Continuous attributes require Gaussian summaries or a binary structure over candidate thresholds, so split quality depends on an approximation whose memory grows per leaf, and the honest comparison with a batch tree disappears at that point.

Memory grows with the tree, not with the data. VFDT handles this by deactivating the least promising leaves, which stops their statistics accumulating and freezes that part of the model.

Synthetic generators flatter these models. Prequential accuracy on the standard stream generators is the field's default benchmark, and those generators were largely designed alongside the tree algorithms being measured.