Elsevier

Pattern Recognition

Volume 45, Issue 6, June 2012, Pages 2432-2444
Pattern Recognition

A supervised non-linear dimensionality reduction approach for manifold learning

https://doi.org/10.1016/j.patcog.2011.12.006Get rights and content

Abstract

In this paper we introduce a novel supervised manifold learning technique called Supervised Laplacian Eigenmaps (S-LE), which makes use of class label information to guide the procedure of non-linear dimensionality reduction by adopting the large margin concept. The graph Laplacian is split into two components: within-class graph and between-class graph to better characterize the discriminant property of the data. Our approach has two important characteristics: (i) it adaptively estimates the local neighborhood surrounding each sample based on data density and similarity and (ii) the objective function simultaneously maximizes the local margin between heterogeneous samples and pushes the homogeneous samples closer to each other.

Our approach has been tested on several challenging face databases and it has been conveniently compared with other linear and non-linear techniques, demonstrating its superiority. Although we have concentrated in this paper on the face recognition problem, the proposed approach could also be applied to other category of objects characterized by large variations in their appearance (such as hand or body pose, for instance).

Highlights

► We propose a novel supervised non-linear dimensionality reduction (DR) approach that adopts the large margin concept. ► The approach adaptively estimates the local neighborhood surrounding each sample based on local density and similarity. ► It maximizes the local margin between heterogeneous samples and pushes the homogeneous samples closer to each other. ► For validation purposes, we applied our method to the face recognition problem. ► Results obtained on six face data sets show that our approach outperforms many recent linear and non-linear DR techniques.

Introduction

In recent years, a new family of non-linear dimensionality reduction techniques for manifold learning has emerged. The most known ones are: kernel principal component analysis (KPCA) [1], locally linear embedding (LLE) [2], [3], Isomap [4], Supervised Isomap [5], Laplacian Eigenmaps (LE) [6], [7]. This family of non-linear embedding techniques appeared as an alternative to their linear counterparts which suffer of severe limitation when dealing with real-world data: (i) they assume the data lie in an Euclidean space and (ii) they may fail when the number of samples is too small. On the other hand, the non-linear dimensionality techniques are able to discover the intrinsic data structure by exploiting the local topology. In general, they attempt to optimally preserve the local geometry around each data sample while using the rest of the samples to preserve the global structure of the data.

In this paper we introduce a novel Supervised LE (S-LE) algorithm, which exploits the class label information for mapping the original data in the embedded space. The use of labels allows us to split graph Laplacian associated to the data into two components: within-class graph and between-class graph. Our proposed approach benefits from two important properties: (i) it adaptively estimates the local neighborhood surrounding each sample based on data density and similarity and (ii) the objective function simultaneously maximizes the local margin between heterogeneous samples and pushes the homogeneous samples closer to each other. The main contributions of our work are as follows: (1) bypassing the use and selection of a predefined neighborhood for graph construction and (2) exploiting the discriminant information in order to get the non-linear embedding (spectral projection).

The combination between locality preserving property (inherited from the classical LE1) and the discriminative property (due to the large margin concept) represents a clear advantage for S-LE, compared with other non-linear embedding techniques, because it finds a mapping which maximizes the distances between data samples from different classes at each local area. In other words, it maps the points in an embedded space where data with similar labels fall close to each other and where the data from different classes fall far apart.

The adaptive selection of neighbors for the two graphs represents also an added value to our algorithm. It is well known that a sensitive matter affecting non-linear embedding techniques is represented by the proper choice for neighborhood size. Setting a too high value for this parameter would result in a loss of local information, meanwhile a too low value could result in an over-fragmentation of the manifold (problem known as ‘short-circuiting’). For this reason, setting an adequate value for this parameter is crucial in order to confer the approach topological stability.

The rest of the paper is organized as follows. Section 2 reviews some related work on linear and non-linear dimensionality reduction techniques. In this section, we also recall, for the sake of completeness, the classic Laplacian Eigenmaps algorithm. Section 3 is devoted to the presentation of our new proposed algorithm. Section 4 presents extensive experimental results obtained on a man-made object data set and on six face databases. Finally, Section 5 contains our conclusions and guidelines for future work.

Section snippets

Related work

During the last few years, a large number of approaches have been proposed for constructing and computing an embedded subspace by finding an explicit or non-explicit mapping that projects the original data to a new space of lower dimensionality [8], [9], [10]. These methods can be grouped into two families: linear and non-linear approaches.

