Bagging and random forests
Bagging (bootstrap aggregating) and Random Forests are ensemble methods that reduce model variance by training many decision trees on bootstrap samples and aggregating their predictions; random forests further decorrelate trees by selecting random subsets of features at each split.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Bagging and Random Forests are used by engineers to improve prediction accuracy and stability when single models (especially decision trees) overfit or have high variance. They are widely applied to classification and regression problems in industry (fault detection, sensor data, reliability analysis) because they are robust, require little feature scaling, and give useful measures like variable importance.
Key ideas
Out-of-bag (OOB) sample/estimate: For a tree trained on a given bootstrap sample, the examples not included in that sample are its out-of-bag examples. The OOB error estimate aggregates predictions for each example using only the trees for which that example was OOB; it is an internal cross-validation estimate requiring no separate validation set. For M trees, the probability an example receives at least one OOB prediction is 1 - (1 - (1 - 1/n)^n)^M ≈ 1 - 0.632^M, and the expected number of OOB predictions per example is ≈ 0.368·M.
Why bagging helps: Bagging reduces the variance of an unstable estimator (one where small changes to training data produce large changes in the fitted model), while bias typically remains similar. If base learners are independent and each has variance σ^2, averaging M learners reduces variance by factor 1/M. In practice base learners are correlated; the variance of the average depends on the pairwise correlation ρ between learners. Exact statement (commonly used in exams):
Theorem (variance of average of M identically distributed estimators with variance σ^2 and pairwise correlation ρ):
If estimators T1,...,TM are identically distributed with E[Ti] = μ and Var(Ti) = σ^2 and Corr(Ti,Tj) = ρ for i ≠ j (assume equal pairwise correlation), then Var((1/M) Σ Ti) = (ρ + (1 - ρ)/M)·σ^2.
Assumptions: identical distribution, equal pairwise correlation, finite second moments. Derivation below in step form (universities commonly ask for it):
Derivation: write Var(mean) = (1/M^2) Σi Var(Ti) + (2/(M^2)) Σ_{i<j} Cov(Ti,Tj)
- Var(Ti) = σ^2, there are M terms → (M·σ^2)/M^2 = σ^2/M.
- Cov(Ti,Tj) = ρ·σ^2, there are M(M-1)/2 pairs → 2/(M^2) · [M(M-1)/2] · ρσ^2 = ((M-1)/M)·ρσ^2.
- Sum = σ^2/M + ((M-1)/M)·ρσ^2 = (ρ + (1-ρ)/M)σ^2.
Interpretation: As M → ∞ the variance tends to ρ·σ^2. If trees are uncorrelated (ρ ≈ 0), variance → 0; if perfectly correlated (ρ = 1), averaging does not reduce variance.
Random Forest (Breiman, 2001) = Bagged ensemble of decision trees where at each candidate split during tree construction a random subset of m_try features (out of total p features) is considered. This reduces correlation ρ between trees and so improves ensemble variance reduction. Trees are typically grown to maximum depth without pruning on bootstrap samples; forest predictions are obtained by averaging for regression and by majority vote or averaged class probabilities for classification. Reducing m_try lowers correlation but can increase bias; m_try should be tuned.
Typical heuristics (not strict rules): for classification m_try ≈ floor(sqrt(p)), for regression m_try ≈ floor(p/3). These are widely used defaults but can be tuned.
Decision tree split criteria used in random forests:
- Gini impurity (classification): at node with class proportions pk, Gini = 1 - Σ_k p_k^2.
- Entropy/information gain can also be used.
- For regression trees node impurity usually measured by mean squared error (MSE) reduction.
Variable importance measures:
- Mean decrease in impurity (MDI): sum over splits where a feature is used of the weighted impurity decrease (weighted by the number or proportion of samples reaching the node), averaged over trees.
- Permutation importance: for each tree, permute values of a feature in the OOB samples and measure increase in OOB error; average the increase across trees. This estimates predictive importance.
Computational complexity: Training M full-grown trees on bootstrap samples is roughly M times a single tree cost. Trees are trained independently and are easily parallelizable. A rough per-tree complexity is O(n · m_try · depth) (often O(n · m_try · log n) for balanced trees), and across the forest this scales by a factor of M.
Diagram to draw (for exam): Draw four boxes representing the original dataset (labelled 1..n). Draw three arrows to three separate bootstrap samples (each of size n drawn with replacement); inside each bootstrap sample, illustrate some repeated indices and some omitted indices. From each bootstrap sample draw an arrow to a decision tree. From the trees draw arrows to an aggregator block (majority vote / averaging). Label OOB examples for each tree, and indicate the aggregation method (vote/average). Also label p (number of features) and m_try at the split node with a note "choose m_try random features".
Formulas
Prob(not chosen in one bootstrap sample) = (1 - 1/n)^n where n = training set size; (dimensionless). Applies to bootstrap sampling with replacement.
Limit_{n→∞} (1 - 1/n)^n = e^{-1} where e = 2.718281828...; dimensionless; shows asymptotic probability ≈ 0.368.
Var(average of M estimators) = (ρ + (1 - ρ)/M) · σ^2 where ρ = pairwise correlation (dimensionless), σ^2 = variance of single estimator (units = (prediction unit)^2), M = number of estimators; applies under identical distribution and equal pairwise correlation assumptions.
Gini = 1 - Σ_{k} p_k^2 where p_k = proportion of class k at a node (dimensionless); applies to classification node impurity.
Entropy = -Σ_k p_k log_2 p_k where p_k = class proportion; units = bits; applies when using information gain.
OOB_error = (1 / N_valid) Σ_{i in valid} Loss(y_i, ŷ_i^{OOB}) where ŷ_i^{OOB} is aggregated prediction for example i using only trees where i was OOB, N_valid = number of examples with at least one OOB prediction; Loss = 0-1 for classification or squared error for regression.
m_try (classification heuristic) ≈ floor(sqrt(p)) where p = total number of features; dimensionless; heuristic default.
m_try (regression heuristic) ≈ floor(p/3) heuristic default.
Worked examples
- Variance reduction numerical example (exam-style derivation and numeric substitution)
Problem: A base tree estimator has variance σ^2 = 1 (units: (prediction)^2). Pairwise correlation between trees is estimated as ρ = 0.2. If we average M = 25 trees, what is the variance of the ensemble average?
Solution steps:
- Formula: Var(mean) = (ρ + (1 - ρ)/M)·σ^2.
- Substitute values: Var(mean) = (0.2 + (1 - 0.2)/25)·1 = 0.2 + 0.8/25.
- Compute 0.8/25 = 0.032.
- Sum = 0.2 + 0.032 = 0.232.
- Final answer: Var = 0.232 (prediction-unit^2).
This shows most of the remaining variance is due to correlation ρ; increasing M beyond 25 gives diminishing returns because variance → 0.2 as M → ∞.
- Bootstrap and OOB example (small dataset) — model answer to an exam question
Problem: Consider dataset with 4 examples indexed 1..4 with true class labels y = [0, 1, 0, 1]. Three bootstrap samples (size 4) used to train three trees are:
- Tree1 sample indices: [1, 1, 2, 4]
- Tree2 sample indices: [2, 3, 3, 4]
- Tree3 sample indices: [1, 2, 4, 4] Assume the following predictions for OOB examples: Tree1 predicts example 3 → 0; Tree2 predicts example 1 → 0; Tree3 predicts example 3 → 0. Compute the OOB error.
Solution steps:
- Identify OOB examples per tree: Tree1 OOB = {3}; Tree2 OOB = {1}; Tree3 OOB = {3}.
- Collect aggregated OOB predictions per example:
- Example 1: predictions from trees where 1 was OOB = {Tree2 → 0}. Aggregated (majority) = 0. True y1 = 0 → correct.
- Example 2: appears in all three samples (no OOB predictions) → excluded from OOB error calculation.
- Example 3: predictions from trees where 3 was OOB = {Tree1 → 0, Tree3 → 0}. Aggregated = 0. True y3 = 0 → correct.
- Example 4: appears in all three samples → excluded.
- Number of examples with OOB predictions N_valid = 2 (examples 1 and 3). Number misclassified among them = 0.
- OOB_error = 0 / 2 = 0.
Final answer: OOB error = 0 (zero misclassification among OOB-evaluated examples).
Note: This example also shows a limitation: some examples may never be OOB across the forest; OOB estimate uses only those with at least one OOB prediction.
Common mistakes
- Using the 1/M variance reduction formula without accounting for correlation ρ; real trees are correlated so variance does not go to zero unless ρ ≈ 0.
- Miscomputing the (1 - 1/n)^n limit; for finite n compute numerically, and for large n use e^{-1} ≈ 0.368.
- Confusing OOB estimate with training error; OOB approximates validation error but is not identical to k-fold cross-validation.
- Reporting default m_try values as theoretical truths instead of heuristics to be tuned.
- Interpreting variable importance (MDI) without noting that features with many categories or continuous features can artificially appear more important. Interpreting permutation importance with strongly correlated features can be misleading; shuffling one correlated feature may show little importance even if the group of correlated features is important.
For your exam
Types of questions you will see:
- Definitions (define bagging, bootstrap, random forest, OOB).
- Short notes (advantages/disadvantages of bagging; why random feature selection reduces correlation).
- Derivations (derive ensemble variance formula assuming equal pairwise correlation—write steps shown above). Full-marks answer: start from Var(mean) expansion, count terms, substitute covariance = ρσ^2, simplify.
- Numericals (compute variance after averaging given σ^2, ρ, M; compute probability an example is OOB for given n; compute Gini impurity for node with class counts).
- Diagrams (draw bootstrap → trees → aggregator; indicate OOB examples and m_try at splits).
- Practical short-answer/interpretation (explain permutation importance steps and limitations).
What full-marks answers include:
- Clear definitions with bolded terms, stated assumptions, and units if applicable.
- Step-by-step derivations (no skipped algebraic steps for the variance derivation).
- Correct diagram labels: dataset indices, bootstrap samples (show duplicates/omissions), trees, aggregator, OOB labels, p and m_try.
- When asked for heuristics (m_try), state that they are defaults and should be tuned.
Quick check
- What is the usual purpose of using random feature selection (m_try) in Random Forests?
- Give the formula for Gini impurity for a node with two classes with proportions p and 1-p.
- What is the asymptotic probability that a given training example is not selected in one bootstrap sample of size n?
Answers: 1) To reduce correlation between trees (lower ρ) so averaging reduces variance more; 2) Gini = 1 - (p^2 + (1 - p)^2) = 2p(1 - p); 3) e^{-1} ≈ 0.368.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?