Random Forests

Let the training set be

$$\mathcal D=\{(x_i,y_i)\}_{i=1}^n.$$

For tree $b\in\{1,\ldots,B\}$, draw a bootstrap dataset

$$\mathcal D_b^\star = \{(x_{i_1},y_{i_1}),\ldots,(x_{i_n},y_{i_n})\},$$

where each index $i_j$ is sampled uniformly from $\{1,\ldots,n\}$ with replacement. Some rows appear multiple times; some rows are left out.

A bagged tree fits

$$\hat f_b(x)=T(x;\mathcal D_b^\star).$$

For regression, bagging predicts by averaging:

$$\hat f_{\text{bag}}(x) = \frac{1}{B}\sum_{b=1}^B \hat f_b(x).$$

For classification with classes $1,\ldots,K$, each tree votes:

$$\hat y_b(x)\in\{1,\ldots,K\},$$

and the forest predicts

$$\hat y_{\text{forest}}(x) = \arg\max_k \sum_{b=1}^B \mathbf 1[\hat y_b(x)=k].$$

Random forests add feature subsampling. If there are $p$ input features, then at each split the tree considers only a random subset

$$M_{b,\ell}\subseteq\{1,\ldots,p\}, \qquad |M_{b,\ell}|=m_{\text{try}},$$

for node $\ell$ in tree $b$. With $m_{\text{try}}=p$, the method is bagging. With $m_{\text{try}}<p$, strong features cannot appear in every split candidate set, so the trees tend to become less correlated.

The averaging story is clearest under squared error. Suppose each tree's prediction at a fixed $x$ has variance $\sigma^2$ and any two tree predictions have correlation $\rho$. The variance of the average is

$$\operatorname{Var}\left(\frac1B\sum_{b=1}^B \hat f_b(x)\right) = \rho\sigma^2+\frac{1-\rho}{B}\sigma^2.$$

The $1/B$ term improves when trees are not perfectly correlated. The $\rho\sigma^2$ term remains when all trees move together. That is why random forests do not just make many trees; they try to make useful trees whose errors are not too synchronized.

Out-of-bag evaluation uses the rows left out of a tree's bootstrap sample. For row $i$, define

$$O_i=\{b: i\notin \mathcal D_b^\star\}.$$

The OOB prediction for row $i$ uses only trees in $O_i$, so it is a built-in validation-like estimate for the forest:

$$\hat y_{\text{OOB}}(x_i) = \arg\max_k \sum_{b\in O_i}\mathbf 1[\hat y_b(x_i)=k].$$

This is useful, but it is not a replacement for careful evaluation contracts, distribution-shift checks, calibration checks, or domain-specific costs.