Uniform Manifold Approximation and Projection for Dimension Reduction

Uniform Manifold Approximation and Projection for Dimension Reduction

Uniform Manifold Approximation and Projection for Dimension Reduction (UMAP) is a non-linear dimensionality reduction method developed by Leland McInnes, John Healy and James Melville. Since its publication in 2018, it has become a widely used method for dimensionality reduction and visualisation of high-dimensional data across numerous fields of research. UMAP is a manifold-learning algorithm that employs insights from category theory and topological data analysis

Manifold Hypothesis & Intuition

Like other manifold-learning methods, UMAP uses the hypothesis that most real-world data sets sampled from some n-dimensional Euclidean space ${\mathbb{ℝ}}^N$, in fact, lie on a d-manifold ${ℳ}$ embedded into ${\mathbb{ℝ}}^N$. In particular, even if the dimension of the ambient space ${\mathbb{ℝ}}^N$ is large, the dimension of the manifold ${ℳ}$ will typically be small. UMAP endeavours to find such a manifold that approximates a given sample well and embed it into a low-dimensional Euclidean space.

Formally, UMAP assumes we are given a sample $X=\{x_1,...,x_n\}\subset {\mathbb{ℝ}}^N$ which lies on a Riemannian-d-manifold $({ℳ},g)$ embedded into ${\mathbb{ℝ}}^N$. While the embedding ${ℳ}\hookrightarrow {\mathbb{ℝ}}^N$ must be continuous, it need not be an isometry with respect to the Euclidean metric. Crucially, it is assumed that $x_1,...,x_n\in {\mathbb{ℝ}}^N$ have been sampled from the uniform distribution with respect to the volume form associated with the (possibly unknown) Riemannian metric $g$.

The UMAP algorithm first infers $g$ and then approximates ${ℳ}$ at changing resolutions using a sequence of simplicial sets. The algorithm projects the sequence of simplicial approximations into a low-dimensional Euclidean space ${\mathbb{ℝ}}^m$, where $m\ll N$ is user-defined. The projection to low-dimensional space is optimised such that it minimises the difference between the Euclidean metric and $g$. As the points $x_1,...,x_n$ can be mapped to the vertices of the projected simplicial sets, the algorithm yields a dimensionality reduction of the high-dimensional sample.

Theoretical Foundations

McInnes et al. use so-called fuzzy simplicial sets, a notion from category theory which generalises the notion of a simplicial set, to formalise the theoretical foundations of their algorithm. Fuzzy simplicial sets are related to filtrations of a simplicial complex, a construction widely used in topological data analysis and persistent homology. Both a simplicial set and a simplicial complex can be viewed as combinatorial descriptions of a manifold. McInnes et al. describe the operations of building a simplicial approximation of a Riemannian manifold $({ℳ},g)$ from a finite sample and embedding the vertices of a fuzzy simplicial set in a metric space as two functors. By proving that their two functors are adjoint, they show that their proposed embedding gives an optimal reconstruction of the metric structure of $({ℳ},g)$.

Algorithm

Construction of Neighbourhood Graph

The UMAP algorithm itself uses a $k$-nearest-neighbour graph ($k$-nn graph) on a finite pseudo-metric space $(X,d)$, which is a special case of a fuzzy-simplicial set. Let the $k$-nn graph $G$ have vertices $X$ and directed edges $E$. For fixed $x\in X$, define ${\rho }_x=\min \{d(x,x^{\prime })|(x,x^{\prime })\in E,d(x,x^{\prime })>0\}$ and ${\sigma }_x>0$ such that $$\sum _{(x,x^{\prime })\in E}\exp (-\frac{\max \{0,d(x,x^{\prime })-{\rho }_x\}}{{\sigma }_x})={\log }_2(k).$$

Each edge is then weighted by $\exp (-\max \{0,d(x,x^{\prime })-{\rho }_x\}/{\sigma }_x)$, resulting in a weighted adjacency matrix $A$. The $x,x^{\prime }$-entry of $A$ can then be interpreted as the probability of a directed edge from $x$ to $x^{\prime }$ existing. The directed, weighted graph is then turned into an undirected, weighted graph by setting its adjacency matrix to be $B=A+A^T-A\circ A^T,$ where $\circ$ denotes the Hadamard product (i.e. element-wise multiplication). The weight of an undirected edge in $B$ between $x$ and $x^{\prime }$ can then be interpreted as the edge existing in at least one direction in the graph determined by $A$.

