aiwiki.page
中文

t-SNE

t-SNE 是一种非线性降维方法,通过近似保留局部邻域的相似性来可视化高维数据。

28 个关键词2 个词条链接到这里AI 撰写
降维数据可视化机器学习表征学习无监督学习流形学习困惑度学生t分布t-SNE

t-SNE(t分布随机邻域嵌入)是一种非线性降维方法,主要用于在二维或三维空间中对高维数据进行数据可视化。它将观测之间的相似性表示为概率,并构造一种低维布局,使其中的相似性概率与原始概率近似匹配。t-SNE 由劳伦斯·范德马滕和杰弗里·辛顿于 2008 年提出,广泛应用于机器学习和探索性数据分析。它的主要优势是揭示局部邻域结构;对于图中相距很远的各组点,它们之间的距离、呈现出的大小以及组间空白通常都没有直接的定量解释。

目的与概念基础

一个观测可能由数百乃至数千个特征来描述,例如像素强度、测量值,或由表征学习模型生成的坐标。这样的观测无法直接在其原始空间中绘制出来。低维表示,也称为嵌入,为每个观测分配少量坐标,同时尝试保留某些特定关系。

t-SNE 属于无监督学习,因为其标准目标不需要类别标签。它也常被归入流形学习方法,尽管它并不要求对数据背后的流形建立显式模型。

t-SNE 并不保留所有成对距离,而是侧重于哪些观测彼此邻近。它先将距离转换为邻域概率,再调整图中的坐标,尽可能重现这些概率。得到的结果是对特定关系的可视化,而不是对原始几何结构的重建。

数学表述

设输入观测为 x1,…,xnx_1,\ldots,x_n,其低维坐标为 y1,…,yny_1,\ldots,y_n。标准表述采用欧几里得距离,不过具体实现也可以接受其他距离度量或预先计算的距离。

输入空间中的相似性

对于每个观测 xix_i,选择 xjx_j 作为邻居的条件概率为

pj∣i=exp⁡ ⁣(−∥xi−xj∥2/(2σi2))∑k≠iexp⁡ ⁣(−∥xi−xk∥2/(2σi2)),pi∣i=0.p_{j\mid i} = \frac{\exp\!\left(-\|x_i-x_j\|^2/(2\sigma_i^2)\right)} {\sum_{k\ne i}\exp\!\left(-\|x_i-x_k\|^2/(2\sigma_i^2)\right)}, \qquad p_{i\mid i}=0.

带宽 σi\sigma_i 针对每个观测分别选择。这样,邻域就能适应局部采样密度的差异。

带宽通常通过指定的困惑度来确定:

Perp⁡(Pi)=2H(Pi),H(Pi)=−∑j≠ipj∣ilog⁡2pj∣i.\operatorname{Perp}(P_i)=2^{H(P_i)}, \qquad H(P_i)=-\sum_{j\ne i}p_{j\mid i}\log_2 p_{j\mid i}.

困惑度可以理解为有效邻居数,而不是实际的邻居计数。算法会调整带宽,直到条件分布的困惑度近似达到指定值。

随后,将条件概率对称化:

pij=pj∣i+pi∣j2n.p_{ij}=\frac{p_{j\mid i}+p_{i\mid j}}{2n}.

令 pii=0p_{ii}=0,则这些联合概率在所有有序对上的总和为一。

嵌入中的相似性

在标准的二维表述中,嵌入相似性采用自由度为一的学生t分布:

qij=(1+∥yi−yj∥2)−1∑k≠l(1+∥yk−yl∥2)−1,qii=0.q_{ij} = \frac{(1+\|y_i-y_j\|^2)^{-1}} {\sum_{k\ne l}(1+\|y_k-y_l\|^2)^{-1}}, \qquad q_{ii}=0.

与用于输入相似性的高斯核相比,这种分布的尾部更重。因此,对于嵌入中距离适中的点,其相似性比采用高斯核时更高。

重尾有助于缓解拥挤问题:低维空间无法容纳一个高维点的所有中等距离邻居,并同时让它们保持相近的距离。t 分布允许将不相似的观测放得更远,同时让相邻的观测保持相对接近。

