Bagging and random forests

Fix training data $D=((x_i,y_i){)}_{i=1}^n$ with $n\ge 1$, features $x_i\in {\mathbb{R}}^p$ with $p\ge 1$, and one response mode: regression with $y_i\in \mathbb{R}$, or classification with labels in a fixed ordered finite set $\mathcal{C}=\{c_1<\cdots <c_J\}$, $J\ge 1$. Choose a finite integer depth cap $d_{\max }\ge 0$, an integer tree count $B\ge 1$, and a feature count $m\in \{1,\dots ,p\}$. Choosing $m=p$ disables feature randomization.

For every tree index $b\in \{1,\dots ,B\}$, draw $n$ independent uniform indices $I_{b1},\dots ,I_{bn}$ from $\{1,\dots ,n\}$ and put $N_{bi}=\mathrm{\mid }\{r:I_{br}=i\}\mathrm{\mid }$. For every possible binary node address $\nu$ of depth less than $d_{\max }$, draw a subset $M_{b,\nu }$ uniformly from the $m$-element subsets of $\{1,\dots ,p\}$. All bootstrap-index and feature-subset draws are mutually independent across trees, index positions, and node addresses. Write ${\mathrm{\Theta }}_b=(N_{b1},\dots ,N_{bn},(M_{b,\nu }{)}_{\nu })$; thus the ${\mathrm{\Theta }}_b$ are independent with a common law conditional on the fixed data and chosen settings.

At a node with bootstrap position set $I$, define ${\bar{y}}_I=\mathrm{\mid }I{\mathrm{\mid }}^{-1}{\sum }_{r\in I}{y}_{I_{br}}$ in regression. In classification define $q_{Ik}=\mathrm{\mid }I{\mathrm{\mid }}^{-1}\mathrm{\mid }\{r\in I:y_{I_{br}}=c_k\}\mathrm{\mid }$ and choose one fixed impurity, either misclassification $1-{\max }_k{q}_{Ik}$, Gini $1-{\sum }_k{q}_{Ik}^2$, or entropy $-{\sum }_k{q}_{Ik}\log q_{Ik}$, with $0\log 0=0$.

For tree $b$, write the resampled rows as $D_b^{\ast }=((x_{I_{br}},y_{I_{br}}){)}_{r=1}^n$, so bootstrap positions remain distinct even when they contain the same original row. Build $T_b$ from $D_b^{\ast }$, starting at the root with position set $I=\{1,\dots ,n\}$. At a node of depth $d<d_{\max }$, form the candidate midpoint thresholds between consecutive distinct observed values using the coordinates in that node's set $M_{b,\nu }$. A candidate at coordinate $j$ and threshold $t$ partitions the current bootstrap positions into $I_L=\{r\in I:x_{I_{br},j}\le t\}$ and $I_R=\{r\in I:x_{I_{br},j}>t\}$; only candidates with both children nonempty are used. Score each candidate by ${\sum }_{r\in I_L}(y_{I_{br}}-{\bar{y}}_{I_L}{)}^2+{\sum }_{r\in I_R}(y_{I_{br}}-{\bar{y}}_{I_R}{)}^2$ in regression or by $\mathrm{\mid }{I}_L\mathrm{\mid }{Q}_{I_L}+\mathrm{\mid }{I}_R\mathrm{\mid }{Q}_{I_R}$ in classification, where $Q$ is the chosen impurity. Select a candidate of least score, breaking ties by coordinate index and then cut index, and recurse on its two children. If $d=d_{\max }$ or there is no candidate, make the node a leaf. When $m=p$, this is the greedy CART growth procedure on the bootstrap sample; when $m<p$, the same procedure restricts each node's candidate coordinates to its sampled subset. Each regression leaf predicts its sample mean; each classification leaf predicts its most frequent class, choosing the least class index in a tie. Define $h(x,{\mathrm{\Theta }}_b)$ by following the unique tree path for $x$.

For regression, the finite-forest prediction is $B^{-1}{\sum }_{b=1}^{B}h(x,{\mathrm{\Theta }}_b)$. For classification, it is the class receiving the largest number of votes, with the least class index breaking ties. For a training observation $i$, let $O_i=\{b:N_{bi}=0\}$. Its out-of-bag prediction is formed using only trees indexed by $O_i$, with the same regression average or classification vote rule; if $O_i=\mathrm{\varnothing }$, no out-of-bag prediction is returned. An out-of-bag prediction is a diagnostic computed from this finite forest, not an exact identity for its full-forest prediction or risk.

The data flow is shown below. The arrows mean that the same fixed $D$ and the independent randomization vector determine each tree, and the stated aggregation combines the resulting predictions; the diagram records the procedure and is not a proof of a performance claim.

diagram failed to render:
\begin{tikzpicture}[>=stealth]
  \node[draw,rounded corners] (data) at (0,0) {fixed data $D$};
  \node[draw,rounded corners] (random) at (0,-1.2) {IID $\Theta_b$};
  \node[draw,rounded corners] (tree) at (3,-0.6) {$T_b(x)=h(x,\Theta_b)$};
  \node[draw,rounded corners] (aggregate) at (6,-0.6) {vote or average over $b=1,\ldots,B$};
  \draw[->] (data) -- (tree);
  \draw[->] (random) -- (tree);
  \draw[->] (tree) -- (aggregate);
\end{tikzpicture}

Finite tree structure, leaf predictions, and classification impurities

Greedy CART split scores, midpoint candidates, and deterministic ties

Breiman, “Random Forests,” §§1, 3.1, and 11, printed pp. 5–7, 11, and 25–26

