Designing Validation for Tree-Size Selection

Why Validation Design Matters

A classification tree can fit its growth data closely and still make poor predictions on new observations. To assess how its performance changes across tree sizes, the candidate trees must be evaluated on data that did not help determine their splits or terminal-node predictions. Validation is the name for this separate evaluation step.

The key design question is not merely how many observations to set aside. The validation observations must be independent of the data used to construct the candidate trees, and they should represent the population and prediction task of interest. Otherwise, the resulting error rate may describe the design of the data split rather than the tree’s expected performance in use.

Definition: A validation set is a set of labeled observations held apart from tree construction and used to estimate the predictive performance of one or more fitted candidate trees. For tree-size comparisons, the candidate trees must be determined without using the validation outcomes. The validation error for a tree is the proportion of validation observations whose predicted class differs from the observed class.

Separate Tree Construction From Validation

Suppose the available labeled observations are divided into a growth set and a validation set. The growth set is used to fit the initial classification tree and, if applicable, to produce a nested sequence of pruned subtrees. Each candidate tree is then applied to the validation predictors, and its predicted classes are compared with the observed validation classes.

The validation outcomes must not be used to choose split variables, split points, terminal-node class probabilities, or class labels for the candidate trees. Nor should they be used to decide which candidate sizes to include in the sequence. Those decisions would allow validation information to influence the fitted candidates. The validation set is useful precisely because it is not part of that fitting process.

A further distinction is important: validation data help estimate performance during model development, while a separate test set can be reserved for a final performance assessment after development is complete. If validation results are used repeatedly to revise the modeling procedure, the validation set is no longer an untouched assessment of the final procedure. The test set should remain unavailable until that development is finished.

Define the prediction task.
Specify the outcome classes, the population to which predictions will be applied, and the unit on which a prediction is made.

Set aside validation observations.
Separate them before fitting the tree sequence, and keep their outcomes out of construction decisions.

Construct candidate trees using growth data.
Fit the tree and generate the candidate sizes using only the growth data.

Score every candidate on the same validation set.
Record its predicted class for each validation observation and calculate its validation error.

Interpret the estimates within the design.
Check that the validation units and class proportions reflect the intended application, and remember that the estimates have sampling uncertainty.

What Validation Error Estimates

For a fixed fitted tree, let $I_j=1$ when the tree misclassifies validation observation $j$, and let $I_j=0$ otherwise. With $n_{\mathrm{val}}$ validation observations, the empirical validation error is

\widehat{R}_{\mathrm{val}}=\frac{1}{n_{\mathrm{val}}}\sum_{j=1}^{n_{\mathrm{val}}} I_j =\frac{\text{number of validation misclassifications}}{n_{\mathrm{val}}}.

If the validation observations are independent draws from the target prediction population, and the tree is fixed independently of those observations, then each indicator has the same probability $R$ of being 1, where $R$ is that tree’s misclassification probability in the target population. The sample mean therefore estimates $R$.

Justification: Conditional on the growth data, the fitted tree is fixed. If the validation observations are independent and identically distributed from the target population, then $E[I_j\mid\text{growth data}]=R$ for every $j$. By linearity of expectation, $$ E[\widehat{R}_{\mathrm{val}}\mid\text{growth data}] =\frac{1}{n_{\mathrm{val}}}\sum_{j=1}^{n_{\mathrm{val}}}E[I_j\mid\text{growth data}] =\frac{1}{n_{\mathrm{val}}}(n_{\mathrm{val}}R)=R. $$ Thus validation error is unbiased for the fixed tree’s target-population misclassification probability under these conditions. The result does not say the estimate has no sampling variability, nor does it justify treating the error of a tree selected after repeated validation comparisons as an independent final assessment.

When the observations are independent, the indicators for a fixed tree are Bernoulli with probability $R$. The standard error of their sample mean is estimated by

\widehat{\operatorname{SE}}(\widehat{R}_{\mathrm{val}}) =\sqrt{\frac{\widehat{R}_{\mathrm{val}}(1-\widehat{R}_{\mathrm{val}})}{n_{\mathrm{val}}}}.

This is an uncertainty measure for a fixed tree under the sampling assumptions; it is not a guarantee that the estimate is precise. In particular, a small validation set can produce a noisy error estimate. Further, the errors for different candidate trees are calculated on the same observations. Their estimates are consequently related, not independent: a difficult observation may be misclassified by several candidates.

Designing a Representative Validation Set

The validation unit should match the unit of future prediction. If the intended task is to classify a new policyholder, multiple records from one policyholder should not be split across growth and validation sets as though they were unrelated people. Shared characteristics can make the records dependent, and information from one record can help the tree predict another record belonging to the same person. In that setting, separate policyholders between the sets.

The validation sampling scheme should also match the target population. A deliberately balanced sample can be useful for ensuring that each class is represented, but its unweighted error may not estimate error in a population with different class proportions. If class-specific validation errors are available and the target class proportions are known, they can be combined using those proportions.

Validation should also reflect the conditions under which predictions will be made. For example, if deployment involves predicting outcomes for a later period, a random split across dates may put closely related observations from both periods into both sets. A time-ordered separation may better match the intended task. The general principle is to prevent information from the validation cases, or from closely linked cases, from entering tree construction.

Worked Example: Calculating Error Across Candidate Sizes

A hypothetical insurer uses labeled policy records to develop a classification tree for whether a policy will require a manual review. From 120 records, 80 are assigned to the growth set and 40 to validation before fitting. Three candidate subtrees with 2, 4, and 7 terminal nodes are generated using only the 80 growth records. On the 40 validation records, they make 11, 8, and 7 errors, respectively. Calculate each validation error and the estimated standard error for the 4-node tree.

