Not tested

This topic is not tested in the final exam. Read it for a deeper understanding of why PCA and regularization help classification.

Introduction

PCA extracts the most representative information on the whole data, and LDA extracts the most discriminative information under a linear constraint. Both were built to lose the least information. This topic asks a deeper question: can dimensionality reduction actually raise the classification accuracy, and if so, why and how? It continues Visual Data Dimensionality Reduction.

Generalization is how well a classifier trained on the training samples performs on new samples it has never seen. A classifier generalizes well when its accuracy on new data stays close to its accuracy on the training data.

Main idea

A classifier learns from training data, and some statistics of the training data always differ from those of the whole population. Dimensionality reduction raises the accuracy only when it removes or corrects the dimensions that are unreliable (misleading) for classification. In a Gaussian classifier (the Bayes classifier for Gaussian classes) these are the dimensions of the small eigenvalues of the class covariance matrices.


Overview

The whole topic is one chain of questions:

It has three parts:

  • the objectives of feature extraction and dimensionality reduction for recognition
  • the problems of statistical classification in high dimension
  • the solutions by regularization and by dimensionality reduction

Step 1: questions on PCA and LDA

Why ask these questions:

  • the raw data holds more information than any of its low dimensional subspaces
  • any dimensionality reduction loses information, so extracting the most discriminative information only means losing the least information
  • if a higher accuracy can come from less information, the criterion "extract the most discriminative information" cannot explain where the gain comes from
  • a shallow study of this leads to wrong conclusions, so the issue needs careful thought

So the real questions are:

  • can PCA and LDA raise the classification accuracy?
  • why or why not?
  • if yes, to what extent, and how?

Reading order

The notes follow one line of thought, each step using the one before:

  1. Objectives of Dimensionality Reduction: four kinds of information, and why only removing misleading information can raise the accuracy
  2. Discriminant Function in Eigenspace: the Gaussian classifier written with eigenvalues, and the problem of small eigenvalues
  3. Eigenvalue Regularization: solutions 1 to 3, which keep every dimension and make the small eigenvalues larger
  4. PCA for Classification: solution 4, which drops the dimensions of the small eigenvalues
  5. Eigenspectrum Model: solution 5, which replaces the unreliable eigenvalues with a smooth model
  6. Supervised and Asymmetric PCA: solution 6, which weights the less reliable class more, and the conclusions

Concept map

flowchart TD
    A["Objectives<br/>remove misleading information MLI = RP ∩ DT"] --> B["Discriminant function in eigenspace<br/>gᵢ(x) = −½ Σ (zₖ − z̄ₖ)² / λₖ + bᵢ"]
    B -->|"small λₖ are too small"| C["Solutions 1 to 3<br/>λₖ + a, ρav, ρup"]
    C --> D["Solution 4: PCA<br/>drop the terms k > m"]
    D --> E["Solution 5: eigenspectrum model<br/>α / (k + β)"]
    E --> F["Solution 6: SPCA and APCA<br/>weight the less reliable class more"]

Why do we need this

It explains why PCA and regularization help a classifier, which the criteria "least reconstruction error" and "most discriminative information" cannot. It also shows how to choose which dimensions to remove.


Key math ideas

The math ideas this topic relies on, and where each one appears:

  • Eigenvectors and eigenvalues: the axes of each class and the spread along them, in Discriminant Function in Eigenspace, Eigenvalue Regularization, PCA for Classification and Eigenspectrum Model
  • Dot product and projection: the coordinates along each eigenvector of a class, in Discriminant Function in Eigenspace
  • Mahalanobis distance: the distance written as a sum over eigenvectors, so each axis can be judged on its own, in Discriminant Function in Eigenspace, Eigenvalue Regularization and PCA for Classification
  • Inverse covariance and whitening: a training that is too small makes too large, in Discriminant Function in Eigenspace and Eigenvalue Regularization
  • Covariance matrix: a estimated from few samples has the wrong shape, in Discriminant Function in Eigenspace
  • Rank: a class covariance from samples has rank at most , so most of its eigenvalues are zero, in Discriminant Function in Eigenspace
  • Likelihood: the ML covariance is fitted to the same few samples, so its smallest eigenvalues are far too small, in Discriminant Function in Eigenspace
  • Trace: the lost spread is shared out equally over the dropped axes, in Eigenvalue Regularization

Visual 1: fewer reliable dimensions, higher accuracy

A simulation of the main idea, how to read it:

  • two Gaussian classes in dimensions, each learned from only samples, then tested on new samples
  • black dashed: the Gaussian classifier with all dimensions and every learned gets 90.3%, far below the 99.5% it would get with the true and
  • blue: first reduce to dimensions by PCA, and going left from , dropping the dimensions of the small, unreliable eigenvalues raises the accuracy to 95.9% at
  • below about the curve falls fast, because useful dimensions are now dropped too
  • so less information gives more accuracy only when the removed part is the misleading part, and the other fixes are compared in Eigenvalue Regularization