Stratified K-Fold Validation for Discriminant Rules

Why Stratify Cross-Validation?

A discriminant rule is fitted on labelled observations and then used to predict the class of a new observation. To assess its classification error without reserving a separate test set, K-fold validation repeatedly fits the rule on part of the observed data and predicts the held-out part. For binary or multiclass data, random folds can have very different class compositions, especially when some classes are uncommon. Stratification controls this source of imbalance by allocating observations within each class across the folds.

Stratification does not make cross-validation an independent test set, nor does it remove all variability. The fitted rules share much of their training data, and a different fold assignment may produce different predictions. A careful analysis therefore specifies the target class weights, aggregates the held-out errors accordingly, and treats variation across fold assignments as a measure of split sensitivity rather than automatically as a confidence interval for population risk.

Setup and Definitions

Definition: Let $(X_i,Y_i)$, $i=1,\ldots,n$, be labelled observations with class labels in $\{1,\ldots,G\}$. Write $n_g=\sum_{i=1}^n \mathbf{1}\{Y_i=g\}$ for the observed count in class $g$. A stratified $K$-fold assignment partitions the observations into disjoint folds $I_1,\ldots,I_K$, whose union is $\{1,\ldots,n\}$, by allocating observations separately within each class. The fold counts $n_{kg}=\sum_{i\in I_k}\mathbf{1}\{Y_i=g\}$ should be as nearly equal across $k$ as the integer counts permit. Each observation is predicted by a discriminant rule fitted without fold $I_k$, denoted $\hat g_{-k}$. Its out-of-fold prediction is $\hat g_{-k}(X_i)$ when $i\in I_k$.

The rule fitted without fold $k$ uses the observations outside $I_k$, and hence has training size $n-|I_k|$. Every observation receives exactly one out-of-fold prediction. For a class $g$ with $n_g>0$, define its out-of-fold error estimate by

\widehat R_g^{\mathrm{CV}} = \frac{1}{n_g}\sum_{i:Y_i=g} \mathbf{1}\{\hat g_{-k(i)}(X_i)\ne g\},

where $k(i)$ is the fold containing observation $i$. A target-weighted estimate is

\widehat R_q^{\mathrm{CV}} = \sum_{g:n_g>0} q_g\widehat R_g^{\mathrm{CV}}, \qquad q_g\ge 0,\quad \sum_{g=1}^G q_g=1.

The target weights $q_g$ specify the class mixture for the risk being estimated. For example, choosing $q_g=n_g/n$ gives the observed-prevalence weighting, while equal weights $q_g=1/G$ target the average of the class-specific errors. The estimate is defined only if every class assigned positive target weight has $n_g>0$. More generally, the displayed sum can include only observed classes if $q_g=0$ for every unobserved class. If a target class has positive weight but is absent from the sample, its class-specific error cannot be estimated by this formula; it must not be silently treated as zero.

The class-specific risk of a fixed rule is the probability of misclassification conditional on class $g$. A target-weighted risk combines these conditional risks using the specified $q_g$. Cross-validation substitutes predictions from rules trained on subsets for predictions from a fixed rule. Its estimate thus directly reflects the fitting procedure at the fold training sizes, not exactly the risk of a rule fitted on all $n$ observations.

Aggregation: What Is Being Averaged?

For each fold, let $e_{kg}$ be the number of errors among class-$g$ observations in fold $k$, and let $e_k=\sum_g e_{kg}$ and $n_k=|I_k|$. Then the pooled, or observation-weighted, error is

\widehat R_{\mathrm{pooled}}^{\mathrm{CV}} = \frac{\sum_{k=1}^K e_k}{n} = \sum_{g:n_g>0}\frac{n_g}{n}\widehat R_g^{\mathrm{CV}}.

This identity follows by counting each out-of-fold error once and grouping the same errors by their true class. It shows that pooled error implicitly uses empirical class proportions as weights. By contrast, an unweighted mean of fold error rates, $K^{-1}\sum_k e_k/n_k$, gives every fold equal influence even when fold sizes differ. It need not equal pooled error. For a class-balanced target, aggregate the class-specific errors with equal class weights rather than averaging fold rates indiscriminately.

