\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).
\DeclareMathOperator*{\argmin}{arg\,min}
\newcommand{\datapoint}{\vz}
\newcommand{\dataset}{\mathcal{D}}
\newcommand{\feature}{x}
\newcommand{\hypospace}{\mathcal{H}}
\newcommand{\hypothesis}{h}
\newcommand{\learnthypothesis}{\widehat{\hypothesis}}
\newcommand{\lossfunc}[2]{L\left(#1,#2 \right)}
\newcommand{\regparam}{\alpha}
\newcommand{\testset}{\dataset^{(\rm test)} }
\newcommand{\trainset}{\dataset^{(\rm train)}}
\newcommand{\truelabel}{y}
\newcommand{\valerror}{E_{v}}
\newcommand{\valset}{\dataset^{(\rm val)}}
\newcommand{\vz}[0]{{\bf z}}

\begin{document}

\section{model selection}

\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}
Model selection chooses among several alternative machine learning (ML)
		methods by comparing their validation errors. Each ML method learns a hypothesis via a training method such as empirical risk minimization (ERM). A core design choice of a ML method is
		the underlying hypothesis space, or model. The effective
		hypothesis space can also depend on hyperparameters of the
		optimization algorithms used to solve ERM. The training error of an ML method cannot serve as the criterion for model selection, as it always chooses the largest of nested hypothesis spaces.
		The validation error can be obtained from the average loss on a single validation set, or via $k$-fold cross-validation ($k$-fold CV). The ultimately chosen
		hypothesis must be assessed on data points that have
		been used neither for learning any individual hypothesis
		nor for choosing among them.

\subsection{Definition}
Fig.~\ref{fig_modelsel_picture_dict} depicts
	data points collected by a weather station at Krems an der Donau. Each
	data point represents a day, with the morning minimum temperature as
	feature $\feature$ and the maximum daytime temperature as
	label $\truelabel$. The figure also shows two
	hypothesis maps, each learned by a machine learning (ML) method via
		empirical risk minimization (ERM) from the training set $\trainset$ of six data points. One is a linear hypothesis $\learnthypothesis^{(1)}$, learned over a linear model. The other is a degree-five polynomial $\learnthypothesis^{(2)}$, learned over the larger hypothesis space of polynomial regression.
\par
		The polynomial delivers perfect predictions on every data point of $\trainset$, so its
		training error, the average squared error loss over $\trainset$, is
		zero. The linear hypothesis misses each of them and its
		training error is $0.47$. The training error therefore ranks the polynomial first, and
		following that ranking would pick the candidate that predicts
		worst on a data point outside $\trainset$.
		Model selection ranks the two instead by the validation error on a validation set
		$\valset$ that ERM did not use. On the fourteen validation data points of
		Fig.~\ref{fig_modelsel_picture_dict}, the average
		squared error loss is $2065$ for the polynomial and $7.06$ for the
		linear hypothesis, so model selection picks the linear
		hypothesis $\learnthypothesis^{(1)}$.
\par
		The validation error of the selected hypothesis is biased downward, since the selection favored the candidate with the smallest one. Model selection therefore leaves a test set $\testset$ untouched for estimating the risk of the selected hypothesis. 
		\begin{figure}[H]
		\begin{center}
		\begin{tikzpicture}
		\begin{axis}[
			width=0.86\linewidth, height=0.54\linewidth,
			axis lines=left,
			xlabel={feature $\feature$},
			ylabel={label $\truelabel$},
			xmin=-15.6, xmax=5.6, ymin=-18, ymax=18,
			label style={font=\small},
			tick label style={font=\small},
			legend style={draw=none, fill=none, font=\small,
				at={(0.98,0.02)}, anchor=south east,
				legend columns=2},
			]
			\addplot[black, thick]
				table[col sep=comma, x=x, y=y]
				{validation_line.csv};
			\addlegendentry{$\learnthypothesis^{(1)}$ (linear)}
			\addplot[black!55, thick, dashed]
				table[col sep=comma, x=x, y=y]
				{validation_poly.csv};
			\addlegendentry{$\learnthypothesis^{(2)}$ (polynomial)}
			\addplot[only marks, mark=*, mark size=2.6pt, black]
				table[col sep=comma, x=x, y=y]
				{validation_train.csv};
			\addlegendentry{$\trainset$}
			\addplot[only marks, mark=triangle, mark size=3.4pt,
				black!55, line width=0.9pt]
				table[col sep=comma, x=x, y=y]
				{validation_val14.csv};
			\addlegendentry{$\valset$}
			\addplot[only marks, mark=square, mark size=2.8pt, black]
				table[col sep=comma, x=x, y=y]
				{validation_test6.csv};
			\addlegendentry{$\testset$}
		\end{axis}
		\end{tikzpicture}
		\end{center}
		\caption{Model selection between two ML methods that learn a
			hypothesis via ERM from the same six data points
			(filled circles). One
			method uses degree-five polynomials as hypothesis space, the other a linear model. The degree-five polynomial
			$\learnthypothesis^{(2)}$ (dashed curve) delivers perfect
			predictions on every data point of the
			training set, so its training error is zero against
			$0.47$ for the linear hypothesis $\learnthypothesis^{(1)}$
			(solid curve). Averaged over
			the fourteen validation data points (open triangles), the
			squared error loss is $2065$ for the polynomial and $7.06$ for the
			linear hypothesis, so the validation error selects the linear
			hypothesis $\learnthypothesis^{(1)}$. The six data points of
			the test set (open squares) are held out from both ERM
			and the model selection, so the average squared error loss on them,
			$1.83$, estimates the risk of the selected
			hypothesis. Data generated by
			\texttt{pythondemos/validation.py}
			\label{fig_modelsel_picture_dict}}
		\end{figure}
		Model selection chooses among several alternative ML methods by comparing their validation errors
		(Shalev-Shwartz and Ben-David, 2014, Sect.~11.2.2). Consider $C$ candidates
		$\learnthypothesis^{(c)}$, $c = 1, \ldots, C$, obtained from ERM with a different effective hypothesis space, or model, $\hypospace^{(c)}$. The effective hypothesis space can also depend
		on hyperparameters of the optimization
		algorithm used to solve ERM. Typical
		hyperparameters include the learning rate of a gradient-based method, the strength $\regparam$ of a regularization penalty term, and the depth of a decision tree (Goodfellow et al., 2016, Sect.~11.4).
\par
		The training error of the learned hypotheses
		$\learnthypothesis^{(c)}$ cannot serve as the criterion for choosing between them. For nested candidates $\hypospace^{(1)} \subseteq \cdots \subseteq \hypospace^{(C)}$ it always chooses the largest hypothesis space, since the minimum of the training error over a superset is no larger, even when
		that results in overfitting, as the degree-five polynomial of
		Fig.~\ref{fig_modelsel_picture_dict} does
		(Hastie et al., 2009, Sect.~7.2, Fig.~7.1;
		Shalev-Shwartz and Ben-David, 2014, Sect.~11.2.3). Model selection therefore follows model training, e.g.,
		via ERM, and model validation, e.g., via
		$k$-fold cross-validation ($k$-fold CV).
\par
		Algorithm~\ref{alg_modelsel_dict} summarizes a complete ML
		workflow, consisting of model training, model
		validation and model selection.
		\begin{algorithm}[H]
		\caption{Model selection
			\label{alg_modelsel_dict}}
		\begin{algorithmic}[1]
			\Statex \textbf{Input:} training set $\trainset$, validation set
				$\valset$, a loss function $L$ for training and a
				loss function $L_{v}$ for validation, candidate
				hypothesis spaces $\hypospace^{(c)}$ with their
				hyperparameter settings, for $c = 1, \ldots, C$
			\For{$c = 1, \ldots, C$}
				\State learn a
					hypothesis via ERM,
					$$\learnthypothesis^{(c)} = \argmin_{\hypothesis \in \hypospace^{(c)}} \frac{1}{|\trainset|} \sum_{\datapoint \in \trainset} \lossfunc{\datapoint}{\hypothesis}$$
				\State compute the validation error
					$\valerror\big(\learnthypothesis^{(c)}\big)$ via the
					average $L_{v}$ of $\learnthypothesis^{(c)}$ on $\valset$
			\EndFor
			\State $c^{\star} := \arg\min_{c = 1, \ldots, C}\,
				\valerror\big(\learnthypothesis^{(c)}\big)$, a tie going to
				the smaller hypothesis space
			\Statex \textbf{Output:} the selected hypothesis
				$\learnthypothesis^{(c^{\star})}$
		\end{algorithmic}
		\end{algorithm}
		The two loss functions used in Algorithm \ref{alg_modelsel_dict} for training and validation 
		can be different: ERM needs one that its optimization method can handle, while validation 
		can use the loss function that matters for the application, such as the $0/1$ loss.
		When the training set is too small to spare a validation set, steps 2 and 3 of Algorithm \ref{alg_modelsel_dict} 
		can be replaced by $k$-fold CV (Hastie et al., 2009, Sect.~7.10). 
\par
		The final hypothesis $\learnthypothesis^{(c^{\star})}$ delivered by Algorithm \ref{alg_modelsel_dict} 
		must be evaluated on a test set. A test set consists of data points that have been used neither 
		for learning any individual $\learnthypothesis^{(c)}$ nor for choosing between them.
		Under an independent and identically distributed assumption (i.i.d.\ assumption) for the data generation, the average loss on $\testset$ is an 
		unbiased estimator of the risk of $\learnthypothesis^{(c^{\star})}$:
		the data points of $\testset$ are independent of how
		$\learnthypothesis^{(c^{\star})}$ was obtained
		(Shalev-Shwartz and Ben-David, 2014, Sect.~11.2.1), so each loss has the
		risk as its expectation and so has their average
		(Bertsekas and Tsitsiklis, 2008, Sect.~9.1). If $\trainset$ and $\valset$
		are modelled as random, so is $\learnthypothesis^{(c^{\star})}$, and
		with it the risk being estimated: the expectation is then
		conditional on $\learnthypothesis^{(c^{\star})}$, over $\testset$
		alone.

\subsection{Cross References}
validation, validation error, $k$-fold CV, training set, validation set, test set, hyperparameter, hypothesis space, overfitting

\subsection{References}
\begin{enumerate}
  \item Bertsekas and Tsitsiklis (2008). Introduction to Probability. 2nd ed., Athena Scientific, Belmont, MA, USA.
  \item Goodfellow et al. (2016). Deep Learning. MIT Press, Cambridge, MA, USA.
  \item Shalev-Shwartz and Ben-David (2014). Understanding Machine Learning: From Theory to Algorithms. Cambridge Univ. Press, New York, NY, USA.
  \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}