Decision Trees, Forests, and Boosting

Logistic regression scored access-change request REQ-10234, then converted that score into a human-review decision using asymmetric costs. A tree answers the same routing question with conditional rules: high ambiguity may usually require review, unless evidence for automatic handling under policy P-7 changes the case.

That access-review setting stays with us. Eight historical requests form training data; eight later requests form validation data. That train, validation, and eventual test split matters because a tree can memorize historical exceptions while failing on the next batch.

One access-review table, now with nonlinear rules

Each access-change request has two scaled evidence features:

The fitting example uses these eight historical requests:

Four requests require review and four can be automatic. No single obvious feature perfectly separates them: R3 needs review despite modest ambiguity, while R8 remains safe for automation despite higher ambiguity because the policy evidence is strong.

Impurity measures mixed leaves

A decision tree repeatedly splits rows into leaves. A useful split makes each leaf more uniform in the target.

For a binary leaf with review proportion $p$, Gini impurity is:

$$G = 1 - p^2 - (1-p)^2$$

A pure leaf has $G=0$. A leaf evenly split between classes has $G=0.5$.

An alternative is entropy:

$$H = -p\log_2(p) - (1-p)\log_2(1-p)$$

Both metrics reward purer child leaves. A split's impurity decrease is the parent impurity minus weighted child impurity. When entropy is the impurity metric, this decrease is called information gain. Below we use Gini decrease, or Gini gain, because its arithmetic is compact.

At the root, four of eight rows need review:

$$G_{\text{root}} = 1 - (4/8)^2 - (4/8)^2 = 0.500$$

Suppose the tree tests ambiguity <= 3.35:

• Left leaf: labels [0, 0, 1, 0, 0], so $G_{\text{left}} = 0.320$.
• Right leaf: labels [1, 1, 1], so $G_{\text{right}} = 0.000$.
• Weighted impurity: $(5/8)(0.320) + (3/8)(0.000) = 0.200$.
• Gini gain: $0.500 - 0.200 = 0.300$.

That split is helpful, but it isn't perfect: R3 remains a required-review request inside the mostly automatic leaf.

What are the Gini impurities of a pure binary leaf and a leaf split 50/50 between classes?

Answer

The pure leaf has G = 0; the evenly mixed leaf has G = 0.5. A useful split lowers the weighted child impurity relative to the parent.

A stump tries every midpoint

A decision stump is a tree with one split. For each numeric feature, the stump can place a threshold between adjacent observed values. The training algorithm scores each candidate using impurity decrease and keeps the best one.

Testing midpoints matters. A threshold such as 3.35 represents the boundary between observed values 3.2 and 3.5; it avoids inventing an unnecessary boundary through an actual training row.

The best stump rule is:

$$\texttt{ambiguity} \le 3.35$$

The left leaf predicts review probability $1/5 = 0.20$. The right leaf predicts $3/3 = 1.00$.

The tree produces a score before a decision. A score of 0.20 isn't automatically "safe": the routing threshold must reflect the harm of an automatic permission change that needed review.

Why does a numeric stump test thresholds between adjacent observed values rather than directly on every value?

Answer

A midpoint represents the boundary that separates two neighboring values without inventing a special rule for one training row. Any threshold inside that gap produces the same partition.

Build the stump in NumPy

This implementation searches every feature and midpoint, stores leaf probabilities, then scores the training rows. That's the core mechanic hidden inside a library tree.

The stump misses R3. A deeper tree can create another branch to repair that training mistake, but a repaired training label alone gives no evidence that the extra branch generalizes.

Validation turns a fitted rule into evidence

We now freeze the fitted stump and score later requests that were not used to choose its split:

The operational costs match the classification lesson:

A 0.50 threshold minimizes neither cost nor risk by definition. We compare candidate thresholds on validation data, then would confirm a selected policy on a fresh test period before deployment.

Both thresholds achieve the same F1 score here. They differ sharply in business cost: the lower threshold sends more requests to review but avoids expensive false negatives on this validation batch.

Depth can memorize the exception

A one-split tree is easy to audit but often underfits. An unconstrained tree can isolate every historical row. That becomes overfitting when the tree fits historical rows too specifically and transfers worse to new requests. The right question is whether extra depth improves held-out behavior, not whether it reaches perfect training accuracy.

