Honest Leaf Estimation After Tree Construction

Why Separate Tree Construction from Leaf Estimation?

A regression tree adapts its partition to the data: split locations and even the number of leaves may be chosen after examining the sample. That flexibility can make a leaf’s fitted mean optimistic if the same outcomes both selected the tree and estimated its leaf values. Honest estimation separates these tasks: one sample constructs the partition, and an independent sample estimates the values within its leaves.

The separation gives a precise conditional guarantee. Once the construction sample is held fixed, the partition is fixed too. The estimation observations that fall in any particular leaf can then be treated as a sample from the population restricted to that leaf. Their mean estimates the leaf’s population mean without bias. This is a statement about a cellwise target, not necessarily about the regression function at every point in the cell.

Definition and Conditional Targets

Because \(D_E\) and \(D_S\) are independent and the population distribution is fixed, conditioning on \(D_S\) simply treats the realized leaf \(A\) as fixed. We assume \(E[Y^2]<\infty\), so the conditional means and variances used below exist whenever the cell has positive probability. We do not assign a value to \(\hat\mu_A\) when \(N_A=0\); any fallback rule for an empty leaf must be analyzed separately.

Write \(m(x)=E[Y\mid X=x]\), when a version of this conditional expectation is defined. The cell target is an average of the regression function over the predictor distribution in the leaf:

This identity follows from iterated expectation. It also indicates an important distinction: unless \(m(x)\) is constant on \(A\), the target \(\mu_A\) need not equal \(m(x)\) for a particular \(x\in A\).

Conditional Unbiasedness and Variance

The conditioning on the count matters: these formulas describe the estimate when the leaf contains exactly \(k\) estimation observations. They do not assert that a leaf with no observations has an unbiased estimate.

Proof. Conditional on \(D_S\), the leaf \(A\) is fixed. Each estimation observation has probability \(p_A=P(X\in A\mid D_S)>0\) of landing in \(A\). Given that exactly \(k\) observations land there, the \(k\) responses associated with those observations have the conditional distribution of \(Y\) given \(X\in A,D_S\), independently. This follows from iid sampling: conditioning on which indices fall in \(A\) gives independent observations, each restricted to \(A\); the resulting distribution of their responses is the same for every possible set of \(k\) indices. Averaging over the possible index sets does not change the distribution of their sample mean.

Thus, under the stated conditioning, \(\hat\mu_A\) is the mean of \(k\) independent responses with mean \(\mu_A\) and variance \(\sigma_A^2\). Linearity of expectation gives \(E[\hat\mu_A\mid D_S,N_A=k]=k^{-1}(k\mu_A)=\mu_A\). Independence gives \(\operatorname{Var}(\hat\mu_A\mid D_S,N_A=k)=k^{-2}(k\sigma_A^2)=\sigma_A^2/k\).

The proof relies on the estimation sample being independent of the construction sample. It does not require the tree-building method to be simple or nonadaptive: conditional on \(D_S\), its realized partition is fixed. It does require that the outcomes in \(D_E\) have not been used to choose that partition.

Pointwise Prediction Error: Variance Plus Approximation Bias

A tree prediction is often evaluated at a particular predictor value \(x\), not against the leaf average. If \(x\in A\), then conditional on \(D_S\) and \(N_A=k\), the estimator still has mean \(\mu_A\). Its conditional mean squared error for predicting \(m(x)\) separates into a sampling-variance term and a squared difference between the cell target and the pointwise regression value.

Derivation. Add and subtract \(\mu_A\), then expand the square: \[ E[(\hat\mu_A-m(x))^2\mid D_S,N_A=k] =E[(\hat\mu_A-\mu_A)^2\mid D_S,N_A=k] +2(\mu_A-m(x))E[\hat\mu_A-\mu_A\mid D_S,N_A=k] +(\mu_A-m(x))^2. \] The middle term is zero by conditional unbiasedness. The first term is the conditional variance, \(\sigma_A^2/k\). Substitution gives the claimed identity. The second term is an approximation error from representing all points in a leaf by one constant; honesty removes neither this term nor the variation of \(m(x)\) within the leaf. \(\square\)

This decomposition helps keep two sources of error distinct. Increasing the number of estimation observations in a leaf reduces its sampling variance. Changing the partition can change both the cell variance and the gap between \(\mu_A\) and \(m(x)\). The latter is a property of the cell and regression function, not a failure of conditional unbiasedness.

Random Leaf Counts and Empty Cells

Even with a fixed partition, \(N_A\) is random because estimation predictors are random. Conditional on \(D_S\), it has a binomial distribution with parameters \(n\) and \(p_A=P(X\in A\mid D_S)\). Consequently,

An empty leaf makes the sample mean undefined. A procedure may discard the leaf, merge it, or use a fallback value, but the theorem does not give that fallback an unbiasedness guarantee. For a positive count, the variance decreases as \(1/N_A\). If we condition only on the event \(N_A>0\), then the estimate remains unbiased for \(\mu_A\), and its variance is \(\sigma_A^2 E[1/N_A\mid D_S,N_A>0]\). To see this, condition first on each possible positive count \(k\): the conditional mean is always \(\mu_A\) and the conditional variance is \(\sigma_A^2/k\), so averaging over \(k\) leaves the mean unchanged and averages those variances.

What Honesty Guarantees—and a Common Pitfall

Honest estimation is useful because its guarantees are conditional on the realized, possibly complicated partition. The construction sample can choose split locations, tree depth, and pruning decisions; the estimation sample then supplies the leaf means without also having determined which partition looked favorable. This separation makes the leafwise mean and variance calculations transparent.

A common mistake is to say, “The leaf mean is unbiased, so it estimates the regression function at every point in that leaf.” The first clause is true only for the cellwise target \(\mu_A\), conditional on the construction sample and a positive leaf count. The correction is that the pointwise target \(m(x)\) can differ from \(\mu_A\); the resulting discrepancy appears explicitly as \((\mu_A-m(x))^2\) in the conditional prediction error.

A related mistake is to select a split using estimation outcomes and then apply the conditional theorem as if the selected partition were fixed independently. Conditioning on a partition that was chosen using those same outcomes can change the conditional distribution of the leaf responses. The independence argument in the proof no longer applies. A separate estimation sample avoids this particular selection effect; it does not by itself ensure a good partition, eliminate approximation error, or solve the empty-leaf problem.