| |
Nonlinear Dimensionality Reduction and Manifold Learning
Non-linear CCA and PCA by Alignment of Local Models
- In the same way that you can align local representations
of linear subspace models to get globally nonlinear models, you can
also align representations of linear input-output models such as
Canonical Correlation Analysis to get non-linear CCA.
A special case of our method, when applied to only a single manifold,
reduces to the Laplacian Eigenmaps algorithm.
- Jakob Verbeek, Nikos Vlassis and I had a paper entitled
Non-linear CCA and PCA by Alignment of Local Models
describing this work in NIPS 2003.
Automatic Alignment of Local Representations
- A big challenge when getting many experts to learn in concert is
to get their hidden representations to agree in some way.
In this paper, we
present an automatic alignment procedure which maps the disparate
internal representations learned by several local dimensionality reduction
experts into a single, coherent global coordinate system for the
original data space. Our algorithm can be applied to any set of
experts, each of which produces
a low-dimensional local representation
of a high-dimensional input. Unlike the Global Coordination
paper below (which coordinates models by modifying their objective
functions) our algorithm is invoked after training and applies
an efficient eigenmethod to post-process the
trained models. It has no local optima and the size of the system it
must solve scales with the number of local models rather than the
number of original data points, making it more efficient than
model-free algorithms such as Isomap or LLE.
- A paper on this work, with Yee Whye Teh:
Automatic Alignment of Local Representations
appeared in NIPS14.
Stochastic Neighbour Embedding
- Nonlinear dimensionality reduction algorithms can often be
formulated in terms of what they preserve about the original data.
Some, like PCA preserve variance, others, like MDS or Isomap large distances
(metric, nonmetric or geodesic), others like SOM or LLE preserve
nearby neighbours. In this paper
we describe a probabilistic approach to the task of embedding
high-dimensional objects into a low-dimensional space in a way that
preserves the *distribution of neighbor identities*.
A Gaussian is centered on each object in the
high-dimensional space and the densities under this Gaussian are used
to define a probability distribution over all the potential neighbors
of the
object. The aim of the embedding is to approximate this distribution
as well as possible when the same operation is performed in the
low-dimensional space. The natural cost function is a sum of
Kullback-Leibler divergences, one per object. This leads to a simple
gradient for adjusting the positions of objects in the low-dimensional
space. Unlike other dimensionality reduction methods,
this probabilistic framework makes it easy to represent
each high-dimensional object by a mixture of widely separated
low-dimensional points. This allows the embeddings of ambiguous
objects, like the document count vector for the word ``bank'', to be
close to the embeddings of both ``river'' and ``finance'' without
forcing outdoor concepts to be located close to corporate ones.
- As an example, here's a map of the NIPS
vols.0-12 authors as produced by the SNE algorithm.
- A paper on SNE, written with Geoff Hinton:
Stochastic Neighbor Embedding
appeared in NIPS14.
Global Coordination
- High dimensional data that lies on or near a low dimensional
manifold can be described by a collection of local linear models.
Such a description, however, does not provide a global
parameterization of the manifold---arguably an important goal
of unsupervised learning.
In this paper, we show how to learn a collection of local linear
models that solves this more difficult problem. Our local linear
models are represented by a mixture of factor analyzers, and the
``global coordination'' of these models is achieved by adding a
regularizing term to their objective function. The regularizer breaks
a degeneracy in the mixture model's parameter space, favoring models
whose internal coordinate systems are aligned
in a consistent way. As a result, the internal coordinates change
smoothly and continuously as one traverses a connected path on the % data
manifold---even when the path crosses the domains of many different
local models. The regularizer takes the form of a Kullback-Leibler
divergence and illustrates an unexpected application of variational
methods: not to perform approximate inference in intractable
probabilistic models, but to learn more useful internal
representations in tractable~ones.
- Our paper,
Global Coordination of Local Linear Models appeared in
NIPS13 (joint work with Lawrence Saul and Geoff Hinton).
Locally Linear Embedding (LLE)
-
Exploratory data analysis and visualization play an
increasingly important role in all areas of science.
The need to analyze large amounts of multivariate data
raises the fundamental problem of dimensionality reduction--how to
discover compact representations of high dimensional data. Here we
introduce locally linear embedding (LLE), an unsupervised learning
algorithm that is able to discover the global structure of nonlinear
manifolds. LLE uses local symmetries and linear reconstructions to
compute low dimensional, neighborhood preserving embeddings of
multivariate data. Applied to images of faces, LLE discovers a
coordinate representation of facial attributes; applied to documents
of text, it colocates--in a continuous semantic space--words with
similar contexts.
(with Lawrence Saul, AT&T Labs)
- A paper describing this
work appeared in the Dec22, 2000 issue of Science.
Here is a link to the
online version of the paper.
- A longer version
of the LLE paper is now available, which appeared in volume 4 of JMLR.
Learning nonlinear dynamics
[ |
Information |
Research |
Teaching |
Professional |
]
Sam Roweis, Vision, Learning and Graphics Group,
NYU, www.cs.nyu.edu/~roweis
|