Supervised Laplacian Eigenmaps

While the LE may give good results for non-linear dimensionality reduction, it has not been widely used and assessed for classification tasks. Indeed, many experiments show that the recognition rate in the embedded space can be highly depending on the choice of the neighborhood size in the reconstructed graph [15], [30], [31]. Choosing the ideal size, K or ϵ, in advance can be a very difficult task. Moreover, the introduced mapping by LE does not exploit the discriminant information given by

Experimental results

In this section, we report the experimental results obtained from the application of our proposed algorithm to the problem of visual pattern recognition. Extensive experiments in terms of classification accuracy have been carried out on a man-made object database as well as on some public face databases. All these databases are characterized by a large variation in object appearance.

Conclusions and future work

We proposed a novel supervised non-linear dimensionality reduction technique, namely Supervised Laplacian Eigenmap (S-LE). Our algorithm benefits from two important properties: (i) it adaptively estimates the local neighborhood surrounding each sample based on data density and similarity and (ii) the objective function simultaneously maximizes the local margin between heterogeneous samples and pushes the homogeneous samples closer to each other.

For validation purposes, we applied our method to

Acknowledgment

This work was partially supported by the Spanish Government under the project TIN2010-18856.

Bogdan Raducanu received the B.Sc. degree in computer science from the University “Politehnica” of Bucharest, Bucharest, Romania, in 1995 and the Ph.D. degree “Cum Laude” from the University of the Basque Country, Bilbao, Spain, in 2001. Currently, he is a senior researcher at the Computer Vision Center in Barcelona, Spain. His research interests are: computer vision, pattern recognition, machine learning, artificial intelligence, social computing and human–robot interaction. He is the author

References (38)

  • X. Geng et al.

    Supervised nonlinear dimensionality reduction for visualization and classification

    IEEE Transactions on Systems, Man, and Cybernetics-part B: Cybernetics

    (2005)
  • M. Belkin et al.

    Laplacian eigenmaps for dimensionality reduction and data representation

    Neural Computation

    (2003)
  • L. Saul et al.

    Spectral methods for dimensionality reduction

  • S. Yan et al.

    Graph embedding and extension: a general framework for dimensionality reduction

    IEEE Transactions on Pattern Analysis and Machine Intelligence

    (2007)
  • T. Zhang et al.

    Patch alignment for dimensionality reduction

    IEEE Transactions on Knowledge and Data Engineering

    (2009)
  • H. Li et al.

    Efficient and robust feature extraction by maximum margin criterion

    IEEE Transactions on Neural Networks

    (2006)
  • T. Kim et al.

    Locally linear discriminant analysis for multimodally distributed classes for face recognition with a single model image

    IEEE Transactions on Pattern Analysis and Machine Intelligence

    (2005)
  • X. He et al.

    Locality preserving projections

  • X. He et al.

    Face recognition using Laplacianfaces

    IEEE Transactions on Pattern Analysis and Machine Intelligence

    (2005)
  • Cited by (130)

    • Application of adaptive Laplacian Eigenmaps in near infrared spectral modeling

      2022, Spectrochimica Acta - Part A: Molecular and Biomolecular Spectroscopy
    View all citing articles on Scopus

    Bogdan Raducanu received the B.Sc. degree in computer science from the University “Politehnica” of Bucharest, Bucharest, Romania, in 1995 and the Ph.D. degree “Cum Laude” from the University of the Basque Country, Bilbao, Spain, in 2001. Currently, he is a senior researcher at the Computer Vision Center in Barcelona, Spain. His research interests are: computer vision, pattern recognition, machine learning, artificial intelligence, social computing and human–robot interaction. He is the author or co-author of about 60 publications in international conferences and journals. In 2010, he was the leading Guest Editor of Image and Vision Computing journal for a special issue on ‘Online Pattern Recognition’.

    Fadi Dornaika received the Ph.D. in signal, image, and speech processing from the Institut National Polytechnique de Grenoble, France, in 1995. He is currently an Ikerbasque research professor at the University of the Basque Country. He has published more than 130 papers in the field of computer vision. His research concerns geometrical and statistical modelling with focus on 3D object pose, real-time visual servoing, calibration of visual sensors, cooperative stereo-motion, image registration, facial gesture tracking, and facial expression recognition.

    View full text