n_neighbors vs perplexity (API discussion)

[dkobak]

Hi Pavlin, I met Leland @lmcinnes last week at a workshop in Denmark and he said he thinks openTSNE should transition away from using perplexity to something like n_neighbors because apparently multiple people mentioned to him that the notion of perplexity is confusing. A separate argument (not from Leland but from me) is that default perplexity=30 implies k=90 neighbors which is much slower than what one would have with k=10 or k=15 neighbors.

One possibility of allowing that would be to add n_neighbors parameter into the TSNE() constructor API. If provided, it would override perplexity=30 and use Uniform affinity class with the n_neighbors param. Leland's suggestion would then to actually make n_neighbors=10 or 15 default (instead of perplexity), but that's maybe a bit more radical than what you would want to allow here (?). But one could think about it again in some future version.

The only downsides that I see is one extra param in the class constructor, and also it's not great to have TSNE(perplexity=30, n_neighbors=10) to silently override the perplexity setting. But it'd be nice to make TSNE(n_neighbors=10) possible... Not sure if there is a better way to achieve that.

[lmcinnes]

My argument is that n_neighbors makes sense for t-SNE, and many people have a much clearer intuitive grasp of what n_neighbors=15 means than what perplexity=30 means. One has a very concrete description in terms of nearest neighbors, while the other involves explaining what perplexity is and how that interacts with how far out t-SNE looks.

[pavlin-policar]

On the one hand, the goal of openTSNE has always been to be a fast implementation of the t-SNE aglorithm. From this point of view, the default should always be vanilla t-SNE and therefore, perplexity is one of the main parameters and can't be replaced with n_neighbors. If openTSNE does not default to vanilla t-SNE, then perhaps openTSNE is not the correct name for the library. One could argue that we aren't running vanilla anymore anyways since, by default, we have a different number of iterations, the learning rate is different, and exaggeration can is different from the original publication, but I'd argue that these are not changes to the core t-SNE algorithm, but simply optimization tricks to get better t-SNE embeddings. Swapping out perplexity for uniform neighbors fundamentally changes the maths of t-SNE and IMO isn't t-SNE anymore, even if differences are negligible.

On the other hand, is the goal of openTSNE to continually be updated to offer scalable dimensionality reduction? From this perspective, replacing perplexity with n_neighbors makes perfect sense. There's virtually no difference between Uniform affinities and Gaussian-based ones, so why not default to Uniform ones; they're way faster. But I don't think this is the route we want to take. I think I prefer openTSNE being the reference implementation of t-SNE. The guiding principle of openTSNE should be to offer vanilla t-SNE by default, but have all these nice extensions and speed ups there if you want to use them. This is what we've done so far.

However, I totally agree with both of you. n_neighbors is way more intuitive and using a uniform kernel makes a lot of sense. In my own work, I almost always use uniform kernels with some exaggeration > 1. I think adding a n_neighbors parameter that silently switches to a uniform kernel and ignores the perplexity parameter could be confusing to users. One route we could take is that we could add two parameters to the main TSNE class -- affinities and n_neighbors -- where the user could specify what kind of affinities they want to use (uniform/fixed/standard) and then set the corresponding parameters. However, since we also have fixed bandwidth affinities, we would then also need to add a bandwidth parameter to the main constructor. So that could get out of hand.

Another option that's been on my mind since Dagstuhl, actually, is to add a recipe module (or something similar) that would have useful things that we run all the time. For instance, in Dagstuhl, we talked about a fast variant that takes the most crude approximation but still delivers very reasonable results. For instance, we could get the full MNIST embedding that still shows good clusters in a manner of seconds. One of these recipes could be "uniform" using uniform affinities, another could be "big_dataset" using unfirom affinities and extended iterations. So then, the code might look like openTSNE.recipes.uniform(...). This is primarly inspired by scanpy, which does something similar to its preprocessing.

I'm really curious what your guys' thoughts are about this; I'm sure you must have similar considerations with UMAP as well. What do you think the best way to implement this would be?

[lmcinnes]

I definitely understand your concerns, as I have had similar issues with, for example, the hdbscan libraries I've written. There are things I would like to tweak, but it does need to be a faithful implementation of the algorithm. So I agree, the default should definitely be classic t-SNE. It is really a matter of how to handle other options.

I do actually like the sound of the the recipe approach, because I do think there are likely a number of recipe options that are fairly standard (as you note, I think uniform kernels and somewhat increased exaggeration is a fairly common recipe; likewise a recipe targeting very large data). In fact I like this idea enough that I may try to implement something similar for UMAP -- predefined recipes that standardise options choices for various different use cases.

[dkobak]

I think recipes module is a cool idea in general, but I am not sure about the best API. That's definitely something to think about.

Adding affinities="gaussian" to the main class actually sounds reasonable to me (independent of whether you add recipes module or not). To handle additional affinity params, one could have a single affinity_params dictionary. So that would allow

TSNE(affinities="uniform", affinity_params={"n_neighbors": 10})

and using any other affinities similarly.

By the way, I feel many existing parameters could be "hidden away" into similar dictionaries, like for example theta=0.5, n_interpolation_points=3, min_num_intervals=50, ints_in_interval=1 could all go into a negative_gradient_params dictionary. This is anyway passed into a function computing negative gradient. Similar to metric_params and knn_kwargs which you do have (should it for consistency be renamed into knn_params by the way?)

And learning_rate="auto", initial_momentum=0.8, final_momentum=0.8, max_grad_norm=None, max_step_norm=5 could all go into optimizer_params dictionary. Or is this somehow a bad practice? Here I am less sure. But in practice nobody touches these parameters and should not really touch them either...