Linear Discriminant Analysis

The Bayes rule for classes that are multivariate normal with a shared covariance matrix, and its estimate from data. The rule is proved linear, with posterior probabilities of softmax form and an exact error rate in terms of the Mahalanobis distance between the class means; with unequal covariance matrices the discriminant functions are proved quadratic (QDA), and affine exactly when the matrices agree. Fisher's criterion is proved to give the same direction for two classes and a generalized eigenvector problem for several, and least squares on a class code is proved to give the same direction too. The plug-in estimates are derived as maximum likelihood estimates. Logistic regression is compared conceptually, as a conditional model against a joint one, and in a cross-validated experiment over 30 seeds predicting sex from NHANES body measurements, with learning curves that show where each wins. Worked problems on an exact two-class example against the nearest-centroid rule, least squares on a class code, and a one-dimensional quadratic boundary.

Among the 5,176 adults of the NHANES 2017 to 2018 examination (National Center for Health Statistics, 2020) with a recorded height and weight, men average 173.5 cm and 88.4 kg, and women 159.8 cm and 77.0 kg. The two groups overlap: many women are taller or heavier than many men. Suppose we know only a person's height and weight. What is the best rule for guessing their recorded sex, how often must it be wrong, and how should the rule be estimated from a sample?

Introduction to Supervised Learning proves that the rule with the smallest error probability is the Bayes classifier: predict the class with the largest conditional probability given the inputs. Linear discriminant analysis (LDA) is that rule when each class is multivariate normal and all classes share one covariance matrix, with the unknown parameters replaced by estimates. This article proves that the rule is then linear in the inputs and computes its error rate exactly. For heights and weights the normal theory predicts an error rate of 0.173, and the population rule actually errs in 0.171 of the 5,176 adults.

First we derive the Bayes rule for normal classes and its error rate. Then we drop the shared covariance and obtain quadratic discriminant analysis (QDA). Next we prove that Fisher's criterion, which makes no normal assumption, and least squares on a class code both give the LDA direction. Then we show that the usual estimates are maximum likelihood estimates. Finally we set LDA against logistic regression, which fits the same form of conditional probabilities by a different likelihood, and compare the two on NHANES data. The article assumes The Multivariate Normal Distribution and Covariance Matrices and Quadratic Forms, whose notation it uses: $N_p(\boldsymbol\mu, \Sigma)$ is the $p$-variate normal with mean vector $\boldsymbol\mu$ and covariance matrix $\Sigma$. With $p = 1$ the second argument is the variance, while the site's one-dimensional $N(\mu, \sigma)$ has the standard deviation second.

Normal classes with a shared covariance

Let the class label $Y$ take the values $1, \ldots, K$ with prior probabilities $\pi_k = P(Y = k) > 0$, and let the input $\mathbf{X}$, given $Y = k$, have the density $f_k$. Bayes' theorem gives

$$P(Y = k \mid \mathbf{X} = \mathbf{x}) = \frac{\pi_kf_k(\mathbf{x})}{\sum_{j=1}^K\pi_jf_j(\mathbf{x})},$$

and the Bayes classifier predicts the $k$ with the largest numerator $\pi_kf_k(\mathbf{x})$. The LDA model takes $f_k$ to be the density of $N_p(\boldsymbol\mu_k, \Sigma)$, with class means $\boldsymbol\mu_k$ and one positive definite $\Sigma$ for all classes.

Here is the idea in one sentence. In the logarithm of the normal density the term quadratic in $\mathbf{x}$ is $-\frac12\mathbf{x}^{\mathsf T}\Sigma^{-1}\mathbf{x}$, the same for every class when $\Sigma$ is shared, so it cancels from every comparison and what remains is linear.

Theorem 1 (the Bayes rule is linear). Under the LDA model define the linear discriminant functions

$$\delta_k(\mathbf{x}) = \mathbf{x}^{\mathsf T}\Sigma^{-1}\boldsymbol\mu_k - \tfrac12\boldsymbol\mu_k^{\mathsf T}\Sigma^{-1}\boldsymbol\mu_k + \ln\pi_k.$$

Then

$$P(Y = k \mid \mathbf{X} = \mathbf{x}) = \frac{e^{\delta_k(\mathbf{x})}}{\sum_{j=1}^Ke^{\delta_j(\mathbf{x})}}, \qquad \ln\frac{P(Y = k \mid \mathbf{X} = \mathbf{x})}{P(Y = l \mid \mathbf{X} = \mathbf{x})} = \delta_k(\mathbf{x}) - \delta_l(\mathbf{x}),$$

the log odds between any two classes are affine functions of $\mathbf{x}$, and the Bayes classifier predicts $\arg\max_k\delta_k(\mathbf{x})$. When $\boldsymbol\mu_k \ne \boldsymbol\mu_l$, the boundary between classes $k$ and $l$, where their conditional probabilities are equal, is the hyperplane $\{\mathbf{x} : (\boldsymbol\mu_k - \boldsymbol\mu_l)^{\mathsf T}\Sigma^{-1}\mathbf{x} = \frac12(\boldsymbol\mu_k^{\mathsf T}\Sigma^{-1}\boldsymbol\mu_k - \boldsymbol\mu_l^{\mathsf T}\Sigma^{-1}\boldsymbol\mu_l) - \ln(\pi_k/\pi_l)\}$.

Proof. The normal density is $f_k(\mathbf{x}) = (2\pi)^{-p/2}(\det\Sigma)^{-1/2}\exp\{-\frac12(\mathbf{x} - \boldsymbol\mu_k)^{\mathsf T}\Sigma^{-1}(\mathbf{x} - \boldsymbol\mu_k)\}$. Expanding the quadratic form, using $\mathbf{x}^{\mathsf T}\Sigma^{-1}\boldsymbol\mu_k = \boldsymbol\mu_k^{\mathsf T}\Sigma^{-1}\mathbf{x}$ (a scalar equals its transpose and $\Sigma^{-1}$ is symmetric),

$$\ln(\pi_kf_k(\mathbf{x})) = c(\mathbf{x}) + \delta_k(\mathbf{x}), \qquad c(\mathbf{x}) = -\tfrac p2\ln(2\pi) - \tfrac12\ln\det\Sigma - \tfrac12\mathbf{x}^{\mathsf T}\Sigma^{-1}\mathbf{x},$$

where $c(\mathbf{x})$ does not depend on $k$. So $\pi_kf_k(\mathbf{x}) = e^{c(\mathbf{x})}e^{\delta_k(\mathbf{x})}$, and the factor $e^{c(\mathbf{x})}$ cancels from Bayes' formula, which gives the first display. The log odds follow by dividing two of them. Each $\delta_k$ is an affine function of $\mathbf{x}$, so their differences are. The largest posterior probability belongs to the largest $\delta_k$, because $e^t$ is increasing. Setting $\delta_k(\mathbf{x}) = \delta_l(\mathbf{x})$ and rearranging gives the boundary, a hyperplane because $\Sigma^{-1}(\boldsymbol\mu_k - \boldsymbol\mu_l) \ne \mathbf{0}$ when $\boldsymbol\mu_k \ne \boldsymbol\mu_l$. $\square$

