Correcting Split Selection in Online Decision Trees via Anytime-Valid Inference

Technical Summary: Correcting Split Selection in Online Decision Trees via Anytime-Valid Inference

1. Problem Definition

The paper addresses a fundamental statistical flaw in Hoeffding Trees (HT), the standard base learner for ensemble methods in data stream learning (e.g., Adaptive Random Forests). While HTs have achieved empirical success by incrementally growing trees using concentration inequalities (like Hoeffding's or McDiarmid's) to determine when a split is statistically significant, their theoretical guarantees are invalid in practice.

The core issue is the optional stopping problem. Standard concentration inequalities assume a fixed sample size. However, HTs employ a data-dependent stopping rule: they continuously monitor impurity estimates and commit to a split the first time a threshold is crossed. This "optional continuation" invalidates fixed-time bounds, potentially inflating the probability of false splits to one. Furthermore, existing corrections often assume independent, stationary data, whereas HTs are frequently deployed in non-stationary, dependent streams within ensemble frameworks.

2. Methodology

The authors propose a principled alternative based on Safe, Anytime-Valid Inference (SAVI), specifically utilizing Testing by Betting and Confidence Sequences (CS).

• Reframing Split Selection: Instead of comparing candidate splits against each other to find the global optimum (which may be ill-defined in non-stationary settings), the method frames split selection as an online model comparison. It tests whether a "challenger" model (a leaf split according to a candidate) demonstrably outperforms the "incumbent" model (the unsplit leaf) based on observed data.
• Loss Functions: Predictive performance is evaluated using bounded loss functions (e.g., log loss or Brier score), serving as analogues to entropy and Gini impurity.
• Hypothesis Testing:
  • Strong Null ($H_0$): The challenger never outperforms the incumbent at any point in time ($\delta_t \le 0$).
  • Weak Null ($H_{w,0}$): The challenger does not outperform the incumbent on average over time.
  • The paper primarily adopts the Strong Null, aligning with recommendations for comparing closely related algorithms on the same data stream.
• Testing Mechanisms:
  1. Betting-Based Test (AVTB): Interprets hypothesis testing as a betting game. A bettor wagers on the sign of the loss difference ($\Delta_t$). Under the null, no strategy yields positive expected growth. The method uses a Universal Portfolio (UP) strategy with a Jeffreys prior to update wealth ($W_t$). If $W_t$ exceeds $1/\alpha$, the null is rejected, and the split is committed. This process is a nonnegative supermartingale, ensuring validity under arbitrary stopping times via Ville's inequality.
  2. Confidence Sequence Test (AVTCS): Uses empirical Bernstein confidence sequences to test the weak null. The stopping time is defined when the lower bound of the confidence sequence for the average advantage exceeds zero.
• Global Error Control: To handle the potentially infinite number of candidate splits generated over time, the authors allocate significance levels ($\alpha_{v,c}$) across all tests such that their sum is bounded by a global $\alpha$. This ensures that the probability of any false split occurring over the tree's lifetime is at most $\alpha$.

3. Key Contributions

1. Valid Split Criterion: Derivation of a split criterion that remains statistically valid under arbitrary data-dependent stopping rules, applicable to both non-stationary and dependent data streams.
2. Finite Commitment: Proof that if a candidate split exhibits a persistent predictive advantage, the procedure commits to the split in finite time with a rate of $\tilde{O}(\log(1/\alpha)/\Delta^2)$.
3. Monotonic Risk Reduction: Under stationary i.i.d. data, the expected predictive loss of the deployed tree is shown to be non-increasing over time and strictly improves at every split commit.
4. Drop-in Replacement: The method serves as a direct replacement for Hoeffding Trees within existing ensemble frameworks like Adaptive Random Forests (ARF), creating an "Anytime-Valid Forest" (AVF).

4. Experimental Results

The authors evaluated their method (AVT) and its ensemble variant (AVF) on 12 real-world data streams (6 regression, 6 classification) and synthetic benchmarks.

• Performance:
  • Stability: Unlike standard Hoeffding Trees, which exhibited repeated, abrupt drops in generalization performance even on stationary data, the anytime-valid methods showed stable, monotone improvement.
  • Accuracy: AVTB (betting-based) generally outperformed the standard HT and was competitive with or surpassed the ARF baseline on several streams. The ensemble AVF consistently outperformed standard ARF across nearly all datasets.
  • Model Size: The proposed methods produced substantially smaller trees (fewer nodes/leaves) compared to HT and ARF while achieving higher or comparable predictive performance.
• Computational Cost:
  • Inference time remained comparable to HT.
  • Update times were higher due to the maintenance of shadow challenger statistics and wealth calculations but remained within practical bounds (milliseconds per instance).
  • The authors note that AVF often learns shallower trees, reducing the number of nodes requiring updates, which mitigates computational overhead.

5. Significance and Claims

The paper claims to resolve a "fundamental limitation" of existing online decision tree methods. By abandoning fixed-sample-size inequalities in favor of anytime-valid inference, the authors provide statistical guarantees that hold under the very conditions (data-dependent stopping, non-stationarity) where previous methods fail.

The significance lies in:

• Theoretical Rigor: Providing the first valid statistical guarantees for split selection in online trees under optional stopping.
• Practical Robustness: Demonstrating that statistical validity translates to empirical stability, preventing the "collapse" of performance seen in standard HTs.
• Efficiency: Achieving better predictive performance with smaller, more parsimonious models, suggesting that the "noise" introduced by invalid split decisions in standard HTs leads to unnecessary tree growth.

The authors conclude that their framework serves as a robust, drop-in replacement for Hoeffding Trees, effectively correcting the statistical foundation of one of the most widely used algorithms in data stream mining.