Why Track Each Tree Update?
In squared-error boosting, a fitted model is built by adding trees in sequence. Each new tree responds to what the current model has not yet fitted: its target values are the current residuals, not the original responses. This makes the arithmetic iterative. A calculation that carries forward an old residual, or adds a leaf prediction to the wrong fit, can give plausible-looking but incorrect results.
This tutorial works through complete updates on small training samples. The tree partitions are specified in each example; the task is to calculate the predictions in their terminal nodes and update the fitted values. Unless stated otherwise, use ordinary unweighted squared error and a full update: add the tree prediction directly to the current fitted value.
The initial constant fit is commonly set to the sample mean, so \(F_0(x_i)=\bar y\) for every training observation, where \(\bar y=\frac{1}{n}\sum_{i=1}^n y_i\). After that, residuals must be recalculated from the latest fitted values at every iteration. The formulas above describe the update for a given partition; they do not specify how to search over possible tree partitions.
Why the Terminal-Node Prediction Is a Mean
The prediction in a leaf is chosen to minimize squared error for the residuals assigned to that leaf. Suppose a leaf contains \(k\) residuals \(r_1,\ldots,r_k\), and the leaf predicts a constant \(c\). Its squared error is \(Q(c)=\sum_{i=1}^k(r_i-c)^2\). Differentiating with respect to \(c\) gives \(Q'(c)=-2\sum_{i=1}^k(r_i-c)\). At a minimum, \(Q'(c)=0\), so \(kc=\sum_{i=1}^k r_i\), and hence \(c=\bar r\), the mean residual in the leaf. Since \(Q''(c)=2k>0\), this critical point is the minimum.
The same result follows by completing the square. Writing \(\bar r=\frac{1}{k}\sum_i r_i\),
The cross-term vanishes because \(\sum_i(r_i-\bar r)=0\). The second term is nonnegative and is zero only at \(c=\bar r\). Thus the mean is the unique squared-error-minimizing constant prediction in the leaf.
Worked Updates
Worked Example: Two Updates With Three Terminal Nodes
A hypothetical training set has responses \((2,4,8,10)\). Start with the sample-mean fit. At the first iteration, the tree has leaves containing observations \(\{1,2\}\) and \(\{3,4\}\). At the second iteration, its leaves contain \(\{1\}\), \(\{2,3\}\), and \(\{4\}\). Calculate both trees’ leaf predictions, the updated fits, and the residual sum of squares after each update.
Method. Initialize at the mean, average the current residuals within each specified leaf, add those predictions to the current fits, then recompute residuals and squared error. This sequence avoids applying the second tree to the original responses.
The initial mean is \((2+4+8+10)/4=24/4=6\), so \(F_0=(6,6,6,6)\). The initial residuals are \(y_i-F_0(x_i)=(-4,-2,2,4)\).
For the first tree, the prediction for \(\{1,2\}\) is \((-4-2)/2=-3\), and the prediction for \(\{3,4\}\) is \((2+4)/2=3\). Adding these predictions gives \(F_1=(6-3,6-3,6+3,6+3)=(3,3,9,9)\). The new residuals are \((2-3,4-3,8-9,10-9)=(-1,1,-1,1)\), so the residual sum of squares is \(1+1+1+1=4\).
For the second tree, the leaf predictions are \(-1\) for \(\{1\}\), \((-1+1)/2=0\) for \(\{2,3\}\), and \(1\) for \(\{4\}\). Therefore, \(F_2=(3-1,3+0,9+0,9+1)=(2,3,9,10)\). The residuals are \((0,1,-1,0)\), and the residual sum of squares is \(0^2+1^2+(-1)^2+0^2=2\).
Check. Both updates add the corresponding leaf prediction to the previous fit, and the second iteration’s residuals are calculated from \(F_1\). The final fits are \((2,3,9,10)\), not the original responses.
Worked Example: Recomputing Residuals Before the Second Tree
For responses \((1,4,7,10,13,16)\), initialize at the mean. The first tree splits after observation 3, giving leaves \(\{1,2,3\}\) and \(\{4,5,6\}\). The second tree has leaves \(\{1,2\}\), \(\{3,4\}\), and \(\{5,6\}\). Find the leaf predictions and fitted values at both iterations, and calculate the residual sum of squares after each tree.
Method. Recalculate the residual vector after the first update, then average that vector within each second-tree leaf. This avoids the common mistake of fitting the second tree to residuals from the initial model.
The response mean is \((1+4+7+10+13+16)/6=51/6=8.5\), so every initial fit is 8.5. The initial residuals are \((-7.5,-4.5,-1.5,1.5,4.5,7.5)\).
The first leaf prediction is \((-7.5-4.5-1.5)/3=-13.5/3=-4.5\). The second is \((1.5+4.5+7.5)/3=13.5/3=4.5\). Thus \(F_1=(4,4,4,13,13,13)\). The new residuals are \((-3,0,3,-3,0,3)\); the residual sum of squares is \(9+0+9+9+0+9=36\).
For the second tree, the mean residuals in its three leaves are \((-3+0)/2=-1.5\), \((3-3)/2=0\), and \((0+3)/2=1.5\). Adding these to the current fits gives \(F_2=(4-1.5,4-1.5,4+0,13+0,13+1.5,13+1.5)=(2.5,2.5,4,13,14.5,14.5)\). The residuals are \((-1.5,1.5,3,-3,-1.5,1.5)\). Their squared sum is \(2.25+2.25+9+9+2.25+2.25=27\).
Check. The first residual sum of squares is 36 and the second is 27. The second tree removes 9 units of squared error; its leaf predictions sum to zero within each leaf when subtracted from that leaf’s current residuals.
Worked Example: Unequal Leaf Sizes and an Error Audit
A hypothetical sample has responses \((2,6,10,14,18)\). Initialize at the sample mean. The first tree has leaves \(\{1,2,3\}\) and \(\{4,5\}\). The second tree has leaves \(\{1,2\}\), \(\{3,4\}\), and \(\{5\}\). Calculate the leaf predictions, updated fits and residual sums of squares.
Method. Use the mean residual in each leaf, accounting for each leaf’s own size. In particular, do not average the leaf predictions equally to obtain an observation-level update.
The initial mean is \((2+6+10+14+18)/5=50/5=10\). Thus \(F_0=(10,10,10,10,10)\), and the initial residuals are \((-8,-4,0,4,8)\).
For the first tree, the prediction in \(\{1,2,3\}\) is \((-8-4+0)/3=-12/3=-4\). The prediction in \(\{4,5\}\) is \((4+8)/2=6\). Hence \(F_1=(6,6,6,16,16)\). The residuals are \((-4,0,4,-2,2)\), with squared sum \(16+0+16+4+4=40\).
For the second tree, the predictions are \((-4+0)/2=-2\) in \(\{1,2\}\), \((4-2)/2=1\) in \(\{3,4\}\), and \(2\) in the singleton leaf \(\{5\}\). The updated fit is \(F_2=(6-2,6-2,6+1,16+1,16+2)=(4,4,7,17,18)\). The new residuals are \((-2,2,3,-3,0)\), with squared sum \(4+4+9+9+0=26\).
Check. For the second tree, the residual sum of squares falls from 40 to 26, a reduction of 14. The reductions from the three leaves are \(2(-2)^2=8\), \(2(1)^2=2\), and \(1(2)^2=4\), which sum to 14.
Tracking the Squared-Error Change
There is a quick check on each leaf update. If a leaf contains \(k\) current residuals with mean \(\bar r\), its squared error before the update is \(\sum_i r_i^2\). After adding \(\bar r\) to the fit, the new residuals in that leaf are \(r_i-\bar r\). Their squared sum is
To verify the identity, expand the left side as \(\sum_i r_i^2-2\bar r\sum_i r_i+k\bar r^2\). Since \(\sum_i r_i=k\bar r\), this equals \(\sum_i r_i^2-2k\bar r^2+k\bar r^2=\sum_i r_i^2-k\bar r^2\). The reduction is therefore \(k\bar r^2\), which is nonnegative. Summing this reduction over the leaves gives the training squared-error reduction for the specified tree update.
Common Mistakes and Exam Traps
- Reusing old residuals. After updating the fit, compute \(r_{i,m+1}=y_i-F_m(x_i)\). Do not use \(y_i-F_{m-1}(x_i)\) again at the next stage.
- Adding rather than subtracting in the residual definition. The residual is response minus fit. The tree prediction is added to the fit, so the new residual is the old residual minus that prediction.
- Using the response mean in later leaves. The initial fit may be the response mean, but later leaf predictions are means of the current residuals.
- Ignoring leaf membership or size. Average only the residuals assigned to that terminal node. A singleton leaf predicts its one residual exactly.
- Confusing a prediction with a fitted value. A leaf prediction is the amount added at that stage; the updated fit also includes all earlier stages.
For example, in the first worked example the second-tree prediction in leaf \(\{2,3\}\) is 0 because its current residuals are 1 and \(-1\). A tempting but wrong calculation would take the mean of the original responses, \((4+8)/2=6\), as that tree prediction. That would disregard the current model entirely. The correction is to use the latest residuals, not the original responses.
Check Your Understanding
For each problem, use a full update: add each terminal-node mean residual directly to the current fit.
- For responses \((2,4,8,10)\), start at the mean and use a first tree with leaves \(\{1,2\}\) and \(\{3,4\}\). A second tree has leaves \(\{1\}\), \(\{2,3\}\), and \(\{4\}\). Give the second-tree leaf predictions and final fits. (Answer: leaf predictions \((-1,0,1)\); final fits \((2,3,9,10)\).)
- For responses \((1,4,7,10,13,16)\), initialize at the mean and use one tree split after observation 3. Give the leaf predictions, updated fits, and residual sum of squares. (Answer: leaf predictions \((-4.5,4.5)\); fits \((4,4,4,13,13,13)\); residual sum of squares \(36\).)
- For responses \((2,5,8,11)\), initialize at the mean. The first tree splits after observation 2; the second has leaves \(\{1\}\), \(\{2,3\}\), and \(\{4\}\). Find the second-tree leaf predictions, final fits, and final residual sum of squares. (Answer: leaf predictions \((-1.5,0,1.5)\); fits \((2,3.5,9.5,11)\); residual sum of squares \(4.5\).)
- Current fits for responses \((5,7,9,15)\) are \((6,6,10,10)\). A new tree has leaves \(\{1,2,3\}\) and \(\{4\}\). Calculate the leaf predictions, updated fits, and new residual sum of squares. (Answer: predictions \((-1/3,5)\); fits \((17/3,17/3,29/3,15)\); residual sum of squares \(8/3\).)
- The current residuals for six observations are \((-3,1,2,2,4,0)\). A tree has leaves \(\{1,2,3\}\) and \(\{4,5,6\}\). Find its leaf predictions, the new residual vector, and the reduction in residual sum of squares. (Answer: predictions \((0,2)\); new residuals \((-3,1,2,0,2,-2)\); reduction \(12\).)