The posterior probabilities have the softmax form of Multinomial and Softmax Regression, with scores $\eta_k = \delta_k(\mathbf{x})$ linear in $\mathbf{x}$; with two classes it is the logistic function of the log odds, as in Logistic Regression. This fact is the hinge of the comparison at the end of the article.

A geometric reading. Write $\Delta_k^2(\mathbf{x}) = (\mathbf{x} - \boldsymbol\mu_k)^{\mathsf T}\Sigma^{-1}(\mathbf{x} - \boldsymbol\mu_k)$ for the squared Mahalanobis distance from $\mathbf{x}$ to the class mean. The expansion in the proof shows $\delta_k(\mathbf{x}) = -\frac12\Delta_k^2(\mathbf{x}) + \ln\pi_k + \frac12\mathbf{x}^{\mathsf T}\Sigma^{-1}\mathbf{x}$, and the last term is common to all classes. So the rule assigns $\mathbf{x}$ to the class mean nearest in Mahalanobis distance, after a correction of $-2\ln\pi_k$ to the squared distance for the class sizes. Equivalently, transform the inputs by $\Sigma^{-1/2}$, which makes the common covariance the identity, and classify to the nearest transformed mean in ordinary distance. With $\Sigma = \sigma^2I$ and equal priors this is the nearest-centroid rule of Vector Space Classification (Rocchio classification), whose boundary is the perpendicular bisector between the centroids. With a general $\Sigma$ the LDA boundary is not perpendicular to the segment between the means: it is tilted by $\Sigma^{-1}$.

The error rate

For two classes the error of the rule can be computed exactly, and it depends on the parameters only through one number.

Theorem 2 (error of the two-class rule). For $K = 2$, let $\Delta^2 = (\boldsymbol\mu_1 - \boldsymbol\mu_2)^{\mathsf T}\Sigma^{-1}(\boldsymbol\mu_1 - \boldsymbol\mu_2)$ be the squared Mahalanobis distance between the class means, $\Delta > 0$, and $c = \ln(\pi_2/\pi_1)$. The Bayes rule assigns class 1 when $L(\mathbf{x}) = \delta_1(\mathbf{x}) - \delta_2(\mathbf{x}) - \ln(\pi_1/\pi_2) > c$, and under the LDA model

$$P(\text{error}) = \pi_1\,\Phi\Big(\frac{c - \Delta^2/2}{\Delta}\Big) + \pi_2\,\Phi\Big(\frac{-c - \Delta^2/2}{\Delta}\Big),$$

which is $\Phi(-\Delta/2)$ when $\pi_1 = \pi_2$. This is the Bayes error rate of the model.

Proof. Here $L(\mathbf{x}) = \mathbf{a}^{\mathsf T}\big(\mathbf{x} - \frac12(\boldsymbol\mu_1 + \boldsymbol\mu_2)\big)$ with $\mathbf{a} = \Sigma^{-1}(\boldsymbol\mu_1 - \boldsymbol\mu_2)$, the log ratio of the two densities. Given class 1, $\mathbf{X} \sim N_p(\boldsymbol\mu_1, \Sigma)$, so $L(\mathbf{X})$ is normal (The Multivariate Normal Distribution, linear combinations) with mean $\mathbf{a}^{\mathsf T}\frac12(\boldsymbol\mu_1 - \boldsymbol\mu_2) = \Delta^2/2$ and variance $\mathbf{a}^{\mathsf T}\Sigma\mathbf{a} = (\boldsymbol\mu_1 - \boldsymbol\mu_2)^{\mathsf T}\Sigma^{-1}\Sigma\Sigma^{-1}(\boldsymbol\mu_1 - \boldsymbol\mu_2) = \Delta^2$. Given class 2 the mean is $-\Delta^2/2$ and the variance again $\Delta^2$. A class-1 input is misclassified when $L \le c$, which has probability $\Phi((c - \Delta^2/2)/\Delta)$; a class-2 input when $L > c$, probability $1 - \Phi((c + \Delta^2/2)/\Delta) = \Phi((-c - \Delta^2/2)/\Delta)$. Weighting by the priors gives the formula, and with $c = 0$ both terms are $\Phi(-\Delta/2)$. The rule is the Bayes classifier by Theorem 1, so its error is the Bayes error rate. $\square$

So under the model, everything about how separable the classes are is contained in $\Delta$. Two equally likely classes whose means differ by 1.88 standard deviations in the best direction have an error rate of $\Phi(-0.94)$, whether that happens in one dimension or in a hundred.

The running example

For the 5,176 adults (2,512 men and 2,664 women), the population moments, with divisor $N$, are:

  • men: mean height 173.5 cm and weight 88.4 kg, standard deviations 7.69 and 22.03, correlation 0.441;
  • women: mean height 159.8 cm and weight 77.0 kg, standard deviations 6.99 and 22.30, correlation 0.324.

Pooling the two covariance matrices, weighted by the class sizes, gives a within-class matrix $\Sigma_W$ and a Mahalanobis distance between the class means of $\Delta = 1.882$. With the population shares as priors, Theorem 2 predicts an error rate of 0.173 for normal classes with this common covariance; $\Phi(-\Delta/2)$ is also 0.173 to three places, since the shares are nearly equal. The rule built from the population parameters actually misclassifies 0.171 of the 5,176 adults: 0.194 of the men and 0.149 of the women. Heights are nearly normal, but weights are skewed to the right, and the two covariance matrices differ, so the agreement is an observation about these data, not a consequence of the theorem. The quadratic rule of the next section, built from the population's two separate covariance matrices, misclassifies a little less, 0.168. Is the shared covariance worth giving up?

Unequal covariances: quadratic discriminant analysis

Drop the assumption of a common covariance and let class $k$ be $N_p(\boldsymbol\mu_k, \Sigma_k)$. The quadratic terms no longer cancel.

Theorem 3 (quadratic discriminant analysis). With class densities $N_p(\boldsymbol\mu_k, \Sigma_k)$, the Bayes classifier predicts $\arg\max_k\delta_k^{Q}(\mathbf{x})$, with

$$\delta_k^Q(\mathbf{x}) = -\tfrac12\ln\det\Sigma_k - \tfrac12(\mathbf{x} - \boldsymbol\mu_k)^{\mathsf T}\Sigma_k^{-1}(\mathbf{x} - \boldsymbol\mu_k) + \ln\pi_k.$$

