\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{\datapointspace}{\mathcal{Z}}
\newcommand{\defeq}{:=}
\newcommand{\feature}{x}
\newcommand{\featuredim}{d}
\newcommand{\featurespace}{\mathcal{X}}
\newcommand{\featuretrafo}{\phi}
\newcommand{\featuretrafovec}{{\bf \Phi}}
\newcommand{\featurevec}{\vx}
\newcommand{\hilbertspace}{\mathcal{H}}
\newcommand{\hypothesis}{h}
\newcommand{\innerprodgeneric}[3]{\langle #1, #2 \rangle_{#3}}
\newcommand{\kernel}{k}
\newcommand{\kernelmap}[2]{k\big(#1,#2\big)}
\newcommand{\labelspace}{\mathcal{Y}}
\newcommand{\normgeneric}[2]{\mleft\lVert #1 \mright\rVert_{#2}}
\newcommand{\nrfeatures}{\featuredim}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\sampleidx}{r}
\newcommand{\samplesize}{m}
\newcommand{\vw}[0]{{\bf w}}
\newcommand{\vx}[0]{{\bf x}}
\newcommand{\vz}[0]{{\bf z}}
\newcommand{\weights}{\vw}

\begin{document}

\section{feature space}

\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}
input space, instance space

\subsection{Abstract}
The feature space of a machine learning (ML) application is the set of all
		values that the feature vector of a data point can take. It
		is the range of the feature transformation that maps a
		data point to its feature vector. For data points with
		$\nrfeatures$ numeric features the feature space is usually
		the Euclidean space $\reals^{\nrfeatures}$, whose Euclidean distance
		and inner product are what nearest neighbor methods and
		linear models use. The same data points placed in two
		feature spaces have different nearest neighbors and yield
		different hypotheses, so the choice of the feature space is
		part of the model, and dropping a feature is
		model pruning. A feature space can also be a finite set, such
		as the months of a year, or a set of strings or graphs, which
		a kernel makes accessible. A kernel brings a second
		feature space with it, a Hilbert space of possibly infinite
		dimension in which the kernel is the inner product
		and which a kernel method uses without ever forming its
		elements.

\subsection{Definition}
A day at Krems an der Donau can be
		described by a single number, its morning minimum temperature, or
		by two numbers, that minimum and the maximum temperature of the
		previous day (GeoSphere Austria, 2026). The first description turns
		every day into a point of the real line $\reals$, the second into
		a point of the plane $\reals^{2}$. The set of all values that the
		feature vector of a data point can take is the feature space
		$\featurespace$ of a machine learning (ML) application. A
		feature transformation
		\begin{equation}
			\label{equ_featurespace_map_dict}
			\featuretrafovec: \datapointspace \rightarrow \featurespace,
			\quad \featurevec = \featuretrafovec(\datapoint) \text{,}
		\end{equation}
		maps a data point $\datapoint$ from the set $\datapointspace$
		of all data points of the application to its feature vector,
		and the feature space is the range of this map
		(Shalev-Shwartz and Ben-David, 2014, Sect.~16.1). The two descriptions of a day are
		two feature transformations \eqref{equ_featurespace_map_dict}
		of the same data points, with the feature spaces $\reals$ and
		$\reals^{2}$.
\par
		For data points with $\nrfeatures$ numeric features,
		the default feature space is the Euclidean space
		$\reals^{\nrfeatures}$ (Axler, 2024, Sect.~1A). The word
		\emph{space}, rather than \emph{set}, says that $\featurespace$
		carries structure that an ML method uses: the Euclidean distance
		$\normgeneric{\featurevec - \featurevec'}{2}$ makes
		$\reals^{\nrfeatures}$ a metric space, and the
		inner product $\featurevec^{\top} \featurevec'$ makes it a
		Hilbert space. The $k$-nearest neighbors ($k$-NN) method uses the distance:
		the nearest neighbor of a data point with
		feature vector $\featurevec$ in a training set with
		feature vectors $\featurevec^{(1)}, \ldots,
		\featurevec^{(\samplesize)}$ is $\featurevec^{(\sampleidx^{\star})}$
		with
		\begin{equation}
			\label{equ_featurespace_nn_dict}
			\sampleidx^{\star} \defeq
			\argmin_{\sampleidx = 1, \ldots, \samplesize}
			\normgeneric{\featurevec - \featurevec^{(\sampleidx)}}{2}
			\text{,}
		\end{equation}
		and the label of that neighbor is the prediction
		for $\featurevec$ (Cover and Hart, 1967;
		Hastie et al., 2009, Sect.~2.3.2). A
		linear model uses the inner product: its hypotheses
		are the maps $\hypothesis(\featurevec) = \weights^{\top} \featurevec
		+ b$ with model parameters $\weights \in \reals^{\nrfeatures}$ and
		$b \in \reals$ (Hastie et al., 2009, Sect.~2.3.1).
\par
		Which feature space the $366$ days of $2024$ at Krems are placed in
		changes what both methods deliver. The label of a day is its
		maximum daytime temperature. On $22$ May $2024$ the morning minimum
		was $14.4$ degrees Celsius, the maximum of the previous day $22.7$,
		and the maximum of the day itself $22.4$. In the feature space
		$\reals$, the nearest neighbor \eqref{equ_featurespace_nn_dict}
		of this day among the other $365$ days is $4$ September, with the
		same morning minimum $14.4$ but a maximum of $34.1$. In $\reals^{2}$
		it is $11$ June, with the feature vector $(14.5, 22.7)^{\top}$ and
		a maximum of $20.2$ (Fig.~\ref{fig_featurespace_demo_dict}). The
		prediction by the nearest neighbor misses the
		label by $11.7$ degrees in the first feature space and by
		$2.2$ degrees in the second, and $346$ of the $366$ days have a
		different nearest neighbor in $\reals$ than in $\reals^{2}$. A
		linear model learned by least squares from all $366$ days has
		a training mean squared error (MSE) of $19.2$ in $\reals$ and of $9.2$ in
		$\reals^{2}$.
\par
		The choice of the feature space is therefore part of the
		model. A hypothesis space is a set of maps $\hypothesis:
		\featurespace \rightarrow \labelspace$ into the label space
		$\labelspace$, so changing $\featurespace$ changes which maps it
		contains. The hypotheses $\hypothesis(\feature) = w \feature
		+ b$ on $\reals$ are, read as maps of the pair $(\feature_{1},
		\feature_{2})^{\top}$, the hypotheses $w_{1} \feature_{1} +
		w_{2} \feature_{2} + b$ on $\reals^{2}$ with $w_{2} = 0$. Dropping a
		feature thus shrinks the hypothesis space, which is
		model pruning, one of the three routes that
		regularization distinguishes: the training error of empirical risk minimization (ERM)
		cannot fall ($19.2$ against $9.2$), while the smaller hypothesis space
		may generalize better. Feature learning methods and
		feature standardization change the feature space in the other
		direction, by learning or rescaling the feature transformation
		\eqref{equ_featurespace_map_dict}. Rescaling one feature
		changes the distances in the nearest neighbor rule
		\eqref{equ_featurespace_nn_dict}, and with them the nearest
		neighbors.
		\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.46\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.03,0.97)}, anchor=north west},
			legend cell align=left,
		]
			\nextgroupplot[
				xlabel={morning minimum temperature\\(a) the feature space $\reals$ is the horizontal axis},
				ylabel={label: maximum daytime temperature},
				xmin=-9, xmax=23, ymin=-5, ymax=41]
			\addplot[black, thin, forget plot]
				table[col sep=comma, x=tmin, y=yhat]{featurespace_line_plot.csv};
			\addplot[only marks, mark=o, mark size=1.6pt, black,
				restrict expr to domain={\thisrow{role}}{0:0}]
				table[col sep=comma, x=tmin, y=tmax]{featurespace_points_plot.csv};
			\addplot[only marks, mark=square*, mark size=2pt, black,
				restrict expr to domain={\thisrow{role}}{1:1}]
				table[col sep=comma, x=tmin, y=tmax]{featurespace_points_plot.csv};
			\addplot[only marks, mark=triangle, mark size=2.4pt, black,
				restrict expr to domain={\thisrow{role}}{2:2}]
				table[col sep=comma, x=tmin, y=tmax]{featurespace_points_plot.csv};
			\addplot[only marks, mark=diamond, mark size=2.4pt, black,
				restrict expr to domain={\thisrow{role}}{3:3}]
				table[col sep=comma, x=tmin, y=tmax]{featurespace_points_plot.csv};
			\nextgroupplot[
				xlabel={morning minimum temperature\\(b) the feature space $\reals^{2}$ is the plane},
				ylabel={previous day's maximum temperature},
				xmin=-9, xmax=23, ymin=0, ymax=52]
			\addplot[only marks, mark=o, mark size=1.6pt, black,
				restrict expr to domain={\thisrow{role}}{0:0}]
				table[col sep=comma, x=tmin, y=prevtmax]{featurespace_points_plot.csv};
			\addlegendentry{days (circles)}
			\addplot[only marks, mark=square*, mark size=2pt, black,
				restrict expr to domain={\thisrow{role}}{1:1}]
				table[col sep=comma, x=tmin, y=prevtmax]{featurespace_points_plot.csv};
			\addlegendentry{22 May (square)}
			\addplot[only marks, mark=triangle, mark size=2.4pt, black,
				restrict expr to domain={\thisrow{role}}{2:2}]
				table[col sep=comma, x=tmin, y=prevtmax]{featurespace_points_plot.csv};
			\addlegendentry{4 Sep (triangle)}
			\addplot[only marks, mark=diamond, mark size=2.4pt, black,
				restrict expr to domain={\thisrow{role}}{3:3}]
				table[col sep=comma, x=tmin, y=prevtmax]{featurespace_points_plot.csv};
			\addlegendentry{11 Jun (diamond)}
		\end{groupplot}
		\end{tikzpicture}
		\caption{The same days of $2024$ at Krems in two feature spaces:
			every $18$th of the $366$ days (circles), $22$ May (filled
			square), its nearest neighbor in $\reals$, $4$ September
			(triangle), and its nearest neighbor in $\reals^{2}$, $11$
			June (diamond), $23$ days in all. (a) The feature space $\reals$
			of the morning minimum temperature, drawn against the
			label; the distance between two days is the
			horizontal gap between their markers, and the solid line is the
			linear model hypothesis learned by least squares.
			(b) The feature space $\reals^{2}$ of the morning minimum and the
			previous day's maximum; the filled square and the diamond almost
			coincide, while the triangle is far from both. Data generated by
			\texttt{pythondemos/featurespace.py}
			\label{fig_featurespace_demo_dict}}
		\end{figure}
		A feature space need not be a Euclidean space. Describing a day by
		its month gives the finite feature space $\featurespace = \{1,
		\ldots, 12\}$. A hypothesis on it is a table of $12$ values,
		and the table that minimizes the training MSE holds the
		monthly means of the maximum temperature, with an MSE of
		$17.0$. One-hot encoding (see feature vector) maps the $12$ months
		to the $12$ unit vectors of $\reals^{12}$, and on these every
		table is a linear model: least squares learns the same $12$
		means. Under the discrete metric, which is $0$ for two
		equal and $1$ for two different months, each of the $30$ other days
		of May is a nearest neighbor of $22$ May. Other feature spaces
		without arithmetic are the strings over an alphabet, for text
		documents and DNA sequences, and the graphs, for molecules.
		A method then accesses the feature space through a kernel
		that measures the similarity of two of its elements
		(Schölkopf and Smola, 2002, Sect.~13.2;
		Vishwanathan et al., 2010). The hours of a day, placed
		on a cycle graph, are the feature space of
		kernel ridge regression.
\par
		A kernel brings a second feature space with it. A kernel
		$\kernel: \featurespace \times \featurespace \rightarrow \reals$ is
		an inner product of transformed feature vectors
		$\featuretrafo(\featurevec)$ in a Hilbert space $\hilbertspace$,
		$\kernelmap{\featurevec}{\featurevec'} =
		\innerprodgeneric{\featuretrafo(\featurevec)}{\featuretrafo(\featurevec')}{\hilbertspace}$
		(Bishop, 2006, Eq.~(6.1)), and $\hilbertspace$ is also called
		the feature space of the kernel. For the polynomial
		kernel of degree two on $\reals^{2}$, this space is explicit,
		\begin{equation}
			\label{equ_featurespace_poly_dict}
			\kernelmap{\featurevec}{\featurevec'}
			= \big(1 + \featurevec^{\top} \featurevec'\big)^{2}
			= \featuretrafo(\featurevec)^{\top} \featuretrafo(\featurevec')
			\text{,}
		\end{equation}
		with the feature transformation $\featuretrafo(\featurevec) =
		\big(1, \sqrt{2} \feature_{1}, \sqrt{2} \feature_{2},
		\feature_{1}^{2}, \sqrt{2} \feature_{1} \feature_{2},
		\feature_{2}^{2}\big)^{\top} \in \reals^{6}$, so a linear model
		on the transformed feature vectors is a quadratic
		hypothesis on the original feature space
		(Shalev-Shwartz and Ben-David, 2014, Example~16.1). The $366 \times 366$
		matrix of the polynomial kernel values
		\eqref{equ_featurespace_poly_dict} of the days at Krems has
		rank $6$, the dimension of $\reals^{6}$. The feature
		space of the Gaussian kernel $\exp\big(-\normgeneric{\featurevec
		- \featurevec'}{2}^{2} / (2 \sigma^{2})\big)$ has infinite
		dimension (Shalev-Shwartz and Ben-David, 2014, Example~16.2): for $\sigma = 1$
		degree, the matrix of its values on the $366$ days has
		rank $366$, so no feature space of smaller dimension
		produces these values. A kernel method never forms the
		transformed feature vectors; it uses the feature space
		$\hilbertspace$ only through kernel values, which is what
		makes a space of infinite dimension usable
		(Bishop, 2006, Sect.~6.2; Shalev-Shwartz and Ben-David, 2014, Sect.~16.2).
		Fig.~\ref{fig_featurespace_dict} draws three further shapes of a
		feature space: the real line, a bounded convex subset of the
		plane, and the nodes of an undirected graph. The second is the
		feature space of a sensor with a bounded range, and in the third the
		distance between two feature vectors is the length of the
		shortest path between their nodes.
		\begin{figure}[H]
			\centering
			\begin{tikzpicture}[scale=0.6]
			% --------- 1D Line Feature Space (left) ---------
			\begin{scope}[xshift=0cm]
  				% Axis
 	 			\draw[->] (-0.5, 0) -- (3.5, 0) node[right] {$x_1$};
  				% Points
  				\foreach \x/\lbl in {0.5/$\featurevec^{(1)}$, 1.5/$\featurevec^{(2)}$, 2.8/$\featurevec^{(3)}$}
				\filldraw[black] (\x,0) circle (2pt) node[above] {\lbl};
  				% Label
  				\node at (1.5, -2.8)  {$\featurespace^{(1)}$};
				\node at (1.5, -3.8) {(a)};
			\end{scope}
			% --------- 2-D Bounded (Disk) Feature Space (middle) ---------
			\begin{scope}[xshift=8cm]
  				% Circle boundary
  				\draw[thick] (0,0) circle (1.8);
  				\fill[gray!5] (0,0) circle (1.8);
  				% Points inside circle
  				\filldraw[black] (0.8, 0.9) circle (2pt) node[anchor=south west] {$\featurevec^{(1)}$};
  				\filldraw[black] (-1.2, 0.5) circle (2pt) node[anchor=south east] {$\featurevec^{(2)}$};
  				\filldraw[black] (0.3, -1.4) circle (2pt) node[anchor=north west] {$\featurevec^{(3)}$};
  				% Label
  				\node at (0.5, -2.8) {$\featurespace^{(2)}$};
				\node at (0.5, -3.8) {(b)};
			\end{scope}
			% --------- Graph-Based Feature Space (right) ---------
			\begin{scope}[xshift=14cm, yshift=0.3cm]
  				% Nodes
 	 			\filldraw[black] (0,0) circle (2pt) node[anchor=north east] {$\featurevec^{(1)}$};
 	 			\filldraw[black] (2,1.2) circle (2pt) node[anchor=south west] {$\featurevec^{(2)}$};
  				\filldraw[black] (1,2.5) circle (2pt) node[anchor=south east] {$\featurevec^{(3)}$};
  				\filldraw[black] (3,2.5) circle (2pt) node[anchor=south west] {$\featurevec^{(4)}$};
  				% Edges
  				\draw[-] (0,0) -- (2,1.2);
  				\draw[-] (2,1.2) -- (1,2.5);
  				\draw[-] (1,2.5) -- (3,2.5);
  				% Label
  				\node at (1.5, -3.1) {$\featurespace^{(3)}$};
				\node at (1.5, -4.1) {(c)};
			\end{scope}
			\end{tikzpicture}
		\caption{Three feature spaces. (a) The real line $\featurespace^{(1)}
			= \reals$. (b) A bounded convex set $\featurespace^{(2)}
			\subseteq \reals^{2}$. (c) A finite feature space
			$\featurespace^{(3)}$ whose elements are the nodes of an
			undirected graph \label{fig_featurespace_dict}}
		\end{figure}

\subsection{Cross References}
feature vector, feature, feature transformation, data point, label space, Euclidean space, Euclidean distance, metric space, Hilbert space, inner product, $k$-NN, linear model, hypothesis space, model pruning, feature learning, feature standardization, kernel, kernel method, kernel ridge regression, RKHS, graph

\subsection{References}
\begin{enumerate}
  \item Axler (2024). Linear Algebra Done Right. 4th ed., Springer, Cham, Switzerland.
  \item Bishop (2006). Pattern Recognition and Machine Learning. Springer Science+Business Media, New York, NY, USA.
  \item Cover and Hart (1967). Nearest neighbor pattern classification. IEEE Transactions on Information Theory, 13(1), pp.~21--27.
  \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 Schölkopf and Smola (2002). Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. 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 Vishwanathan et al. (2010). Graph Kernels. Journal of Machine Learning Research, 11, pp.~1201--1242.
  \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}
