Decision Tree Fundamentals

A decision tree's structure—its nodes, edges, and splitting rules—is merely the scaffolding. The actual value of the tree lies in its leaf predictions: the outputs returned when a sample reaches a terminal node. Every path through the tree terminates at a leaf, and every leaf must provide an answer.

But what exactly should that answer be? For classification, should we output the most common class, or class probabilities? For regression, should we return the mean or median of target values? How do we handle edge cases—leaves with very few samples or leaves where classes are tied?

This page provides a rigorous treatment of leaf prediction mechanisms. We will explore how predictions are computed, the statistical properties of these predictions, and the implications for model behavior and calibration. Understanding leaf predictions is essential for interpreting tree outputs, debugging unexpected behavior, and extending trees to more sophisticated ensemble methods.

In classification trees, each leaf node contains a subset of training samples that reached it during tree construction. The prediction for any new sample that traverses to this leaf is derived from these training samples.

Majority Class Prediction

The most common prediction rule is majority voting: the leaf predicts the most frequent class among its training samples.

Formal definition:

For a leaf node $\ell$ containing samples $\mathcal{D}_\ell = {(\mathbf{x}_i, y_i)}$, the predicted class is:

$$\hat{y}\ell = \arg\max{k \in {1, \ldots, K}} \sum_{i : (\mathbf{x}i, y_i) \in \mathcal{D}\ell} \mathbb{1}[y_i = k]$$

Where $K$ is the number of classes and $\mathbb{1}[\cdot]$ is the indicator function.

Example:

• Leaf contains: 45 samples of class A, 5 samples of class B
• Prediction: class A (majority with 90% of samples)

Tie-Breaking

When two or more classes have equal maximum counts, a tie-breaking rule is needed:

1. Lowest class index: Predict the class with smallest index (deterministic)
2. Random selection: Uniformly random among tied classes
3. Prior-weighted: Prefer the class with higher prior probability

Most implementations use the lowest-index rule for reproducibility.

Class Probability Predictions

Often more useful than a single class label is the probability distribution over classes. This enables:

• Calibrated confidence estimates
• Threshold tuning for precision-recall tradeoffs
• Probabilistic ensemble combination

Empirical class probabilities:

$$\hat{P}(Y = k | \mathbf{x} \in \ell) = \frac{n_{\ell,k}}{n_\ell}$$

Where:

• $n_{\ell,k}$ = number of samples of class $k$ in leaf $\ell$
• $n_\ell$ = total samples in leaf $\ell$

Example:

• Leaf contains: 45 class A, 5 class B (total 50)
• Probability predictions: $P(A) = 0.90$, $P(B) = 0.10$

These probabilities are empirical frequencies from training data, directly interpretable as the fraction of training samples of each class that reached this leaf.

Probability Calibration Issues

Leaf probabilities from decision trees are often poorly calibrated:

1. Pure leaves overconfident: A leaf with 10/10 class A samples predicts $P(A) = 1.0$, but the true probability may be lower

2. Small sample variance: Leaves with few samples have high-variance probability estimates

3. Discretization artifacts: Trees produce only $|V_L|$ distinct probability values, not a smooth probability surface

For well-calibrated probabilities, consider:

• Larger minimum leaf samples (min_samples_leaf)
• Laplace smoothing (pseudo-counts)
• Post-hoc calibration (Platt scaling, isotonic regression)

Regression trees predict continuous values rather than discrete classes. The prediction mechanism differs but shares the same fundamental principle: aggregate the training samples in the leaf.

Mean Prediction (Standard)

The standard regression tree prediction is the arithmetic mean of target values in the leaf:

$$\hat{y}\ell = \frac{1}{n\ell} \sum_{i : (\mathbf{x}i, y_i) \in \mathcal{D}\ell} y_i$$

Why the mean?

The mean minimizes the sum of squared errors within the leaf:

$$\hat{y}\ell = \arg\min_c \sum{i \in \ell} (y_i - c)^2$$

Taking the derivative and setting to zero: $$\frac{\partial}{\partial c} \sum_i (y_i - c)^2 = -2\sum_i (y_i - c) = 0$$ $$\Rightarrow c = \bar{y}_\ell$$

This aligns with the Mean Squared Error (MSE) splitting criterion used during tree construction.