The boundary between classes $k$ and $l$ is the zero set of $\delta_k^Q - \delta_l^Q$, a polynomial of degree at most 2 in $\mathbf{x}$ whose quadratic part is $\frac12\mathbf{x}^{\mathsf T}(\Sigma_l^{-1} - \Sigma_k^{-1})\mathbf{x}$. That part vanishes for all $\mathbf{x}$ if and only if $\Sigma_k = \Sigma_l$; then $\delta_k^Q - \delta_l^Q$ is affine and, when $\boldsymbol\mu_k \ne \boldsymbol\mu_l$, the boundary is the hyperplane of Theorem 1.

Proof. $\ln(\pi_kf_k(\mathbf{x})) = -\frac p2\ln(2\pi) + \delta_k^Q(\mathbf{x})$, and the constant is common to all classes, so the largest $\pi_kf_k$ belongs to the largest $\delta_k^Q$. Expanding, the terms of $\delta_k^Q - \delta_l^Q$ quadratic in $\mathbf{x}$ are $-\frac12\mathbf{x}^{\mathsf T}\Sigma_k^{-1}\mathbf{x} + \frac12\mathbf{x}^{\mathsf T}\Sigma_l^{-1}\mathbf{x}$. Let $M = \Sigma_l^{-1} - \Sigma_k^{-1}$, a symmetric matrix. If $\mathbf{x}^{\mathsf T}M\mathbf{x} = 0$ for every $\mathbf{x}$, then for all $\mathbf{u}, \mathbf{v}$, $0 = (\mathbf{u} + \mathbf{v})^{\mathsf T}M(\mathbf{u} + \mathbf{v}) - \mathbf{u}^{\mathsf T}M\mathbf{u} - \mathbf{v}^{\mathsf T}M\mathbf{v} = 2\mathbf{u}^{\mathsf T}M\mathbf{v}$, and taking $\mathbf{u}, \mathbf{v}$ to be coordinate vectors shows every entry of $M$ is 0. So the quadratic part vanishes exactly when $\Sigma_k^{-1} = \Sigma_l^{-1}$, that is, $\Sigma_k = \Sigma_l$, and then the remaining terms are those of Theorem 1. $\square$

Example (flat boundaries with unequal covariances). The theorem is about the discriminant functions, not about the shape of the boundary as a set. Unequal covariances can still give flat boundaries. In one dimension the zero set of a quadratic is at most two points, as Problem 3 shows for heights. In $p$ dimensions, if $\Sigma_l^{-1} - \Sigma_k^{-1} = m\,\mathbf{a}\mathbf{a}^{\mathsf T}$ for a vector $\mathbf{a}$ and the linear part of $\delta_k^Q - \delta_l^Q$ is also a multiple of $\mathbf{a}^{\mathsf T}\mathbf{x}$, the boundary is the set where the quadratic $\frac m2(\mathbf{a}^{\mathsf T}\mathbf{x})^2 + \beta\,\mathbf{a}^{\mathsf T}\mathbf{x} + \gamma$ in the single number $\mathbf{a}^{\mathsf T}\mathbf{x}$ vanishes: two parallel hyperplanes, one, or none.

QDA estimates $K$ covariance matrices, $Kp(p+1)/2$ numbers, where LDA estimates one. Hastie, Tibshirani and Friedman (2009, §4.3.1) describe regularized discriminant analysis, which shrinks each $\Sigma_k$ toward the pooled matrix by a tuning constant chosen by validation, between the two extremes.

Gaussian naive Bayes is QDA with diagonal covariances. If each $\Sigma_k$ is diagonal, the inputs are independent within each class and $f_k$ is a product of one-dimensional normal densities. That is the Gaussian naive Bayes model worked by hand in Introduction to Supervised Learning, the continuous counterpart of Naive Bayes Classification for text. When the class variances of each variable differ it is a quadratic classifier; when they are equal across classes it is linear. Its independence assumption ignores the correlation between height and weight within each sex (0.441 and 0.324 here), and the experiments below show what that costs.

Fisher's criterion

Fisher (1936) reached the same direction from a different question, without assuming normality. For four measurements of the flowers of fifty plants each of two iris species, he asked which linear function $X = \lambda_1x_1 + \cdots + \lambda_4x_4$ "will maximize the ratio of the difference between the specific means to the standard deviations within species". In his notation he maximized $D^2/S$, the squared difference of the means of $X$ over its within-species sum of squares, and found coefficients proportional to the solutions of a linear system in the within-species sums of squares and products.

