Abstract
This paper describes a novel framework to jointly learn data-dependent label and locality-preserving projections. Given a set of data instances from multiple classes, the proposed approach can automatically learn which classes are more similar to each other, and construct discriminative features using both labeled and unlabeled data to map similar classes to similar locations in a lower dimensional space. In contrast to linear discriminant analysis (LDA) and its variants, which can only return c-1 features for a problem with c classes, the proposed approach can generate d features, where d is bounded only by the number of the input features. We describe and evaluate the new approach both theoretically and experimentally, and compare its performance with other state of the art methods.
Introduction
Dimensionality reduction is a critical step in processing high-dimensional data such as images and text. Traditional methods, however, face significant limitations. Linear Discriminant Analysis (LDA) is constrained by the number of classes ($c$), producing at most $c-1$ features, which often leads to overfitting when labeled data is scarce. Conversely, Locality Preserving Projections (LPP) focuses on the data's manifold structure but ignores discriminative class labels. Canonical Correlation Analysis (CCA) maps two sets of data to a common space but lacks an effective mechanism to utilize unlabeled data. This paper introduces "Discriminative Projections," a semi-supervised framework that overcomes these bottlenecks by jointly learning mappings for both data and labels.
Methodology: Discriminative Projections
The core innovation of this framework is the simultaneous learning of two mapping functions: $f$, which maps data instances ($x$) to a $d$-dimensional space, and $g$, which maps class labels ($y$) to that same space. Unlike standard approaches that treat labels as fixed one-hot vectors, this method allows labels to be data-dependent and flexible.
The algorithm optimizes a cost function comprising three primary components:
- Label Matching: Minimizing the distance between a projected data point and its projected true label.
- Manifold Regularization: Utilizing a graph Laplacian from both labeled and unlabeled data to preserve local geometric structures.
- Separation: Maximizing the distance between data points and incorrect labels.
The resulting optimization problem is solved via generalized eigenvalue decomposition, providing an efficient and optimal linear projection.
Experimental Evaluation
The approach was evaluated on two distinct datasets:
- USPS Digit Data: 9,298 grayscale images ($16 \times 16$) of handwritten digits (0-9).
- TDT2 (Topic Detection and Tracking): A high-dimensional sparse text dataset, focusing on the four largest categories (5,705 documents).
Results and Discussion
Discriminative Projections demonstrated superior performance across several metrics. In nearest-neighbor tests, the method consistently outperformed LDA, CCA, and LPP. Notably, on the USPS dataset, a 100D embedding achieved significantly higher accuracy than the 9D embedding to which LDA is restricted.
Key insights from the results include:
- Breaking the $c-1$ Barrier: By projecting labels into a flexible space, the dimensionality $d$ is bounded only by the input features, allowing for richer visualizations and more complex feature sets even for binary classification.
- Generalization: While LDA and CCA showed signs of overfitting on training data, Discriminative Projections maintained high performance on unseen test data.
- Semantic Label Mapping: The algorithm successfully discovered intrinsic relationships between classes, mapping similar digits (e.g., 3, 6, and 9) closer together in the learned label space.
Conclusion
While the current framework focuses on linear projections, it offers a robust semi-supervised approach to dimensionality reduction. Future work may address extensions to non-linear kernels and improving scalability for extremely large datasets where similarity graph construction becomes computationally intensive. Additionally, while the weight parameter $\mu$ for manifold regularization can be set via heuristics, further automation of parameter selection remains an area for exploration.
Summary updated