\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{\featuredim}{d}
\newcommand{\featuretrafo}{\phi}
\newcommand{\featurevec}{\vx}
\newcommand{\mB}[0]{{\bf B}}
\newcommand{\mC}[0]{{\bf C}}
\newcommand{\mS}{\mathbf{S}}
\newcommand{\norm}[1]{\Vert  {#1} \Vert}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\samplecovmtxgeneric}{\widehat{\mC}}
\newcommand{\sampleidx}{r}
\newcommand{\samplemeanvec}[1]{\widehat{{\bm \mu}}^{(#1)}}
\newcommand{\samplemeanvecgeneric}{\widehat{\bm \mu}}
\newcommand{\samplesize}{m}
\newcommand{\trainset}{\dataset^{(\rm train)}}
\newcommand{\truelabel}{y}
\newcommand{\vw}[0]{{\bf w}}
\newcommand{\vx}[0]{{\bf x}}
\newcommand{\weights}{\vw}

\begin{document}

\section{linear discriminant analysis (LDA)}

\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}
Linear discriminant analysis (LDA) learns a linear
		feature transformation that replaces the feature vector of
		a data point by one feature, chosen so that the two
		label values of a binary classification problem are told apart as
		well as possible. The criterion is the Fisher criterion, the
		ratio of the between-class to the within-class scatter of the new
		feature. The direction attaining its maximum is
		obtained by solving one linear system, so LDA is a closed form
		rather than an iterative method. The two scatter matrices
		add up to the sample covariance matrix, the matrix whose
		quadratic form principal component analysis (PCA) maximizes, so PCA keeps the
		direction of largest total sample variance while LDA weighs
		the two parts against each other. A direction can carry nearly
		all of the sample variance and nearly none of the
		between-class part. With more than two label values, LDA
		delivers at most one direction fewer than there are values. The
		name also denotes the classifier that reaches the same
		direction from a multivariate normal distribution per label value with one
		shared covariance matrix.

\subsection{Definition}
A weather
		station at Krems an der Donau (Austria) records the morning
		minimum and the maximum daytime temperature of each day, and a
		forecaster wants one number per day that tells the days with
		precipitation from the dry ones. The two temperatures move
		together: a cold day is cold in the morning and in the
		afternoon, a warm day is warm in both. That shared swing is the
		direction along which the days vary most, and it is the
		direction principal component analysis (PCA) keeps. It is also close to useless for the
		question asked, because it says how warm a day was and not
		whether it rained. LDA produces one number per day as well, and
		it chooses the direction from the labels.
\par
		LDA is a feature learning method for binary classification. Consider a
		training set $\trainset = \big\{ (\featurevec^{(1)},
		\truelabel^{(1)}), \ldots, (\featurevec^{(\samplesize)},
		\truelabel^{(\samplesize)}) \big\}$ of sample size
		$\samplesize$, with feature vectors $\featurevec^{(\sampleidx)}
		\in \reals^{\featuredim}$ and labels
		$\truelabel^{(\sampleidx)} \in \{-1,+1\}$. LDA learns a linear
		feature transformation
		$$\featuretrafo^{(\weights)}: \reals^{\featuredim} \rightarrow
		\reals: \featurevec \mapsto \weights^{\top} \featurevec
		\text{,}$$
		which replaces the $\featuredim$ raw features of a
		data point by the single new feature
		$\featuretrafo^{(\weights)}(\featurevec)$. The labels enter
		through two matrices. Let $\samplemeanvec{c}$ be the
		sample mean of the feature vectors carrying the
		label value $c$, and $p_{c}$ the fraction of the
		training set that carries it. The sample mean of all
		feature vectors is then $\samplemeanvecgeneric = \sum_{c \in
		\{-1,+1\}} p_{c} \samplemeanvec{c}$. The two matrices are
		(Hastie et al., 2009, Sect.~4.3.3):
		\begin{equation}
			\label{equ_lda_scatter_dict}
			\mS \defeq \frac{1}{\samplesize} \sum_{c \in \{-1,+1\}}
			\sum_{\sampleidx \, : \, \truelabel^{(\sampleidx)} = c}
			\big( \featurevec^{(\sampleidx)} - \samplemeanvec{c} \big)
			\big( \featurevec^{(\sampleidx)} - \samplemeanvec{c}
			\big)^{\top} \text{,}
		\end{equation}
		\begin{equation}
			\label{equ_lda_between_dict}
			\mB \defeq \sum_{c \in \{-1,+1\}} p_{c}
			\big( \samplemeanvec{c} - \samplemeanvecgeneric \big)
			\big( \samplemeanvec{c} - \samplemeanvecgeneric
			\big)^{\top} \text{.}
		\end{equation}
		The within-class scatter matrix $\mS$ averages the spread
		of the feature vectors around the sample mean of their
		own label value, and the between-class scatter matrix
		$\mB$ measures how far the two sample means lie apart. Along
		a direction $\weights$, the new feature has within-class
		sample variance $\weights^{\top} \mS \weights$ and
		between-class sample variance $\weights^{\top} \mB \weights$.
\par
		The criterion LDA maximizes is the ratio of the two, the Fisher
		criterion (Bishop, 2006, Sect.~4.1.4, Eq.~(4.26);
		Fisher, 1936;
		Hastie et al., 2009, Sect.~4.3.3, Eq.~(4.15)),
		\begin{equation}
			\label{equ_lda_fisher_dict}
			\max_{\weights \in \reals^{\featuredim} \, : \,
			\norm{\weights} = 1} \frac{\weights^{\top} \mB
			\weights}{\weights^{\top} \mS \weights} \text{.}
		\end{equation}
		A direction scores high when the two sample means are far
		apart on it and the days of one label value stay close
		together on it. The ratio of the two sample variances in the
		Fisher criterion \eqref{equ_lda_fisher_dict} does not change when
		$\weights$ is rescaled, so the constraint costs nothing and what
		is learned is a direction. For an invertible $\mS$, the
		maximizing direction is that of
		\begin{equation}
			\label{equ_lda_solution_dict}
			\widehat{\weights} = \mS^{-1} \big( \samplemeanvec{+1} -
			\samplemeanvec{-1} \big)
		\end{equation}
		(Bishop, 2006, Sect.~4.1.4, Eq.~(4.30)). The LDA direction
		\eqref{equ_lda_solution_dict} is computed in closed form, by
		solving one linear system: LDA is not an iterative method, so no
		operator has its output as a fixed point.
\par
		The name also denotes a classifier, not only the
		feature transformation. Modeling each label value by a
		multivariate normal distribution with its own mean and one shared
		covariance matrix, and estimating these model parameters by
		maximum likelihood, gives a linear classifier whose
		decision boundary is a hyperplane with the normal
		vector \eqref{equ_lda_solution_dict}
		(Hastie et al., 2009, Sect.~4.3). The direction is
		the same, and the probabilistic model supplies the threshold that the
		Fisher criterion leaves open.
\par
		The difference from PCA is one matrix. The
		within-class scatter matrix \eqref{equ_lda_scatter_dict}
		and the between-class scatter matrix
		\eqref{equ_lda_between_dict} add up to the
		sample covariance matrix
		(Hastie et al., 2009, Sect.~4.3.3),
		\begin{equation}
			\label{equ_lda_decomp_dict}
			\mS + \mB = \samplecovmtxgeneric \text{.}
		\end{equation}
		The labels have disappeared from the sum
		\eqref{equ_lda_decomp_dict}. PCA maximizes
		$\weights^{\top} \samplecovmtxgeneric \weights$ over the
		directions of unit norm, which is the total
		sample variance of the new feature and says nothing
		about which part of the sum \eqref{equ_lda_decomp_dict} it
		comes from. The Fisher criterion \eqref{equ_lda_fisher_dict}
		weighs the two parts against each other instead. A direction can
		therefore carry nearly all of the total sample variance and
		nearly none of the between-class part, which is what the opening
		example describes.
\par
		That example is measurable. The training set holds the $1461$
		days of $2020$ to $2023$ at Krems, each with the morning minimum
		and the maximum daytime temperature as its two features
		and the label $+1$ when precipitation was recorded. The
		eigenvector of $\samplecovmtxgeneric$ belonging to its
		largest eigenvalue carries $93$ percent of the total
		sample variance and reaches a Fisher
		criterion of $0.00034$, while the LDA direction
		\eqref{equ_lda_solution_dict} reaches $0.103$, larger by a factor
		of $303$. The two directions are $89$ degrees apart, so what the
		labels depend on lies almost exactly along the direction
		PCA ranks last (Fig.~\ref{fig_lda_directions_dict}). The
		LDA direction weighs
		the two features with opposite signs, $(0.817, -0.577)$,
		so its new feature is large on a day whose temperature
		changed little between morning and afternoon, which is what cloud
		cover does.
		\begin{figure}[H]
			\centering
			\begin{tikzpicture}
			\begin{axis}[
				width=0.66\linewidth, axis equal image,
				xlabel={morning minimum temperature in $^{\circ}$C},
				ylabel={maximum daytime temperature in $^{\circ}$C},
				axis lines=left, clip=false,
				enlarge x limits=0.18, enlarge y limits=0.14,
				legend style={draw=none, fill=none, font=\small,
					at={(0.5,-0.3)}, anchor=north},
				legend cell align=left,
				tick label style={font=\small}, label style={font=\small},
				]
				\addplot[only marks, mark=square, mark size=2.0pt, black]
					table[col sep=comma, x=x1, y=x2]{lda_dry_plot.csv};
				\addlegendentry{day without precipitation (open squares)}
				\addplot[only marks, mark=*, mark size=1.8pt, black]
					table[col sep=comma, x=x1, y=x2]{lda_wet_plot.csv};
				\addlegendentry{day with precipitation (filled circles)}
				\addplot[->, very thick, black]
					table[col sep=comma, x=x1, y=x2]{lda_axis_pca.csv};
				\addlegendentry{direction of largest sample variance (solid arrow)}
				\addplot[->, very thick, black, dashed]
					table[col sep=comma, x=x1, y=x2]{lda_axis_lda.csv};
				\addlegendentry{LDA direction (dashed arrow)}
			\end{axis}
			\end{tikzpicture}
		\caption{Twenty of the $366$ days of $2024$ at Krems an der Donau
			(Austria), ten with and ten without recorded precipitation,
			drawn by taking every $14$th of the $144$ wet days and every
			$22$nd of the $222$ dry days. Each day is a data point
			with its morning minimum and its maximum daytime temperature
			as the two features, drawn as a filled circle when
			precipitation was recorded and as an open square otherwise.
			The two arrows start at the
			sample mean of the training set and are drawn equally
			long, since only their directions are learned. The solid
			arrow is the direction of largest sample variance and
			the dashed arrow the direction along which the two kinds of
			day are told apart best. Data generated by
			\texttt{pythondemos/lda.py}
			\label{fig_lda_directions_dict}}
		\end{figure}
		The criterion \eqref{equ_lda_fisher_dict} has one maximum
		over the directions of the plane and one minimum, and
		Fig.~\ref{fig_lda_criterion_dict} shows where the two directions
		sit on it. Thresholding the single LDA feature at the value
		learned on the $1461$ training days classifies $63.7$ percent of
		the $366$ days of $2024$, kept aside as the test set,
		correctly. The single PCA
		feature reaches $60.9$ percent and always predicting the
		majority label value $60.7$ percent. Two temperatures of
		one day say little about rain, and the little they say lies in
		the direction PCA discards.
		\begin{figure}[H]
			\centering
			\begin{tikzpicture}
			\begin{axis}[
				width=0.66\linewidth, height=0.42\linewidth,
				xlabel={angle of the direction $\weights$ in degrees},
				ylabel={Fisher criterion},
				axis lines=left, xtick={0,45,90,135,180},
				ytick={0,0.025,0.05,0.075,0.1},
				scaled y ticks=false,
				y tick label style={/pgf/number format/fixed,
					/pgf/number format/precision=3},
				ymin=-0.01, ymax=0.115,
				legend style={draw=none, fill=none, font=\small,
					at={(0.5,-0.42)}, anchor=north},
				legend cell align=left,
				tick label style={font=\small}, label style={font=\small},
				]
				\addplot[black, very thick]
					table[col sep=comma, x=angle, y=J]{lda_fisher.csv};
				\addlegendentry{Fisher criterion of the direction (solid curve)}
				\addplot[dashed, black] coordinates {(144.79,-0.01) (144.79,0.1031)};
				\addlegendentry{angle of the LDA direction (dashed line)}
				\addplot[dotted, black] coordinates {(53.79,-0.01) (53.79,0.1031)};
				\addlegendentry{angle of the direction of largest sample variance (dotted line)}
			\end{axis}
			\end{tikzpicture}
		\caption{The Fisher criterion \eqref{equ_lda_fisher_dict} of
			every direction of the plane, for the two temperature
			features of the $1461$ days of $2020$ to $2023$ at
			Krems. A direction and its opposite give the same value, so
			the angle runs over half a turn. The dashed line marks the
			angle of the LDA direction, where the solid curve attains its
			maximum, and the dotted line the angle of the direction
			of largest sample variance, which sits near the
			minimum. Data generated by
			\texttt{pythondemos/lda.py}
			\label{fig_lda_criterion_dict}}
		\end{figure}
		Three limits come with the closed form
		\eqref{equ_lda_solution_dict}. It needs an invertible
		$\mS$, which fails when the training set holds fewer
		data points than features. Shrinking $\mS$ towards a
		multiple of the identity matrix, which is
		regularization by a penalty, is the usual repair
		(Hastie et al., 2009, Sect.~4.3.1, Eq.~(4.14)).
		With more than two label values, the between-class scatter
		matrix is built from all the sample means and has
		rank at most one below their number, so LDA delivers at
		most that many directions, however large $\featuredim$ is
		(Hastie et al., 2009, Sect.~4.3.3). And the single
		new feature is only as good as a linear combination can be:
		two labels separated by a curved decision boundary
		overlap on every direction
		(Hastie et al., 2009, Sect.~12.4).
\par
		Where a linear combination is not enough, the answer is to run
		LDA on an enlarged feature vector that also holds the squares
		and the products of the raw features. A hyperplane
		in the feature space of the enlarged feature vector is a
		curved decision boundary in the feature space of the
		raw features
		(Hastie et al., 2009, Sect.~12.5), and a
		kernel method is the general form of the step. What LDA
		buys for the cost of solving one linear system is the factor of
		$303$ in the Fisher criterion \eqref{equ_lda_fisher_dict}. Of the
		two single features at Krems, the one chosen from the
		labels gains $3.0$ percentage points on predicting the
		majority label value and the PCA feature gains
		$0.3$.

\subsection{Cross References}
PCA, feature learning, feature transformation, dimensionality reduction, binary classification, linear classifier, sample covariance matrix, decision boundary, kernel method, logistic regression

\subsection{References}
\begin{enumerate}
  \item Bishop (2006). Pattern Recognition and Machine Learning. Springer Science+Business Media, New York, NY, USA.
  \item Fisher (1936). The Use of Multiple Measurements in Taxonomic Problems. Ann. Eugenics, 7(2), pp.~179--188.
  \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}
