Bias-Variance Bounds from Forest Weights

Why Forest Weights Give a Useful Error Bound

A forest prediction at a query point \(x\) is a weighted average of training responses. That representation exposes two distinct sources of error. The responses may be noisy even when the weights select observations near \(x\); and the weights may put substantial mass on observations whose regression means differ from the mean at \(x\). A useful bound must keep these sources separate: response variance is controlled by squared weights, while regression-function bias is controlled by how far the weighted observations are from the query.

The separation requires care about how the weights were constructed. In particular, the response values used to estimate the leaf predictions must not also determine the weights in a way that destroys their conditional mean-zero residual property. Honesty provides a sufficient condition: conditional on the training covariates and the forest construction, the estimation responses have their stated conditional means and variances.

Setup and Conditional Decomposition

For the results below, assume the estimation responses are conditionally independent given \(\mathcal G\), with \(E[Y_i\mid\mathcal G]=m(X_i)\) and \(\operatorname{Var}(Y_i\mid\mathcal G)=\sigma^2(X_i)<\infty\). The weights are fixed given \(\mathcal G\). This is the relevant implication of honesty here: the randomness used to choose the weights does not use the estimation responses in a way that changes these conditional moments. If weights depend on those same responses, the decomposition below need not hold.

Write the conditional weighted bias as \(B_W(x)=\sum_i W_i(x)\{m(X_i)-m(x)\}\). The predictor's conditional mean is \(m(x)+B_W(x)\). Conditional independence makes the variance of the weighted response noise a sum of squared weights.

To prove the identity, decompose each response as \(Y_i=m(X_i)+\varepsilon_i\), where \(E[\varepsilon_i\mid\mathcal G]=0\). Then $$ \hat m(x)-m(x)=B_W(x)+\sum_{i=1}^n W_i(x)\varepsilon_i. $$ The conditional expectation of the second term is zero, so its cross-product with the fixed conditional bias has expectation zero. Conditional independence gives \(E[\varepsilon_i\varepsilon_j\mid\mathcal G]=0\) for \(i\ne j\), while \(E[\varepsilon_i^2\mid\mathcal G]=\sigma^2(X_i)\). Expanding the square therefore gives the stated bias square plus the sum of weighted variances. \(\square\)

Bounding the Bias and Variance

A smoothness condition converts bias into a localization measure. Suppose \(m\) is \(L\)-Lipschitz in a metric \(d\): for all relevant \(z,x\), \(|m(z)-m(x)|\leq Ld(z,x)\). By the triangle inequality and nonnegative normalized weights, $$ |B_W(x)|\leq L\sum_{i=1}^n W_i(x)d(X_i,x). $$ Squaring gives one useful bound. Jensen's inequality for the convex function \(t\mapsto t^2\), applied to the probability weights \(W_i(x)\), gives another, often looser, bound in terms of weighted squared distances.

The first inequality follows by bounding the absolute bias term by term and using the variance bound in the decomposition. For the second, Jensen gives \((\sum_i W_i d_i)^2\leq\sum_i W_i d_i^2\), where \(d_i=d(X_i,x)\). Thus the bias is small when the weights concentrate near \(x\), and the variance is small when no small set of observations carries too much weight.

The quantity \(N_{\mathrm{eff}}(x)=1/\sum_i W_i(x)^2\) is called the effective sample size of these weights. Since the weights sum to one, \(N_{\mathrm{eff}}(x)\geq1\); equal weights on \(k\) observations give \(N_{\mathrm{eff}}(x)=k\). Under the variance bound, the conditional response-variance contribution is at most \(\bar\sigma^2/N_{\mathrm{eff}}(x)\). A large effective sample size does not itself ensure small bias: the observations receiving those weights must also be well localized.

These statements hold conditionally for a realized set of weights. Taking expectations over covariates and construction randomness preserves the bounds after taking expectations of their right-hand sides. The squared-weight term concerns response noise conditional on the construction. If the prediction itself is randomized across forest constructions and the target is its unconditional risk, variation of the conditional prediction across constructions must also be accounted for; it is not the response-noise term in this decomposition.

From Conditional Bounds to Prediction Risk

The theorem targets the regression function \(m(x)\), the conditional mean response. If the goal is to predict a new response \(Y_0\) at \(x\), rather than estimate its mean, there is additional irreducible noise. Suppose \(Y_0\) is conditionally independent of the estimation responses given the construction, with mean \(m(x)\) and variance \(\sigma^2(x)\). Expanding around \(m(x)\), the cross-product has conditional expectation zero, so $$ E[(\hat m(x)-Y_0)^2\mid\mathcal G] = E[(\hat m(x)-m(x))^2\mid\mathcal G]+\sigma^2(x). $$ This distinction matters: even a predictor that equals \(m(x)\) exactly has response-prediction error \(\sigma^2(x)\), unless the response is conditionally deterministic.

The bound is useful for interpreting what forest-weight conditions accomplish. Localization controls the error from averaging regression means at nearby rather than identical covariates. Weight dispersion controls the response-noise cost. Neither property alone controls both terms, and the bound does not assert that either term vanishes without additional conditions on the sequence of forests and data.

Common Pitfall

• Wrong reasoning: “The weights are nonnegative and sum to one, so the forest prediction is unbiased for \(m(x)\).” Normalization only makes a weighted average. Its conditional expectation is \(\sum_i W_i(x)m(X_i)\), which need not equal \(m(x)\).
• Correction: The difference is exactly \(B_W(x)=\sum_iW_i(x)\{m(X_i)-m(x)\}\). It is controlled by smoothness together with localization, not by weight normalization alone.
• Another common slip: Replacing \(\sum_iW_i^2\sigma^2(X_i)\) by \(\sum_iW_i\sigma^2(X_i)\). The former is the variance of a weighted sum of conditionally independent responses; the squared weights are essential.

For a non-honest, response-adaptive weighting rule, one must also verify that conditional residuals still have mean zero given the weights. Without that condition, the displayed bias-variance identity is not justified merely by writing down normalized weights.