UMAP

Definition

Uniform manifold approximation and projection (UMAP) is a nonlinear dimensionality reduction algorithm similar to t-SNE. However, unlike to t-SNE, UMAP uses spectral embedding to initialize the low-dimensional graph, and uses a graph that only connected to each points’ nearest neighbors.

Algorithm

1. For each point in high-dimensional space, find its nearest neighbors.

2. Compute the distances between the nearest neighbors for each point.

$d(x_i,x_j)$

3. Calculate the local connectivity parameter ${\sigma }_i$ for each point using the equation $\sum _{j=1}^k\exp \left(-\frac{\max (0,d(x_i,x_j)-{\rho }_i)}{{\sigma }_i}\right)={\log }_2(k)$ where $k$ is the number of nearest neighbors, and ${\rho }_i$ is the minimum distance among the nearest neighbors

4. Calculate the edge weights to the nearest neighbors and symmetrize the graph

$v_{i|j}=\exp \left(-\frac{\max (0,d(x_i,x_j)-{\rho }_i)}{{\sigma }_i}\right)$ $v_{ij}=v_{ji}=v_{i|j}+v_{j|i}-v_{i|j}{v}_{j|i}$

5. Initialize the low-dimensional representation using spectral embedding.

6. optimize the low-dimensional representation by minimizing both the attractive and the repulsive force using SGD.

The cost function is defined as ${\sum }_{e\in E}\left[\underset{\text{attractive force}}{\underbrace{w_h(e)\log \left(\frac{w_h(e)}{w_l(e)}\right)}}+\underset{\text{repulsive force}}{\underbrace{(1-w_h(e))\log \left(\frac{1-w_h(e)}{1-w_l(e)}\right)}}\right]$ where $E$ is the set of edges, and $w_h(e)$ and $w_l(e)$ are the weights of the edge of the high-dimensional and low-dimensional graph respectively.