\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{\feature}{x}
\newcommand{\featurespace}{\mathcal{X}}
\newcommand{\featurevec}{\vx}
\newcommand{\hypothesis}{h}
\newcommand{\labelspace}{\mathcal{Y}}
\newcommand{\norm}[1]{\Vert  {#1} \Vert}
\newcommand{\predictedlabel}{\widehat{\truelabel}}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\truelabel}{y}
\newcommand{\vw}[0]{{\bf w}}
\newcommand{\vx}[0]{{\bf x}}
\newcommand{\weight}{w}
\newcommand{\weights}{\vw}

\begin{document}

\section{binary classification}

\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}
two-class classification

\subsection{Abstract}
Binary classification refers to machine learning (ML) applications with
		a binary label space. The goal of binary classification is to
		assign each data point to one of two classes, each class
		represented by one of the two label values. Strictly
		speaking, a binary classifier is a hypothesis map from
		the feature space to a binary label space. However, it
		is customary to construct such a classifier by comparing the
		value of a real-valued hypothesis map against a threshold.
		Linear classifiers are obtained from the sign of a linear
		hypothesis map. A binary classifier partitions the
		feature space into two decision regions separated by a
		decision boundary, which is a hyperplane for a
		linear classifier. The natural loss function is the
		$0/1$ loss, whose average over a dataset is $1$ minus
		the accuracy. However, this loss function is hard to
		optimize for training methods, and its average on
		imbalanced data is dominated by the majority label
		value, so it does not indicate which of the two kinds of mistake
		a classifier makes. Practical methods therefore often use
		other loss functions for model training and
		validation.

\subsection{Definition}
A frost warning answers
		one question: will the temperature in the coming night fall below
		$0$ degrees Celsius? The answer is yes or no, nothing in between.
		An email is spam or not. A credit application defaults or not. A
		biopsy image is malignant or benign. Binary classification is the
		machine learning (ML) problem behind all of these questions: predict, from the
		features of a data point, which of two values its
		label, a number $\truelabel$, takes.
\par
		Binary classification is classification with a
		label space $\labelspace$ that holds two elements. Each
		data point carries one label, and that label
		takes one of the two values. The two values are usually written
		(or encoded) as $\labelspace = \{-1, +1\}$ or $\labelspace =
		\{0, 1\}$. The choice of the two label values (the
		encoding) is a convention and irrelevant for the basic properties
		of binary classification methods. However, mathematical
		expressions about them often assume a particular encoding, such
		as $\{-1, +1\}$, and need to be modified accordingly if a
		different encoding, such as $\{0, 1\}$, is used.
\par
		Strictly speaking, a binary classifier is a hypothesis
		map that takes values in a binary label space $\labelspace$.
		It is usually built from a real-valued hypothesis map
		$\hypothesis: \featurespace \rightarrow \reals$ by comparing its
		value against a threshold. For the label encoding
		$\labelspace = \{-1, +1\}$ and the threshold $0$, a
		data point is then classified by the sign,
		$\predictedlabel = \operatorname{sign}(\hypothesis(\featurevec))$.
		The classifier partitions the feature space into two
		decision regions, one per label value. They are
		separated by the decision boundary, the set of $\featurevec$
		with $\hypothesis(\featurevec) = 0$. The product $\truelabel \cdot
		\hypothesis(\featurevec)$ is the margin of $\hypothesis$ on
		the data point $(\featurevec, \truelabel)$. It is positive
		exactly when the prediction is right.
