6
$\begingroup$

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:

enter image description here

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

[edit]

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

enter image description here

Improve this question
$\endgroup$
5
  • $\begingroup$ 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$? $\endgroup$
    – GeoMatt22
    Commented Jan 9, 2017 at 18:26
  • $\begingroup$ @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). $\endgroup$
    – David Kozak
    Commented Jan 9, 2017 at 19:41
  • $\begingroup$ 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? $\endgroup$
    – GeoMatt22
    Commented Jan 9, 2017 at 20:16
  • $\begingroup$ 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. $\endgroup$
    – GeoMatt22
    Commented Jan 9, 2017 at 20:18
  • $\begingroup$ 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. $\endgroup$
    – David Kozak
    Commented Jan 9, 2017 at 20:49

1 Answer 1

Reset to default
3
$\begingroup$

"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.

Below is a (not-too-extreme) example of this. I simulated 100 points from a Gaussian Mixture with two Gaussians of equal probability. The data was not quite linearly separable. I chose a point, i, at random and varied Perplexity and k. Note the sudden change in first derivative of the k-nn approach as we near 50 (the expected number of points that fall within a given cluster).

enter image description here

enter image description here

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ +1. The question though is why this smoothness is something desirable. $\endgroup$
    – amoeba
    Commented Apr 27, 2017 at 10:01
  • 2
    $\begingroup$ It seems desirable for stability of the solution. If small changes to the parameters produce drastically different results for sigma then we'll end up with instability in the kernel which will cause the Cost function to lose its meaning.... $\endgroup$
    – David Kozak
    Commented Jun 13, 2017 at 18:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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