Quantifying Local and Global Fidelity of Nonlinear Embeddings
Organizations: Data Science and AI Innovation Laboratory, Baylor University, Waco, Texas, USA.
Abstract
Dimension reduction rests on a claim: t-SNE and UMAP preserve local structure, PCA global structure. Our DLP curve is the share of each point's k nearest neighbors a map keeps. Corrected for chance, it gives L at k=10 and G over 30 to 50% of the data, local and global fidelity. At the midpoint the curve is provably a rank correlation of distances. The LG reversal test decides, with a stated error rate, which of two maps is local and which global. On twelve datasets of up to 1.38 million points, G agrees with established global scores at 0.84 and 0.93, and the area under R_NX at 0.22 and 0.30. The entity fidelity E, read at each point's entity size, predicts which entities a map loses beyond L and G where entity sizes differ. In an agent memory of one million passages, t-SNE and PCA cross at 150,000 passages (p=2.6e-5).
Figures & tables
| Work | Local score | Global score | One statistic | Relative band | Proven meaning | Rate | Test |
|---|---|---|---|---|---|---|---|
| Our DLP curve 13 | over all , the curve every score here is read from | ||||||
| 15 | , mean , | , mean , | ✓ | ||||
| 17 | over all , area on a axis | ✓ | |||||
| DREAMS 18 | NN recall, | Spearman of distances | |||||
| This paper | , mean , | ✓ | ✓ | ✓ | ✓ | ✓ | |
| Profile score | Distance | Random-triplet accuracy |
|---|---|---|
| (exact) | 0.18 | 0.10 |
| Middle band, | 0.57 | 0.70 |
| Area under | 0.22 | 0.30 |
| , | 0.80 | 0.91 |
| , | 0.84 | 0.93 |
| , | 0.91 | 0.97 |
| Symbol | Meaning |
|---|---|
| , , | data point, its position in the map, number of points |
| , | reference dissimilarity of the data; Euclidean distance in the map |
| , | rank of point among the other points by distance from point |
| , | the nearest neighbors of point in the data and in the map |
| , | degree of locality preservation at , and its chance-corrected value |
| , | halves agreement of point , and its mean over points |
| Dataset | PCA | NPCA | t-SNE | t-SNE 200 | SR-tSNE2 | UMAP | PaCMAP | PCA | NPCA | t-SNE | t-SNE 200 | SR-tSNE2 | UMAP | PaCMAP |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Pathology-100K | 0.012 | 0.008 | 0.436 | 0.331 | 0.458 | 0.233 | 0.205 | 0.597 | 0.461 | 0.442 | 0.456 | 0.442 | 0.290 | 0.494 |
| SEA-AD (single cell) | 0.000 | 0.000 | 0.082 | 0.048 | 0.117 | 0.018 | 0.014 | 0.286 | 0.285 | 0.243 | 0.232 | 0.243 | 0.340 | 0.417 |
| Instacart (supply chain) | 0.001 | 0.001 | 0.102 | 0.057 | 0.123 | 0.009 | 0.004 | 0.213 | 0.211 | 0.236 | 0.254 | 0.236 | 0.221 | 0.268 |
| MS MARCO (agent memory) | 0.000 | 0.000 | 0.253 | 0.200 | 0.309 | 0.065 | 0.030 | 0.283 | 0.188 | 0.222 | 0.227 | 0.222 | 0.153 | 0.211 |
| MNIST | 0.007 | 0.008 | 0.377 | 0.289 | 0.390 | 0.153 | 0.103 | 0.301 | 0.266 | 0.187 | 0.205 | 0.187 | 0.106 | 0.117 |
| Dataset | Domain | Representation | ||
|---|---|---|---|---|
| Pathology-100K | Pathology | 100,000 | 768 | Phikon |
| SEA-AD (single cell) | Single cell | 1,378,211 | 50 | 50 PCs |
| Instacart (supply chain) | Supply chain | 195,827 | 2,000 | purchases |
| MS MARCO (agent memory) | Agent memory | 1,000,000 | 768 | BGE-base |
| MNIST | Vision | 70,000 | 784 | pixels |
| CIFAR-10 | Vision | 60,000 | 512 | ResNet-18 |
| Swiss roll | S-curve | Tree | |
|---|---|---|---|
| PCA | .41/.24 | .45/.29 | .10/.53 |
| NPCA | .41/.24 | .32/.13 | .07/.47 |
| KPCA | .41/.26 | .52/.52 | .01/.01 |
| LLE | .63/.60 | .55/.55 | .33/.57 |
| Isomap | .88/ .98 | .80/ .90 | .22/ .60 |
| t-SNE, PCA init | .85/.84 | .78/.85 | .51 /.55 |
| Dataset | PCA | NPCA | t-SNE | SR-tSNE2 | ||
| Pathology-100K | 0.012/0.597 | 0.008/0.461 | 0.436/0.442 | 0.458/0.442 | ||
| SEA-AD | 0.000/0.286 | 0.000/0.285 | 0.082/0.243 | 0.117/0.243 | ||
| Instacart | 0.001/0.213 | 0.001/0.211 | 0.102/0.236 | 0.123/0.236 | ||
| MS MARCO | 0.000/0.283 | 0.000/0.188 | 0.253/0.222 | 0.309/0.222 | ||
| MNIST | 0.007/0.301 | 0.008/0.266 | 0.377/0.187 | 0.390/0.187 | ||
| CIFAR-10 | 0.002/0.327 | 0.002/0.303 | 0.199/0.297 | 0.200/0.297 |
| Path | Value | sd | J | ||
|---|---|---|---|---|---|
| t-SNE, perplexity | 5 | 0.363 | 0.189 | 0.050 | 1,986 |
| 15 | 0.379 | 0.220 | 0.036 | 2,692 | |
| 30 | 0.370 | 0.218 | 0.038 | 3,424 | |
| 50 | 0.354 | 0.244 | 0.004 | 4,246 | |
| 100 | 0.315 | 0.234 | 0.007 | 7,164 | |
| 200 | 0.259 | 0.255 | 0.011 | 11,480 |
| B: PaCMAP | B: NPCA | B: PCA | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| UMAP | t-SNE | SR-tSNE2 | t-SNE | SR-tSNE2 | NPCA | |||||||
| Dataset | ||||||||||||
| Pathology-100K | 0.3 | 0.6 | 0.4 | 33.8 | 33.7 | |||||||
| SEA-AD | 1.0 | 0.9 | 0.9 | 34.5 | 34.5 | |||||||
| Instacart | 4.5 | 8.4 | 8.4 | 99.3 | 99.3 | |||||||
| MS MARCO | 0.7 | 1.1 | 1.1 | 64.6 | 64.6 | |||||||
| SE of | Size, jackknife | Size, independent | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Dataset | SD | jackknife | independent | Declared | ||||||
| Pathology-100K | +0.155 | 0.0029 | 0.0205 | 0.0019 | 0.00 | 0.00 | 0.06 | 0.14 | 1.00 | 0.101 (0.003) |
| SEA-AD | +0.043 | 0.0061 | 0.0441 | 0.0030 | 0.00 | 0.00 | 0.14 | 0.18 | 0.00 | 0.344 (0.008) |
| Instacart | -0.023 | 0.0025 | 0.0096 | 0.0018 | 0.00 | 0.00 | 0.14 | 0.08 | 0.00 | 0.986 (0.014) |
| MS MARCO | +0.061 | 0.0037 | 0.0125 | 0.0015 | 0.00 | 0.00 | 0.14 | 0.22 | 1.00 | 0.145 (0.006) |
| MNIST | +0.114 | 0.0048 | 0.0378 | 0.0031 | 0.00 | 0.00 | 0.10 | 0.28 | 1.00 | 0.190 (0.004) |
| Dataset | Question about fewer points: use the local map | Question about more points: use the global map | Crossover size |
|---|---|---|---|
| Pathology-100K | the tiles that resemble a tumor tile | the layout of the nine tissues | 10,040 tiles (4,210–15,870) |
| Pathology-7K | the tiles that resemble a tumor tile | the layout of the nine tissues | 776 tiles (387–1,165) |
| MS MARCO | the passages near a query and its retrieved set (t-SNE) | the topics of the memory and their distances (PCA) | 150,400 passages (79,100–221,700), t-SNE against PCA |
| 8-K | the filings near a new event (UMAP) | the topics of the memory (PCA) | 427 filings (226–628), UMAP against PCA |
| SEA-AD | t-SNE for the neighbors of a cell and for subtypes; the global gap of 0.044 between PCA and t-SNE stays within its sampling error ( ), and PaCMAP has the highest , 0.417, for the distances between cell types | ||
| Instacart | against PCA, t-SNE is more local by 0.080 and more global by 0.021; PaCMAP has the highest , 0.268, for the layout of segments | ||
| Variant | Default | mean | min | Distance | Triplets |
|---|---|---|---|---|---|
| , (default) | 1.000 | 1.00 | 1.00 | 0.84 | 0.93 |
| , | 0.982 | 0.83 | 0.43 | 0.80 | 0.91 |
| , | 0.979 | 0.89 | 0.52 | 0.91 | 0.97 |
| Midpoint | 0.957 | 0.79 | 0.24 | 0.94 | 0.98 |
| Middle band, | 0.752 | 0.15 | 0.81 | 0.57 | 0.70 |
Dimensionality Reduction
Dimensionality reduction maps high-dimensional data to compact representations for visualization, prediction, compression, and scientific modeling.
See all 159 papers