search

DmitryUlyanov / Multicore-TSNE

Parallel t-SNE implementation with Python and Torch wrappers.
Other
1.89k stars 228 forks source link

other metrics #18

Open chupvl opened 7 years ago

chupvl commented 7 years ago

Hi!

is it possible to add other metrics, some data are not well suited for default 'euclidean' one?

Many thanks!

DmitryUlyanov commented 7 years ago

Hi, as far as I know quadtree is only suited for euclidean. You can get cosine for free by normalizing your data first. Other metrics are not supported.

DmitryUlyanov commented 6 years ago

Now it is possible to easily add new metrics (yet in C++ with recompilation). If you have any preferences I could implement some.

asanakoy commented 6 years ago

@DmitryUlyanov why quadtree is only suited for euclidean? If I just change a distance function when you instantiate VpTree<> from euclidean to cosine will it be sufficient?

DmitryUlyanov commented 6 years ago

Hi @asanakoy, my statement from 25 June was incorrect.

If I just change a distance function when you instantiate VpTree<> from euclidean to cosine will it be sufficient?

Now I realize that it is not that easy. Distance should also be changed in gradient computation and for now it is hardcoded to be euclidean.

DmitryUlyanov commented 6 years ago

Well, you still can get cosine similarity by normalizing your data to have unit norm.

asanakoy commented 6 years ago

Now I realize that it is not that easy. Distance should also be changed in gradient computation and for now it is hardcoded to be euclidean.

Could you please point out which line of code it is?

asanakoy commented 6 years ago

Well, you still can get cosine similarity by normalizing your data to have unit norm.

But this is not exactly the same as the cosine distance.

asanakoy commented 6 years ago

I have added not normalized cosine distance (basically it is dot product) in my fork https://github.com/asanakoy/Multicore-TSNE/commit/eebf7365e5f75ec772acb6212a47eef8d5aef0f6

But as you mentioned above it's not fully correct because I forgot to change the gradient computation.

DmitryUlyanov commented 6 years ago

Could you please point out which line of code it is?

https://github.com/DmitryUlyanov/Multicore-TSNE/blob/master/multicore_tsne/tsne.cpp#L242 https://github.com/DmitryUlyanov/Multicore-TSNE/blob/master/multicore_tsne/tsne.cpp#L313

Maybe there are more.

But this is not exactly the same as the cosine distance.

I see, but if we used squared euclidean distance than it is. Looks easy to change in the code :)

By the way, both cosine distance and squared euclidean are not proper distances. This repo actually uses squared euclidean for VP tree by default and it seem to work well, but maybe there are cases where it breaks the method.

asanakoy commented 6 years ago

I have investigated the implementation more carefully.

VPTree works with any metric distance. And it can work well with angular distance (arccosine distance) as it is pseudo metric. No need to change a gradient calculation as the new distance function is only appplied in the original space. The distance in the target embedding space is euclidean.

I have implemented several different distance metrics + added lots of comments about implementation in my fork https://github.com/asanakoy/Multicore-TSNE.