From Subsampled Trees to a U-Statistic
A forest can be viewed as an average of predictions from trees trained on subsets of the observed data. When the average includes every subset of a fixed size, it has a precise statistical structure: it is a U-statistic. This connection is useful because it separates the tree-building rule from the way subsamples are combined. It also gives a direct way to understand what changes when computation allows only a random selection of the subsamples.
Let \(Z_1,\ldots,Z_n\) be independent and identically distributed observations, where \(Z_i\) contains the variables used to train the tree. Fix a prediction point \(x\) and a subsample size \(s\), with \(1\leq s\leq n\). For a set of indices \(I\subseteq\{1,\ldots,n\}\) of size \(s\), write \(Z_I\) for the observations in that subset. A tree trained on \(Z_I\) returns a prediction at \(x\).
If the tree-building procedure uses randomization, denote its random input by \(\omega\), and write its prediction as \(T(x;Z_I,\omega)\). For the moment, average over that randomization and define the subset-level prediction \(h_x(Z_I)=E_{\omega}[T(x;Z_I,\omega)]\). If the tree procedure is already deterministic, this expectation simply leaves its prediction unchanged.
Symmetry matters because a subset is a set of observations, not an ordered list. Many tree algorithms do not depend on the order in which the training observations are presented, in which case the randomized prediction kernel \(h_x\) is symmetric. If an algorithm can depend on presentation order, its symmetrized kernel is \(h_x^{\mathrm{sym}}(z_1,\ldots,z_s)=\frac{1}{s!}\sum_{\pi}h_x(z_{\pi(1)},\ldots,z_{\pi(s)})\), where the sum is over all permutations \(\pi\) of \(1,\ldots,s\). This is symmetric by construction. Averaging this kernel over subsets gives the same average as averaging the original ordered kernel over every ordering of every subset.
Thus the all-subsets forest prediction is a U-statistic when its subset-level prediction is represented by a fixed symmetric kernel. The kernel may depend on the prediction point \(x\), but for a fixed \(x\) it is a function of \(s\) observations. This representation does not assert that every fitted forest is a U-statistic: the averaging over subsets and the definition of the kernel must meet these conditions.
Worked Examples of the Representation
Worked Example: Counting and Averaging Every Subsample
Suppose \(n=5\) observations are available and each tree uses \(s=3\). The number of distinct training subsets is \(\binom{5}{3}=10\), not 3. Suppose the kernel predictions at a fixed \(x\) for the ten subsets are as follows.
| Subset | Kernel prediction | Subset | Kernel prediction |
|---|---|---|---|
| \(\{1,2,3\}\) | 2 | \(\{1,2,4\}\) | 4 |
| \(\{1,2,5\}\) | 1 | \(\{1,3,4\}\) | 5 |
| \(\{1,3,5\}\) | 3 | \(\{1,4,5\}\) | 6 |
| \(\{2,3,4\}\) | 2 | \(\{2,3,5\}\) | 7 |
| \(\{2,4,5\}\) | 4 | \(\{3,4,5\}\) | 6 |
The predictions sum to \(2+4+1+5+3+6+2+7+4+6=40\). Since there are ten subsets, the all-subsets forest prediction is \(40/10=4\). The denominator counts subsets; it is not the subsample size \(s=3\).
Worked Example: A Kernel That Reduces to the Sample Mean
For five observed responses \(y_1=1,y_2=2,y_3=4,y_4=7,y_5=11\), consider the order-three kernel \(h(y_a,y_b,y_c)=(y_a+y_b+y_c)/3\). This is a symmetric kernel: permuting the three responses does not change their average.
There are \(\binom{5}{3}=10\) subsets. Each response appears in exactly \(\binom{4}{2}=6\) of them, because once that response is included, the other two can be chosen from the remaining four in six ways. Therefore, the sum of all ten kernel values is \(\frac{1}{3}\,6(y_1+y_2+y_3+y_4+y_5)=2(1+2+4+7+11)=50\).
Dividing by ten gives \(U_{5,3}=50/10=5\). The sample mean is also \((1+2+4+7+11)/5=5\). Here the U-statistic equals the sample mean because this particular kernel averages its arguments. A general tree-prediction kernel need not have this special form, so its U-statistic need not reduce to a simple average of individual responses.
Worked Example: An Incomplete Average
Use the ten kernel predictions in the first example, whose complete average is 4. Suppose computation uses only four subsets, with predictions 2, 5, 7, and 6. Their average is \((2+5+7+6)/4=5\), which is one realization of an incomplete-subset estimate. It differs from the complete average by \(5-4=1\).
The difference does not show that the complete average was calculated incorrectly. The four selected predictions are only a sample from the ten possible subset predictions. If four subsets are drawn independently and uniformly with replacement, their average has conditional expectation 4, even though a particular draw, such as this one, can give 5.
Population Target and Unbiasedness
A U-statistic has a corresponding population quantity. Suppose \(Z_1,\ldots,Z_s\) are independent observations from the common distribution of the data, and assume \(h_x(Z_1,\ldots,Z_s)\) is integrable. Define \(\theta_s(x)=E[h_x(Z_1,\ldots,Z_s)]\). Integrability ensures this expectation exists; in regression settings, for example, it is enough that the absolute expectation of the prediction kernel is finite.
Proof. By the definition of the U-statistic and linearity of expectation, \(E[U_{n,s}(x)]=\binom{n}{s}^{-1}\sum_{|I|=s}E[h_x(Z_I)]\). For each fixed subset \(I\), the \(s\) observations in \(Z_I\) have the same joint distribution as \(s\) independent observations from the common data distribution. Hence every expectation in the sum equals \(\theta_s(x)\). There are exactly \(\binom{n}{s}\) subsets, so the sum equals \(\binom{n}{s}\theta_s(x)\), and division by \(\binom{n}{s}\) gives the result. \(\square\)
This theorem concerns the expectation over repeated data sets. It does not say that a particular observed forest prediction equals \(\theta_s(x)\), nor that \(\theta_s(x)\) must equal the regression function \(E[Y\mid X=x]\). Those are separate questions about the prediction rule and its statistical properties.
What Incomplete Subsampling Changes
When \(\binom{n}{s}\) is large, computing every subset prediction may be impractical. Let \(N=\binom{n}{s}\), and, conditional on the observed data, draw \(I_1,\ldots,I_M\) independently and uniformly from the \(N\) subsets, with replacement. The incomplete estimator is \(\widetilde U_{M,n,s}(x)=M^{-1}\sum_{m=1}^{M}h_x(Z_{I_m})\).
Proof. Given the data, each sampled subset prediction \(A_m=h_x(Z_{I_m})\) is drawn uniformly from the fixed list of \(N\) values \(a_I=h_x(Z_I)\). Its conditional mean is \(N^{-1}\sum_{|I|=s}a_I=U_{n,s}(x)\). Linearity of conditional expectation then gives \(E[M^{-1}\sum_m A_m\mid Z_1,\ldots,Z_n]=U_{n,s}(x)\).
The draws are conditionally independent because the subsets are sampled independently with replacement. Therefore the conditional variance of their average is \(M^{-1}\operatorname{Var}(A_1\mid Z_1,\ldots,Z_n)\). The variance of a uniform draw from the finite list is \(N^{-1}\sum_{|I|=s}(a_I-U_{n,s}(x))^2\). Substitution gives the displayed variance formula. \(\square\)
The result quantifies the trade-off: increasing \(M\) reduces the conditional variance from subset selection in proportion to \(1/M\), while \(M=N\) with every subset included gives the complete average and no subset-selection variation. Uniform sampling without replacement also gives an unbiased estimate of the complete average; its variance is reduced by the finite-population correction. The formula above specifically assumes independent draws with replacement.
If each selected subset produces a randomized tree rather than the randomization-averaged prediction \(h_x(Z_I)\), there is an additional source of variation. Suppose the tree randomizations are independent across draws and have finite conditional variances. Then the conditional variance of the averaged tree predictions equals \(\frac{1}{M}\left\{\operatorname{Var}_{I}(h_x(Z_I)\mid Z_1,\ldots,Z_n)+E_I[\operatorname{Var}_{\omega}(T(x;Z_I,\omega)\mid Z_I,Z_1,\ldots,Z_n)]\right\}\). The first term is variation across chosen subsets; the second is variation from the randomized tree rule within a chosen subset. Averaging more trees reduces both Monte Carlo contributions, but does not change the definition of the complete all-subsets U-statistic.
Common Pitfall and Practical Meaning
A common mistake is to call any forest average a U-statistic merely because its trees use subsamples. That reasoning skips the requirements on the kernel and the averaging scheme. For the standard representation, the subset-level rule must be a fixed, measurable symmetric function of the \(s\) observations, and the complete U-statistic averages that rule over all size-\(s\) subsets. If the tree rule is order-dependent, symmetrize it or explicitly average over orderings. If only some subsets are used, the result is an incomplete estimate of the complete U-statistic, not that complete U-statistic itself.
The distinction is useful in both theory and computation. The U-statistic representation identifies the exact target of all-subsets averaging and makes its expectation transparent. Incomplete subsampling can approximate that average at lower computational cost, but a finite run introduces additional variation. In applications, report the subsample size and the number of subsets or trees actually averaged; these determine which quantity was computed and how much Monte Carlo variability remains.
Check Your Understanding
Use the definitions and results above to answer the following questions.
- For \(n=8\) and subsample size \(s=2\), how many terms are in the complete U-statistic?
- Why is symmetrization needed if a tree’s output can depend on the order in which its training observations are presented?
- Under what assumptions does the expectation of the complete forest equal the population quantity \(\theta_s(x)\)?
- For incomplete subsampling with replacement, what does the conditional expectation equal, and what controls its conditional variance?
- Why does using \(M\) randomly selected subsets not generally produce the same numerical prediction as averaging all \(\binom{n}{s}\) subsets?