Theorem 4 (Fisher's discriminant). For two samples with means $\bar{\mathbf{x}}_1, \bar{\mathbf{x}}_2$ and pooled covariance matrix $S_p$ (positive definite), the criterion

$$J(\mathbf{a}) = \frac{\big(\mathbf{a}^{\mathsf T}(\bar{\mathbf{x}}_1 - \bar{\mathbf{x}}_2)\big)^2}{\mathbf{a}^{\mathsf T}S_p\mathbf{a}}, \qquad \mathbf{a} \ne \mathbf{0},$$

is largest exactly at the nonzero multiples of $\mathbf{a}^* = S_p^{-1}(\bar{\mathbf{x}}_1 - \bar{\mathbf{x}}_2)$, and its maximum is the squared Mahalanobis distance $D^2 = (\bar{\mathbf{x}}_1 - \bar{\mathbf{x}}_2)^{\mathsf T}S_p^{-1}(\bar{\mathbf{x}}_1 - \bar{\mathbf{x}}_2)$. This is the direction of the plug-in LDA rule.

Proof. With $\mathbf{v} = \bar{\mathbf{x}}_1 - \bar{\mathbf{x}}_2$ and the symmetric square roots of $S_p$, $\mathbf{a}^{\mathsf T}\mathbf{v} = (S_p^{1/2}\mathbf{a})^{\mathsf T}(S_p^{-1/2}\mathbf{v})$, and the Cauchy–Schwarz inequality (Probability Inequalities) gives $(\mathbf{a}^{\mathsf T}\mathbf{v})^2 \le (\mathbf{a}^{\mathsf T}S_p\mathbf{a})(\mathbf{v}^{\mathsf T}S_p^{-1}\mathbf{v})$. So $J(\mathbf{a}) \le D^2$, with equality exactly when $S_p^{1/2}\mathbf{a}$ is a multiple of $S_p^{-1/2}\mathbf{v}$, that is, $\mathbf{a}$ a multiple of $S_p^{-1}\mathbf{v}$. By Theorem 1 with the estimates in place of the parameters, the plug-in rule compares $\mathbf{x}^{\mathsf T}S_p^{-1}(\bar{\mathbf{x}}_1 - \bar{\mathbf{x}}_2)$ with a threshold, the same direction. $\square$

The squared two-sample $t$ statistic of the projected values $\mathbf{a}^{\mathsf T}\mathbf{x}_i$ is $\frac{n_1n_2}{n_1 + n_2}J(\mathbf{a})$, so Fisher's direction is the combination with the largest two-sample $t$. Hotelling's T-Squared Test (Theorem 3 and the two-sample section) proves that this largest squared $t$ is the two-sample $T^2 = \frac{n_1n_2}{n_1 + n_2}D^2$. The two articles meet here: Hotelling's test asks whether the best direction separates the means more than chance would, and LDA uses the same direction to classify.

Two things Fisher's route does not supply are a threshold and a probability. Theorem 4 holds for any data, normal or not; the threshold $\frac12(\bar{\mathbf{x}}_1 + \bar{\mathbf{x}}_2)^{\mathsf T}\mathbf{a}^* + \ln(n_2/n_1)$ and the error rate of Theorem 2 come from the normal model.

The running sample

Draw 20 men and 20 women from the 5,176 adults (seed 1, without replacement). The sample means are 173.98 cm and 92.54 kg for the men, 162.17 cm and 78.11 kg for the women, and the pooled covariance matrix, with divisor $n - K = 38$, is

$$S_p = \begin{pmatrix} 57.49 & 49.07 \\ 49.07 & 441.91\end{pmatrix}.$$

Fisher's direction, $S_p^{-1}(\bar{\mathbf{x}}_{\text{men}} - \bar{\mathbf{x}}_{\text{women}})$, is $(0.1963, 0.0109)$ per cm and per kg. With equal class sizes the prior term is $\ln(20/20) = 0$, and the rule predicts "man" when

$$0.1963\,\text{height} + 0.0109\,\text{weight} > 33.92,$$

the value of the left side at the midpoint (168.08 cm, 85.32 kg) of the two sample means. Along the boundary, 18.09 kg of weight trade for 1 cm of height. Height carries nearly all the information, because weight varies so much within each sex. The sample Mahalanobis distance is $D^2 = 2.477$, or $D = 1.574$, and Hotelling's two-sample statistic is $T^2 = 10D^2 = 24.77$, that is $F = 12.06$ on 2 and 37 degrees of freedom. The two sexes certainly differ in mean height and weight; the question for classification is how much they overlap.

The rule misclassifies 0.225 of its own 40 adults and 0.187 of the other 5,136, against 0.171 for the rule built from the population parameters. QDA fitted to the same 40 adults misclassifies 0.200 of them but 0.217 of the others: with 20 adults per class, its two separate covariance matrices fit the sample's noise. The Euclidean nearest-centroid rule on the raw measurements, which ignores $S_p$, misclassifies 0.325 of the others: it treats a kilogram like a centimeter.

The 20 men (circles) and 20 women (triangles) of the running sample, with the fitted LDA boundary (solid line) and the QDA boundary (dashed curve). Notice that the LDA line is nearly vertical, because height separates the sexes and weight mostly adds noise, and that the QDA curve encloses the women in a bounded region: a short adult who is heavy enough is classified as a man.
The 20 men (circles) and 20 women (triangles) of the running sample, with the fitted LDA boundary (solid line) and the QDA boundary (dashed curve). Notice that the LDA line is nearly vertical, because height separates the sexes and weight mostly adds noise, and that the QDA curve encloses the women in a bounded region: a short adult who is heavy enough is classified as a man.

Several classes

With $K > 2$ classes, Fisher's question becomes: which direction spreads the class means most, relative to the spread within classes? Let $n_k$ be the class sizes, $n = \sum_k n_k$, $\bar{\mathbf{x}}$ the overall mean, and define the between-class and within-class matrices

$$B = \sum_{k=1}^Kn_k(\bar{\mathbf{x}}_k - \bar{\mathbf{x}})(\bar{\mathbf{x}}_k - \bar{\mathbf{x}})^{\mathsf T}, \qquad W = \sum_{k=1}^K\sum_{i \in k}(\mathbf{x}_i - \bar{\mathbf{x}}_k)(\mathbf{x}_i - \bar{\mathbf{x}}_k)^{\mathsf T}.$$

For a direction $\mathbf{a}$, $\mathbf{a}^{\mathsf T}B\mathbf{a}$ and $\mathbf{a}^{\mathsf T}W\mathbf{a}$ are the between-class and within-class sums of squares of the projected values $\mathbf{a}^{\mathsf T}\mathbf{x}_i$, as in One-Way Analysis of Variance, so their ratio is the analysis of variance's $SSB/SSW$ for the projection.

Theorem 5 (discriminant coordinates). Let $W$ be positive definite. The ratio $\mathbf{a}^{\mathsf T}B\mathbf{a}/\mathbf{a}^{\mathsf T}W\mathbf{a}$ is largest at the eigenvectors of $W^{-1}B$ for its largest eigenvalue, and the maximum is that eigenvalue. $W^{-1}B$ has at most $K - 1$ nonzero eigenvalues, all of them positive, and the corresponding eigenvectors can be chosen with $\mathbf{a}_j^{\mathsf T}W\mathbf{a}_l = 0$ for $j \ne l$.

Proof. Put $\mathbf{b} = W^{1/2}\mathbf{a}$, which runs over all nonzero vectors as $\mathbf{a}$ does. The ratio becomes $\mathbf{b}^{\mathsf T}C\mathbf{b}/\mathbf{b}^{\mathsf T}\mathbf{b}$ with $C = W^{-1/2}BW^{-1/2}$, symmetric and positive semidefinite. By the spectral decomposition $C = Q\Lambda Q^{\mathsf T}$ (Covariance Matrices and Quadratic Forms, Theorem 2), with $\mathbf{c} = Q^{\mathsf T}\mathbf{b}$ the ratio is $\sum_j\lambda_jc_j^2/\sum_jc_j^2$, a weighted average of the eigenvalues. It is at most $\lambda_1$, with equality exactly when $\mathbf{c}$ puts all its weight on eigenvalues equal to $\lambda_1$, that is, when $\mathbf{b}$ is an eigenvector of $C$ for $\lambda_1$. Now $C\mathbf{b} = \lambda\mathbf{b}$ is $W^{-1/2}B\mathbf{a} = \lambda W^{1/2}\mathbf{a}$, which on multiplying by $W^{-1/2}$ is $W^{-1}B\mathbf{a} = \lambda\mathbf{a}$; so the maximizers are the eigenvectors of $W^{-1}B$, with the same eigenvalues as $C$. Orthogonal eigenvectors $\mathbf{b}_j$ of $C$ give $\mathbf{a}_j^{\mathsf T}W\mathbf{a}_l = \mathbf{b}_j^{\mathsf T}\mathbf{b}_l = 0$. For the count: $\sum_kn_k(\bar{\mathbf{x}}_k - \bar{\mathbf{x}}) = \mathbf{0}$, so the $K$ vectors $\bar{\mathbf{x}}_k - \bar{\mathbf{x}}$ span a space of dimension at most $K - 1$, and $B$, a sum of outer products of them, has rank at most $K - 1$. Then so has $C$, and its nonzero eigenvalues, at most $K - 1$ of them, are positive because $C$ is positive semidefinite. $\square$

The eigenvectors are the discriminant coordinates (or canonical variates). Hastie, Tibshirani and Friedman (2009, §4.3.3) show that once the inputs are transformed by $W^{-1/2}$, the sphered directions $W^{1/2}\mathbf{a}$ span the subspace through the transformed class means, so that LDA's nearest-mean rule loses nothing by working in those $K - 1$ coordinates. For $K = 2$, $B = \frac{n_1n_2}{n}(\bar{\mathbf{x}}_1 - \bar{\mathbf{x}}_2)(\bar{\mathbf{x}}_1 - \bar{\mathbf{x}}_2)^{\mathsf T}$ (the computation is in Theorem 6's proof), and the single eigenvector is Fisher's direction of Theorem 4.

