3
$\begingroup$

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

enter image description here

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

enter image description here

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$?

$\endgroup$
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$
1
$\begingroup$

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

t-SNE by Laurens van der Maaten

| improve this answer | |
$\endgroup$
  • $\begingroup$ of course, but i'm trying to implement $\endgroup$ – Daniel Falbel Nov 23 '16 at 10:33
  • $\begingroup$ You could study the implementations ;) $\endgroup$ – Emre Nov 23 '16 at 11:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.