22
$\begingroup$

I would like to do dimensionality reduction on nearly 1 million vectors each with 200 dimensions(doc2vec). I am using TSNE implementation from sklearn.manifold module for it and the major problem is time complexity. Even with method = barnes_hut, the speed of computation is still low. Some time even it runs out of Memory.

I am running it on a 48 core processor with 130G RAM. Is there a method to run it parallely or make use of the plentiful resource to speed up the process.

$\endgroup$
  • $\begingroup$ Did you try map-reduc'ing in a framework like Spark? $\endgroup$ – Dawny33 Feb 6 '16 at 14:23
  • $\begingroup$ Nope.. how does it work and can you please direct me.. $\endgroup$ – yazhi Feb 6 '16 at 14:46
  • $\begingroup$ Pl go through Spark's documentation for understanding it :) $\endgroup$ – Dawny33 Feb 6 '16 at 14:48
  • 1
    $\begingroup$ See if this Spark implementation works. $\endgroup$ – Emre Feb 11 '16 at 17:55
  • 1
    $\begingroup$ It's Scala for Spark. If you want a python implementation you might be able to translate it; Spark runs on python too. $\endgroup$ – Emre Feb 11 '16 at 19:07
14
$\begingroup$

You must look at this Multicore implementation of t-SNE.

I actually tried it and can vouch for its superior performance.

| improve this answer | |
$\endgroup$
7
$\begingroup$

Check out FFT-accelerated Interpolation-based t-SNE (paper, code, and Python package).

From the abstract:

We present Fast Fourier Transform-accelerated Interpolation-based t-SNE (FIt-SNE), which dramatically accelerates the computation of t-SNE. The most time-consuming step of t-SNE is a convolution that we accelerate by interpolating onto an equispaced grid and subsequently using the fast Fourier transform to perform the convolution. We also optimize the computation of input similarities in high dimensions using multi-threaded approximate nearest neighbors.

The paper also includes an example of a dataset with a million points and 100 dimensions (similar to OP's setting), and it seems to take ~1 hour.

| improve this answer | |
$\endgroup$
6
$\begingroup$

Since, there are no answers in SO, I have asked myself in github page and the issue has been closed by stating the following reply by GaelVaroquaux..

If you only want to parallelise vector operation, then you should use a build of numpy compiled with MKL (don't attempt to do it yourself, it's challenging).

There could be approaches to high-level parallelism in the algorithm itself, which would probably lead to larger gains. However, after a quick look at the code, I didn't see any clear way of doing that.

I am going to ahead and close this issue, as it is more of a blue-sky whish list. I completely agree, I would like TSNE to go faster, and it would be great is parallelism was easy. But in the current state of affairs, more work is required to be in a state where we can tackle such wish list.

| improve this answer | |
$\endgroup$
6
$\begingroup$

Try UMAP:https://github.com/lmcinnes/umap

It's significantly faster than t-SNE.

| improve this answer | |
$\endgroup$
0
$\begingroup$

Since version 0.22, there is a new parameter called n_jobs in the scikit-learn t-SNE implementation. This parameter specifies the number of parallel jobs to run for neighbors search.

The Multicore-TSNE project mentioned in another answer seems to be dead.

| improve this answer | |
$\endgroup$

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.