How to equalize the pairwise affinity perplexities when implementing t-SNE?

Question

I'm trying to implement the t-SNE algorithm:

I found that to compute the pairwise affinities, I have to follow this:

My problem is computing $\sigma_i$. In the Wikipedia I found:

The bandwidth of the Gaussian kernels $\sigma_{i}$, is set in such a way that the perplexity of the conditional distribution equals a predefined perplexity using a binary search. As a result, the bandwidth is adapted to the density of the data: smaller values of $\sigma_{i}$ are used in denser parts of the data space.

I don't understand what this really means. How can I calculate $\sigma_i$?

Answer 1

It simply means that you should set the bandwidths through binary search. The way it works is that you start with a preset target perplexity (Mark's link suggests values from 5 to 50 as reasonable values), and bounds for the bandwidth. If the target perplexity is inside the interval defined by the boundary perplexities, you iteratively halve the search space until you converge to the target:

$$2^{H(p; \sigma_L)} < PP_\mathrm{target} < 2^{H(p; \sigma_U)}$$

If the target was not in the initial interval, you expand the interval and try again.

Answer 2

You can find various implementations at Laurens van der Maaten's page here:

t-SNE by Laurens van der Maaten