Maximum Neighborhood Margin Discriminant Projection for Classification

Jianping Gou, Yongzhao Zhan, Min Wan, Xiang‐Jun Shen, Jinfu Chen, Lan DuThe Scientific World JOURNAL 2014 · DOI

TL;DR

This paper introduces Maximum Neighborhood Margin Discriminant Projection (MNMDP), a novel supervised dimensionality reduction technique that leverages both local data structure and class labels. By maximizing the margin between intraclass and interclass neighborhoods, MNMDP aims to improve classification accuracy by better preserving intrinsic data manifolds and enhancing inter-class separability.

What Problem Does This Paper Address?

High-dimensional data presents a significant challenge in many machine learning tasks, including classification, due to the "curse of dimensionality." Dimensionality reduction (DR) techniques aim to map this data into a lower-dimensional subspace while preserving essential information. Traditional methods like Principal Component Analysis (PCA) focus on global data structure, while Linear Discriminant Analysis (LDA) incorporates class information but can struggle with complex manifold structures. Locality Preserving Projection (LPP) and its variants capture local manifold structures but often neglect class information, limiting their effectiveness in classification. This paper addresses the need for a DR method that effectively combines both local geometric information and explicit class labels to achieve superior classification performance.

Methods

The core contribution is the Maximum Neighborhood Margin Discriminant Projection (MNMDP) algorithm. MNMDP builds upon the graph embedding framework, similar to LPP, but introduces several key innovations:

  • Supervised Affinity Weighting: Unlike unsupervised methods, MNMDP explicitly uses class labels. It constructs a k-nearest neighbor graph and assigns affinity weights to edges. These weights are designed to capture both local geometric similarity (using an exponential decay function) and discriminating information.
  • Intraclass Affinity: For neighbors within the same class, the weight is 1 + exp(-||x_i - x_j||^2 / δ), which emphasizes similarity and incorporates a "discriminating weight" for same-class points.
  • Interclass Affinity: For neighbors from different classes, the weight is exp(-||x_i - x_j||^2 / δ) * (1 - exp(-||x_i - x_j||^2 / δ)), which aims to push apart points from different classes.
  • Maximizing Neighborhood Margin: The objective is to maximize the margin between the aggregated intraclass neighborhood scatter and the interclass neighborhood scatter. This is achieved by formulating a generalized eigenvalue problem (S⁻ - S⁺)Φ = λΦ, where S⁻ and S⁺ are the interclass and intraclass scatter matrices, respectively, and Φ is the projection matrix. The optimal projection matrix is formed by eigenvectors corresponding to the largest positive eigenvalues.
  • Local Scaling Regulator (δ): A parameter δ is introduced to dynamically adjust the affinity weights based on local data density, allowing for a more robust representation of classification contributions.

Datasets

The proposed MNMDP method was evaluated on four publicly available, high-dimensional datasets:

  • PolyU HRF (High-Resolution-Fingerprint) database: Used for fingerprint recognition.
  • PolyU FKP (Finger-Knuckle-Print) database: Used for finger-knuckle print recognition.
  • AR face database: A standard benchmark for face recognition.
  • UCI Musk database: A two-class classification task for predicting molecule properties.

Key Insights and Ideas

  • Synergy of Local and Global Information: The paper strongly suggests that effective classification requires a balance between preserving local manifold structures (like LPP) and explicitly leveraging class separability (like LDA). MNMDP's novel affinity weighting mechanism is designed to achieve this synergy.
  • Importance of Affinity Weight Design: The specific formulation of intraclass and interclass affinity weights is crucial. The 1 + exp(...) term for intraclass points and the (1 - exp(...)) term for interclass points are key to enhancing discrimination.
  • "Neighborhood Margin" as a Discriminative Measure: Maximizing the margin between intraclass and interclass neighborhood scatters provides a direct mechanism to push apart different classes while keeping same-class points together, leading to improved classification.
  • Robustness to Noise and Dimensionality: The paper demonstrates that MNMDP consistently outperforms other methods across various reduced dimensionality settings and shows good performance even with varying numbers of training samples.

Key Results

The experimental results across the four diverse datasets consistently show that MNMDP achieves superior classification performance compared to PCA, LDA, LPP, and UDP.

  • HRF: MNMDP achieved the highest recognition rates, with optimal dimensionality significantly lower than other methods. For instance, with l=8 training samples, MNMDP reached 83.78% accuracy with only 40 dimensions, outperforming LDA (78.55% with 55 dimensions) and others.
  • FKP: Similar to HRF, MNMDP consistently outperformed other methods, achieving up to 94.45% accuracy with 55 dimensions for l=9.
  • AR: MNMDP demonstrated remarkable performance, reaching up to 99.00% accuracy with 120 dimensions for l=13.
  • Musk: MNMDP also showed the best performance on this binary classification task, achieving 87.91% accuracy with only 7 dimensions for l=140.

Across all datasets, MNMDP generally required a lower reduced dimensionality to achieve its peak performance compared to the other methods.

Limitations and Future Work

  • Parameter Sensitivity (δ and k): While the paper shows that appropriate values for δ (local scaling regulator) and k (neighborhood size) are important and can be found through experimentation, the method's performance can be sensitive to these parameters.
  • Linear Projection: MNMDP, in its current form, is a linear projection method. The authors acknowledge that for complex, non-linear data structures, mapping to Hilbert space with kernel tricks might be necessary.
  • Future Work: The authors explicitly mention plans to extend MNMDP with kernel tricks to handle non-linear data structures, which would further enhance its applicability. They also suggest exploring more comparative discussions with other distance metric learning methods like NCA and LMNNC.

Summary updated

Abstract

We develop a novel maximum neighborhood margin discriminant projection (MNMDP) technique for dimensionality reduction of high-dimensional data. It utilizes both the local information and class information to model the intraclass and interclass neighborhood scatters. By maximizing the margin between intraclass and interclass neighborhoods of all points, MNMDP cannot only detect the true intrinsic manifold structure of the data but also strengthen the pattern discrimination among different classes. To verify the classification performance of the proposed MNMDP, it is applied to the PolyU HRF and FKP databases, the AR face database, and the UCI Musk database, in comparison with the competing methods such as PCA and LDA. The experimental results demonstrate the effectiveness of our MNMDP in pattern classification.
BibTeX
@article{gou2014maximum,
  author = {Jianping Gou and Yongzhao Zhan and Min Wan and Xiang‐Jun Shen and Jinfu Chen and Lan Du},
  title = {{Maximum Neighborhood Margin Discriminant Projection for Classification}},
  journal = {The Scientific World JOURNAL},
  year = {2014},
  doi = {10.1155/2014/186749},
}
Figure