\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{\dataset}{\mathcal{D}}
\newcommand{\defeq}{:=}
\newcommand{\feature}{x}
\newcommand{\featurespace}{\mathcal{X}}
\newcommand{\featurevec}{\vx}
\newcommand{\hypospace}{\mathcal{H}}
\newcommand{\hypothesis}{h}
\newcommand{\labelspace}{\mathcal{Y}}
\newcommand{\lossfunczo}[2]{L^{(0/1)}\left(#1,#2 \right)}
\newcommand{\predictedlabel}{\widehat{\truelabel}}
\newcommand{\prob}[1]{\mathbb{P}\left(#1\right)}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\sampleidx}{r}
\newcommand{\samplesize}{m}
\newcommand{\thresholdfct}{\tau}
\newcommand{\truelabel}{y}
\newcommand{\vx}[0]{{\bf x}}

\begin{document}

\section{$\bf 0/1$ loss}

\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{Synonyms}
misclassification loss, zero-one loss

\subsection{Abstract}
The $0/1$ loss of a classifier on a data point is
		$1$ if the predicted label differs from the true label
		and $0$ if the two agree, so it is the indicator function of a
		misclassification. Its average over a dataset is the
		fraction of misclassified data points, which is one minus
		the accuracy, and its expectation is the
		probability of a misclassification, whose smallest value
		over all classifiers is the Bayes risk. For
		binary classification it depends on the data point only through the
		margin, and it uses the real-valued hypothesis only
		through its sign. As a function of the model parameters
		it is piecewise constant with a zero gradient wherever the
		gradient exists, and finding the linear classifier with the
		fewest misclassifications on a training set is NP-hard, so it
		is not used as the objective function of training. Empirical risk minimization (ERM)
		uses a convex surrogate instead, the hinge loss or the
		logistic loss divided by $\ln 2$, each an upper bound on the
		$0/1$ loss whose minimizers over all functions have the
		sign of the classifier with the Bayes risk. The $0/1$
		loss remains the loss by which a classifier is
		evaluated on a test set.

\subsection{Definition}
A frost warning for Krems an
		der Donau is issued in the evening and is either right or wrong
		the next morning: frost came, or it did not. Counting a wrong
		warning as $1$ and a right one as $0$ is the $0/1$ loss. In
		general, consider a data point with features
		$\featurevec \in \featurespace$ and a label $\truelabel$
		from a finite label space $\labelspace$, and a
		classifier $\hypothesis: \featurespace \rightarrow
		\labelspace$ that predicts the label. The $0/1$ loss
		incurred by $\hypothesis$ on the data point
		$(\featurevec, \truelabel)$ is
		(Goodfellow et al., 2016, Sect.~5.1.2;
		Shalev-Shwartz and Ben-David, 2014, Sect.~3.2.2)
		\begin{equation}
			\label{equ_zerooneloss_def_dict}
			\lossfunczo{(\featurevec, \truelabel)}{\hypothesis}
			\defeq \begin{cases} 0 & \text{if }
			\hypothesis(\featurevec) = \truelabel \text{,} \\
			1 & \text{if } \hypothesis(\featurevec) \neq \truelabel
			\text{.} \end{cases}
		\end{equation}
		It is the indicator function of a misclassification, and it
		takes the same two values whether the label space holds two
		elements or many.
\par
		The average of the $0/1$ loss \eqref{equ_zerooneloss_def_dict}
		over a dataset $\dataset = \{(\featurevec^{(1)},
		\truelabel^{(1)}), \ldots, (\featurevec^{(\samplesize)},
		\truelabel^{(\samplesize)})\}$ is the fraction of misclassified
		data points,
		\begin{equation}
			\label{equ_zerooneloss_avg_dict}
			\frac{1}{\samplesize} \sum_{\sampleidx=1}^{\samplesize}
			\lossfunczo{(\featurevec^{(\sampleidx)},
			\truelabel^{(\sampleidx)})}{\hypothesis}
			= 1 - \operatorname{acc}(\hypothesis \mid \dataset) \text{,}
		\end{equation}
		which is one minus the accuracy of $\hypothesis$ on
		$\dataset$. On a training set, the average
		\eqref{equ_zerooneloss_avg_dict} is the training error of
		$\hypothesis$ under the $0/1$ loss, and on a test set
		it is the error rate reported for a classification method.
		For data points that are realizations of independent and identically distributed (i.i.d.)
		random variables (RVs) with a common probability distribution, the expectation of
		the $0/1$ loss is the probability that $\hypothesis$
		misclassifies a data point, which is the risk of
		$\hypothesis$ under the $0/1$ loss
		(Shalev-Shwartz and Ben-David, 2014, Sect.~3.2.2). The risk is smallest for
		the classifier that assigns each $\featurevec$ the
		label value with the largest conditional probability
		given $\featurevec$, and that smallest risk is the
		Bayes risk (Bishop, 2006, Sect.~1.5.1).
\par
		For binary classification with $\labelspace = \{-1, +1\}$, a
		classifier is usually built from a real-valued
		hypothesis $\hypothesis: \featurespace \rightarrow \reals$
		that predicts $\predictedlabel =
		\operatorname{sign}(\hypothesis(\featurevec))$. The $0/1$
		loss \eqref{equ_zerooneloss_def_dict} of this
		classifier depends on the data point only through the
		margin $\truelabel \cdot \hypothesis(\featurevec)$,
		\begin{equation}
			\label{equ_zerooneloss_margin_dict}
			\lossfunczo{(\featurevec, \truelabel)}{\hypothesis}
			= \begin{cases} 0 & \text{if } \truelabel \cdot
			\hypothesis(\featurevec) > 0 \text{,} \\
			1 & \text{if } \truelabel \cdot
			\hypothesis(\featurevec) \leq 0 \text{.} \end{cases}
		\end{equation}
		A positive margin is a correct prediction, and a
		data point on the decision boundary
		$\hypothesis(\featurevec) = 0$ counts as misclassified. The
		margin form \eqref{equ_zerooneloss_margin_dict} uses
		$\hypothesis$ only through its sign, so multiplying $\hypothesis$
		by any positive number leaves the $0/1$ loss of every
		data point unchanged.
\par
		The $0/1$ loss is the natural loss for
		classification, and empirical risk minimization (ERM) with it would take the
		training error \eqref{equ_zerooneloss_avg_dict} as the
		objective function to minimize over a hypothesis space $\hypospace$.
		Two obstacles stand in the way.
		First, as a function of the model parameters of
		$\hypothesis$, the average $0/1$ loss is piecewise
		constant: it changes only when the decision boundary crosses
		a data point, and between two such crossings its
		gradient is zero. Gradient descent (GD) and its variants therefore
		receive no direction of improvement from it, and the average is
		neither convex nor smooth
		(Shalev-Shwartz and Ben-David, 2014, Sect.~12.3). Second, the problem is hard
		even for methods that use no gradient. If some
		linear classifier classifies every data point of the
		training set correctly, a linear program finds one
		(Shalev-Shwartz and Ben-David, 2014, Sect.~9.1). Without that guarantee, finding
		the linear classifier with the fewest misclassifications on a given
		training set is NP-hard, and so is finding one whose number of
		correct predictions is within a fixed factor of the
		largest achievable (Ben-David et al., 2003;
		Shalev-Shwartz and Ben-David, 2014, Sect.~8.2.2).
\par
		Fig.~\ref{fig_zerooneloss_krems_dict} shows both obstacles in the
		frost warning of the opening. Each of the $\samplesize = 365$ days
		of $2024$ at Krems is a data point whose single
		feature $\feature$ is the lowest temperature of the day
		and whose label is $\truelabel = +1$ if the lowest
		temperature of the following day is below $0\,^{\circ}\mathrm{C}$
		(frost) and $\truelabel = -1$ otherwise. Frost follows $68$ of
		the $365$ days. The warning compares the day's lowest temperature
		with a threshold $\thresholdfct$: the hypothesis
		$\hypothesis(\feature) = \thresholdfct - \feature$ predicts frost
		when it is positive, and the single model parameter
		$\thresholdfct$ selects a classifier from the
		hypothesis space of all thresholds. The $0/1$ loss of one
		day is a step in $\thresholdfct$, from $1$ to $0$ at the day's
		temperature, and the average over the year is a staircase with
		$195$ steps, one at each distinct temperature. Its smallest
		value, $40/365 = 0.110$, is attained by every threshold strictly
		between $0.2$ and $0.3$ and between $0.4$ and
		$0.6\,^{\circ}\mathrm{C}$: the set of minimizers is not a single
		point, and the slope of the staircase is zero at every threshold
		that is not a jump. A warning that never predicts frost has
		average $0/1$ loss $68/365 = 0.186$, and one that always
		predicts frost has $0.814$.
\par
		Practical classification methods replace the $0/1$
		loss in ERM by a surrogate loss function that is
		convex in $\hypothesis(\featurevec)$ and an upper bound on
		the $0/1$ loss (Shalev-Shwartz and Ben-David, 2014, Sect.~12.3). The
		hinge loss $\max\{0, 1 - \truelabel \cdot
		\hypothesis(\featurevec)\}$, which gives the support vector machine (SVM), lies on
		or above the $0/1$ loss for every margin
		(Shalev-Shwartz and Ben-David, 2014, Sect.~12.3). The logistic loss $\ln(1 +
		\exp(-\truelabel \cdot \hypothesis(\featurevec)))$, which gives
		logistic regression, equals $\ln 2 \approx 0.69$ at margin $0$ and
		is an upper bound only after division by $\ln 2$. Scaling a
		surrogate so that it passes through $1$ at margin $0$ is
		the usual convention when loss functions are compared
		(Bishop, 2006, Fig.~7.5;
		Hastie et al., 2009, Sect.~10.6). Because the
		surrogate is an upper bound, the risk of any
		hypothesis under the $0/1$ loss is at most its
		risk under the surrogate, so a hypothesis with a
		small surrogate risk misclassifies rarely
		(Shalev-Shwartz and Ben-David, 2014, Sect.~12.3). Both surrogates are also
		calibrated for classification: for a convex
		function of the margin that is differentiable
		at $0$ with a negative derivative there, every sequence of
		hypotheses whose surrogate risk tends to its
		smallest possible value has a $0/1$ risk that tends to the
		Bayes risk (Bartlett et al., Thms.~1 and 6). Over all
		functions of $\featurevec$, the hinge loss is
		minimized by the sign of $\prob{\truelabel = +1 \mid \featurevec}
		- 1/2$ and the logistic loss by the logarithm of the odds of
		$\truelabel = +1$, and the sign of either minimizer is the
		classifier with the Bayes risk
		(Hastie et al., 2009, Table~12.1). Unlike the
		$0/1$ loss, a surrogate changes when $\hypothesis$ is
		multiplied by a positive number, so it depends on the scale of
		$\hypothesis$ and not only on its sign.
\par
		For the frost warning, the average logistic loss divided by
		$\ln 2$ and the average hinge loss are convex
		functions of the threshold that lie above the staircase
		everywhere (Fig.~\ref{fig_zerooneloss_krems_dict}). Each has a
		single minimizer, $\thresholdfct = -0.04\,^{\circ}\mathrm{C}$ for
		the logistic loss and $0.06\,^{\circ}\mathrm{C}$ for the
		hinge loss, and at both the average $0/1$ loss is
		$41/365 = 0.112$, one day more than the smallest value of the
		staircase. At the minimizer of the logistic loss, the average
		logistic loss divided by $\ln 2$ is $0.405$ for $\hypothesis$,
		$0.333$ for $\hypothesis/2$, and $0.670$ for $2\hypothesis$, while
		the average $0/1$ loss is the same for all three.
		\begin{figure}[H]
		\centering
		\begin{tikzpicture}
		\begin{groupplot}[
			group style={group size=2 by 1, horizontal sep=1.7cm},
			width=0.5\linewidth, height=0.44\linewidth,
			axis lines=left,
			tick label style={font=\scriptsize},
			label style={font=\scriptsize, align=center},
			legend style={draw=none, fill=none, font=\scriptsize,
				at={(0.97,0.97)}, anchor=north east},
			legend cell align=left,
		]
			\nextgroupplot[
				xlabel={threshold $\thresholdfct$ ($^{\circ}$C)\\(a) one day: $2$ November, $\feature = 2.4\,^{\circ}$C},
				ylabel={loss of the day},
				xmin=-0.6, xmax=9.4, ymin=-0.05, ymax=3.2]
			\addplot[black, thick, const plot] table[col sep=comma, x=tau, y=zo]{zerooneloss_oneday.csv};
			\addlegendentry{0/1 loss}
			\addplot[black, thick, dashed] table[col sep=comma, x=tau, y=log2]{zerooneloss_oneday.csv};
			\addlegendentry{scaled logistic loss}
			\addplot[black, thick, dotted] table[col sep=comma, x=tau, y=hinge]{zerooneloss_oneday.csv};
			\addlegendentry{hinge loss}
			\nextgroupplot[
				xlabel={threshold $\thresholdfct$ ($^{\circ}$C)\\(b) average over the $365$ days},
				ylabel={average loss},
				xmin=-12, xmax=20, ymin=0, ymax=1.6]
			\addplot[black, thick, const plot] table[col sep=comma, x=tau, y=zo]{zerooneloss_stair.csv};
			\addplot[black, thick, dashed] table[col sep=comma, x=tau, y=log2]{zerooneloss_curves.csv};
			\addplot[black, thick, dotted] table[col sep=comma, x=tau, y=hinge]{zerooneloss_curves.csv};
		\end{groupplot}
		\end{tikzpicture}
		\caption{The frost warning $\hypothesis(\feature) = \thresholdfct
			- \feature$ at Krems as a function of its threshold
			$\thresholdfct$. (a) The $0/1$ loss (solid curve), the
			logistic loss divided by $\ln 2$ (dashed curve), and the
			hinge loss (dotted curve) of one day, $2$ November
			$2024$, whose lowest temperature was $\feature =
			2.4\,^{\circ}\mathrm{C}$ and which was followed by frost. The
			$0/1$ loss jumps from $1$ to $0$ at $\thresholdfct = 2.4$,
			where both surrogates equal $1$, and the surrogates lie on or
			above the $0/1$ loss at every threshold. (b) The averages of
			the same three losses over the $365$ days of $2024$.
			The average $0/1$ loss is a staircase with $195$ steps and
			its smallest value $0.110$ just above $0\,^{\circ}\mathrm{C}$;
			the two averaged surrogates are convex curves with one
			minimizer each, both within $0.1\,^{\circ}\mathrm{C}$ of
			$0\,^{\circ}\mathrm{C}$. Data generated by
			\texttt{pythondemos/zerooneloss.py}
			\label{fig_zerooneloss_krems_dict}}
		\end{figure}
		A small average $0/1$ loss on the training set is not the
		goal of training but a means to a small risk, and the
		two can differ. Fig.~\ref{fig_zerooneloss_overfit_dict} shows a
		training set on which a linear classifier $\hypothesis'$
		misclassifies one data point while a classifier
		$\hypothesis''$ whose decision boundary bends around that
		data point misclassifies none. A small shift of a
		feature vector near this decision boundary flips the
		prediction of $\hypothesis''$, so its zero training error
		does not indicate
		good generalization; this is overfitting. Restricting
		the hypothesis space to linear classifiers is a form of
		regularization, the route that shrinks the hypothesis space.
		\begin{figure}[H]
		\centering
		\begin{tikzpicture}[>=Stealth, scale=0.85]
			% Axes
			\draw[->, thick] (-0.3,0) -- (5.5,0) node[below] {$\feature_1$};
			\draw[->, thick] (0,-0.3) -- (0,4.5) node[left] {$\feature_2$};
			% Class 0 points (blue circles) — top-left cluster
			\foreach \x/\y in {0.5/3.5, 0.8/2.8, 1.2/3.8, 1.0/3.2, 1.6/3.0, 0.7/3.9} {
				\fill[blue] (\x,\y) circle (2pt);
			}
			% Class 1 points (red squares) — bottom-right cluster
			\foreach \x/\y in {3.5/1.0, 4.0/1.5, 3.8/0.8, 4.3/1.2, 3.2/1.8, 4.5/0.5} {
				\fill[red] (\x,\y) +(-2pt,-2pt) rectangle +(2pt,2pt);
			}
			% One class-1 outlier near class 0
			\fill[red] (1.5,2.5) +(-2pt,-2pt) rectangle +(2pt,2pt);
			% Simple linear boundary (good generalization)
			\draw[thick, dashed, gray] (0,0.5) -- (5,4.5)
				node[right] {$\hypothesis'$ (1 error)};
			% Overfitting boundary: lasso around the red points (cluster +
			% outlier), keeping all blue points outside.
			\draw[thick, blue!60!black]
				plot[smooth cycle, tension=0.7] coordinates {
					(1.3, 2.75)
					(1.7, 2.75)
					(2.3, 2.45)
					(3.2, 2.15)
					(4.7, 2.05)
					(5.1, 0.30)
					(3.0, -0.10)
					(1.8, 1.00)
					(1.3, 2.20)
				};
			\node[blue!60!black, anchor=west] at (4.7, 2.05)
				{$\hypothesis''$ (0 errors)};
		\end{tikzpicture}
		\caption{Two classifiers on one training set of
			data points with two features, drawn as blue
			circles and red squares by their label value. The
			linear classifier $\hypothesis'$ (dashed line) misclassifies one
			data point, the red square among the blue circles, so
			its average $0/1$ loss on the training set is
			$1/13$. The classifier $\hypothesis''$ (solid curve)
			bends its decision boundary around that data point
			and reaches an average $0/1$ loss of zero, but a small
			shift of a feature vector near this decision boundary
			flips its prediction
			\label{fig_zerooneloss_overfit_dict}}
		\end{figure}

\subsection{Cross References}
loss, loss function, classification, binary classification, classifier, accuracy, training error, risk, Bayes risk, margin, hinge loss, logistic loss, ERM, SVM, logistic regression, confusion matrix, imbalanced data

\subsection{References}
\begin{enumerate}
  \item Bartlett et al.. Convexity, Classification, and Risk Bounds. Journal of the American Statistical Association, 101(473), pp.~138--156.
  \item Ben-David et al. (2003). On the Difficulty of Approximately Maximizing Agreements. Journal of Computer and System Sciences, 66(3), pp.~496--514.
  \item Bishop (2006). Pattern Recognition and Machine Learning. Springer Science+Business Media, New York, NY, 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}
