33
$\begingroup$

Assume I have a dataset for a supervised statistical classification task, e.g., via a Bayes' classifier. This dataset consists of 20 features and I want to boil it down to 2 features via dimensionality reduction techniques such as Principal Component Analysis (PCA) and/or Linear Discriminant Analysis (LDA).

Both techniques are projecting the data onto a smaller feature subspace: with PCA, I would find the directions (components) that maximize the variance in the dataset (without considering the class labels), and with LDA I would have the components that maximize the between-class separation.

Now, I am wondering if, how, and why these techniques can be combined and if it makes sense.

For example:

  1. transforming the dataset via PCA and projecting it onto a new 2D subspace
  2. transforming (the already PCA-transformed) dataset via LDA for max. in-class separation

or

  1. skipping the PCA step and using the top 2 components from a LDA.

or any other combination that makes sense.

$\endgroup$
3
  • 2
    $\begingroup$ There can be no universal best practice. PCA and LDA, as dimensionality reduction techniques, are very different. Sometimes people do PCA prior LDA, but it has its risks to throw away (with the discarded PCs) important discriminative dimensions. The question that you ask has actually been asked in some form several times on this site. Please search "PCA LDA", to read what people said to it. $\endgroup$
    – ttnphns
    Commented Jul 8, 2014 at 6:34
  • $\begingroup$ @SebastianRaschka: I am wondering if my answer here was useful, or do you have any further questions about these issues? $\endgroup$
    – amoeba
    Commented Aug 7, 2014 at 9:07
  • $\begingroup$ @amoeba sorry, it didn't see the answer until now -- somehow it must have slipped through the cracks, thank you! $\endgroup$
    – user39663
    Commented Aug 7, 2014 at 17:09

2 Answers 2

51
$\begingroup$

Summary: PCA can be performed before LDA to regularize the problem and avoid over-fitting.

Recall that LDA projections are computed via eigendecomposition of $\boldsymbol \Sigma_W^{-1} \boldsymbol \Sigma_B$, where $\boldsymbol \Sigma_W$ and $\boldsymbol \Sigma_B$ are within- and between-class covariance matrices. If there are less than $N$ data points (where $N$ is the dimensionality of your space, i.e. the number of features/variables), then $\boldsymbol \Sigma_W$ will be singular and therefore cannot be inverted. In this case there is simply no way to perform LDA directly, but if one applies PCA first, it will work. @Aaron made this remark in the comments to his reply, and I agree with that (but disagree with his answer in general, as you will see now).

However, this is only part of the problem. The bigger picture is that LDA very easily tends to overfit the data. Note that within-class covariance matrix gets inverted in the LDA computations; for high-dimensional matrices inversion is a really sensitive operation that can only be reliably done if the estimate of $\boldsymbol \Sigma_W$ is really good. But in high dimensions $N \gg 1$, it is really difficult to obtain a precise estimate of $\boldsymbol \Sigma_W$, and in practice one often has to have a lot more than $N$ data points to start hoping that the estimate is good. Otherwise $\boldsymbol \Sigma_W$ will be almost-singular (i.e. some of the eigenvalues will be very low), and this will cause over-fitting, i.e. near-perfect class separation on the training data with chance performance on the test data.

To tackle this issue, one needs to regularize the problem. One way to do it is to use PCA to reduce dimensionality first. There are other, arguably better ones, e.g. regularized LDA (rLDA) method which simply uses $(1-\lambda)\boldsymbol \Sigma_W + \lambda \boldsymbol I$ with small $\lambda$ instead of $\boldsymbol \Sigma_W$ (this is called shrinkage estimator), but doing PCA first is conceptually the simplest approach and often works just fine.

Illustration

Here is an illustration of the over-fitting problem. I generated 60 samples per class in 3 classes from standard Gaussian distribution (mean zero, unit variance) in 10-, 50-, 100-, and 150-dimensional spaces, and applied LDA to project the data on 2D:

