Explore possibilities for better t-SNE convergence

[ItsLastDay]

t-SNE is, in essence, optimizing the Kullback-Leibler divergence between neighbour distributions in high- and low-dimensional spaces. The minimum possible value for KL is 0 when distributions are identical.

However, given our data, bhtsne does not yield a zero- or near-zero-valued map. For small set of tags (~300), the observed divergence is about 1.1. For the full set of tags, it is as high as 5.0, with small improvements provided by more iterations.

This can potentially misguide users who try to make an analysis out of visualization. There should be some way to improve convergence in our case. Possible steps:

• perform a multiple-map t-SNE, as suggested by this video. It may turn out to be impossible due to non-scaling of such approach (i.e. Barnes-Hut optimization does not work). Search for an open-source implementation or go for one;
• much research is done for visualizing some concrete classes of data. We can find analogues and apply tricks from existing approaches. For instance, our problem is really similar to "given n authors and k papers by them, visualize all authors based on co-authorship of papers";
• we can play with conversion from tag-tag post count to weights in the tag graph. Actually, some approaches can be inferred from similar work. Also can look here and here at an attempt to visualize SO tags, but in much smaller scale;
• maybe visualizing intermediate steps of t-SNE can give insight on how to improve convergence

[ItsLastDay]

What I've done so far:

• tried to play with scaling of edge weight conversion, i.e. 1000 / x -> 10 / x. This has nearly zero effect on convergence. I assume that because normalization is done inside t-SNE, all scaling is meaningless;
• played with t-SNE external parameters: perplexity, theta, maximum number of iterations. Giving lower theta values does not significantly change convergence, but make iterations a lot slower. Even transition from theta=0.3 to theta=0.1 results in 5x slowdown.
  On the contrary, giving different perplexities results in +-0.1 change in the resulting KL value. However, I do not consider this a good result;
• played with t-SNE internal parameters: learning rate of gradient descend, cutoff iterations for switching mode of operation of gradient descend. My changes resulted either in crash of t-SNE or huge degeneration of obtained KL value. I concluded that manipulating those parameters needs more competence and care.

[ItsLastDay]

I compared produced visualizations for different strategies of converting number of posts between tags to an edge weight in nearest neighbour matrix.

1000 / edge_w:
Has a KL value (the less, the better) of 5.45 after 10k iterations. Each 50 iterations costed 120 sec.
The picture is not so informative, because many tags are very close together:

100 / log(edge_w + 1):
Has a KL value of 4.88 after 10k iterations. Each 50 iterations costed 75 sec.
The picture is more informative, in my opinion:

As a conclusion, the second function is superior to the first. This makes me think that there can be even better functions for converting edge weight.