Least squares on a class code

Fisher (1936, section IV) also noticed an "analogy of partial regression": give every plant a value of a dummy variable $y$ that depends only on its species, regress $y$ on the measurements, and the regression coefficients are proportional to the discriminant coefficients. Hastie, Tibshirani and Friedman (2009, §4.3) state the same for any coding and leave the proof as an exercise. Here it is.

Theorem 6 (regression on a class code). In two classes of sizes $n_1, n_2$, with the within-class matrix $W$ positive definite, code $y_i = t_1$ for class 1 and $t_2$ for class 2, with $t_1 \ne t_2$, and fit $y$ by least squares on an intercept and the inputs. The slope vector is

$$\hat{\boldsymbol\beta} = \frac{c\,(t_2 - t_1)}{1 + c\,\mathbf{d}^{\mathsf T}W^{-1}\mathbf{d}}\,W^{-1}\mathbf{d}, \qquad \mathbf{d} = \bar{\mathbf{x}}_2 - \bar{\mathbf{x}}_1,\ c = \frac{n_1n_2}{n_1 + n_2},$$

a multiple of $S_p^{-1}(\bar{\mathbf{x}}_2 - \bar{\mathbf{x}}_1)$, positive when $t_2 > t_1$. If in addition $n_1 = n_2$ and $t_2 = -t_1 > 0$, the rule "class 2 when the fitted value is positive" is the plug-in LDA rule with equal priors.

Proof. With an intercept, the least-squares slopes solve $T\hat{\boldsymbol\beta} = \mathbf{s}$, where $T = \sum_i(\mathbf{x}_i - \bar{\mathbf{x}})(\mathbf{x}_i - \bar{\mathbf{x}})^{\mathsf T}$ and $\mathbf{s} = \sum_i(\mathbf{x}_i - \bar{\mathbf{x}})(y_i - \bar y)$ (the centered normal equations of The Geometry of Least Squares). Since $\bar{\mathbf{x}} = (n_1\bar{\mathbf{x}}_1 + n_2\bar{\mathbf{x}}_2)/n$, we have $\bar{\mathbf{x}}_1 - \bar{\mathbf{x}} = -\frac{n_2}{n}\mathbf{d}$ and $\bar{\mathbf{x}}_2 - \bar{\mathbf{x}} = \frac{n_1}{n}\mathbf{d}$; likewise $t_1 - \bar y = -\frac{n_2}{n}(t_2 - t_1)$ and $t_2 - \bar y = \frac{n_1}{n}(t_2 - t_1)$. As $y$ is constant within a class,

$$\mathbf{s} = n_1(\bar{\mathbf{x}}_1 - \bar{\mathbf{x}})(t_1 - \bar y) + n_2(\bar{\mathbf{x}}_2 - \bar{\mathbf{x}})(t_2 - \bar y) = \frac{n_1n_2^2 + n_2n_1^2}{n^2}(t_2 - t_1)\mathbf{d} = c\,(t_2 - t_1)\mathbf{d}.$$

Splitting each deviation as $\mathbf{x}_i - \bar{\mathbf{x}} = (\mathbf{x}_i - \bar{\mathbf{x}}_k) + (\bar{\mathbf{x}}_k - \bar{\mathbf{x}})$, the cross terms sum to zero within each class, so $T = W + n_1(\bar{\mathbf{x}}_1 - \bar{\mathbf{x}})(\bar{\mathbf{x}}_1 - \bar{\mathbf{x}})^{\mathsf T} + n_2(\bar{\mathbf{x}}_2 - \bar{\mathbf{x}})(\bar{\mathbf{x}}_2 - \bar{\mathbf{x}})^{\mathsf T} = W + c\,\mathbf{d}\mathbf{d}^{\mathsf T}$. Now check that the stated $\hat{\boldsymbol\beta}$ solves the equations: $(W + c\mathbf{d}\mathbf{d}^{\mathsf T})W^{-1}\mathbf{d} = \mathbf{d}(1 + c\,\mathbf{d}^{\mathsf T}W^{-1}\mathbf{d})$, so $T\hat{\boldsymbol\beta} = c(t_2 - t_1)\mathbf{d} = \mathbf{s}$. $T$ is invertible because $W$ is positive definite and $c\mathbf{d}\mathbf{d}^{\mathsf T}$ is positive semidefinite, so this is the solution. As $W = (n - 2)S_p$, it is a multiple of $S_p^{-1}\mathbf{d}$, and the multiple has the sign of $t_2 - t_1$.

For the rule: with $n_1 = n_2$ and $t_1 = -t_2$, $\bar y = 0$, the fitted intercept is $\bar y - \hat{\boldsymbol\beta}^{\mathsf T}\bar{\mathbf{x}} = -\hat{\boldsymbol\beta}^{\mathsf T}\bar{\mathbf{x}}$, and $\bar{\mathbf{x}} = \frac12(\bar{\mathbf{x}}_1 + \bar{\mathbf{x}}_2)$. The fitted value at $\mathbf{x}$ is $\hat{\boldsymbol\beta}^{\mathsf T}(\mathbf{x} - \frac12(\bar{\mathbf{x}}_1 + \bar{\mathbf{x}}_2))$, a positive multiple (when $t_2 > 0$) of $(\bar{\mathbf{x}}_2 - \bar{\mathbf{x}}_1)^{\mathsf T}S_p^{-1}(\mathbf{x} - \frac12(\bar{\mathbf{x}}_1 + \bar{\mathbf{x}}_2))$, which is the plug-in $\delta_2 - \delta_1$ with equal priors. $\square$

With unequal class sizes the intercepts differ, and so do the two rules, as Hastie, Tibshirani and Friedman (2009, §4.3) note. With more than two classes, regression on indicator columns need not give the LDA rule: Hastie, Tibshirani and Friedman (2009, §4.2, Figure 4.2) show three classes that LDA separates while the regression rule never predicts the middle one, which they call masking.

Estimating the parameters

The rule needs $\pi_k$, $\boldsymbol\mu_k$ and $\Sigma$. The plug-in estimates used above are the class proportions $\hat\pi_k = n_k/n$, the class means $\bar{\mathbf{x}}_k$, and the pooled covariance $S_p = W/(n - K)$ (Hastie, Tibshirani and Friedman, 2009, §4.3). They are, up to the divisor of $S_p$, the maximum likelihood estimates of the LDA model fitted to the pairs $(\mathbf{x}_i, y_i)$.