Result: For any nonnegative target weights $q_g$ summing to one, the foldwise estimator matching those weights is $$ \widehat R_q^{\mathrm{CV}} = \sum_{g:n_g>0}q_g \frac{\sum_{k=1}^K e_{kg}}{\sum_{k=1}^K n_{kg}}, $$ provided $q_g=0$ for every class with $n_g=0$. This is generally not the unweighted average of foldwise overall error rates.

To verify the result, the folds partition the data, so $\sum_k e_{kg}$ is exactly the number of out-of-fold errors in class $g$, and $\sum_k n_{kg}=n_g$. Dividing gives $\widehat R_g^{\mathrm{CV}}$; weighting and summing gives the stated estimator. For empirical-prevalence weights, $q_g=n_g/n$, this reduces to $\sum_g\sum_k e_{kg}/n=\sum_k e_k/n$, the pooled error. The condition on unobserved classes is essential: if $n_g=0$, the class-specific denominator is zero and the corresponding conditional error is not identified from these data. $\square$

Worked Example: Binary Errors and Two Different Targets

Suppose a binary data set has 4 observations in class A and 8 in class B, divided across three folds with class counts $(2,2)$, $(1,3)$, and $(1,3)$. The numbers in each pair are the counts for A and B. Suppose the foldwise error counts are respectively $(1,0)$, $(0,1)$, and $(1,1)$.

For class A, there are $1+0+1=2$ errors among $2+1+1=4$ observations, so $\widehat R_A^{\mathrm{CV}}=2/4=0.5$. For class B, there are $0+1+1=2$ errors among $2+3+3=8$, so $\widehat R_B^{\mathrm{CV}}=2/8=0.25$.

The pooled error is $(2+2)/12=1/3$. Equivalently, the empirical-prevalence weighting gives $(4/12)(0.5)+(8/12)(0.25)=1/3$. With equal target weights for the two classes, the estimate is $(0.5+0.25)/2=0.375$. These answers differ because they target different class mixtures, not because one calculation is erroneous.

The fold sizes are all 4 here, so the unweighted mean of fold error rates is also $(1/4+1/4+2/4)/3=1/3$. That agreement is not general; it occurs because the folds have equal sizes.

Practical Construction and Feasibility

A usable implementation must ensure that every training split supports the discriminant rule being fitted. For example, if the rule estimates class-specific parameters for each target class, a training split that omits one of those classes cannot fit that rule in the usual way. Stratification helps prevent this, but does not guarantee feasibility when a class has very few observations. Before fitting, check the class counts in every training split; if a required class is absent, change the fold design or state that the intended procedure cannot be evaluated with this sample.

Set the target.
Specify the class weights $q_g$ and the discriminant fitting procedure to be assessed. Ensure positive-weight classes are represented in the observed data.

Allocate folds within classes.
Distribute each class's observations as evenly as possible across the $K$ folds, while checking that every training complement contains all classes required by the fitting procedure.

Fit and predict out of fold.
For each fold, fit the discriminant rule using only observations outside that fold, then predict the class labels for observations inside it.

Aggregate and report.
Count errors by true class, compute class-specific rates, and combine them using the stated $q_g$. Report $K$, fold sizes, class counts, and the aggregation target.

Worked Example: A Target Class Is Unobserved

Suppose the intended classes are A, B, and C, with target weights $q=(0.6,0.4,0)$. The observed data contain $n_A=5$, $n_B=3$, and $n_C=0$, and out-of-fold predictions make 1 error in A and 2 in B.

The estimable class-specific rates are $\widehat R_A^{\mathrm{CV}}=1/5=0.2$ and $\widehat R_B^{\mathrm{CV}}=2/3$. Since $q_C=0$, the target-weighted estimate is defined: $\widehat R_q^{\mathrm{CV}}=0.6(0.2)+0.4(2/3)=0.12+0.266\overline{6}=0.386\overline{6}$.

If instead the target weights were equal across all three classes, then $q_C=1/3>0$. There is no observed class-C denominator and no class-C out-of-fold error rate, so the equal-class estimate is undefined from these data. Assigning class C an error rate of zero would be an unsupported assumption, not a correction for the missing class.

Variability Across Fold Assignments

Even with the same labelled data and the same $K$, different valid stratified assignments may yield different fitted rules and out-of-fold predictions. To describe this sensitivity, generate $R$ valid stratified assignments, apply the same fitting and aggregation procedure to each, and denote the resulting estimates by $T_1,\ldots,T_R$. Their mean and sample variance are

