Out-of-Sample Extensions for LLE, Isomap, MDS, Eigenmaps, and Spectral Clustering

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

1,157 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Deep Metric Learning via Lifted Structured Feature Embedding (2015, background): “In this regard, metric learning [13, 39, 34] and dimensionality reduction [18, 7, 29, 2] techniques aim at learning semantic distance measures and embeddings such that similar input objects are mapped to nearby points on a manifold and dissimilar objects are mapped apart from each other.”
Spectral Inference Networks: Unifying Deep and Spectral Learning (2018, methodology): “Typically, the eigenfunctions of interest are approximated from a ﬁxed number of points small enough to be stored in memory, and then the value of the eigenfunction at other points is approximated by use of the Nystr¨om method (Bengio et al., 2004).”
Unsupervised Learning of Image Manifolds by Semidefinite Programming (2004, background): “Other directions for future work include the investigation of image manifolds with different topologies [13] (such as those isometric to low dimensional spheres or torii), the extrapolation of results to out-of-sample inputs [2], and the relation of SDE to kernel methods for nonlinear dimensionality”
SpectralNet: Spectral Clustering using Deep Neural Networks (2018, background): “Moreover, generalizing a spectral embedding to unseen data points, a task commonly referred to as out-of-sample-extension (OOSE), is a non-trivial task; see, for example, (Bengio et al., 2004; Fowlkes et al., 2004; Coifman & Lafon, 2006b).”
Locally Consistent Concept Factorization for Document Clustering (2011, background): “This is commonly referred as the out-of-sample extension issue [3].”
Learning a kernel matrix for nonlinear dimensionality reduction (2004, methodology): “The first is to develop faster and potentially distributed (Biswas & Ye, 2003) methods for solving the instance of semidefinite programming in SDE and for out-of-sample extensions ( Bengio et al., 2004 ).”
Large-Scale Multi-View Spectral Clustering via Bipartite Graph (2015, methodology): “They either rely on approximation of eigenfuncions (Fowlkes et al. 2004; Bengio et al. 2004) or data projection such as error correcting output code (ECOC) method Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence”
Dimensionality Reduction by Learning an Invariant Mapping (2006, background): “in [3], but they too rely on a predetermined computable distance metric.”
Local Manifold Learning-Based $k$ -Nearest-Neighbor for Hyperspectral Image Classification (2010, methodology): “The kernel-based out-of-sample extension method mitigates this problem [23], [24].”
A Spectral Approach to Gradient Estimation for Implicit Distributions (2018, methodology): “Connection to Manifold-modeling Dimension Reduction Methods It has been pointed out in previous works (Williams, 2001; Ham et al., 2004; Bengio et al., 2004a;b) that many successful manifold-modeling dimen-sion reduction methods (e.g., MDS, LLE, Laplacian eigen-maps, and Spectral clustering) can be…”
Local and Global Regressive Mapping for Manifold Learning with Out-of-Sample Extrapolation (2010, methodology): “According to the specific algorithmic procedures of manifold learning algorithms, Bengio et al. have defined a data dependent kernel matrix K for ISOMap, LLE and LE, respectively (Bengio et al. 2003).”
Survey on distance metric learning and dimensionality reduction in data mining (2014, methodology): “For the methods getting embedding coordinates directly (e.g., Isomap, LLE, LE), we need additional efforts to make them extensible Bengio et al. (2004).”
Distance Metric Learning: A Comprehensive Survey (2006, methodology): “[47] have presented an extension to five unsupervised learning algorithms based on a spectral embedding of the data: MDS, spectral clustering, Laplacian eigenmaps, ISOMAP and LLE.”
Trace optimization and eigenproblems in dimension reduction methods (2011, methodology): “In [6] an inﬁnite dimensional operator was used as a means to deﬁne out-of-sample extensions of various non-linear methods.”
Low-Shot Learning with Large-Scale Diffusion (2017, methodology): “, in [7] and [20], in the speech domain, in this work, we use a weighted sum of nearest neighbors from the (perhaps unlabeled) training data [4].”
Geometric harmonics: A novel tool for multiscale out-of-sample extension of empirical functions (2006, methodology): “X. This technique is inspired from the Nystrom method, widely used in partial differential solvers, and recently employed in machine learning and in spectral graph theory as a way to subsample large data sets [ 3 ,9,13].”
Learning Eigenfunctions Links Spectral Embedding and Kernel PCA (2004, methodology): “Something interesting about this kernel is that when c → ∞, the embedding obtained for a new point x converges to the extension of LLE proposed in Saul and Roweis (2002), as shown in Bengio et al. (2004) (this is the kernel we actually used in the experiments reported here).”
Representation Learning: A Review and New Perspectives (2012, methodology): “Distributed representations for symbolic data were introduced by Hinton (1986), and first developed in the context of statistical language modeling by Bengio et al. (2003) in so-called neural net language models (Bengio, 2008).”