Information Technology Reference

In-Depth Information

Fig. 3.35
The Swiss-roll data set, illustrating how Isomap exploits geodesic paths for nonlinear

dimensionality reduction.
Straight lines
in the embedding (the
blue
line in part
a
) now represent

simpler and cleaner approximations to the true geodesic paths than do the corresponding graph

paths (the
red
line in part
b
) (Reproduced from Tenenbaum et al. (
2000
)Fig.3.
http://www.

approximation is to transform a non-linear data into many smaller linear data and

then re-construct a global solution from local solutions of linear structures. Both

algorithms explained below are tested on a Swiss-roll-like non-linear data structure

of 20,000 data points.

The Isomap algorithm extracts meaningful dimensions by measuring the distance

between data points along the surface (Tenenbaum et al.
2000
). Isomap works best

for shapes that can be flattened out, like cylinders or Swiss rolls. Isomap measures

the distance between any two points on the shape, then uses these geodesic distances

in combination with the classic MDS algorithm in order to make a low dimensional

representation of that data. Figure
3.35
demonstrates how Isomap unfolds data

shaped like a Swiss roll.

In the Isomap algorithm, the local quantities computed are the distances between

neighboring data points. For each pair of non-neighboring data points, Isomap finds

the shortest path through the data set connecting them, subject to the constraint

that the path must hop from neighbor to neighbor. The length of this path is

an approximation to the distance between its end points, as measured within the

underlying manifold. Finally, the classical method of MDS is used to find a set

of low-dimensional points with similar pairwise distances. The Isomap algorithm

worked well on several test data, notably face images with three degrees of freedom,

up-down pose, left-right pose, and lighting direction (Fig.
3.36
) and hand images

with wrist rotation and finger extension as two degrees of freedom (Fig.
3.37
). In

other words, the true dimension of the face image data is 3 and that of the hand data

is 2. The residual variance of Isomap drops faster than PCA and MDS, which means

that PCA and MDS tend to overestimate the dimensionality, in contrast to Isomap

(Tenenbaum et al.
2000
).

3.3.5

Locally Linear Embedding

The Locally Linear Embedding (LLE) algorithm uses linear approximation to model

a non-linear manifold (Roweis and Saul
2000
). It is like using a lot of small pieces

Search WWH ::

Custom Search