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