Overfitting in LDA

Note how as the dimensionality grows, classes become better and better separated, whereas in reality there is no difference between the classes.

We can see how PCA helps to prevent the overfitting if we make classes slightly separated. I added 1 to the first coordinate of the first class, 2 to the first coordinate of the second class, and 3 to the first coordinate of the third class. Now they are slightly separated, see top left subplot:

Overfitting in LDA and regularization with PCA

Overfitting (top row) is still obvious. But if I pre-process the data with PCA, always keeping 10 dimensions (bottom row), overfitting disappears while the classes remain near-optimally separated.

PS. To prevent misunderstandings: I am not claiming that PCA+LDA is a good regularization strategy (on the contrary, I would advice to use rLDA), I am simply demonstrating that it is a possible strategy.


Update. Very similar topic has been previously discussed in the following threads with interesting and comprehensive answers provided by @cbeleites:

See also this question with some good answers:

$\endgroup$
4
  • $\begingroup$ That's a great answer, seriously! And while explaining the underlying theory you have a nice practical explanation there too, another great answer for my reference collection. Thanks a lot! $\endgroup$
    – user39663
    Commented Aug 7, 2014 at 17:08
  • $\begingroup$ I don't understand the second plot, it seems to me that the classes are not separated with PCA before LDA (bottom row) $\endgroup$
    – pierolefou
    Commented Mar 31, 2016 at 20:09
  • $\begingroup$ @PierreE, on the second plot the classes are generated such that they are almost not separated. The separation is tiny. In the bottom row you can see this slight separation, but you need to look closely: focus on the blue and red classes and you will see that one is shifted to the left and another to the right. $\endgroup$
    – amoeba
    Commented Mar 31, 2016 at 20:40
  • $\begingroup$ OK I see. I forgot that the separation of classes we see in the top row is actually overfitting. Thanks $\endgroup$
    – pierolefou
    Commented Mar 31, 2016 at 20:52
2
$\begingroup$

If you have a two class problem then LDA will take you down to 1 dimension. There is no reason to do PCA first.

$\endgroup$
6
  • 2
    $\begingroup$ Hm, I don't follow your reasoning here: I am pretty certain that the LDA does NOT bring you down to 1-dimension unless you choose to. It depends on how many eigenvectors you wish to retain after sorting the eigenvalues by decreasing values. Maybe I am missing something here ... but I didn't mention the number of classes. Let's assume we have 3 classes with 20 features each, and I want to project them onto a 3D subspace. $\endgroup$
    – user39663
    Commented Jul 8, 2014 at 1:57
  • 1
    $\begingroup$ The only reason to do PCA first is if the within-class covariance matrix is singular. If you have 20 features and three classes then it wont be singular so dont do PCA first. $\endgroup$
    – Aaron
    Commented Jul 8, 2014 at 3:43
  • 4
    $\begingroup$ assume we have 3 classes. @SebastianRaschka: Then LDA will allow you maximum 2 discriminant functions. The number of eigenvalues in LDA is min(num_groups-1,num_features). $\endgroup$
    – ttnphns
    Commented Jul 8, 2014 at 6:25
  • $\begingroup$ @Sebastian The number of discriminant functions you pick from LDA depends on what you want to do with it. As a space transform it's pretty much is like "supervised" PCA and you pick as many as you want. As an hyperplane separation classification method, the hyperplane is, by definition, of dimension N-1. I might ask a question on that topic for additional information though, because I still don't understand where does the min(num_groups-1,num_features) come from... $\endgroup$
    – Matthieu
    Commented Feb 13, 2016 at 14:54
  • 1
    $\begingroup$ @Matthieu I believe it's because of the in-between class scatter matrix, you create it by adding c (c=number of classes) matrices that have rank 1 or less. So you can only have c-1 non-zero eigenvalues at max. $\endgroup$
    – user39663
    Commented Feb 13, 2016 at 22:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.