Stratified and leave-one-out cross-validation: Exercises

This page is a self-test. Each problem is stated cleanly; the full worked solution hides inside a collapsible Solution callout. Try it first, then reveal. Problems are labelled L1 → L5 (Recognition → Mastery). Build on 2.6.03-K-fold-cross-validation, 2.6.04-Bias-variance-tradeoff-in-cross-validation, and the parent Stratified and leave-one-out cross-validation.

Before we start, one picture to fix the vocabulary we lean on throughout.

Figure — Stratified and leave-one-out cross-validation

Look at the two coloured bars. The left bar is the full dataset's class mix. In stratified CV, every fold's bar (right) has the same shape — same fraction of each colour. That "same shape" is the single fact almost every exercise below tests.

Level 1 — Recognition

Recall Solution — L1.1

Each iteration leaves out one sample. To use every sample once as the test point, you need one iteration per sample, so: $k = n = 200.$ This is Leave-One-Out Cross-Validation (LOOCV): the special case $k = n$ . Answer: $k = 200$ folds; this is LOOCV.

Recall Solution — L1.2

Stratification demands each fold copy the $60%/40%$ ratio.

Fold X: $6/10 = 60%$ A, $4/10 = 40%$ B → matches ✓
Fold Y: $8/10 = 80%$ A, $2/10 = 20%$ B → does not match ✗

Answer: Fold X is the stratified one.

Recall Solution — L1.3

False. Stratified CV preserves the original imbalance in every fold — it does not rebalance to 50/50. Forcing 50/50 would be a resampling method (see 3.2.05-Handling-imbalanced-classes and 2.3.08-Sampling-methods), which is a different tool with a different purpose.

Level 2 — Application

Recall Solution — L2.1

(a) Split each class evenly into $k = 6$ groups: $class 0 per fold = \frac{90}{6} = 15, class 1 per fold = \frac{30}{6} = 5.$ Each fold = $15 + 5 = 20$ samples.

(b) Original ratio: $90/120 = 75%$ class 0. Fold ratio: $15/20 = 75%$ class 0. ✓ Identical. Answer: 15 class-0 + 5 class-1 per fold; ratio preserved at 75%/25%.

Recall Solution — L2.2

Each of the 8 minority samples independently lands outside a chosen fold with probability $1 - \frac{1}{5} = 0.8$ . For the fold to miss the class, all 8 must land outside: $P \approx (0.8)^{8} = 0.1678.$ Answer: $\approx 0.168$ , i.e. about a 17% chance that this one fold contains zero minority samples. Stratification drives this to (essentially) zero.

Recall Solution — L2.3

LOOCV: train on $n - 1 = 49$ of 50 samples: $\frac{49}{50} = 0.98 = 98%.$ 5-fold: train on $\frac{k - 1}{k} = \frac{4}{5} = 80%$ . Answer: LOOCV trains on 98% each iteration vs 80% for 5-fold — this is why LOOCV has the lowest bias.

Level 3 — Analysis

Recall Solution — L3.1

The LOOCV estimate is the mean of the held-out errors: $CV_{LOOCV} = \frac{1}{n} \sum_{i = 1}^{n} e_{i} = \frac{0.20 + 0.05 + 0.45 + 0.10 + 0.30 + 0.15}{6} .$ Sum $= 1.25$ , so $CV_{LOOCV} = \frac{1.25}{6} = 0.2083.$ Answer: $\approx 0.208$ .

Recall Solution — L3.2

(a) Low bias. The model in each iteration trains on $n - 1$ samples — nearly the full dataset. So the model being scored is almost identical to the final model trained on all $n$ . There is almost no "penalty" from training on less data, hence $Bias_{LOOCV} \approx 0.$ (b) High variance. Look at the figure: iteration 1's training set and iteration 2's training set share $n - 2$ samples (all but two). The bars overlap almost completely. Highly overlapping training sets produce highly correlated error terms $e_{i}$ . When you average correlated numbers, the randomness does not cancel out the way it would for independent numbers, so the final average fluctuates a lot from dataset to dataset: $Var_{LOOCV} \approx \frac{1}{n ^{2}} \sum_{i} \sum_{j} Cov (ϵ_{i}, ϵ_{j}) — big because the covariances are large.$ Answer: overlap $\Rightarrow$ almost-identical models (low bias) but strongly correlated errors (high variance). Compare with 2.6.04-Bias-variance-tradeoff-in-cross-validation.

Recall Solution — L3.3

When $n_{i}$ is not divisible by $k$ , folds use $⌊ n_{i} / k ⌋$ or $⌈ n_{i} / k ⌉$ per class. For class A: $23/4 = 5.75$ , so $⌊ ⌋ = 5$ and $⌈ ⌉ = 6$ . The remainder is $23 - 4 \times 5 = 3$ , so 3 folds get 6 and 1 fold gets 5: $6 + 6 + 6 + 5 = 23. ✓$ (Class B: $10/4 = 2.5$ → two folds get 3, two folds get 2: $3 + 3 + 2 + 2 = 10$ .) Answer: class A distributes as $6, 6, 6, 5$ ; folds differ by at most one sample — as close to equal as integers allow.

