Random Forest Predictors as Randomized Averages

Why a Forest Is an Average

A regression tree gives a prediction at a query point $x$, but its value can depend on choices made while fitting it. A fitting procedure may select a bootstrap sample or subsample, consider random subsets of predictors, or use random tie-breaking. A random forest combines predictions from trees produced under such random choices. To understand what the forest estimates, it is important to say which randomness is being averaged over.

We will condition on the observed training data first. This keeps variation due to the data collected in a study separate from variation introduced by the forest algorithm. Within the algorithm, we will distinguish the selection of training observations from the random choices used to construct a tree. Finally, a practical forest uses finitely many trees, so its prediction is a Monte Carlo approximation to an average over the algorithm’s randomization.

Definition: Let $D_n$ denote the observed training data, and fix a query point $x$. A randomized regression tree predictor is a real-valued random variable $T(x;D_n,I,\xi)$, where $I$ denotes any random selection of training observations used for the tree and $\xi$ denotes random choices made in constructing the tree, conditional on $D_n$ and $I$. A regression forest predictor with $B$ trees is the arithmetic average of $B$ tree predictions. Its infinite-forest target, conditional on $D_n$, is $$ m_{D_n}(x)=E[T(x;D_n,I,\xi)\mid D_n]. $$

The notation allows for different procedures. If every tree uses all the observed data, then $I$ is fixed and only $\xi$ contributes algorithmic randomness. If trees use bootstrap samples or subsamples, then $I$ is random as well. The infinite-forest target averages over whichever random choices the specified procedure makes; it does not average over new training data unless that is explicitly part of the definition.

Three Sources of Variation

It is useful to separate three sources that can otherwise be conflated.

Tree-construction randomness: given $D_n$ and a selected training set $I$, the procedure may use random feature candidates, randomized split choices, or random tie-breaking. These choices are represented by $\xi$.
Training-sample selection: given the observed $D_n$, a tree may be fitted using a randomly drawn bootstrap sample or subsample. This selection is represented by $I$. It is algorithmic resampling of the observed data, not the original sampling that produced $D_n$.
Finite-forest Monte Carlo variation: a practical forest averages a finite number $B$ of randomized trees. Which random choices happen to appear among those $B$ trees affects the computed average.

These sources can be nested. For example, each tree may first receive a bootstrap sample and then use randomized split construction. A finite forest repeatedly draws both $I$ and $\xi$. If the tree-building rule is completely deterministic and always uses the full training set, the first two sources are absent, but a forest algorithm with no random choices then produces the same tree repeatedly.

The original training data can itself be regarded as random across repeated studies. That is a separate layer: the conditional target $m_{D_n}(x)$ changes when $D_n$ changes. Conditioning on $D_n$ is what allows us to discuss the forest algorithm’s randomization without mixing it with sampling variation in the data.

Worked Example: Averaging Random Tree Constructions

Fix the training data and query point. Suppose the tree uses one of two possible randomized constructions: it predicts $2$ with probability $3/4$, and $8$ with probability $1/4$. There is no random training-sample selection in this example.

The infinite-forest target is the expected prediction over tree construction: $$ m_{D_n}(x)=\frac{3}{4}(2)+\frac{1}{4}(8)=\frac{6+8}{4}=\frac{14}{4}=3.5. $$

Thus $3.5$ is not necessarily the prediction of any single tree. It is the average prediction under the specified random construction rule. A finite forest approximates this expectation by averaging the constructions that actually occurred.

Separating Selection and Construction

The two algorithmic sources can be separated using conditional expectations. For a fixed selected sample $I$, first average over tree construction. Then average those conditional means over the selection rule. The resulting identity is an application of iterated expectation, while the corresponding variance identity shows how much variation each layer contributes.

