Linear Discriminant Analysis

A classifier needs a rule that maps a feature vector $x \in \mathbb{R}^p$ to a class label $k \in \{1, \dots, K\}$. The generative strategy models the class-conditional density $p(x \mid y = k)$ — how features are distributed within each class — together with the class prior $\pi_k = P(y=k)$. Bayes' theorem then gives the posterior:

Classification picks the class maximizing this posterior. This is exactly the strategy of Naive Bayes Classifiers, but Naive Bayes further assumes the features are conditionally independent given the class. LDA instead assumes each class-conditional density is a multivariate Gaussian,

with mean $\mu_k$ and covariance $\Sigma_k$ specific to class $k$, but crucially adds the restriction that all classes share the same covariance matrix, $\Sigma_k = \Sigma$ for every $k$. This shared-covariance assumption is the entire reason the resulting boundary is linear rather than curved — the quadratic terms in $x$ that would otherwise appear cancel between classes. If instead each class is allowed its own covariance $\Sigma_k$, the method is called Quadratic Discriminant Analysis (QDA): it keeps the Gaussian assumption but drops the shared-covariance restriction, producing quadratic (curved, e.g. elliptical or hyperbolic) decision boundaries. LDA and QDA thus form a bias–variance pair: LDA has higher bias (a stricter model) but lower variance (fewer parameters to estimate — one $\Sigma$ instead of $K$ of them), while QDA is more flexible but needs more data to estimate its per-class covariances reliably.

Deriving the linear boundary. Classification compares posteriors across classes; because the denominator of Bayes' rule is common to all classes, it suffices to compare the numerators $\pi_k\, p(x\mid y=k)$, or equivalently their logarithms, the discriminant functions:

Substituting the shared-covariance Gaussian density and dropping terms that do not depend on $k$ (they cancel when comparing classes) gives, after expanding the quadratic form $(x-\mu_k)^\top \Sigma^{-1} (x-\mu_k)$:

The term $-\tfrac{1}{2}x^\top \Sigma^{-1} x$, which is quadratic in $x$, is identical for every class (since $\Sigma$ does not depend on $k$) and was dropped precisely because it cancels in any pairwise comparison. What remains, $\delta_k(x)$, is linear in $x$ — an affine function $w_k^\top x + b_k$ with

The predicted class is $\hat y = \arg\max_k \delta_k(x)$, and the boundary between any two classes $k, l$ — the set where $\delta_k(x) = \delta_l(x)$ — is a hyperplane, since it is defined by a linear equation in $x$.

Estimating parameters from data. Given a training set $\{(x_i, y_i)\}_{i=1}^n$ with $n_k$ examples in class $k$, the maximum-likelihood estimates are:

The covariance estimate pools the (mean-centered) scatter within each class across all classes — a weighted average of the per-class sample covariances — which is why it is called the pooled within-class covariance. Dividing by $n-K$ rather than $n$ makes it an unbiased estimator, mirroring the degrees-of-freedom correction in ordinary sample variance.

Two-class special case. For $K=2$, comparing $\delta_1(x)$ and $\delta_2(x)$ reduces to thresholding a single linear score:

classify as class 1 if this quantity is positive. The vector $\Sigma^{-1}(\mu_1-\mu_2)$ is the Fisher discriminant direction: projecting data onto it maximizes the ratio of between-class separation to within-class spread, which is Fisher's original 1936 formulation of the problem, independent of any Gaussian assumption. ``` ALGORITHM: Fit LDA (K classes, n samples, p features) INPUT: training pairs (x_i, y_i), i = 1..n, y_i in {1,...,K} OUTPUT: priors {pi_k}, means {mu_k}, shared covariance Sigma 1. for k = 1 to K: 2. S_k <- { x_i : y_i = k } 3. n_k <- |S_k| 4. pi_k <- n_k / n 5. mu_k <- (1 / n_k) sum_{x in S_k} x 6. 7. Sigma <- zero matrix (p x p) 8. for k = 1 to K: 9. for each x in S_k: 10. Sigma <- Sigma + (x - mu_k)(x - mu_k)^T 11. Sigma <- Sigma / (n - K) 12. return {pi_k}, {mu_k}, Sigma ALGORITHM: Predict LDA INPUT: new point x, fitted {pi_k}, {mu_k}, Sigma OUTPUT: predicted class label 1. SigmaInv <- Sigma^{-1} // computed once, reused for all queries 2. best_score <- -infinity; best_k <- none 3. for k = 1 to K: 4. w_k <- SigmaInv mu_k 5. b_k <- -0.5 mu_k^T SigmaInv mu_k + log(pi_k) 6. score_k <- w_k^T x + b_k 7. if score_k > best_score: 8. best_score <- score_k; best_k <- k 9. return best_k ``` The fitting step is a single closed-form pass over the data with no iteration, gradient descent, or convergence check required — a sharp contrast to Logistic Regression and the Sigmoid, whose maximum-likelihood parameters require iterative optimization (e.g. Newton's method or gradient ascent) because the logistic log-likelihood has no closed-form maximizer.

Time complexity. Fitting requires one pass over the $n$ training points to accumulate class sums (means) — $O(np)$ — and a second pass to accumulate the pooled scatter matrix, which costs $O(np^2)$ since each point contributes an outer product of size $p \times p$. Inverting the resulting $p \times p$ covariance matrix costs $O(p^3)$ via standard methods (e.g. Cholesky decomposition, which is preferred since $\Sigma$ is symmetric positive semi-definite). Total fitting time is

dominated by the scatter accumulation when $n \gg p$, and by the matrix inversion when $p$ is large relative to $n$. Prediction for a single new point, after the inverse is precomputed once, costs $O(Kp)$ to evaluate the $K$ linear discriminant scores — extremely fast, since it is just $K$ dot products.

Space complexity. Storing the pooled covariance matrix requires $O(p^2)$ space; storing the $K$ mean vectors requires $O(Kp)$. Total space is $O(p^2 + Kp)$, independent of $n$ once fitting is complete — the training data itself need not be retained.

Correctness argument. The core claim is that under the shared-covariance Gaussian model, the Bayes-optimal classifier (the one minimizing expected misclassification rate) is exactly $\arg\max_k \delta_k(x)$ with $\delta_k$ linear. This follows in three steps: 1. Bayes' decision theory guarantees that $\arg\max_k P(y=k\mid x)$ minimizes the 0-1 loss risk, for any correctly specified $p(x\mid y=k)$ and prior $\pi_k$ — a fact independent of the Gaussian assumption. 2. Because the denominator $\sum_j \pi_j p(x\mid y=j)$ is the same for all $k$, maximizing the posterior is equivalent to maximizing the numerator $\pi_k p(x\mid y=k)$, or its log, $\delta_k(x)$. 3. Expanding the Gaussian log-density with a common $\Sigma$ makes the quadratic term $-\tfrac12 x^\top\Sigma^{-1}x$ identical across all $k$, so it can be dropped without changing which $k$ attains the maximum — leaving a strictly linear function of $x$. So given that the shared-covariance Gaussian model is correct, LDA implements the exact Bayes-optimal rule — no approximation is introduced beyond the modeling assumption itself. The maximum-likelihood parameter estimates ($\hat\mu_k$, $\hat\Sigma$, $\hat\pi_k$) are consistent (converge to the true parameters as $n\to\infty$ by the law of large numbers) and, for Gaussian data, are the unique maximizers of the joint likelihood — the sample mean and pooled sample covariance are exactly the MLE solutions obtainable by setting the gradient of the log-likelihood to zero.

Honest tradeoffs. The correctness argument is conditional: if the true class-conditional densities are not Gaussian, or if classes truly have different covariances, LDA's boundary is no longer Bayes-optimal, though it can still perform well as a biased but low-variance approximation — this is precisely why LDA sometimes beats both QDA and logistic regression on small or noisy datasets, trading a correctness guarantee for statistical stability. When the equal-covariance assumption is dropped, QDA removes this bias at the cost of estimating $K$ separate $p\times p$ covariance matrices, an $O(Kp^2)$ parameter cost that can overfit badly when $n$ is small relative to $p$.