Theorem 7 (maximum likelihood under the LDA model). For independent pairs $(\mathbf{x}_i, y_i)$ from the LDA model, with every class present and $n - K \ge p$, the maximum likelihood estimates are $\hat\pi_k = n_k/n$, $\hat{\boldsymbol\mu}_k = \bar{\mathbf{x}}_k$ and $\hat\Sigma = W/n$.

Proof. The joint density of a pair is $\pi_{y}f_{y}(\mathbf{x})$, so the log-likelihood splits into two parts with no parameter in common:

$$\ell = \sum_{k=1}^Kn_k\ln\pi_k \;+\; \sum_{i=1}^n\ln f_{y_i}(\mathbf{x}_i).$$

The priors. The first part, divided by $n$, is $\sum_k\hat p_k\ln\pi_k$ with $\hat p_k = n_k/n$. Gibbs' inequality (Cross-Entropy and Kullback–Leibler Divergence) says $\sum_k\hat p_k\ln\pi_k \le \sum_k\hat p_k\ln\hat p_k$ for every probability vector $\boldsymbol\pi$, with equality only at $\boldsymbol\pi = \hat{\mathbf{p}}$.

The means and the covariance. The second part is $-\frac{np}{2}\ln(2\pi) - \frac n2\ln\det\Sigma - \frac12\sum_k\sum_{i \in k}(\mathbf{x}_i - \boldsymbol\mu_k)^{\mathsf T}\Sigma^{-1}(\mathbf{x}_i - \boldsymbol\mu_k)$. Within class $k$, expanding about $\bar{\mathbf{x}}_k$ as in Hotelling's T-Squared Test (proof of Theorem 4), the sum is $\operatorname{tr}(\Sigma^{-1}W_k) + n_k(\bar{\mathbf{x}}_k - \boldsymbol\mu_k)^{\mathsf T}\Sigma^{-1}(\bar{\mathbf{x}}_k - \boldsymbol\mu_k)$, with $W_k$ the class's matrix of sums of squares and products. For any $\Sigma$ this is smallest at $\boldsymbol\mu_k = \bar{\mathbf{x}}_k$. What remains is $-\frac n2\ln\det\Sigma - \frac12\operatorname{tr}(\Sigma^{-1}W)$ plus a constant, with $W = \sum_kW_k$, positive definite with probability 1 under the model (by Lemmas 1 and 2 of Hotelling's T-Squared Test, applied to each class, $W$ is distributed as a sum of $n - K \ge p$ independent outer products of $N_p(\mathbf{0}, \Sigma)$ vectors). By Lemma 4 of that article it is maximized uniquely at $\Sigma = W/n$. $\square$

The divisor matters little in practice but not nothing. Multiplying $\Sigma$ by a constant multiplies the terms of $\delta_k$ that involve $\Sigma^{-1}$ but not $\ln\pi_k$, so with unequal priors the maximum likelihood $W/n$ and the unbiased $W/(n - K)$ give slightly different thresholds. With equal priors they give the same rule.

A second point is easy to miss. These are maximum likelihood estimates of the joint distribution of $(\mathbf{X}, Y)$. The conditional probabilities $P(Y = k \mid \mathbf{x})$ computed from them are functions of those estimates, by Theorem 1, but they are not the estimates that maximize the conditional likelihood of $Y$ given $\mathbf{X}$. That is what logistic regression does.

Logistic regression or LDA?

By Theorem 1, the LDA model implies that the log odds are linear in $\mathbf{x}$, which is exactly the logistic regression model for two classes and the multinomial (softmax) model for $K$ (Multinomial and Softmax Regression). The two methods fit the same family of conditional probabilities, and they differ in which likelihood they maximize:

  • Logistic regression maximizes $\prod_iP(Y = y_i \mid \mathbf{x}_i)$, the conditional likelihood. It says nothing about the distribution of $\mathbf{X}$. Its model is true whenever the log odds are linear: for normal classes with a shared covariance, but also, for instance, for class densities of the form $h(\mathbf{x})\exp\{\boldsymbol\theta_k^{\mathsf T}\mathbf{x} - A(\boldsymbol\theta_k)\}$ that share $h$ and differ only in $\boldsymbol\theta_k$, whose log ratio $(\boldsymbol\theta_k - \boldsymbol\theta_l)^{\mathsf T}\mathbf{x} - A(\boldsymbol\theta_k) + A(\boldsymbol\theta_l)$ is linear in $\mathbf{x}$ (Exponential Families).
  • LDA maximizes $\prod_i\pi_{y_i}f_{y_i}(\mathbf{x}_i)$, the joint likelihood. It uses the distribution of the inputs too, through the normal model, and the model it fits is narrower.

Hastie, Tibshirani and Friedman (2009, §4.4.5) put the trade in these terms. If the classes really are normal with a shared covariance, the joint likelihood carries more information about the coefficients, and ignoring the marginal part loses efficiency. They summarize Efron (1975) as "a loss of efficiency of about 30% asymptotically in the error rate" in the worst case, which they paraphrase as: with 30% more data, the conditional likelihood (logistic regression) does as well. Efron's abstract states that logistic regression is typically "between one half and two thirds as effective as normal discrimination for statistically interesting values of the parameters". We have read only the abstract of Efron's paper, not the computations behind either summary, and do not reconcile the two figures here. The same reliance on the model is LDA's weakness. Observations far from the boundary, which logistic regression nearly ignores, enter LDA's covariance estimate, so LDA is not robust to gross outliers. When the classes can be separated by a hyperplane, the logistic maximum likelihood estimate does not exist (Deviance and Inference for GLMs, Theorem 4), while LDA's estimates remain defined.

Ng and Jordan (2001) compared the same pair of approaches, generative against discriminative, for naive Bayes and logistic regression. Their abstract reports that the discriminative classifier has the lower asymptotic error, while the generative one can approach its own, higher, asymptotic error faster, so that each can win in a different range of sample sizes. The experiments below look for both effects in one population.

Cross-validated error

The script compared four classifiers by ten-fold cross-validation on two datasets: height and weight for the 5,176 adults, and six body measurements (height, weight, waist circumference, arm circumference, upper leg length and arm length) for the 4,919 adults who have all six. Folds were stratified by sex and reshuffled for each of 30 seeds. Logistic regression was fitted without a penalty. Each entry is the median over the seeds of the share of adults misclassified, with the interquartile range in parentheses.

Classifier Height and weight Six measurements
LDA 0.1710 (0.1706 to 0.1713) 0.1626 (0.1622 to 0.1632)
QDA 0.1690 (0.1687 to 0.1692) 0.1557 (0.1553 to 0.1563)
logistic regression 0.1699 (0.1698 to 0.1702) 0.1632 (0.1627 to 0.1634)
Gaussian naive Bayes 0.1842 (0.1839 to 0.1845) 0.1996 (0.1992 to 0.1998)

With thousands of training adults, LDA and logistic regression differed by about a thousandth, and QDA was best on both datasets: the two sexes' covariance matrices differ, and with this much data the extra parameters are well estimated. Gaussian naive Bayes was worst, and worse with six measurements than with two. A likely reason, which the experiment does not isolate, is that the six grow together with body size within each sex, so that treating them as independent counts the same information several times.

Learning curves

The asymptotic comparison says nothing about small samples. For training sets of $n$ adults, half of each sex, drawn without replacement and tested on all the other adults of the dataset, the script averaged the error over 20 training sets for each of 30 seeds. The table gives the median over seeds of these averages, with the interquartile range, and the number of the 600 training sets in which the two classes were completely separable by a hyperplane, so that the logistic estimate did not exist (checked by a linear program for strict separation; quasi-complete separation, which also prevents the estimate, is not counted, so the counts are lower bounds; the fitting routine then stops when its convergence test is met, at a large coefficient vector).

Height and weight:

$n$ LDA logistic separable sets
10 0.214 (0.209 to 0.227) 0.226 (0.222 to 0.241) 283
20 0.191 (0.190 to 0.194) 0.199 (0.195 to 0.201) 83
40 0.181 (0.179 to 0.182) 0.182 (0.180 to 0.184) 5
100 0.173 (0.173 to 0.174) 0.174 (0.173 to 0.174) 0
400 0.171 (0.170 to 0.171) 0.170 (0.170 to 0.171) 0

Six measurements:

$n$ LDA logistic separable sets
10 0.319 (0.305 to 0.334) 0.284 (0.275 to 0.291) 592
20 0.233 (0.228 to 0.240) 0.256 (0.247 to 0.265) 408
40 0.197 (0.193 to 0.201) 0.209 (0.203 to 0.211) 65
100 0.178 (0.175 to 0.178) 0.180 (0.179 to 0.182) 0
400 0.166 (0.165 to 0.166) 0.167 (0.166 to 0.167) 0

Three observations, each about this experiment:

  • From 20 to 100 adults LDA erred less than logistic regression on both datasets, by up to 2.3 percentage points, and the gap closed as $n$ grew. That is the pattern the efficiency argument predicts, here for data that are only roughly normal.
  • With six measurements and 10 adults, LDA was the worse of the two. Its pooled covariance matrix then has $10 - 2 = 8$ degrees of freedom for 21 distinct entries, and its inverse is erratic. Logistic regression, whose training set was separable in at least 592 of the 600 draws, did better with those large-coefficient fits than LDA did with its noisy estimate.
  • At 400 adults the two were within a thousandth of each other, as in the cross-validation.

Example (does LDA need normal data?). It is tempting to conclude that LDA should not be used on skewed measurements such as weight. The direction of Theorem 4 maximizes Fisher's criterion for any data, and Theorem 6 obtains it again from least squares; normality is needed only for the threshold to be optimal and for the error formula of Theorem 2. On these data, with weights skewed to the right, LDA matched logistic regression at large $n$ and beat it at moderate $n$. The lower error of QDA with plentiful data suggests that what costs LDA here is the unequal covariance of the two classes, though a single comparison does not isolate that cause.

What is proved here, what is cited, what the experiments show

Proved here. The LDA Bayes rule, its linearity and its softmax posterior (Theorem 1), the Mahalanobis nearest-mean reading and the nearest-centroid special case; the exact error of the two-class rule (Theorem 2); the quadratic rule and the condition for affine discriminant functions (Theorem 3), with an example of flat boundaries under unequal covariances; Fisher's criterion and its maximizer (Theorem 4) and the discriminant coordinates for $K$ classes (Theorem 5); least squares on a class code (Theorem 6); the maximum likelihood estimates of the LDA model (Theorem 7).

Taken from other articles, where they are proved. The Bayes classifier is optimal (Introduction to Supervised Learning); linear combinations of normal vectors, the normal density (The Multivariate Normal Distribution); spectral decomposition and square roots (Covariance Matrices and Quadratic Forms); Cauchy–Schwarz (Probability Inequalities); Gibbs' inequality (Cross-Entropy and Kullback–Leibler Divergence); the normal estimate of a covariance matrix and the representation of $W$ (Hotelling's T-Squared Test, Lemmas 1, 2 and 4); nonexistence of the logistic estimate under separation (Deviance and Inference for GLMs).

