\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{\featuredim}{d}
\newcommand{\featurespace}{\mathcal{X}}
\newcommand{\featuretrafovec}{{\bf \Phi}}
\newcommand{\featurevec}{\vx}
\newcommand{\hypothesis}{h}
\newcommand{\labelspace}{\mathcal{Y}}
\newcommand{\trainset}{\dataset^{(\rm train)}}
\newcommand{\valset}{\dataset^{(\rm val)}}
\newcommand{\vx}[0]{{\bf x}}

\begin{document}

\section{feature transformation}

\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}
feature map, basis expansion

\subsection{Abstract}
A feature transformation is a function that maps the
		feature vector of a data point to a new feature vector,
		so that a machine learning (ML) method runs on the new features in place
		of the raw ones. What is learned is then the composition of the
		transformation with a hypothesis on the new
		feature space, which is why a linear model of the new
		features is not a linear model of the raw ones. Methods
		differ in where the transformation comes from: principal component analysis (PCA) obtains
		it from the raw features alone, linear discriminant analysis (LDA) uses the
		labels as well, a random projection draws it at
		random, and an autoencoder learns it with an artificial neural network (ANN). Each
		hidden layer of a deep net is one more feature
		transformation, and a kernel method fixes one through the
		choice of a kernel without ever evaluating it. The number of
		new features sizes the hypothesis space of the method that
		runs on them, so keeping it small is model pruning, one of
		the three routes that regularization distinguishes. For the
		maximum daytime temperature at Krems an der Donau (Austria), the
		first five powers of the day of the year turn a nearly flat
		hypothesis into a curve that follows the seasons and cut the
		validation error from $88.2$ to $23.6$ squared degrees. The choice
		matters as much as the count: the three odd powers of the day leave
		the validation error above that of the constant hypothesis, which
		is why the transformation is often learned from the dataset
		rather than chosen by hand.

