Discriminant analysis encompasses methods that can be used for both classification and dimensionality reduction. Linear discriminant analysis (LDA) is particularly popular because it is both a classifier and a dimensionality reduction technique. Quadratic discriminant analysis (QDA) is a variant of LDA that allows for non-linear separation of data. Finally, regularized discriminant analysis (RDA) is a compromise between LDA and QDA.
This post focuses mostly on LDA and explores its use as a classification and visualization technique, both in theory and in practice. Since QDA and RDA are related techniques, I shortly describe their main properties and how they can be used in R.
Linear discriminant analysis
LDA is a classification and dimensionality reduction techniques, which can be interpreted from two perspectives. The first is interpretation is probabilistic and the second, more procedure interpretation, is due to Fisher. The first interpretation is useful for understanding the assumptions of LDA. The second interpretation allows for a better understanding on how LDA performs dimensionality reduction.
The probabilistic interpretation
Each class \(k \in \{1, \ldots, K\}\) is assigned a prior \(\hat{\pi}_k\) such that that \(\sum_{i=1}^k \hat{\pi}_k = 1\). According to Bayes’ rule, the posterior probability is
\[\rm{Pr}(G = k |X = x) = \frac{f_k(x) \pi_k}{\sum_{l=1}^K f_l(x) \pi_l} \]
where \(f_k(x)\) is the density of \(X\) conditioned on \(k\). The maximum-a-posteriori (MAP) estimator simplifies to
\[G(x) = \arg \max_k \rm{Pr}(G = k | X = x) = \arg \max_k f_k(x) \pi_k \]
because the denominator is identical for all classes.
LDA assumes that the density is Gaussian:
\[f_k(x) = {|2 \pi \Sigma_k|}^{-1/2} \exp\left(-\frac{1}{2}(x - \mu_k)^T\Sigma_k^{-1}(x - \mu_k)\right)\]
where \(\Sigma_k\) is the covariance matrix for the samples from class \(k\) and \(|.|\) is the determinant. LDA assumes that all classes have the same covariance matrix, i.e. \(\Sigma_k = \Sigma\,, \forall k\).
Plugging \(f_k\) into the classification function, we arrive at the classification function:
\[G(x) = \arg \max_k \delta_k(x)\]
where
\[\delta_k(x) = x^T \Sigma^{-1} \mu_k -\frac{1}{2} \mu_k^T \Sigma^{-1} \mu_k + \log \pi_k \]
is the discriminant function for class \(k\). So, now that we have a classifier, how we can compute it?
To find the covariance matrix, we simply compute
\[\hat{\Sigma} = \sum_{k=1}^K \frac{1}{N - K} \sum_{g_i = k} (x_i - \hat{\mu}_k) (x_i - \hat{\mu}_k)^T\,.\]
Note that the deviation from the means is divided by \(N-K\), the degrees of freedom, to obtain an unbiased estimator.
The means of the classes, which are also called centroids, are defined by
\[\hat{\mu}_k = \frac{1}{N_k} \sum_{g_i = k} x_i\,.\]
The priors \(\pi_k\) are set to the prevalence ratio of the class-specific observations:
\[\hat{\pi}_k = \frac{N_k}{N}\,.\]
With this, we have defined all parameters required for the classifier.
The dimensionality reduction procedure of LDA involves the within-class variance, \(W = \hat{\Sigma}\), and the between-class variance, \(B\). The between-class variance indicates the deviation of centroids from the overall mean, \(\hat{\mu} = \sum_{k=1}^K \hat{\pi}_k \hat{\mu}_k\), and is defined as:
\[B = \sum_{k=1}^K \hat{\pi}_k(\hat{\mu}_k - \hat{\mu}) (\hat{\mu}_k - \hat{\mu})^T\,.\]
Finding a sequence of optimal substeps involves three steps:
Compute the \(K \times p\) matrix \(M\) containing the centroids, \(\mu_k\), and determine the common covariance matrix \(W\).
Compute \(M^{\ast} = MW^{-\frac{1}{2}}\) using the eigen-decomposition of W.
Compute \(B^{\ast}\) (the between-class covariance) and its eigen-decomposition \(B^{\ast} = V^{\ast} D_B {V^{\ast}}^T\). The columns \(v^{\ast}_l\) of \(V^{\ast}\) define the coordinates of the reduced subspace.
The \(l\)-th discriminant variable (one of the \(K-1\) new dimensions) is determined by \(Z_l = v_l^T X\) with \(v_l = W^{-\frac{1}{2}} v^{\ast}_l\).
The interpretation of Fisher
Fisher’s LDA optimization criterion states that the centroids of the groups should be spread out as far as possible. This amounts to finding a linear combination \(Z = a^T X\) such that \(a^T\) maximizes the between-class variance relative to the within-class variance.
As before, the within-class variance is \(W\) is the pooled covariance matrix, \(\hat{\Sigma}\), which indicates the deviation of all observations from their class centroids. The between-class variance is defined according to the deviation of the centroids from the overall mean, as defined earlier. For \(Z\), the between class variance is \(a^T B a\) and the within-class variance is \(A^T W a\). Thus, LDA can be optimized through the Rayleigh quotient
\[\max_a \frac{a^T B a}{a^T W a}\,, \]
which defines an optimal mapping of \(X\) to the new space \(Z\). Note that \(Z \in \mathbb{R}^{1 \times p}\), that is, the observations are mapped to a single dimension. To obtain additional dimensions, we need to solve the optimization problem for \(a_1, \ldots, a_{K-1}\) where each successive \(a_k\) is constructed to be orthogonal in \(W\) to the previous discriminant coordinates. This leads to the linear transformation \(G = (Z_1^T, Z_2^T, \ldots, Z_{K-1}^T) \in \mathbb{R}^{p \times q}\) with which we can map from \(p\) to \(q\) dimension via \(X G\). Why do we consider \(K-1\) projections? This is because the affine subspace that is spanned by the \(K\) centroids has a rank of at most \(K-1\).
Using Fisher’s formulation of LDA, classification involves two steps:
Sphere the data using the common covariance matrix \(\hat{\Sigma} = UDU^T\) (eigendecomposition) such that \(X^{\ast} = D^{-\frac{1}{2}} U^T X\). In this way, the covariance of \(X^{\ast}\) becomes the identity matrix. By eliminating the covariance between the variables in this way, it becomes much easier to separate the classes in the transformed space.
Classify observations \(x_i\) to the closest class centroid in the transformed space, taking into account the class priors \(\pi_k\). Here, the intuition is that an observation with equal distance to two centroids would be assigned to the class with the greater prior.
Reduced-rank LDA
LDA performs classification in a reduced subspace. When performing classification, we do not need to use all \(K-1\) dimensions and instead can choose a smaller subspace \(H_l\) with \(l __ K-1\). When \(l __ K-1\) is used, this is called reduced-rank LDA. The motivation for reduced-rank LDA is that classification basd on a reduced number of discriminant variables can improve performance on the test set when the model is overfitted.
Complexity of the LDA model
The number of effective parameters of LDA can be derived in the following way. There are \(K\) means, \(\hat{\mu}_k\) that are estimated. The covariance matrix does not require additional parameters because it is already defined by the centroids. Since we need to estimate \(K\) discriminant functions (to obtain the decision boundaries), this gives rise to \(K\) calculations involving the \(p\) elements. Additionally, we have \(K-1\) free parameters for the \(K\) priors. Thus, the number of effective LDA parameters is \(Kp + (K-1)\).
Summary of LDA
Here, I summarize the two perspectives on LDA and give a summary of the main properties of the model.
Probabilistic view
LDA uses Bayes’ rule to determine the posterior probability that an observation \(x\) belongs to class \(k\). Due to the normal assumption of LDA, the posterior is defined by a multivariate Gaussian whose covariance matrix is assumed to be identical for all classes. New points are classified by computing the discriminant function \(\delta_k\) (the enumerator of the posterior probability) and returning the class \(k\) with maximal \(\delta_k\). The discriminant variables can be obtained through eigen-decompositions of the within-class and between-class variance.
Fisher’s view
According to Fisher, LDA can be understood as a dimensionality reduction technique where each successive transformation is orthogonal and maximizes the between-class variance relative to the within-class variance. This procedure transforms the feature space to an affine space with \(K-1\) dimensions. After sphering the input data, new points can be classified by determining the closest centroid in the affine space under consideration of the class priors.
Properties of LDA
LDA has the following properties:
LDA assumes that the data are Gaussian. More specifically, it assumes that all classes share the same covariance matrix.
LDA finds linear decision boundaries in a \(K-1\) dimensional subspace. As such, it is not suited if there are higher-order interactions between the independent variables.
LDA is well-suited for multi-class problems but should be used with care when the class distribution is imbalanced because the priors are estimated from the observed counts. Thus, observations will rarely be classified to infrequent classes.
Similarly to PCA, LDA can be used as a dimensionality reduction technique. Note that the transformation of LDA is inherently different to PCA because LDA is a supervised method that considers the outcomes.
The phoneme data set
To exemplify linear discriminant analysis, we will use the phoneme speech recognition data set. This data set is useful for showcasing discriminant analysis because it involves five different outcomes.
library(RCurl)
f