优化目标

t-SNE 最小化从输入相似性分布 PP 到嵌入分布 QQ 的KL散度:

C=DKL(P∥Q)=∑i≠jpijlog⁡pijqij.C=D_{\mathrm{KL}}(P\|Q) = \sum_{i\ne j}p_{ij}\log\frac{p_{ij}}{q_{ij}}.

这个损失函数是不对称的。对于 pijp_{ij} 较大的点对,如果赋予它很小的 qijq_{ij},就会受到很强的惩罚。因此,该目标会强烈抑制将输入空间中的邻居分开,但并不直接保留输入空间中的每一个较大距离。

对于标准核,梯度为

∂C∂yi=4∑j≠i(pij−qij)yi−yj1+∥yi−yj∥2.\frac{\partial C}{\partial y_i} = 4\sum_{j\ne i} (p_{ij}-q_{ij}) \frac{y_i-y_j}{1+\|y_i-y_j\|^2}.

优化过程可以理解为吸引与排斥相互作用之间的平衡。输入相似性较强的点对彼此吸引,而排斥相互作用则有助于防止整个布局坍缩。

坐标通常通过带有动量及其他数值调整的梯度下降来更新。由于目标函数是非凸的,不同的初始化方式和优化设置可能产生不同的布局。

参数与优化行为

有几项设置会显著影响结果。

困惑度。 较低的值侧重于较小的邻域和更精细的结构。较高的值会纳入更广的邻域,可能揭示更大尺度上的关系。没有任何单一取值适用于所有数据集,而且困惑度必须与观测数量相适应。

初始化。 坐标可以从较小的随机值开始,也可以从主成分分析嵌入开始。初始化会影响收敛情况以及最终图形的整体布局,但并不会因此使全局距离本身变得可靠。

早期夸大。 在优化的初始阶段,将输入亲和度 pijp_{ij} 乘以一个大于一的因子。这会暂时增强相似点之间的吸引力,帮助形成邻域分组。随后再恢复通常的亲和度。

学习率。 学习率控制坐标更新的步长。取值不当可能导致收敛缓慢、布局不稳定或构型失真。不同实现采用的数值约定有所不同,因此相同的参数值不一定意味着相同的行为。

优化时长与随机性。 迭代次数不足时,图形可能仍远未达到稳定解。随机初始化和近似邻居搜索过程还会引入额外的变动。固定随机种子可以提高特定计算环境下的可复现性,但不能证明某种解释是有效的。

这些设置是可视化过程的超参数,而不是由数据唯一推断出的特征。

数据准备与距离选择

t-SNE 基于提供给它的相似性进行运算。因此,其输出取决于预处理方式、保留的特征和距离度量。

当各特征的单位或数值范围不同时,欧几里得距离可能主要由其中少数特征决定。特征缩放会改变这些距离,进而改变 t-SNE 试图保留的关系。缩放并非中性操作:是否适当取决于特征的含义。

在应用 t-SNE 之前,通常会先使用主成分分析或相关方法,将高维数据降至一个中间维数。这可以减少计算量并抑制部分噪声,但也可能丢弃有意义的变化。

对于词嵌入或图像特征等学习得到的表征,嵌入反映的是该表征及其相似性度量,而不只是原始观测。视觉上明显分离的一组点,可能源于有意义的结构、技术伪影,也可能源于特征工程过程中的选择。

计算方法

直接实现会计算所有观测对之间的相互作用。因此,每次优化迭代的时间复杂度为平方级;若保留稠密的成对亲和度,所需存储空间也可能达到平方级。

以下几项进展使其能够实际处理更大的数据集:

  • Barnes–Hut t-SNE 使用空间树,对距离足够远的点组之间的排斥相互作用进行近似。在输出维数较低的典型条件下,力的计算复杂度约为 O(nlog⁡n)O(n\log n)。稀疏的输入亲和度也能降低吸引相互作用的计算成本。
  • 基于插值的方法(包括 FIt-SNE)通过网格插值和快速傅里叶变换来近似排斥相互作用。这些方法能显著降低大型数据集的优化成本。
  • 近似最近邻搜索 通过查找数量有限的潜在邻居,而不是计算每个点对,来降低构造输入相似性的成本。