Cited. Fisher's (1936) criterion and his regression analogy, read in the paper; the plug-in estimates, regularized discriminant analysis, the subspace of the discriminant coordinates and masking in indicator regression and the comparison with logistic regression as Hastie, Tibshirani and Friedman (2009, §§4.2, 4.3, 4.4.5) give them; Efron's (1975) efficiency result from his abstract and through Hastie et al.; Ng and Jordan's (2001) finding from their abstract.

The experiments show cross-validated and learning-curve error rates of four classifiers for one prediction problem in one population, over 30 seeds. They agree with the cited asymptotic comparison in direction; they do not test it.

Worked problems

These problems were written for this article, on small exact cases and on the running sample. The script tools/experiments/statistics/linear-discriminant-analysis.py checks every number.

Problem 1 (LDA against the nearest centroid). Two classes are normal with means $\boldsymbol\mu_1 = (0, 0)$ and $\boldsymbol\mu_2 = (2, 0)$ and the common covariance $\Sigma = \begin{pmatrix} 2 & 1 \\ 1 & 2\end{pmatrix}$, with equal priors. Find the LDA rule and its error rate, and the error rate of the Euclidean nearest-centroid rule. Then redo the LDA rule with $\pi_1 = 0.8$.

Solution. LDA errs with probability 0.2071, the nearest centroid with 0.2398; with $\pi_1 = 0.8$ the Bayes error falls to 0.1409.

$\det\Sigma = 3$ and $\Sigma^{-1} = \frac13\begin{pmatrix} 2 & -1 \\ -1 & 2\end{pmatrix}$. With $\mathbf{d} = \boldsymbol\mu_2 - \boldsymbol\mu_1 = (2, 0)$, the direction is $\mathbf{a} = \Sigma^{-1}\mathbf{d} = (4/3, -2/3)$ and $\Delta^2 = \mathbf{d}^{\mathsf T}\Sigma^{-1}\mathbf{d} = 8/3$, so $\Delta = 1.6330$. With equal priors the rule assigns class 2 when $\mathbf{a}^{\mathsf T}(\mathbf{x} - (1, 0)) > 0$, that is, $\frac43(x_1 - 1) - \frac23x_2 > 0$, or $2x_1 - x_2 > 2$. By Theorem 2 its error is $\Phi(-\Delta/2) = \Phi(-0.8165) = 0.2071$.

