Tree models partition the input space into axis-aligned regions and fit a constant per region, giving interpretable but high-variance predictors. Ensemble methods combine many trees: bagging and random forests average independently grown trees to cut variance, while boosting grows trees sequentially to cut bias.

- Express a tree as a piecewise-constant function and choose splits with an impurity criterion.

- Control overfitting with cost-complexity pruning.

- Reduce variance by bagging and decorrelate trees with feature subsampling.

- Estimate generalization error for free with out-of-bag samples.

- Build a strong predictor as an additive sum of weak learners (AdaBoost, gradient boosting).

A CART tree partitions the input space into $M$ disjoint regions $R_1,\dots,R_M$ (the leaves) and predicts a constant $c_m$ on each. The prediction is defined as

$$\boxed{ h(x)=\sum_{m=1}^{M} c_m\,\mathbf{1}\{x\in R_m\} }$$

Each internal node tests one feature against a threshold, $x_j\le s$, sending an example left or right. A path from the root to a leaf is a conjunction of such tests.

*Remark:* the regions are axis-aligned boxes, so the decision boundary is a staircase. A single tree has low bias but high variance.

For a region with class proportions $\hat p_k$, impurity measures how mixed the labels are. The Gini index is defined as

$$\boxed{ G = 1-\sum_{k}\hat p_k^{\,2} }$$

and the entropy as

$$\boxed{ H = -\sum_{k}\hat p_k\log_2\hat p_k }$$

A candidate split sends $N_-$ examples to child $R_-$ and $N_+$ to child $R_+$ out of $N$. Its information gain is defined as

$$\boxed{ IG = I(\text{parent})-\frac{N_-}{N}\,I(R_-)-\frac{N_+}{N}\,I(R_+) }$$

where $I$ is the chosen impurity. CART greedily picks the feature and threshold that maximize $IG$ at each node.

| criterion | formula | range (binary) | note |

| --- | --- | --- | --- |

| Gini | $1-\sum_k\hat p_k^{2}$ | $[0,0.5]$ | cheaper, no logarithm |

| entropy | $-\sum_k\hat p_k\log_2\hat p_k$ | $[0,1]$ | information-theoretic |

*Remark:* the two criteria almost always pick the same split. Gini is the default in most implementations because it avoids the logarithm.

For regression the leaf value is the mean of the targets in the region, defined as

$$\boxed{ c_m=\frac{1}{N_m}\sum_{x^{(i)}\in R_m} y^{(i)} }$$

and splits minimize the within-region squared error instead of a classification impurity.

An unpruned tree fits the training set exactly and overfits. Cost-complexity pruning trades fit against tree size $|T|$ (the number of leaves) through a penalty $\alpha\ge0$:

$$\boxed{ C_\alpha(T)=\sum_{m} N_m\,I(R_m)+\alpha\,|T| }$$

Increasing $\alpha$ collapses the weakest splits, yielding a nested sequence of subtrees. The best $\alpha$ is chosen by cross-validation.

Bagging (bootstrap aggregating) trains $B$ trees on $B$ bootstrap resamples of the data and averages them. The bagged predictor is defined as

$$\boxed{ h_{\text{bag}}(x)=\frac{1}{B}\sum_{b=1}^{B} h_b(x) }$$

For classification the average is replaced by a majority vote. Averaging leaves bias unchanged while shrinking variance.

A bootstrap sample draws $N$ examples with replacement from $N$ examples. The probability that a given example is never drawn is $(1-\tfrac1N)^N\to e^{-1}\approx0.37$, so about 37% of the data is left out of each tree. These are its out-of-bag (OOB) examples.

If the $B$ trees each have variance $\sigma^2$ and pairwise correlation $\rho$, the variance of their average is

$$\boxed{ \rho\sigma^2+\frac{1-\rho}{B}\,\sigma^2 }$$

The second term vanishes as $B$ grows, but the first, $\rho\sigma^2$, does not. Reducing the correlation $\rho$ between trees is therefore the key lever, and that is what random forests target.

A random forest is bagging plus feature subsampling: at each split only a random subset of $m_{\text{try}}$ features is considered as split candidates. The usual choices are

$$\boxed{ m_{\text{try}}=\lfloor\sqrt{n}\,\rfloor\ \text{(classification)},\qquad m_{\text{try}}=\lfloor n/3\rfloor\ \text{(regression)} }$$

Restricting the candidate features stops every tree from splitting on the same dominant feature, which decorrelates the trees and lowers $\rho$.

*Remark:* OOB error averages each tree's error over only the examples that tree never saw, giving a cross-validation-like estimate at no extra cost.

| property | bagging | random forest |

| --- | --- | --- |

| resampling | bootstrap | bootstrap |

| split candidates | all $n$ features | random $m_{\text{try}}$ features |

| tree correlation $\rho$ | higher | lower |

| variance reduction | moderate | stronger |

Boosting builds a predictor as a weighted sum of $T$ weak learners $h_t$ (typically shallow trees), fitted one at a time. The additive model is defined as

$$\boxed{ H_T(x)=\sum_{t=1}^{T}\alpha_t\,h_t(x) }$$

Each stage corrects the errors of the running sum, so the ensemble is built sequentially and reduces bias rather than variance.

With labels $y\in\{-1,+1\}$, AdaBoost keeps example weights $w^{(i)}$ that concentrate on the currently misclassified points. At round $t$ the weak learner has weighted error $\varepsilon_t$, and its coefficient is defined as

$$\boxed{ \alpha_t=\tfrac12\log\frac{1-\varepsilon_t}{\varepsilon_t} }$$

so a more accurate learner ($\varepsilon_t$ small) gets a larger vote. The weights are then updated as

$$\boxed{ w^{(i)}\leftarrow w^{(i)}\exp\!\big(-\alpha_t\,y^{(i)}h_t(x^{(i)})\big) }$$

and renormalized. Misclassified examples ($y^{(i)}h_t(x^{(i)})<0$) gain weight, so the next learner focuses on them.

Gradient boosting generalizes the idea to any differentiable loss $L$. At stage $t$ it fits the next learner to the negative gradient of the loss evaluated at the current model, the pseudo-residual defined as

$$\boxed{ r^{(i)}_t=-\left[\frac{\partial L\big(y^{(i)},f(x^{(i)})\big)}{\partial f}\right]_{f=H_{t-1}} }$$

The model is then updated with a learning rate (shrinkage) $\nu\in(0,1]$:

$$\boxed{ H_t=H_{t-1}+\nu\,\alpha_t\,h_t }$$

*Remark:* with squared-error loss the pseudo-residual is just the ordinary residual $y^{(i)}-H_{t-1}(x^{(i)})$, so each tree fits what the current model still gets wrong.

| property | bagging | boosting |

| --- | --- | --- |

| training | parallel, independent | sequential, each on the previous errors |

| base learners | deep, low bias | shallow, high bias |

| mainly reduces | variance | bias |

| reweighting | none (bootstrap) | weights or pseudo-residuals |

---

Next: [Course overview](/en/Machine%20Learning)