Tree Weights and Their Normalization Identities

Why Write a Forest as Weights?

A regression tree predicts at a query point by averaging responses from training observations that fall in the same terminal leaf. A forest averages predictions from randomized trees. Expressing these operations in terms of weights makes the connection explicit: each training response contributes to the prediction with a nonnegative coefficient, and those coefficients add to one. The resulting identities are useful for interpreting a prediction and checking a calculation.

The weights are generally data-dependent. In particular, if the tree-building procedure chooses splits using the responses, the weights can depend on the observed responses as well as on the predictors. The identities below are algebraic and remain true in that setting; they do not, by themselves, make the weights independent of the responses.

Tree and Forest Weights

Fix a training data set \(D=((X_1,Y_1),\ldots,(X_n,Y_n))\) and a query point \(x\). Let \(\Theta\) denote all randomness used to construct one tree, such as randomized feature selection or a random training sample. Once \(D\) and \(\Theta\) are fixed, the tree has a terminal leaf containing \(x\). Denote that leaf by \(L(x;D,\Theta)\).

For a tree that averages the training responses represented in each leaf, let \(M_i(\Theta)\) be the number of times observation \(i\) is represented in the tree’s training sample. For an ordinary unweighted tree fit on the full sample, \(M_i=1\). For a bootstrap tree, \(M_i\) is the bootstrap multiplicity. The leaf prediction is defined only when the leaf has positive total represented sample size.

The indicator in the numerator is one exactly when training observation \(i\) is assigned to the same terminal leaf as the query. Thus a tree gives zero weight to observations outside that leaf and to observations with zero multiplicity in its training sample. A forest can give positive weight to an observation if there is positive probability that a randomized tree assigns it positive weight.

Tree-Weight Identities

The main properties follow directly from the definition, provided the leaf contains at least one represented training observation. No assumption that the tree partition was chosen independently of the responses is needed for these pointwise identities.

Proof. Each multiplicity \(M_i(\Theta)\) is nonnegative, and the indicator is either zero or one. The denominator is positive by assumption. Hence every weight is nonnegative. Summing the numerators over \(i\) gives exactly the denominator: $$ \sum_{i=1}^n W_i(x;D,\Theta) = \frac{\sum_{i=1}^n M_i(\Theta)\mathbf{1}\{X_i\in L(x;D,\Theta)\}} {\sum_{j=1}^n M_j(\Theta)\mathbf{1}\{X_j\in L(x;D,\Theta)\}} =1. $$ The numerator for observation \(i\) is zero if its multiplicity is zero or it is not in the query leaf. Finally, a weighted sum with nonnegative weights summing to one is a convex combination. In particular, the tree prediction lies between the smallest and largest responses with positive tree weight. \(\square\)

For an unweighted tree fit on the full sample, this formula reduces to equal weights among the observations in the query leaf. If that leaf contains \(k\) training observations, each receives weight \(1/k\). Bootstrap multiplicities instead give repeated observations proportionally more weight.

Forest Weights and Conditional Expectations

Averaging over tree randomness preserves the same basic properties, provided the query leaf has positive represented sample size almost surely under the tree randomization. Conditional expectations here are taken over \(\Theta\), with \(D\) and \(x\) fixed. Since \(n\) is finite and each weight lies between zero and one, the expectations exist and can be interchanged with the finite sum.

Proof. Conditional expectation preserves nonnegativity, so \(\alpha_i\geq0\). By linearity of conditional expectation and the tree unit-sum identity, $$ \sum_{i=1}^n\alpha_i =\sum_{i=1}^n E_\Theta[W_i\mid D,x] =E_\Theta\!\left[\sum_{i=1}^n W_i\mid D,x\right] =E_\Theta[1\mid D,x]=1. $$ For the prediction identity, each \(Y_i\) is fixed when conditioning on the full data \(D\). Therefore, $$ m_D(x) =E_\Theta\!\left[\sum_{i=1}^n W_iY_i\mid D,x\right] =\sum_{i=1}^n E_\Theta[W_i\mid D,x]Y_i =\sum_{i=1}^n\alpha_iY_i. $$ If a weight is zero except on an event of probability zero, its conditional expectation is zero. This proves the support assertion. \(\square\)

It follows that \(m_D(x)\) also lies between the smallest and largest training responses with positive forest weight. The forest weights need not be equal: they record how often, and with what tree-specific weight, each observation contributes across the randomized trees.

Finite Forests and Support

A practical forest contains a finite number \(B\) of trees. Write their weights and predictions as \(W_i^{(b)}(x)\) and \(T^{(b)}(x)\), for \(b=1,\ldots,B\). The finite-forest weight is the average of the tree weights: $$ \widehat{\alpha}_{i,B}(x)=\frac{1}{B}\sum_{b=1}^B W_i^{(b)}(x). $$ Then, simply by rearranging finite sums, the forest prediction is $$ \widehat{m}_B(x)=\frac{1}{B}\sum_{b=1}^B T^{(b)}(x) =\sum_{i=1}^n\widehat{\alpha}_{i,B}(x)Y_i. $$ Each finite-forest weight is nonnegative, and the weights sum to one because each tree’s weights do. If each tree has the same conditional marginal distribution, given \(D,x\), as the single randomized tree used to define \(\alpha_i(x;D)\), then the expected finite-forest weights equal \(\alpha_i(x;D)\), whether or not the trees are independent: linearity of expectation gives \(E[\widehat{\alpha}_{i,B}\mid D,x]=\alpha_i\).

Support can be stated at two levels. For one tree, positive weight requires membership in the query leaf and positive multiplicity. For the forest, positive weight requires positive probability of positive tree weight. For a finite forest, it requires positive weight in at least one of the realized trees. Consequently, averaging cannot assign weight to an observation that receives zero weight in every component tree.

What the Identities Do Not Say

A common mistake is to infer that because the weights are nonnegative and sum to one, they are independent of the responses. That conclusion does not follow. A tree can select splits using the observed \(Y_i\), and those splits determine which observations share a leaf. In that case the weights themselves can change when the responses change. The equality \(m_D(x)=\sum_i\alpha_iY_i\) is still valid: it averages tree-specific weighted predictions with the weights calculated from the same data.

For the same reason, one cannot generally take an expectation over the responses by treating the weights as fixed. An expression such as \(E[\alpha_iY_i\mid X_1,\ldots,X_n]=\alpha_i E[Y_i\mid X_1,\ldots,X_n]\) is valid if \(\alpha_i\) is measurable given the conditioning variables. If \(\alpha_i\) and \(Y_i\) are conditionally independent given \(X_1,\ldots,X_n\), the valid factorization is \(E[\alpha_iY_i\mid X_1,\ldots,X_n]=E[\alpha_i\mid X_1,\ldots,X_n]E[Y_i\mid X_1,\ldots,X_n]\); more generally, this factorization holds when their conditional covariance is zero. The nonnegativity, unit-sum, support, and conditional-expectation identities established here require no such independence assumption; stronger response-conditional claims do.