Theorem: Fix $D_n$ and $x$. Suppose $T=T(x;D_n,I,\xi)$ has a finite second moment conditional on $D_n$. Define $$ \mu_I=E[T\mid D_n,I], \qquad \sigma_I^2=\operatorname{Var}(T\mid D_n,I). $$ Then $$ E[T\mid D_n]=E[\mu_I\mid D_n] $$ and $$ \operatorname{Var}(T\mid D_n) =E[\sigma_I^2\mid D_n]+\operatorname{Var}(\mu_I\mid D_n). $$

The first identity says that the infinite forest can be computed by averaging the construction-randomized prediction for each possible selected sample, and then averaging over the sample-selection distribution. The second identity separates expected variation from tree construction, conditional on selection, from variation in the mean prediction across possible selected samples.

Proof. By iterated expectation, $$ E[T\mid D_n]=E[E[T\mid D_n,I]\mid D_n]=E[\mu_I\mid D_n]. $$ For the variance identity, write $\mu=E[T\mid D_n]=E[\mu_I\mid D_n]$. Decompose $$ T-\mu=(T-\mu_I)+(\mu_I-\mu). $$ Squaring and taking conditional expectation given $D_n$ gives $$ \operatorname{Var}(T\mid D_n) =E[(T-\mu_I)^2\mid D_n]+E[(\mu_I-\mu)^2\mid D_n] +2E[(T-\mu_I)(\mu_I-\mu)\mid D_n]. $$ The first term is $E[\sigma_I^2\mid D_n]$, and the second is $\operatorname{Var}(\mu_I\mid D_n)$. For the cross-term, condition first on $D_n,I$. Since $E[T-\mu_I\mid D_n,I]=0$ and $\mu_I-\mu$ is fixed under that conditioning, $$ E[(T-\mu_I)(\mu_I-\mu)\mid D_n,I] =(\mu_I-\mu)E[T-\mu_I\mid D_n,I]=0. $$ Averaging this zero conditional expectation over $I$ shows that the cross-term vanishes. This proves both identities. $\square$

Worked Example: Quantifying Both Algorithmic Sources

For a fixed $D_n$ and $x$, suppose the selection rule chooses $I=1$ or $I=2$, each with probability $1/2$. Given $I=1$, tree construction gives predictions $0$ and $2$, each with probability $1/2$. Given $I=2$, construction gives predictions $8$ and $10$, each with probability $1/2$.

For $I=1$, the conditional mean is $\mu_1=(0+2)/2=1$, and the conditional variance is $\sigma_1^2=((0-1)^2+(2-1)^2)/2=1$. For $I=2$, $\mu_2=(8+10)/2=9$, and $\sigma_2^2=((8-9)^2+(10-9)^2)/2=1$. The overall mean is $(1+9)/2=5$.

The expected within-selection variance is $(1+1)/2=1$. The variance of the two conditional means is $((1-5)^2+(9-5)^2)/2=16$. Therefore the total variance is $1+16=17$. Directly, the four possible predictions $0,2,8,10$ are equally likely, and their variance about $5$ is $(25+9+9+25)/4=17$. Most of the variation here comes from which training sample is selected, not from construction randomness conditional on that selection.

What a Finite Forest Estimates

A practical forest uses $B$ randomized trees. Write their predictions at $x$ as $T_1(x),\ldots,T_B(x)$, and their average as $$ \widehat m_{B,D_n}(x)=\frac{1}{B}\sum_{b=1}^{B}T_b(x). $$ When the trees are generated by independent repetitions of the same randomization procedure, conditional on $D_n$, this average is an unbiased Monte Carlo estimate of $m_{D_n}(x)$. Its variability is due to the finite number of draws, even though the training data are held fixed.

Theorem: Fix $D_n$ and $x$. Suppose $T_1(x),\ldots,T_B(x)$ are conditionally independent and identically distributed given $D_n$, with finite conditional mean $m_{D_n}(x)$ and variance $v_{D_n}(x)$. Then $$ E[\widehat m_{B,D_n}(x)\mid D_n]=m_{D_n}(x), \qquad \operatorname{Var}(\widehat m_{B,D_n}(x)\mid D_n)=\frac{v_{D_n}(x)}{B}. $$

