Linear and Quadratic Discriminant Analysis

Linear and quadratic discriminant analysis are generative classifiers. They estimate class priors and class-conditional feature distributions, then apply Bayes' rule.

Their decision boundaries emerge from distributional assumptions rather than from a boundary fitted directly. That gives them a different failure profile from logistic regression, which models the conditional class probability directly. What follows is mostly published arithmetic: what the generative assumption buys when it holds, and what it costs when it does not.

The covariance assumption controls flexibility and sample demand.

The third column is not a hand-wave. “Shrinks covariance estimates toward simpler structure” names a specific published estimator with a closed form. Ledoit and Wolf published it in 2004. It “is the asymptotically optimal convex linear combination of the sample covariance matrix with the identity matrix”: distribution-free, and optimal under quadratic loss as p and n go to infinity together. It is needed because for p larger than n the sample covariance matrix is not even invertible.

scikit-learn ships that lemma as one flag. Its 1.9.0 user guide, under “Shrinkage and Covariance Estimator”, says of shrinkage='auto': “This automatically determines the optimal shrinkage parameter in an analytic way following the lemma introduced by Ledoit and Wolf.” The parameter runs from 0, the empirical covariance, to 1, the diagonal matrix of variances. Regularized discriminant analysis is a dial between the two columns to its left, and the position of that dial can be computed rather than guessed.

Means locate class centers. Covariance describes scale, correlation, and orientation around those centers. Every quantity in the chain below is estimated from data, and each one has its own sample cost.

Discriminant analysis can be strong on small structured datasets, but the feature geometry matters.

For multiple classes, LDA finds directions that emphasize separation between class means relative to variation within classes. The number of those directions is capped at classes minus one. scikit-learn documents the limit for its own implementation — “This shows that, implicit in the LDA classifier, there is a dimensionality reduction by linear projection onto a K−1 dimensional space.”

This supervised use differs from PCA, which ignores labels and preserves directions of overall variance rather than class separation. Whether supervision then wins is an empirical question. Face recognition is where it was raced both ways.

The first race went to supervision. A 1997 leave-one-out test on the 160-image, 16-person Yale face database put three methods side by side. Fisherfaces gave error rates of 7.3% on the close crop and 0.6% on the full face, in a 15-dimensional reduced space. Eigenfaces gave 24.4% and 19.4% in 30 dimensions. Correlation gave 23.9% and 20.0% in 160. On the full face that is 0.6% against 19.4%.

Then Martinez and Kak ran the opposite experiment, in 2001: 50 subjects from the AR face database, only two training and five test images per person, repeated over all 21 train/test splits. PCA recognition saturated at 44–75% for f=80. LDA swung from 31% to 68% at f=10, and from 41% to 82% at f=40 — higher at its best, worse at its worst, and far more dependent on which split it happened to get. “Our overall conclusion is that when the training data set is small, PCA can outperform LDA and, also, that PCA is less sensitive to different training data sets,” they wrote in their abstract.

Supervision is the difference. Two images per class is where the difference stops paying.

The model is compact, so assumption checks can be concrete. Step 4 is not a vague instruction. In scikit-learn's LinearDiscriminantAnalysis the shrinkage parameter runs from 0, the empirical covariance, to 1, the diagonal matrix of variances, and shrinkage='auto' places it by the Ledoit–Wolf lemma instead of by taste.

When the Gaussian and covariance assumptions are approximately useful, LDA can estimate an efficient boundary from relatively few parameters. Logistic regression may be the more robust choice when the class-conditional distributions are badly misspecified.

The first half of that has a price tag on it. In 1975 Bradley Efron tabulated the asymptotic relative efficiency of logistic regression against normal discrimination, with equal class priors. Δ is the square root of the Mahalanobis distance. The efficiency runs 1.000 at Δ=0, 1.000 at Δ=0.5, .995 at Δ=1, .968 at Δ=1.5, .899 at Δ=2, .786 at Δ=2.5, .641 at Δ=3, .486 at Δ=3.5 and .343 at Δ=4. Note where the curve falls. It is flat while the classes overlap heavily, and it collapses as they separate — “Just when good discrimination becomes possible, for Δ between 2.5 and 3.5, the ARE of the logistic procedure falls off sharply”. His abstract states the summary: “Typically, logistic regression is shown to be between one half and two thirds as effective as normal discrimination for statistically interesting values of the parameters.”

Sixteen years later Ruiz-Velasco recomputed the same efficiency independently, in Biometrika in 1991, and found that it does not depend on how many variables there are: “The Pitman asymptotic efficiency for hypothesis tests in this context is the same as the asymptotic relative efficiency calculated using mis-classification rates and is independent of the number of explanatory variables and the number of parameters to be tested.”

So the price of dropping the generative assumption is roughly a third to a half of your sample, in exactly the regime where the classes are worth telling apart — provided the assumption is true. The comparison remains empirical: use consistent preprocessing, priors, splits, and decision metrics.

There is a way to keep the generative model and still survive a wide dataset. Shrink the class centres until most of the features drop out. Tibshirani and three colleagues did that in PNAS in 2002, with a method that is “an enhancement of the simple nearest prototype (centroid) classifier”. There is one centroid per class. Each is shrunk toward the overall centroid until most genes contribute nothing. On the small round blue cell tumour data “only 43 genes … are the only ones required for the classification. This approach yields zero test and zero training errors.” On the leukaemia data they passed over the cross-validation minimum, which “leaves about 1,000 genes”. They took instead the point where the error begins to climb: 21 genes, a cross-validation error of 1/38 and a test error of 2/34. Modelling the feature distribution paid here. It paid because the model of it was kept small enough to estimate.