用 GPU 加速 TSNE：从几小时到几秒
- 2019 年 12 月 2 日
- 笔记
原标题 | Accelerating TSNE with GPUs: From hours to seconds
作 者 | Daniel Han-Chen
翻 译 | 人气呆毛选手、米粒_Melxy
审 校 | 鸢尾、唐里
图1. MNIST Fashion上的cuML TSNE需要3秒。 Scikit-Learn需要1个小时。
TSNE（T分布随机领域嵌入）是一种流行的无监督降维算法，其用途广泛，包括神经病学，图像相似性和可视化神经网络。 但它的最大缺点是在大多数可用的实现中处理时间很长。 RAPIDS现在基于CannyLab.开发的基于GPU的Barnes-Hut方法，提供了GPU加速的快速TSNE。 RAPIDS的cuML机器学习库中的TSNE的运行速度比相应的CPU处理快2,000倍，并且比当前GPU版本使用的GPU内存少30％。
该博客首先介绍一些用例示例，然后是将cuML的GPU TSNE实现与scikit-learn进行比较的基准测试。 然后，详细解释TSNE如何实现以及如何在cuML中对其进行优化，使其能在GPU上运行。
TSNE的应用
TSNE与传统的监督方法（例如线性回归和决策树）形成对比，因为它不需要标签。 TSNE试图通过移动相似点和相异点，使其互相远离来识别数据的结构。
图2.在时尚用例中使用的TSNE。
在图2中，TSNE被应用于由60,000件衣物图像组成的时装数据集。这对于将“相似”服装聚集的自然分组很有用。 TSNE能够将时装图像的复杂空间减小到较小的空间，从而更易于使用。每个图像的像素向量都用作输入，TSNE将其映射为2个维度，即每个图像映射为2个值。在图5中，根据原始输入的服装类别（例如靴子是蓝色）绘制了TSNE的二维输出并进行了颜色编码。 TSNE不知道这些类别，但是找到了一个能够将更多相似项放在一起的分组。
下图是使用MNIST数字数据集的示例。给定手写数字，任务是将每个数字分类为0、1、2等。在对所有60,000个数字图像应用TSNE之后，我们发现没有任何标签，TSNE设法分离数据。可以在图3中看到如何用数字类型（0到9）对清晰的簇进行颜色编码。
图3. MNIST数字数据集的TSNE图
TSNE还用于可视化卷积神经网络，以帮助从业者辨别复杂的分类器是否真正在“学习”。下图显示了TSNE应用于AlexNet，其中实际分类器（4096维）之前图像的CNN输出缩减为2维 ，然后显示实际的输入图像。 请注意，在图4中，相似的图像趋于接近，这意味着AlexNet如何将它们“视为”相似。
图 4. 来源: CS231n Convolutional Neural Networks for Visual Recognition
TSNE vs. Principal Component Analysis (PCA)
TSNE是一种非线性降维算法，而主成分分析是线性的。这意味着PCA的组成部分通常具有一定的含义，而TSNE不再按重要性排序，其创建的领域之外也不具有可解释性。在CPU上，通常建议用PCA将维度减小到50，然后再将其输入TSNE以提高性能。但GPU并非如此。
RAPIDS cuML Speed-Up over Scikit-Learn
许多数据科学家从scikit-learn流行的TSNE实现开始。 Scikit-learn的TSNE提供了熟悉的，易于使用的界面，但会遇到可伸缩性问题。 例如，一个60,000个示例数据集可能需要1个小时才能在CPU上的scikit-learn中收敛。 在但NVIDIA V100 GPU上运行的cuML TSNE可以在同一数据集上3秒内就可以完成收敛。
表1.在NVIDIA DGX-1上使用1个V100 GPU运行的cuML的TSNE时间。
注意表1中的对数log。
表2. cuML和Scikit-Learn（DGX 1）之间的时间间隔（以秒为单位）
因此cuML的TSNE运行速度提高了1000倍，并且获得了相似的可信度评分.
表3.显示了cuML在NVIDIA DGX 1上运行的scikit-learn的加速完整的过程图。
在具有204,800个样本和80个特征的数据集上，cuML需要5.4秒，而Scikit学习需要将近3个小时，加速了2,000倍。 而且还在仅使用一个V100 GPU（DGX1：32gb GV100 GPU，Intel Xeon E5–2698 v4 CPU @ 2.20GHz w / 20核和40个线程）的NVIDIA DGX-1机器上测试了TSNE。 数据传输时间也包括在此基准测试中。 图5显示了包含100个样本和80列的数据集。 请注意，即使在小型数据集上，cuML也可以更快。
图5.乳腺癌小型数据上的cuML TSNE（1秒）
使用上述PCA技巧确实使scikit-learn的TSNE的端到端性能稍有提高，但是，RAPIDS cuML TSNE仍在204,800个样本和50列的高数据集上展示了超过1,000倍的加速。 这使TSNE可以在数据集上进行训练，而无需首先使用PCA缩小维度。
TSNE如何起作用
cuML的TSNE主要基于CannyLab最初的Barnes Hut实现。当前，支持两种算法：Barnes Hut TSNE和Exact TSNE。 Barnes Hut的运行速度比Exact版本快得多，但准确性略低（错误率最多3％）。对于大型数据集（样本> = 2,000），建议使用Barnes Hut算法以提高速度。
TSNE有两个主要目标：
- 距离近的点应该保持近距离。
- 距离远的点应该保持远距离。
给定高维度设置（例如3D或1,000 D）中的某些数据点，目标是将这些点嵌入较低的空间（例如2维），以便保留输入数据的局部邻域结构可能以其嵌入式形式出现。
更具体地说，首先将原始高维空间中的点转换为看起来像钟形曲线或正态分布的概率密度，如下面的图6中的红线所示。 接近的点会彼此增加概率，因此密集区域往往具有更高的值。 同样，离群点和相异点的值也较小。
图6.来源：study.com
这是为什么TSNE名称中“ T分布”的来源。下部空间中的点也使用钟形曲线进行建模，尽管它像图6中的蓝线一样伸展。
人们尝试使用非扩展版本，但这会导致一个称为“拥挤问题”的问题，其中嵌入的点会聚在一起。
图7.左图显示了拥挤问题。 TSNE通过使用T分布解决了这一问题。
现在，想象一下弹簧将低维空间中的每个点连接到其他点。 想象以下情况：
- 原先接近的点将互相拖拉。 （吸引）
- 原本不相似的点将相互推动。 （排斥）
从本质上讲，我们的弹簧功能已经颠倒了。 人们会期望遥远的点会有弹簧将它们拉在一起，但在TSNE中则相反。
现在，释放低维空间中的弹簧，这是TSNE的优化阶段。 当所有弹簧停止运动时，我们终止了进化系统。 我们移除弹簧，每个点的终点变成最终的嵌入。
TSNE优化
可以使用四种优化来提高TSNE在GPU上的性能：
- 用更少的GPU内存计算更高的维度概率
- 近似高维概率
- 减少算术运算
- 沿行广播
优化 1 — 用更少的GPU内存计算更高维度的概率
还记得通过考虑其他每个点的影响来计算每个点的概率的目标吗？ 当A点对B点的影响与B点对A的影响不同时，它们是不对称的。 为了使它们相等，将两种贡献相加并在它们之间进行分配，这称为对称化概率。
最初，由于使用了不必要的中间存储缓冲区，对称化步骤效率很低。 在RAPIDS实现中，内存使用减少了30％，并且现在已高度并行化。 现在，在总运行时间中，对称化花费的时间为总运行时间的1％或更少，而以前为25％。
表4. GPU上每个内核的时序。对称化花费了总时间的1％。
为了实现此优化，我们首先使用快速cuML primitives将点之间的距离转换为COO（坐标格式）稀疏矩阵。稀疏矩阵格式擅长表示连接的节点和边的图。在k个最近邻图的情况下尤其如此，因为它们具有固定数量的连接边，因为只需要考虑每个点的最近邻。稀疏格式仅需要存储连接的顶点，从而为TSNE等算法提供了显着的加速和较低的存储开销。 COO格式由3个非常简单的数组表示：数据值（COO_Vals），列索引（COO_Cols）和单个行索引（COO_Rows）。
例如，假设有一个给定的点（0，7），其值为10。它的转置（或反向）为（7，0），也为10。这是如何将其存储在最终COO稀疏矩阵中的方法：
const int i = RowPointer[row]; COO_Vals[i] = val; COO_Cols[i] = col; COO_Rows[i] = row;
要使其转置或反转，只需像这样翻转col和row指针：
const int j = RowPointer[col]; COO_Vals[j] = val; COO_Cols[j] = row; COO_Rows[j] = col;
注意上面的示例还包含一个名为“ RowPointer”的数组。 COO布局不包括有关每一行的开始或结束位置的信息。 包含此信息使我们可以并行化查找，并在对称化步骤中快速求和转置后的值。 RowPointer的想法来自CSR（压缩稀疏行）稀疏矩阵布局。 在CSR布局中，entries是根据其所在的行进行索引的。例如，所有行索引为1的元素都以排好序的方式放置在RowPointer索引的开头。 CSR布局非常适合以行方式访问数据的算法。
结合这两种布局，我们可以将COO格式用于图形中每个元素的高效并行计算，而CSR格式用于执行元素的转置。 由于RowPointer包含每一行中存在的元素数，因此可以使用atomicAdd来并行汇总每对点的贡献。
const int i = atomicAdd(&RowPointer[row], 1); const int j = atomicAdd(&RowPointer[col], 1);
图8.运行中的对称内核的示意图。
图8显示了整个过程。 给定点（0，7）的值为10，对行指针进行索引以获取该点的行索引，并将其存储。然后，翻转至（7，0），访问行指针，并将其与第一个指针并行存储。
优化2-近似高维概率
TSNE的作者van der Maaten指出，与其计算所有点之间的全距离，不如计算最近邻并从中计算出高维概率。 cuML遵循CannyLabs使用Facebook的FAISS库在GPU上计算前k个近邻的方法。这样就从必须存储N²个元素减少到仅存储N* k个元素（N是数据采样数，k是近邻数）的概率计算。
优化3-减少算术运算
在许多TSNE的实现中，将吸引力计算（弹簧拉力）拆分为先在点A上，后在点B上进行计算。如果同时计算交互，而不是单独计算，TSNE的速度可以显著提高。这样可以将乘法和地址的数量，从原来的9个减少到大约4个，并使此计算速度提高50％。
优化4-逐行广播
图9.计算公共值并将其分布在每一行！
另一个基本优化是注意到行间重复了维度1中的点A，和维度2之间的距离。这意味着，不必为每个维度分别计算值，只需对它进行一次计算，然后广播并重新用于其他维度即可。这再次减少了算术运算，并进一步加快了TSNE的速度。这是许多CUDA算法（包括cuML中的许多算法）使用的通用技术。
改善TSNE的数值稳定性
在CannyLab的原始实现中，cuML修复了一些罕见的数字稳定性问题，包括一些死循环和越界的内存访问。此外我们还知道TSNE对它的超参非常敏感。 在cuML中提供了一种自适应学习方案，其中可以根据用户的输入数据来调整参数。
有时如果学习率太大，嵌入点可能会成为异常值。在cuML中指定了MAX_BOUND，它将小心地将异常值推回并重置所有动量变量。这也有助于提高TSNE的准确性和可信度。
我们如何在RAPIDS中运行TSNE？
让我们比较scikit-learn的API和RAPIDS cuML的API。 本示例使用scikit-learn的数字数据集。
scikit-learn API：
现在将其与cuML进行比较：
由于cuML几乎是scikit-learn的直接替代品，因此sklearn.manifold包可以替换为cuml.manifold，其他所有功能都可以使用。
这是一个Jupyter Notebook，展示了在Fashion MNIST数据集上的cuML TSNE的演示。
有关更多TSNE示例和对TSNE的数学优化的更深入了解，请在此处查看更多扩展的Jupyter Notebook。
在波士顿住屋数据集上使用cuML TSNE
结论
TSNE在实现非常大和很复杂的数据集可视化方面非常成功。它能够识别无标签数据集中的结构。然而它的最大缺点是执行时间慢。
借助新的RAPIDS TSNE实现可以将速度提高2,000倍，同时使用的GPU内存也会减少30％。提出您的想法并提供反馈。在此处的Google Colab实例上免费试用cuML TSNE。
TSNE参考文献
- David M. Chan, Roshan Rao, Forrest Huang, John F. Canny : t-SNE-CUDA: GPU-Accelerated t-SNE and its Applications to Modern Data https://arxiv.org/pdf/1807.11824.pdf [31 Jul 2018]
- George C. Linderman, Manas Rachh, Jeremy G. Hoskins, Stefan Steinerberger, Yuval Kluger: Efficient Algorithms for t-distributed Stochastic Neighborhood Embedding https://arxiv.org/abs/1712.09005 [25 Dec 2017]
- Laurens van der Maaten, Geoffrey Hinton : Visualizing High-Dimensional Data Using t-SNE https://lvdmaaten.github.io/publications/papers/JMLR_2008.pdf [2008]
via https://medium.com/rapids-ai/tsne-with-gpus-hours-to-seconds-9d9c17c941db
