Cuml: [FEA] T-distributed Stochastic Neighbor Embedding (t-SNE)

[bgp2112]

This request is for the incorporation of a gpu-accelerated implementation of t-SNE into cuML.

There is an existing implementation, https://github.com/CannyLab/tsne-cuda, that mirrors some of the scikit-learn interface, and it would be ideal to have this or a similar implementation built into RAPIDS with added support for multiple GPUs.

Additional reference:
https://arxiv.org/abs/1807.11824

[danielhanchen]

Hey there! Thanks for posting your feature request to cuML! Super appreciate it :)

I'm sure we'll get around implementing TSNE into cuML in the near future. Actually since you mentioned it, I was actually looking at Maaten's original code implementation (the O(N^2) one) today. I personally myself haven't reviewed the Barnes Hut version (O(nlogn)), since that's much more complicated [maybe later].

[mmshad]

Thanks for adding this request. We use t-SNE on large neuroscience datasets at Harvard University. Having an optimized GPU version of t-SNE will help a lot. It is used for dimensionality reduction in a non-linear fashion.

Use Cases:

1. Finding hidden structures in the neural recordings of brain
2. Behavioral segmentation using t-SNE maps

[cjnolet]

The link that @bgp2112 has posted does give t-SNE quite a performance boost!

@mmshad, In the meantime, I would recommend taking a look at UMAP. It's very similar in the way that it preserves local structure while reducing dimensions for both visualization and downstream ML.

UMAP tends to be very fast to compute. We have a new version in branch-0.6 in cuML that will be getting released over the next week. Hopefully UMAP can get you up and running quickly.

[mmshad]

Thanks @cjnolet for your suggestion. We actually tested UMAP (see this paper for comparison with t-SNE), however, t-SNE provides better structures (at least for our dense datasets). I will definitely test the tsne-cuda package.

[danielhanchen]

Yep for now please check out CannyLab's version. However, in v0.7, I am hoping to include TSNE (as optimised as I can try) into cuML. I'll try my very best! :)

[danielhanchen]

@bgp2112 @mmshad Hiii! Sorry for the late delay (As you know TSNE has a lot of complicated moving parts). (I'm sure you've already tried CannyLab's TSNE). But anyways in cuML v9, TSNE is finally part of cuML!!

If you're still going to use TSNE in the future, consider cuML's implementation! cuML's version is approx 1500x faster than sklearn, and approx 30 - 50% faster than even CannyLab's version!!!! [Eg MNIST 60,000 takes approx 3s or so + looks the same as CL [CL takes 6 - 7s]

I based the repulsion kernels primarily off CannyLab BH, with some heavy modifications. Attractive kernels and all other moving parts in cuML are purely made from scratch, and optimized to the bare metal.

Also, our version uses less memory!

If you're still willing to try out cuML's version, wait a little longer on v9! [Or if you can't wait, you can git pull from the current repo! A notebook showing off TSNE's speed + optimizations is at TSNE Notebook

[mmshad]

@bgp2112 , thank you for the update. This is great since it saves us a lot of time. I'll give it a try using the notebook and will let you know how it works for us.

[Pezhvuk]

If you're still willing to try out cuML's version, wait a little longer on v9! [Or if you can't wait, you can git pull from the current repo! A notebook showing off TSNE's speed + optimizations is at TSNE Notebook

@danielhanchen The Notebook no longer seems to be available :(.

[danielhanchen]

Hi @Pezhvuk Oh yep we decided the notebook was too long. However, the basic demo has been uploaded. You can check it out in https://github.com/rapidsai/notebooks/pull/211. (Direct link: https://nbviewer.jupyter.org/github/rapidsai/notebooks/blob/695bd4efdaac88d617ccdbe0f0e724092e4fe03b/cuml/tsne_demo.ipynb)

For the old notebook which showcases the full functionality of cuML TSNE, the old pull request is @ https://github.com/danielhanchen/notebooks/blob/5bd0a28bd64077a55e68db44388030a971acdb08/cuml/TSNEdemo.ipynb

Also in branch 9 cuML (current latest), TSNE defaults to naive. You'll have to manually set method = 'barnes_hut' and also learning_rate_method = 'adaptive' to run barnes hut O(nlogn) TSNE. Currently you might experience some memory issues (which are fixed in v10 next month).

Thanks for using cuML!

[Pezhvuk]

@danielhanchen Thank you so much for all this information. The memory issue is certainly there, but there are some other issues that I cannot explain/debug, because the verbosity = 1/2 parameter does not print out anything. Namely, running the t-SNE, with slightly different parameters, on the same dataframe yields vastly different runtimes. The runtimes are either several seconds (fab!) to unknown (it took so long I gave up). Also will the "PCA" initiation method be included in next month's release? And finally, is there a plan to implement Isomap in the future?

Thanks for the great package!

[danielhanchen]

@Pezhvuk Well glad on the fast second runs! Also sorry about the issues :(
For verbosity = 1 (i think 2 is same as 1 for cuML's TSNE), you should see output in either the Python Console or if you are using Jupyter Notebook, in the console. If not, I'll investigate.

Yep I also found my TSNE implementation to have vastly different times (ie first run is fast, but then second or later runs either slow or just stay there forever). This is fixed in branch 10 :) (ie next release :) ) This was a by-product of the memory issues.

On very different intializations, for now I'm adding Spectral intialization. It should have the same intialization structure as PCA, however if PCA is very popular, will add PCA / SVD as well later. (Also next release :) ) Also have you tried random_state = 0 or something? [I know that still has vastly diff results]

Isomap hmmm. I have implemented Isomap before, so I have the main gist of it. It's possible, but I'll have to refresh myself on Isomap. I remember a traversal graph is built using the shortest paths. Anyways I'll get back to you.

To summarize:

1. Memory issues - fixed next release
2. Slow / forever running - fixed next release
3. PCA init / random issues - fixed next release
4. Isomap - will get back to you :)

Thanks for using cuML!

[Pezhvuk]

@danielhanchen Thank you for such a prompt reply!

In summary, hooray to all of it. I cannot wait for the next release, and just all the future releases and features.

If I could contribute to the implementation, or anything else, do let me know. I'd be glad to help. :)

[danielhanchen]

@Pezhvuk Thanks so much once again! :)

Oh thanks so much for your potential help then :) Since cuML is open source, if you have time and you would like to contribute, (either by say providing ideas / finding issues etc [as you've already done thanks again!]), then feel free to!!

But ye once again thanks for trying out cuML :)