Cross-validation — k-fold: Foundations — Coding deep dive

Before you can read the parent note Cross-validation — k-fold, you need to earn every symbol it uses. This page introduces them one at a time, each with a plain-words meaning, a picture, and the reason the topic needs it. Nothing here assumes you've met the notation before.

1. A dataset $D$ , its size $n$ , and its samples $(x_{i}, y_{i})$

Let's decode every piece of that line, left to right.

The curly braces ${\dots}$ mean "a collection of things" — here, a collection of rows.
Each row is a pair written in round brackets $(x_{i}, y_{i})$ : an input glued to its correct answer.
The little number below, the subscript $i$ , is just a row label — "the $i$ -th row". So $x_{3}$ is the input of row 3.
The three dots $\dots$ mean "and so on in the same pattern", counting up to the last row $n$ .

In the parent's aerospace example, $n = 1000$ and one row is one flight record: $x_{i}$ holds the 50 sensor readings (temperature, vibration, pressure), and $y_{i}$ is a single bit — did the engine fail within 100 hours ( $1$ ) or not ( $0$ )?

2. The fold count $k$ and fold sizes

Since we already met $n$ , keep the two straight — they play very different roles:

Which is bigger,

n

k

n

— you have many rows (

n = 1000

) split into a few folds (

k = 5

n = 1000

and

k = 5

, how big is each fold?

\frac{n}{k} = \frac{1000}{5} = 200

rows.

The picture below shows the clean case where the chop divides evenly.

3. Folds $D_{i}$ and the "carve out" operations $\cup$ , $\cap$ , $∖$

Before we can write the fold equation, we must name the folds themselves.

The parent then writes $D = D_{1} \cup D_{2} \cup \dots \cup D_{k}$ . Three new symbols hide in there. Each is a way of talking about groups of rows.

Now the parent's line $D = D_{1} \cup D_{2} \cup \dots \cup D_{k}$ just says: "gluing all the folds back together rebuilds the whole dataset — nothing lost, nothing added."

And $D_{i} \cap D_{j} = \emptyset$ for $i \neq = j$ (read " $i$ not equal to $j$ ") says: "two different folds share no rows." That is the disjoint property, and it is why a row can never be both trained-on and tested-on in the same round.

The set-minus symbol powers the parent's training-set definition: $D_{train}^{(i)} = D ∖ D_{i}$ Read aloud: "the training set for round $i$ is the whole dataset with fold $i$ removed." The superscript $(i)$ in brackets is just a round label — "the version used in round $i$ ", not a power. (Brackets around the top number are the standard way to signal "this is a label, don't multiply.")

4. The learning algorithm $A$ and the trained model $M_{i}$

Think of $A$ as an empty brain and the parentheses $A (\dots)$ as "feed this data into the brain". Out pops a specific fitted model $M_{i}$ . Because each round removes a different fold, each $M_{i}$ is a slightly different model.

Why the subscript on

M_{i}

Because there are

k

different trained models, one per round —

M_{1}, M_{2}, \dots, M_{k}

5. The metric function and the score $Score_{i}$

What does the metric use each of its two inputs for? The first, $M_{i}$ , makes the guesses; the second, $D_{test}^{(i)}$ , supplies both the inputs to guess from and the hidden true answers to compare against. The parent uses two common metrics:

Accuracy — fraction of guesses that are correct. Simple, but a liar when one class is rare (guessing "no failure" always gives 95% on a 5%-failure dataset).
F1 score — a balanced number that rewards catching the rare cases and not crying wolf. Preferred when failures are rare.

You don't need the F1 formula yet — just know $Score_{i}$ is one honest grade per round, and higher is better here.

6. Summation $\sum$ , mean, and the CV score

Here is the symbol that scares the most beginners. It is friendly once unpacked.

Now the headline formula falls out for free:

Why average, not just pick one? One round could get an easy test fold and score high by luck. Averaging $k$ rounds cancels good luck against bad luck, giving a steadier estimate of true performance.

7. Spread: the standard deviation $σ_{CV}$

The average alone hides consistency. The parent also reports a spread.

Decode it piece by piece, from inside out:

$Score_{i} - CV_{k}$ — how far one grade sits from the average (a "miss").
$(\dots)^{2}$ — square it, so negative misses and positive misses both count as positive distance.
$\sum \dots$ — add up all the squared misses.
$\frac{1}{k - 1}$ — divide (nearly the average miss; using $k - 1$ not $k$ is a standard small-sample correction).
— take the square root to undo the squaring, returning to the original units.

How these pieces feed the topic

Everything on this page is a prerequisite arrow pointing at the same destination: a single trustworthy number (plus a wobble) for how well a model will do on data it has not seen.

Where to go next

The parent itself: Cross-validation — k-fold
Before folds, the simplest idea: 5.6.01-Train-test-split-validation-set and 5.6.02-Holdout-method
Keeping rare classes balanced across folds: 5.6.04-Stratified-sampling
Pushing $k$ all the way to $n$ : 5.6.06-Leave-one-out-cross-validation-(LOOCV)
Why $k$ affects reliability: 5.6.10-Bias-variance-tradeoff-in-model-selection
Prefer to read in Hinglish: 5.6.05 Cross-validation — k-fold (Hinglish)

Equipment checklist

You are ready for the parent note when you can answer each of these without peeking.

What does

(x_{i}, y_{i})

stand for?

Row

i

of the data — inputs

x_{i}

paired with the correct answer

y_{i}

What is the difference between

n

and

k

n

is the number of rows;

k

is the number of folds we chop them into.

When

n

is not divisible by

k

, how big is each fold?

Either

⌊ n / k ⌋

⌈ n / k ⌉

rows — differing by at most one sample.

What does

D_{i}

denote?

The

i

-th fold — the bundle of rows in piece number

i

What does

D_{i} \cap D_{j} = \emptyset

tell you?

Different folds share no rows — they are disjoint, so no row is both trained-on and tested-on.

What does

D ∖ D_{i}

mean?

The whole dataset with fold

i

removed — i.e. the training set for round

i

What is the difference between

A

and

M_{i}

A

is the empty recipe;

M_{i}

is the model after

A

has learned from round-

i

training data.

What kind of object is

Metric

A function taking a model and a dataset and returning one number (a scalar score).

What does

\sum_{i = 1}^{k} Score_{i}

compute?

The sum of all

k

round grades:

Score_{1} + \dots + Score_{k}

How do you get

CV_{k}

from that sum?

Divide by

k

— it is the average of the

k

grades.

What does a large

σ_{CV}

warn you about?

The model's performance swings a lot depending on which data it sees — it is not consistent.

Recall Self-test: rebuild the whole pipeline from memory

Say the five steps out loud: (1) split $D$ into $k$ disjoint folds; (2) for each fold, train on $D ∖ D_{i}$ and test on $D_{i}$ ; (3) score each round with a metric; (4) average the scores to get $CV_{k}$ ; (5) take the standard deviation $σ_{CV}$ for the spread. If you can do all five, open the parent note.