Honesty and Conditional Tree Predictions

Why Separate Split Selection From Estimation?

A regression tree uses the observed data twice in conceptually different ways: it chooses regions of the predictor space, then assigns a prediction to each region. If the same responses influence both choices, a selected region may partly reflect unusually high or low noise in those responses. The resulting leaf average can look more extreme because of how the leaf was chosen.

Honesty addresses this issue by separating the data used to choose the partition from the data used to estimate its leaf values. Once the partition is fixed, the leaf-estimation observations can be treated as a fresh sample for estimating averages within its cells. The key result is conditional: a leaf average is unbiased for the mean response among observations whose covariates fall in that leaf. This is not automatically the same as the regression function at every point in the leaf.

Definition and Sampling Setup

Assume the estimation sample \((X_i,Y_i)\), \(i=1,\ldots,n\), consists of independent, identically distributed pairs and is independent of the structure sample. Write \(\mathcal T\) for the information that determines the partition. Conditional on \(\mathcal T\), a particular leaf is a fixed measurable region \(A=A(\mathcal T)\) in predictor space. Define its occupancy and leaf estimate by

The population target for this fixed cell is

provided \(P(X\in A)>0\) and \(E[|Y|]<\infty\). If a variance is also considered, assume \(E[Y^2]<\infty\). Because the estimation sample is independent of \(\mathcal T\), conditioning on \(\mathcal T\) fixes the region without changing the distribution of any estimation observation.

Conditional Unbiasedness for a Fixed Partition

The occupancy \(N_A\) is random even after the partition is fixed. A statement conditional on \(N_A=k\) is meaningful only when that conditioning event has positive probability. The next result makes this qualification explicit.

Proof. Fix \(\mathcal T\), so that \(A\) is fixed, and write \(p=P(X\in A\mid\mathcal T)>0\). Conditional on which \(k\) indices fall in \(A\), the observations at those indices have the distribution of \((X,Y)\) conditional on \(X\in A\). In particular, each such response has conditional mean \(\mu_A\). This follows from independence of the observations: for any specified set of indices, conditioning those covariates to lie in \(A\) leaves each selected pair distributed as the original pair restricted to \(X\in A\).

If the set of selected indices is not specified, condition on \(N_A=k\). This event is the disjoint union over all index sets of size \(k\) of the events that exactly those indices fall in \(A\). On each such event, the leaf average is the average of \(k\) responses, each with mean \(\mu_A\), so its conditional expectation is \( k^{-1}(k\mu_A)=\mu_A.\) Averaging this same conditional expectation over the possible index sets still gives \(\mu_A\). This proves the claim whenever \(P(N_A=k\mid\mathcal T)>0\). \(\square\)

Conditional on \(\mathcal T\), \(N_A\) has a binomial distribution with parameters \(n\) and \(p\). If \(0<p<1\), every \(k=0,\ldots,n\) has positive probability, so the theorem applies to \(k=1,\ldots,n\). If \(p=1\), only \(k=n\) is possible; if \(p=0\), no positive occupancy is possible and \(\mu_A\) is not defined by conditioning on \(X\in A\). These cases are why the positive-probability qualification is necessary.

Variance and Conditioning on the Covariates

The same sampling argument gives the variance of the leaf average. Let \(\sigma_A^2=\operatorname{Var}(Y\mid X\in A)\), assumed finite. For each possible positive occupancy \(k\), the \(k\) responses in the cell are conditionally independent with the distribution of \(Y\mid X\in A\). Hence

Derivation. Conditional on the selected index set, the average contains \(k\) independent responses, each with variance \(\sigma_A^2\). Therefore its variance is \( k^{-2}\sum_{j=1}^k \sigma_A^2=\sigma_A^2/k.\) This value does not depend on which indices were selected, so conditioning only on the occupancy gives the same variance. The result shows why a leaf with more estimation observations has less sampling variation, while the theorem above explains its conditional target.

There is a related, more granular statement. Define \(m(x)=E[Y\mid X=x]\), choosing a version of the conditional expectation. Given the estimation covariates and the partition, the conditional expectation of the leaf average is the average of the regression function at the covariates that landed in the leaf:

This follows by applying linearity of conditional expectation to the fixed set of included indices. It does not require the \(Y_i\) to be conditionally independent given the covariates for the expectation identity, though that independence is part of the i.i.d. sampling setup here. This conditional-on-covariates target is generally a sample average of \(m(X_i)\), not the single value \(m(x)\) at a query point.

Why Honesty Matters—and What It Cannot Guarantee

With an independent estimation sample, the partition can be treated as fixed when analyzing the leaf average. The tree may have selected its boundaries adaptively from the structure data, but those choices do not select on the estimation responses. Conditional unbiasedness therefore applies to the cell chosen by the structure sample, subject to the moment and occupancy conditions.

Honesty alone does not guarantee accurate prediction at a point, a small variance, or consistency. A cell can be too wide for its mean to approximate \(m(x)\), or can receive very few estimation observations. Conversely, a narrow cell may have a favorable target but insufficient occupancy. Those issues require additional arguments about cell geometry and leaf occupancy; they are not consequences of the conditional-unbiasedness calculation.

Common Mistake

A common error is to say, “The partition is fixed, so the leaf average is unbiased for \(m(x)\) at every \(x\) in the leaf.” The argument establishes no such pointwise conclusion. Fixing the partition makes the leaf a region \(A\); averaging responses from that region targets \(E[Y\mid X\in A]\). In general, this is an average over the distribution of covariates within \(A\), whereas \(m(x)\) is a conditional mean at one covariate value. A second error is to condition on an occupancy that cannot occur. Conditional formulas are defined only for \(k\) with \(P(N_A=k\mid\mathcal T)>0\).