TriMap: Large-scale Dimensionality Reduction Using Triplets
Ehsan Amid、Manfred K. Warmuth Google Research, Brain Team {eamid,
Abstract
We introduce “TriMap”; a dimensionality reduction technique based on triplet constraints, which preserves the global structure of the data better than the other commonly used methods such as t-SNE, LargeVis, and UMAP. To quantify the global accuracy of the embedding, we introduce a score that roughly reflects the relative placement of the clusters rather than the individual points. We empirically show the excellent performance of TriMap on a large variety of datasets in terms of the quality of the embedding as well as the runtime. On our performance benchmarks, TriMap easily scales to millions of points without depleting the memory and clearly outperforms t-SNE, LargeVis, and UMAP in terms of runtime.
中文速览
现有的降维可视化方法（如 t-SNE、UMAP）擅长保留数据的局部邻域结构，却往往打乱了不同聚类之间的整体相对位置，也缺乏一个能客观衡量这种"全局结构"好坏的指标。为此，作者提出了 TriMap 方法：以三元组约束（triplet constraint）——即"点 i 比点 k 更靠近点 j"——作为优化信号，从 PCA 初始化出发，通过带权重的梯度下降迭代调整低维嵌入，同时还设计了一个"全局得分"（Global Score, GS）来量化嵌入在多大程度上还原了高维数据的整体布局。实验表明，TriMap 在全局结构保留上明显优于 t-SNE、LargeVis 和 UMAP，局部精度也相当，且运行速度更快——在约 170 万点的数据集上仅需约 1.3 小时，而 UMAP 超过 12 小时限制仍未完成。这项工作填补了非线性降维方法在全局结构保真与大规模可扩展性上的双重空白，为数据可视化提供了更可靠的工具。
原文 arXiv:1910.00204;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1910.00204v2