Why is the exact algorithm 10 times faster? about bhtsne

[lvdmaaten]

What is the size of the dataset you feed the algorithm? And what value of theta do you use when you run Barnes-Hut t-SNE?

[k8280627]

I fed sample # = 2500 and 7000. I use theta = 0 for exact, and tried theta = 1e-3, 1e-7 for Barnes-Hut tsne.

[lvdmaaten]

Try larger values for theta. Theta determines how many branches of the quadtree are being pruned; larger values of theta imply more pruning, which, in turn, implies faster speed and slightly less accurate results.

In most of my experiments, I found theta = 0.5 to be a good trade-off between speed and quality.

[k8280627]

Thanks for the suggestion! I just tried out and found out that if I use 2500 samples with dimension=102, for the exact algorithm (theta = 0), it took 9.44 sec to run 50 iterations.

For BH tsne, I tried theta = 0.5, 1 and it took ~65 sec and ~70 sec for 50 iterations. I was wondering, Is this unusual?

If it is, there might be something wrong with my experiment....

[lvdmaaten]

Yeah, that is quite unexpected. Does your data have duplicates (or near-duplicates) by any chance?

[k8280627]

I am not quite sure whether my data would have near duplicates. But I tried MNIST and has got similar results.

When using N=2500, theta=0 takes ~9 sec per 50 iters, and theta=0.5 takes 68 sec per 50 iters.

When N = 10000, theta=0 takes 150 sec per 50 iters, and theta=0.5 takes 281 sec per 50 iters.

I could not try N = 20000+ right now since my PC does not have enough computing power.

I was suspecting if there's a slight chance that the computing power of PC would affect the result?

Thank you so very much for answering all my questions. It's very helpful to me!

[lvdmaaten]

The exact numbers may vary per CPU, but I see no reason why they would vary as much as you describe in your post. Are you sure you compiled the bhtsne binary in optimized mode (-O2 / -O3) rather than in debug mode?

Running the MNIST example with N=2500 from the README using the Python wrapper, I see the following timings on my Macbook Pro (3.5 GHz Intel Core i7):

>>> import time
>>> import numpy as np
>>> import bhtsne
>>> data = np.loadtxt("mnist2500_X.txt", skiprows=1)
>>> start_time = time.time(); embedding_array = bhtsne.run_bh_tsne(data, initial_dims=data.shape[1], theta=0.5); end_time = time.time();
>>> print(end_time - start_time)
24.6498529911
>>> start_time = time.time(); embedding_array = bhtsne.run_bh_tsne(data, initial_dims=data.shape[1], theta=0.0); end_time = time.time();
>>> print(end_time - start_time)
68.8492469788

[k8280627]

Sorry for the late reply. I finally found out that I indeed compiled the code in the debug mode instead of the optimized mode, and that is exactly the reason why theta = 0.5 was much slower than theta = 0. After switching to optimized mode, both modes run at expected speeds. I cannot thank you enough for your help!!