The Role of Dimensionality Reduction in Classification

Weiran Wang, Miguel Á. Carreira-PerpiñánAAAI 2014 · OpenReview

Abstract: Dimensionality reduction (DR) is often used as a preprocessing step in classification, but usually one first fixes the DR mapping, possibly using label information, and then learns a classifier (a filter approach). Best performance would be obtained by optimizing the classification error jointly over DR mapping and classifier (a wrapper approach), but this is a difficult nonconvex problem, particularly with nonlinear DR. Using the method of auxiliary coordinates, we give a simple, efficient algorithm to train a combination of nonlinear DR and a classifier, and apply it to a RBF mapping with a linear SVM. This alternates steps where we train the RBF mapping and a linear SVM as usual regression and classification, respectively, with a closed-form step that coordinates both. The resulting nonlinear low-dimensional classifier achieves classification errors competitive with the state-of-the-art but is fast at training and testing, and allows the user to trade off runtime for classification accuracy easily. We then study the role of nonlinear DR in linear classification, and the interplay between the DR mapping, the number of latent dimensions and the number of classes. When trained jointly, the DR mapping takes an extreme role in eliminating variation: it tends to collapse classes in latent space, erasing all manifold structure, and lay out class centroids so they are linearly separable with maximum margin.

Introduction

In machine learning, dimensionality reduction (DR) is typically treated as a "filter" approach: researchers first reduce the dimensions of their data (using PCA, LDA, etc.) and then train a classifier on the result. While common, this is sub-optimal because the DR step does not "know" what the classifier needs to succeed.

The ideal alternative is a "wrapper" approach—jointly optimizing both the DR mapping ($F$) and the classifier ($g$). However, this creates a difficult non-convex optimization problem, especially with nonlinear mappings. The parameters are tightly coupled, making standard gradient descent slow and prone to poor local optima. This research introduces an efficient way to perform this joint optimization and explores what the "ideal" DR mapping looks like when it is forced to assist a classifier.

Methods: The Method of Auxiliary Coordinates (MAC)

The authors employ the Method of Auxiliary Coordinates (MAC) to solve the joint optimization problem. Instead of trying to solve the nested function $g(F(x))$ directly, they introduce auxiliary variables ($z$) that act as "targets" in the low-dimensional latent space. This transforms the hard problem into an alternating three-step process:

  1. The g-step: Train a standard linear SVM using the current latent coordinates ($z$).
  2. The F-step: Train a nonlinear mapping (specifically an RBF network) to map the original inputs ($x$) to the latent coordinates ($z$). This is essentially a standard RBF regression.
  3. The Z-step: A coordination step with a closed-form solution that nudges the latent coordinates to better satisfy both the classifier and the mapping.

This approach is powerful because it reuses well-developed, efficient algorithms and is highly parallelizable.

Key Insights: The "Collapse" Phenomenon

When DR and classification are optimized jointly, the mapping takes an extreme role. Instead of trying to preserve the "shape" or manifold of the data (as PCA or t-SNE do), it tries to erase it.

Figure 5: Visualization of the "collapse" phenomenon on spiral datasets. As the number of latent dimensions $L$ increases, the mapping collapses complex manifolds into discrete points (centroids) in latent space, arranged for optimal linear separability.

As visualized in Figure 5, the mapping attempts to collapse all points of the same class into a single point (centroid) in latent space. The authors found that for $K$ classes, the ideal latent dimensionality is $L = K - 1$. In this configuration, the mapping arranges class centroids at the vertices of a regular simplex (e.g., an equilateral triangle for 3 classes), providing the maximum possible margin for a linear classifier. This process effectively removes "unwanted degrees of freedom"—variations in the input that do not change the label.

Experimental Results

The researchers evaluated their approach on a mix of synthetic and real-world benchmarks, including the MNIST handwritten digit dataset and the PC/MAC document classification task.

Figure 3: Performance comparison on the PC/MAC dataset. The table shows that the joint optimization ("Ours") achieves lower error rates than PCA, LDA, and standard SVMs. The plots visualize how the joint approach separates classes more effectively than PCA.

On the MNIST dataset, the joint approach achieved a test error of 2.60%, which is competitive with Gaussian SVMs (2.93%) but with a massive reduction in the number of basis functions required (2,500 vs. ~13,800), leading to much faster classification at test time. On the PC/MAC dataset (Figure 3), the method outperformed standard LDA and PCA-based pipelines, showing that joint optimization is robust even in high-dimensional, sparse settings. The algorithm also showed near-linear speedup when distributed across multiple processors.

Conclusion

By jointly training the DR mapping and the classifier, this framework achieves state-of-the-art accuracy with significantly faster test-time performance. While the problem remains non-convex and sensitive to initialization, the MAC approach provides a scalable and efficient solution. Future work may extend this framework to more complex feature-extraction mappings, such as convolutional neural networks, to handle invariances more explicitly.

Summary updated

Abstract

Dimensionality reduction (DR) is often used as a preprocessing step in classification, but usually one first fixes the DR mapping, possibly using label information, and then learns a classifier (a filter approach). Best performance would be obtained by optimizing the classification error jointly over DR mapping and classifier (a wrapper approach), but this is a difficult nonconvex problem, particularly with nonlinear DR. Using the method of auxiliary coordinates, we give a simple, efficient algorithm to train a combination of nonlinear DR and a classifier, and apply it to a RBF mapping with a linear SVM. This alternates steps where we train the RBF mapping and a linear SVM as usual regression and classification, respectively, with a closedform step that coordinates both. The resulting nonlinear low-dimensional classifier achieves classification errors competitive with the state-of-the-art but is fast at training and testing, and allows the user to trade off runtime for classification accuracy easily. We then study the role of nonlinear DR in linear classification, and the interplay between the DR mapping, the number of latent dimensions and the number of classes. When trained jointly, the DR mapping takes an extreme role in eliminating variation: it tends to collapse classes in latent space, erasing all manifold structure, and lay out class centroids so they are linearly separable with maximum margin.
BibTeX
@inproceedings{wang2014role,
  author = {Weiran Wang and Miguel Á. Carreira-Perpiñán},
  title = {{The Role of Dimensionality Reduction in Classification}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2014},
  url = {https://openreview.net/forum?id=HJWfEebO-B},
}
Figure