In this small slice, the deep tree fixes every training mistake and performs worse on validation. Real projects tune constraints such as max_depth, min_samples_leaf, and pruning using validation or cross-validation rather than a single training score.^{[1]Reference 1The Elements of Statistical Learning.https://hastie.su.domains/ElemStatLearn/[2]Reference 2Scikit-learn: Machine Learning in Python.https://jmlr.org/papers/v12/pedregosa11a.html}

Random forests average across perturbed trees

Bagging (bootstrap aggregating) trains many trees in parallel on perturbed views of the training set. A random forest is a bagging ensemble with an extra twist: each tree receives a bootstrap sample of rows and, at each split, considers only a random subset of candidate features. Averaging their class-probability scores reduces the instability of one fully grown tree while preserving nonlinear splits.^{[3]Reference 3Random Forestshttps://doi.org/10.1023/A:1010933404324}

The forest emits more varied scores than the stump. As before, its threshold belongs to the routing policy and must be evaluated with the same costs and fresh evidence.

Boosting adds small corrections

Gradient boosting builds trees sequentially. Each new tree learns a correction to predictions made so far. For squared-error regression, that correction target is the residual $y - \hat{y}$; Friedman generalized the idea to differentiable losses through negative gradients.^{[4]Reference 4Greedy Function Approximation: A Gradient Boosting Machinehttps://projecteuclid.org/journals/annals-of-statistics/volume-29/issue-5/Greedy-Function-Approximation--A-Gradient-Boosting-Machine/10.1214/aos/1013203451.full}

Before returning to binary routing, consider a side task: predict review-handling minutes for three access changes. Their ambiguity values are [1, 2, 5], and actual handling times are [10, 20, 60] minutes.

Shrinkage reduces the impact of any single correction. More rounds can accumulate useful structure, but too many rounds or overly complex trees can still overfit.

What is the structural difference between a random forest and gradient boosting?

Answer

A forest fits perturbed trees independently and averages their scores. Boosting fits trees sequentially, with each new tree correcting errors left by the current ensemble.

Classification boosting on access routing

For needs_review, a classification boosting model uses a classification loss rather than raw minute residuals. The operational comparison remains the same: score the held-out requests, apply a candidate routing threshold, and count costly mistakes.

On this validation slice, boosting ranks review cases better than the stump but still needs a cost-aware threshold. With eight rows, treat that result as a mechanics exercise and a reason to gather more evaluation data, not as a production winner.

Choose how many boosting rounds with validation

Fixed n_estimators=20 is a teaching default, not a deployment choice. Too few rounds underfit; too many fit residual noise. The primary anti-overfit control after tree depth is validation-driven early stopping: score each successive ensemble on held-out data and stop when validation loss stops improving for a patience window. In scikit-learn that is n_iter_no_change (with validation_fraction) or an explicit staged_predict loop you own:

If you implement the loop yourself, call staged_predict_proba (or staged_predict) after a full fit and record validation cost or log loss after every round. Freeze the best round on validation, then open the locked test once.

Costs, class weights, and thresholds

Post-hoc threshold tuning is necessary, but it isn't always enough. Gini and default log-loss treat class errors symmetrically during tree growth. When false negatives cost far more than false positives, you can also:

• pass class_weight to estimators that expose it, such as RandomForestClassifier, or pass per-row sample_weight to fit, such as for GradientBoostingClassifier, so minority / high-harm rows influence splits more during training
• keep a separate validation threshold sweep for the deployed action rule

Weights change how the forest or booster fits, but their API belongs to the specific estimator. The threshold still turns scores into actions under the business cost table. Use both when FN ≫ FP, not threshold alone.

Ensemble scores are not calibrated by default

Leaf frequencies and forest-averaged class fractions are useful ranking scores. They are not automatically honest probabilities. Random forests often improve calibration by averaging many trees; boosted margins frequently need post-hoc calibration (Platt, isotonic, or temperature-style maps) on a reserved split, the same discipline as in the logistic ECE chapter. Treat ensemble predict_proba as a score until a reliability audit says otherwise.

Trees stop at training support

A tree or forest prediction is constant outside the training support of each split. If production ambiguity scores climb past every training value, the leaf still returns the training mean or class rate for that region. That is fine for in-support routing and dangerous for continuous scores at extremes. Monitor feature ranges and don't assume smooth extrapolation the way a linear model might.

MDI favors high-cardinality features

Tree libraries often report mean decrease in impurity (MDI) as their default feature importance metric. MDI calculates the sum of all split gains (in Gini or entropy) for a feature across all trees in the forest. While fast to compute, MDI has a severe limitation: it's heavily biased toward high-cardinality and continuous features.

A high-cardinality feature (e.g. a unique user ID, a high-precision timestamp, or random float noise) offers many unique candidate split points. During tree construction, the greedy split search is highly likely to find some threshold on this feature that coincidentally splits the small training sample well, reducing training impurity. As a result, the forest over-allocates splits to this noise feature, inflating its MDI score.

To diagnose this bias, compare MDI against permutation importance on a held-out validation set. Permutation importance measures the drop in a chosen metric (like F1 score or accuracy) when a single feature's values are shuffled across rows, destroying its predictive power. This controlled check shows a random high-cardinality feature outranking a predictive binary feature under MDI, while held-out permutation importance favors the predictive feature:

Permutation importance asks a held-out question: how much does the chosen metric drop when one feature is shuffled? It's often more useful for validation diagnostics, though correlated features can share or mask importance.^{[5]Reference 5Permutation Feature Importancehttps://scikit-learn.org/stable/modules/permutation_importance.html[6]Reference 6Permutation Importance with Multicollinear or Correlated Featureshttps://scikit-learn.org/stable/auto_examples/inspection/plot_permutation_importance_multicollinear.html}

The wide permutation uncertainty is useful information: eight validation rows are too few for confident claims about which evidence field drives general behavior. Here, scoring="f1" uses the forest's default class predictions. A deployment audit should also define a scorer for documented routing cost at the selected threshold.

A local explanation for a one-feature stump

SHAP (SHapley Additive exPlanations) represents a model prediction as a baseline value plus additive feature contributions.^{[7]Reference 7A Unified Approach to Interpreting Model Predictionshttps://arxiv.org/abs/1705.07874} For our one-feature stump, using the training rows as background, the calculation is exact without any library:

• Baseline review score across the training background: $0.50$.
• Left-leaf score: $0.20$, so ambiguity contributes $-0.30$.
• Right-leaf score: $1.00$, so ambiguity contributes $+0.50$.
• auto_policy_support contributes 0.00 because this stump never split on it.

R3 shows the limit. The explanation faithfully reports why the stump scored the request low; it doesn't prove that low ambiguity made automatic processing correct. Explanations audit model behavior, while labels, policy review, and held-out monitoring audit decision quality.

Trees don't all handle missing values the same way

"Trees handle missing data automatically" is a half-truth that breaks pipelines. What a tree does with a missing feature depends entirely on the library and version:

The trap is assuming the behavior is uniform. Moving a pipeline between estimators or versions can turn native routing into an input error. The reverse trap is quieter: zero_as_missing and sparse-matrix conventions mean a literal 0 and a missing value can be treated identically or differently depending on the tool, which changes splits without any error. Decide your missing-value contract explicitly (impute, encode a missingness flag, or rely on documented native behavior) rather than trusting that "the tree will figure it out."

Choosing a model on later requests

A tree model earns deployment consideration only after the same later-request evaluation used for simpler baselines. Start with a regularized tree or ensemble, compare it against logistic regression under identical splits and costs, and inspect whether the added flexibility repairs meaningful failures.

Trees give transparent conditional splits; forests reduce single-tree instability; boosting accumulates targeted corrections. None of those mechanisms replaces held-out evaluation.

Practice tasks

1. Change R8's target to 1. Recompute the best stump split and explain why policy support may become more useful.
2. Add a third feature, photo_damage_score, and extend fit_stump to consider it. Report whether validation cost improves.
3. Tune max_depth and min_samples_leaf for the forest using only the validation data above. Then write down what separate data you would reserve for an unbiased final check.
4. Modify the false-negative cost from $120 to $40. Recompute threshold choices for stump, forest, and boosting.
5. Implement one more boosting regression round with a smaller learning rate. Compare training MSE after four rounds.