Consider a two-class, two-feature problem — say, classifying wine as red (class 1) or white (class 2) from (acidity, sugar), both standardized. Training data (small illustrative sample):

Step 1 — priors and means. $n_1 = n_2 = 3$, $n=6$, so $\hat\pi_1 = \hat\pi_2 = 0.5$.

Step 2 — pooled covariance. Centered class-1 points: $(0,0), (0.5,-0.5), (-0.5,0.5)$; centered class-2 points: $(0,0), (0.5,0.5), (-0.5,-0.5)$. Their outer-product sums each give $\begin{pmatrix}0.5 & -0.5\\-0.5 & 0.5\end{pmatrix}$ and $\begin{pmatrix}0.5 & 0.5\\0.5 & 0.5\end{pmatrix}$ respectively, summing to $\begin{pmatrix}1.0 & 0\\0 & 1.0\end{pmatrix}$. Dividing by $n - K = 6-2=4$:

Step 3 — Fisher direction. $\mu_1 - \mu_2 = (-2.0, 1.5)$, so

Step 4 — discriminant score for a new point. Take a test wine $x = (2.0, 1.0)$.

Compute each piece: $x^\top w = (2.0)(-8.0) + (1.0)(6.0) = -16 + 6 = -10$. Midpoint $\tfrac12(\mu_1+\mu_2) = (2.0, 1.25)$, so $\tfrac12(\mu_1+\mu_2)^\top w = (2.0)(-8.0)+(1.25)(6.0) = -16 + 7.5 = -8.5$. Priors are equal so $\log(\pi_1/\pi_2)=0$. Total:

Since this is negative, $x=(2.0,1.0)$ is classified as class 2 (white) — sensible, since it lies closer to the white cluster $(3.0, 0.5)$ than the red cluster $(1.0, 2.0)$ once the (here, isotropic) covariance is accounted for. Notice the classifier did not need to iterate or search: the entire boundary was determined algebraically from means, prior ratio, and one matrix inverse.

Contrast with logistic regression. Logistic regression would fit the same linear form $w^\top x + b$ by maximizing the conditional log-likelihood via iterative reweighted least squares or gradient ascent, without ever assuming the $x$'s are Gaussian. On this well-separated, roughly Gaussian, equal-spread toy dataset, both methods land on nearly the same boundary — but LDA got there in closed form, using information about the marginal distribution of $x$ that logistic regression ignores entirely.

LDA remains a workhorse baseline wherever data are moderately low-dimensional, classes are roughly Gaussian, and interpretability or speed matters. In computer vision, the classic Fisherfaces method applies LDA (often after a PCA preprocessing step) to face recognition, exploiting the fact that projecting onto the Fisher discriminant direction is far more robust to lighting variation than PCA alone. In bioinformatics, LDA and shrinkage-LDA variants classify tumor subtypes from gene-expression profiles, where sample sizes are small and a closed-form, low-variance estimator is preferable to an iteratively-fit high-variance one. In finance, credit-scoring and bankruptcy-prediction models have historically used LDA for its linear, auditable decision rule — a regulatory advantage over opaque nonlinear classifiers. It is also a standard dimensionality-reduction preprocessing step: unlike PCA, LDA's projection direction is chosen using label information, making it a supervised complement to unsupervised techniques. Modern deep learning systems rarely use LDA directly at scale, but its Gaussian-generative logic reappears in Gaussian mixture models, quadratic discriminant analysis, and as a theoretical benchmark against which discriminative methods like Logistic Regression and the Sigmoid are compared in statistics and machine learning coursework.

Ask the tutor: How does regularized (shrinkage) LDA choose the shrinkage parameter λ in practice, and how does that connect to ridge regression?