Relation to FIt-SNE?

[ghost]

How is this related or how does it compare to FIt-SNE on which you have also done work?

[pavlin-policar]

Hi, sorry for the late reply - I somehow missed this in my inbox. This is a re-implementation of Fit-SNE in python/cython. While working on this I simplified the Fit-SNE code substantially - this also resulted in a speed-up. These changes have already been merged into the C++ implementation (see PR).

The goal of this implementation is to have a pure python implementation, which wouldn't need any specific libraries which are difficult to compile on Windows (this is not true yet, because I need to replace fftw with numpy's FFT which are supposedly faster when using intel's mkl optimizations). I am currently integrating this into Orange, where we currently use scikit-learn, which is terribly slow. Because we'll be using it in Orange, there's more functionality for interactive optimization than in most libraries. We can stop and continue optimization with callbacks, get visualizations before the optimization is complete. This is nice to have in an interactive widget environment. Having the library written in Python is also better for experimenting and possible extensions, and having written the slow parts in Cython, the difference in speed to the C++ implementation is negligible.

There are also a couple other minor differences:

• we report the kl divergence (although I think George has incorporated this into Fit-SNE a couple weeks ago)
• we allow new data to be added into the existing embedding by direct optimization. To my knowledge, no other library does this. It's sometimes difficult to get nice embeddings like this, but it may have potential.
• I've added bits of useful code from various research papers on tSNE that don't really appear anywhere e.g. late exaggeration (I believe George came up with this as well and it's probably in FitSNE). I haven't really found it that useful, but maybe someday. Also, pBIC is a measure to evaluate the quality of the tSNE embedding that works across different perplexities. Again, I haven't played around with this too much, but one paper mentioned it, and if it turns out to be good, we could use it for automatic perplexity selection.
• The code is written so it's extensible. tSNE only needs an affinity matrix to run, so in this sense, we are not limited to tabular data and their distances. We could probably embed graphs with adjacency matrices or powers of the adjacency matrix to embed large graphs. Or any other data on which we can compute similarities. I haven't tried this yet, but it should be possible.

I've been meaning to put citations into the readme, so everything is properly attributed, but I've been swamped and haven't had the time to do it.

TLDR: I found the FitSNE paper and implementation and couldn't really make sense of it, so I worked through the theory and wrote my own implementation, where the code is far more readable IMO. I added various bits and bobs that I found while reading up on tSNE. The slow parts are written in cython so it's multithreaded and about as fast as C++. The other parts are written in python so it's really easy to play around with and experiment with tSNE.