Semi-Supervised Dimension Reduction for Multi-Label Classification

Buyue Qian, Ian DavidsonAAAI 2010 · DOI

Introduction

Real-world data often presents a trifecta of challenges: high dimensionality, multi-label classification requirements, and incomplete annotations. For instance, a single image might be labeled with multiple tags like "nature," "sunset," and "beach," but obtaining a full set of labels for every image in a massive dataset is prohibitively expensive. Traditional approaches often treat dimensionality reduction and classification as separate, sequential steps. However, this decoupling can lead to suboptimal results where the reduced feature space fails to preserve the geometric structures critical for accurate label inference.

The SSDR-MC Framework

The Semi-Supervised Dimension Reduction for Multi-label Classification (SSDR-MC) framework addresses these issues by unifying dimensionality reduction and label inference into a single, alternating optimization process. The core philosophy is based on reconstruction error, similar to Locally Linear Embedding (LLE), where each data point is represented as a weighted linear combination of its nearest neighbors.

The model minimizes a joint objective function that balances feature reconstruction error with label reconstruction error. Because solving for both the neighborhood weights ($W$) and the missing labels ($F$) simultaneously is computationally difficult, the authors employ an iterative approach:

  1. Weight Learning: With labels fixed, the algorithm determines the weights that best describe the local data geometry.
  2. Label Inference: With weights fixed, labels are propagated from known instances to unlabeled ones across the graph.

The Virtuous Cycle of Optimization

A key insight of this research is the synergistic relationship between dimensionality reduction and label propagation. As the algorithm iterates, the geometric structure of the data and the correlation between labels (e.g., "bearded" and "male") mutually inform each other. This creates a "virtuous cycle" where improved label estimates lead to a more representative low-dimensional embedding, which in turn facilitates more accurate label prediction.

Figure 2: Comparison of dimensionality reduction techniques. (a) PCA and (b) PCA+LDA show significant overlap between classes. (c-e) SSDR-MC iterations demonstrate how the proposed method progressively separates clusters in the low-dimensional space.

Experimental Evaluation

The authors evaluated SSDR-MC across diverse domains, including face images, biological data (Yeast), natural scenes, and high-dimensional text (SIAM TMC 2007).

Figure 1: Sample images from the face dataset used for qualitative analysis. These images contain multiple overlapping attributes such as identity, gender, and facial hair.

Key findings include:

  • Performance: SSDR-MC consistently outperformed established baselines like RankSVM and ML-GFHF, achieving statistically significant improvements at the 98.77% level.
  • Label Efficiency: The model remained robust even with extremely sparse labeling (as low as 2.5%), with performance improving monotonically as more labels were provided.
  • Qualitative Clustering: In face image experiments, the model successfully grouped individuals based on shared attributes, placing "unbearded males" closer to "females" than to "bearded males" due to higher label similarity.

Conclusion and Future Directions

While SSDR-MC demonstrates strong performance and efficiency—particularly through the use of sparse linear systems for weight recovery—some challenges remain. The algorithm's convergence is managed via a tolerance threshold, as strict convergence for the classification function is not guaranteed. Future work may explore the formal role of negative weights in multi-label geometry and further automate parameter tuning for new datasets.

Summary updated

BibTeX
@inproceedings{qian2010semi,
  author = {Buyue Qian and Ian Davidson},
  title = {{Semi-Supervised Dimension Reduction for Multi-Label Classification}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7693},
}
Figure