4
$\begingroup$

I have started using the UMAP method for dimension reduction which is a similar method to t-SNE, Diffusion Maps, Laplacian Eigenmaps, etc.

The named dimension reduction methods have in common that they are non-parametric, i.e. there is no easy straightforward way to embed new data.

In the UMAP package for python and R, however, such an embedding for new data is possible.

During my research I could not find any source describing how these predictions are generated. I have read through the UMAP paper.

Does anyone know how UMAP predictions are generated in the package from a mathematical point of view?

$\endgroup$
8
$\begingroup$

Great question. I will answer it using t-SNE because I assume it is familiar to more people. I think UMAP is very promising and is a great contribution but to be honest I am getting a little bit annoyed with all the marketing and the hype that surrounds it. People think that t-SNE cannot embed new points but UMAP miraculously can. In reality, t-SNE can do it just as well as UMAP can; it is just a matter of convenient implementation.

A figure to attract attention:

enter image description here


they are non-parametric, i.e. there is no easy straightforward way to embed new data

This is not quite correct. It is true that t-SNE is non-parametric. What this actually means is that t-SNE does not construct a function $f(x):\mathbb R^p\to \mathbb R^2$ that would map high-dimensional points $x$ down to 2D. Instead it positions all the points on a plane and lets them "interact": similar points attract each other and dissimilar points repel each other, and after a while similar points gather together in clusters. In practical implementations, each point only feels attraction from its nearest $k$ neighbours for some small value of $k$.

Now imagine you get a new point $x_\mathrm{test}$. There is no function $f()$ that would give you its 2D position as $f(x_\mathrm{test})$. However, you can put it somewhere in the existing t-SNE embedding and let it "interact" with all existing points: it will be attracted to the points most similar to it (its nearest neighbours) and repeled from all other points. Only this point is allowed to move, while all existing points remain in place. If everything works well, $x_\mathrm{test}$ will arrive to its place somewhere close to its nearest neighbours.

When actually doing it, it is very helpful to position it initially somewhere close to its nearest neighbours (e.g. mean location of its $k$ nearest neighbours), because this will make the convergence much faster and much more reliable. In fact, simply positioning it at the mean location of its $k$ nearest neighbours can already work so well that no further optimisation would be needed at all.

[As an aside: if one has a whole bunch of test points, then one can deal with them independently one by one, or try to embed them all together and let them interact between each other as well. This can have very different outcomes if all test points are similar to each other but dissimilar to the original points. In the former case the test points will be "forced" into the existing embedding. In the latter case they will gather together as a separate cluster.]

I know several biology papers that used some variation of this method. Berman 2014 and Macosko 2015 are two such examples. Here is a very nice and very fast recent Python implementation of t-SNE https://github.com/pavlin-policar/openTSNE that allows embedding of new points out of the box. To quote the documentation https://opentsne.readthedocs.io/en/latest/,

[t-SNE has had several criticisms over the years, one of which is that] t-SNE is nonparametric therefore it is impossible to add new samples to an existing embedding. This argument is often repeated and likely comes from the fact that most software packages simply did not take the time to implement this functionality. t-SNE is nonparametric meaning that it does not learn a function $f$ that projects samples from the ambient space into the embedding space. However, the objective function of t-SNE is well defined and new samples can easily be added into an existing embedding by taking a data point and optimizing its position with respect to the existing embedding. This is the only available implementation we know of that allows adding new points to an existing embedding.

The figure above is from https://github.com/berenslab/rna-seq-tsne/ which is a companion repository to this preprint: https://www.biorxiv.org/content/10.1101/453449v1.


Regarding UMAP, as you say, the math behind the test set embeddings is not explicitly described anywhere, but I am quite sure that this is what it does. Briefly looking at the source code seems to confirm it.

$\endgroup$
  • 2
    $\begingroup$ +1 (Zero upvotes so far? Damn this community has high standards.) Regarding the fact that $t$-SNE did not natively embedded new points: I think that this is/was a clear problem. I hope that the implementation variant(s) that allow for new points to be added gain traction and/or the native implementation is extended to allow this; it was huge short-coming of the original implementation. $\endgroup$ – usεr11852 Mar 22 at 9:20
  • $\begingroup$ Thanks. But what do you mean by "native implementation"? The original C++ Barnes-Hut implementation by van der Maaten? That's I think what is still most often used, thanks to various wrappers. Not sure if Matlab's implementation is also just a wrapper or is a full Matlab re-implementation. Scikit version is a pure Python re-implementation, I think (?). In any case, there is no reason to use Barnes-Hut anymore, now that there is FI approximation (of FIt-SNE). I think there are only two implementations of FIt-SNE: the original C++ code with wrappers and pure Python/numba openTSNE. $\endgroup$ – amoeba Mar 22 at 10:56
  • 1
    $\begingroup$ I strongly suspect that too... As mentioned hopefully some new-point-embedding-capable variant will get a substantial share. $\endgroup$ – usεr11852 Mar 22 at 11:34
  • 1
    $\begingroup$ @amoeba, thanks for this extensive answer and explanations! So is what you are saying the following? Given the low-dimensional embedding of the dataset $D$, we choose the low-dimensional embedding $y_{test}$ for $x_{test}$ as the minimizer of the loss function $L$ of the dimension reduction method: $y_{test} = \text{argmin}_y ( L(D \cup \{y\}))$ $\endgroup$ – L D Mar 22 at 14:38
  • 1
    $\begingroup$ @LD Yes, I think this is correct and I like this way of putting it. I might edit it into my answer :-) There is a little caveat here though because tSNE (and also UMAP) "symmetrize" the similarities between points, but when embedding a $x_\mathrm{test}$ one would usually just take similarities from it to all training-set points without "symmetrization". But I guess one can still take your formula a general definition and this lack of symmetrization is more of a trick to make it computationally simpler. $\endgroup$ – amoeba Mar 23 at 22:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.