Spectral Dimensionality Reduction

This file is part of IDEAS, which uses RePEc data

Spectral Dimensionality Reduction

Author Info

Yoshua Bengio
Olivier Delalleau
Nicolas Le Roux
Jean-François Paiement
Pascal Vincent
Marie Ouimet

Abstract

In this paper, we study and put under a common framework a number of non-linear dimensionality reduction methods, such as Locally Linear Embedding, Isomap, Laplacian Eigenmaps and kernel PCA, which are based on performing an eigen-decomposition (hence the name 'spectral'). That framework also includes classical methods such as PCA and metric multidimensional scaling (MDS). It also includes the data transformation step used in spectral clustering. We show that in all of these cases the learning algorithm estimates the principal eigenfunctions of an operator that depends on the unknown data density and on a kernel that is not necessarily positive semi-definite. This helps to generalize some of these algorithms so as to predict an embedding for out-of-sample examples without having to retrain the model. It also makes it more transparent what these algorithm are minimizing on the empirical data and gives a corresponding notion of generalization error.

Dans cet article, nous étudions et développons un cadre unifié pour un certain nombre de méthodes non linéaires de réduction de dimensionalité, telles que LLE, Isomap, LE (Laplacian Eigenmap) et ACP à noyaux, qui font de la décomposition en valeurs propres (d'où le nom "spectral"). Ce cadre inclut également des méthodes classiques telles que l'ACP et l'échelonnage multidimensionnel métrique (MDS). Il inclut aussi l'étape de transformation de données utilisée dans l'agrégation spectrale. Nous montrons que, dans tous les cas, l'algorithme d'apprentissage estime les fonctions propres principales d'un opérateur qui dépend de la densité inconnue de données et d'un noyau qui n'est pas nécessairement positif semi-défini. Ce cadre aide à généraliser certains modèles pour prédire les coordonnées des exemples hors-échantillons sans avoir à réentraîner le modèle. Il aide également à rendre plus transparent ce que ces algorithmes minimisent sur les données empiriques et donne une notion correspondante d'erreur de généralisation.

Download Info
To download:

If you experience problems downloading a file, check if you have the proper application to view it first. Information about this may be contained in the File-Format links below. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.

Publisher Info
Paper provided by CIRANO in its series CIRANO Working Papers with number 2004s-27.

Download reference. The following formats are available: HTML (with abstract), plain text (with abstract), BibTeX, RIS (EndNote, RefMan, ProCite), ReDIF
Length:
Date of creation: 01 May 2004
Date of revision:
Handle: RePEc:cir:cirwor:2004s-27

Contact details of provider:
Postal: 2020 rue University, 25e �tage, Montr�al, Qu�c, H3A 2A5
Phone: (514) 985-4000
Fax: (514) 985-4039
Email:
Web page: http://www.cirano.qc.ca/
More information through EDIRC

For technical questions regarding this item, or to correct its listing, contact: (Webmaster).

This paper has been announced in the following NEP Reports:

NEP-ALL-2004-06-07 (All new papers)
NEP-ECM-2004-06-10 (Econometrics)

Statistics

Access and download statistics

Did you know? You can use convenient plug-ins to search directly IDEAS from your browser.

This page was last updated on 2009-12-19.

This information is provided to you by IDEAS at the Department of Economics, College of Liberal Arts and Sciences, University of Connecticut using RePEc data on a server sponsored by the Society for Economic Dynamics.