Hoeffding Tree Split Confidence

Worked Example

Suppose we are deciding between two features, A and B, in a binary classification tree using Gini impurity. We observe N independent samples. For this example, let N = 200, corresponding to a count multiplier of 10 applied to our "Strong" table base counts. We specify a confidence bound parameter delta = 0.05.

1. The base counts for feature A are [[8, 2], [2, 8]], total 20. Multiplied by 10 gives [[80, 20], [20, 80]]. We compute the Gini gain of A. Root Gini = 1 - (100/200)^2 - (100/200)^2 = 0.5. Child Gini for [80, 20] is 1 - (80/100)^2 - (20/100)^2 = 0.32. Total child Gini = (100/200)*0.32 + (100/200)*0.32 = 0.32. Gain A = 0.5 - 0.32 = 0.18.
2. For feature B, the counts are [[60, 40], [40, 60]]. Child Gini = 1 - (60/100)^2 - (40/100)^2 = 0.48. Gain B = 0.5 - 0.48 = 0.02.
3. The merit gap between the best and second-best split is Gap = Gain A - Gain B = 0.18 - 0.02 = 0.16.
4. We compute the Hoeffding bound epsilon using the conservative range R = 1 for Gini gain: epsilon = sqrt(ln(1/0.05) / (2 * 200)) = sqrt(2.9957 / 400) ≈ 0.0865.
5. Since Gap (0.16) > epsilon (0.0865), we can confidently split on feature A.

Experiment

Open the Hoeffding Tree Split Confidence module to test how the number of observations and the allowed error rate affect the split decision.

1. Set Tables to "Strong", Count multiplier to 10, Delta to 0.05, and Tie threshold to 0. Notice the Gap (0.16) is larger than the Hoeffding epsilon (0.0865), resulting in a "Split by merit gap" decision.
2. Change the Count multiplier to 1. The total observations drop to 20, causing the Hoeffding epsilon to increase to 0.273. Because epsilon is now larger than the Gap (0.16), the decision becomes "Defer" to wait for more data.
3. Set Tables to "Weak", Count multiplier to 100, and Delta to 0.05. Here the Gap is only 0.02, while epsilon shrinks to 0.0273. The decision remains "Defer".
4. To force a split despite similar merits, change the Tie threshold to 0.05. Since the epsilon (0.0273) falls below this threshold, the algorithm uses the "Split by tie heuristic" decision, avoiding infinite deferrals when features are nearly identical.

Limitations

The Hoeffding bound assumes that the observations are independently generated from a stationary distribution. It provides an idealized per-decision confidence interval, not an anytime guarantee for the entire adaptive tree structure, which would require more complex uniform bounds over all possible node sequences. The implementation uses a conservative range R=1 for Gini gain. Additionally, the tie-breaking threshold is a practical heuristic, not a mathematically robust confidence proof, and is applied strictly as an alternative when pure merit separation cannot be achieved. The examples represent aggregate statistics, not a full streaming-tree implementation.

References

See the original paper for more details:

• Domingos, P., & Hulten, G. (2000). Mining High-Speed Data Streams. Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining. This foundational paper introduces the Hoeffding Tree (VFDT) algorithm, describing the use of the Hoeffding bound for stream split decisions and the tie-breaking heuristic.