Level 4 — Synthesis

Recall Solution — L4.1

(a) Stratified k-fold. With 3% positives, plain random folds risk zero positives; stratification guarantees $\approx 3%$ positives in every fold. Pair with techniques from 3.2.05-Handling-imbalanced-classes if needed. (b) LOOCV. Tiny $n$ and cheap training make LOOCV's $n$ retrains affordable, and its near-zero bias gives the best point estimate of test error. (c) Neither — use time-series CV. Random or stratified folds leak future into past. See 5.4.02-Time-series-cross-validation. Answer: (a) stratified, (b) LOOCV, (c) time-series CV.

Recall Solution — L4.2

Number of models trained = number of folds. (a) LOOCV: $k = n = 500$ models → $500 \times 2 = 1000$ s. (b) 10-fold: $k = 10$ models → $10 \times 2 = 20$ s. Ratio: $1000/20 = 50$ . Answer: LOOCV takes 1000 s, 10-fold takes 20 s; LOOCV is 50× more expensive — exactly the factor $n / k = 500/10$ .

Recall Solution — L4.3

Stratification means each fold copies the class ratio. But a LOOCV test fold has exactly one sample, so it holds only one class — it can never mirror a multi-class ratio. There is nothing to stratify. The training set in LOOCV is simply "everything except one point," which already keeps the class ratio nearly intact automatically. Answer: stratified LOOCV is not meaningful — with 1-sample test folds there is no distribution to preserve.

Level 5 — Mastery

Recall Solution — L5.1

Fold $j$ holds $\frac{n _{i}}{k}$ samples of class $i$ out of $\frac{n}{k}$ total. Its class- $i$ proportion: $\frac{n _{i} / k}{n / k} = \frac{n _{i}}{k} \cdot \frac{k}{n} = \frac{n _{i}}{n} = p_{i} .$ The $k$ cancels — the fold size doesn't matter, only the ratio carried over. That cancellation is the entire mathematical content of stratification. $■$

Recall Solution — L5.2

Per fold: $P = (0.8)^{6} = 0.2621$ . By linearity of expectation, expected count of empty folds over $k = 5$ folds: $E [empty folds] = k \cdot P = 5 \times 0.2621 = 1.311.$ Answer: $\approx 1.31$ folds — on average more than one of your five folds would have no minority sample. This is the quantitative case for stratification.

Worked example L5.3 — Full LOOCV from raw fits

Dataset of $n = 4$ points $(x, y)$ : $(1, 2), (2, 2), (3, 4), (4, 5)$ . For each held-out point, a fitted line $\hat{f}^{(- i)}$ is given below. Using squared loss, compute each $e_{i}$ and the LOOCV error.

Leave out $i$	line $\hat{f}^{(- i)} (x)$	at $x_{i}$
1 ( $x = 1$ )	$1.0 x + 1.0$
2 ( $x = 2$ )	$1.1 x + 0.7$
3 ( $x = 3$ )	$1.2 x + 0.4$
4 ( $x = 4$ )	$0.9 x + 1.2$

Recall Solution — L5.3

Predict, subtract true $y$ , square.

$i = 1$ : $\overset{y}{^} = 1.0 (1) + 1.0 = 2.0$ ; $e_{1} = (2 - 2.0)^{2} = 0.00$ .
$i = 2$ : $\overset{y}{^} = 1.1 (2) + 0.7 = 2.9$ ; $e_{2} = (2 - 2.9)^{2} = 0.81$ .
$i = 3$ : $\overset{y}{^} = 1.2 (3) + 0.4 = 4.0$ ; $e_{3} = (4 - 4.0)^{2} = 0.00$ .
$i = 4$ : $\overset{y}{^} = 0.9 (4) + 1.2 = 4.8$ ; $e_{4} = (5 - 4.8)^{2} = 0.04$ .

$CV_{LOOCV} = \frac{0.00 + 0.81 + 0.00 + 0.04}{4} = \frac{0.85}{4} = 0.2125.$ Answer: $e = (0, 0.81, 0, 0.04)$ ; LOOCV error $= 0.2125$ .

Recall Self-test recap (cloze)

Stratified CV makes each fold copy the dataset's class distribution. LOOCV is the special case $k =$ ::: $n$ Each LOOCV iteration trains on how many samples? ::: $n - 1$ Bias of LOOCV is approximately ::: zero LOOCV variance is high because training sets ::: overlap heavily, making errors correlated Cost ratio of LOOCV to $k$ -fold ::: $n / k$