Decision Trees as Base Learners

Decision trees are the specific type of model overwhelmingly used as the building block within gradient boosting frameworks. While other models could theoretically serve as base learners, decision trees, particularly Classification and Regression Trees (CART), offer a compelling combination of properties that make them exceptionally well-suited for the additive, error-correcting nature of boosting.

Why Decision Trees?

Decision trees partition the feature space into rectangular regions and assign a constant prediction value within each region (specifically, within each leaf node). This inherent structure provides several advantages in the context of boosting:

1. Capturing Non-linearities and Interactions: Unlike linear models, trees naturally model non-linear relationships between features and the target variable. Furthermore, the sequential nature of splits allows trees to capture complex interaction effects. For example, a split on feature A followed by a split on feature B effectively isolates a region defined by conditions on both A and B, implicitly modeling their interaction. Boosting adds trees that refine predictions in different regions of the feature space, capturing patterns.

2. Handling Diverse Data Types: Standard CART algorithms can handle both numerical (continuous or discrete) and categorical features natively during the splitting process, although some boosting library implementations might require preprocessing like one-hot encoding for categorical variables initially. More advanced libraries like LightGBM and CatBoost incorporate specialized, highly efficient methods for handling categorical features directly, a topic we will cover in detail later.

3. Computational Considerations: Finding optimal splits in trees involves scanning features and potential split points. While computationally intensive for deep trees on large datasets, algorithms have been developed (exact greedy, approximate methods, histogram-based approaches) that make training reasonably efficient, especially for the relatively simple trees used in boosting. These algorithms are readily parallelizable to a certain extent.

4. Interpretability (of Individual Trees): While a large boosted ensemble with hundreds or thousands of trees is complex, a single, shallow decision tree is relatively easy to visualize and understand. This property is helpful during the development and debugging phases, allowing inspection of what each individual tree contributes to the ensemble.

The Concept of "Weak Learners"

Boosting iteratively combines multiple "weak learners" to produce a single "strong learner". A weak learner is defined as a model that performs only slightly better than random guessing on the classification or regression task. In the context of decision trees, this translates to using shallow trees, often referred to as "stumps" (trees with only one split, i.e., depth 1) or trees with very limited depth (e.g., depth 2 to 8).

Why weak learners?

• Reduced Overfitting: Deep, complex trees are prone to overfitting the training data. By keeping individual trees simple, boosting restricts the complexity added at each iteration.
• Focus on Residuals: Each new tree focuses on correcting the errors (residuals or pseudo-residuals) made by the ensemble so far. A weak learner is sufficient for capturing the signal present in these residuals without overfitting to the noise.
• Gradual Improvement: Boosting builds the model incrementally. Using weak learners ensures this process is gradual, preventing large, potentially unstable jumps in the model's predictions and allowing for fine-tuning through many iterations.

Common hyperparameters used to control tree complexity and keep them "weak" include:

• max_depth: The maximum depth allowed for any individual tree.
• min_samples_split: The minimum number of samples required to consider splitting an internal node.
• min_samples_leaf: The minimum number of samples required to be present in a leaf node.
• max_leaf_nodes: The maximum number of terminal nodes (leaves) a tree can have.

This contrasts sharply with algorithms like Random Forests, which typically benefit from using deep, fully grown (or nearly fully grown) decision trees as base learners, relying on averaging predictions across many uncorrelated trees to reduce variance.

Tree Construction in Boosting

While standard decision trees are trained to predict the target variable $y$ directly, trees within a gradient boosting ensemble are trained differently. At each iteration $m$, a new tree $h_m(x)$ is trained to predict the pseudo-residuals from the previous stage.

For common loss functions like squared error in regression, the pseudo-residuals are simply the negative gradients of the loss function with respect to the model's prediction at the previous step, which conveniently turn out to be the actual residuals: $r_{im} = y_i - F_{m-1}(x_i)$, where $F_{m-1}(x)$ is the ensemble's prediction after $m-1$ iterations.

For other loss functions (like Log Loss for classification), the pseudo-residuals represent the negative gradient, guiding the tree construction towards directions that maximally reduce the overall loss. The tree splitting criteria (like variance reduction for regression trees) are then applied using these pseudo-residuals as the target values.

Consider a simple regression example:

1. Start with an initial constant prediction $F_0(x)$.
2. Calculate the residuals $r_{i1} = y_i - F_0(x_i)$ for all data points $i$.
3. Train a shallow decision tree $h_1(x)$ to predict these residuals $r_{i1}$. The splits in this tree aim to group data points with similar residual values.
4. Update the ensemble prediction: $F_1(x) = F_0(x) + \nu h_1(x)$ (where $\nu$ is the learning rate).
5. Calculate new residuals $r_{i2} = y_i - F_1(x_i)$.
6. Train a new tree $h_2(x)$ to predict $r_{i2}$, and so on.

Each tree focuses on explaining the remaining error unexplained by the current ensemble.

A simplified view of a single regression tree grown on pseudo-residuals within a boosting iteration. Splits aim to minimize the variance of the residuals within the resulting nodes.

Addressing Tree Limitations

Individual decision trees suffer from certain drawbacks:

• High Variance: They can be very sensitive to small changes in the training data, leading to different tree structures and potentially overfitting.
• Greedy Splitting: The process of finding the best split at each node is greedy and doesn't guarantee a globally optimal tree.

Gradient boosting effectively mitigates these issues:

• Variance Reduction: By averaging the predictions of many trees (albeit in an additive, staged manner) and using techniques like shrinkage (learning rate) and subsampling (stochastic gradient boosting), the overall variance of the final model is significantly reduced compared to a single tree.
• Improved Accuracy: The sequential fitting process allows the ensemble to gradually refine predictions and potentially discover more complex patterns than a single tree could capture optimally due to its greedy nature. Regularization techniques, discussed later, further control complexity.

In summary, decision trees, particularly shallow CART implementations, provide the necessary flexibility to model complex functions and interactions, can handle different data types, and can be trained reasonably efficiently. Their tendency towards high variance when grown deep is purposefully constrained in boosting by keeping them "weak". They are trained not on the original target but on the residuals or gradients of the loss function, allowing the boosting ensemble to sequentially correct errors and build a powerful predictive model. This foundation is critical for appreciating the specific optimizations and enhancements introduced by algorithms like XGBoost, LightGBM, and CatBoost.