Why Resample Training Cases for Trees?
A classification or regression tree can change noticeably when the training cases change. A few altered cases may affect which split is selected, how the terminal nodes are formed, or what predictions those nodes produce. This sensitivity is one reason tree ensembles fit multiple trees and combine their predictions rather than relying on a single fitted tree.
The bootstrap provides a way to create alternative training samples from the data already observed. Each bootstrap sample has the same number of rows as the original training set, but rows are selected with replacement. A selected case can appear more than once, while another case may not appear at all. The resulting samples give tree-fitting procedures different case multiplicities and can therefore produce different trees.
The word “sample” can be misleading if it suggests that the result must contain \(n\) distinct cases. It does not. For example, if the original cases are indexed \(1,\ldots,n\), a bootstrap sample might draw case 4 twice, case 1 once, and case 3 once, while not drawing some other cases. Its length is still \(n\).
The ordinary bootstrap described here assumes rows can be treated as exchangeable draws from the observed training cases. It is commonly used for independent observations. If observations are clustered, paired, or ordered in time, resampling individual rows independently can destroy important structure; a design that preserves the relevant dependence is needed instead.
Draws, Multiplicities, and Omitted Cases
It is useful to record a bootstrap sample in two equivalent forms: as the ordered list of draws, or as a set of multiplicities. Let \(N_i\) be the number of times training case \(i\) is selected. Then \(N_i\) is a nonnegative integer, and the total number of draws is
A case is omitted from that bootstrap sample exactly when \(N_i=0\). A case is repeated when \(N_i\) is greater than 1. Repetitions do not create new independent information about the population; they give the selected observed case greater weight in fitting that particular tree.
Worked Example: Counting Repeated and Omitted Cases
A hypothetical training set contains six cases, indexed 1 through 6. One bootstrap sample is drawn in this order: \(2,5,2,1,6,5\). Find every case’s multiplicity, the number of distinct cases represented, the number omitted, and the number of draws beyond the first appearance of each represented case.
Step 1: Tally the draws. Case 1 appears once; case 2 appears twice; cases 3 and 4 appear zero times; case 5 appears twice; and case 6 appears once. Thus the multiplicities are \((1,2,0,0,2,1)\).
Step 2: Check the sample size. The multiplicities sum to \(1+2+0+0+2+1=6\), matching the six draws.
Step 3: Count represented and omitted cases. Cases 1, 2, 5, and 6 are represented, so there are 4 distinct cases. Cases 3 and 4 are omitted, so there are 2 omitted cases.
Step 4: Count excess repetitions. The first appearance of each of the 4 represented cases accounts for 4 draws. The remaining \(6-4=2\) draws are repeats: one extra draw of case 2 and one extra draw of case 5.
Check. The four represented cases contribute one initial draw each, and the two repeated draws bring the total to 6. A common mistake is to say the bootstrap sample has only four observations because only four distinct cases appear. It has six draws, with multiplicities as listed.
Why Multiplicities Are Equivalent to Repeated Rows
For many tree-fitting calculations, the ordered list of bootstrap draws is not necessary once the multiplicities are known. To see why, suppose a tree-fitting procedure evaluates a loss \(L_i\) for each occurrence of case \(i\), and the loss for that case is the same each time it appears. The total loss across the bootstrap draws is the sum of the case losses, including repeats. Grouping equal terms gives the multiplicity-weighted form:
This follows simply by collecting the \(N_i\) identical contributions \(L_i\) for each original case \(i\). The same accounting applies to class counts, sums of responses, and many impurity calculations. A row with multiplicity 3 contributes three times to such a calculation; a row with multiplicity 0 contributes nothing to that bootstrap fit.
This equivalence concerns the data contributions to a fit. A software implementation must use frequency weights in a way consistent with its tree criteria and stopping rules to reproduce the same fit as explicitly repeating rows. The bootstrap sample is still conceptually the list of draws.
Worked Example: A Bootstrap Leaf Estimate
A hypothetical binary classification training set has five cases with class labels, in index order, \(0,1,0,1,1\). A bootstrap sample draws indices \(2,2,3,5,5\). For a tree restricted to one terminal node, calculate the bootstrap class-1 proportion and compare it with the original training-set proportion.
Step 1: Record multiplicities. The sample contains case 2 twice, case 3 once, and case 5 twice. Cases 1 and 4 are omitted. The multiplicities are \((0,2,1,0,2)\), which sum to 5.
Step 2: Count class 1 in the bootstrap sample. Case 2 has label 1 and contributes \(2\) copies. Case 3 has label 0 and contributes \(0\) class-1 cases. Case 5 has label 1 and contributes \(2\) copies. Thus there are \(2+0+2=4\) class-1 draws out of 5.
Step 3: Calculate the leaf estimate. The estimated class-1 proportion in this one-node tree is \(4/5=0.8\). The estimated class-0 proportion is \(1/5=0.2\), so the majority-class prediction is class 1.
Step 4: Compare with the original data. The original labels contain three 1s among five cases, giving a class-1 proportion of \(3/5=0.6\). The bootstrap estimate is therefore \(0.8\), not \(0.6\), because cases 2 and 5 were repeated and case 4, also a class-1 case, was omitted.
Check. The bootstrap class counts are four 1s and one 0, totaling five draws. A common mistake is to count only the three distinct represented cases; that would discard the influence of the repeated rows.
How Different Samples Can Produce Different Trees
Bootstrap resampling changes the weights attached to training cases. As a result, the class composition of a node and the improvement from a candidate split can change. Even when the candidate predictor variables are unchanged, a different resample can favor a different root split. The following calculation uses Gini impurity, defined for a node with class proportions \(p_0\) and \(p_1\) as \(1-p_0^2-p_1^2\). For a proposed split, the weighted child impurity is the sum of each child’s impurity multiplied by its fraction of the parent’s cases; the Gini gain is parent impurity minus weighted child impurity.
Worked Example: Two Resamples Select Different Root Splits
A hypothetical four-case classification data set has two binary predictors, \(A\) and \(B\), and a binary response \(Y\). The observations are \((A,B,Y)=(0,0,0),(0,1,0),(1,0,1),(1,1,0)\). A tree considers splitting at the root on either \(A\) or \(B\), and selects the split with the larger Gini gain. Compare two bootstrap samples represented by multiplicities: sample I is \((2,0,1,1)\), and sample II is \((1,0,1,2)\), in the listed case order.
Method. Treat each multiplicity as the number of copies of that case, calculate the parent impurity and the weighted impurity after each candidate split, then choose the larger gain.
Sample I: parent node. Its four draws consist of three class-0 cases and one class-1 case. Therefore \(p_0=3/4\), \(p_1=1/4\), and parent impurity is
Sample I: split on \(A\). The \(A=0\) child contains two copies of case 1, both class 0, and has impurity 0. The \(A=1\) child contains one class-1 copy of case 3 and one class-0 copy of case 4, so its impurity is \(1-(1/2)^2-(1/2)^2=0.5\). The weighted child impurity is \((2/4)(0)+(2/4)(0.5)=0.25\). The gain is \(0.375-0.25=0.125\).
Sample I: split on \(B\). The \(B=0\) child contains two class-0 copies of case 1 and one class-1 copy of case 3. Its impurity is \(1-(2/3)^2-(1/3)^2=4/9\). The \(B=1\) child contains one class-0 copy of case 4 and has impurity 0. The weighted child impurity is \((3/4)(4/9)+(1/4)(0)=1/3\). The gain is \(0.375-1/3=1/24\), approximately \(0.0417\). Sample I selects \(A\), since \(0.125>0.0417\).
Sample II: parent node. There are again three class-0 draws and one class-1 draw, so the parent impurity is \(0.375\).
Sample II: split on \(A\). The \(A=0\) child contains one class-0 copy and has impurity 0. The \(A=1\) child contains one class-1 copy and two class-0 copies, giving impurity \(4/9\). The weighted child impurity is \((1/4)(0)+(3/4)(4/9)=1/3\). The gain is \(0.375-1/3=1/24\), approximately \(0.0417\).
Sample II: split on \(B\). The \(B=0\) child has one class-0 copy of case 1 and one class-1 copy of case 3, giving impurity 0.5. The \(B=1\) child has two class-0 copies of case 4 and has impurity 0. The weighted child impurity is \((2/4)(0.5)+(2/4)(0)=0.25\). The gain is \(0.375-0.25=0.125\). Sample II selects \(B\), since \(0.125>0.0417\).
Check. Each multiplicity vector sums to 4, and the parent class counts are identical in both samples. Nevertheless, the different case weights make \(A\) the preferred split in Sample I and \(B\) the preferred split in Sample II. The calculation avoids the mistake of assuming that identical parent class proportions force identical trees.
From Bootstrap Trees to an Ensemble
In a tree ensemble based on bootstrap resampling, a separate bootstrap sample is generated for each tree, and the tree is fitted to that sample. Because the multiplicities differ across samples, the fitted trees may differ in their splits, terminal-node membership, or predictions. An ensemble then combines predictions across trees: regression procedures commonly average numerical predictions, while classification procedures can combine class votes or estimated class probabilities.
The purpose of resampling is not to make every tree different, nor does it guarantee that every bootstrap sample yields a useful tree. Two samples can happen to produce similar trees. The point is that a flexible tree learner may respond to changes in the training cases, and resampling supplies controlled variation in those cases. Aggregation can then reduce reliance on the idiosyncrasies of any one fitted tree.
Bootstrap diversity is conditional on the observed training set. It does not mean the ensemble has collected new independent observations from the underlying population. Each tree reuses the same original cases, with a different pattern of repetition and omission. Also, resampling rows and restricting which predictors a tree may consider are distinct mechanisms; the former changes case weights, while the latter changes available split candidates.
Common Mistakes and Scope
- Sampling without replacement. A bootstrap sample permits repeats. Drawing \(n\) distinct cases without replacement would merely rearrange the original training set.
- Changing the sample size unintentionally. A standard bootstrap sample of size \(n\) has \(n\) draws even if fewer than \(n\) distinct cases appear.
- Dropping repeated rows when fitting. A repeated case contributes repeatedly, or equivalently receives its multiplicity as a frequency weight when the fitting calculation supports that equivalence.
- Calling omitted cases deleted from the data set. Omission applies to one bootstrap sample only. The case remains in the original training data and may appear in other resamples.
- Assuming ordinary row bootstrap is suitable for every data structure. If observations have dependence or a special sampling design, the resampling unit and method must preserve that structure.
Check Your Understanding
For each problem, treat the listed draws or multiplicities as one bootstrap sample unless stated otherwise.
- A training set has five indexed cases. A bootstrap draw is \(2,5,2,1,5\). How many distinct cases appear, how many are omitted, and how many draws are repeats beyond each case’s first appearance? (Answer: 3 distinct cases; 2 omitted cases; 2 repeat draws.)
- Four bootstrap draws have labels \(0,1,1,0\). What is the bootstrap class-1 proportion? (Answer: \(2/4=0.5000\).)
- Three original regression responses are \(2,5,8\), and a bootstrap sample has multiplicities \((2,0,1)\). Find the bootstrap one-node mean and the original-data mean. (Answer: Bootstrap mean \(=(2(2)+0(5)+1(8))/3=4\); original mean \(=(2+5+8)/3=5\).)
- A bootstrap sample has four draws with multiplicities \((1,0,2,1)\). State the sample size, number of represented cases, number omitted, and total number of repeat draws beyond first appearances. (Answer: Sample size 4; 3 represented; 1 omitted; 1 repeat draw.)
- Two bootstrap samples of equal size give different multiplicities to cases in the same training set. Explain why they can select different root splits even when they have the same parent class proportions. (Answer: The case weights within predictor-defined child nodes can differ, changing each candidate split’s weighted child impurity and Gini gain; equal parent proportions do not imply equal split gains.)