\subsection{Definition}
A weather station at Krems
		an der Donau (Austria) records the maximum daytime temperature of
		every day of $2023$ and $2024$. Each day is a data point, its
		label is that temperature, and its single raw feature
		$\feature$ is the position of the day in the year, rescaled to the
		interval $[-1, 1]$. The $365$ days of $2023$ form the
		training set $\trainset$ and the $366$ days of $2024$ the
		validation set $\valset$. Linear regression on $\feature$ learns a
		nearly flat hypothesis from $\trainset$ by
		least squares: it rises by $6.9$ degrees from the first day
		of the year to the last, against a label range of $38.4$
		degrees. Its training error is $79.4$ squared degrees and its
		validation error $88.2$, above the $84.9$ of the constant
		hypothesis that always predicts the sample mean of the
		labels in $\trainset$. Replacing $\feature$ by the five
		numbers $\feature, \feature^{2}, \ldots, \feature^{5}$ and running
		the same method on them gives a curve that follows the seasons,
		with a validation error of $23.6$.
		Fig.~\ref{fig_featuretransformation_dict}(a) draws the two learned
		hypotheses over the days of $\trainset$.
		\begin{figure}[H]
		\centering
		\begin{tikzpicture}
		\begin{groupplot}[
			group style={group size=2 by 1, horizontal sep=1.6cm},
			width=0.47\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.5,-0.46)}, anchor=north},
			legend cell align=left,
		]
			\nextgroupplot[
				xlabel={day of the year $2023$\\(a) the two learned hypotheses},
				ylabel={maximum temperature in degrees},
				xmin=0, xmax=370, ymin=-4, ymax=42]
			\addplot[only marks, mark=*, mark size=1.5pt, black]
				table[col sep=comma, x=day, y=tmax]{featuretransformation_days_plot.csv};
			\addlegendentry{training day (filled circles)}
			\addplot[thick, black]
				table[col sep=comma, x=day, y=raw]{featuretransformation_curves.csv};
			\addlegendentry{hypothesis, raw feature (solid curve)}
			\addplot[thick, black, dashed]
				table[col sep=comma, x=day, y=poly]{featuretransformation_curves.csv};
			\addlegendentry{hypothesis, new features (dashed curve)}
			\nextgroupplot[
				xlabel={number $\featuredim'$ of new features\\(b) the two errors},
				ylabel={average squared error loss},
				xmin=0, xmax=15, ymin=0, ymax=95]
			\addplot[thick, black, mark=*, mark size=1.5pt]
				table[col sep=comma, x=dprime, y=train]{featuretransformation_errors.csv};
			\addlegendentry{training error (solid curve)}
			\addplot[thick, black, dashed, mark=square, mark size=1.8pt]
				table[col sep=comma, x=dprime, y=val]{featuretransformation_errors.csv};
			\addlegendentry{validation error (dashed curve)}
		\end{groupplot}
		\end{tikzpicture}
		\caption{A feature transformation of the single raw feature
			of a day at Krems, its position in the year. (a) Twenty of the
			$365$ days of $\trainset$, every $19$th one in calendar order
			(filled circles), the hypothesis learned from the raw
			feature alone (solid curve), and the hypothesis
			learned from the $\featuredim' = 5$ new features
			(dashed curve), which is a polynomial of the raw feature. (b) The training error (solid curve,
			filled circles) and the validation error (dashed curve, open
			squares) against the number $\featuredim'$ of new
			features. Data generated by
			\texttt{pythondemos/featuretransformation.py}
			\label{fig_featuretransformation_dict}}
		\end{figure}
		A feature transformation is a function
		\begin{equation}
			\label{equ_feattrafo_def_dict}
			\featuretrafovec: \featurespace \rightarrow \featurespace',
			\qquad \featurevec \mapsto \featuretrafovec(\featurevec)
			\text{,}
		\end{equation}
		which carries the feature vector $\featurevec$ of a
		data point from its feature space $\featurespace$ to a
		new feature vector in a new feature space $\featurespace'$.
		For a single raw feature, the powers of the opening example
		are the transformation
		\begin{equation}
			\label{equ_feattrafo_poly_dict}
			\featuretrafovec(\feature) \defeq \big( \feature,
			\feature^{2}, \ldots, \feature^{\featuredim'} \big)^{\top}
			\text{,}
		\end{equation}
		which delivers $\featuredim'$ new features. A machine learning (ML)
		method then runs on the new features in place of the raw
		ones, and it delivers a hypothesis $\hypothesis'$ on
		$\featurespace'$. What is learned overall is then the
		composition
		\begin{equation}
			\label{equ_feattrafo_comp_dict}
			\hypothesis = \hypothesis' \circ \featuretrafovec:
			\featurespace \rightarrow \labelspace, \qquad \featurevec
			\mapsto \hypothesis' \big( \featuretrafovec(\featurevec)
			\big) \text{.}
		\end{equation}
		The composition \eqref{equ_feattrafo_comp_dict} is why a
		linear model of the new features is not a linear model
		of the raw ones. With the powers \eqref{equ_feattrafo_poly_dict},
		the learned $\hypothesis$ is a polynomial of degree
		$\featuredim'$ in $\feature$, which is polynomial regression
		(Bishop, 2006, Sect.~3.1).
\par
		Methods differ in where $\featuretrafovec$ comes from.
		Principal component analysis (PCA) obtains it from the raw features alone, as the
		linear map of a given rank whose reconstruction error is
		smallest (Hastie et al., 2009, Sect.~14.5.1).
		Linear discriminant analysis (LDA) uses the labels as well, projecting onto the
		subspace spanned by the class centroids
		(Hastie et al., 2009, Sect.~4.3.3). A
		random projection draws $\featuretrafovec$ at random instead
		of learning it (Johnson and Lindenstrauss, 1984), and an
		autoencoder learns a nonlinear $\featuretrafovec$ with an
		artificial neural network (ANN) (Hinton and Salakhutdinov, 2006). Each hidden layer of a
		deep net is one more feature transformation, learned jointly
		with the output layer
		(Mallat, 2016). A kernel method
		fixes $\featuretrafovec$ through the choice of a kernel,
		which returns the inner product of two transformed
		feature vectors (Schölkopf and Smola, 2002, Sect.~1.1). Such a
		method uses the transformed feature vectors only through those
		inner products, so $\featuretrafovec$ is never evaluated
		(Schölkopf and Smola, 2002, Sect.~1.5). A
		transformation that delivers fewer new features than the
		data point has raw ones is dimensionality reduction, and obtaining
		$\featuretrafovec$ from a dataset rather than by hand is the
		subject of feature learning.
\par
		The number $\featuredim'$ of new features in the definition
		\eqref{equ_feattrafo_def_dict} sizes the hypothesis space of the
		method that runs on them. For the powers
		\eqref{equ_feattrafo_poly_dict}, every hypothesis available
		at $\featuredim'$ is available at $\featuredim' + 1$ as well, so
		the training error, the average squared error loss over $\trainset$,
		cannot rise with $\featuredim'$: it falls from $79.4$ to $13.2$
		squared degrees as
		$\featuredim'$ grows from $1$ to $14$. The validation error on
		$\valset$ behaves differently. It is smallest at $\featuredim' =
		5$ with $23.6$ squared degrees and rises again to $27.9$ at
		$\featuredim' = 14$, the overfitting that a large
		hypothesis space brings (Bishop, 2006, Sect.~1.1).
		Fig.~\ref{fig_featuretransformation_dict}(b) draws the two errors.
		Keeping $\featuredim'$ small therefore shrinks the
		hypothesis space, which is model pruning, one of the three
		routes that regularization distinguishes.
\par
		Two other names are in use for the function
		\eqref{equ_feattrafo_def_dict}. The kernel method literature
		calls it a feature map (Schölkopf and Smola, 2002, Sect.~2.1), and
		the statistical learning literature a basis expansion
		(Hastie et al., 2009, Sect.~5.1). The two senses of \emph{feature map} are distinct: a
		feature transformation is the map between feature spaces of
		the definition \eqref{equ_feattrafo_def_dict}, while a
		feature map is the grid of activations delivered by
		one channel of a convolutional layer.
\par
		Since the training error cannot rise with $\featuredim'$, it cannot
		report the cost of a transformation that delivers too many new
		features, so $\featuredim'$ is a hyperparameter and is
		chosen on held-out data points by validation. The count
		is not the whole choice, since a transformation fixed before the
		labels are looked at can discard what the label depends
		on. The three odd powers $\feature, \feature^{3}, \feature^{5}$
		leave the validation error at $86.7$ squared degrees, above the $84.9$
		of the constant hypothesis, while the two even powers
		$\feature^{2}, \feature^{4}$ alone give $22.0$. Every odd power is
		antisymmetric about $\feature = 0$, the middle of the year, and the
		maximum daytime temperature at Krems is nearly symmetric about that
		point. The composition \eqref{equ_feattrafo_comp_dict} also changes
		what a weight means: a weight of a linear model on the
		new features multiplies one of them, at Krems a cube of a
		rescaled calendar position, and not a quantity the station recorded.
\par
		In return, least squares on the new features reaches
		hypotheses that no linear model of the raw feature
		contains, at Krems a curve that follows the seasons where a straight
		line is of no use. Two alternatives avoid the choice of
		$\featuretrafovec$ by hand. One keeps the raw features and
		takes a method whose hypothesis space is not a linear model of
		them, such as a decision tree. The other obtains
		$\featuretrafovec$ from the dataset, which is feature learning,
		with an autoencoder or the hidden layers of a
		deep net.

\subsection{Cross References}
feature learning, feature, feature space, PCA, LDA, random projection, autoencoder, dimensionality reduction, kernel method, feature map, polynomial regression, regularization, hyperparameter, validation, decision tree

\subsection{References}
\begin{enumerate}
  \item Bishop (2006). Pattern Recognition and Machine Learning. Springer Science+Business Media, New York, NY, USA.
  \item Hinton and Salakhutdinov (2006). Reducing the dimensionality of data with neural networks. Science, 313(5786), pp.~504--507.
  \item Schölkopf and Smola (2002). Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. MIT Press, Cambridge, MA, USA.
  \item Mallat (2016). Understanding deep convolutional networks. Philos. Trans. Roy. Soc. A, 374(2065), pp.~Art.\ no.\ 20150203.
  \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.
  \item Johnson and Lindenstrauss (1984). Extensions of Lipschitz mappings into a Hilbert space. Contemporary Math., 26, pp.~189--206.
\end{enumerate}

\end{document}
