\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).
\renewcommand{\boundary}[1]{\partial #1}
\newcommand{\decreg}[1]{\mathcal{R}_{#1}}
\newcommand{\defeq}{:=}
\newcommand{\feature}{x}
\newcommand{\featurespace}{\mathcal{X}}
\newcommand{\featurevec}{\vx}
\newcommand{\hypothesis}{h}
\newcommand{\labelspace}{\mathcal{Y}}
\newcommand{\nrcategories}{K}
\newcommand{\predictedlabel}{\widehat{\truelabel}}
\newcommand{\truelabel}{y}
\newcommand{\vw}[0]{{\bf w}}
\newcommand{\vx}[0]{{\bf x}}
\newcommand{\weight}{w}
\newcommand{\weights}{\vw}

\begin{document}

\section{decision region}

\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}
A decision region of a classifier is the set of all
		feature vectors that the classifier maps to one
		particular label value. The decision regions partition the
		feature space, one region per label value, and all
		feature vectors in the same region obtain the same
		prediction, so the decision regions determine the
		classifier completely. The union of the boundaries
		of the decision regions is the decision boundary. The shape
		of the decision regions depends on the model: a
		linear classifier has halfspaces, a decision tree has
		unions of axis-parallel rectangles, and logistic regression on
		polynomial features has regions separated by a curve.

\subsection{Definition}
A frost warning predicts from
		the minimum and the maximum air temperature of a day whether the
		following night brings frost. Any rule that gives this warning
		splits the pairs of temperatures into two parts: the pairs for
		which it predicts frost and the pairs for which it does not.
		Each part is a decision region of the rule. In general, a
		classifier is a hypothesis $\hypothesis\colon
		\featurespace \rightarrow \labelspace$ with a finite
		label space $\labelspace$. Its decision region for the
		label value $\predictedlabel \in \labelspace$ is the set
		of feature vectors that it maps to this value,
		$$
		\decreg{\predictedlabel} \defeq \big\{ \featurevec \in
		\featurespace : \hypothesis(\featurevec) = \predictedlabel
		\big\} \text{.}
		$$
		The decision regions partition the feature space: every
		feature vector lies in exactly one of them, there is one
		region per label value, and a region may consist of
		several separate pieces (Bishop, 2006, Sect.~1.5.1). All
		feature vectors in the same decision region obtain the same
		prediction, so the decision regions determine the
		classifier completely. The boundary
		$\boundary{\decreg{\predictedlabel}}$ of a decision region is
		the set of feature vectors such that every
		neighborhood contains elements of $\decreg{\predictedlabel}$
		and of its complement. The union of these boundaries
		over all label values is the decision boundary.
\par
		The shape of the decision regions depends on the model.
		A linear classifier with $\hypothesis(\featurevec) =
		\operatorname{sign}(\weights^{\top} \featurevec + \weight_{0})$
		has the two halfspaces on either side of the
		hyperplane $\weights^{\top} \featurevec + \weight_{0} = 0$
		as its decision regions (Bishop, 2006, Sect.~4.1.1). For
		more than two label values, a linear classifier predicts the
		value with the largest of $\nrcategories$ linear scores. Each
		decision region is then an intersection of $\nrcategories - 1$
		halfspaces and therefore convex
		(Bishop, 2006, Sect.~4.1.2). A decision tree compares
		one feature with a threshold at each split, so its
		decision regions are unions of axis-parallel rectangles
		(Hastie et al., 2009, Sect.~9.2.1).
		Logistic regression on polynomial features has decision regions
		separated by a curve, the level set of a polynomial.
\par
		Fig.~\ref{fig_decisionregion_dict} shows the decision regions
		of three classifiers learned from the same
		data points with two features: a linear classifier, a
		decision tree, and logistic regression on polynomial
		features. A data point whose label differs
		from the label value of the region containing its
		feature vector is misclassified, and the fraction of such
		data points is the average $0/1$ loss. The two
		label values are separated by a curve and not by any
		straight line, so the linear classifier misclassifies half of the
		data points, while the other two misclassify none.
		\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 $\feature_{1}$},
			ylabel={feature $\feature_{2}$},
			xmin=-2.6, xmax=2.6, ymin=-2.6, ymax=2.6,
			xtick={-2,0,2}, ytick={-2,0,2},
			tick label style={font=\scriptsize},
			label style={font=\scriptsize},
			colormap={bw}{color=(white) color=(black!25)},
			point meta min=-1, point meta max=1,
		]
			\nextgroupplot[xlabel={feature $\feature_{1}$\\(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]
				{decisionregion_regions.csv};
			\addplot[only marks, mark=square*, mark size=1.6pt, black,
				restrict expr to domain={\thisrow{y}}{1:1}]
				table[col sep=comma, x=x1, y=x2]{decisionregion_points.csv};
			\addplot[only marks, mark=o, mark size=1.6pt, black,
				restrict expr to domain={\thisrow{y}}{-1:-1}]
				table[col sep=comma, x=x1, y=x2]{decisionregion_points.csv};
			\node[font=\scriptsize, anchor=west] at (axis cs:-2.4,2.2) {$\decreg{+1}$};
			\node[font=\scriptsize, anchor=west] at (axis cs:-2.4,-2.2) {$\decreg{-1}$};
			\nextgroupplot[xlabel={feature $\feature_{1}$\\(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]
				{decisionregion_regions.csv};
			\addplot[only marks, mark=square*, mark size=1.6pt, black,
				restrict expr to domain={\thisrow{y}}{1:1}]
				table[col sep=comma, x=x1, y=x2]{decisionregion_points.csv};
			\addplot[only marks, mark=o, mark size=1.6pt, black,
				restrict expr to domain={\thisrow{y}}{-1:-1}]
				table[col sep=comma, x=x1, y=x2]{decisionregion_points.csv};
			\nextgroupplot[xlabel={feature $\feature_{1}$\\(c) logistic regression on\\polynomial features}]
			\addplot[matrix plot*, point meta=explicit, mesh/cols=60,
				mesh/ordering=rowwise]
				table[col sep=comma, x=x1, y=x2, meta=poly]
				{decisionregion_regions.csv};
			\addplot[only marks, mark=square*, mark size=1.6pt, black,
				restrict expr to domain={\thisrow{y}}{1:1}]
				table[col sep=comma, x=x1, y=x2]{decisionregion_points.csv};
			\addplot[only marks, mark=o, mark size=1.6pt, black,
				restrict expr to domain={\thisrow{y}}{-1:-1}]
				table[col sep=comma, x=x1, y=x2]{decisionregion_points.csv};
		\end{groupplot}
		\end{tikzpicture}
		\end{center}
		\caption{Decision regions of three classifiers learned
			from the same ten data points with two features.
			Filled squares are data points with label
			$\truelabel = +1$, and open circles are data points
			with label $\truelabel = -1$. The shaded area is the
			decision region $\decreg{+1}$, the unshaded area the decision
			region $\decreg{-1}$, and the border between them the
			decision boundary. (a) A linear classifier, whose regions
			are two half-planes. (b) A decision tree of depth four,
			whose regions are unions of axis-parallel rectangles. (c)
			Logistic regression on all monomials of the two features up
			to degree two, whose regions are separated by a curve. Data
			generated by \texttt{pythondemos/decisionregion.py}
			\label{fig_decisionregion_dict}}
		\end{figure}

\subsection{Cross References}
classifier, classification, binary classification, decision boundary, boundary, neighborhood, linear classifier, decision tree, logistic regression, halfspace, hyperplane, feature space, label space, $0/1$ loss

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