Week 03 · From Local Decisions to Ensembles
Central question. Why can combining unstable trees produce a useful model, and what evidence would justify choosing it over a different classifier?
Scope. Preserve both parts of the week: tree fundamentals from the lecture and ensemble construction/model selection from the tutorial. Apply the Week 02 SVM/kernel self-study in a shared comparison; do not relocate that material to Week 03.
Learning outcomes and prerequisites
- route an observation through a tree and compute a leaf prediction;
- compare weighted split criteria for classification and regression;
- explain greedy growth, pruning, complexity controls and instability;
- distinguish bootstrap/bagging, OOB evaluation, forests and additive boosting;
- calculate one residual/negative-gradient boosting update with shrinkage;
- compare modern boosting tools, including missing/categorical-data handling;
- design cross-validation and hyperparameter searches without leakage or leaderboard overfitting.
Prerequisites: data roles and squared error from Week 01; scores, probabilities, metrics and SVM basics from Week 02. Introduce the expectations/covariances needed for an averaging argument locally. Entropy is introduced as a split criterion here; the wider information-theory account belongs to Week 07.
Companions: trees lecture, ensembles tutorial, Hidden Pairs instructions, and the syllabus. The existing lab baseline is not a separate tutorial notebook.
Notation contract
| Symbol | Meaning and convention |
|---|---|
| \(x_i\in\mathbb R^{d\times1}\), \(y_i\) | One input column and its observed target; binary labels here are 0/1 |
| \(S_R\), \(K\) | Training row indices reaching region \(R\); class count, with classes \(0,\ldots,K-1\) |
| \(R\), \(n_R\), \(p_{R,c}\) | Node region, number of training observations in it, class fraction |
| \((j,s)\); \(R_L,R_R\) | Feature/threshold split and its left/right child regions |
| \(I(R)\) | Declared impurity; compare children using weights \(n_{R_L}/n_R\) and \(n_{R_R}/n_R\) |
| \(q_{R,c}\), \(\widehat c_R\) | Leaf class fraction used as a probability estimate and separate majority decision |
| \(a_R\), \(\bar y_R\) | Regression leaf constant and its training mean under squared error |
| \(N\), \(\mathcal L(T)\) | Total training count and the set of leaf regions of tree \(T\) |
| \(\mathcal R_G(T)\), \(\alpha\) | Whole-tree sample-weighted Gini and penalty per leaf; distinct from \(L_i\) |
| \(T(x)\); \(T_m(x)\), \(M\) | One tree; base tree \(m\) and total number of trees |
| \(\mathcal D\), \(\omega\), \(f_*(x)\), \(\mu(x)\) | Random training sample, fitting randomness, population conditional mean and average fitted regression prediction |
| \(\overline T_M(x)\), \(\sigma_T^2\), \(\rho\) | Averaged tree output, individual prediction variance and common pairwise correlation under stated assumptions |
| \(\mathcal O_i\), \(\mathcal C\) | Trees omitting row \(i\); rows with at least one OOB contributor |
| \(F_m(x)\), \(\eta\) | Additive predictor after \(m\) updates and shrinkage/step size |
| \(r_{mi}\), \(q_m(x)\), \(\pi\) | Pseudo-residual at stage \(m\), binary probability after that stage and training class-one fraction |
| \(L_i\), \(\bar L\) | Per-example loss and explicitly mean-reduced objective |
Single inputs remain columns and observations are rows of \(X\), as in Weeks 01–02. Splits use complete numeric coordinates, \(x_j\leq s\) to go left, and unweighted training observations. The lecture’s split \(\Theta=(j,t_m)\) becomes \((j,s)\); its impurity \(H\) becomes \(I\), reserving \(I_H\) for entropy. Class sums use \(c\) to avoid confusing a class index with observation index \(i\). Logs are natural.
Statistical bias is not the intercept \(b\). Regression boosting predicts a real value; binary classification boosting updates a score/logit, not an unchecked sum of probabilities. A random forest and a boosting sequence use different training and aggregation procedures even when both contain trees.
A sequence of questions partitions the input space
From an apartment price to a local prediction
Suppose we want to predict an apartment’s price from its area, number of rooms and floor. A linear model combines these measurements into one score. A tree instead asks questions such as “is the area at most 60 square metres?” and routes the apartment to another question or a prediction. The trees lecture uses this housing motivation; its illustrative thresholds and prices are not market estimates or fitted results to reuse as evidence.
A decision tree has a root, internal decision nodes and terminal nodes called leaves. Each numeric rule here tests one coordinate against a threshold. A leaf stores a constant prediction. The resulting model is piecewise constant: it can change its prediction across a boundary while remaining constant inside each leaf region. A small tree makes an individual prediction path easy to inspect, although inspecting a path does not establish that the prediction is correct or that the rule is causal.
For a node region \(R\) and split \((j,s)\), define
\[ \begin{aligned} R_L&=\{x\in R:x_j\leq s\},\\ R_R&=\{x\in R:x_j>s\}. \end{aligned} \]
“Left” means the inequality is true. Equality goes left. These sets partition only the current parent region. Thus a descendant’s horizontal cut stops at its parent’s vertical boundary; it does not split the entire plane again. In two dimensions, repeated axis-aligned cuts produce rectangular leaf regions, possibly unbounded outside the displayed plotting window. Different tree variants can use other rules; we study numeric binary CART-style splits here. CART means classification and regression trees.
Freeze a small classification example
To see both the data and every count, use the following synthetic training set. Coordinates are dimensionless. Each ID denotes one observation; every row is training data with equal weight. There is no validation/test partition or performance estimate in this miniature example. Its class-zero pocket is small on purpose: predicting class one everywhere already fits 14 of 16 rows, but misses both class-zero observations.
| ID | \(x_1\) | \(x_2\) | \(y\) |
|---|---|---|---|
| A | 1 | 1 | 0 |
| B | 1 | 2 | 0 |
| C | 1 | 3 | 1 |
| D | 1 | 4 | 1 |
| E | 2 | 1 | 1 |
| F | 2 | 2 | 1 |
| G | 2 | 3 | 1 |
| H | 2 | 4 | 1 |
| I | 3 | 1 | 1 |
| J | 3 | 2 | 1 |
| K | 3 | 3 | 1 |
| L | 3 | 4 | 1 |
| M | 4 | 1 | 1 |
| N | 4 | 2 | 1 |
| O | 4 | 3 | 1 |
| P | 4 | 4 | 1 |
The CSV preserves the same rows. The housing regression motivation and this binary task are separate examples: prices are not class labels.
Consider the fixed tree in Figure 1. At the root, ask \(x_1\leq1.5\). Its right child is already a leaf containing E–P. Its left child contains A–D and asks \(x_2\leq2.5\), separating A–B from C–D. The next section checks why these particular rules reduce the declared training criterion; first read the figure as a prediction procedure.
For U, the first answer is yes, including equality at 1.5. The second is no, because \(3.25>2.5\). The path is \(R\to R_L\to R_{LR}\), whose two training labels are both one. Querying this fitted tree changes neither its thresholds nor its training counts. U has no observed label, so its predicted class one is not a measured correct answer.
What a classification leaf stores
In a nonempty leaf, estimate a class probability by its training fraction: \(q_{R,c}=p_{R,c}\). If a single class is required, choose the majority, \(\widehat c_R=\arg\max_c p_{R,c}\). Here ties choose the smallest class index. The leaves above have counts (2,0), (0,2) and (0,12), so their class-one fractions are 0, 1 and 1. Pure training counts do not establish calibrated probabilities or certainty on new observations; recall Week 02’s confidence counterexample.
Before its second rule, \(R_L\) has counts (2,2). Were it a leaf, it would have \(q_{R_L,1}=0.5\) and class zero under our majority-tie convention. Week 02’s inclusive rule \(q\geq0.5\) would instead choose class one. Those are different decision policies, not different fitted class fractions. Declare which policy produces the reported predictions.
Where does \((1.5,2.5)^\top\) go? What changes for \((1.50001,2.5)^\top\)? Use the inequalities rather than the apparent side of a thick plotted line.
Choose a split by a declared criterion
Count the class mixture before choosing a rule
Let \(S_R=\{i:x_i\in R\}\) index the training observations reaching a node. For \(K\) classes numbered \(0,\ldots,K-1\),
\[ \begin{aligned} n_R&=|S_R|,\\ p_{R,c}&=\frac{1}{n_R}\sum_{i\in S_R}\mathbf1[y_i=c]. \end{aligned} \]
The indicator \(\mathbf1[\cdot]\) is one when its statement is true and zero otherwise. A pure node has one class fraction equal to one. At the root of our binary example, \(p_{R,0}=2/16\) and \(p_{R,1}=14/16\). We use Gini impurity
\[ \begin{aligned} I_G(R)&=\sum_{c=0}^{K-1}p_{R,c}(1-p_{R,c})\\ &=1-\sum_{c=0}^{K-1}p_{R,c}^2. \end{aligned} \]
One interpretation is to draw a label from the node’s empirical class frequencies and independently draw a random guess from the same frequencies. The probability that they differ is \(I_G(R)\). This is an interpretation of the class mixture, not the error rate of a majority predictor. In the binary case, writing \(p=p_{R,1}\) gives \(I_G=2p(1-p)\): zero for a pure node and \(1/2\) for an even mixture. Our root has \(I_G(R)=7/32=0.21875\).
A different criterion is entropy, used locally here as a measure of class mixture:
\[ I_H(R)=-\sum_{c=0}^{K-1}p_{R,c}\log p_{R,c}. \]
Use natural logarithms, so these values are in nats. Define a zero-count term by \(\lim_{p\downarrow0}p\log p=0\). A pure node then has entropy zero; an even binary mixture has entropy \(\log2\). Using another fixed logarithm base rescales all scores by the same positive constant and preserves their ranking. Gini and entropy are different criteria and need not select the same split on every dataset. The broader information-theory account remains a Week 07 reading.
For comparison, a majority leaf correctly labels fraction \(\max_c p_{R,c}\), so its training misclassification rate is
\[ I_E(R)=1-\max_c p_{R,c}. \]
At this root that rate is \(1/8\), not Gini’s \(7/32\). The maximum follows directly from counting correct majority predictions; use this expression when checking the lecture’s summary of criteria. It is not \(1-\min_c p_{R,c}\).
Weight children by how many observations reach them
For a candidate rule \((j,s)\), define its weighted child impurity and reduction:
\[ \begin{aligned} Q_I(R;j,s)&=\frac{n_{R_L}}{n_R}I(R_L)\\ &\quad+\frac{n_{R_R}}{n_R}I(R_R),\\ \Delta I&=I(R)-Q_I(R;j,s). \end{aligned} \]
All candidate rules at this node share the same parent impurity. Minimizing \(Q_I\) is therefore equivalent to maximizing \(\Delta I\). The weights sum to one: the criterion averages impurity over observations, not equally over two children of different sizes. These count weights are not an instruction to reweight the two classes.
For the root rule \(x_1\leq1.5\), the left child has counts (2,2) and impurity \(1/2\); the right child has counts (0,12) and impurity zero. Hence
\[ \begin{aligned} Q_G&=\frac4{16}\frac12+\frac{12}{16}0=\frac18,\\ \Delta I_G&=\frac7{32}-\frac18=\frac3{32}. \end{aligned} \]
Now consider \(x_1\leq2.5\). Its left child has eight observations with counts (2,6), so Gini impurity is \(3/8\); its right child is pure. The weighted score is \((8/16)(3/8)=3/16\), worse than \(1/8\). An unweighted mean would give \(1/4\) for the first rule and \(3/16\) for the second, reversing the preference. The error comes from treating a four-row child as if it represented half the training observations.
Enumerate candidates, rather than guessing an attractive line
With complete numeric features, candidate thresholds can be midpoints of successive distinct values among observations at the active node. Thresholds inside one such gap produce the same training partition. Equal feature values stay together; empty-child splits are excluded. Here each feature has values 1, 2, 3 and 4, so each supplies thresholds 1.5, 2.5 and 3.5.
| Rule | L / R | \(Q_G\) | \(Q_H\) |
|---|---|---|---|
| \(x_1\leq1.5\) | 4 / 12 | 0.12500 | 0.17329 |
| \(x_1\leq2.5\) | 8 / 8 | 0.18750 | 0.28117 |
| \(x_1\leq3.5\) | 12 / 4 | 0.20833 | 0.33792 |
| \(x_2\leq1.5\) | 4 / 12 | 0.20833 | 0.35571 |
| \(x_2\leq2.5\) | 8 / 8 | 0.18750 | 0.28117 |
| \(x_2\leq3.5\) | 12 / 4 | 0.20833 | 0.33792 |
“L / R” lists the left and right child counts \(n_{R_L}\) and \(n_{R_R}\); the slash separates counts, and their sum is 16. \(Q_G\) uses Gini and \(Q_H\) uses entropy in nats. Both select \(x_1\leq1.5\) for this dataset. Our Gini search compares exact scores before rounding; equal scores choose the lower feature index, then the lower threshold. These are the toy’s declared rules, not assumed library defaults.
Inside \(R_L\), all first coordinates equal one, so only \(x_2\) supplies candidate splits. The threshold 2.5 separates A–B from C–D, making both children pure and reducing weighted Gini from \(1/2\) to zero. In contrast, using majority error would give no improvement at the root: predicting class one everywhere makes two errors, while the first split’s tied left leaf also makes two. An unchanged immediate error count can therefore hide a useful change in class mixture. The deeper tree shown above fits all 16 training labels; this is a calculation about training fit, not generalization evidence.
The split ledger records all six root candidates, three left-child candidates, sample IDs, class counts and both impurity calculations. It also records the fixed tree and query path. The handbook’s tree chapter provides further discussion of partitioning and split criteria. The growth section follows the same example through stopping and pruning.
A regression leaf minimizes squared error at its mean
For regression, return to prices rather than reinterpreting the binary labels. Suppose a nonempty leaf contains target values \(y_i\) and predicts one constant \(a\). Under squared error it minimizes
\[ \begin{aligned} \mathrm{SSE}_R(a)&=\sum_{i\in S_R}(y_i-a)^2,\\ \frac{d\mathrm{SSE}_R}{da}&=2\sum_{i\in S_R}(a-y_i)=0,\\ a_R&=\bar y_R=\frac1{n_R}\sum_{i\in S_R}y_i. \end{aligned} \]
The second derivative is \(2n_R>0\), so the mean is the unique minimizer. Summing or averaging squared errors gives the same minimizing constant. Define regression impurity as the mean squared deviation within the node:
\[ I_{\mathrm{MSE}}(R)=\frac1{n_R}\sum_{i\in S_R}(y_i-\bar y_R)^2. \]
This empirical variance uses denominator \(n_R\), not the \(n_R-1\) convention used to estimate a population variance without bias. A split’s weighted child MSE equals the sum of the two children’s squared-error sums divided by the parent count. Comparing unweighted child MSEs would again change the objective.
Take four synthetic prices 4, 6, 8 and 10, expressed in millions of currency units. The leaf mean is 7, its squared-error sum is 20, and its MSE is 5. If a candidate rule groups (4,6) and (8,10), the child means are 5 and 9. Each child has squared-error sum 2 and MSE 1, so weighted child MSE is 1 and the reduction is 4. These squared quantities have squared price units. No real price data, learned housing threshold or validation result is implied. The regression calculation is also saved in the ledger.
A classification leaf summarizes a class distribution; a regression leaf summarizes a numerical target under a chosen loss. Both attach a constant to a region, but their targets, leaf values and fitting criteria must stay distinct.
Greedy growth, pruning and instability
A local decision, repeated recursively
The split calculation chooses a rule at the active node. It compares the children that would result now; it does not search every possible continuation of those children. This is a greedy procedure. A locally best split need not yield the best complete tree under a depth or leaf budget.
For the frozen example, use Gini, maximum depth two and at least two training observations in each leaf. Count the root as depth zero. At each node:
- Stop if its labels are pure or its depth limit has been reached.
- Enumerate thresholds between distinct feature values, retaining only splits whose two children each contain at least the minimum leaf count.
- Choose the smallest weighted child Gini, resolving ties by lower feature index and then lower threshold. Stop if there is no admissible split or no strictly positive local impurity reduction.
- Accept the rule and repeat in its children. Our recorded order is depth first, left before right.
The order names how we process nodes; it is not a claim that all rules on one level are jointly optimized. This ordinary threshold search does not train a tree by gradient descent. Once a rule is accepted during this growth procedure, we keep it while growing below it. Pruning later removes branches rather than reoptimizing all their thresholds.
At \(R\), the best rule remains \(x_1\leq1.5\), giving children of sizes 4 and 12. At \(R_L\), the three second-coordinate thresholds give child sizes 1/3, 2/2 and 3/1. Only 2.5 meets our minimum leaf count of two. Its children A–B and C–D are pure. We visit and stop at \(R_{LL}\) and \(R_{LR}\), then visit the already pure \(R_R\). There are three leaves, although depth two could accommodate up to four. Stopping at pure nodes avoids unnecessary splits in this example.
Watch regions and rules grow together
Figure 2 replays 12 recorded events in 32 seconds. The points and axes stay fixed; a region changes only when its corresponding rule is accepted. Dashed lines are candidates, not extra boundaries in the fitted tree. The root comparison displays three representative candidates; the full ledger retains all six. The left-child comparison displays all three, marking the two size-inadmissible choices. Play or pause with native controls; the video has no audio or autoplay.
The sequence starts with one leaf, compares and accepts the root rule, then compares and accepts the left-child rule. It explicitly stops at the three pure leaves and finishes by tracing \(U=(1.5,3.25)^\top\) through the fixed tree. Candidate comparison does not change predictions; acceptance does. Querying changes neither the rules nor training counts. The frames hold discrete states, with no interpolated thresholds or invented intermediate trees.
The key accepted states are also available without motion in Figure 3. The full event ledger records node IDs, row IDs, counts, proportions, candidate eligibility, chosen rules, stops and exact playback timing.
Let \(N=16\) be the total training count and let \(\mathcal L(T)\) be the leaves of tree \(T\). Define a whole-tree training risk by
\[ \mathcal R_G(T)=\sum_{R'\in\mathcal L(T)}\frac{n_{R'}}{N}I_G(R'). \]
Each \(R'\) is a leaf region. A split at node \(R\) changes this risk by \((n_R/N)\Delta I_G\). Thus the root split reduces risk by \(3/32\), while splitting its four-row left child reduces risk by \((4/16)(1/2)=1/8\). The risk values are \(7/32\), \(1/8\), then zero. Training classification errors are two, two, then zero: a lower Gini score and fewer mistakes are different statements. Neither sequence supplies validation or test evidence.
Stop growth before fitting every detail
Depth, leaf count, minimum leaf size and required impurity reduction restrict which trees can be grown. A depth limit bounds the number of questions on a path. A minimum leaf count rejects a candidate that would make either child too small; it can change which split is selected, not just when growth stops. A minimum improvement rule rejects gains too small under its declared normalization. Our illustration requires a strictly positive local Gini gain; software thresholds should be read with their own normalization.
With the same rows and tie rules, reducing the maximum depth to one leaves the two-leaf stump. Keeping depth two but raising the minimum leaf count to three also leaves that stump: its four-row left child cannot be divided into two children of at least three. It keeps fractions \(0.5\) and \(1\) in its two leaves, with two training errors. These are verified effects of the stated constraints, not recommendations for a real dataset.
More leaves can fit small pockets, accidental label errors and sample-specific patterns. Pure training leaves can still make mistakes on new data. Conversely, a small leaf is not automatically noise: A–B are the entire minority class in this toy. Choose complexity using validation or appropriately constructed cross-validation, considering the task’s metric and data dependence. The training table alone cannot tell us which complexity will generalize.
At \(R_L\), why does minimum leaf size three block every split even though its labels are mixed? Why does a pure 12-row node stop under our rules even though many numerical thresholds remain available?
Prune a grown tree with a declared cost
Pre-pruning imposes restrictions during growth. Post-pruning starts from a grown tree and replaces selected branches by leaves. Removing a branch merges its descendant regions and recomputes the constant prediction from all training rows reaching that node. It does not discard those observations.
For this classification example, define the cost-complexity objective
\[ \begin{aligned} J_\alpha(T)&=\mathcal R_G(T)+\alpha|\mathcal L(T)|,\\ \alpha&\geq0. \end{aligned} \]
The first term is sample-weighted Gini, normalized by the same total \(N\) for every candidate subtree. The second charges \(\alpha\) for each leaf. Do not substitute misclassification error or an unnormalized impurity sum without changing the interpretation and numerical scale of \(\alpha\). The official pruning guide uses the weighted-impurity version of this trade-off; other presentations may use a different risk.
There are exactly three subtrees obtainable by pruning our grown tree:
| Candidate | Leaves | \(\mathcal R_G\) | \(J_\alpha\) |
|---|---|---|---|
| Full tree | 3 | \(0\) | \(3\alpha\) |
| Root split only | 2 | \(1/8\) | \(1/8+2\alpha\) |
| One root leaf | 1 | \(7/32\) | \(7/32+\alpha\) |
The full tree and the single leaf have equal cost at \(\alpha=7/64\). The two-leaf stump is never a minimizer: to beat the full tree it would need \(\alpha\geq1/8\), while to beat the single leaf it would need \(\alpha\leq3/32\). Those intervals do not overlap. If equal costs prefer fewer leaves, the selected subtree has three leaves below \(7/64\) and one leaf at or above it. For example, at \(\alpha=1/8\), the costs are \(3/8\), \(3/8\) and \(11/32\); the single leaf has the smallest cost. It predicts class one for every input and misses A–B in training.
This exact enumeration makes pruning distinct from the animation’s forward growth. A depth-one growth restriction gives a stump that this pruning objective never selects, so pre-pruning and post-pruning need not coincide. The calculation ranks subtrees of this grown tree; it is not a global search over every tree structure. Nor does it select a useful \(\alpha\) for new data: validation must compare the resulting alternatives. We report no validation result or final test performance for the toy.
A small data change can move a boundary
Keep every coordinate, the depth/leaf limits and tie rules fixed. In a separate sensitivity experiment, change only E’s training label from one to zero. This is a hypothetical data perturbation, not a recommendation to relabel an observation to improve a model.
The best root threshold moves from 1.5 to 2.5. In the perturbed table, \(x_1\leq2.5\) and \(x_2\leq2.5\) tie at weighted Gini \(15/64\); our lower-feature rule chooses \(x_1\). The left child again splits on \(x_2\leq2.5\), expanding the class-zero prediction region. Observation F at \((2,2)^\top\) keeps its class-one label but its prediction changes from one to zero.
Greedy choices can change when a candidate ranking or tie changes, affecting predictions for observations other than the changed row. This example shows that sensitivity can occur; it does not estimate a typical frequency or prove that every tree is unstable. Averaging differently fitted trees can reduce some prediction variability when their errors are not too similar. The next section examines the assumptions needed for that argument.
Averaging needs diversity
The changed label in the previous example moved a boundary for other rows. Suppose we could collect another training sample from the same population and fit again. Would the prediction at a fixed input move? This question concerns prediction variance across fits. It differs from the spread of target values inside a leaf and from the error measured on one fixed test set.
An ensemble combines several fitted predictors. Averaging can soften the effect of sample-specific decisions, but repeated copies of the same prediction add nothing. We need to know both how much predictions vary and how much of that variation they share.
Separate systematic error, fit variation and fresh noise
For this derivation only, consider regression at a fixed input \(x\). Let \(f_*(x)=\mathbb E[Y\mid x]\) be the population conditional mean and write a new target as \(Y=f_*(x)+\epsilon\). Assume finite second moments, \(\mathbb E[\epsilon\mid x]=0\), and fresh noise independent of the training sample and fitting randomness at this input. Its variance is \(\sigma_\epsilon^2(x)\); a Gaussian assumption is unnecessary.
Let \(\mathcal D\) denote a random training sample, \(\omega\) the fitting randomness, and \(\widehat f(x;\mathcal D,\omega)\) the resulting prediction. Its average across those fits is \(\mu(x)=\mathbb E_{\mathcal D,\omega}[\widehat f(x;\mathcal D,\omega)]\). Subtract and add this mean:
\[ Y-\widehat f =\epsilon+\bigl(f_*-\mu\bigr)+\bigl(\mu-\widehat f\bigr). \]
Squaring and averaging leaves three terms. The centered fit fluctuation and noise have zero means; their cross term vanishes under the stated independence. Thus, with all functions evaluated at this fixed \(x\) and the expectation over training samples, fitting randomness and fresh noise,
\[ \begin{aligned} \mathbb E[(Y-\widehat f)^2] &=\underbrace{(\mu-f_*)^2}_{\text{squared bias}}\\ &\quad+\underbrace{\mathbb E[(\widehat f-\mu)^2]}_{\text{prediction variance}}\\ &\quad+\underbrace{\sigma_\epsilon^2(x)}_{\text{fresh noise}}. \end{aligned} \]
A numerical check. Suppose \(f_*(x)=1\), equally likely fits predict 1 or 3, and independent fresh noise is equally likely to be \(-1\) or \(+1\). The mean fit is 2, squared bias is 1, prediction variance is 1 and noise variance is 1. Enumerating the four equally likely fit/noise combinations gives mean squared error 3. None of these expectations is an average over the rows of a single training set. The generator checks the enumeration exactly.
Statistical bias here is a systematic prediction error, not an intercept. This is a squared-error decomposition; it does not decompose classification accuracy into the same three quantities. Nor does it prove that increasing model complexity always reduces bias or that bagging preserves the bias of a tree trained on the original sample.
Covariance determines how much averaging helps
For an ensemble at a fixed \(x\), write \(Z_m=T_m(x)\) and \(\overline T_M(x)=M^{-1}\sum_{m=1}^M Z_m\). Here the \(Z_m\) are real-valued regression predictions, or one specified class’s probability estimates. All variances and covariances below refer to a common experiment that redraws the training sample and fitting randomness. By expanding the square of a sum,
\[ \begin{aligned} \operatorname{Var}(\overline T_M) &=\frac{1}{M^2}\sum_{m=1}^M\operatorname{Var}(Z_m)\\ &\quad+\frac{2}{M^2}\sum_{m<k}\operatorname{Cov}(Z_m,Z_k). \end{aligned} \]
For a transparent special case, assume every \(Z_m\) has variance \(\sigma_T^2>0\) and every distinct pair has correlation \(\rho\). There are \(M(M-1)/2\) pairs, each with covariance \(\rho\sigma_T^2\), so
\[ \operatorname{Var}(\overline T_M) =\sigma_T^2\left[\rho+\frac{1-\rho}{M}\right]. \]
With \(M=10\), the variance relative to one tree is \(0.1\) when \(\rho=0\), \(0.325\) when \(\rho=0.25\), and \(0.775\) when \(\rho=0.75\). At \(\rho=1\), all the variance remains. The plot holds the individual variance and correlation fixed as \(M\) grows; it is an algebraic illustration, not a measured forest learning curve.
If all trees have the same expected prediction \(\mu(x)\), linearity of expectation gives \(\mathbb E[\overline T_M(x)]=\mu(x)\): averaging does not remove their common bias. Bootstrapping can change the distribution of a fitted tree, so this statement compares an average with its own constituent predictors, not automatically with one original-sample tree.
Why separate fits can still be correlated. Independent bootstrap draws and random seeds can make trees independent conditional on a fixed training sample. Across new training samples they still share the same underlying sample. For identically constructed trees, their common conditional mean can vary with \(\mathcal D\), creating covariance across fits. Distinct random seeds therefore do not establish \(\rho=0\) in the formula above.
If the trees are strongly correlated, would ten times as many trees necessarily give ten times less variance? Use the covariance term, rather than the number of model files, to explain your prediction.
Bootstrap, out-of-bag evaluation and random forests
Resample row identities, retaining their targets
We usually have one training sample, not a supply of independent datasets. A bootstrap sample draws \(N\) row indices independently and uniformly with replacement from those \(N\) training rows. Each chosen input and target stay together. A row may appear several times, while another is absent. The sample has \(N\) draws, not necessarily \(N\) distinct observations. Repetitions contribute to the fitted counts, leaf means and split costs; silently deduplicating them changes the procedure.
Bagging, or bootstrap aggregating, fits a base model on each bootstrap sample and combines the predictions. No tree is trained to correct the previous tree’s residuals. The fits can be computed separately; shared original data still matter for their statistical dependence.
To make every repetition and omission visible, use a separate, synthetic one-feature regression dataset. These rows are not relabelled versions of the earlier sixteen-point classification example.
| Row | \(r_1\) | \(r_2\) | \(r_3\) | \(r_4\) | \(r_5\) | \(r_6\) |
|---|---|---|---|---|---|---|
| \(x_1\) | 1 | 2 | 3 | 4 | 5 | 6 |
| \(y\) | 0 | 0 | 2 | 2 | 4 | 4 |
The following three possible ordered bootstrap draws are fixed for inspection, not selected as evidence of typical performance. Fit a regression stump to each: root depth zero, maximum depth one, at least two draws per child, minimum total squared error over distinct-value midpoints, lower-threshold ties, and \(\leq\) routing left. Leaf predictions are means including repeats.
| Tree | Six drawn row indices | Fitted rule | Left mean | Right mean |
|---|---|---|---|---|
| \(T_1\) | 1, 1, 2, 4, 5, 6 | \(x_1\leq3\) | \(0\) | \(10/3\) |
| \(T_2\) | 1, 2, 3, 3, 6, 6 | \(x_1\leq2.5\) | \(0\) | \(3\) |
| \(T_3\) | 2, 2, 4, 5, 6, 6 | \(x_1\leq4.5\) | \(2/3\) | \(4\) |
For example, \(T_1\) puts targets \(0,0,0\) on the left and \(2,4,4\) on the right. The exported ledger enumerates every admissible threshold and checks the selected minimum. These are fitted stumps, not invented prediction values.
Why about 37 percent are omitted
A particular row has probability \(1-1/N\) of being missed on one draw. Missing it on all \(N\) independent draws has probability
\[ \begin{aligned} P(\text{row }i\text{ omitted}) &=\left(1-\frac1N\right)^N\\ &\longrightarrow e^{-1}\approx0.368. \end{aligned} \]
Linearity of expectation gives expected omitted count \(N(1-1/N)^N\) and expected distinct included count \(N[1-(1-1/N)^N]\). The omission events for different rows need not be independent for this count identity. With \(N=6\), omission probability is \((5/6)^6\approx0.335\), and the expected number of distinct included rows is about \(3.99\). Neither 37 percent nor this expected count is a requirement for every realized draw. Changing the number of draws from \(N\) to \(B\) changes the omission probability to \((1-1/N)^B\).
Build an OOB prediction for each observation first
For training row \(i\), define \(\mathcal O_i\) as the set of tree indices whose bootstrap samples omit that row entirely. When \(|\mathcal O_i|>0\), its regression out-of-bag (OOB) prediction is
\[ \widehat y_i^{\mathrm{OOB}} =\frac{1}{|\mathcal O_i|}\sum_{m\in\mathcal O_i}T_m(x_i). \]
The eligible set changes with \(i\). For \(r_3\), only Trees 1 and 3 qualify; Tree 2 saw \(r_3\) twice. The valid predictions are 0 and \(2/3\), giving \(\widehat y_3^{\mathrm{OOB}}=1/3\). The observed target is 2, so its squared error is \((2-1/3)^2=25/9\). Adding Tree 2’s prediction would violate OOB eligibility, even though it is part of the ensemble.
| Row | Eligible trees | OOB prediction | Squared error |
|---|---|---|---|
| \(r_1\) | 3 | \(2/3\) | \(4/9\) |
| \(r_2\) | none | undefined | not scored |
| \(r_3\) | 1, 3 | \(1/3\) | \(25/9\) |
| \(r_4\) | 2 | \(3\) | \(1\) |
| \(r_5\) | 2 | \(3\) | \(1\) |
| \(r_6\) | none | undefined | not scored |
Let \(\mathcal C=\{i:|\mathcal O_i|>0\}\) be the covered rows. The illustrative OOB MSE is
\[ \frac{1}{|\mathcal C|}\sum_{i\in\mathcal C} (y_i-\widehat y_i^{\mathrm{OOB}})^2 =\frac{47}{36}\approx1.306. \]
Coverage is \(|\mathcal C|/N=4/6\). Three trees leave two observations without a valid prediction. Do not replace undefined predictions with zero or quietly report a full-coverage score. Report coverage and contributor counts; more bootstrap trees usually improve coverage. With independent draws across trees, the probability that a fixed row gets no OOB contributor among \(M\) trees is \([1-(1-1/N)^N]^M\).
Averaging each tree’s own OOB MSE instead gives \(55/27\approx2.037\) here. It evaluates a different quantity: trees have different OOB sets, and a loss of averaged predictions is not an average of prediction losses. For a new external input, the bagged predictor uses all trees; the OOB construction withholds different trees to assess training observations they did not see.
OOB is useful internal evidence under an appropriate sampling scheme, not a final untouched test set. Selecting many settings against OOB scores also selects against those observations. Ordinary row bootstrapping does not protect against related patients, repeated subjects or temporal leakage. Preprocessing that learns from all rows can also let an OOB row influence its predictors: fit learned transformations within each resample, or use a properly nested validation pipeline. Keep the final evaluation protocol aligned with the population and dependence structure of interest.
Specify what the ensemble combines
Regression averages real-valued outputs. Classification requires a separate choice of aggregation:
- Hard voting: each tree chooses a class; select the class with most votes.
- Probability averaging: average each class’s leaf probability estimate, \(\overline q_c(x)=M^{-1}\sum_m q_{m,c}(x)\), then choose the class with largest average. Here \(q_{m,c}(x)\) is the class fraction in the leaf reached in tree \(m\).
Use the same eligible-tree restriction for OOB classification probabilities or votes. Declare class ties; this chapter keeps the smallest-class convention from the tree example. Averaging valid probability vectors preserves a sum of one but does not establish calibration.
The two decisions can differ. Binary class-one probabilities \(0.49,0.49,1\) give hard votes \(0,0,1\), selecting class zero. Their mean probability is \(0.66\), selecting class one. The scikit-learn forest guide specifies probability averaging for its classifier; that implementation choice should not be silently substituted for the tutorial’s majority-vote example.
Random forests change the split candidates
If one feature repeatedly offers the best split, bootstrap trees can still look similar. A standard random-forest construction adds another random choice: at each decision node, draw a subset of candidate features, then search for the best valid split among them. The subset can change at the next node. It is different from drawing one feature subset once and restricting an entire tree to it.
Return briefly to the sixteen original classification rows. Searching both features gives root rule \(x_1\leq1.5\) with weighted Gini \(1/8\). If that node’s candidate subset contains only \(x_2\), its best rule is \(x_2\leq2.5\) with weighted Gini \(3/16\). Random feature restriction can therefore force a locally worse split. Its purpose is to make fitted trees less alike; any reduction in shared variation must be weighed against weaker individual predictions. This exact root comparison is not an empirical claim that the resulting forest performs better. The forest guide describes resampling rows and selecting features at splits as distinct sources of randomness.
For a bootstrap forest, the construction can be read as four steps:
- Draw a bootstrap sample of paired training rows for each tree.
- At each eligible node, draw candidate features and choose a valid split using the declared criterion and stopping rules.
- Store leaf outputs and combine tree predictions using the declared rule.
- When computing OOB predictions, include only trees omitting the row being predicted, and report coverage before scoring.
The feature-subset size is a modeling choice, not a universal fraction of \(d\). Depth and leaf size control individual trees; the number of trees controls averaging stability, storage and prediction cost. More trees do not restore omitted signal, remove a common bias or guarantee better held-out accuracy.
What would justify choosing a forest?
A training fit and the toy OOB arithmetic above do not establish superiority over a single tree. A defensible comparison uses the same held-out folds and metric for both models, fits any learned preprocessing within training folds, and gives each method a declared validation search over complexity controls. Use group- or time-aware splits when needed. Compare held-out predictions, variation across appropriate folds, and fitting/prediction cost; use OOB as an additional forest diagnostic rather than comparing its OOB score directly with a single tree’s training score. After settings are frozen, an untouched test set provides a separate final assessment. The later model-selection section will develop that protocol alongside the Week 02 SVM baseline.
Which source of randomness changes row multiplicities, and which changes the features available to a node? For one training observation, which of the resulting trees may enter its OOB prediction?
Boosting learns corrections
Bagging asks several models for predictions and averages their answers. Boosting instead builds a sequence: each new tree depends on the current ensemble and supplies a correction. A small tree can make a useful change even when it would be a poor predictor of the original targets on its own. The ensembles tutorial develops this transition from separately fitted trees to successive corrections.
Start with the best constant, then ask what remains
For regression, use per-example half-squared loss and its mean:
\[ \begin{aligned} L_i(F)&=\frac12\bigl(y_i-F(x_i)\bigr)^2,\\ \bar L(F)&=\frac1N\sum_i L_i(F). \end{aligned} \]
The best constant under this objective is the training mean: \(F_0(x)=\bar y\). At stage \(m\), compute the residual using the current prediction,
\[ r_{mi}=y_i-F_{m-1}(x_i). \]
Fit a small regression tree \(T_m\) to pairs \((x_i,r_{mi})\), minimizing squared error to those residuals using the declared tree constraints. A leaf therefore stores the mean residual of its training rows. Add a scaled correction:
\[ F_m(x)=F_{m-1}(x)+\eta T_m(x). \]
Here \(\eta>0\) is shrinkage. Our worked algorithm uses a fixed \(\eta\) and the fitted residual means directly, with no additional line search or leaf-value refit. The initial constant and all previous trees stay fixed as the next tree is added. This is stage-wise fitting. The new tree learns a function of \(x\), so its correction is available for unseen inputs, not only for the rows whose residuals we calculated.
One complete correction on six rows
Reuse W03-C’s synthetic regression table, now fitting all six rows rather than bootstrap samples: \(x_1=1,\ldots,6\) and \(y=(0,0,2,2,4,4)\). Keep depth one, at least two rows per leaf, squared-error split selection over adjacent-value midpoints, lower-threshold ties and \(\leq\) routing left. Set \(\eta=0.4\). These are instructional settings, not recommended hyperparameters.
The initial mean is \(F_0=2\), so the first residual vector is \((-2,-2,0,0,2,2)\). Only thresholds 2.5, 3.5 and 4.5 meet the leaf-size rule. The squared errors for fitting these residuals are 4, \(16/3\) and 4, respectively. The tie convention selects \(x_1\leq2.5\). Its residual means are \(-2\) on the left and 1 on the right. Consequently the added correction is \(-0.8\) or \(+0.4\), not the whole fitted tree.
| \(x_1\) | \(y\) | \(F_0\) | \(r_{1i}=y-F_0\) |
|---|---|---|---|
| 1 | 0 | 2 | −2 |
| 2 | 0 | 2 | −2 |
| 3 | 2 | 2 | 0 |
| 4 | 2 | 2 | 0 |
| 5 | 4 | 2 | 2 |
| 6 | 4 | 2 | 2 |
Use those residuals as the tree’s fitting targets, then update the predictor:
| \(x_1\) | \(T_1(x_i)\) | \(0.4T_1(x_i)\) | \(F_1(x_i)\) |
|---|---|---|---|
| 1 | −2 | −0.8 | 1.2 |
| 2 | −2 | −0.8 | 1.2 |
| 3 | 1 | 0.4 | 2.4 |
| 4 | 1 | 0.4 | 2.4 |
| 5 | 1 | 0.4 | 2.4 |
| 6 | 1 | 0.4 | 2.4 |
Rows 3 and 4 had zero residual but move upward because they share a correction leaf with rows 5 and 6. The tree approximates the residual vector with a piecewise constant function; it cannot choose six arbitrary independent updates. What matters for fitting is the total objective, not that every row improves on every step.
The training MSE decreases from \(8/3\approx2.667\) to \(104/75\approx1.387\). Our declared mean half-squared objective is half the MSE: it decreases from \(4/3\) to \(52/75\). Changing this reporting scale does not change the minimizing prediction, but it does change derivative factors.
At the next stage, recompute \(r_{2i}=y_i-F_1(x_i)\): \((-1.2,-1.2,-0.4,-0.4,1.6,1.6)\). Reusing the first residuals would repeatedly fit an outdated correction. The exact generator records three stages:
| Stage | Selected threshold | Training MSE after update |
|---|---|---|
| Initial constant | none | \(8/3\approx2.667\) |
| 1 | 2.5 | \(104/75\approx1.387\) |
| 2 | 4.5 | \(1064/1875\approx0.567\) |
| 3 | 4.5 | \(12776/46875\approx0.273\) |
With constant shrinkage, the accumulated prediction is \(F_M(x)=F_0(x)+\eta\sum_{m=1}^M T_m(x)\). This is a sum of corrections, not a mean of trees trained independently on \(y\).
Why residual fitting is a gradient step in prediction space
For a differentiable per-example loss, define the pseudo-residual
\[ r_{mi}=-\left. \frac{\partial L_i(F)}{\partial F(x_i)} \right|_{F=F_{m-1}}. \]
For half-squared loss the derivative is \(F(x_i)-y_i\), so the negative derivative is exactly the ordinary residual. Under full per-example squared error it is \(2(y_i-F(x_i))\); under mean squared error, the negative derivative with respect to each prediction is \(2(y_i-F(x_i))/N\). For our mean half-squared objective it is \(r_{mi}/N\). The common positive factor changes the step scale. We use per-example derivatives to define pseudo-residual targets and state the mean reduction separately, avoiding a hidden factor in \(\eta\).
Imagine the vector of current predictions on all training inputs. Its negative gradient gives a desired change at each coordinate. A restricted regression tree approximates that direction by fitting the pseudo-residuals. It also extends the correction to inputs outside the training table. This is the useful sense of functional gradient descent; the split thresholds are still selected by greedy tree search, not differentiated through.
For half-squared loss and residual-mean leaves, the fitted tree satisfies \(\sum_i r_{mi}T_m(x_i)=\sum_i T_m(x_i)^2\). Expanding the new squared error gives
\[ \begin{aligned} &\mathrm{MSE}(F_{m-1})-\mathrm{MSE}(F_m)\\ &\qquad=\eta(2-\eta)\,\frac1N\sum_i T_m(x_i)^2. \end{aligned} \]
Thus this particular update reduces training MSE for \(0<\eta<2\) when the correction is nonzero. The generator checks the identity at every displayed stage. This conclusion depends on the loss and fitted leaf means; it is not a general guarantee for arbitrary loss functions, approximate updates or unseen examples.
Some boosting algorithms first select regions from pseudo-residuals, then optimize leaf values against the original loss, or use a Newton approximation with second derivatives. An additional line search may choose a multiplier. Those are distinct choices; our example makes none of them silently. The official boosting formulation is a useful implementation companion for this distinction.
Binary boosting adds logits, then computes probabilities
Return to Week 02’s score/probability distinction. Let \(F(x)\) be a binary logit, and write \(q(x)=\sigma(F(x))\) for the class-one probability estimate. With labels \(y_i\in\{0,1\}\),
\[ q(x)=\frac{1}{1+\exp(-F(x))}. \]
BCE written as a function of the score is
\[ \begin{aligned} L_i(F)&=\log(1+\exp(F(x_i)))\\ &\quad-y_iF(x_i). \end{aligned} \]
The stable numerical form is \(\max(F,0)+\log(1+\exp(-|F|))-y_iF\), evaluated separately per row. Differentiate with respect to the logit, not the probability:
\[ \begin{aligned} \frac{\partial L_i}{\partial F(x_i)}&=q(x_i)-y_i,\\ r_{mi}&=y_i-q_{m-1}(x_i). \end{aligned} \]
A positive pseudo-residual asks for a higher logit; a negative one asks for a lower logit. Fit a regression tree to these real-valued pseudo-residuals and add its output to \(F\). It is a regression tree inside a classifier; it need not output a class or a probability.
For initial class-one fraction \(\pi\in(0,1)\), the best constant logit under BCE satisfies \(\sigma(F_0)=\pi\), giving
\[ F_0=\log\frac{\pi}{1-\pi}. \]
A one-class training sample has no finite unregularized constant optimum. Handle that case explicitly through an appropriate constant-class model or a declared smoothing/regularization choice; do not evaluate an infinite logit or silently clip it and call it the same solution.
A binary step with every quantity named
Use a separate synthetic binary table on the same six coordinates, with \(y=(0,0,1,0,1,1)\). These are new targets, not the earlier regression values. Here \(\pi=1/2\), so \(F_0=0\) and every initial probability is \(1/2\). Pseudo-residuals are \((-1/2,-1/2,1/2,-1/2,1/2,1/2)\).
Keep the same stump constraints and \(\eta=0.4\). Fitting these pseudo-residuals selects threshold 2.5 (tied with 4.5, resolved downward). The left mean is \(-1/2\) and right mean \(1/4\). Our explicitly first-order update gives:
| Rows | \(T_1\) | Logit \(F_1\) | Probability \(q_1\) |
|---|---|---|---|
| 1, 2 | \(-0.5\) | \(-0.2\) | \(0.450166\) |
| 3–6 | \(0.25\) | \(0.1\) | \(0.524979\) |
Mean training BCE decreases from \(0.693147\) to \(0.645644\). These are probabilities after applying sigmoid to the updated logits. Adding \(0.4T_1\) directly to the old probabilities would produce \(0.3\) and \(0.6\), which are different values and are not this update. Further unchecked additions to probabilities could even leave \([0,1]\).
Class decisions are another step. This chapter retains the smallest-class tie convention, so class one requires \(q>1/2\) here. Week 02’s threshold examples used \(q\geq\tau\); at exactly \(\tau=1/2\) that convention decides differently. After this update no row has probability exactly \(1/2\). A threshold change would change decisions without changing the fitted logits or BCE.
The displayed step uses pseudo-residual means as leaf outputs. It is not a numerical reproduction of a library’s GradientBoostingClassifier, which may refine those values. For example, a Newton leaf correction at the initial state uses the sum of \(y_i-q_i\) divided by the sum of \(q_i(1-q_i)\), giving \(-2\) and \(1\) in these same regions before shrinkage, rather than \(-1/2\) and \(1/4\). State the algorithm before comparing its numbers.
Shrinkage controls each addition; validation controls the fit
A smaller \(\eta\) makes each correction less influential and often requires more stages to reach a comparable training fit. It does not by itself make an arbitrary noisy direction useful. Tree depth/leaf size, stage count and shrinkage interact; choose them using validation evidence. Early stopping monitors an appropriate validation objective with a declared stopping rule, then preserves the best accepted stage rather than waiting for training loss to stop decreasing. The test set must not choose that stage.
Boosting can alter both bias and variance. The slogan “bagging reduces variance, boosting reduces bias” is a motivation, not a complete guarantee. Both methods can fail under leakage, distribution shift, weak features or unsuitable complexity. Declining training MSE/BCE in our tables establishes only that these particular updates improved their declared training objectives.
If a positive example has a low predicted probability, what is the sign of \(y-q\)? Which quantity must change before you recompute its probability? For regression, why must the next residual use \(F_1\) rather than \(F_0\)?
Modern boosting tools and honest model selection
A library can fit a sophisticated ensemble while the experiment still answers the wrong question. Before choosing a package, specify what an observation is, what information will be available at prediction time, and what result would count as useful on new data. The learning algorithm, preprocessing and selection procedure together determine the model we are evaluating.
XGBoost, LightGBM and CatBoost
These packages implement boosted trees with different engineering and modeling choices. They are not three new loss functions, nor are their fitted numbers required to match our first-order examples. Use the following as a guide to questions to ask, not a ranking of speed or accuracy.
| Library | Construction to recognize |
|---|---|
| XGBoost | Tree boosting with an explicit regularized objective and gradient/curvature information for updates. See its boosted-tree derivation. |
| LightGBM | Histogram split search and leaf-wise growth, extending the leaf with the largest gain. A depth bound does not turn it into level-wise growth. See algorithm features. |
| CatBoost | Boosting with integrated categorical transformations, including statistics computed in permutation order, and one-hot handling in specified cases. See categorical transformations. |
“Supports missing or categorical data” is incomplete without the input contract:
| Library | Missing values and categorical inputs |
|---|---|
| XGBoost | The tree booster learns missing-value branch directions (FAQ). Native categories require declared categorical types and an enabled, supported tree method; the Python tutorial uses category columns, enable_categorical=True and hist. Preserve categorical information in model serialization (guide). |
| LightGBM | Numerical missing-value handling is available; zero is not automatically synonymous with missing. Declare categorical features; integer codes must follow the documented encoding contract, including treatment of negative codes (advanced topics). |
| CatBoost | Numerical missing values use a declared missing-value mode (guide). Categorical columns must be identified, and missing categories need a consistent representation such as an explicit string token; float/NaN categorical inputs are not interchangeable with numeric NaNs (FAQ). |
Integer category codes are identifiers, not necessarily ordered measurements. Passing them as ordinary numeric features can accidentally impose an ordering. For any package, keep category meanings consistent between training and prediction. A new category, an absent measurement and a recorded zero are three different events; decide their representations explicitly. Native handling also does not prevent target leakage or a change in data collection.
| Library | Controls to inspect; practical limit |
|---|---|
| XGBoost | Shrinkage, boosting rounds, depth, child constraints and leaf penalties; parameter meaning depends on the booster and tree method (parameters). |
| LightGBM | num_leaves, min_data_in_leaf, depth, learning rate and rounds; leaf-wise growth needs complexity control, especially on small samples (tuning). |
| CatBoost | Depth, learning rate, iterations and leaf regularization; CPU/GPU and growth-policy options have documented restrictions (parameters). |
These references were checked on 22 October 2026. The served documentation identified XGBoost 3.4.2 and LightGBM 4.7.0; CatBoost’s online manual is unversioned, with release 1.2.10 recorded alongside this source check. This is a documentation snapshot, not an execution test of those three releases. Record installed versions and the chosen API/backend when reproducing an experiment. No package is universally fastest, most accurate or free of preprocessing decisions.
Cross-validation evaluates a fitting procedure
A hyperparameter is a choice such as tree depth, shrinkage or SVM \(C\) that we select outside the ordinary parameter-fitting step. A held-out validation score can guide that choice. If data are limited, cross-validation reuses the development sample in several train/validation partitions: fit on the training portion of each fold, predict its held-out portion, and summarize a declared metric across folds.
The held-out fold must remain outside every learned step of its predictor. For a numeric SVM, the sequence is training-fitted imputation if needed, training-fitted scaling, then fitting the SVM. For categories, learn encoding vocabularies within training folds and declare unknown-category behavior. Target-based encodings need particular care: a training row’s transformed value must not simply reveal its own label; use an appropriate cross-fitting or ordered scheme within the training portion as well.
Fitting a scaler once on the whole development sample before CV lets held-out rows influence fitted statistics. Feature selection, learned dimensionality reduction and target encodings can leak more directly. A pipeline makes the fitting boundary explicit: clone and fit the whole chain separately inside each fold, then apply it to that fold’s held-out rows. The official pitfalls guide explains why splitting before learned preprocessing matters.
Choose the split to match the prediction question. Stratified folds can help preserve class proportions for approximately independent binary observations. They do not make repeated patients, related records or successive time points independent. Use group-separated folds when groups must be unseen, and forward splits when the task predicts future observations. Exclude features that would not exist at the claimed prediction time. The cross-validation guide provides distinct splitters for these settings.
Early stopping also learns from data. If it chooses the boosting stage within a CV fit, use an inner training/validation arrangement rather than choosing the stage on the outer fold whose score you intend to treat as independent evaluation evidence. The final test set must not choose preprocessing, a threshold, the stopping stage or the search budget.
Search a declared space, not an unlimited supply of scores
A grid evaluates a listed collection of configurations. Random search draws configurations from declared distributions; it can try more distinct values of influential parameters than a small Cartesian grid. A distribution on a logarithmic scale can be appropriate when the meaningful question is whether \(C\) or a learning rate differs by orders of magnitude. The range is still a modeling decision. The search guide describes the grid and randomized procedures.
A budget has a concrete effect. If an independently drawn configuration has probability 0.1 of lying in a specified useful region, ten draws hit that region with probability \(1-0.9^{10}\approx0.651\). This hypothetical calculation assumes a fixed region and independent draws. It is not a success probability for an actual tuning task, where the useful region is unknown.
Bayesian optimization uses earlier configuration/validation results to fit a surrogate of the response surface. An acquisition rule proposes another configuration, balancing promising predicted performance against uncertainty. Evaluate it using the same declared protocol, then update the surrogate. Snoek, Larochelle and Adams develop a Gaussian-process version. The surrogate need not be the classifier itself; optimizing its suggestions still consumes validation evidence. It cannot repair an invalid split or guarantee a global optimum from a small budget.
Record the search space, configuration count or time limit, metric, folds, seeds and tie rule. Equal trial counts do not imply equal compute or equally thorough coverage. Inspect training/validation gaps, contributor counts for OOB diagnostics, and practical prediction/storage cost alongside the selected score. Fold variation is useful descriptive evidence, but overlapping training sets mean it is not automatically a confidence interval.
Keep selection and final assessment separate
Selecting the largest of many noisy validation scores favors positive noise as well as useful settings. A mean CV score used to choose the winning model is therefore a selection score, not an independent estimate of the chosen procedure’s performance.
Two defensible arrangements are:
- Reserve a final test set. Use only development data for all comparisons and tuning, freeze the complete procedure, refit on development data, then assess it on the test set without using the result for another choice.
- Use nested CV. Each outer training portion contains its own inner search, including preprocessing and model-family selection. Score the selected fit on the untouched outer fold. The outer results assess the whole selection procedure, not one configuration chosen using all folds beforehand.
If a final test result triggers another round of tuning, that set has become part of development. Further claims need fresh independent evidence. A public competition leaderboard has the same feedback problem: repeated submissions and manual choices can adapt to it even when the labels are hidden. A small leaderboard increase does not establish a population improvement. Follow the authoritative lab instructions for the actual assessment; the example below contains no competition data or solution.
Compare against a scaled SVM: a reproducible miniature experiment
A smooth kernel boundary and an axis-aligned tree partition have different inductive biases. Scaling is essential to a meaningful distance-based kernel comparison. Use the Week 02 SVM bridge for the margin/kernel explanation: \(C\) controls the soft-margin penalty and \(\gamma\) the RBF distance scale. Keep the evaluation protocol shared. The instructor’s observation that SVMs were strongest in this class’s lab is task-specific evidence, not a universal ranking to build into an example.
For a separate synthetic illustration, generate 240 two-moons observations with noise 0.22 and seed 2026, and multiply the second coordinate by 100 to represent different measurement units. Reserve a stratified 60-row test set with split seed 2026. Use the remaining 180 development rows in the same three stratified folds for every candidate (shuffle seed 2027). Each fold fits 120 rows and predicts 60; no fold touches the final test observations.
Declare three configurations per family before scoring them:
| Family | Small search space and fixed choices |
|---|---|
| Single tree | Depth 2, 4 or unbounded; minimum leaf size 2. |
| Forest | Minimum leaf size 1, 3 or 6; 100 bootstrap trees, square-root feature candidates. |
| Histogram boosting | Maximum leaves 3, 7 or 15; 80 stages, shrinkage 0.1, minimum leaf size 10, early stopping disabled. |
| RBF SVM | \(C=1,\gamma=0.1\); \(C=1,\gamma=1\); or \(C=10,\gamma=1\). A StandardScaler fitted inside each training fold; no probability calibration. |
This is a small comparison of scikit-learn estimators, not a benchmark of XGBoost, LightGBM or CatBoost. The example ran with Python 3.9.6, NumPy 1.26.4 and scikit-learn 1.6.1, using one computational thread. Randomized tree fits use seed 2026. Three configurations each give comparable declared trial counts, not equal computational cost or exhaustive optimization.
The primary metric is binary ROC-AUC with class one as positive. Use continuous class-one probabilities for trees/ensembles and the SVM’s signed decision scores. A margin score need not be a calibrated probability for ranking; thresholded class predictions discard ranking information. The SVC API distinguishes decision scores from optional probability estimation.
For each family, select its highest mean fold AUC. Select the overall candidate by the same mean; exact ties use the first configuration in the recorded order. The script stores all candidates, fold identities and held-out scores, and independently checks AUC by positive/negative score comparisons, assigning half credit to ties.
| Family | Selected setting | Mean CV AUC |
|---|---|---|
| Tree | depth=None | 0.8739 |
| Forest | leaf=1 | 0.9680 |
| Histogram boosting | leaves=7 | 0.9613 |
| Scaled RBF SVM | C=1, gamma=1 | 0.9863 |
The declared CV rule selects Scaled RBF SVM (C=1, gamma=1). After refitting on all 180 development rows, its one final test ROC-AUC is 0.9989 on 60 rows. The other families are not test-scored for further selection.
The CV entries above were used for selection. They are not an independent four-way test comparison, and the final test result is one small-sample outcome. The smooth moons geometry favors methods that can represent curved boundaries; changing data, noise, splits or the search space can change the ranking. No claim about the class competition follows from this illustration. We did not change its seed or settings to enforce the instructor’s reported lab ranking.
The synthetic rows and complete selection ledger make the calculation inspectable. The export script also checks that each SVM scaler’s mean uses only its own training rows. A fixed seed reproduces this experiment; it is not a substitute for evidence across appropriate samples, splits or tasks.
Synthesis, extensions and optional exercises
Three ways to change a prediction
A tree learns a partition and assigns local constants. Its usefulness comes from nonlinear rules that are easy to trace; its sensitivity comes partly from discrete split choices. Bagging averages predictions from resampled fits. Its benefit depends on how much variability those predictions share. A random forest changes feature candidates as well as row multiplicities to diversify those fits. Boosting instead adds successive corrections defined by a loss. Its classifier combines scores before converting them to probabilities.
| Mechanism | What is fitted; what is combined |
|---|---|
| One tree | Greedy rules and leaf outputs; one path gives the prediction. |
| Bagging/forest | Separate fits on resampled rows, with per-node feature randomization in the illustrated forest; average values/probabilities or use declared votes. |
| Boosting | Trees fitted in sequence to current pseudo-residuals, possibly with further leaf optimization; add scaled corrections to the current predictor. |
None of these constructions decides whether a result generalizes. That requires a valid data boundary, a metric tied to the task and evidence that was not consumed by selecting the method.
Common confusions to avoid
| Distinction | Consequence |
|---|---|
| Impurity versus held-out loss | A split’s training improvement does not establish generalization. |
| Local split versus whole-tree optimum | Greedy selection does not jointly optimize all future rules. |
| Separate fits versus independent predictions | Shared original data can leave substantial covariance. |
| OOB prediction versus per-tree error | Aggregate eligible predictions per row before scoring them. |
| Probability averaging versus hard voting | They can yield different class decisions; neither proves calibration. |
| Residual versus pseudo-residual | They agree under per-example half-squared loss, not every loss/reduction. |
| Binary score versus probability | Add boosting corrections to the logit, then apply sigmoid. |
| Selected CV score versus final assessment | Repeated tuning consumes validation evidence, including leaderboard feedback. |
Connection to later methods
Our tree leaves define fixed regions for a fitted predictor. In Week 04, neural networks learn intermediate representations and train them with derivatives. Both use models, objectives and evaluation boundaries; the way they search for useful functions differs. Week 07 returns to probability models and why particular losses and uncertainty statements are justified.
Optional outlook: tabular foundation models. TabPFN and TabICL provide a contrasting approach using pretrained models and in-context learning from a supplied table. Pretraining moves substantial learning before the current task; it does not eliminate questions about data roles, applicable tasks, computational limits or tuning. This is an optional reading comparison, not another required derivation or an executed benchmark. Evaluate a chosen version under the same held-out protocol rather than treating the name “foundation model” as evidence of superiority.
Optional exercises
These are new practice tasks, not assessed lab solutions. Give the computation and its interpretation; answer keys are not included.
- Route and decide. For the original sixteen-row classification tree, trace \((1.5,2.5)^\top\) and \((1.5001,2.5)^\top\). Give the leaf fraction and class for each, and identify which equality convention matters.
- Weight a split. A parent has class counts \((3,5)\). Candidate A produces \((3,1)\) and \((0,4)\); candidate B produces \((1,3)\) and \((2,2)\). Compute weighted Gini for each. Explain why child counts belong in the calculation.
- Stop or prune. Use the three subtrees in the pruning example. At \(\alpha=0.10\) and \(0.12\), calculate every penalized objective and select a subtree. Explain why a depth limit need not reproduce that selection.
- Average correlated fits. For equal individual variance 4, common correlation 0.3 and \(M=5\), compute the average’s variance and its limiting value as \(M\) grows. State the assumptions and what the calculation says about a common bias.
- Find OOB contributors. In the six-row bootstrap ledger, add a fourth draw with indices \((1,1,3,4,5,5)\). Identify its OOB rows and the new contributor sets for all observations. Explain which predictions must be computed before reporting a new OOB MSE; the omission list alone is not a prediction.
- Take another correction step. Starting from regression \(F_1\), fit the next admissible stump using the declared rules and \(\eta=0.4\). Compute the new MSE and explain any individual rows whose loss increases. Separately, find the sign of the binary pseudo-residual for \(y=1,q=0.2\) and name the quantity to which a correction is added.
- Audit a search. A team computes target encodings on all rows, runs random CV, tries 100 settings, chooses the largest CV score and tunes again after every leaderboard submission. Propose a corrected procedure, including preprocessing, dependence-aware splitting when needed and final evidence.
- Design a fair comparison. Specify a tree/forest/boosting/scaled-SVM comparison for a dataset with repeated customers and missing categories. Declare the prediction question, metric, data boundaries, input handling, search budget, early-stopping rule and resource measurements. Explain what result would and would not justify choosing a method.
References and further reading
- Yandex ML handbook: decision trees.
- Yandex ML handbook: ensembles.
- Week 02 SVM self-study and its official implementation guide.
- The trees and ensembles presentations are linked through the companion pages above. Official tool documentation and primary papers are linked where their claims enter the explanation; the tool snapshot date is stated above.