Abstract
Cross-validation is a useful and generally applicable technique often employed in machine learning, including decision tree induction. An important disadvantage of straightforward implementation of the technique is its computational overhead. In this paper we show that, for decision trees, the computational overhead of cross-validation can be reduced significantly by integrating the cross-validation with the normal decision tree induction process. We discuss how existing decision tree algorithms can be adapted to this aim, and provide an analysis of the speedups these adaptations may yield. The analysis is supported by experimental results.
Introduction
In machine learning, $n$-fold cross-validation (CV) is the gold standard for estimating model accuracy and tuning hyperparameters. However, the standard "serial" approach—partitioning data into $n$ blocks and training $n$ separate models—is computationally expensive. For decision trees, this process is highly redundant. In a 10-fold CV, approximately 90% of the training data is identical across folds, leading the algorithm to perform the same statistical tests repeatedly. This paper introduces a parallel algorithm that integrates cross-validation directly into the induction process to eliminate this overhead.
Methodology: Integrated Parallel Induction
The proposed parallel algorithm shifts the focus from looping through folds to looping through tree nodes, building all $n$ trees (plus a master tree on the full dataset) simultaneously.
Additive Statistics
The efficiency hinges on "additive" statistics (e.g., counts or sums). For any node, the algorithm computes statistics for the entire dataset ($D$) and for each of the $n$ test subsets ($D_i$). The statistics for a specific fold's training set ($T_i = D - D_i$) are then derived instantly: $S(T_i) = S(D) - S(D_i)$. This ensures each example is processed only once per node, regardless of the number of folds.
The Forest Structure
As long as the folds agree on the optimal split for a node, they share that node in a unified data structure. If the folds diverge and select different tests, the structure bifurcates into a forest, as illustrated in Figure 1.
Experimental Evaluation
The authors implemented this approach within TILDE, an Inductive Logic Programming (ILP) system. ILP is particularly well-suited for this optimization because its first-order logic queries are computationally intensive. Testing was conducted on five datasets: SB and CB (artificial geometric patterns), Muta (mutagenesis benchmark), ASM (adaptive systems management), and Mach (verification dataset).
Key Results
The parallel algorithm demonstrated significant performance gains over the serial baseline. As shown in Figure 5, speedups ($S$) approached the theoretical maximum in stable datasets.
For the "Simple Bongard" (SB) dataset, the algorithm achieved a 9.2x speedup for 10-fold CV. Furthermore, the parallel overhead ($O_p$)—the extra time spent on CV relative to building a single tree—was as low as 27%, compared to 1100% for the serial approach.
Discussion and Insights
The efficiency of the parallel method is intrinsically linked to the stability of the learning problem. In stable datasets, where small training set variations do not change the chosen split, folds rarely diverge, maximizing node sharing.
While highly effective for discrete tests in ILP, the authors note limitations regarding continuous attributes. If different folds suggest slightly different split points, the algorithm may bifurcate prematurely, reducing speedup. Additionally, while the forest structure is more memory-intensive than a single tree, the computational savings often outweigh the memory costs in complex learning tasks.
Conclusion
By integrating cross-validation into the tree induction process, the computational cost of model evaluation can be drastically reduced. This approach transforms $n$-fold cross-validation from a brute-force repetition into an efficient, parallelized operation, particularly benefiting computationally expensive domains like Inductive Logic Programming.
Summary updated