\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb}
\usepackage{algorithm,algpseudocode}
\usepackage{bm}
\usepackage{hyperref}
\usepackage{float}
\usepackage{subcaption}
\usepackage{enumitem}
\usepackage{xcolor}
\definecolor{darkgreen}{rgb}{0.0, 0.5, 0.0}
\definecolor{aaltoBlue}{RGB}{0, 51, 102}
\definecolor{pinegreen}{cmyk}{0.92,0,0.59,0.25}
\definecolor{royalblue}{cmyk}{1,0.50,0,0}
\definecolor{lavander}{cmyk}{0,0.48,0,0}
\definecolor{violet}{cmyk}{0.79,0.88,0,0}
\definecolor{lightblue}{RGB}{173, 216, 230}
\usepackage{tikz}
\usepackage{pgfplots}
\usetikzlibrary{calc,arrows.meta,positioning,fit,shapes.geometric,shapes.misc,intersections,patterns,decorations.pathreplacing,backgrounds,matrix}
\usepgfplotslibrary{fillbetween,groupplots}
\setcounter{secnumdepth}{-\maxdimen}
% Long unbreakable tokens (the ISO/IEC author names in citations, term names
% in the title) otherwise overflow the margin by a few points; a modest
% emergency stretch lets TeX loosen the paragraph instead.
\emergencystretch=2em
\usepackage{mleftright}
% Project macros used by this entry (auto-extracted).
\newcommand{\algomap}{\mathcal{A}}
\newcommand{\cverror}{E_{\rm CV}}
\newcommand{\dataset}{\mathcal{D}}
\newcommand{\emprisk}[2]{\widehat{L}\big(#1|#2\big)}
\newcommand{\feature}{x}
\newcommand{\foldidx}{b}
\newcommand{\hypothesis}{h}
\newcommand{\learnthypothesis}{\widehat{\hypothesis}}
\newcommand{\samplesize}{m}
\newcommand{\trainset}{\dataset^{(\rm train)}}
\newcommand{\truelabel}{y}
\newcommand{\valerror}{E_{v}}
\newcommand{\valset}{\dataset^{(\rm val)}}

\begin{document}

\section{$k$-fold cross-validation ($k$-fold CV)}

\subsection*{Author and editors}
Alexander Jung\textsuperscript{*}, Department of Computer Science, Aalto University, Espoo, Finland (ORCID \mbox{\href{https://orcid.org/0000-0001-7538-0990}{0000-0001-7538-0990}}) \\
Editors: Konstantina Olioumtsevits (ORCID \mbox{\href{https://orcid.org/0000-0003-2697-8659}{0000-0003-2697-8659}}), Ekkehard Schnoor (ORCID \mbox{\href{https://orcid.org/0000-0001-8252-1499}{0000-0001-8252-1499}}), Aalto University, Espoo, Finland \\
\textsuperscript{*}Corresponding author: \href{mailto:alex.jung@aalto.fi}{alex.jung@aalto.fi}



\subsection{Abstract}
$k$-fold cross-validation ($k$-fold CV) divides a
		dataset into $k$ folds of equal size and uses each fold once
		as the validation set while the other $k-1$ folds form the
		training set of a given machine learning (ML) method. The $k$ resulting
		validation errors are averaged into a single number, an indicator of
		generalization beyond the training set. While a single
		validation step estimates the risk of a single
		hypothesis, $k$-fold CV estimates the risk of an
		ML method. Leave-one-out cross-validation (LOO-CV) is the extreme case of $k$-fold
		CV with one data point per fold.

\subsection{Definition}
Fig.~\ref{fig_kfoldcv_picture_dict} depicts
		four
		data points, representing daily weather conditions at Krems
		an der Donau (Austria). Each data point is characterized by the
		minimum temperature of a day as the feature $\feature$ and
		its maximum temperature as the label $\truelabel$. Three of
		the four data points are used as the training set for
		polynomial regression with degree three. The remaining data point
		serves as the validation set. A polynomial of degree three (a cubic)
		has four coefficients and the training set holds three
		data points. Thus, unless two data points have the same
		feature,
		polynomial regression delivers a hypothesis that passes exactly
		through those three data points and, in turn, the
		training error is zero.
\par
		However, as depicted in Fig.~\ref{fig_kfoldcv_picture_dict}, the
		learned hypothesis $\learnthypothesis$ does not generalize
		well beyond the training set, i.e., polynomial regression with degree
		three is overfitting. The validation error on the held-back
		data point can reveal this overfitting, but a single
		split does so unreliably. Holding back the first data point
		gives a validation error of
		$1.37$, which suggests a reliable hypothesis. Holding back
		the second, third or fourth data point instead gives
		validation errors of $8.05$, $7.02$ and $72.42$, as panels (b) to
		(d) of Fig.~\ref{fig_kfoldcv_picture_dict} illustrate. Their
		average $22.22$ is the $4$-fold CV estimate. Using different
		splits of a dataset into training set and validation set
		offers a more reliable assessment of a machine learning (ML) method.
		\begin{figure}[H]
		\centering
		\begin{tikzpicture}
		\begin{axis}[
			width=0.62\linewidth, height=0.34\linewidth,
			axis lines=left,
			xmin=0, xmax=11, ymin=2, ymax=44,
			xlabel={$\feature$\\(a) $\foldidx = 1$},
			ylabel={$\truelabel$},
			tick label style={font=\scriptsize},
			label style={font=\scriptsize, align=center},
			legend style={font=\scriptsize, draw=none, fill=none,
				at={(0.26,0.99)}, anchor=north west},
			legend cell align=left,
		]
			\addplot[black, thick] table[col sep=comma, x=x, y=line1]
				{kfoldcv_lines.csv};
			\addlegendentry{learned hypothesis}
			\addplot[only marks, mark=*, mark size=2.2pt, black,
				unbounded coords=discard] table[col sep=comma, x=x,
				y=train1]{kfoldcv_panels.csv};
			\addlegendentry{training}
			\addplot[only marks, mark=square, mark size=3.4pt, red,
				line width=1pt, unbounded coords=discard]
				table[col sep=comma, x=x, y=val1]
				{kfoldcv_panels.csv};
			\addlegendentry{validation}
		\end{axis}
		\end{tikzpicture}\endgraf\medskip
		\begin{tikzpicture}
		\begin{groupplot}[
			group style={group size=3 by 1, horizontal sep=0.45cm,
				yticklabels at=edge left},
			width=0.285\linewidth, height=0.30\linewidth,
			axis lines=left,
			xmin=0, xmax=11, ymin=2, ymax=44,
			xticklabels={}, yticklabels={},
			tick label style={font=\tiny},
			label style={font=\tiny, align=center},
		]
			\nextgroupplot[xlabel={$\feature$\\(b) $\foldidx = 2$}, ylabel={$\truelabel$}]
			\addplot[black, thick] table[col sep=comma, x=x, y=line2]
				{kfoldcv_lines.csv};
			\addplot[only marks, mark=*, mark size=1.6pt, black,
				unbounded coords=discard] table[col sep=comma, x=x,
				y=train2]{kfoldcv_panels.csv};
			\addplot[only marks, mark=square, mark size=2.1pt, red,
				line width=0.8pt, unbounded coords=discard]
				table[col sep=comma, x=x, y=val2]
				{kfoldcv_panels.csv};
			\nextgroupplot[xlabel={$\feature$\\(c) $\foldidx = 3$}]
			\addplot[black, thick] table[col sep=comma, x=x, y=line3]
				{kfoldcv_lines.csv};
			\addplot[only marks, mark=*, mark size=1.6pt, black,
				unbounded coords=discard] table[col sep=comma, x=x,
				y=train3]{kfoldcv_panels.csv};
			\addplot[only marks, mark=square, mark size=2.1pt, red,
				line width=0.8pt, unbounded coords=discard]
				table[col sep=comma, x=x, y=val3]
				{kfoldcv_panels.csv};
			\nextgroupplot[xlabel={$\feature$\\(d) $\foldidx = 4$}]
			\addplot[black, thick] table[col sep=comma, x=x, y=line4]
				{kfoldcv_lines.csv};
			\addplot[only marks, mark=*, mark size=1.6pt, black,
				unbounded coords=discard] table[col sep=comma, x=x,
				y=train4]{kfoldcv_panels.csv};
			\addplot[only marks, mark=square, mark size=2.1pt, red,
				line width=0.8pt, unbounded coords=discard]
				table[col sep=comma, x=x, y=val4]
				{kfoldcv_panels.csv};
		\end{groupplot}
		\end{tikzpicture}
		\caption{(a) Four data points, each a day at Krems an der
			Donau (Austria) with its minimum temperature as feature
			$\feature$ and its maximum temperature as label
			$\truelabel$. The filled circles indicate one
			possible choice of a training set of three
			data points. The red open square indicates the resulting
			held-out data point, which serves as the validation set.
			The curve is the hypothesis learned by polynomial regression
			with degree three. The fold index $\foldidx$ numbers the
			held-back data point. (b) to (d) The same for
			$\foldidx = 2, 3, 4$: holding back a different
			data point changes the learned hypothesis and its
			validation error. Data generated by
			\texttt{pythondemos/kfoldcv.py}
			\label{fig_kfoldcv_picture_dict}}
		\end{figure}
		Consider an ML method $\algomap$ that maps a training set to
		a learned hypothesis $\learnthypothesis =
		\algomap(\trainset)$. $k$-fold CV estimates the expected
		loss (or risk) of the method $\algomap$ as follows
		(Hastie et al., 2009, Sect.~7.10;
		Stone, 1974). It divides a dataset $\dataset$
		evenly into $k$ subsets, the folds $\dataset^{(1)},\,\ldots,\,
		\dataset^{(k)}$ (Fig.~\ref{fig_kfoldcv_dict}). For each fold
		$\foldidx = 1, \,\ldots, \,k$, one iteration trains the
		model on the union of all folds except
		$\dataset^{(\foldidx)}$ and evaluates the resulting
		hypothesis on the held-out fold $\dataset^{(\foldidx)}$.
		The $k$ per-fold validation errors are then averaged to obtain the
		CV error $\cverror$, the CV estimate of the expected loss.
		Algorithm~\ref{alg_kfoldcv_dict} summarizes this procedure.
		\begin{figure}[H]
		\centering
			\begin{tikzpicture}[font=\small]
				\def\k{5}          % number of folds
				\def\cellw{1.6}    % width of one segment
				\def\cellh{0.40}   % height of one segment
				\def\gap{0.18}     % vertical gap between rows
				% rows: i = 1..k; columns: j = 1..k
				\foreach \i in {1,...,\k} {
					% row baseline y
					\pgfmathsetmacro{\y}{-(\i-1)*(\cellh+\gap)}
					% row label
					\node[anchor=east] at (-0.25,\y+0.5*\cellh) {iteration \i};
					% draw k equal segments; shade the \i-th as validation
					\foreach \j in {1,...,\k} {
						\pgfmathsetmacro{\x}{(\j-1)*\cellw}
						\ifnum\i=\j
						\fill[gray!35] (\x,\y) rectangle ++(\cellw,\cellh);
						\draw (\x,\y) rectangle ++(\cellw,\cellh);
						\else
						\draw (\x,\y) rectangle ++(\cellw,\cellh);
						\fi
					}
				}
				% add labels D^{(j)} above the columns
				\foreach \j in {1,...,\k} {
					\pgfmathsetmacro{\x}{(\j-1)*\cellw + 0.5*\cellw}
					\node[anchor=south] at (\x,\cellh+0.2) {$\dataset^{(\j)}$};
				}
			\end{tikzpicture}
		\caption{An instance of $k$-fold CV with $k=5$: the available
			dataset $\dataset$ is evenly divided into five folds
			$\dataset^{(1)},\,\ldots,\,\dataset^{(5)}$. Each row
			corresponds to one iteration; the shaded cell marks the fold
			used as validation set, while the remaining $k-1$ folds form
			the training set
			\label{fig_kfoldcv_dict}}
		\end{figure}
		\begin{algorithm}[H]
		\caption{$k$-fold CV
			\label{alg_kfoldcv_dict}}
		\begin{algorithmic}[1]
			\Statex \textbf{Input:} ML method $\algomap$, dataset $\dataset$,
				number of folds $k$
			\State divide $\dataset$ evenly into the folds
				$\dataset^{(1)}, \ldots, \dataset^{(k)}$
			\For{$\foldidx = 1, \ldots, k$}
				\State $\trainset := \dataset \setminus
					\dataset^{(\foldidx)}$, \quad $\valset :=
					\dataset^{(\foldidx)}$
				\State $\learnthypothesis^{(\foldidx)} :=
					\algomap(\trainset)$
				\State $\valerror^{(\foldidx)} :=
					\emprisk{\learnthypothesis^{(\foldidx)}}{\valset}$
			\EndFor
			\Statex \textbf{Output:} CV error $\cverror = (1/k) \sum_{\foldidx=1}^{k}
				\valerror^{(\foldidx)}$
		\end{algorithmic}
		\end{algorithm}
		A single validation set assesses one hypothesis, e.g., the one
		that $\algomap$ delivers from a training set
		(Bates et al., 2023, Sect.~3.3.1). In contrast,
		$k$-fold CV does not assess a single hypothesis. Instead,
		every iteration learns a potentially different
		hypothesis; panels (a) to (d) of
		Fig.~\ref{fig_kfoldcv_picture_dict} show four such
		hypotheses. Thus, the average validation error $\cverror$
		measures the method $\algomap$ rather than one hypothesis.
		In Fig.~\ref{fig_kfoldcv_picture_dict}, $\algomap$ is polynomial regression
		with degree three and $\cverror = 22.22$. In particular, $\cverror$
		measures the average
		risk of the hypotheses obtained from
		training sets holding the fraction $(k-1)/k$ of the
		dataset (Bates et al., 2023, Sect.~3;
		Hastie et al., 2009, Sect.~7.10.1).
\par
		Compared to a single split into training set and validation set,
		$k$-fold CV uses each data point for both training and
		validation. In Fig.~\ref{fig_kfoldcv_dict}, for example,
		each data point has been used four times for training
		and once for validation after all five iterations.
		Like $k$-fold CV, the bootstrap estimates the risk of
		a method by averaging over several hypotheses, each
		learned from a different resample of the dataset; unlike
		the folds of $k$-fold CV, these resamples overlap
		(Bates et al., 2023, Sect.~3.5).
\par
		Important variants and special cases of $k$-fold CV include the
		following:
		\begin{itemize}
			\item \emph{Stratified $k$-fold cross-validation (stratified $k$-fold CV)}: It preserves the class
			proportions of the full dataset in every fold, important
			for classification with imbalanced data
			(Kohavi, 1995).
			\item \emph{Leave-one-out cross-validation (LOO-CV)}: It is the extreme case
			$k = \samplesize$, with $\samplesize$ the number of
			data points in the dataset, where each fold
			contains a single data point (Stone, 1974). It
			trains on almost the full dataset in every iteration,
			at the cost of $\samplesize$ training runs and a high
			variance of the estimate.
			\item \emph{Repeated $k$-fold CV}: It averages the results of
			several runs with different random fold assignments
			(Kim, 2009). This reduces the variance
			contributed by the partitioning and is useful for small
			datasets, where a single partitioning strongly affects the
			estimate.
		\end{itemize}

\subsection{Cross References}
validation, validation error, generalization gap, learning curve, LOO-CV, stratified $k$-fold CV, model selection, bootstrap

\subsection{References}
\begin{enumerate}
  \item Bates et al. (2023). Cross-Validation: What Does It Estimate and How Well Does It Do It?. Journal of the American Statistical Association, 119(546), pp.~1434--1445.
  \item Hastie et al. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction. 2nd ed., Springer Science+Business Media, New York, NY, USA.
  \item Kim (2009). Estimating Classification Error Rate: Repeated Cross-Validation, Repeated Hold-Out and Bootstrap. Computational Statistics \& Data Analysis, 53(11), pp.~3735--3745.
  \item Kohavi (1995). A Study of Cross-Validation and Bootstrap for Accuracy Estimation and Model Selection. In: Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI), pp.~1137--1143.
  \item Stone (1974). Cross-Validatory Choice and Assessment of Statistical Predictions. Journal of the Royal Statistical Society. Series B (Methodological), 36(2), pp.~111--133.
\end{enumerate}

\end{document}