Proof. Linearity of conditional expectation gives $$ E[\widehat m_{B,D_n}(x)\mid D_n] =\frac{1}{B}\sum_{b=1}^{B}E[T_b(x)\mid D_n] =\frac{1}{B}\sum_{b=1}^{B}m_{D_n}(x) =m_{D_n}(x). $$ Conditional independence makes the covariances between distinct tree predictions zero. Hence $$ \operatorname{Var}(\widehat m_{B,D_n}(x)\mid D_n) =\frac{1}{B^2}\sum_{b=1}^{B}\operatorname{Var}(T_b(x)\mid D_n) =\frac{Bv_{D_n}(x)}{B^2} =\frac{v_{D_n}(x)}{B}. $$ This proves the result. $\square$

The conditional standard deviation of the finite-forest prediction is therefore $\sqrt{v_{D_n}(x)/B}$. Increasing $B$ reduces this Monte Carlo variation at the rate $B^{-1/2}$, but it does not change the target $m_{D_n}(x)$. The result requires conditional independence of the randomized tree draws; if trees are dependent, covariance terms must also be included in the variance of their average.

Worked Example: A Finite Forest as a Monte Carlo Estimate

Suppose, conditional on the training data and a fixed query, each randomized tree predicts $10$ with probability $0.3$ and $0$ with probability $0.7$. The infinite-forest prediction is $$ m_{D_n}(x)=0.3(10)+0.7(0)=3. $$

For one tree, the variance is $$ v_{D_n}(x)=0.3(10-3)^2+0.7(0-3)^2 =0.3(49)+0.7(9)=14.7+6.3=21. $$ With $B=7$ conditionally independent trees, the finite-forest prediction has conditional variance $21/7=3$ and conditional standard deviation $\sqrt{3}$.

If a particular run contains two predictions of $10$ and five predictions of $0$, its average is $(2(10)+5(0))/7=20/7$, about $2.857$, rather than $3$. This difference is a realized finite-simulation discrepancy, not a change in the infinite-forest target.

Why the Distinction Matters

The decomposition clarifies what a prediction or uncertainty statement refers to. Holding $D_n$ fixed and averaging over tree randomization describes the algorithmic target. Averaging over random selections of training observations adds another layer of algorithmic variation. Using only $B$ trees adds Monte Carlo variation around the resulting target. Variation across newly collected training samples is different again: it concerns how the conditional target itself changes with the data.

A common mistake is to call the prediction from a finite forest “the expectation over trees.” It is an estimate of that expectation, and in a particular run it may differ from it. A related mistake is to treat bootstrap selection as the same thing as finite-forest Monte Carlo error. Bootstrap selection is one random input to an individual tree; finite-forest error arises because only finitely many randomized trees are averaged. Repeating more trees reduces the latter under the independence assumptions above, while the selection randomness remains part of the distribution of an individual tree and of the infinite-forest average.

These distinctions are useful when describing an algorithm precisely, comparing forests built with different randomization rules, or diagnosing whether a prediction changes because the training data changed or because a different finite set of trees was generated. They also establish the basic conditional-average viewpoint used in later analyses of forest predictions.

Key takeaway: A regression forest is an average of randomized tree predictions. State what is held fixed before taking that average: the observed data, the selected training sample, or the finite set of trees. These choices determine which sources of variation are included.

Check Your Understanding

Answer each question by identifying what is random and what is being conditioned on.

If every tree uses the full observed data but randomizes candidate split variables, which source of algorithmic randomness is present?
State the iterated-expectation identity that relates the mean tree prediction to the conditional mean given a selected training sample.
In the variance decomposition, what does the term $\operatorname{Var}(\mu_I\mid D_n)$ measure?
Under what conditions does the conditional variance of a finite forest equal the single-tree variance divided by $B$?
Explain why increasing the number of trees reduces finite-forest Monte Carlo variation without changing the infinite-forest target.