Fisher’s linear discriminant analysis
Section of Statistical classifiers and discriminant analysis, part of Statistical learning
Fisher’s linear discriminant analysis
| Type | Section |
| Taught in | Statistical classifiers and discriminant analysis |
| Part | Statistical learning |
| Questions using it | 1 |
LDA obtained a linear boundary by assuming normal classes with a shared covariance. Many labelled samples are not normal, and writing down a density may be more than the problem requires. Fisher asked a different question for two classes (Fisher, 1936). Among all one-dimensional projections, which direction separates the two class means the most, relative to the scatter within the classes? Fisher’s linear discriminant analysis maximises that ratio. A hyperplane perpendicular to the maximising direction is then the boundary. The criterion uses the class means and a pooled covariance. It does not assume normality, and it does not require the population covariances to be equal. The pooled matrix S is still a constraint: the denominator treats the two classes as having a common scatter. That constraint is why the direction will match the vector \boldsymbol\beta of normal LDA, even though the two derivations start from different places.
Let the sample means be \widehat{\boldsymbol\mu}_1 and \widehat{\boldsymbol\mu}_2, and let S be their pooled sample covariance. A projection direction is a vector \mathbf{a}\in\mathbb{R}^p. Its length will not matter, because the ratio below is unchanged if \mathbf{a} is rescaled. In the projected space the class means are the scalars \mathbf{a}^\top\widehat{\boldsymbol\mu}_1 and \mathbf{a}^\top\widehat{\boldsymbol\mu}_2. Each class mean, measured from the midpoint of the two projected means, is
\mathbf{a}^\top\widehat{\boldsymbol\mu}_1-\tfrac12\mathbf{a}^\top(\widehat{\boldsymbol\mu}_1+\widehat{\boldsymbol\mu}_2) =\tfrac12\mathbf{a}^\top(\widehat{\boldsymbol\mu}_1-\widehat{\boldsymbol\mu}_2),
and the other class contributes the negative of the same quantity. The sum of the two squared deviations is the between-class variance
2\Bigl(\tfrac12\mathbf{a}^\top(\widehat{\boldsymbol\mu}_1-\widehat{\boldsymbol\mu}_2)\Bigr)^2 =\tfrac12\bigl(\mathbf{a}^\top\widehat{\boldsymbol\mu}_1-\mathbf{a}^\top\widehat{\boldsymbol\mu}_2\bigr)^2.
The within-class variance in the projected space is \mathbf{a}^\top S\mathbf{a}. Using a pooled S here is a summary of scatter. It adds squared distances from each observation to its own class mean and multiplies by a constant. The ratio to be maximised is
\frac{\bigl(\mathbf{a}^\top\widehat{\boldsymbol\mu}_1-\mathbf{a}^\top\widehat{\boldsymbol\mu}_2\bigr)^2}{2\,\mathbf{a}^\top S\mathbf{a}}.
The ratio depends on the direction of \mathbf{a} and not on its length. One route constrains \mathbf{a}^\top S\mathbf{a}=1 and differentiates (\mathbf{a}^\top\mathbf{d})^2 with a Lagrange multiplier for that constraint, where \mathbf{d}=\widehat{\boldsymbol\mu}_1-\widehat{\boldsymbol\mu}_2. The stationary equation is (\mathbf{a}^\top\mathbf{d})\,\mathbf{d}=\lambda S\mathbf{a}, so \mathbf{a} is proportional to S^{-1}\mathbf{d}. The same direction falls out of Cauchy–Schwarz, and that argument makes the positive-definiteness assumption easy to see.
Theorem 1 (Fisher’s direction) Let \mathbf{d}=\widehat{\boldsymbol\mu}_1-\widehat{\boldsymbol\mu}_2\ne\mathbf{0} and let S be positive definite. Among nonzero directions, the Fisher ratio is maximised by \mathbf{a}\propto S^{-1}\mathbf{d}. If \mathbf{d}=\mathbf{0}, the ratio is zero for every nonzero direction, so it selects no preferred direction.
Positive-definiteness of S supplies the square-root factors. Write \mathbf{a}^\top\mathbf{d}=(S^{1/2}\mathbf{a})^\top(S^{-1/2}\mathbf{d}). Then
(\mathbf{a}^\top\mathbf{d})^2\le(\mathbf{a}^\top S\mathbf{a})\,(\mathbf{d}^\top S^{-1}\mathbf{d}),
so the ratio is at most \mathbf{d}^\top S^{-1}\mathbf{d}/2, with equality if and only if S^{1/2}\mathbf{a} is proportional to S^{-1/2}\mathbf{d}, that is \mathbf{a}\propto S^{-1}\mathbf{d}. Cauchy–Schwarz did the work, and it needed S positive definite so that S^{1/2} exists. The maximal value of the ratio is \mathbf{d}^\top S^{-1}\mathbf{d}/2.
The discriminant function is the projection \mathbf{a}^\top\mathbf{x}=\mathbf{x}^\top S^{-1}(\widehat{\boldsymbol\mu}_1-\widehat{\boldsymbol\mu}_2). The ratio fixes the direction. The threshold is a separate choice. The boundary is a hyperplane \mathbf{a}^\top\mathbf{x}-a_0=0 orthogonal to \mathbf{a}. A common choice is the midpoint of the two projected class means, a_0=\mathbf{a}^\top(\widehat{\boldsymbol\mu}_1+\widehat{\boldsymbol\mu}_2)/2. If a normal model is then placed on each class, the threshold can instead sit where the posterior densities are equal, which returns the LDA intercept.
Fisher’s direction \mathbf{a}\propto S^{-1}(\widehat{\boldsymbol\mu}_1-\widehat{\boldsymbol\mu}_2) is exactly the vector \boldsymbol\beta of normal LDA. Fisher arrived at it without a normality assumption by maximising separation. The normal model supplies the same direction, and the intercept, as a Bayes rule. With equal priors and the midpoint threshold the two rules coincide: the LDA calculation above put the boundary through the midpoint (3.5,3) when the priors were equal.
Used in
- Taught in Statistical classifiers and discriminant analysis
- Questions that use it (1) — Fisher’s direction
- 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