这些加速方法引入了近似方案的选择。端到端运行时间还取决于输入维数、邻居搜索成本、困惑度、输出维数及硬件;仅仅加快力的计算,并不能使每个阶段都实现线性扩展。

图形处理器和经过优化的实现可以进一步加速。不同软件包在初始化、学习率约定、停止准则以及可用的近似方法方面有所差异。

应用

t-SNE 用于探索图像集合、文档表征、测量数据集,以及人工神经网络学习到的特征。它可以揭示局部分组、过渡结构、异常观测,以及标签与特征空间邻域之间可能存在的不一致。

在生物学研究中,一种常见应用是将高维基因表达测量数据可视化,其中包括单细胞数据集。在机器学习中,它常用于考察模型如何在内部潜在空间中组织观测。

这些应用都属于探索性分析。单凭一幅 t-SNE 图,无法确立类别边界、验证表征的有效性、证明模型的泛化能力,也无法确定所观察到的分组是由什么原因造成的。

解释与局限

偏重局部结构,而非全局几何

彼此邻近的点通常意味着它们在输入空间中相似,但邻域保留只是近似的。反过来,相距很远的点,其不相似程度未必与图中距离成正比。

在不同次运行中,远距离点组之间的相对位置可能发生显著变化,而许多局部邻域仍保持相似。整个布局的旋转、镜像反射和平移本身都没有内在意义。

点组大小和密度可能具有误导性

由于输入带宽会适应局部密度,t-SNE 无法可靠地保留密度或所占空间的体积。原始空间中紧凑、密集的一组点,在图中可能与更分散的一组点大小相近。因此,表观面积并不是变异程度的直接度量。

同样,组间空白的多少也不是对原始空间中分离程度经过标定的度量。

可见的点组不一定就是簇

t-SNE 本身不是聚类分析算法。它生成的是坐标,而不是具有统计依据的划分。邻域尺度或优化过程可能促使图中形成看似分离的岛状结构,而连续结构有时也会显得支离破碎。

在 t-SNE 坐标上应用K均值聚类等方法,是按照可视化中失真的几何结构来分组,而不一定依据原始数据中希望识别的结构。

嵌入对数据和设置敏感

改变困惑度、预处理方式、样本构成或初始化,都可能改变布局。添加或移除观测可能使已有点发生移动,因为目标函数依赖于整个数据集。

标准 t-SNE 为每个给定观测优化坐标,而不是学习从输入向量到输出坐标的通用映射。因此,它本身不具备样本外变换能力。扩展方法可以相对于固定嵌入放置新观测,或训练参数化映射,但这些方法会引入额外假设。

嵌入质量可以用基于邻域的指标来评估,例如可信度;该指标会惩罚那些在输入空间中相距很远、却在嵌入中成为邻居的点。这类指标评估的是关系保留的某些特定方面,而不是每一种视觉解释是否真实。

与其他方法的关系

t-SNE 源于辛顿和萨姆·罗韦斯于 2002 年提出的随机邻域嵌入。2008 年的 t-SNE 表述将对称联合相似性与重尾嵌入分布相结合,改善了优化行为并缓解了拥挤问题。此后的 Barnes–Hut 实现和基于插值的实现,将其实用范围扩展到了大得多的数据集。

与主成分分析不同,t-SNE 是非线性的,也不寻找方差最大的方向。PCA 提供可应用于新观测的线性变换,并支持解释方差的计算;标准 t-SNE 则不具备这两项能力。

均匀流形近似与投影是另一种广泛使用的非线性可视化方法。它优化的是另一种基于邻域的目标,常见实现还支持将新观测放入已有嵌入中。这两种方法都不保证忠实保留全局几何结构,也不能仅凭图中可见的分组就证明分组有效。

自编码器则通过重建目标来学习编码和解码函数。它们可以提供可复用的表征,但其训练目标不同于 t-SNE 对邻域概率匹配的明确侧重。