Who Counts as a Neighbour?

t-SNE & UMAP showed t-SNE's core habit: friends stay together. Before t-SNE draws anything, it writes down who counts as whose neighbour in the original data, as a table of numbers. The flat picture is then arranged so that its own neighbours match that table. In this problem you build the table.

Step 1: each point picks its neighbours. For point $i$ , every other point $j$ gets a weight that shrinks as the squared distance between them grows. How fast it shrinks is set by a width $\sigma_i$ that belongs to point $i$ :

w_{ij} = \exp\!\left(-\frac{\lVert x_i - x_j \rVert^2}{2\sigma_i^2}\right), \qquad p_{j \mid i} = \frac{w_{ij}}{\sum_{k \ne i} w_{ik}}

You can read $p_{j|i}$ as the chance that $i$ picks $j$ as its neighbour. A point never picks itself, and each point's chances add up to 1.

Step 2: choose each width by perplexity. One shared width would be unfair. A point in a dense crowd and a point out on its own need very different reach. So each point gets the width that gives it the same effective number of neighbours, called the perplexity:

\text{Perp}_i = 2^{H_i}, \qquad H_i = -\sum_{j \ne i} p_{j \mid i} \log_2 p_{j \mid i}

Any term with $p_{j|i} = 0$ counts as 0. If $i$ spread its chances evenly over 3 neighbours, its perplexity would be exactly 3. A wider $\sigma_i$ spreads the chances out and raises the perplexity. A narrower one concentrates them and lowers it. For every point, find the $\sigma_i$ whose perplexity matches the target to within $10^{-9}$ .

Step 3: make it symmetric. Point $i$ may like $j$ more than $j$ likes $i$ . t-SNE averages the two directions, and scales the result so the whole table adds up to 1:

P_{ij} = \frac{p_{j \mid i} + p_{i \mid j}}{2n}, \qquad P_{ii} = 0

Here $n$ is the number of points.

Task: write neighbour_affinities(points, perplexity). It returns $P$ as a list of $n$ lists, with every entry rounded to 4 decimal places.

points is a list of points. Each point is a list of numbers, and all points have the same length.
The target perplexity can always be reached for every point.

Who Counts as a Neighbour?

Examples

Hints