Elamur Research
☰
home / papers / 2018 / UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction

UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "arXiv — non-exclusive licence to distribute" does not allow redistributing the text itself. Original — arxiv.org/pdf/1802.03426

Summary

UMAP is a dimension-reduction method meant to scale to large, varied datasets. It aims to make embeddings that look as good as t-SNE's while running faster, and it can output any number of dimensions. The authors base the method on Riemannian geometry and algebraic topology, especially David Spivak's work on fuzzy simplicial sets. Each point gets its own distance scale, normalised by how far away its k-th nearest neighbour is, so the data can be treated as if it were spread evenly over a manifold. These separate local views are turned into fuzzy simplicial sets and joined into one weighted neighbour graph. A low-dimensional layout is then fitted with stochastic gradient descent, which minimises the cross-entropy between the high-dimensional and low-dimensional fuzzy structures. An appendix shows that t-SNE, LargeVis and UMAP all fit one shared framework. According to the authors, UMAP gives similar visual quality to t-SNE, keeps the large-scale layout of the data better, and runs faster. It also works as a general preprocessing step for machine learning, not only for 2-D plots. Early releases had already been adopted in bioinformatics and materials science.

Key points

  • Graph construction: each neighbour gets a membership weight of exp(−(d − ρᵢ)/σᵢ). Here ρᵢ is the distance to the point's nearest neighbour, and σᵢ is a per-point scale calibrated much like t-SNE's perplexity. The distance d does not have to be Euclidean.
  • Symmetrisation: the two directed weights are merged with a fuzzy union, v_ij = v_j|i + v_i|j − v_j|i·v_i|j. Unlike t-SNE, no global normalisation is applied.
  • Low-dimensional similarity: the curve 1/(1 + a‖yᵢ−yⱼ‖^{2b}) is used. With default settings, a ≈ 1.929 and b ≈ 0.7915; setting a = b = 1 gives back t-SNE's Student-t kernel.
  • Comparison with LargeVis: the objective is close to LargeVis's, but there is no γ weight on the repulsion term, so it can be optimised with SGD on approximate nearest neighbours.
  • Further directions: the paper names semi-supervised learning, metric learning and embedding mixed (heterogeneous) data. The summarised text is arXiv:1802.03426v3 (September 2020).

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Computing & GPUs

Cited by

345 papers of our library cite it (of the 140673 whose bibliographies we read); 8 of them have a page here, 337 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.1802.03426 · arXiv 1802.03426

@misc{mcinnes2018umap,
  title = {{UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction}},
  author = {McInnes, Leland and Healy, John and Melville, James},
  year = {2018},
  doi = {10.48550/arxiv.1802.03426},
  eprint = {1802.03426},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1802.03426}
}

References

