# Why use perplexity rather than nearest neighbor match in t-SNE?

I am trying to work through Van der Maaten and Hinton's paper on t-SNE (which was inspired by Hinton and Roweis' SNE) and am having trouble understanding why they use a perplexity parameter.

In the t-SNE paper the authors suggest "The perplexity can be interpreted as a smooth measure of the effective number of neighbors". It is clear to me why they need to set $\sigma_i$ to different values for each i, but why complicate matters with complexity? It is easier to understand and just as quick to do a binary search for a $\sigma_i$ that results in k (user-specified) neighbors within two standard deviations of the point i.

I tested this thought on a simple case, 100 samples from a Gaussian Mixture with 3-dimensions, using a Perplexity of 20 in one case and k=6 nearest neighbors in the second case. In this case there is a near-linear relationship between the $\sigma_i$ generated by each method, as shown below:

Perhaps my example just wasn't complex enough? Or maybe the use of Perplexity conveys some additional information as log_2(entropy) that I just don't have intuition for?

Any insight would be appreciated

In response to @geomatt's comment, I have run it again but dropped the dimension down to two to be able to visualize. This shows the location of points in (x1,x2) space with the resulting sigma values in black (k-nn) and red (perplexity). Aside from the constant multiple I still don't notice a huge difference

• I would think "smooth measure" implies something about the scales of spatial variability, which your plot would not show. Are there sharper changes/gradients in $\sigma$ between neighbors when using $k$? Jan 9, 2017 at 18:26
• @GeoMatt22 Good question. Since points that are near to eachother will be picking up many of the same neighbours my intuition suggests that there shouldn't be a sharp gradient between neighbours when using k. I did run it in case intuition failed, but nothing really stood out in all the data. I edited the post to include a plot with a few data points (couldn't include them all or it would get too cluttered, but I did run it on more and in higher dimension). Jan 9, 2017 at 19:41
• OK. Two notes: 1) For visualization, more informative would be to superimpose a "translucent 2-$\sigma$ ball" over each point. In thinking about this, then I would suggest 2) try to compare more comparable cases. Your $\sigma_k$ values are much larger than for perplexity, implying $k$ is perhaps too large to be comparable. If you had smaller $k$ (such that the regression line is closer to 1:1), then perhaps the $\sigma_k$ values would be more sensitive to density variations, e.g. maybe showing non-smooth threshold behavior? Jan 9, 2017 at 20:16
• Another possibility (aside from the author's declared "smooth" justification) would be that even if an "equivalent $k$" could always be identified post hoc ... it could be that this varies a lot for a given perplexity, while a roughly constant perplexity "does well" over a variety of data sets. Jan 9, 2017 at 20:18
• Ah I think I see... Suppose there are two separated clusters in the data and one of the clusters has k-1 points in it. The smoothness could be in the $\sigma$ in k-space. In this scenario if I dropped k then the variance would drop dramatically for each of the points in that cluster so the output is highly sensitive to the value of k chosen. Jan 9, 2017 at 20:49

"The perplexity can be interpreted as a smooth measure of the effective number of neighbors" could be interpreted as $\frac{\delta \sigma_i}{\delta P}$ being smooth. That is, varying Perplexity has an effect on $\sigma_i$ for a fixed i that is continuous in all derivatives.
This is not true of the k-NN approach. One can imagine fixing an i that lies within a cluster containing G points. varying k from 2 ... G-1 should result in similar but monotonically increasing values of $\sigma_i$. There is a jump at k=G as the value of $\sigma$ must be large enough to reach outside the cluster. The distance between the cluster and the nearest point determines the size of this jump.