Unsupervised Discriminant Analysis Based on the Local and Non-local Mean

Caikou Chen, Jun Shi, Pu HuangPhysics 2012 · DOI

TL;DR

This paper introduces a new feature extraction method, Unsupervised Discriminant Analysis (UDA), that improves upon existing Unsupervised Discriminant Projection (UDP) by being more robust to outliers and computationally efficient. By using local and non-local means instead of raw sample points to construct scatter matrices, UDA achieves better performance on face recognition tasks.

What Problem Does This Paper Address?

In computer vision and pattern recognition, feature extraction is crucial for representing high-dimensional data in a lower-dimensional space, which aids in classification and recognition. While methods like Principal Component Analysis (PCA) and Linear Discriminant Analysis (LDA) are popular, they struggle with the non-linear structures often found in real-world data. More advanced techniques like Unsupervised Discriminant Projection (UDP) attempt to address this by considering both local (neighboring) and non-local (distant) relationships between data points. However, UDP's performance is significantly degraded by outliers in the training data, and it can be computationally expensive, especially with high-dimensional data and limited training samples. This paper aims to overcome these limitations by developing a more robust and efficient feature extraction method.

Methods

The core innovation of this paper is the proposed Unsupervised Discriminant Analysis (UDA) method. UDA builds upon the Unsupervised Discriminant Projection (UDP) framework but modifies how the local and non-local scatter matrices are constructed.

  • UDP's Approach: UDP aims to maximize the non-local scatter and minimize the local scatter. It defines local scatter based on the distance between projected sample points within a K-nearest neighbor (KNN) neighborhood and non-local scatter based on distances between points outside this neighborhood.
  • UDA's Novelty: UDA replaces the direct use of individual sample points in scatter matrix calculations with the mean of neighboring samples.
  • Local Scatter: Instead of calculating scatter between individual neighboring points, UDA calculates the scatter between a sample point and the local mean of its KNN neighbors.
  • Non-local Scatter: Similarly, UDA calculates the scatter between a sample point and the non-local mean of points outside its KNN neighborhood.

This shift to using means is hypothesized to make the scatter matrices more accurate and less sensitive to outliers. The objective function for UDA is to maximize the non-local scatter and minimize the local scatter, similar to UDP, but using the new mean-based scatter matrices. The optimal projection axes are found by solving a generalized eigenvalue problem.

The algorithm proceeds as follows:

  1. Determine K-nearest neighbors for each sample and construct an adjacency matrix.
  2. Perform initial dimensionality reduction using PCA.
  3. Construct the local and non-local scatter matrices using the local and non-local means as described above.
  4. Obtain the optimal projection axes by computing the eigenvectors corresponding to the largest eigenvalues of the generalized eigenvalue problem.

Datasets

The proposed UDA method was evaluated on three standard face image databases:

  • ORL Face Database: Contains 40 individuals, each with 10 images (112x92 resolution).
  • YALE Face Database: Consists of 15 individuals, each with 11 images (100x80 resolution), captured under varying facial expressions and lighting conditions.
  • AR Face Database: Features 120 individuals, each with 26 images (50x40 resolution), exhibiting different facial expressions, lighting, and occlusions (including glasses).

The paper does not mention the introduction of any new benchmarks.

Key Insights and Ideas

  • Robustness to Outliers: The central idea is that using local and non-local means for scatter matrix construction makes the feature extraction process inherently more robust to outliers. Outliers have a less pronounced effect on the mean of a group of points compared to their direct influence on individual point-to-point distances.
  • Computational Efficiency: By using means, the method can potentially reduce computational complexity. While not explicitly detailed how, the paper claims UDA is computationally more efficient than UDP.
  • Balancing Local and Non-local Information: The method effectively leverages both local neighborhood information and broader non-local relationships, a strategy that has proven beneficial in feature extraction.

Key Results

The experimental results on the ORL, YALE, and AR face databases consistently show that the proposed UDA method outperforms PCA, LDA, and the original UDP method in terms of recognition rate.

  • ORL Database: UDA achieved a maximal recognition rate of 93% with 35 dimensions, outperforming PCA (88.5%), LDA (92%), and UDP (90.5%).
  • YALE Database: UDA achieved a maximal recognition rate of 98.67% with 30 dimensions, significantly better than PCA (92%), LDA (93.33%), and UDP (93.33%).
  • AR Database: UDA achieved a recognition rate of 74.17% with 200 dimensions, compared to UDP's 72.8% with the same dimensionality. Furthermore, UDA demonstrated a reduction in feature extraction time (999.8 seconds) compared to UDP (1030.7 seconds).

These results suggest that UDA is not only more accurate but also more efficient.

Limitations and Future Work

  • Limitations: The paper acknowledges that the performance of UDP (and by extension, UDA's reliance on its framework) can be influenced by outliers, though UDA aims to mitigate this. The specific computational efficiency gains are stated but not deeply analyzed in terms of algorithmic complexity.
  • Future Work: Not explicitly discussed in the paper, but the demonstrated robustness and efficiency suggest potential applications in other areas of pattern recognition and computer vision where outlier sensitivity and computational cost are significant challenges. Further theoretical analysis of the computational complexity and robustness guarantees could be valuable.

Summary updated

Abstract

Considering the performance of unsupervised discriminant projections (UDP) is gravely influenced by outliers, especially in small training sample size situation, a novel method called unsupervised discriminant analysis (UDA) based on the local and non-local mean for feature extraction is proposed in this paper, which is robust to outliers. It utilizes the local and non-local mean to construct the local and non-local scatter, to some extent, overcomes the discriminant difficulty caused by outliers. Besides, LUDA is computationally more efficient than UDP. Experimental results on ORL, YALE and AR face image databases show that the proposed UDA is more efficient and effective than UDP.
BibTeX
@inproceedings{chen2012unsupervised,
  author = {Caikou Chen and Jun Shi and Pu Huang},
  title = {{Unsupervised Discriminant Analysis Based on the Local and Non-local Mean}},
  booktitle = {Physics},
  year = {2012},
  doi = {10.1016/j.phpro.2012.02.289},
}
Figure