Bagging and random forests — Examples

Use classification labels $0<1$ and the fixed training sample $D=((x_1,0),(x_2,1))$ with $x_1=(0,1)$ and $x_2=(1,0)$. Grow trees with depth cap $1$ and one uniformly selected feature at the root, along with the size-$2$ bootstrap samples in the bagged random-forest algorithm. Let ${\mathrm{\Theta }}_b$ be IID tree randomizations with common law $Q$, write $p_c(x)=Q\{h(x,{\mathrm{\Theta }}_b)=c\}$, and define $m(x,y)=p_y(x)-{\max }_{c\mathrm{\ne }y}{p}_c(x)$. Let the test pair have the point-mass law at $(x^{\ast },Y)=((1\mathrm{/}4,1\mathrm{/}4),1)$, and for $B$ trees let $G_B(x)$ be their majority vote with class $0$ breaking a tie and $P{E}_B=\mathbf{1}\{G_B(x^{\ast })\mathrm{\ne }1\}$. Then each randomized tree predicts class $1$ at $x^{\ast }$ with probability $1\mathrm{/}2$, so $m(x^{\ast },1)=0$ and $P\{m(X,Y)<0\}=0$. For every odd $B$, $P{E}_B$ has expectation $1\mathrm{/}2$ over the tree randomizations; consequently it cannot converge almost surely to the strict-margin value $0$.

For a mixed bootstrap sample, the two possible root splits and their leaf labels are shown below. In each tree the left child is selected when the displayed feature is at most $1\mathrm{/}2$, and the right child otherwise. The test point lies in the left child of both trees, whose labels differ. The diagram records these two CART cases; the verification derives the risk from the finite randomization counts and does not rely on the diagram.

diagram failed to render:
\begin{tikzpicture}[level distance=10mm,sibling distance=18mm]
  \node[draw] at (0,0) {$x_1\le\tfrac12$}
    child {node[draw] {$0$}}
    child {node[draw] {$1$}};
  \node[draw] at (6,0) {$x_2\le\tfrac12$}
    child {node[draw] {$1$}}
    child {node[draw] {$0$}};
\end{tikzpicture}

Bootstrap and randomized-feature construction

Risk limit with the zero-margin hypothesis

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

Take the classification sample $D=((0,0),(1,1))$ with ordered labels $0<1$, grow depth-zero trees, and use $B=2$ bootstrap trees. A tree is out of bag for observation $1$ exactly when its bootstrap count for training index $1$ is zero. On the event that the first bootstrap count vector is $(2,0)$ and the second is $(0,2)$, the full forest receives one vote for each class and predicts $0$ by the least-index tie rule. The out-of-bag set for observation $1$ is then $\{2\}$, so its out-of-bag prediction is $1$. This event has probability $1\mathrm{/}16$, and it exhibits a finite-forest out-of-bag prediction that differs from the full finite-forest prediction.

Bootstrap counts, class ties, and out-of-bag predictions

Classification leaf predictions

Breiman, “Random Forests,” §3.1 and Appendix II, printed pp. 11 and 31–32

Hastie, Tibshirani, and Friedman, The Elements of Statistical Learning, §15.3.1, printed pp. 592–593

Let $X\in \{0,1\}$, $Y=X$, with $P(X=0,Y=0)=3\mathrm{/}4$ and $P(X=1,Y=1)=1\mathrm{/}4$. Conditional on fixed training data, let each randomized tree independently be the constant class-$0$ stump with probability $3\mathrm{/}4$ and the constant class-$1$ stump with probability $1\mathrm{/}4$. For a randomization $\theta$, write $p_c(x)=Q\{h(x,\theta )=c\}$; for $y\in \{0,1\}$ define $m(x,y)=p_y(x)-p_{1-y}(x)$, $s=\mathbb{E}[m(X,Y)]$, and $P{E}^{\ast }=P\{m(X,Y)<0\}$. For each tree set $r_{\theta }(x,y)=\mathbf{1}\{h(x,\theta )=y\}-\mathbf{1}\{h(x,\theta )=1-y\}$ and $sd(\theta )=\sqrt{{\mathrm{Var}}_{X,Y}(r_{\theta }(X,Y))}$. For independent randomizations $\mathrm{\Theta },{\mathrm{\Theta }}^{\mathrm{\prime }}$ let $d={\mathbb{E}}_{Q}sd(\mathrm{\Theta })$ and $\rho ={\mathbb{E}}_{Q\times Q}[{\mathrm{Cov}}_{X,Y}(r_{\mathrm{\Theta }},r_{{\mathrm{\Theta }}^{\mathrm{\prime }}})]\mathrm{/}{d}^2$. Then the limiting margins at the two test pairs are $m(0,0)=1\mathrm{/}2$ and $m(1,1)=-1\mathrm{/}2$, so $s=1\mathrm{/}4$ and $P{E}^{\ast }=1\mathrm{/}4$. Each tree's raw-margin standard deviation is $\sqrt{3\mathrm{/}4}$, the covariance numerator defining $\rho$ is $3\mathrm{/}16$, and $\rho =1\mathrm{/}4$. The strength-correlation bound has right-hand side $15\mathrm{/}4$ in this example.

Strength, raw margins, and the correlation bound

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