Out-of-Sample Extensions

Since most spectral dimensionality reduction techniques do not provide a solution to the out-of-sample extension problem out of the box , numerous methods have been presented to enable new points to be incorporated into a previously learnt embedding. These methods can be broadly split into those that work for a specific spectral dimensionality reduction technique, and those that are generic enough to work with any spectral dimensionality reduction technique. 

---

Keywords Out-of-sample extension Pre-image Nystrdm method learning... 

Perhaps the most well known algorithm specific out-of-sample estimation method is that of Bengio et al. [6] where the problem of spectral dimensionality reduction is phrased within a kernel framework so that the Nystrom technique can be used to perform the out-of-sample extension. 

A large value of /u. should be used so that the above formulation approximates the out-of-sample extension given by Saul and Roweis [13] that is discussed in more detail below. 

Fig. 5.1 A toy case where the out-of-sample extension methods described in Sect. 5.2.2 would fail to work...

Although numerous solutions to the out-of-sample extension problem have been presented, there are common problems that run throughout the solutions. Firstly, for techniques such as GOoSE [16] and non-parametric LLE [13] that utilise the original high-dimensional data, it is assumed that this data is available this may not always be the case however. It is conceivable that the data, for whatever reason, is not available and so such methods will not be useable. As well as this, these methods make a fundamental assumption about the unseen data points that may not always be the case and is also difficult to verify. Such methods assume that the new data points lie within the previously seen data. That is, the manifold is well sampled around the new data point x. As an example of this consider the cases shown in Fig. 5.1. In this example, the manifold is well sampled around x and so x can be reasonably reconstructed from its nearest neighbours. In this instance methods such as those described in Sect. 5.2.2 will perform well. However, in the example shown in Fig. 5.1 for the point z this will not be the case. Although z is sampled from... 

Numerous potential solutions to the pre-image problem have been presented [21-24] but the one of particular interest is that of Arias et al. [18] as they provide a direct link between the Nystrdm extension for the out-of-sample extension problem, and the pre-image problem. As such, this method fits into the Nystrom framework described in Sect. 5.2.1. 

The pre-image can suffer from similar drawbacks to the out-of-sample extension, namely the pre-image lying far away from the previously observed manifold. This problem can be partially overcome by providing a normalisation as with the above described method whereby y is projected onto the unit sphere [18]. 

A closely related problem to that of the out-of-sample extension problem is incremental learning where the low-dimensional embedding is learnt incrementally rather than in batch. Incremental learning has obvious advantages over batch learning, for example, many real world datasets cannot be learnt using a batch learning approach... 

As with the out-of-sample extension problem, providing an incremental version of LLE is a difficult task as LLE does not have a clear interpretation in terms of distances or dot products [6]. One solution to the problem, Iterative LLE (ILLE) [31], follows the same steps as the original LLE algorithm (Sect. 2.3.4) but with a different eigen decomposition step. 

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... 

Strange, H., Zwiggelaar, R. A generalised solution to the out-of-sample extension problem in manifold learning. In Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence, pp. 471-476 (2011)... 

---