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

| Bagging | high capacity (deep trees) | in parallel, on resampled data | variance |

| Boosting | low capacity (stumps) | sequentially, on reweighted data | bias |

2. There is **no bootstrap**: every example is used to train every learner.

3. The data is **reweighted**: examples misclassified by $h_t$ gain weight, so $h_{t+1}$ concentrates on them.

2. Compute its weighted error $\varepsilon_t = \sum_{i \in \mathcal{M}_t} w^{(i)}$ over the misclassified set $\mathcal{M}_t$.

3. Give it its vote, large when the error is small:

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

| 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 |

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

| 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 |

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 the cross-validation of [General concepts](/en/Machine%20Learning/02%20General%20concepts).

A random forest is bagging applied to deep trees, plus a second source of randomness. The variance formula of section 8.2 said the residual term $\rho\sigma^2$ survives averaging, so the trees must be decorrelated: 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 makes the trees' errors as uncorrelated as possible and lowers $\rho$.

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

| property | bagging | random forest |

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

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

| variance reduction | moderate | stronger |