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

Before you can read the parent note, you need a toolbox. Below, every symbol and idea it uses is built from nothing — plain words first, then a picture, then why the topic needs it. Read top to bottom; each rung of the ladder stands on the one below.

1. A sample, and the pair $(x,y)$

The picture: think of a spreadsheet. Each row is one sample. The left columns are $x$, the last column is $y$.

Why the topic needs it: cross-validation is entirely about which rows go into training and which go into testing. If you can't picture one row as $(x,y)$, none of the splitting makes sense.

2. The dataset size $n$

The picture: the height of the spreadsheet. 100 rows means $n=100$.

Why the topic needs it: LOOCV literally sets the number of folds equal to $n$. So $n$ is the number of times you retrain the model — the whole cost of LOOCV rides on this one letter.

3. Classes, and the counts $n_1,n_2,\dots ,n_C$

So if $y$ is either "cat" or "dog", then $C=2$. If $60$ rows are cats and $40$ are dogs, then $n_1=60$ (cats) and $n_2=40$ (dogs).

Why $\sum$ appears: the parent writes ${\sum }_{i=1}^C{n}_i=n$. The symbol $\sum$ (capital Greek "sigma") means "add these up". The little $i=1$ underneath and $C$ on top mean "let $i$ run from 1 up to $C$, and add every $n_i$." In words: the counts of all classes add up to the total number of samples. Of course they do — every row belongs to exactly one class.

$\underset{\text{written compactly as }{\sum }_{i=1}^C{n}_i}{\underbrace{n_1+n_2+\cdots +n_C}}=n$

Why the topic needs it: stratification is all about keeping each class's share fixed. You cannot talk about "keeping the mix" without a symbol for "how many of each kind."

4. Class proportion $p_i=\frac{n_i}{n}$

The picture: a pie chart. If $70$ of $100$ rows are class 0, that slice is $p_0=70/100=0.7$, i.e. $70\%$ of the pie.

Why the topic needs it: the whole promise of stratified CV is "every fold has the same $p_i$ as the full dataset." $p_i$ is the quantity we protect. Every proportion is between $0$ and $1$, and all of them add to $1$ (the full pie).

5. Folds: cutting the deck into $k$ piles

The picture: shuffle a deck of $n$ cards, deal them into $k$ piles. Each round, one pile is the test set (hidden) and the other $k-1$ piles glued together are the training set.

Why the topic needs it: k-fold, stratified, and LOOCV are all the same recipe with different $k$. LOOCV is just $k=n$: as many piles as cards, so each pile is a single card. Understanding "fold = one pile you take turns hiding" unlocks the entire family. See 2.6.03-K-fold-cross-validation for the base recipe this builds on.

6. Set language: $D_i$, $\cup$, $\cap$, and $|\cdot |$

The parent note groups samples with set notation. A "set" is just a collection of things — think of a labelled box.

The picture: two overlapping circles (a Venn diagram). Union = the whole shaded blob; intersection = only the lens where they overlap.

Why the topic needs it: stratification builds a fold by taking one small sub-box from each class and pouring them together — that is exactly $F_j=D_1^{(j)}\cup D_2^{(j)}\cup \dots$. And to check "how many class-$i$ samples are in fold $j$" the parent writes $|F_j\cap \text{class }i|$: the count of the overlap between fold $j$ and class $i$.

7. Floor and ceiling: $\lfloor \cdot \rfloor$ and $\lceil \cdot \rceil$

When $n_i$ doesn't divide evenly by $k$, you can't put a whole number of samples in each sub-fold. The parent handles this with floor and ceiling.

The picture: a number line. $x$ sits between two integers; floor slides left to the integer below, ceiling slides right to the integer above.

Why the topic needs it: if $n_i=33$ and $k=5$, then $33/5=6.6$. Some sub-folds get $\lfloor 6.6\rfloor =6$, others get $\lceil 6.6\rceil =7$. That is what the parent's "$\frac{n_i}{k}\pm 1$" means — you can't split people into fractions.

8. The model $\hat{f}$ and the "leave-one-out" superscript ${\hat{f}}^{(-i)}$

Why the topic needs it: this is the heart of LOOCV. The whole point is honesty — you test the model on a sample it was never trained on. The superscript $(-i)$ is the notation that guarantees this honesty.

9. Error, loss $L$, and the average

Worked mini-check (from the parent's example): sample 1 has $y=2$, prediction $\hat{y}=3.2$. Then $L=(2-3.2{)}^2=(-1.2{)}^2=\mathrm{1.44.}$

The picture: $n$ dots on a number line (the errors); ${\text{CV}}_{\text{LOOCV}}$ is their balance point.

Why the topic needs it: one error tells you almost nothing (bad luck on one sample). Averaging over all samples turns luck into a reliable estimate of real-world error.

10. Bias, variance, expectation $E[\cdot ]$, and covariance

The parent's cost/accuracy discussion needs three probability words.

The picture: a dartboard. Bias = distance of the cluster's centre from the bullseye. Variance = spread of the darts. See 2.6.04-Bias-variance-tradeoff-in-cross-validation.

Why the topic needs it: LOOCV's $n$ training sets overlap in $n-2$ samples, so their errors are highly correlated (large covariance). That correlation is exactly why LOOCV has near-zero bias but high variance — the parent's punchline.

Prerequisite map

Equipment checklist

Cover the right side and answer aloud. If any stumps you, reread its section above.