Nonlinear dimensionality reduction
≈ 9 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
) with a rectangular hole in the middle. Top-right: the original 2D manifold used to generate the 3D dataset. Bottom left and right: 2D recoveries of the manifold respectively using the LLE and Hessian LLE algorithms as implemented by the Modular Data Processing toolkit. Nonlinear dimensionality reduction (NLDR), also known as manifold learning, is any of various related techniques that aim to project high-dimensional data, potentially existing across non-linear manifolds (non-affine subspaces) which cannot be adequately captured by linear decomposition methods, onto lower-dimensional latent manifolds, with the goal of either visualizing the data in the low-dimensional space, or learning the mapping (either from the high-dimensional space to the low-dimensional embedding or vice versa) itself. The techniques described below can be understood as generalizations of linear decomposition methods used for dimensionality reduction, such as singular value decomposition and principal component analysis.
) with a rectangular hole in the middle. Top-right: the original 2D manifold used to generate the 3D dataset. Bottom left and right: 2D recoveries of the manifold respectively using the LLE and Hessian LLE algorithms as implemented by the Modular Data Processing toolkit. Nonlinear dimensionality reduction (NLDR), also known as manifold learning, is any of various related techniques that aim to project high-dimensional data, potentially existing across non-linear manifolds (non-affine subspaces) which cannot be adequately captured by linear decomposition methods, onto lower-dimensional latent manifolds, with the goal of either visualizing the data in the low-dimensional space, or learning the mapping (either from the high-dimensional space to the low-dimensional embedding or vice versa) itself. The techniques described below can be understood as generalizations of linear decomposition methods used for dimensionality reduction, such as singular value decomposition and principal component analysis. C = \frac{1}{m}\sum_{i=1}^m{\mathbf{x}_i\mathbf{x}_i^\mathsf{T}}. It then projects the data onto the first k eigenvectors of that matrix. By comparison, KPCA begins by computing the covariance matrix of the data after being transformed into a higher-dimensional space, C = \frac{1}{m}\sum_{i=1}^m{\Phi(\mathbf{x}_i)\Phi(\mathbf{x}_i)^\mathsf{T}}. It then projects the transformed data onto the first k eigenvectors of that matrix, just like PCA. It uses the kernel trick to factor away much of the computation, such that the entire process can be performed without actually computing \Phi(\mathbf{x}) . Of course \Phi must be chosen such that it has a known corresponding kernel. Unfortunately, it is not trivial to find a good kernel for a given problem, so KPCA does not yield good results with some problems when using standard kernels. For example, it is known to perform poorly with these kernels on the Swiss roll manifold. However, one can view certain other methods that perform well in such settings (e.g., Laplacian Eigenmaps, LLE) as special cases of kernel PCA by constructing a data-dependent kernel matrix. KPCA has an internal model, so it can be used to map points onto its embedding that were not available at training time. E(W) = \sum_i \left|\mathbf{X}_i - \sum_j {\mathbf{W}_{ij}\mathbf{X}_j}\right|^2 The weights W ij refer to the amount of contribution the point X j has while reconstructing the point X i . The cost function is minimized under two constraints: Each data point X i is reconstructed only from its neighbors. That is, W_{ij} = 0 if point X j is not a neighbor of the point X i . The sum of every row of the weight matrix equals 1, that is, \sum_j {\mathbf{W}_{ij}} = 1 . These two constraints ensure that W is unaffected by rotation and translation. In the second step, a neighborhood preserving map is created based the weights. Each point X_i \in \R^D is mapped onto a point Y_i \in \R^d by minimizing another cost: C(Y) = \sum_i \left|\mathbf{Y}_i - \sum_j {\mathbf{W}_{ij}\mathbf{Y}_j}\right|^{2} Unlike in the previous cost function, the weights W ij are kept fixed and the minimization is done on the points Y i to optimize the coordinates. This minimization problem can be solved by solving a sparse N X N eigenvalue problem (N being the number of data points), whose bottom d nonzero eigen vectors provide an orthogonal set of coordinates. The only hyperparameter in the algorithm is what counts as a "neighbor" of a point. Generally the data points are reconstructed from K nearest neighbors, as measured by Euclidean distance. In this case, the algorithm has only one integer-valued hyperparameter K, which can be chosen by cross validation. Contagion maps use multiple contagions on a network to map the nodes as a point cloud. In the case of the Global cascades model the speed of the spread can be adjusted with the threshold parameter t \in [0,1] . For t=0 the contagion map is equivalent to the Isomap algorithm. Diffusion maps leverages the relationship between heat diffusion and a random walk (Markov Chain); an analogy is drawn between the diffusion operator on a manifold and a Markov transition matrix operating on functions defined on the graph whose nodes were sampled from the manifold. In particular, let a data set be represented by \mathbf{X} = [x_1,x_2,\ldots,x_n] \in \Omega \subset \mathbf {R^D} . The underlying assumption of diffusion map is that the high-dimensional data lies on a low-dimensional manifold of dimension \mathbf{d} . Let X represent the data set and \mu represent the distribution of the data points on X. Further, define a kernel which represents some notion of affinity of the points in X. The kernel \mathit{k} has the following properties k(x,y) = k(y,x), k is symmetric k(x,y) \geq 0\qquad \forall x,y, k k is positivity preserving Thus one can think of the individual data points as the nodes of a graph and the kernel k as defining some sort of affinity on that graph. The graph is symmetric by construction since the kernel is symmetric. It is easy to see here that from the tuple (X,k) one can construct a reversible Markov Chain. This technique is common to a variety of fields and is known as the graph Laplacian. For example, the graph K = (X,E) can be constructed using a Gaussian kernel. K_{ij} = \begin{cases} e^{-\|x_i -x_j\|^2_2/\sigma ^2} & \text{if } x_i \sim x_j \\ 0 & \text{otherwise} \end{cases} In the above equation, x_i \sim x_j denotes that x_i is a nearest neighbor of x_j . Properly, Geodesic distance should be used to actually measure distances on the manifold. Since the exact structure of the manifold is not available, for the nearest neighbors the geodesic distance is approximated by euclidean distance. The choice \sigma modulates our notion of proximity in the sense that if \|x_i - x_j\|_2 \gg \sigma then K_{ij} = 0 and if \|x_i - x_j\|_2 \ll \sigma then K_{ij} = 1 . The former means that very little diffusion has taken place while the latter implies that the diffusion process is nearly complete. Different strategies to choose \sigma can be found in. In order to faithfully represent a Markov matrix, K must be normalized by the corresponding degree matrix D : P = D^{-1}K. P now represents a Markov chain. P(x_i,x_j) is the probability of transitioning from x_i to x_j in one time step. Similarly the probability of transitioning from x_i to x_j in t time steps is given by P^t (x_i,x_j) . Here P^t is the matrix P multiplied by itself t times. The Markov matrix P constitutes some notion of local geometry of the data set X. The major difference between diffusion maps and principal component analysis is that only local features of the data are considered in diffusion maps as opposed to taking correlations of the entire data set. K defines a random walk on the data set which means that the kernel captures some local geometry of data set. The Markov chain defines fast and slow directions of propagation through the kernel values. As the walk propagates forward in time, the local geometry information aggregates in the same way as local transitions (defined by differential equations) of the dynamical system. The metaphor of diffusion arises from the definition of a family diffusion distance \{ D_t \}_{ t \in N} D_t^2(x,y) = \|p_t(x,\cdot) - p_t(y,\cdot)\|^2 For fixed t, D_t defines a distance between any two points of the data set based on path connectivity: the value of D_t(x,y) will be smaller the more paths that connect x to y and vice versa. Because the quantity D_t(x,y) involves a sum over of all paths of length t, D_t is much more robust to noise in the data than geodesic distance. D_t takes into account all the relation between points x and y while calculating the distance and serves as a better notion of proximity than just Euclidean distance or even geodesic distance.
See also
Manifold hypothesis Spectral submanifold Taken's theorem Whitney embedding theorem Discriminant analysis Elastic map Feature learning Growing self-organizing map (GSOM) Self-organizing map (SOM)
References
Further reading
External links
Isomap Generative Topographic Mapping Mike Tipping's Thesis Gaussian Process Latent Variable Model Locally Linear Embedding Relational Perspective Map DD-HDS homepage RankVisu homepage Short review of Diffusion Maps Nonlinear PCA by autoencoder neural networks
Text derived from https://en.wikipedia.org/w/index.php?oldid=1375372456 under CC BY-SA 4.0; modifications have been made.