\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{\E}[0]{{\mathbb{E}}}
\newcommand{\bootstrapidx}{b}
\newcommand{\bootstrapsample}[1]{\widetilde{\dataset}^{(#1)}}
\newcommand{\datapoint}{\vz}
\newcommand{\dataset}{\mathcal{D}}
\newcommand{\feature}{x}
\newcommand{\featurevec}{\vx}
\newcommand{\hypothesis}{h}
\newcommand{\learnthypothesis}{\widehat{\hypothesis}}
\newcommand{\learntlocalhypothesis}[1]{\widehat{\hypothesis}^{(#1)}}
\newcommand{\nrbootstraps}{B}
\newcommand{\prob}[1]{\mathbb{P}\left(#1\right)}
\newcommand{\probdist}{\mathbb{P}}
\newcommand{\sampleidx}{r}
\newcommand{\samplesize}{m}
\newcommand{\trainset}{\dataset^{(\rm train)}}
\newcommand{\truelabel}{y}
\newcommand{\valset}{\dataset^{(\rm val)}}
\newcommand{\vx}[0]{{\bf x}}
\newcommand{\vz}[0]{{\bf z}}

\begin{document}

\section{bootstrap}

\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}
The bootstrap is a stochastic algorithm that generates
		perturbed variants, referred to as bootstrap samples, of a given
		dataset. Each bootstrap sample is obtained by randomly
		selecting data points, with replacement, from the original
		dataset. The bootstrap samples have the same size as the
		original dataset. However, they might repeat some of the
		original data points while omitting others. Several bootstrap
		samples allow the study of the properties of a machine learning (ML) method.
		For example, a robust ML method delivers similar
		model parameters for two datasets that differ only in the
		random fluctuations of the data generation. Bootstrap samples can
		also be used to estimate a confidence interval for a
		validation error. Another application of the bootstrap is
		bagging, where the hypotheses learned from the
		bootstrap samples are aggregated into one.

\subsection{Definition}
Five days of weather recordings at Krems an der Donau
	are all the data there is. Each day is a data point, its
	feature the minimum temperature of the day and its label the
	maximum temperature of the same day (Fig.~\ref{fig_bootstrap_five}).
		This dataset is small: it does not allow the training
		of a high-dimensional model, and a hypothesis learned
		from it depends on which five days happened to be recorded. The bootstrap is a stochastic algorithm, stated
		as Algorithm~\ref{alg_bootstrap_dict}, that generates additional
		datasets from the recorded one, the so-called bootstrap
		samples (Efron and Tibshirani, 1993), and so makes that dependence
		measurable. Fig.~\ref{fig_bootstrap_five} shows two bootstrap samples
		obtained from Algorithm~\ref{alg_bootstrap_dict}. A bootstrap
		sample can contain a data point of $\dataset$ several times,
		so it is a list of data points rather than a set. The
		bootstrap is based on the independent and identically distributed assumption (i.i.d.\ assumption).
		\begin{algorithm}[H]
		\caption{The bootstrap
			\label{alg_bootstrap_dict}}
		\begin{algorithmic}[1]
			\Statex \textbf{Input:} dataset $\dataset = \big\{\datapoint^{(1)},
				\,\ldots, \,\datapoint^{(\samplesize)}\big\}$, number
				$\nrbootstraps$ of bootstrap samples
			\For{$\bootstrapidx = 1, \,\ldots, \,\nrbootstraps$}
				\For{$\sampleidx = 1, \,\ldots, \,\samplesize$}
					\State draw an index $i$ uniformly at random from
						$\{1, \,\ldots, \,\samplesize\}$
					\State $\widetilde{\datapoint}^{(\sampleidx)} :=
						\datapoint^{(i)}$
				\EndFor
				\State $\bootstrapsample{\bootstrapidx} :=
					\big(\widetilde{\datapoint}^{(1)}, \,\ldots,
					\,\widetilde{\datapoint}^{(\samplesize)}\big)$
			\EndFor
			\Statex \textbf{Output:} bootstrap samples $\bootstrapsample{1}, \,\ldots,
				\,\bootstrapsample{\nrbootstraps}$
		\end{algorithmic}
		\end{algorithm}
		\begin{figure}[H]
		\centering
		\begin{minipage}[t]{0.44\linewidth}
			\centering
			\begin{tikzpicture}
			\begin{axis}[
				width=\linewidth, height=0.64\linewidth,
				axis lines=left, xlabel near ticks, ylabel near ticks,
				xmin=-6, xmax=20, ymin=6, ymax=35,
				xlabel={minimum temperature $\feature$ ($^{\circ}$C)},
				ylabel={maximum temperature $\truelabel$ ($^{\circ}$C)},
				tick label style={font=\scriptsize},
				label style={font=\scriptsize}]
				\addplot[only marks, mark=o, mark size=2.6pt, black,
					point meta=explicit,
					nodes near coords={\pgfmathprintnumber
						\pgfplotspointmeta},
					every node near coord/.append style={font=\scriptsize,
						anchor=south west, inner sep=1.5pt}]
					table[col sep=comma, x=tmin, y=tmax, meta=idx]
					{bootstrap_fivedays.csv};
			\end{axis}
			\end{tikzpicture}
			\\ {\small (a) the dataset $\dataset$ of five days}
		\end{minipage}
		\\[2pt]
		\begin{minipage}[t]{0.44\linewidth}
			\centering
			\begin{tikzpicture}
			\begin{axis}[
				width=\linewidth, height=0.64\linewidth,
				axis lines=left, xlabel near ticks, ylabel near ticks,
				xmin=-6, xmax=20, ymin=6, ymax=35,
				xlabel={minimum temperature $\feature$ ($^{\circ}$C)},
				ylabel={maximum temperature $\truelabel$ ($^{\circ}$C)},
				tick label style={font=\scriptsize},
				label style={font=\scriptsize}]
				\addplot[only marks, mark=o, mark size=3.2pt, black!40]
					table[col sep=comma, x=tmin, y=tmax]
					{bootstrap_fivedays.csv};
				\addplot[only marks, mark=square*, mark size=2.0pt, black]
					table[col sep=comma, x=tmin, y=tmax]
					{bootstrap_star1.csv};
			\end{axis}
			\end{tikzpicture}
			\\ {\small (b) bootstrap sample $\bootstrapsample{1}$}
		\end{minipage}\hfill
		\begin{minipage}[t]{0.44\linewidth}
			\centering
			\begin{tikzpicture}
			\begin{axis}[
				width=\linewidth, height=0.64\linewidth,
				axis lines=left, xlabel near ticks, ylabel near ticks,
				xmin=-6, xmax=20, ymin=6, ymax=35,
				xlabel={minimum temperature $\feature$ ($^{\circ}$C)},
				ylabel={maximum temperature $\truelabel$ ($^{\circ}$C)},
				tick label style={font=\scriptsize},
				label style={font=\scriptsize}]
				\addplot[only marks, mark=o, mark size=3.2pt, black!40]
					table[col sep=comma, x=tmin, y=tmax]
					{bootstrap_fivedays.csv};
				\addplot[only marks, mark=triangle*, mark size=2.6pt, black]
					table[col sep=comma, x=tmin, y=tmax]
					{bootstrap_star2.csv};
			\end{axis}
			\end{tikzpicture}
			\\ {\small (c) bootstrap sample $\bootstrapsample{2}$}
		\end{minipage}
		\caption{A dataset of five data points representing
			daily weather conditions at Krems an der Donau, the $15$th of
			February, April, June, August, and October $2022$, and below
			it two bootstrap samples obtained from it by
			Algorithm~\ref{alg_bootstrap_dict}. In (a) each day is a
			data point (open circle, numbered). In (b) and (c) the gray
			open circles repeat the five days, and the filled markers are
			the five draws of the bootstrap sample:
			$\bootstrapsample{1}$ (filled squares) holds the days $2, 3,
			3, 4, 5$ and omits day $1$, while $\bootstrapsample{2}$ (filled
			triangles) holds the days $1, 2, 2, 4, 5$ and omits day $3$.
			The second marker of a day drawn twice sits slightly above the
			first, so that two draws of one day do not hide each other.
			Weather data: GeoSphere Austria (GeoSphere Austria, 2026). Data
			generated by \texttt{pythondemos/bootstrap.py}
			\label{fig_bootstrap_five}}
		\end{figure}
		Here, a dataset $\dataset = \big\{ \datapoint^{(1)},
		\,\ldots, \,\datapoint^{(\samplesize)}\big\}$ is interpreted as
		the realizations of $\samplesize$ independent and identically distributed (i.i.d.) random variables (RVs) with
		a common probability distribution $\probdist$. That $\probdist$ is unknown
		and must be estimated from $\dataset$ itself. The bootstrap
		estimates it by the empirical distribution
		$\probdist^{(\dataset)}$ of $\dataset$
		(Efron, 1979; Efron and Tibshirani, 1993;
		Hastie et al., 2009, Sect.~8.2.1). For every
		event $\mathcal{A}$, the fraction of the data points
		$\datapoint^{(\sampleidx)}$ that fall into it approximates its
		probability by the law of large numbers
		(Billingsley, 1986, Thm.~6.1;
		Efron and Tibshirani, 1993, Sect.~4.2),
		\[
			\frac{1}{\samplesize} \big| \sampleidx: \datapoint^{(\sampleidx)}
			\in \mathcal{A} \big| \approx \prob{\mathcal{A}} \text{.}
		\]
\par
		The empirical distribution
		$\probdist^{(\dataset)}$ is a fully specified probability distribution and can
		be sampled as often as wanted. As many data points and as many
		datasets as needed can therefore
		be generated from the collected dataset. The gain
		is copies, not information. Each copy keeps the size
		$\samplesize$ of $\dataset$, because the quantity being imitated is
		the spread of a dataset of that size drawn from $\probdist$.
		Nor does a copy contain new data points:
		$\probdist^{(\dataset)}$ places all its mass on the $\samplesize$
		data points observed, so no draw can produce one that
		$\dataset$ does not already contain. A variant, the smoothed
		bootstrap, draws from a smoothed version of $\probdist^{(\dataset)}$
		in which each data point is replaced by a small bump-shaped
		probability density function (pdf); it produces data points that $\dataset$ does not
		contain, which the bootstrap itself never does.
\par
		Sampling $\samplesize$ data points from
		$\probdist^{(\dataset)}$ is the same as drawing $\samplesize$ times
		from $\dataset$ with replacement, which is what
		Algorithm~\ref{alg_bootstrap_dict} does: every draw is made from
		the whole of $\dataset$, so a data point can be drawn twice
		and another not at all (Fig.~\ref{fig_bootstrap_resample_dict}).
		The number $\nrbootstraps$ of bootstrap samples is limited only by
		the computation they cost.
		\begin{figure}[H]
		\begin{center}
		\begin{tikzpicture}[font=\small,
			cell/.style={draw, minimum width=0.52cm, minimum height=0.46cm,
				inner sep=1pt},
			orig/.style={cell, fill=black!8}]
			\foreach \i/\lab in {0/1,1/2,2/3,3/4,4/5,5/6,6/7,7/8}
				\node[orig] at (\i*0.56,0) {$\lab$};
			\node[anchor=east, font=\small] at (-0.45,0) {$\dataset$};
			\foreach \row/\y in {1/-0.85, 2/-1.45, 3/-2.05}
				\node[anchor=east, font=\small] at (-0.45,\y)
					{$\bootstrapsample{\row}$};
			\foreach \i/\lab in {0/2,1/5,2/6,3/6,4/7,5/7,6/8,7/8}
				\node[cell] at (\i*0.56,-0.85) {$\lab$};
			\foreach \i/\lab in {0/1,1/1,2/3,3/3,4/4,5/7,6/7,7/8}
				\node[cell] at (\i*0.56,-1.45) {$\lab$};
			\foreach \i/\lab in {0/1,1/2,2/3,3/3,4/3,5/4,6/7,7/7}
				\node[cell] at (\i*0.56,-2.05) {$\lab$};
			\node[anchor=west, font=\footnotesize] at (4.5,-0.85)
				{omits $1, 3, 4$};
			\node[anchor=west, font=\footnotesize] at (4.5,-1.45)
				{omits $2, 5, 6$};
			\node[anchor=west, font=\footnotesize] at (4.5,-2.05)
				{omits $5, 6, 8$};
		\end{tikzpicture}
		\end{center}
		\caption{Three bootstrap samples $\bootstrapsample{1}$,
			$\bootstrapsample{2}$, $\bootstrapsample{3}$ drawn from a
			dataset $\dataset$ of $\samplesize = 8$ data points
			(shaded), each by drawing $8$ times with replacement. Every row
			has the same length as $\dataset$, repeats some
			data points and omits others; each of the three happens
			to contain $5$ of the $8$ distinct data points, against
			the $0.63 \cdot 8 \approx 5$ that the calculation below predicts
			\label{fig_bootstrap_resample_dict}}
		\end{figure}
		A data point is left out of a bootstrap sample with
		probability $(1 - 1/\samplesize)^{\samplesize}$, so it appears
		in one with probability $1 - (1 -
		1/\samplesize)^{\samplesize}$, which approaches $1 - 1/e \approx
		0.63$ as $\samplesize$ grows, since $(1 - 1/\samplesize)^{\samplesize}$
		converges to $1/e$. The number of distinct data points in a
		bootstrap sample follows from that one probability
		alone. Write $I_{\sampleidx}$ for the RV that takes the value
		one when $\datapoint^{(\sampleidx)}$ appears in
		$\bootstrapsample{\bootstrapidx}$ and zero otherwise. The count of
		distinct data points is $\sum_{\sampleidx=1}^{\samplesize}
		I_{\sampleidx}$, so its expectation is
		\[
			\E \Big\{ \sum_{\sampleidx=1}^{\samplesize} I_{\sampleidx}
			\Big\} = \sum_{\sampleidx=1}^{\samplesize}
			\prob{I_{\sampleidx} = 1} = \samplesize \big( 1 -
			(1 - 1/\samplesize)^{\samplesize} \big) \approx
			0.63\,\samplesize \text{.}
		\]
		The $I_{\sampleidx}$ are not independent: a day drawn twice forces
		another to be left out. The expectation of a sum is the sum
		of the expectations nonetheless.
\par
		A bootstrap sample therefore holds about $0.63\,\samplesize$
		distinct data points and overlaps $\dataset$ heavily. That
		overlap is what separates the bootstrap from $k$-fold cross-validation ($k$-fold CV), which
		partitions $\dataset$ into blocks that do not overlap at all. Used
		naively to estimate the prediction error of a learned
		hypothesis, the bootstrap therefore evaluates it on
		data points that entered its own training, and the
		estimate comes out optimistic (Hastie et al., 2009, Sect.~7.11).
\par
		Machine learning (ML) training methods can be applied separately to each
		bootstrap sample, giving the learned hypotheses
		$\learntlocalhypothesis{1}, \,\ldots,
		\,\learntlocalhypothesis{\nrbootstraps}$. A quantity computed from
		$\bootstrapsample{\bootstrapidx}$ is a bootstrap replication
		(Efron and Tibshirani, 1993), such as the hypothesis
		$\learntlocalhypothesis{\bootstrapidx}$ learned by empirical risk minimization (ERM) from
		$\bootstrapsample{\bootstrapidx}$ or its prediction
		$\learntlocalhypothesis{\bootstrapidx}(\featurevec)$ for a fixed
		data point. The spread of the $\nrbootstraps$ bootstrap
		replications estimates how much the output of the ML method
		changes due to random fluctuations in the data generation
		(Hastie et al., 2009, Sect.~8.2.1).
\par
		Fig.~\ref{fig_bootstrap_krems} shows the bootstrap for
		learning a linear hypothesis from weather data recorded at
		Krems an der Donau during $2024$, $\samplesize = 366$ days. Each
		dot is one data point, its feature the minimum
		temperature and its label the maximum temperature of the
		day; the figure draws $20$ of them. The thick line is the
		hypothesis learned from all $366$ by ERM with the
		squared error loss. The thin lines show
		bootstrap replications $\learntlocalhypothesis{\bootstrapidx}$,
		$\bootstrapidx = 1, \,\ldots, \,\nrbootstraps$, learned by the
		same ERM problem from bootstrap samples. Their spread is
		narrow here, and the $95\%$ confidence interval for the slope
		is $[1.05, 1.15]$.
		\begin{figure}[H]
			\begin{center}
			\begin{tikzpicture}
			\begin{axis}[
				width=0.72\linewidth, height=0.6\linewidth,
				axis lines=left, xlabel near ticks, ylabel near ticks,
				xmin=-12, xmax=23, ymin=-5, ymax=37,
				xlabel={minimum temperature $\feature$ ($^{\circ}$C)},
				ylabel={maximum temperature $\truelabel$ ($^{\circ}$C)},
				tick label style={font=\scriptsize},
				label style={font=\scriptsize},
				legend style={draw=none, fill=none, font=\scriptsize,
					at={(0.5,-0.2)}, anchor=north},
				legend cell align=left]
				\addplot[only marks, mark=*, mark size=1.6pt, black]
					table[col sep=comma, x=tmin, y=tmax]
					{bootstrap_krems_plot.csv};
				\addlegendentry{data point $\datapoint^{(\sampleidx)}$ (dot)}
				\addplot[black!55, line width=0.15pt]
					table[col sep=comma, x=tmin, y=tmax, empty line=jump]
					{bootstrap_lines.csv};
				\addlegendentry{bootstrap replications
					$\learntlocalhypothesis{\bootstrapidx}$, $\bootstrapidx = 1,
					\,\ldots, \,25$ (thin lines)}
				\addplot[black, line width=1pt]
					table[col sep=comma, x=tmin, y=tmax, empty line=jump]
					{bootstrap_fit.csv};
				\addlegendentry{hypothesis $\learnthypothesis$ (thick line)}
			\end{axis}
			\end{tikzpicture}
			\end{center}
			\caption{Daily minimum and maximum temperature at Krems an der
				Donau in $2024$. The dots are $20$ of the $\samplesize = 366$
				data points, every $19$th day of the year. The
				thick line is the hypothesis $\learnthypothesis$
				learned from all $\samplesize$ data points, the thin
				lines are the bootstrap replications
				$\learntlocalhypothesis{\bootstrapidx}$ learned from the
				first $25$ of $\nrbootstraps = 500$ bootstrap samples, and
				the spread of all $500$ gives the confidence interval
				for the slope. Weather data: GeoSphere Austria
				(GeoSphere Austria, 2026). Data generated by
				\texttt{pythondemos/bootstrap.py}
				\label{fig_bootstrap_krems}}
		\end{figure}
		While basic validation gives a point estimate for the
		risk of a hypothesis, i.e., the validation error, the
		bootstrap adds a confidence interval to this point estimate.
		A hypothesis $\learnthypothesis$ is learned once from the
		training set $\trainset$, and the validation set $\valset$ is
		resampled $\nrbootstraps$ times with replacement, each bootstrap
		sample of the size of $\valset$. Evaluating
		the same $\learnthypothesis$ on each of them gives $\nrbootstraps$
		estimates of the risk. The sample mean of these
		estimates is the risk estimate, and the square root of their
		sample variance is its bootstrap standard error
		(Efron and Tibshirani, 1993, Sect.~6.2). The estimate plus or minus a
		standard normal quantile times this standard error is a
		confidence interval (Efron and Tibshirani, 1993, Sect.~13.2).
\par
		Bagging is the bootstrap put to a different use: instead of
		measuring the spread of $\learntlocalhypothesis{1}, \,\ldots,
		\,\learntlocalhypothesis{\nrbootstraps}$, it averages them into one
		hypothesis, which is how a random forest is built from
		decision trees.

\subsection{Cross References}
empirical distribution, i.i.d., RV, probability distribution, variance, $k$-fold CV, bagging, confidence interval, validation, validation set, validation error

\subsection{References}
\begin{enumerate}
  \item Billingsley (1986). Probability and Measure. 2nd ed., Wiley, New York, NY, USA.
  \item Efron and Tibshirani (1993). An Introduction to the Bootstrap. Chapman \& Hall, New York, NY, USA.
  \item Efron (1979). Bootstrap Methods: Another Look at the Jackknife. Ann. Statist., 7(1), pp.~1--26.
  \item GeoSphere Austria (2026). GeoSphere Austria climate station archive. Data hub, station historical resource klima-v2-1d. URL: https://dataset.api.hub.geosphere.at/v1/station/historical/klima-v2-1d.
  \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.
\end{enumerate}

\end{document}
