Mapping Associations - Mapping Scientific Frontiers: The Quest for Knowledge Visualization - page 125

Fig. 3.36 Face images varying in pose and illumination (Fig. 1A) (Reprinted from Tenenbaum
et al. 2000 )
of two-dimensional planes to patch up a three-dimensional sphere. Cartographers
use similar techniques when they transform the spherical surface of the earth to a
flat map and the mapping must preserve the local relationships between places.
The LLE algorithm divides a set of high-dimensional data into small patches
that each can be easily flattened. These flattened small patches are reassembled in a
lower dimensional space, but the relative positions of data points within each patch
are preserved as much as possible.
LLE computes the best approximation of each data point by a weighted linear
combination of its neighbors. Then the algorithm finds a set of low-dimensional
points, each of which can be linearly approximated by its neighbors with the
same coefficients that were determined from the high-dimensional data points. Both
Isomap and LLE produce impressive results on some benchmark artificial data sets,
as well as on “real world” data sets. Importantly, they succeed in learning nonlinear
manifolds, in contrast to algorithms such as PCA, which has no built-in mechanism
to detect geodesic distances along a non-linear structure in a high-dimensional
space. Figure 3.38 shows how LLE unfolds the Swiss roll data.
Both Isomap and LLE algorithms introduce some distortions of the data, espe-
cially for more complicated shapes that include curves. The different approaches
may prove to be better or worse for different types of data. Isomap, based on