Method. Divide each error count by the same validation-set size, 40. For the standard error, use the Bernoulli sample-mean formula for a fixed tree evaluated on independent validation records.

For the 2-node tree, $\widehat{R}_{\mathrm{val}}=11/40=0.2750$. For the 4-node tree, it is $8/40=0.2000$. For the 7-node tree, it is $7/40=0.1750$. These are proportions, so the corresponding percentages are 27.50%, 20.00%, and 17.50%.

For the 4-node tree, substitute $\widehat{R}_{\mathrm{val}}=0.2$ and $n_{\mathrm{val}}=40$:

\widehat{\operatorname{SE}} =\sqrt{\frac{0.2(1-0.2)}{40}} =\sqrt{\frac{0.2(0.8)}{40}} =\sqrt{\frac{0.16}{40}} =\sqrt{0.004} \approx 0.0632.

The standard error is approximately 0.0632, or 6.32 percentage points. This indicates substantial sampling uncertainty relative to the observed error rates. The calculation describes uncertainty for the fixed 4-node tree under the stated assumptions; it does not make the three validation errors independent or establish a final performance estimate after using the validation results to make modeling decisions.

Check. The error counts are all at most 40, and each reported proportion equals its count divided by 40. The method avoids comparing raw error counts from validation sets of different sizes.

Worked Example: Correcting for a Deliberately Balanced Validation Sample

A hypothetical review-screening task has two outcome classes. In the target population, 75% of cases are Class A and 25% are Class B. To ensure both classes are well represented, the validation sample contains 20 cases from each class. A fixed tree misclassifies 2 Class A cases and 8 Class B cases. Calculate the raw validation error and an estimate weighted to the target class proportions.

Method. First calculate the unweighted sample proportion of errors. Then calculate the error within each class and weight those class-specific rates by the target population proportions.

There are $2+8=10$ errors among $20+20=40$ validation cases. The raw error is $10/40=0.2500$.

The Class A error rate is $2/20=0.1000$, and the Class B error rate is $8/20=0.4000$. Applying the target proportions gives

\widehat{R}_{\mathrm{weighted}} =(0.75)(0.1000)+(0.25)(0.4000) =0.0750+0.1000 =0.1750.

The unweighted estimate is 0.2500, while the weighted estimate for the stated target class proportions is 0.1750. The difference arises because the validation sample allocates half its cases to Class B, whereas Class B accounts for only one quarter of the target population.

Check. The weights sum to $0.75+0.25=1$, and the weighted estimate lies between the two class-specific error rates, 0.1000 and 0.4000. The correction avoids treating the balanced validation sample as if its class proportions matched the target population.

Common Design Traps

Growing the tree before setting aside validation data. If the validation observations have already influenced split selection or tree construction, they are not a clean holdout for that fitted tree.
Choosing a validation criterion that does not match the task. Misclassification rate counts every error equally. If the intended performance measure assigns different costs to different errors, the validation score should reflect that intended measure rather than being interpreted as an estimate of equal-cost error.
Ignoring the sampling design. A class-balanced validation set does not necessarily have target-population class proportions. Use appropriate weights when the target proportions are known and the validation design supports that calculation.
Splitting related records across sets. If several rows belong to the same person, account, or other prediction unit, separate those units rather than randomly splitting individual rows.
Repeatedly tuning against the same validation outcomes. Trying many development changes in response to the same results can make those results overly favorable as an assessment of the final procedure. Keep a separate test set for an assessment after development.
Reporting a proportion without its denominator. An error rate of 0.20 based on 20 cases is generally less stable than the same rate based on 2,000 cases. State the validation size alongside the estimate.

Key takeaway: Validation error estimates the performance of a fixed candidate tree when validation cases are independent of tree construction and representative of the target prediction population. Protect the validation outcomes from fitting decisions, use an appropriate sampling design, and interpret every error rate in light of its denominator and uncertainty.

Check Your Understanding

For each problem, assume the stated candidate tree was fixed without using the validation outcomes unless the question says otherwise.

A fixed tree makes 9 errors on 50 independent validation cases sampled from the target population. Calculate its validation error to four decimal places. (Answer: 0.1800)
A validation set contains 30 Class 0 cases, of which 3 are misclassified, and 10 Class 1 cases, of which 4 are misclassified. The target population has class proportions 0.80 and 0.20. Calculate the raw validation error and the error weighted to the target proportions. (Answer: Raw error $7/40=0.1750$; weighted error $0.80(3/30)+0.20(4/10)=0.1600$.)
Two candidate trees make 14 and 11 errors, respectively, on the same 100 validation cases. Calculate their validation errors and the difference in percentage points. (Answer: 0.1400 and 0.1100; the second rate is 3 percentage points lower.)
A future prediction is made once per claimant, but each claimant contributes five records. What is the appropriate unit to separate between growth and validation sets, and why? (Answer: Separate claimants; splitting their records across sets can create dependence and information leakage between the sets.)
A modeler changes a tree after observing 8 errors on 40 validation cases, then reports 7 errors on those same 40 cases for the revised tree. An untouched test set has 12 errors among 60 cases. Calculate the revised validation error and test error, and state which is the independent assessment after development. (Answer: Revised validation error $7/40=0.1750$; test error $12/60=0.2000$; the untouched test set is the independent assessment after development.)

What You'll Learn