65 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. E Alpaydin and Fevzi Alimoglu. Pen-based recognition of handwritten digits data set. university of california, irvine. Machine Learning Repository. Irvine: University of California, 4(2), 1998. find
  2. Frederik Otzen Bagger, Savvas Kinalis, and Nicolas Rapin. Bloodspot: a database of healthy and malignant haematopoiesis updated with purified and single cell mrna sequencing profiles. Nucleic Acids Research, 2018. find
  3. Michael Barr. Fuzzy set theory and topos theory. Canad. Math. Bull, 29(4):501–508, 1986. find
  4. Etienne Becht, Charles-Antoine Dutertre, Immanuel W.H. Kwok, Lai Guan Ng, Florent Ginhoux, and Evan W Newell. Evaluation of umap as an alternative to t-sne for single-cell data. bioRxiv, 2018. find
  5. Etienne Becht, Leland McInnes, John Healy, Charles-Antoine Dutertre, Immanuel WH Kwok, Lai Guan Ng, Florent Ginhoux, and Evan W Newell. Dimensionality reduction for visualizing single-cell data using umap. Nature biotechnology, 37(1):38, 2019. find
  6. Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. In Advances in neural information processing systems, pages 585–591, 2002. find
  7. Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural computation, 15(6):1373–1396, 2003. find
  8. Aurélien Bellet, Amaury Habrard, and Marc Sebban. A survey on metric learning for feature vectors and structured data. arXiv preprint arXiv:1306.6709, 2013. — [arXiv:1306.6709](https://arxiv.org/abs/1306.6709) find
  9. Tess Brodie, Elena Brenna, and Federica Sallusto. Omip-018: Chemokine receptor expression on human t helper cells. Cytometry Part A, 83(6):530–532, 2013. find
  10. Lars Buitinck, Gilles Louppe, Mathieu Blondel, Fabian Pedregosa, Andreas Mueller, Olivier Grisel, Vlad Niculae, Peter Prettenhofer, Alexandre Gramfort, Jaques Grobler, Robert Layton, Jake VanderPlas, Arnaud Joly, Brian Holt, and Gaël Varoquaux. API design for machine learning software: experiences… find
  11. John N Campbell, Evan Z Macosko, Henning Fenselau, Tune H Pers, Anna Lyubetskaya, Danielle Tenen, Melissa Goldman, Anne MJ Ver-stegen, Jon M Resch, Steven A McCarroll, et al. A molecular census of arcuate hypothalamus and median eminence cell types. Nature neuroscience, 20(3):484, 2017. find
  12. Junyue Cao, Malte Spielmann, Xiaojie Qiu, Xingfan Huang, Daniel M Ibrahim, Andrew J Hill, Fan Zhang, Stefan Mundlos, Lena Christiansen, Frank J Steemers, et al. The single-cell transcriptional landscape of mammalian organogenesis. Nature, page 1, 2019. find
  13. Gunnar Carlsson and Facundo Mémoli. Classifying clustering schemes. Foundations of Computational Mathematics, 13(2):221–252, 2013. find
  14. Shan Carter, Zan Armstrong, Ludwig Schubert, Ian Johnson, and Chris Olah. Activation atlas. Distill, 2019. https://distill.pub/2019/activation-atlas. ↗
  15. Brian Clark, Genevieve Stein-O’Brien, Fion Shiau, Gabrielle Cannon, Emily Davis, Thomas Sherman, Fatemeh Rajaii, Rebecca James-Esposito, Richard Gronostajski, Elana Fertig, et al. Comprehensive analysis of retinal development at single cell resolution identifies nfi factors as essential for mitotic… find
  16. Ronald R Coifman and Stéphane Lafon. Diffusion maps. Applied and computational harmonic analysis, 21(1):5–30, 2006. find
  17. Alex Diaz-Papkovich, Luke Anderson-Trocme, and Simon Gravel. Revealing multi-scale population structure in large cohorts. bioRxiv, page 423632, 2018. find
  18. Wei Dong, Charikar Moses, and Kai Li. Efficient k-nearest neighbor graph construction for generic similarity measures. In Proceedings of the 20th International Conference on World Wide Web, WWW ’11, pages 577–586, New York, NY, USA, 2011. ACM. find
  19. Carlos Escolano, Marta R Costa-jussà, and José AR Fonollosa. (self-attentive) autoencoder-based universal language representation for machine translation. arXiv preprint arXiv:1810.06351, 2018. — [arXiv:1810.06351](https://arxiv.org/abs/1810.06351) find
  20. Mateus Espadoto, Nina ST Hirata, and Alexandru C Telea. Deep learning multidimensional projections. arXiv preprint arXiv:1902.07958, 2019. — [arXiv:1902.07958](https://arxiv.org/abs/1902.07958) find
  21. Mateus Espadoto, Francisco Caio M Rodrigues, and Alexandru C Telea. Visual analytics of multidimensional projections for constructing classifier decision boundary maps. find
  22. Greg Friedman et al. Survey article: an elementary illustrated introduction to simplicial sets. Rocky Mountain Journal of Mathematics, 42(2):353–423, 2012. find
  23. Lukas Fuhrimann, Vahid Moosavi, Patrick Ole Ohlbrock, and Pierluigi Dacunto. Data-driven design: Exploring new structural forms using machine learning and graphic statics. arXiv preprint arXiv:1809.08660, 2018. — [arXiv:1809.08660](https://arxiv.org/abs/1809.08660) find
  24. Benoit Gaujac, Ilya Feige, and David Barber. Gaussian mixture models with wasserstein distance. arXiv preprint arXiv:1806.04465, 2018. — [arXiv:1806.04465](https://arxiv.org/abs/1806.04465) find
  25. Paul G Goerss and John F Jardine. Simplicial homotopy theory. Springer Science & Business Media, 2009. find
  26. Matthias Hein, Jean-Yves Audibert, and Ulrike von Luxburg. Graph laplacians and their convergence on random neighborhood graphs. Journal of Machine Learning Research, 8(Jun):1325–1368, 2007. find
  27. Harold Hotelling. Analysis of a complex of statistical variables into principal components. Journal of educational psychology, 24(6):417, 1933. find
  28. Dmitry Kobak and Philipp Berens. The art of using t-sne for single-cell transcriptomics. Nature communications, 10(1):1–14, 2019. find
  29. Dmitry Kobak and George C Linderman. Umap does not preserve global structure any better than t-sne when using the same initialization. bioRxiv, 2019. find
  30. J. B. Kruskal. Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis. Psychometrika, 29(1):1–27, Mar 1964. find
  31. Siu Kwan Lam, Antoine Pitrou, and Stanley Seibert. Numba: A llvm-based python jit compiler. In Proceedings of the Second Workshop on the LLVM Compiler Infrastructure in HPC, LLVM ’15, pages 7:1–7:6, New York, NY, USA, 2015. ACM. find
  32. Yann Lecun and Corinna Cortes. The MNIST database of handwritten digits. find
  33. John A Lee and Michel Verleysen. Shift-invariant similarities circumvent distance concentration in stochastic neighbor embedding and variants. Procedia Computer Science, 4:538–547, 2011. find
  34. Xin Li, Ondrej E Dyck, Mark P Oxley, Andrew R Lupini, Leland McInnes, John Healy, Stephen Jesse, and Sergei V Kalinin. Manifold learning of four-dimensional scanning transmission electron microscopy. npj Computational Materials, 5(1):5, 2019. find
  35. M. Lichman. UCI machine learning repository, 2013. find
  36. George Linderman. Fit-sne. https://github.com/KlugerLab/FIt-SNE, 2018. ↗
  37. George C Linderman, Manas Rachh, Jeremy G Hoskins, Stefan Steinerberger, and Yuval Kluger. Efficient algorithms for t-distributed stochastic neighborhood embedding. arXiv preprint arXiv:1712.09005, 2017. — [arXiv:1712.09005](https://arxiv.org/abs/1712.09005) find
  38. George C Linderman and Stefan Steinerberger. Clustering with t-sne, provably. SIAM Journal on Mathematics of Data Science, 1(2):313–332, 2019. find
  39. Saunders Mac Lane. Categories for the working mathematician, volume 5. Springer Science & Business Media, 2013. find
  40. J Peter May. Simplicial objects in algebraic topology, volume 11. University of Chicago Press, 1992. find
  41. Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed representations of words and phrases and their compositionality. In Advances in neural information processing systems, pages 3111–3119, 2013. find
  42. Kevin R Moon, David van Dijk, Zheng Wang, Scott Gigante, Daniel B Burkhardt, William S Chen, Kristina Yim, Antonia van den Elzen, Matthew J Hirn, Ronald R Coifman, et al. Visualizing structure and transitions in high-dimensional biological data. Nature biotechnology, 37(12):1482–1492, 2019. find
  43. Sameer A. Nene, Shree K. Nayar, and Hiroshi Murase. Columbia object image library (coil-20. Technical report, 1996. find
  44. Sameer A. Nene, Shree K. Nayar, and Hiroshi Murase. object image library (coil-100. Technical report, 1996. find
  45. Karolyn A Oetjen, Katherine E Lindblad, Meghali Goswami, Gege Gui, Pradeep K Dagur, Catherine Lai, Laura W Dillon, J Philip McCoy, and Christopher S Hourigan. Human bone marrow assessment by single cell rna sequencing, mass cytometry and flow cytometry. bioRxiv, 2018. find
  46. Jong-Eun Park, Krzysztof Polanski, Kerstin Meyer, and Sarah A Teichmann. Fast batch alignment of single cell transcriptomes unifies multiple mouse cell atlases into an integrated landscape. bioRxiv, page 397042, 2018. find
  47. Jose Daniel Gallego Posada. Simplicial autoencoders. 2018. find
  48. Emily Riehl. A leisurely introduction to simplicial sets. Unpublished expository article available online at http://www. math. harvard. edu/˜ eriehl, 2011. find
  49. Emily Riehl. Category theory in context. Courier Dover Publications, 2017. find
  50. John W Sammon. A nonlinear mapping for data structure analysis. IEEE Transactions on computers, 100(5):401–409, 1969. find
  51. Josef Spidlen, Karin Breuer, Chad Rosenberg, Nikesh Kotecha, and Ryan R Brinkman. Flowrepository: A resource of annotated flow cytometry datasets associated with peer-reviewed publications. Cytometry Part A, 81(9):727–731, 2012. find
  52. David I Spivak. Metric realization of fuzzy simplicial sets. Self published notes, 2012. find
  53. Jian Tang. Largevis. https://github.com/lferry007/LargeVis, 2016. ↗
  54. Jian Tang, Jingzhou Liu, Ming Zhang, and Qiaozhu Mei. Visualizing large-scale and high-dimensional data. In Proceedings of the 25th International Conference on World Wide Web, pages 287–297. International World Wide Web Conferences Steering Committee, 2016. find
  55. Joshua B. Tenenbaum. Mapping a manifold of perceptual observations. In M. I. Jordan, M. J. Kearns, and S. A. Solla, editors, Advances in Neural Information Processing Systems 10, pages 682–688. MIT Press, 1998. find
  56. Joshua B Tenenbaum, Vin De Silva, and John C Langford. A global geometric framework for nonlinear dimensionality reduction. science, 290(5500):2319–2323, 2000. find
  57. Dmitry Ulyanov. Multicore-tsne. https://github.com/DmitryUlyanov/Multicore-TSNE, 2016. ↗
  58. Laurens van der Maaten. Accelerating t-sne using tree-based algorithms. Journal of machine learning research, 15(1):3221–3245, 2014. find
  59. Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(Nov):2579–2605, 2008. find
  60. Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-SNE. Journal of Machine Learning Research, 9:2579–2605, 2008. find
  61. John Williamson. What do numbers look like? https://johnhw. github.io/umap\_primes/index.md.html, 2018. find
  62. Duoduo Wu, Joe Yeong, Grace Tan, Marion Chevrier, Josh Loh, Tony Lim, and Jinmiao Chen. Comparison between umap and t-sne for multiplex-immunofluorescence derived single-cell data from tissue sections. bioRxiv, page 549659, 2019. find
  63. Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. CoRR, abs/1708.07747, 2017. — [arXiv:1708.07747](https://arxiv.org/abs/1708.07747) find
  64. Liu Yang and Rong Jin. Distance metric learning: A comprehensive survey. Michigan State Universiy, 2(2):4, 2006. find
  65. Lofti A Zadeh. Information and control. Fuzzy sets, 8(3):338–353, 1965. find