Hi @lmcinnes,
There has been quite an exciting about UMAP in scRNA-Seq area recently. However, fitting larger data-sets might be an issue depending on amount of available memory. I would love to see a 'partial_fit' method (akin to one available in scikit's incremental PCA) in UMAP, so that data could be lazily loaded and fitted. I do realize that this might be non-trivial, if not theoretically infeasible, but your recent implementation of 'transform' method got my hopes high. It would be nice to have your thoughts on this.
Thanks.
parashardhapola
All 17 comments
If I understand you correctly you want essentially an "out-of-core" fit method that doesn't require the whole dataset to be in memory at one time?
I believe that this is possible, but would likely be slow. Essentially what is really needed is a fast, out-of-core, approximate nearest neighbor algorithm. I believe what I have now may actually work with dask arrays which would provide out-of-core, but for the fact that check_array converts it to an array at the start, and modulo how numba handles dask (I suspect it doesn't). In other-words I think this is algorithmically quite tractable, but might require a fair amount of code to actually make it happen.
If there is significant interest in this (and it seems there may be) I'll see if I can figure out how to actually make this happen.
lmcinnes
on 30 Apr 2018
Yes indeed, I'm looking for an out-of-core fit method and I'm sure that it would be of interest to many.
Pardon me if this is a very naive suggestion but I was thinking that may be this functionality can initially be implemented downstream of distance calculation. Such that, in effect, a user needs to provide a generator which yields distance vector for each sample (of shape m for an m x m distance matrix), instead of complete pre-computed matrix itself. This may avoid, for now, the requirement of an out-of-core ANN algorithm.
parashardhapola
on 30 Apr 2018
Essentially what is really needed is a fast, out-of-core, approximate nearest neighbor algorithm.
Is this what we were working on during the SciPy sprints on some branch/fork https://github.com/lmcinnes/pynndescent? I'd like to see the code – I'm curious what progress has been made, and would be happy to help out more.
stsievert
on 18 Jul 2018
Yes, that's the one. I got basic code hammered out, but hadn't fixed all the bugs. I also chatted with Matt Rocklin and it looks like the proposed solution would be quite slow due to the random(ish) access of a large distributed array required. Still, slow but tractable is better than impossible.
lmcinnes
on 18 Jul 2018
it looks like the proposed solution would be quite slow due to the random(ish) access of a large distributed array required.
I believe that. I sounds like the proposed solution will be enabled by https://github.com/dask/dask/issues/3409.
Is there anywhere I can review the code you've implemented?
stsievert
on 18 Jul 2018
I didn't get it working to a point of pushing it up anywhere. I have a
colleague who may be picking up this work, so I might try and loop him in
with all of this on Monday.
On Wed, Jul 18, 2018 at 5:22 PM Scott Sievert notifications@github.com
wrote:
it looks like the proposed solution would be quite slow due to the
random(ish) access of a large distributed array required.I believe that. I sounds like the proposed solution will be enabled by
dask/dask#3409 https://github.com/dask/dask/issues/3409.Is there anywhere I can review the code you've implemented?
—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/lmcinnes/umap/issues/62#issuecomment-406078490, or mute
the thread
https://github.com/notifications/unsubscribe-auth/ALaKBaibBPDXe0VsSWXNDl6qUba2nyejks5uH6b6gaJpZM4Ts6Gq
.
lmcinnes
on 20 Jul 2018
On the dask side I think that https://github.com/dask/dask/issues/3409#issuecomment-405254656 is probably the next step to try (assuming I understand the situation on the UMAP side (which is doubtful)) :)
mrocklin
on 20 Jul 2018
Really looking forward to it! Computer vision domain would benefit quite a lot from an out-of-core implementation.
soupault
on 25 Jun 2019
Was there something already released for this? I am also looking for the same for acoustic deep learning purpose. I am looking for using UMAP over some TB of data.
ksangeeta2429
on 30 Aug 2019
Currently this is still, at best, an "in the works" issue. The first real hurdle to be overcome, the nearest neighbor search, is looking good. There is a paralllel NN search, and there is reasonable hope to make a few more changes to ensure it is dask enabled for distributed arrays -- this has all been put the the PyNNDescent library, which will become a dependency for umap in the future. The next step is distributed SGD. This is easier, but has had less work done. Speculatively I would suggest that these are features that may arrive in version 0.5. Note, of course, that 0.4 is not even released yet. I suspect that means you may have to use subsampling for your project now. In good news the structures found my umap are generally fairly robust to subsampling.
lmcinnes
on 30 Aug 2019
next step is distributed SGD.
https://github.com/dask/dask/issues/3409 is related (and mentioned above). It kept popping up in my Dask distributed SGD implementation (https://github.com/dask/dask-glm/pull/69).
https://github.com/dask/dask/pull/3901 resolves this issue (thanks to @TomAugspurger). Now, shuffling to a distributed Dask array is much quicker (~100x improvement, 13.7s vs 140ms).
stsievert
on 30 Aug 2019
would really like to see the incremental training feature for UMAP. I work with both image and text data, UMAP easily generates the best manifold with the least amount of tuning compared to everything else I've tried in both categories.
teenoc
on 11 Dec 2019
At present it looks like this is something that might be possible in the v0.5 to v0.6 time-frame. That's not soon, but it may yet happen.
lmcinnes
on 11 Dec 2019
I am writing to mention that I am very interested in this.
natemccoy
on 31 Jan 2020
A possible method to do a large scale nearest neighbor search efficiently would be to use something like k-d trees or this. I had attempted this a while ago and found that it works for lower dimensional data like vgg16. I tried to use it on some very high dimensional genomics applications and had no luck.
I’ll try to dig up this code or my notes on this.
ghost
on 19 Apr 2020
Would be happy to see this incremental UMAP feature!
galinaalperovich
on 3 May 2020
Depending on what exactly you are looking for, this may now be available (in preliminary form) in the 0.5dev branch. To make it work you would use the new, special, AlignedUMAP class, and the update functionality therein. I have a notebook gist that provides a basic walkthrough of these sorts of features. With this approach if your goal is to incrementally add (batches) of new points to an existing embedding, updating the embedding as you go, this should suffice. It may not meet all of your needs, but hopefully it will solve some problems for some users.
lmcinnes
on 3 May 2020
Related issues
Cristianasp
·
4Comments
gabritaglia
·
5Comments
ensonario
·
7Comments
davisidarta
·
5Comments
MichaelMonashev
·
3Comments
Most helpful comment
Depending on what exactly you are looking for, this may now be available (in preliminary form) in the 0.5dev branch. To make it work you would use the new, special, AlignedUMAP class, and the
updatefunctionality therein. I have a notebook gist that provides a basic walkthrough of these sorts of features. With this approach if your goal is to incrementally add (batches) of new points to an existing embedding, updating the embedding as you go, this should suffice. It may not meet all of your needs, but hopefully it will solve some problems for some users.