Linear discriminant analysis
Section of Statistical classifiers and discriminant analysis, part of Statistical learning
Linear discriminant analysis
| Type | Section |
| Taught in | Statistical classifiers and discriminant analysis |
| Part | Statistical learning |
| Questions using it | 9 |
LDA supplies the missing class densities by assuming X\mid Y=g\sim\operatorname{N}_p(\boldsymbol\mu_g,\Sigma), with one covariance shared across classes. This is a distribution conditional on a class label. Different means move the class centres. The common covariance gives them the same shape and orientation. The reward for that restriction is a linear log-odds comparison (Hastie, Tibshirani, and Friedman, 2009).
The labels are known, so the training sample splits into classes and each piece can be estimated on its own. The priors are the training proportions above, unless the design fixed the class sizes or a better external estimate exists. The mean of each class is the ordinary sample mean of its own observations. The common covariance centres every observation by its own class mean, pools the cross-products, and divides by n-G. That divisor is the unbiased one: one degree of freedom is spent on each of the G estimated means,
\widehat\Sigma =\frac{1}{n-G}\sum_{g=1}^{G}\sum_{i:y_i=g} (\mathbf{x}_i-\widehat{\boldsymbol\mu}_g)(\mathbf{x}_i-\widehat{\boldsymbol\mu}_g)^\top.
The discriminant boundary
Main article: LDA decision boundary
Assume equal costs, so the plug-in rule ties two classes where their weighted densities are equal. That tie is the decision boundary. Substitute the two normal densities, cancel every factor that does not depend on the class, take logarithms, and expand the quadratic forms. The shared inverse covariance is the assumption that makes the terms in \mathbf{x}^\top\widehat\Sigma^{-1}\mathbf{x} cancel.
The boundary between classes j and l is \widehat\pi_j\widehat f_j(\mathbf{x})=\widehat\pi_l\widehat f_l(\mathbf{x}), that is
\frac{\widehat\pi_j}{(2\pi)^{p/2}\,|\widehat\Sigma|^{1/2}} \exp\Bigl(-\tfrac12(\mathbf{x}-\widehat{\boldsymbol\mu}_j)^\top\widehat\Sigma^{-1}(\mathbf{x}-\widehat{\boldsymbol\mu}_j)\Bigr) = \frac{\widehat\pi_l}{(2\pi)^{p/2}\,|\widehat\Sigma|^{1/2}} \exp\Bigl(-\tfrac12(\mathbf{x}-\widehat{\boldsymbol\mu}_l)^\top\widehat\Sigma^{-1}(\mathbf{x}-\widehat{\boldsymbol\mu}_l)\Bigr).
The factor (2\pi)^{p/2}\,|\widehat\Sigma|^{1/2} is the same on both sides because the covariance was forced to be common, so it cancels. The logarithms turn the remaining ratio into a difference of quadratic forms. Write q_g=(\mathbf{x}-\widehat{\boldsymbol\mu}_g)^\top\widehat\Sigma^{-1}(\mathbf{x}-\widehat{\boldsymbol\mu}_g). Then
\log\frac{\widehat\pi_j}{\widehat\pi_l} =\frac12\bigl(q_j-q_l\bigr),
and the plug-in log posterior odds are \log(\widehat\pi_j\widehat f_j/\widehat\pi_l\widehat f_l)=\log(\widehat\pi_j/\widehat\pi_l)-\tfrac12(q_j-q_l). Expand each quadratic form. Symmetry of \widehat\Sigma^{-1} gives \mathbf{a}^\top\widehat\Sigma^{-1}\mathbf{b}=\mathbf{b}^\top\widehat\Sigma^{-1}\mathbf{a}, so
q_j-q_l =-2\mathbf{x}^\top\widehat\Sigma^{-1}\widehat{\boldsymbol\mu}_j +\widehat{\boldsymbol\mu}_j^\top\widehat\Sigma^{-1}\widehat{\boldsymbol\mu}_j +2\mathbf{x}^\top\widehat\Sigma^{-1}\widehat{\boldsymbol\mu}_l -\widehat{\boldsymbol\mu}_l^\top\widehat\Sigma^{-1}\widehat{\boldsymbol\mu}_l.
The two copies of \mathbf{x}^\top\widehat\Sigma^{-1}\mathbf{x} cancel. Therefore
\log\frac{\widehat\pi_j\widehat f_j(\mathbf{x})}{\widehat\pi_l\widehat f_l(\mathbf{x})} =\mathbf{x}^\top\widehat\Sigma^{-1}(\widehat{\boldsymbol\mu}_j-\widehat{\boldsymbol\mu}_l) +\log\frac{\widehat\pi_j}{\widehat\pi_l} +\frac12\bigl( \widehat{\boldsymbol\mu}_l^\top\widehat\Sigma^{-1}\widehat{\boldsymbol\mu}_l -\widehat{\boldsymbol\mu}_j^\top\widehat\Sigma^{-1}\widehat{\boldsymbol\mu}_j \bigr).
Had the two classes used different covariances, the quadratic terms would have carried different matrices and would have survived. That is the calculation in the next section. Define
\begin{align*} \boldsymbol\beta &=\widehat\Sigma^{-1}(\widehat{\boldsymbol\mu}_j-\widehat{\boldsymbol\mu}_l),\\ \alpha &=\log\frac{\widehat\pi_j}{\widehat\pi_l} +\frac12(\widehat{\boldsymbol\mu}_l+\widehat{\boldsymbol\mu}_j)^\top \widehat\Sigma^{-1}(\widehat{\boldsymbol\mu}_l-\widehat{\boldsymbol\mu}_j). \end{align*}
The identity (\mathbf{a}+\mathbf{b})^\top M(\mathbf{a}-\mathbf{b})=\mathbf{a}^\top M\mathbf{a}-\mathbf{b}^\top M\mathbf{b}, for symmetric M, rewrites the difference of quadratic mean terms as the second summand in \alpha. The log posterior odds are exactly \alpha+\mathbf{x}^\top\boldsymbol\beta, so the boundary is the hyperplane
\alpha+\mathbf{x}^\top\boldsymbol\beta=0.
Predicting the class with the larger weighted density is the sign rule
\eta(\mathbf{x})= \begin{cases} j, & \alpha+\mathbf{x}^\top\boldsymbol\beta\ge 0,\\ l, & \alpha+\mathbf{x}^\top\boldsymbol\beta<0. \end{cases}
What the cancellation establishes is the shape of the boundary. Under the shared-covariance assumption the log posterior odds are linear in \mathbf{x}, so the comparison of two classes is a single number, the projection \alpha+\mathbf{x}^\top\boldsymbol\beta, and the boundary in that one-dimensional projection is a point. With more than two classes there is one such score for each pair, and the predicted class is the one that wins the comparisons it enters. The regions of the partition are bounded by pieces of these hyperplanes, so the boundary is piecewise linear.
Two equivalent forms are useful. First, define the linear discriminant score
\delta_g(\mathbf{x}) =\mathbf{x}^\top\widehat\Sigma^{-1}\widehat{\boldsymbol\mu}_g -\tfrac12\widehat{\boldsymbol\mu}_g^\top\widehat\Sigma^{-1}\widehat{\boldsymbol\mu}_g +\log\widehat\pi_g.
The rule is \arg\max_g\delta_g(\mathbf{x}), which avoids writing every pair when G>2. The difference \delta_j-\delta_l equals \alpha+\mathbf{x}^\top\boldsymbol\beta. Second, with equal priors the rule assigns \mathbf{x} to the class whose mean is nearest in squared Mahalanobis distance (\mathbf{x}-\widehat{\boldsymbol\mu}_g)^\top\widehat\Sigma^{-1}(\mathbf{x}-\widehat{\boldsymbol\mu}_g). Unequal priors shift each boundary parallel to itself through the term \log(\widehat\pi_j/\widehat\pi_l) in \alpha.
Example 1 (A two-class LDA by hand) Question. Class 1 has observations (3,3), (1,1), (3,2), (1,2) and class 2 has (6,5), (4,3), (6,4), (4,4). Find the LDA rule with equal priors and classify the point (5,1.4).
Solution. The class means are \widehat{\boldsymbol\mu}_1=(2,2)^\top and \widehat{\boldsymbol\mu}_2=(5,4)^\top, and \widehat\pi_1=\widehat\pi_2=\tfrac12. The centred observations of class 1 are (1,1), (-1,-1), (1,0), (-1,0), and class 2 has exactly the same deviations. Each outer product contributes
\begin{pmatrix}1\\1\end{pmatrix}\begin{pmatrix}1&1\end{pmatrix} =\begin{pmatrix}1&1\\1&1\end{pmatrix}, \quad \begin{pmatrix}1\\0\end{pmatrix}\begin{pmatrix}1&0\end{pmatrix} =\begin{pmatrix}1&0\\0&0\end{pmatrix},
and the two negative deviations repeat those matrices, so each class has scatter
A_g=\begin{pmatrix}4&2\\2&2\end{pmatrix}.
The pooled covariance uses divisor n-G=8-2=6:
\widehat\Sigma =\frac{1}{6}(A_1+A_2) =\frac{1}{6}\begin{pmatrix}8&4\\4&4\end{pmatrix} =\begin{pmatrix}4/3&2/3\\2/3&2/3\end{pmatrix}.
The determinant is (4/3)(2/3)-(2/3)^2=8/9-4/9=4/9. The inverse is
\widehat\Sigma^{-1} =\frac{9}{4}\begin{pmatrix}2/3&-2/3\\-2/3&4/3\end{pmatrix} =\begin{pmatrix}1.5&-1.5\\-1.5&3\end{pmatrix}.
With j=1 and l=2,
\boldsymbol\beta =\widehat\Sigma^{-1}(\widehat{\boldsymbol\mu}_1-\widehat{\boldsymbol\mu}_2) =\widehat\Sigma^{-1}\begin{pmatrix}-3\\-2\end{pmatrix} =\begin{pmatrix}-1.5\\-1.5\end{pmatrix}.
Equal priors make the log-weight term zero. The second form of the intercept uses \widehat{\boldsymbol\mu}_2+\widehat{\boldsymbol\mu}_1=(7,6)^\top and \widehat{\boldsymbol\mu}_2-\widehat{\boldsymbol\mu}_1=(3,2)^\top:
\widehat\Sigma^{-1}\begin{pmatrix}3\\2\end{pmatrix} =\begin{pmatrix}1.5\\1.5\end{pmatrix}, \qquad \alpha=\frac12\bigl(7\cdot 1.5+6\cdot 1.5\bigr)=\frac12\cdot 19.5=9.75.
The boundary is 9.75-1.5x_1-1.5x_2=0, that is x_1+x_2=6.5, which passes through the midpoint (3.5,3) of the means. The rule predicts class 1 when x_1+x_2\le 6.5. For (5,1.4), the sum is 6.4<6.5, so the point is class 1.
The Euclidean bisector of the means is the set of \mathbf{x} with (\mathbf{x}-\mathbf{m})^\top(\widehat{\boldsymbol\mu}_2-\widehat{\boldsymbol\mu}_1)=0, where \mathbf{m}=(3.5,3)^\top is the midpoint. That is 3(x_1-3.5)+2(x_2-3)=0, or 3x_1+2x_2=16.5. At the query point, 3(5)+2(1.4)=17.8>16.5, which puts the point on the class-2 side of the Euclidean bisector. The squared Mahalanobis distances agree with LDA. For class 1, \mathbf{x}-\widehat{\boldsymbol\mu}_1=(3,-0.6)^\top and
\widehat\Sigma^{-1}\begin{pmatrix}3\\-0.6\end{pmatrix} =\begin{pmatrix}5.4\\-6.3\end{pmatrix}, \qquad 3\cdot 5.4+(-0.6)(-6.3)=16.2+3.78=19.98.
For class 2, \mathbf{x}-\widehat{\boldsymbol\mu}_2=(0,-2.6)^\top and
\widehat\Sigma^{-1}\begin{pmatrix}0\\-2.6\end{pmatrix} =\begin{pmatrix}3.9\\-7.8\end{pmatrix}, \qquad (-2.6)(-7.8)=20.28.
The nearer mean in Mahalanobis distance is \widehat{\boldsymbol\mu}_1. The covariance tilts the boundary: its normal is (1,1) rather than (3,2). The within-class scatter is largest along the leading eigenvector of \widehat\Sigma. The larger eigenvalue is 1+\sqrt{5}/3, and the matching direction satisfies v_1/v_2=(1+\sqrt{5})/2, so the axis is proportional to (1,(\sqrt{5}-1)/2)\approx(1,0.62)^\top. That direction is close to (3,2)^\top, the direction joining the means, so a displacement along the line of the means is less informative than its Euclidean length suggests.
Used in
- Taught in Statistical classifiers and discriminant analysis
- Also used in Logistic regression · Classification trees · Ensembles, random forests, and boosting · Neural units · High-dimensional analysis
- Questions that use it (9) — LDA with unequal priors · A quadratic boundary · Parameter counts · Fisher’s direction · The fitted LDA model · LDA and principal components · A logistic rule in an unfamiliar setting · When ordinary linear discrimination is not defined · Principal components before linear discrimination
- All 8 questions on Statistical classifiers and discriminant analysis
See also
Training data and classifier · Posterior class probability · Zero–one loss and risk · Bayes-optimal rule · Fisher’s direction · Classification problem · Bayes classifier · Error rates and optimal classifiers