t-SNE default parameters and clarifying documentation

[dkobak]

Following a conversation with @amueller on Twitter (https://twitter.com/amuellerml/status/1285939094397366272):

1. Scikit implementation of t-SNE has a factor of 4 in the gradient that most other implementations (the original Barnes Hut implementation, FIt-SNE, openTSNE) do not have. This factor is there in the formula, but the original implementation absorbed it into the learning rate and other implementations followed this convention. This means that your learning_rate corresponds to 4 times higher learning rate in any other implementation. Your 200 is equivalent to 800 of other implementations. This should be mentioned in the docs.

2. The scale of random Gaussian initialization is std=1e-4. The scale of PCA initialization is whatever the PCA outputs. But t-SNE works better when initialization is small. I think what makes sense is to scale PCA initialization so that it has std=1e-4, as the random init does. I would do that by default for PCA init.
   https://www.nature.com/articles/s41467-019-13056-x
   https://arxiv.org/abs/2007.08902

3. I would suggest to use init='pca' as default, and not init='random'. PCA init performs much better.
   https://www.nature.com/articles/s41467-019-13056-x
   https://www.nature.com/articles/s41587-020-00809-z

4. It has been shown that learning rate needs to grow with the sample size, especially for large datasets. A recently suggested heuristic is learning_rate = n/12 (this would be n/48 using your definition of the learning rate):
   https://www.nature.com/articles/s41467-019-13056-x
   https://www.nature.com/articles/s41467-019-13055-y
   I would suggest to implement this as learning_rate='auto' and make it default.

[TomDLT]

Thanks for this ! To summarize:

1. Documentation update.
2. Change of behavior. Could also be a new option like init='scaled_pca'.
3. Change of default.
4. New feature / potential change of default.

To that I would add:

5. Change of behavior: init='pca' uses PCA(n_components=self.n_components) (i.e. 2 by default), which should probably be changed to a larger value, like 50.

The changes of default/behavior seem very reasonable to me, not sure they need extensive benchmarks.
However, they need full deprecation cycles to avoid breaking user's code.

[dkobak]

Hi @TomDLT. Not sure I understood your (5): if one constructs 2-dimensional t-SNE embedding then it's enough to compute 2 PCA components for the initialization. So I think PCA(n_components=self.n_components) is fine.

The changes of default/behavior seem very reasonable to me, not sure they need extensive benchmarks.

I agree.

However, they need full deprecation cycles to avoid breaking user's code.

What exactly does a "full deprecation cycle" mean?

[TomDLT]

What exactly does a "full deprecation cycle" mean?

See Maintaining backward compatibility.

PCA(n_components=self.n_components)

Sorry, I mixed up PCA initialization (makes sense to use self.n_components) and PCA preprocessing (does not make sense to use self.n_components since too much information is lost). You can ignore (5).

[Thomas9292]

I see the help wanted label. I'd be very happy to help out and write up a PR.

In regards to point 1: making this a docs issue might complicate things in the long term. A good example would be that we'd implement a factor 4 difference to compensate in the auto learning rate in point 4. I could possibly see this rabbit hole get deeper in the future.

Would it be an idea to absorb the factor into the learning rate as the other implementations do?

[dkobak]

@Thomas9292 Thanks! It would be great if you could prepare a PR!

Re point 1: in what sense would it "complicate things in the long term"? My thinking was that simply kicking out the 4 factor would make the implementation inconsistent with the previous versions, and I thought scikit-learn puts a lot of emphasis on consistency. I don't see a way to do this gracefully. (Maybe missing something?) For that reason my suggestion was to add to the docs that any given learning_rate corresponds to the 4 times larger learning rate in other implementations, and that's it.

Re point 4, we could simply implement learning_rate='auto' as n/48, and mention in the docs this correspond to n/12 from Belkina et al. Actually I should say that the heuristic there is learning_rate = n/early_exaggeration, so that's how it could be implemented. And due to the 4 factor, it'd be learning_rate = n/early_exaggeration/4.

[dkobak]

Also Re 4: I am not sure what is the good strategy for small sample sizes, so what we did in FIt-SNE/openTSNE was to use learning_rate = max(200, n/early_exaggeration), where 200 was the previous default. This way it never goes down from the previous default, only becomes higher for large sample sizes.

[Thomas9292]

@dkobak thanks for the response!

I agree with your point. I might have overestimated the number of times this will have to be revisited in the future.

I had some hardware trouble so I'm waiting on my new laptop to arrive, but I think I can get started next week. Besides that: @TomDLT, it would be great to have some confirmation that extensive benchmarks aren't needed. Can you give that or do we ask someone else from the core team to confirm that?

[dkobak]

@Thomas9292

Just to clarify again point 4: learning_rate='auto' could be implemented as learning_rate = max(50, n/early_exaggeration/4), then this will exactly coincide with the defaults in Fit-SNE/openTSNE and agree with the recommendations in published papers. I am not sure if the idea is to make learning_rate='auto' default directly, on starting from a next version -- not sure how exactly the backwards compatibility supposed to work.

[TomDLT]

@TomDLT, it would be great to have some confirmation that extensive benchmarks aren't needed.

I can only speak for myself, other core devs might disagree, but the proposed changes look very reasonable, so I don't think extensive benchmarks are necessary.

That being said, a change of default/behavior is costly: for the developers who need to implement a deprecation cycle to warn the future change of behavior; for the code reviewers who need to make sure the deprecation cycle is correct and well tested; for the users who need to update their code to keep the same behavior as before; for the users that will wonder what to do about this new FutureWarning when using the default; etc.
Therefore, we need to demonstrate, even succinctly, that the new default is better than the old one, and that the cost of changing it is worth paying for.

[dkobak]

@TomDLT I looked at this again now.

Regarding the learning rate (point 4 above): the current default (learning rate = 200, corresponding to 800 in other t-SNE implementations) is probably fine for datasets with sample size up to around n=100k. At least it works well on MNIST. On MNIST one often gets into bad local minimum with learning rate 200 (so "scikit learning rate" 50), but 800 works fine. In order to give an example where the current default produces a bad result, one may need a sample size in hundreds of thousands or closer to a million. However, this takes ages to fit using Barnes-Hut t-SNE and so is arguably not worth fixing. For large sample sizes, nobody should be using scikit-learn implementation anyway, given that there are much faster and very well supported alternatives such as openTSNE by @pavlin-policar (https://github.com/pavlin-policar/openTSNE).

So I am not sure point 4 is worth tackling.

I still think scaled PCA initialization (points 2-3) by default would be good (especially in light of recently published https://www.nature.com/articles/s41587-020-00809-z) but it needs to go through the deprecation cycle. Can we simply defer to this published paper as a motivation for the change?

[TomDLT]

Even if we do not address all the points, it is worth writing something in the documentation.

For points 2 and 3, I agree the linked paper is a sufficient motivation for the change.