Uncovering Locally Discriminative Structure for Feature Analysis

Sen Wang, Feiping Nie, Xiaojun Chang, Xue Li, Quan Z. Sheng, Lina Yao

Abstract

In machine learning, the efficacy of downstream tasks such as classification is heavily dependent on the quality of input features. While supervised methods like Linear Discriminant Analysis (LDA) are widely used, they frequently encounter the "Small Sample Size" (SSS) problem when labeled data is scarce. This paper introduces a novel kernel-based semi-supervised feature learning framework that simultaneously exploits global manifold structures and local discriminative information. By focusing on "local cliques" and applying a localized variant of the Fisher criterion, the proposed method effectively learns high-quality features even in extreme cases where only a single label per class is available.

Introduction

Feature analysis is a cornerstone of pattern recognition. Supervised dimensionality reduction techniques, particularly Linear Discriminant Analysis (LDA), aim to find a projection that maximizes the ratio of between-class scatter to within-class scatter. However, LDA's performance degrades significantly when the number of training samples is much smaller than the dimensionality of the feature space—a phenomenon known as the SSS problem. In such cases, the within-class scatter matrix becomes singular, leading to overfitting.

Semi-supervised learning methods have emerged as a solution, leveraging unlabeled data to uncover the underlying geometric manifold of the data. However, many existing manifold-based methods focus primarily on global structure, often overlooking the fine-grained local discriminative information that distinguishes classes at a neighborhood level. This paper proposes a method to bridge this gap by uncovering local discriminative structures within a semi-supervised framework.

Methodology

The proposed framework, termed Local Discriminant Structure Uncovering, integrates local manifold learning with discriminative analysis through five key components:

  1. Local Cliques: For every data point, the algorithm identifies a "clique" consisting of the point and its $k$-nearest neighbors (kNN). This localized approach captures the intrinsic geometry of the data manifold more effectively than global approximations.
  2. Local Fisher Criterion: Rather than calculating a global scatter matrix, the model applies a variant of the Fisher criterion to each local clique. This evaluates how well samples within that specific neighborhood are separated by class, providing a granular view of discriminative potential.
  3. Global Integration via Graph Laplacian: The discriminative scores derived from all local cliques are aggregated to form a new global graph Laplacian. This matrix serves as a comprehensive representation that encodes both the manifold geometry and local class differences.
  4. Kernel Extension: To address data that is not linearly separable, the authors employ the "kernel trick." By mapping the data into a high-dimensional Hilbert space, the model can define complex class boundaries that would be impossible to capture in the original feature space.
  5. Joint Optimization: The final objective function is designed to minimize intra-class distances for labeled data while regularizing the model with the newly constructed graph Laplacian. This optimization problem is solved efficiently using eigen-decomposition.

Experimental Evaluation

The model was evaluated across five diverse datasets to test its versatility and robustness:

  • COIL-20: Object recognition (20 objects, various poses).
  • UMIST: Face recognition (20 individuals).
  • USPS: Handwritten digit recognition (0-9).
  • YaleB: Face recognition under varying lighting conditions (38 subjects).
  • MIMIC II: Clinical data for mortality prediction (1,000 patient records).

Key Results

The proposed method consistently outperformed established baselines, including Kernel Discriminant Analysis (KDA) and Kernel Semi-supervised Discriminant Analysis (KSDA).

The method's strength was most apparent in scenarios of extreme label scarcity. For instance, on the YaleB dataset with only one label per class ($1 \times c$), the proposed method achieved a Mean Average Precision (MAP) of 0.463, significantly higher than KDA (0.359) and KSDA (0.245). The method also demonstrated competitive performance on the MIMIC II clinical dataset, matching or exceeding the performance of state-of-the-art ensemble methods (EnFS), which highlights its utility beyond image processing.

Discussion and Insights

The Importance of Locality

The research demonstrates that exploiting local structures is often more effective and computationally efficient than attempting to learn global structures, particularly when labels are sparse. By applying the Fisher criterion to small $k \times k$ matrices (where $k$ is typically 3 or 5), the computational burden is reduced compared to full-scale matrix inversions.

Regularization and Dimensionality

The parameter $\lambda$, which controls the weight of the local manifold information, proved critical. Experiments showed that performance consistently peaked when $\lambda > 0$, validating the hypothesis that local discriminative structure is a vital ingredient in feature analysis. Furthermore, the authors observed that reducing dimensionality often improved performance, suggesting the model successfully filters out irrelevant noise during the mapping process.

Limitations and Future Work

While the model is robust, it is not entirely parameter-free. The optimal number of neighbors ($k$) and the regularization parameter ($\lambda$) still require tuning for specific datasets. Additionally, while the local clique approach is efficient, the initial kNN search and the final eigen-decomposition on the full $n \times n$ kernel matrix may pose scalability challenges for massive datasets. Future research may explore approximate kNN algorithms or randomized linear algebra to enhance scalability for "Big Data" applications.

Summary updated

BibTeX
@inproceedings{wang2016uncovering,
  author = {Sen Wang and Feiping Nie and Xiaojun Chang and Xue Li and Quan Z. Sheng and Lina Yao},
  title = {{Uncovering Locally Discriminative Structure for Feature Analysis}},
  booktitle = {ECML/PKDD},
  year = {2016},
  url = {https://openreview.net/forum?id=HivRf9Q5_kr},
}
Figure