\overline T=\frac{1}{R}\sum_{r=1}^R T_r, \qquad s_T^2=\frac{1}{R-1}\sum_{r=1}^R(T_r-\overline T)^2.

For $R\ge2$, $s_T$ summarizes the observed spread of the estimates across the assignments that were run. This is conditional split-to-split variability for the fixed observed data and the chosen fold-generation scheme. It is not, by itself, a standard error or confidence interval for population risk: it does not account for drawing a different data set from the population. Nor does repeating assignments create independent test sets, since the training samples overlap heavily.

Result: If assignments are independently generated from the same specified distribution over valid stratified partitions, and each $T_r$ has finite variance, then $s_T^2$ is unbiased for the variance of $T_r$ under that assignment distribution.

For a proof, write $\mu=E[T_r]$ and $\sigma^2=\operatorname{Var}(T_r)$. The identity $\sum_r(T_r-\overline T)^2=\sum_r(T_r-\mu)^2-R(\overline T-\mu)^2$ follows by expanding both sides and using $\sum_r(T_r-\overline T)=0$. Taking expectations, independence gives $E[\sum_r(T_r-\mu)^2]=R\sigma^2$ and $E[(\overline T-\mu)^2]=\operatorname{Var}(\overline T)=\sigma^2/R$. Thus the expected numerator is $R\sigma^2-R(\sigma^2/R)=(R-1)\sigma^2$, and division by $R-1$ yields $E[s_T^2]=\sigma^2$. This statement concerns randomness in the assignment mechanism, with data held fixed. $\square$

Worked Example: Summarizing Repeated Assignments

On one fixed data set, suppose four independently generated valid stratified assignments produce pooled error estimates $0.20, 0.25, 0.15,$ and $0.30$. Their mean is $\overline T=(0.20+0.25+0.15+0.30)/4=0.225$.

The deviations from the mean are $-0.025, 0.025, -0.075,$ and $0.075$. Their squared sum is $0.000625+0.000625+0.005625+0.005625=0.0125$. Therefore $s_T^2=0.0125/3\approx0.00417$, and $s_T\approx0.0645$.

This standard deviation describes how much the reported estimate changed across these fold assignments on this data set. It does not establish that the population error is $0.225$, and $0.0645$ should not be reported as a population-risk standard error without additional justification.

Common Pitfalls and Interpretation

Dividing by zero for an absent class. A class-specific estimate requires $n_g>0$. If a class has positive target weight but no observed cases, its risk is not estimated by this cross-validation calculation.
Confusing fold-averaged and pooled error. The unweighted mean of fold rates weights folds equally; pooled error weights observations equally. With unequal fold sizes, they generally differ.
Using the wrong class mixture. Pooled error uses empirical class proportions. If the target is class-balanced or reflects another deployment mixture, combine class-specific rates using those target weights instead.
Treating repeated partitions as independent test data. The assignments reuse the same observations and overlapping training sets. Their spread measures partition sensitivity conditional on the observed sample.
Ignoring the training size. Each fold rule is fitted on fewer than $n$ observations. A K-fold estimate is most directly about the specified fitting procedure at those fold training sizes, not precisely the full-sample fitted rule.
Allowing a training split to omit a required class. Stratification is an allocation strategy, not a substitute for checking that every training split can fit the stated discriminant rule.

Stratified K-fold validation is useful because it makes class representation in the held-out folds more controlled and produces out-of-fold predictions for all observed cases. Its interpretation still depends on the target mixture, the fold construction, and the fitting procedure. Reporting these choices makes the error estimate interpretable and makes split sensitivity visible without overstating what it measures.

Check Your Understanding

Work through these questions using the definitions and distinctions above.

Why does pooled out-of-fold error correspond to empirical-prevalence weighting of class-specific error rates?
A data set has no observations from class C. What condition on $q_C$ is required for the stated target-weighted estimate to be defined?
When fold sizes differ, explain why the unweighted mean of fold error rates can differ from pooled error.
What does the sample variance across repeated stratified assignments describe, and what source of uncertainty does it not automatically quantify?
Why must the class composition of every training complement be checked even when folds were stratified?