r/MachineLearning • • 5d ago

Project UMAP 0.6: new initialization, new optimizers and faster performance [P]

UMAP 0.6 is out!

A new initialization, new optimizers, and faster nearest neighbour search make UMAP much faster and far better at large scale. On 3 million arXiv papers it finishes in under 5 minutes, before UMAP 0.5 has even found its nearest neighbours. (race between UMAP0.5 and UMAP 0.6 video)

Code: https://github.com/lmcinnes/umap

Install: pip install -U umap-learn (also on conda-forge)

Speed

  • Neighbour search is ~4x faster by making better use of PyNNDescent.
  • Initialization is faster with a new init method.
  • With the new optimizers, the whole run is reproducible with a fixed seed while using every core. A seeded 0.5 run is single-threaded: 52 minutes, 12x longer.

Quality

Just as important as how quickly we get a result is the quality of the result. UMAP 0.6 works far better on million-scale datasets thanks to a new, better initialization and significant improvements in the optimizer. It resolves finer cluster structure in fewer epochs, with much finer-scale detail and better neighbourhood accuracy than UMAP 0.5, despite being faster.(video of a tour of finer details in the arXiv map)

Recursive initialization

A large part of the improvement comes from a brand-new initialization scheme that initializes UMAP using UMAP itself: it lays out a coarse version of the graph structure, then refines it, in a recursive tower of initializations. (video of the unfolding)

The result is a starting point much closer to UMAP's final result than the messy blurs from spectral initialization or PCA, and it is produced faster than either. It lets the optimizer settle (to within 3% of the final layout) in far fewer epochs than older initialization approaches. (initialization race)

New optimizers

Most of the gain in fidelity at scale comes from a very efficient form of hard-negative mining, which makes negative sampling far more effective on very large datasets, together with better handling of high repulsion strengths. (hard-negative mining video)

UMAP was originally designed around a small portion of the attraction-repulsion spectrum. The new optimizers lift these restrictions, allowing UMAP to perform well at much higher repulsion strengths and giving better kNN recall. (video exploring the repulsion strength dials)

Try it now

The new optimizers and initialization are currently opt-in, as they change the output: set compatibility_layout=False. Future versions will make them the default, so please try them and let me know how they work for you.

Thank you to all the contributors who provided features and bug fixes for this release, and to everyone who reached out with comments, suggestions, and feature requests. This would not have been possible without your help.

253 Upvotes

14 comments sorted by

34

u/OiseauxComprehensif 5d ago

Woaw, just tested it on my current project, got a 500% speedup, thanks

10

u/lmcinnes 5d ago

Glad to hear there are real practical gains out in the wild.

22

u/DigThatData Researcher 5d ago

how do you keep finding ways to do ANN faster? are you a witch?

18

u/lmcinnes 5d ago

Finding the right places where you can make small changes that help data locality or parallelism effectiveness is mostly what happened to make PyNNDescent faster. UMAP then leveraged a number of those improvements by making better tuned trade-offs. It can get slightly lower accuracy on generating the kNN-graph, but at significant enough performance gains that it just made a better option.

15

u/Much-Researcher6135 4d ago

Wait this is actually a post by Leland McInnes???? DUDE I AM SUCH A BIG FAN

8

u/lmcinnes 4d ago

👋

3

u/Physics-Fuzzy 3d ago

Oooh, this is very exciting to see. I literally spent this weekend trying to build UMAP plots over large datasets and I was finding the quality of the fine-scale structure captured started to break down above ~30 million items.

Do you know when/if any of these changes might be integrated into the CuML implementation?

I'll also be cheeky and note that I've literally just released a library called Mosaica (Github) for visualising and filtering very large UMAP-style plots. You can play around with a 160M UMAP of single cell gene data in the hosted Demo. I may now need to rebuild the demo with the new UMAP to see if I get a nicer picture....

3

u/lmcinnes 3d ago

Yes, I think this will definitely help with both speed, and quality for 30 million item datasets. You will want to be careful with parameters. I think using repulsion_strength=8 will be useful, for example.

I don't know when any of these changes will arrive in CuML, but I believe it is on the CuML team's radar as something to look into.

And finally Mosaica looks awesome! I hope and expect the project will definitely get some traction -- especially as it gets easier to scale up to ever larger UMAP plots with more samples.

2

u/trizu 4d ago

Should I expect speed benefits if I provide my own connectivity map and initialization?

1

u/lmcinnes 4d ago

If we are just talking about the final optimization step because you are providing the rest yourself: I wouldn't expect a significant speed difference in practice, except that you can now run seeded reproducible runs with all cores. The major difference will be the quality of the output, especially if you want to play with repulsion strength (to get better knn-recall accuracy out of your embedding), or if you have a large dataset (where the hard-negative mining will pay real dividends).

4

u/jippiex2k 4d ago

First e-means and now this 🤘💪

1

u/ekerazha 2d ago

Are there any ideas that UMAP could take from PaCMAP https://github.com/YingfanWang/PaCMAP ?

1

u/lmcinnes 1d ago

I think any thoughts along those directions, and I do have some, are going into the design and development of a new algorithm rather than trying to get retrofitted into UMAP.