Optimisation Algorithm

The neighbourhood graph $G$ is then embedded into low-dimensional Euclidean space ${\mathbb{ℝ}}^m$, i.e. each $x_i\in X$ is mapped to a $y_i\in Y\subset {\mathbb{ℝ}}^m$. By using stochastic gradient descent, UMAP optimises an embedding such that the weights of a neighbourhood graph constructed in the Euclidean norm in ${\mathbb{ℝ}}^m$ (by the same principles as above) are similar to the one constructed in high-dimensional space. As the sample $X$ is assumed to be uniform in the Riemannian metric $g$ and the embedding is aimed to be (near-)isometric, the parameters $\rho$ and $\sigma$ are assumed to be identical for all $y\in Y$. In particular, UMAP treats $\rho$ as a hyper-parameter, called min_dist, and sets $\sigma =1$.

A caveat to performing this optimisation directly by using stochastic gradient descent is that the function $\mathrm{\Psi }:{\mathbb{ℝ}}^m\times {\mathbb{ℝ}}^m\to [0,1]$ given by $\mathrm{\Psi }(y_i,y_j)=\exp (-\max \{0,\Vert y_i-y_j\Vert -\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{\_}\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}\})$ is not differentiable due to the use of the $\max$-condition. UMAP approximates $\mathrm{\Psi }$ by the function $\mathrm{\Phi }:{\mathbb{ℝ}}^m\times {\mathbb{ℝ}}^m\to [0,1]$ given by $\mathrm{\Psi }(y_i,y_j)={(1+a\Vert y_i-y_j{\Vert }^{2b})}^{-1}$, where $a$ and $b$ are obtained by a least-square fit against $\mathrm{\Psi }$. Unlike $\mathrm{\Psi }$, the function $\mathrm{\Phi }$ is differentiable and, therefore, has a well-defined gradient.

The stochastic gradient descent is then performed against $\mathrm{\Phi }$ and uses a spectral embedding as initialisation. The UMAP algorithm can thus be summarised as follows:

 1  function UMAP(X, k, m, min_dist, n_epochs, n_neg_samples):
 2      
 3      graph = knn_graph(X, k)  # undirected knn graph weighted as above
 4      y = spectral_embedding(graph, m)
 5      fit $\mathrm{\Phi }$ from min_dist
 6      alpha = 1.0
 7
 8      for e = 1,...,n_epochs:
 9          for all ([i,j], p) in graph.edges:
 10             if random() <= p:   # optimise the position of sample y_i with probability p
 11                 y[i] = y[i] + alpha * $\mathrm{\nabla }(\log (\mathrm{\Phi }))$(y[i], y[j])  # apply the attracting force of y_j to the position of y_i
 12                 for s = 1,...,n_neg_samples:
 13                     l = random_int(X.size())   #  Pick any sample at random. It is most likely NOT a neighbour of y_i
 14                     y[i] = y[i] + alpha * $\mathrm{\nabla }(\log (1-\mathrm{\Phi }))$(y[i], y[l])  # apply the repelling force of y_l to the position of y_i
 15
 16         alpha = 1.0 - e / n_epochs
 17
 18     return y

Software

The authors of UMAP implemented the UMAP algorithm in a Python package called umap-learn, which provides a class compatible with the scikit-learn machine learning package. It should be noted that umap-learn uses an approximate, randomised $k$-nn graph via the pynn-descent package. Some of the default parameter values in umap-learn include min_dist=0.1 and n_neg_samples=5.

The R package umap provides two implementations of the UMAP algorithm: one that has been implemented from scratch and one that calls the umap-learn Python package via an interface.

MATLAB provides an implementation in a package called Uniform Manifold Approximation and Projection (UMAP), which follows the Python implementation in umap-learn closely.

Further implementations are provided in Julia (UMAP.jl) and Java (umap-java), each being native implementations in the respective language.

References

This article "Uniform Manifold Approximation and Projection for Dimension Reduction" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Uniform Manifold Approximation and Projection for Dimension Reduction. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

---