Linear Discriminant Analysis (LDA)

Reading Assignments

S. Gong et al., Dynamic Vision: From Images to Face Recognition, Imperial College Press, 2001 (pp. 173-175 and Appendix C: Mathematical Details, hard copy). A. Webb Statistical Pattern Recognition, Arnold, 1999 (pp. 112-116, hard copy). R. Duda et al., Pattern Classication, John Wiley, 2001 (pp. 117-124, hard copy).

Case Studies

D. Swets and J. Weng, "Using Discriminant Eigenfeatuers for Image Retrieval", IEEE Transactions on Pattern Analysis and Machine Intelligenve, vol. 18, no. 8, pp. 831-836, 1996 (on-line). A. Martinez and A. Kak, "PCA versus LDA", IEEE Transactions on Pattern Analy sis and Machine Intelligenve, vol. 23, no. 2, pp. 228-233, 2001, (on-line) P. Belhumeur et al., "Eigenfaces vs Fisherfaces: Recognition Using Class Specic Linear Projection", IEEE Transactions on Pattern Analysis and Machine Intelligenve, vol. 19, no. 7, pp. 711-720, 1997 (on-line)

Multiple classes and PCA

- Suppose there are C classes in the training data. - PCA is based on the sample covariance which characterizes the scatter of the entire data set, irrespective of class-membership. - The projection axes chosen by PCA might not provide good discrimination power.

What is the goal of LDA?

- The objective of LDA is to perform dimensionality reduction while preserving as much of the class discriminatory information as possible. - It seeks to nd directions along which the classes are best separated.

Figures/notesP2.ps

- It does so by taking into consideration the scatter within-classes but also the scatter between-classes. - It is also more capable of distinguishing image variation due to identity from variation due to other sources such as illumination and expression.

Methodology

- Suppose there are C classes - Let i be the mean vector of class i , i = 1, 2,. , C - Let M i be the number of samples within class i , i = 1, 2,. , C , - Let M =
M i be the total number of samples. i=0 (y j i=1 j=1

C C Mi

Within-class scatter matrix:
Between-class scatter matrix:

i )(y j

Sb = = 1/C
(mean of entire data set)
- LDA computes a transformation that maximizes the between-class scatter while minimizing the within-class scatter: maximize

det(S b ) det(S w )

- Such a tranformation should retain class separability while reducing the variation due to sources other than identity (e.g., illumination).
Linear tranformation implied by LDA
- The linear tranformation is given by a matrix U whose columns are the eigenvectors of S 1 S b (called Fisherfaces). w
T b1 u1 b2 uT 2 T = (x ) = U (x ) . . b K uT K
- The eigenvectors are solutions of the generalized eigenvector problem:

S B uk =

k S w uk
- There are at most C 1 non-zero generalized eigenvectors (i.e., K < C )

Does S 1 always exist? w

- If S w is non-singular, we can obtain a conventional eigenvalue problem by writing:

S 1 S B u k = w

- In practice, S w is often singular since the data are image vectors with large dimensionality while the size of the data set is much smaller ( M << N )
-5To alleviate this problem, we can perform two projections: (1) PCA is rst applied to the data set to reduce its dimensionality.
y1 x1 y2 x2 > PCA > . . yK xN
(2) LDA is then applied to further reduce the dimensionality of C 1.