Hastie, Tibshirani, and Friedman, The Elements of Statistical Learning, §15.2, Algorithm 15.1, and §15.3.1, printed pp. 587–593

Fix a finite training dataset and a classifier $h(x,\theta )$ taking values in an ordered finite class set $\mathcal{C}=\{c_1<\cdots <c_J\}$ with $J\ge 2$. Let ${\mathrm{\Theta }}_1,{\mathrm{\Theta }}_2,\dots$ be IID random elements of a measurable space $(\mathsf{T},\mathcal{T})$ with common law $Q$. Regard the sequence as a random element of $({\mathsf{T}}^{\mathbb{N}},{\mathcal{T}}^{\otimes \mathbb{N}})$ and assume it is independent of a test pair $(X,Y)$ with law $P$ on $\mathcal{X}\times \mathcal{C}$. Assume $h$ is jointly measurable in $(x,\theta )$. For $j\in \{1,\dots ,J\}$ define $p_j(x)=Q\{\theta :h(x,\theta )=c_j\}$, and let

For each $B\ge 1$, let $G_B(x)$ be the class with the largest number of votes among $h(x,{\mathrm{\Theta }}_1),\dots ,h(x,{\mathrm{\Theta }}_B)$, choosing the least class index in a tie. Define the finite-forest conditional risk by

If $P\{(x,y):m(x,y)=0\}=0$, then, almost surely with respect to the IID tree-randomization sequence,

Breiman, “Random Forests,” Theorem 1.2 and Appendix I, printed pp. 7 and 29–30

Hastie, Tibshirani, and Friedman, The Elements of Statistical Learning, §15.2, printed pp. 587–593; used for the forest construction, not as a proof of this risk limit

Fix a finite training dataset and a classifier $h(x,\theta )$ taking values in an ordered finite class set $\mathcal{C}=\{c_1<\cdots <c_J\}$ with $J\ge 2$. Assume $h$ is jointly measurable on the product of the test-feature space and the randomization space. Let $Z=(X,Y)$ be a test pair with $Y\in \mathcal{C}$ and test law $P$. Let $\mathrm{\Theta },{\mathrm{\Theta }}^{\mathrm{\prime }}$ be independent randomizations with common law $Q$, and assume the pair $(\mathrm{\Theta },{\mathrm{\Theta }}^{\mathrm{\prime }})$ is independent of $Z$. For $j\in \{1,\dots ,J\}$ define $p_j(x)=Q\{\theta :h(x,\theta )=c_j\}$. For $y=c_k$, let $\widehat{j}(x,y)$ be the least index attaining ${\max }_{j\mathrm{\ne }k}{p}_j(x)$, and define the limiting margin

Assume $s>0$. For a tree randomization $\theta$, define the raw margin $r_{\theta }(x,y)=\mathbf{1}\{h(x,\theta )=y\}-\mathbf{1}\{h(x,\theta )=c_{\widehat{j}(x,y)}\}$ and $sd(\theta )=\sqrt{{\mathrm{Var}}_P(r_{\theta }(Z))}$. Put $d={\mathbb{E}}_Q[sd(\mathrm{\Theta })]$. If $d=0$, then $P\{m(Z)<0\}=0$. If $d>0$, define

Then $\rho \ge 0$ and

The covariance formula for $\rho$ is Breiman's weighted mean raw-margin correlation written without undefined zero-standard-deviation correlation terms.

Breiman, “Random Forests,” Definitions 2.1–2.2 and Theorem 2.3, printed pp. 8–9

Hastie, Tibshirani, and Friedman, The Elements of Statistical Learning, §15.4, printed pp. 597–602; used for the variance/correlation context, not as a proof of this bound

Fix a finite training dataset and a jointly measurable real-valued tree predictor $h(x,\theta )$. Let $Z=(X,Y)$ have test law $P$. Let $\mathrm{\Theta },{\mathrm{\Theta }}^{\mathrm{\prime }}$ be independent randomizations with common law $Q$, assume the pair $(\mathrm{\Theta },{\mathrm{\Theta }}^{\mathrm{\prime }})$ is independent of $Z$, and assume ${\mathbb{E}}_P{Y}^2<\mathrm{\infty }$ and $h(X,\mathrm{\Theta })\in L^2(P\times Q)$. For every allowed tree randomization $\theta$, assume $h(X,\theta )\in L^2(P)$ and ${\mathbb{E}}_{P}Y={\mathbb{E}}_{P}h(X,\theta )$. Put $e_{\theta }(Z)=Y-h(X,\theta )$ and $sd(\theta )=\sqrt{{\mathrm{Var}}_P(e_{\theta }(Z))}$. Define

$P{E}^{\ast }(\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{t})={\mathbb{E}}_P{(Y-{\mathbb{E}}_{Q}h(X,\mathrm{\Theta }))}^2$

$P{E}^{\ast }(\mathrm{t}\mathrm{r}\mathrm{e}\mathrm{e})={\mathbb{E}}_Q{\mathbb{E}}_P{e}_{\mathrm{\Theta }}(Z{)}^2$

$d={\mathbb{E}}_Q[sd(\mathrm{\Theta })]$

If $d=0$, then both risks are zero. If $d>0$, define

Then $\rho \ge 0$ and

The covariance formula for $\rho$ is Breiman's weighted mean residual correlation written without undefined zero-standard-deviation correlation terms.

Breiman, “Random Forests,” Theorem 11.2, printed pp. 25–26

Hastie, Tibshirani, and Friedman, The Elements of Statistical Learning, §§15.1 and 15.4.1–15.4.3, printed pp. 587, 597–602; used for the regression forest and variance/correlation context, not as a proof of this bound