Alternative Prediction Rules

Median prediction: $$\hat{y}_\ell = \text{median}{y_i : (\mathbf{x}i, y_i) \in \mathcal{D}\ell}$$

• Minimizes Mean Absolute Error (MAE) instead of MSE
• More robust to outliers in target values
• Less commonly used; requires MAE splitting criterion for consistency

Weighted mean: $$\hat{y}_\ell = \frac{\sum_i w_i y_i}{\sum_i w_i}$$

• When samples have importance weights
• Used in gradient boosting where weights represent gradients

Quantile predictions:

• Instead of predicting mean, predict specific quantiles (10th, 50th, 90th percentile)
• Enables prediction intervals
• Specialized quantile regression forests

Variance of Leaf Predictions

The variance of the mean estimate in a leaf depends on sample size and target variance:

$$\text{Var}(\hat{y}\ell) = \frac{\sigma\ell^2}{n_\ell}$$

Where $\sigma_\ell^2$ is the variance of target values within the leaf.

Implications:

1. Small leaves are unreliable: With $n_\ell = 3$ and $\sigma_\ell = 10$, the standard error is $10/\sqrt{3} \approx 5.8$—predictions are highly uncertain

2. Min samples constraints matter: Setting min_samples_leaf = 20 ensures standard error ≤ $\sigma_\ell/\sqrt{20} \approx 0.22\sigma_\ell$

3. Deep trees have high variance: More leaves means fewer samples per leaf, hence higher variance predictions

One of the most fundamental properties of decision trees is that they produce piecewise constant functions. Understanding this is crucial for grasping both their capabilities and limitations.

The Nature of Tree Predictions

A decision tree with $L$ leaves defines a function:

$$f(\mathbf{x}) = \sum_{\ell=1}^{L} c_\ell \cdot \mathbb{1}[\mathbf{x} \in R_\ell]$$

Where:

• $c_\ell$ is the constant prediction for leaf $\ell$ (class label or mean value)
• $R_\ell$ is the hyperrectangle region corresponding to leaf $\ell$
• $\mathbb{1}[\mathbf{x} \in R_\ell]$ is 1 if sample x falls in region $\ell$, else 0

Key observation: The prediction is constant within each region. There are no gradients, no smooth transitions—just flat values that jump discontinuously at region boundaries.

Implications for Prediction

Regression:

The predicted function is a staircase in 1D, a set of flat plateaus in 2D, and hypercube-topped terraces in higher dimensions.

• Cannot capture smooth underlying functions exactly
• Must approximate curves with many small steps
• More leaves = finer approximation = higher variance
• The error for smooth functions decreases as $O(L^{-2/d})$ where $d$ is dimension

Classification:

The decision boundary is a union of axis-aligned hyperrectangle edges.

• Cannot represent diagonal boundaries directly
• Diagonal patterns require many splits (staircase approximation)
• Class probability surfaces are also piecewise constant

Relationship to Histograms

A decision tree's prediction histogram is adaptive:

Fixed histogram:

• Bins of equal width
• Predetermined, ignores data distribution
• Wastes capacity on empty regions

Decision tree:

• "Bins" (leaves) have variable sizes
• Adaptive to data density and label structure
• More bins where data is complex, fewer where simple
• Optimal bin boundaries chosen by splitting algorithm

This adaptive binning is why trees can capture complex patterns with relatively few leaves, while fixed histograms struggle.

Understanding the statistical properties of leaf predictions helps us reason about tree behavior, variance-bias tradeoffs, and the role of regularization.

Bias-Variance in Leaves

Bias component:

Within any leaf region $R_\ell$, we predict a single constant $c_\ell$ for all points. If the true function $f(\mathbf{x})$ varies within the region, we incur approximation bias:

$$\text{Bias}\ell^2 = \mathbb{E}{\mathbf{x} \in R_\ell}[(f(\mathbf{x}) - c_\ell)^2]$$

Smaller regions (more leaves) reduce this bias but...

Variance component:

The leaf prediction $\hat{c}_\ell$ is estimated from a finite sample. With fewer samples per leaf:

$$\text{Var}(\hat{c}\ell) = \frac{\sigma^2}{n\ell}$$

More leaves = fewer samples per leaf = higher variance.

The Bias-Variance Tradeoff in Trees

