\( \newcommand{\vect}[1]{\boldsymbol{\mathbf{#1}}} \newcommand{\mat}[1]{\boldsymbol{\mathbf{#1}}} \newcommand{\R}{\mathbb{R}} \newcommand{\E}{\mathbb{E}} \newcommand{\Prob}{\mathbb{P}} \newcommand{\T}{^{\top}} \newcommand{\norm}[1]{\lVert #1 \rVert} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\ihat}{\mkern1mu\hat{\boldsymbol{\imath}}\mkern2mu} \newcommand{\jhat}{\mkern1mu\hat{\boldsymbol{\jmath}}\mkern2mu} \newcommand{\pd}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\argmax}{\operatorname*{arg\,max}} \newcommand{\argmin}{\operatorname*{arg\,min}} \newcommand{\cdata}[1]{\class{c-data}{#1}} \newcommand{\cmodel}[1]{\class{c-model}{#1}} \newcommand{\ctruth}[1]{\class{c-truth}{#1}} \newcommand{\cgrad}[1]{\class{c-grad}{#1}} \newcommand{\closs}[1]{\class{c-loss}{#1}} \newcommand{\cparam}[1]{\class{c-param}{#1}} \newcommand{\csecond}[1]{\class{c-second}{#1}} \renewcommand{\,}{\mkern3mu} \)

ML03.6 · Manifold learning: t-SNE and UMAP

A free, illustrated module of 4 lessons and one interactive in ML03 Unsupervised Learning: Neighbourhood graphs and spectral embedding; From SNE to t-SNE; t-SNE in practice, and how to read it; UMAP.

ML03.6 L2 · Intermediate 4 lessons · about 120 min Live · in review

Part of ML03 Unsupervised Learning in the Machine Learning track.

A straight-line projection cannot unroll a rolled-up sheet or pull ten handwritten digits apart into ten islands. These four lessons trust only short distances instead. A neighbourhood graph and the eigenvectors of its Laplacian unroll the swiss roll and cluster the moons; t-SNE turns distances into neighbour probabilities and matches them with a heavy-tailed curve in the map; practice shows what such a picture can and cannot say; and UMAP lays out a fuzzy neighbour graph by sampling edges, fast enough for large data and able to place new points.

What you need first. PCA and classical multidimensional scaling (ML03.5), graph Laplacians (M03.9), nearest neighbours (ML01.3), gradient descent (ML01.5) and k-means (ML03.1). Entropy and the KL divergence are introduced as far as needed (M09 treats them in full).

Lessons

1. Neighbourhood graphs and spectral embedding ML03.6.1 30 min

   PCA cannot unroll a rolled-up sheet, because it trusts every straight-line distance. Join each point to its nearest neighbours only, and the bottom eigenvectors of the graph Laplacian lay the sheet out flat: Laplacian eigenmaps, spectral clustering and Isomap.

2. From SNE to t-SNE ML03.6.2 30 min

   Turn distances into neighbour probabilities, with a Gaussian whose width is set by the perplexity, and look for a map whose Student-t probabilities match them. Derive the t-SNE gradient line by line and read it as springs that pull and push.

3. t-SNE in practice, and how to read it ML03.6.3 30 min

   Run t-SNE from scratch with momentum and early exaggeration on 500 handwritten digits, match scikit-learn’s TSNE, and learn what a t-SNE picture cannot show: cluster sizes, gaps between clusters, and clumps in pure noise.

4. UMAP ML03.6.4 30 min

   UMAP builds a weighted nearest-neighbour graph with a local scale at every point, joins the two directions of each edge by a fuzzy union, and lays the graph out by stochastic gradient descent on a cross-entropy with negative sampling. Build a simplified UMAP and compare it with t-SNE.

The interactive

ML03.6-X1 · Live t-SNE. Run t-SNE in the page on a few dozen points (two clusters of different spread, three clusters at uneven distances, a line, uniform noise). Slide the perplexity from 2 to 50, step or play, switch early exaggeration on and off, and watch the map rearrange beside the data while the KL divergence falls. It lives in t-SNE in practice, and how to read it.