Introduction

Feature extraction and dimensionality reduction should help recognition, but losing less information does not by itself give any gain in accuracy. This note splits information into four kinds, by population and by training data, and shows that the only source of an accuracy gain is removing misleading information.

Main idea

A classifier already extracts the discriminative information on the training data (DT) and ignores the redundant information on it (RT). Doing either again before the classifier cannot raise the accuracy. Removing the misleading information $\text{MLI}=\text{RP}\cap\text{DT}$, which looks discriminative on the training data but is redundant on the population, can.


Overview

The argument in four moves:

  • more dimensions should help in theory, but often hurt in practice, so something in practice is different
  • the difference is between the population (all data that will ever be seen) and the training data (the samples we have)
  • information that is discriminative on the training data but redundant on the population misleads the classifier
  • so a useful dimensionality reduction must find and remove the dimensions that are unreliable for classification

Step 1: paradox of dimensionality

Two facts that seem to disagree:

  • in theory, the probability of misclassification decreases as the data dimensionality increases, as long as the decision is made properly
  • in practice, a high dimensionality often makes the classification worse, which is the curse of dimensionality

Why the theory holds: the Bayes error is the lowest possible error rate, reached by the optimal (Bayes) classifier that knows the true class distributions. Adding a feature can never raise it, because the optimal classifier is free to ignore the new feature. So more dimensions can only keep or add information about the classes.

How to resolve the paradox:

  • separate the discriminative information about the data population from the discriminative information on the training data set
  • every module of a recognition system aims to extract the most discriminative information about the whole population, not about one training set
  • the theory assumes the population statistics are known, but in practice they are learned from a finite training set

Step 2: four kinds of information

Information about the population:

  • DP is the discriminative information on the population
  • RP is the redundant information on the population
  • every module of the system, though each works in a different way, has the same objective: extract DP or remove RP

Information on the training data:

  • DT is the discriminative information on the training data
  • RT is the redundant information on the training data
  • a proper classifier extracts DT, or removes (ignores) RT, because it is trained to fit the training data, so it uses whatever separates the training classes and ignores the rest

DP and DT are not the same, because the training data is only a sample of the population. Here a piece of information can be thought of as a feature or a direction in the data space, as the example in Step 4 shows.


Step 3: where a gain can come from

The figure plots the recognition accuracy against the reduced dimension , up to the full dimension .

Reading the figure:

  • the black curve is a bad feature extraction, and the accuracy only falls as decreases
  • the blue curve is LDA, which extracts the most discriminative information, and its peak is only a little above the accuracy at
  • the red curve (method R) is any method that removes misleading information, such as the solutions in the later notes, and its peak is far above the accuracy at
  • the green curve uses method R followed by LDA, which reaches the same high accuracy with far fewer dimensions

Why LDA alone gives no gain:

  • if information is split as discriminative + redundant, then reducing the dimension can only lose discriminative information
  • the best LDA can do is to lose the least, and minimizing a loss never gives a gain, so its criterion cannot explain its small rise, which must come from removing some misleading information as a side effect
  • a gain needs a different split: information = reliable information + misleading information, so that removing the misleading part raises the accuracy

Step 4: simple example

What the figure shows:

  • two classes (blue and red) are measured with two features and
  • the blue samples form a column at a small and the red samples form a column at a larger , with both columns spread over a similar range of
  • the two large dots on the axis mark where each class sits along
  • a green vertical line separates the two columns using alone
  • a tilted black line also depends on , and as drawn it crosses both columns

The labels on the axes read:

  • : DP shows up as DT, so a classifier is right to use it
  • : RP should show up as RT, but on a training set it can show up as DT, and then it becomes MLI

The idea: carries no class information in the population, but in a small training set the two classes can happen to differ a little along , so looks discriminative. Information that is redundant on the population but discriminative on the training data is misleading information:

What the two lines stand for:

  • the green line uses only , the boundary that works for the population
  • the black line stands for a boundary that also uses , which is what a classifier does when looks discriminative on its training set
  • such a boundary follows an accident of the training set, so it makes more errors on new samples
  • removing (the MLI) makes the decision more accurate and more robust

What this means for dimensionality reduction:

  • removing RT or extracting DT before the classifier cannot raise the recognition accuracy, because the classifier does that job already, so it can only simplify or speed up the classification
  • removing MLI can raise the accuracy
  • the open questions are whether the criteria of PCA or LDA achieve this, and how to find the unreliable, harmful or misleading dimensions

Step 5: general rules are not enough

Well-known phenomena:

  • the curse of dimensionality
  • the small sample size problem
  • the noise removal effect of dimensionality reduction
  • better generalization in a lower dimensional space

Why they do not help directly:

  • they do not say which dimensions to extract or which to remove for a more robust classification
  • an effective dimensionality reduction cannot be built from these general phenomena alone
  • extracting the maximal discriminative information just means losing the minimal discriminative information, and a minimum loss does not mean any gain
  • so a reduction that only minimizes the loss of discriminative information is unlikely to boost the accuracy

Step 6: target the unreliable dimensions

The key reasoning:

  • a classifier is trained to capture the discriminative information on the training samples
  • if some statistics learned on the training data deviate from those of the population, the error rate on new data increases
  • in practice this always happens to some degree, and the only question is how severe it is

So, to boost the accuracy, dimensionality reduction should target the dimensions that are unreliable or harmful for classification, and remove them.


Why do we need this

It replaces the vague goal "keep the most information" with a precise one: find the dimensions whose training statistics do not match the population, and remove or correct them.


Next step

Discriminant Function in Eigenspace finds exactly where these unreliable dimensions hide in a Gaussian classifier.


Visual 1: misleading information on real numbers

The example of Step 4 computed, how to read it:

  • carries the real class difference (DP), and is pure noise with the same spread in both classes (RP)
  • by chance the 6 training samples per class differ a little along , so the black boundary that uses both features fits them perfectly, while the green one that uses alone makes 2 mistakes
  • on 100,000 new samples (300 drawn) the order flips: 23% wrong with , 9% wrong without it
  • so is : discriminative on the training data, redundant on the population
  • both boundaries are Gaussian classifiers with a shared covariance, fitted to the training samples only