Optimal complexity:

The best tree balances bias and variance. This optimal point depends on:

• Dataset size (more data allows more leaves)
• Signal complexity (complex patterns need more leaves)
• Noise level (noisy data needs fewer leaves to avoid fitting noise)

Sample Size Effects

Minimum samples constraints encode prior knowledge:

• min_samples_leaf = k: Each prediction is based on at least $k$ samples
• Standard error bounded by $\sigma/\sqrt{k}$
• Prevents extreme predictions from tiny leaves

Rule of thumb for regression:

• $k \geq 5$: Acceptable for exploratory analysis
• $k \geq 20$: Reasonable for production models
• $k \geq 50$: Conservative for high-stakes applications

Rule of thumb for classification:

• $k \geq 5$: May work but probabilities are crude
• $k \geq 20$: Reasonable probability estimates
• $k \geq 50$: Well-supported probability estimates

These are rough guidelines; actual requirements depend on class imbalance, noise level, and application requirements.

Several practical issues affect leaf prediction quality in real-world applications.

Dealing with Class Imbalance

In imbalanced classification, naive majority voting can be problematic:

Example: 95% class A, 5% class B training data

• Many leaves will predict class A simply because A samples dominate
• Minority class B may never be predicted unless leaves achieve near-purity

Mitigations:

1. Class weights: Weight minority samples higher during training, affecting both splits and leaf predictions
2. Threshold tuning: Use probability predictions and tune threshold (e.g., predict B if $P(B) > 0.2$)
3. Resampling: Balance training data via over/under-sampling
4. Cost-sensitive learning: Modify split criteria to account for misclassification costs

Empty Test Region Problem

During prediction, a test sample might traverse to a leaf that has characteristics very different from any training sample—even though the tree structure was learned from training data.

Why this happens:

• Training data doesn't fully cover the feature space
• Some feature combinations rare or absent in training
• Split thresholds create regions with no training precedent

Example:

• Training: age ∈ [20, 60], income ∈ [$30k, $150k]
• Test sample: age = 18, income = $200k
• Falls into a leaf that contained no similar training samples

Implications:

• The leaf prediction is based on whatever training samples happened to land there
• May be governed by arbitrary split outcomes, not meaningful pattern
• This is another manifestation of poor extrapolation

Understanding leaf predictions becomes even more important when trees are combined into ensembles. The way individual tree predictions combine determines ensemble behavior.

Random Forest Aggregation

In Random Forests, multiple trees vote/average their predictions:

Classification: $$\hat{P}(Y = k | \mathbf{x}) = \frac{1}{T} \sum_{t=1}^{T} \hat{P}_t(Y = k | \mathbf{x})$$

Each tree provides its leaf's probability estimate; these are averaged across trees.

Regression: $$\hat{y} = \frac{1}{T} \sum_{t=1}^{T} \hat{y}_t$$

Each tree provides its leaf's mean prediction; these are averaged.

Effect on prediction quality:

• Averaging reduces variance (central limit theorem effect)
• Each tree can have noisy leaves; average is smoother
• Ensemble probabilities are better calibrated than individual tree probabilities

Gradient Boosting Leaf Values

In Gradient Boosting, leaf predictions are more sophisticated:

Leaf values are not simple averages. They are optimized to minimize the loss function given previous trees' predictions:

$$c_\ell = \arg\min_c \sum_{i \in \ell} L(y_i, F_{m-1}(\mathbf{x}_i) + c)$$

Where $F_{m-1}$ is the ensemble prediction before adding this tree.

For squared loss (regression): $$c_\ell = \frac{1}{n_\ell} \sum_{i \in \ell} (y_i - F_{m-1}(\mathbf{x}_i)) = \text{mean residual}$$

For exponential/logistic loss: Leaf values involve more complex Newton-Raphson steps.

This means gradient boosting trees' leaves predict residuals or gradient directions, not raw targets. The ensemble prediction is the sum of all trees' contributions.

We have thoroughly examined how decision tree leaves generate predictions. Let us consolidate the key insights:

What's next:

With tree structure, splitting rules, and leaf predictions understood, we now turn to the recursive partitioning algorithm that ties these components together. The next page explores how the tree-growing process works—recursively splitting, assigning predictions, and building the complete tree structure.