The nearest-centroid rule assigns class 2 when $x_1 > 1$, the perpendicular bisector. Given class 1, $X_1$ is normal with mean 0 and variance 2; given class 2, mean 2 and variance 2. Each class is misclassified with probability $\Phi(-1/\sqrt2) = \Phi(-0.7071) = 0.2398$. The correlation makes $x_2$ informative although both classes have the same mean of $x_2$. Within a class, a large $x_2$ goes with a large $x_1$, so for a given $x_1$ a large $x_2$ signals that part of $x_1$ is noise, which favors class 1, the class with the smaller mean of $x_1$. The nearest-centroid rule ignores that.

With $\pi_1 = 0.8$, the threshold of Theorem 2 is $c = \ln(\pi_2/\pi_1) = -\ln 4 = -1.3863$, in the notation where $L$ favors class 1. Class 1 is misclassified with probability $\Phi((c - \Delta^2/2)/\Delta) = 0.0479$ and class 2 with $\Phi((-c - \Delta^2/2)/\Delta) = 0.5129$, for a total of $0.8 \times 0.0479 + 0.2 \times 0.5129 = 0.1409$. The equal-prior rule applied with these priors would still err with probability 0.2071 in each class, so knowing the priors lowers the error by moving the boundary toward the rarer class.

Problem 2 (least squares gives the LDA rule). For the 20 men and 20 women of the running sample, code women $+1$ and men $-1$ and fit $y$ by least squares on height and weight with an intercept. Show that the slopes are proportional to the LDA direction and that the two rules classify every adult identically.

Solution. The slopes are $-0.06255$ per cm and $-0.00346$ per kg, which is $0.3186$ times $S_p^{-1}(\bar{\mathbf{x}}_{\text{women}} - \bar{\mathbf{x}}_{\text{men}}) = (-0.1963, -0.0109)$; the script confirms that the two rules agree on all 40 sample adults and all 5,136 others.

By Theorem 6 with $t_2 - t_1 = 2$, $c = 20 \times 20/40 = 10$ and $W = 38\,S_p$, the factor is $\frac{2c}{38(1 + c\,\mathbf{d}^{\mathsf T}W^{-1}\mathbf{d})}$. Here $c\,\mathbf{d}^{\mathsf T}W^{-1}\mathbf{d} = 10 \times 2.477/38$, so the denominator's bracket is 1.6519, and the factor is $20/(38 \times 1.6519) = 0.3186$, positive, as $t_2 > t_1$. The class sizes are equal and the code is symmetric, so by Theorem 6 the sign of the fitted value is the LDA rule with equal priors, which is the rule of the running sample.

Problem 3 (a quadratic boundary in one dimension). Using height alone, with each sex normal with its population mean and standard deviation (men 173.53 cm and 7.687, women 159.82 cm and 6.989) and the population share of women, 0.5147, as the prior, find the QDA rule. Compare it with the LDA rule that pools the two variances.

Solution. QDA classifies an adult as a woman when the height lies between 21.8 cm and 166.95 cm; LDA when it is below 166.91 cm. On the 5,176 adults both rules misclassify 0.1716.

By Theorem 3 with $p = 1$, the adult is classified as a woman when $\delta_w^Q(x) - \delta_m^Q(x) > 0$, a quadratic $a_2x^2 + a_1x + a_0$ with

$$a_2 = -\frac{1}{2\sigma_w^2} + \frac{1}{2\sigma_m^2}, \quad a_1 = \frac{\mu_w}{\sigma_w^2} - \frac{\mu_m}{\sigma_m^2}, \quad a_0 = -\frac{\mu_w^2}{2\sigma_w^2} + \frac{\mu_m^2}{2\sigma_m^2} + \ln\frac{\pi_w}{\pi_m} - \frac12\ln\frac{\sigma_w^2}{\sigma_m^2}.$$

Numerically $a_2 = -0.001773$, $a_1 = 0.33473$ and $a_0 = -6.455$. Since $a_2 < 0$ (women's heights vary less), the quadratic is positive between its two roots, 21.8 and 166.95. The lower root lies far below the shortest adult in the data, 139.0 cm, so in practice the QDA rule is a single cut at 166.95 cm, almost the LDA cut of 166.91. The second boundary point is real, and it says that under the two normal models a sufficiently extreme short height is more probable for the population with the larger variance, the men. A normal model's tails should not be trusted that far out, and nothing in the data lies there.

Summary

Quantity Formula
Discriminant function $\delta_k(\mathbf{x}) = \mathbf{x}^{\mathsf T}\Sigma^{-1}\boldsymbol\mu_k - \frac12\boldsymbol\mu_k^{\mathsf T}\Sigma^{-1}\boldsymbol\mu_k + \ln\pi_k$
Posterior $P(Y = k \mid \mathbf{x}) = e^{\delta_k(\mathbf{x})}/\sum_je^{\delta_j(\mathbf{x})}$
Two-class error, equal priors $\Phi(-\Delta/2)$, $\Delta^2 = (\boldsymbol\mu_1 - \boldsymbol\mu_2)^{\mathsf T}\Sigma^{-1}(\boldsymbol\mu_1 - \boldsymbol\mu_2)$
QDA $\delta_k^Q(\mathbf{x}) = -\frac12\ln\det\Sigma_k - \frac12(\mathbf{x} - \boldsymbol\mu_k)^{\mathsf T}\Sigma_k^{-1}(\mathbf{x} - \boldsymbol\mu_k) + \ln\pi_k$
Fisher's direction $\arg\max J(\mathbf{a}) = S_p^{-1}(\bar{\mathbf{x}}_1 - \bar{\mathbf{x}}_2)$, $\max J = D^2$
Several classes eigenvectors of $W^{-1}B$, at most $K - 1$
Estimates $\hat\pi_k = n_k/n$, $\bar{\mathbf{x}}_k$, $S_p = W/(n - K)$ (maximum likelihood: $W/n$)
Against logistic regression same conditional form; joint against conditional likelihood

What we have learned

When classes are normal with a shared covariance matrix, the Bayes classifier compares linear functions of the inputs, assigns each point to the class mean nearest in Mahalanobis distance after a correction for class sizes, and has an error rate fixed by the Mahalanobis distance between the means: $\Phi(-\Delta/2)$ for equal priors. Unequal covariances give quadratic discriminant functions, which are affine exactly when the covariance matrices agree. Fisher's criterion and least squares on a class code reach the same direction without any normal assumption, and the plug-in estimates are maximum likelihood estimates of the joint model. Logistic regression fits the same form of conditional probabilities through the conditional likelihood alone. On NHANES heights and weights LDA erred less than logistic regression for training sets of 20 to 100 adults, the two agreed with thousands, and QDA, which can use the sexes' different covariances, was best of all when data were plentiful.

LDA describes each class by one normal distribution. When a class is itself a mixture of groups, or when the labels are missing altogether, the same normal components can be fitted without labels. Gaussian Mixture Models does that with the EM algorithm, and shows k-means as a limiting case.

References