Isomap

Isomap [2], one of the first true nonlinear spectral dimensionality reduction methods, extends metric MDS to handle nonlinear manifolds. Whereas metric MDS measures inter-point EucUdean distances to obtain a feature matrix. Isomap measures the interpoint manifold distances by approximating geodesics. The use of manifold distances can often lead to a more accurate and robust measure of distances between points so that points that are far away according to manifold distances, as measured in the high-dimensional space, are mapped as far away in the low-dimensional space (Fig. 2.3). An example low-dimensional embedding of the S-Curve dataset (Fig. 2.1) found using Isomap is given in Fig. 2.4. 

At the heart of Isomap is the computation of the manifold inter-point distances which is achieved by estimating the geodesic distances across a neighbourhood graph. The geodesic distance between two points is represented as Sy = p(Xi,Xj), where 

---

Figure 4 shows an isomap of the lead pollution in the first smelter area of the Dallas Lead Study. The round symbol in the center represents the smelter. The lines are isopleths of lead in soil in pg/g. Note the cluster of closed isopleths encircling the smelter. The large number of concentric isopleths encircling the smelter shows a steep gradient or rapid change in a short distance between a low (200 ig/g) outside and a high (3,000 pg/g) inside. 

A recently introduced algorithm, called stochastic proximity embedding (SPE), is a novel self-organizing scheme that addresses the key limitations of Isomap (isometric feature mapping) and LLE. SPE builds on the same geodesic principle first proposed and exploited in Isomap, but introduces two algorithmic advances SPE circumvents the calculation of estimated geodesic distances, and uses a pairwise refinement scheme that does not require the complete distance, or proximity, r, matrix. Due to these advances, the method scales linearly with the number of points. 

V. Spiwok and B. Kralova,/. Chem. Phys., 135(22), 224504 (2011). Metadynamics in the Conformational Space Nonhnearly Dimensionally Reduced by Isomap. 

It is this similarity matrix that distinguishes various spectral dimensionality reduction techniques. For example, F could measure the covariance of X as in Principal Components Analysis [1], or the geodesic interpoint distances as in Isomap [2]. 

Fig. 2.4 Example 2-dimensional embeddings of the S-Curve dataset found by Isomap with = 12...

Although results show that both methods can find an optimal value of k for Isomap and LLE they do both require the spectral dimensionality reduction techniques to be run multiple times over the range of parameters, a potentially costly procedure (as discussed in Chap. 6). As well as this, it is assumed that the residual variance is a good measure of the optimality of an embedding. This may of course not always be the case and so both techniques are not so much techniques for finding the optimal parameter values for Isomap and LLE, but rather they are techniques that find the optimal parameter values to minimise the residual variance. 

The neighbourhood around a point Xj is then iteratively built by adding another point Xj if and only iiOj <6 and (I — QiQf)(Xy — Xj) p < f Xi). Although this method may overcome some of the shortcomings of the parameterless Isomap method, it is not without its own problems. For example, it relies on an angle threshold, 9 that must be supplied, as weU as a relaxation factor, f, that, although can be computed automatically, comes at an extra computational cost. 

Fig. 3.4 The low-dimensional embedding of the MNIST digit 0 was found using Isomap (k =...

Samko, O., Marshall, A.D., Rosin, R Selection of the optimal parameter value for the Isomap algorithm. Pattern Recognition Letters 27(9), 968-979 (2006)... 

Mekuz, N., Tsotsos, J.K. Parameterless Isomap with adaptive neighborhood selection. In Deutsche Arbeitsgemeinschaft fiir Mustererkennung DAGM, pp. 364-373 (2006)... 

The method to extend Isomap to incorporate a new point proposed in [6] does not explicitly recompute the geodesic distances with respect to the new point. Rather, the geodesic distances cj) (a, b) over the original data X are used and the j-th co-ordinate of the low-dimensional representation of an unseen point x is given by... 

The Incremental Isomap algorithm [28] seeks to provide an efficient solution to the incremental learning problem when using the Isomap algorithm. Incremental... 

Isomap has three main steps recomputing the geodesic distances obtaining the lowdimensional representation of the new points and updating the low-dimensional embedding. 

Bengio, Y, Paiement, J.F., Vincent, P., Delalleau, O., Roux, N.L., Ouimet, M. Out-of-sample extensions for LLE, Isomap, MDS, Eigenmaps, and Spectral Clustering. In Advances in Neural Information Processing Systems 15 Proceedings of the 2003 Conference (NIPS), pp. 177-184... 

To obtain a low-dimensional embedding using Isomap, three steps are followed a fc-nearest neighbour graph is built the shortest path matrix of the neighbourhood graph is computed Anally, eigendecomposition of the shortest path matrix is computed. As such, the computational complexity of each of these parts are considered separately before an overall complexity for Isomap can be obtained. 

---