The problem of dimensionality reduction arises in many fields of information processing. It poses a particular challenge to researchers attempting to build machines that emulate feats of human perception, such as recognizing faces and understanding speech. Our mental representations of these stimuli are formed by processing vast numbers of sensory inputs. We see objects from the billions of photons impinging on our retinae; we hear them from the tiny vibrations of our ear drums. How do we manage all this information, and how can we build machines with similar capabilities?

In this talk, I will describe locally linear embedding (LLE), an unsupervised learning algorithm that computes low dimensional, neighborhood preserving embeddings of high dimensional data. The data, assumed to lie on a nonlinear manifold, is mapped into a single global coordinate system of lower dimensionality. The mapping is derived from the symmetries of locally linear reconstructions, and the actual computation of the embedding reduces to a sparse eigenvalue problem. Notably, the optimizations in LLE -- though capable of generating highly nonlinear embeddings -- are simple to implement, and they do not involve local minima. I will illustrate the algorithm's performance on several different types of data, including images of faces, word-document counts, and points sampled from the surfaces of two dimensional manifolds.

(Joint work with Sam Roweis, University of Toronto)