\par
		For a linear classifier the real-valued hypothesis is
		$\hypothesis(\featurevec) = \weights^{\top} \featurevec + \weight_{0}$
		with model parameters $\weights$ and $\weight_{0}$, so the
		decision boundary is the hyperplane $\weights^{\top}
		\featurevec + \weight_{0} = 0$, a straight line when there are two
		features (Bishop, 2006, Sect.~4.1.1).
		The predicted label value is the side of that
		hyperplane on which $\featurevec$ lies, and the distance of
		$\featurevec$ from the hyperplane is $|\hypothesis(\featurevec)|
		/ \norm{\weights}$. A data point that lies on the side of the
		other label value is misclassified. Its $0/1$ loss is
		$1$ (Fig.~\ref{fig_binclass_dict}).
		\begin{figure}[H]
		\begin{center}
		\begin{tikzpicture}
		\begin{axis}[
			width=0.72\linewidth,
			axis equal image,
			axis lines=left,
			xlabel={feature $\feature_{1}$},
			ylabel={feature $\feature_{2}$},
			xmin=-0.3, xmax=7.0, ymin=-0.3, ymax=6.0,
			xtick={0,2,4,6}, ytick={0,2,4,6},
			label style={font=\small},
			tick label style={font=\small},
			]
			\addplot[black, thick, domain=0:5.6, samples=2]
				{4.9 - 0.85*x};
			\node[font=\small, anchor=north, rotate=-40.4, inner sep=2pt]
				at (axis cs:4.5,1.075) {$\hypothesis(\featurevec) = 0$};
			\addplot[only marks, mark=*, mark size=2.6pt, black]
				coordinates
				{(3.4,3.5) (4.6,3.0) (2.4,4.4) (5.2,2.0)};
			\addplot[only marks, mark=square, mark size=2.8pt, black]
				coordinates
				{(0.8,1.6) (1.8,2.4) (1.0,3.2) (4.0,2.6)};
			\node[font=\small, anchor=west] at (axis cs:5.4,2.0)
				{$\truelabel = +1$};
			\node[font=\small, anchor=north] at (axis cs:0.8,1.4)
				{$\truelabel = -1$};
			\draw[<->, >=stealth, thick] (axis cs:2.4,4.4) -- (axis cs:1.64,3.506)
				node[midway, above left, font=\small] {$\truelabel \cdot \hypothesis(\featurevec)$};
			\node[font=\small] at (axis cs:4.9,4.7) {$\hypothesis(\featurevec) > 0$};
			\node[font=\small] at (axis cs:1.1,0.4) {$\hypothesis(\featurevec) < 0$};
		\end{axis}
		\end{tikzpicture}
		\end{center}
		\caption{Binary classification of data points with two
			features using a linear classifier. The
			decision boundary $\hypothesis(\featurevec) = 0$ is a
			hyperplane, here a straight line, and it cuts the
			feature space into the two decision regions of the
			label values $\truelabel = +1$ (filled circles, where
			$\hypothesis(\featurevec) > 0$) and $\truelabel = -1$ (open
			squares, where $\hypothesis(\featurevec) < 0$). The
			model parameters are scaled so that $\norm{\weights} = 1$,
			and the double arrow shows the margin $\truelabel \cdot
			\hypothesis(\featurevec)$ of one data point, which is then
			its distance from the line. One of the $8$ data points
			is misclassified: it incurs a $0/1$ loss of $1$, and
			the average $0/1$ loss is $1/8$
			\label{fig_binclass_dict}}
		\end{figure}
		The shape of the decision regions depends on the
		model, and so does how closely they follow the
		training set. Fig.~\ref{fig_binclass_regions_dict} shows three
		classifiers learned from the same $30$ days of weather
		recordings. The linear classifier divides the feature space
		into two half-planes and misclassifies three of the $30$ days.
		The decision tree compares one feature with a
		threshold at each of its splits, so its decision regions
		are unions of axis-parallel rectangles
		(Hastie et al., 2009, Sect.~9.2.1). Grown until every leaf
		holds a single label value, it predicts the label value
		of every day correctly. The artificial neural network (ANN) has a curve as
		decision boundary and also predicts every day correctly. On
		$170$ further days, the linear classifier is
		the most accurate of the three. The tree and the ANN have
		adapted their decision regions to single days of the
		training set, which is overfitting.
		\begin{figure}[H]
		\begin{center}
		\begin{tikzpicture}
		\begin{groupplot}[
			group style={group size=3 by 1, horizontal sep=0.9cm,
				ylabels at=edge left},
			xlabel style={align=center},
			width=0.37\linewidth, height=0.37\linewidth,
			axis lines=left,
			xlabel={$\feature_{1}$ ($^{\circ}$C)},
			ylabel={maximum temperature $\feature_{2}$ ($^{\circ}$C)},
			xmin=-4.2, xmax=14.2, ymin=-2.3, ymax=27.3,
			xtick={0,5,10}, ytick={0,10,20},
			tick label style={font=\scriptsize},
			label style={font=\scriptsize},
			title style={font=\small},
			colormap={bw}{color=(white) color=(black!25)},
			point meta min=-1, point meta max=1,
		]
			\nextgroupplot[xlabel={$\feature_{1}$ ($^{\circ}$C)\\(a) linear classifier}]
			\addplot[matrix plot*, point meta=explicit, mesh/cols=60,
				mesh/ordering=rowwise]
				table[col sep=comma, x=x1, y=x2, meta=lin]
				{binclass_regions.csv};
			\addplot[only marks, mark=*, mark size=1.6pt, black,
				restrict expr to domain={\thisrow{y}*\thisrow{sub}}{1:1}]
				table[col sep=comma, x=x1, y=x2]{binclass_data.csv};
			\addplot[only marks, mark=square, mark size=1.6pt, black,
				restrict expr to domain={\thisrow{y}*\thisrow{sub}}{-1:-1}]
				table[col sep=comma, x=x1, y=x2]{binclass_data.csv};
			\nextgroupplot[xlabel={$\feature_{1}$ ($^{\circ}$C)\\(b) decision tree}]
			\addplot[matrix plot*, point meta=explicit, mesh/cols=60,
				mesh/ordering=rowwise]
				table[col sep=comma, x=x1, y=x2, meta=tree]
				{binclass_regions.csv};
			\addplot[only marks, mark=*, mark size=1.6pt, black,
				restrict expr to domain={\thisrow{y}*\thisrow{sub}}{1:1}]
				table[col sep=comma, x=x1, y=x2]{binclass_data.csv};
			\addplot[only marks, mark=square, mark size=1.6pt, black,
				restrict expr to domain={\thisrow{y}*\thisrow{sub}}{-1:-1}]
				table[col sep=comma, x=x1, y=x2]{binclass_data.csv};
			\nextgroupplot[xlabel={$\feature_{1}$ ($^{\circ}$C)\\(c) ANN}]
			\addplot[matrix plot*, point meta=explicit, mesh/cols=60,
				mesh/ordering=rowwise]
				table[col sep=comma, x=x1, y=x2, meta=ann]
				{binclass_regions.csv};
			\addplot[only marks, mark=*, mark size=1.6pt, black,
				restrict expr to domain={\thisrow{y}*\thisrow{sub}}{1:1}]
				table[col sep=comma, x=x1, y=x2]{binclass_data.csv};
			\addplot[only marks, mark=square, mark size=1.6pt, black,
				restrict expr to domain={\thisrow{y}*\thisrow{sub}}{-1:-1}]
				table[col sep=comma, x=x1, y=x2]{binclass_data.csv};
		\end{groupplot}
		\end{tikzpicture}
		\end{center}
		\caption{Decision regions of three binary
			classifiers learned from the same $30$ data points.
			Each data point represents the weather conditions around a
			specific day: its features are the minimum and the
			maximum temperature of the day in degrees Celsius. Filled
			circles are days followed by frost ($\truelabel = +1$), open
			squares the other days ($\truelabel = -1$). The shaded area is
			the decision region where the classifier predicts
			$+1$. (a) A linear classifier,
			whose regions are two half-planes. (b) A decision tree
			grown until every leaf holds a single label value, whose
			regions are unions of axis-parallel rectangles. (c) An
			ANN with one hidden layer of $32$ units, whose
			decision boundary is a curve. Data generated by
			\texttt{pythondemos/binclass.py}
			\label{fig_binclass_regions_dict}}
		\end{figure}
		The natural loss function for binary classification is the
		$0/1$ loss. It is $1$ for a wrong label value and $0$
		for a right one. Its average over a dataset is therefore the
		fraction of misclassified data points, i.e., $1$ minus the
		accuracy. Empirical risk minimization (ERM) with the $0/1$ loss results in
		computationally hard optimization problems
		(Shalev-Shwartz and Ben-David, 2014, Ch.~12). Practical methods therefore minimize
		a convex surrogate of the $0/1$ loss
		(Shalev-Shwartz and Ben-David, 2014, Sect.~12.3). The hinge loss gives the
		support vector machine (SVM), and the logistic loss gives logistic regression.
		Fig.~\ref{fig_binclass_margin_dict} shows the three
		loss functions as functions of the margin.
		\begin{figure}[H]
		\begin{center}
		\begin{tikzpicture}
		\begin{axis}[
			width=0.78\linewidth, height=0.50\linewidth,
			axis lines=left,
			xlabel={margin $\truelabel \cdot \hypothesis(\featurevec)$},
			ylabel={loss},
			xmin=-2.6, xmax=2.6, ymin=-0.1, ymax=3.7,
			xtick={-2,-1,0,1,2}, ytick={0,1,2,3},
			label style={font=\small},
			tick label style={font=\small},
			legend style={draw=none, fill=none, font=\small,
				at={(0.98,0.98)}, anchor=north east},
			legend cell align=left,
			]
			\addplot[black, thick, domain=-2.6:0, samples=2] {1};
			\addlegendentry{$0/1$ loss}
			\addplot[black, thick, domain=0:2.6, samples=2, forget plot] {0};
			\addplot[only marks, mark=*, mark size=2pt, black, forget plot]
				coordinates {(0,1)};
			\addplot[only marks, mark=o, mark size=2pt, black, forget plot]
				coordinates {(0,0)};
			\addplot[black, thick, dashed, domain=-2.6:2.6, samples=100]
				{max(0, 1 - x)};
			\addlegendentry{hinge loss}
			\addplot[black, thick, dotted, domain=-2.6:2.6, samples=100]
				{ln(1 + exp(-x))};
			\addlegendentry{logistic loss}
		\end{axis}
		\end{tikzpicture}
		\end{center}
		\caption{The three loss functions of binary classification
			(with label space $\labelspace = \{-1, +1\}$) as
			functions of the margin $\truelabel \cdot
			\hypothesis(\featurevec)$: the $0/1$ loss (solid curve;
			at margin $0$ it takes the value $1$, marked by a filled
			circle, and not the value $0$, marked by an open circle), the
			hinge loss (dashed curve), and the logistic loss (dotted
			curve). Both surrogates are convex and decreasing
			functions of the margin, so a more negative margin
			costs more, while the $0/1$ loss only jumps once, at
			margin $0$
			\label{fig_binclass_margin_dict}}
		\end{figure}
		The average $0/1$ loss is not only challenging as an
		objective for training but can also be misleading. In
		particular, the average $0/1$ loss (and the associated
		accuracy) does not indicate which of the two mistakes a
		classifier makes. The two kinds of mistake, a wrong $+1$ and
		a wrong $-1$, usually have different costs. On imbalanced data,
		the constant baseline that always returns the majority
		label value already reaches a high accuracy.
		Both are reasons to report the confusion matrix, and the precision,
		recall, and F$_1$ score computed from it, beside the
		accuracy.
\par
		In the frost warning of the opening, the features of a
		data point are the minimum and the maximum air temperature
		of one day. Its
		label is $\truelabel = +1$ if the minimum temperature of the
		following night falls below $0$ degrees Celsius, and $\truelabel =
		-1$ otherwise. A wrong $-1$ leaves a fruit grower's blossoms
		unprotected in a frost. A wrong $+1$ only costs one night of
		covering or heating them. The two mistakes are therefore not
		interchangeable, and the classifier is chosen so that wrong
		$-1$ predictions are rare.

\subsection{Cross References}
classification, multi-label classification, classifier, decision boundary, $0/1$ loss, logistic loss, logistic regression, accuracy, confusion matrix, imbalanced data, baseline

\subsection{References}
\begin{enumerate}
  \item Bishop (2006). Pattern Recognition and Machine Learning. Springer Science+Business Media, New York, NY, 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}