Embedding cost

The question: how well does this projection do at what a particular method was trying to do?

These three are the objective functions of Sammon mapping, curvilinear component analysis and neighbour retrieval visualiser. Each weights distance error differently, and the weighting is the interesting part.

The measures

Writing $d_{ij}$ for the distance between two points in the data and $\hat{d}_{ij}$ for the distance in the projection, all three penalise the same error $d_{ij} - \hat{d}_{ij}$ and differ only in what they multiply it by:

▲ higher is better · ▼ lower is better · △▽ hollow: unbounded, so the number is comparable only between projections of the same data.

measure		weights errors by	range
sammonStress	▽	$1 / d_{ij}$ — short distances matter most	$[0, \infty)$
curvilinearStress	▽	$F(\hat{d}_{ij})$, a kernel on the projected distance	$[0, \infty)$
nerv	▽	a trade-off between missing and false neighbours, set by $\lambda$	$[0, \infty)$

$$\begin{aligned} \textbf{Sammon} \quad & \frac{\sum_{i<j} (d_{ij} - \hat{d}_{ij})^2 / d_{ij}}{\sum_{i<j} d_{ij}} \\[1.2ex] \textbf{CCA} \quad & \frac{\sum_{i<j} (d_{ij} - \hat{d}_{ij})^2 \; F(\hat{d}_{ij})}{\sum_{i<j} d_{ij}^2 \; F(\hat{d}_{ij})} \end{aligned}$$

The numerators are the published sums; the denominators are sickle’s, and make the values comparable across datasets. Both value fields are the ratio, so a number quoted here will not match a bare transcription of the classical formula. curvilinearStress also returns raw, the unnormalised numerator. Sammon skips pairs at $d_{ij} = 0$, which would divide by zero.

The difference between the two is worth stating plainly, and it is visible in which distance the weight depends on. Sammon weights by $d_{ij}$, the original distance: getting a genuinely-close pair wrong is expensive. CCA weights by $\hat{d}_{ij}$, the projected one: an error is only expensive if the points ended up drawn near each other. That makes CCA tolerant of tearing a manifold apart — which is the point, since a tear is often the only way to flatten something.

Using them

Sammon comes with the default pass. CCA needs its kernel width, NeRV is its own pass:

const a = analyze(hd, ld, { ccaLambda: 1 });

sammonStress(a.embedding).value;        // 0.0238
curvilinearStress(a.embedding).value;   // 0.5316

const p = nervPass(hd, ld, { lambda: 0.5, perplexity: 30 });
nerv(p).value;

blobs_pca, coloured by Sammon stress

An empty scatterplot.

Sammon stress

—

parameters

none

points

—

cost

O(1)

Class colour, not a measure — the thing to compare a per-point encoding against.

0.000 1.000

worsebetter

Sammon stress — per-point score. Each point's own score. These average to the reported value.

Fitted to this projection, from 0.000 to 1.000 — amber rather than purple for that reason. Colours are comparable inside this plot and nowhere else. Domain [0, ∞), higher is better.

Stress that weights short distances most heavily.

`ccaLambda` must be requested

curvilinearStress throws if the pass was not given a positive ccaLambda — omitting it and passing $\lambda \le 0$ both leave the accumulators off, and both raise the same error. There is no sensible default: $\lambda$ is the neighbourhood width in the units of your projection, so the library will not guess it.

ccaKernel picks $F$. The default "exponential" is $F(\hat{d}) = e^{-\hat{d}/\lambda}$, a smooth decay; "step" is the original bounded kernel, $F(\hat{d}) = 1$ for $\hat{d} \le \lambda$ and 0 beyond.

NeRV, and what λ does

NeRV frames the projection as an information retrieval problem: a viewer looking at the plot retrieves neighbours, and can make two kinds of mistake.

• $\lambda = 0$ — only false neighbours are penalised. Precision, $KL(q \| p)$.
• $\lambda = 1$ — only missing neighbours are penalised. Recall, $KL(p \| q)$. This is what SNE and t-SNE minimise.
• $\lambda = 0.5$ — the default here, both equally.

nerv() returns recall and precision alongside the combined value, so you can see which side the cost is coming from rather than only the total.

The per-point $\sigma$ is fitted in the high-dimensional space by bisection to match the requested perplexity, then reused for the projection — the paper’s formulation, and the reason this is the slowest pass in the library.

Per-point values

sammonStress and curvilinearStress have localKind: "sum" — the entries are contributions in the measure’s own units and add up to the total.

Both measures are lower is better and both entries are quantities of error, so a large entry does mean more of the distortion sits on that point: it is worth looking at. The converse is where these arrays mislead. A small entry says only that this measure is not charging for that point, and the weighting decides what counts. Sammon weights by $d_{ij}$, so a point flung a long way breaks pairs that were already distant and is charged little; CCA weights by $\hat{d}_{ij}$, so it forgives a tear outright. On a projection with six points teleported into the wrong class, curvilinearStress bills them 24× the average point and sammonStress only 4× — and Sammon ranks three of those six below average, because the pairs they broke were long ones.

The reading that survives both: a large entry is a lead, a small one is not an all-clear. Reading a score has the general form of this, for share as well as sum.

NeRV’s recall and precision are scalars — the mean per-point $KL(p \| q)$ and $KL(q \| p)$ over the dataset, not per-point arrays. What it does give per point is local, with localKind: "mean": each entry is that point’s own $\lambda \, KL(p_i \| q_i) + (1 - \lambda) \, KL(q_i \| p_i)$, so the entries average to the reported value and say which points are being misrepresented. The split by direction is only available in aggregate. The pass object also carries sigma, the fitted per-point bandwidth.

Cost

sammonStress and curvilinearStress are $O(1)$ read-outs. NeRV is $O(N^2 D)$ with a bisection per point on top, and benefits most from nervAsync.

Verification

All three are checked against the published definition, not against a reference implementation — there is no canonical one to compare against. Each is verified against an independent naive transcription of the formula in the test suite, and NeRV’s σ search is checked to produce exactly the requested perplexity. This is the second verification tier; see Verification.

References

• Sammon, IEEE Trans. Computers C-18 (1969) sammonStress
• Demartines & Hérault, IEEE Trans. Neural Networks 8 (1997) curvilinearStress
• Venna, Peltonen, Nybo, Aidos & Kaski, JMLR 11 (2010) nerv