Abstract
Dimensionality reduction is a fundamental and important research topic in the field of machine learning. This paper focuses on a dimensionality reduction technique that exploits semi-supervising information in the form of pairwise constraints; specifically, these constraints specify whether two instances belong to the same class or not. We propose two dual linear methods to accomplish dimensionality reduction under that setting. These two methods overcome the difficulty of maximizing between-class difference and minimizing within-class difference at the same time, by transforming the original data into a new space in such a way that the bi-objective problem is (almost) equivalently reduced to a single objective problem. Empirical evaluations on a broad range of public datasets show that the two proposed methods are superior to several existing methods for semi-supervised dimensionality reduction.
Introduction
In modern machine learning, high-dimensional data presents a significant challenge known as the "curse of dimensionality." While high-dimensional spaces contain rich information, they are often computationally expensive to process and prone to noise. Dimensionality reduction (DR) serves as the standard solution to these issues.
Traditional DR methods generally fall into two categories: unsupervised methods like Principal Component Analysis (PCA), which ignore labels entirely, and supervised methods like Fisher Linear Discriminant (FLD), which require fully labeled datasets. Semi-supervised DR fills the gap between these extremes by utilizing "pairwise constraints"—information indicating whether two specific data points belong to the same class (must-link) or different classes (cannot-link). This approach is particularly valuable when full labeling is too costly to obtain.
The Bi-Objective Dilemma
Most existing semi-supervised DR algorithms face a fundamental "bi-objective dilemma." They attempt to simultaneously maximize the distance between different classes ($J_B$) and minimize the distance within the same class ($J_W$). Mathematically, these two goals often conflict. Finding an optimal balance is difficult, and many algorithms settle for compromises that fail to preserve the data's most critical underlying structures.
Proposed Methodology: BWDR and WBDR
The researchers propose two dual linear methods designed to bypass this dilemma by transforming the data space so that one of the two objectives becomes a constant, effectively reducing the problem to a single-objective optimization.
- BWDR (Between-class Weighting Dimensionality Reduction): This method "stretches" the data along the eigenvectors of the between-class scatter matrix. This transformation ensures that the between-class difference is uniform in every direction. Once $J_B$ is rendered constant, the algorithm focuses solely on minimizing the within-class difference ($J_W$).
- WBDR (Within-class Weighting Dimensionality Reduction): This is the dual approach. It "compresses" the data based on the within-class scatter matrix so that the within-class difference becomes nearly constant across all directions. The optimization problem then reduces to simply maximizing the between-class difference ($J_B$).
Key Insights and Visual Transformation
The core innovation lies in changing the "physics" of the data space. Instead of struggling to balance competing variables, the transformation makes one goal trivially satisfied. This allows the algorithm to focus entirely on the remaining objective, such as packing same-class points closer together or pushing different-class points further apart.
As shown in the figure above, the transformation effectively separates overlapping clusters, making the underlying class structure much more apparent and easier for subsequent classification algorithms to process.
Experimental Evaluation
The researchers evaluated BWDR and WBDR against standard benchmarks, including:
- 16 UCI Machine Learning Repository datasets: Spanning domains such as biology, finance, and physical sensors.
- Extended Yale Face Database B (YaleB): A standard image dataset for face recognition.
- MNIST: A subset of the handwritten digit database.
Semi-supervision was simulated by randomly sampling pairs of instances to create must-link and cannot-link constraints. Notably, the methods proved efficient even with minimal information, often stabilizing with as little as 0.002% to 0.04% of possible pairwise constraints.
Key Results
- Superior Accuracy: In 1-Nearest Neighbor (1-NN) classification tests, the proposed methods achieved the highest accuracy on nearly all 16 UCI datasets compared to PCA, constrained FLD (cFLD), and SSDR.
- Low-Dimensional Dominance: BWDR and WBDR were particularly effective when reducing data to very low dimensions (1 to 3). While PCA and SSDR often struggled in these scenarios, the proposed methods captured essential class-separating structures immediately.
- Clustering Purity: On image datasets like YaleB, WBDR maintained significantly higher "neighborhood purity" (the likelihood that a point's neighbors belong to the same class) than competing methods.
- Robustness: Unlike some existing methods that can become unstable on specific datasets, the "stretching and compression" approach remained robust across diverse data types.
Conclusion and Future Work
BWDR and WBDR demonstrate that linear methods can be highly effective and computationally efficient when the optimization problem is framed correctly. While these methods currently assume accurate constraints, future work may involve developing "kernelized" versions to handle non-linear manifolds and increasing robustness to noisy or contradictory human-labeled constraints.
Summary updated