aiwiki.page
中文
计算机 / 人工智能 / t-distributed-stochastic-neighbor-embedding

t分布随机邻域嵌入

t分布随机邻域嵌入是一种非线性降维方法,通过在低维表示中保留局部相似关系,实现高维数据的可视化。

23 个关键词2 个词条链接到这里AI 撰写
降维数据可视化机器学习无监督学习流形学习主成分分析困惑度学生t分布t分布随机…

**t分布随机邻域嵌入(t-SNE)**是一种降维方法,主要用于在二维或三维空间中对高维数据集进行数据可视化。它将观测样本之间的相似性表示为概率,并寻找一种低维布局,使其中的相似性概率接近原始数据中的相似性概率。该方法由劳伦斯·范德马滕和杰弗里·辛顿于2008年提出,广泛应用于机器学习和探索性数据分析。它的主要优势是揭示局部邻域结构;对于相互分离的群组之间的距离、群组大小以及图中显现的间隙,则需要更谨慎地解读。

背景与目的

高维观测样本可能描述图像、文档、基因表达谱,或模型学习到的表示。每个样本可能包含数百乃至数千个数值特征,因此难以直接进行可视化。

t-SNE属于无监督学习,因为其标准形式不需要类别标签。它通常被归入流形学习技术,尽管它并不要求对潜在流形建立显式的数学模型。

该方法以辛顿和萨姆·罗韦斯于2002年提出的随机邻域嵌入(SNE)为基础。SNE以概率形式表达邻域关系,并通过优化低维表示来重现这些关系。t-SNE将高维空间中的对称亲和度与嵌入空间中的重尾分布相结合。这些选择使优化形式更为简单,也有助于缓解拥挤问题:在维度低得多的空间中,无法让所有在高维空间中具有中等间距的点都保持相应的距离。

主成分分析(PCA)构建线性方向,依次使投影方差最大化;与之不同,t-SNE直接优化各个观测样本的位置。因此,它的坐标轴并不对应原始特征的固定组合。

数学表述

设输入数据集包含 nn 个观测样本,

x1,…,xn∈RD,x_1,\ldots,x_n\in\mathbb{R}^{D},

其嵌入坐标为

y1,…,yn∈Rd,y_1,\ldots,y_n\in\mathbb{R}^{d},

其中 dd 通常为2或3。

高维亲和度

对于每个观测样本 xix_i,t-SNE定义另一个观测样本 xjx_j 是其邻居的条件概率:

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

样本与自身的亲和度设为零。带宽 σi\sigma_i 针对每个观测样本分别调整,使邻域尺度能够适应局部密度的差异。

这些条件概率经过对称化处理:

pij=pj∣i+pi∣j2n,pii=0.p_{ij} = \frac{p_{j\mid i}+p_{i\mid j}}{2n}, \qquad p_{ii}=0.

得到的亲和度满足

∑i≠jpij=1.\sum_{i\ne j}p_{ij}=1.

标准形式采用欧几里得距离的平方。具体实现也可以使用其他距离度量或预先计算的相异度,这会改变所保留邻域的含义。

困惑度

每个观测样本的带宽通常通过匹配用户指定的困惑度来选取:

Perp⁡(Pi)=2H(Pi),\operatorname{Perp}(P_i)=2^{H(P_i)},

其中

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

困惑度可以理解为有效邻居数。它并非一个严格限定的邻居数量:亲和度仍然是加权的概率。

较小的困惑度强调非常局部的关系,较大的值则纳入更广的邻域。通常可以从约5至50的取值开始尝试,但合适的尺度取决于数据集的大小和结构。设定的困惑度必须小于观测样本数;对于定义在其余观测样本上的条件分布,其理论最大值为 n−1n-1。

低维亲和度

在嵌入空间中,t-SNE采用基于自由度为1的学生t分布的核函数:

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

这个核函数的尾部比高斯分布更重。因此,不相似的观测样本可以被放置在相距较远的位置,而它们的低维亲和度不会像使用高斯核时那样变得极小。这有助于为局部邻域腾出空间,减轻拥挤现象。

目标函数

嵌入过程最小化从高维亲和度分布 PP 到低维分布 QQ 的KL散度:

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

这个损失函数是不对称的。对于 pijp_{ij} 较大的一对样本,如果其嵌入亲和度 qijq_{ij} 变得很小,就会受到很大的惩罚。对于 pijp_{ij} 很小的样本对,其对损失的直接贡献相对较小,但所有点仍通过 QQ 的归一化相互耦合。

因此,该目标强调保留重要的邻居,而不是保留每一对样本之间的距离。它既不保证精确保留邻域,也不保证忠实反映全局几何结构。

对于标准形式,梯度为

∂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+\lVert y_i-y_j\rVert^2}.

这一梯度可以理解为两类相互作用:与高维亲和度相关的吸引作用,以及由嵌入分布产生的排斥作用。

优化与参数

t-SNE求解的是一个非凸的数学优化问题,通常使用带动量的梯度下降或相关更新规则。不同的初始坐标和优化设置可能产生不同的布局。

重要设置包括:

  • **困惑度:**控制高维邻域模型的尺度。
  • **初始化:**初始坐标可以是较小的随机值,也可以是经过缩放的PCA投影。PCA初始化可以提高可复现性,并保留更多大尺度结构,但不能保证全局保真度。
  • **学习率:**控制更新步长。选择不当可能导致收敛缓慢或布局失真。不同软件包采用的数值约定有所不同。
  • **早期夸大:**暂时将产生吸引作用的亲和度乘以一个大于1的因子。这会增强优化初期的吸引力,有助于形成彼此分离的群组。
  • **迭代次数和停止准则:**影响优化是否已充分稳定,从而适合进行解读。
  • **随机种子:**控制初始化等随机因素,并可能影响最终布局。

早期夸大是一个优化阶段,并不意味着最终嵌入采用了另一种概率模型。后续迭代通常优化未经夸大的目标函数。

固定随机种子可以提高某一特定计算配置下的可复现性,但这并不能证明其布局由数据唯一决定。比较不同参数选择下的布局,有助于判断哪些视觉关系是稳定的。

计算方法

精确方法计算所有观测样本对之间的相互作用。每次优化迭代的成对计算大约需要 O(n2)O(n^2) 时间,而显式存储稠密亲和度需要 O(n2)O(n^2) 内存。这些开销限制了它在大型数据集上的应用。

若干近似方法可以提高可扩展性:

  • **稀疏亲和度:**仅使用有限的一组邻近观测样本来近似高维亲和度,这些样本通常通过近似最近邻搜索获得。
  • **Barnes–Hut t-SNE:**利用空间树将远处的点分组,以近似长程排斥作用。在典型的低维设置下,这可以将力的计算开销降低至接近 O(nlog⁡n)O(n\log n)。
  • **基于插值的t-SNE:**FIt-SNE等方法将相互作用插值到网格上,并使用快速傅里叶变换来加速排斥作用的计算。
  • **硬件加速:**具体实现可以利用并行计算和图形处理器。

这些方法是对部分计算进行近似,而不只是更快地执行精确方法。其精度和运行时间取决于实现设置、数据规模以及嵌入维数。

应用与预处理

t-SNE常用于探索以下数据:

在表征学习中,t-SNE图可以显示具有相同标签的观测样本是否位于相邻区域。标签可以用于为结果着色,而不参与嵌入计算。这种视觉上的分离具有描述性,并不是对预测性能的独立衡量。

预处理会显著影响结果,因为它决定了用于构建亲和度的距离。特征缩放、归一化、特征选择以及距离度量的选择,都可能大幅改变邻域。

对于高维稠密数据,通常会在t-SNE之前应用PCA,以减少噪声和计算开销。这也会改变t-SNE能够利用的信息:预处理过程中丢弃的结构无法通过嵌入恢复。

解读与局限

局部结构不等于全局几何结构

t-SNE图中相邻的点旨在反映所选输入表示中的邻域关系。然而,相距很远的群组之间的距离通常不能解释为与其原始相异度成比例。

视觉上较大的间隙并不能证明两个群体在原始空间中截然分离。反过来,图中相邻的群组在原始距离度量下也未必互为最近的群组。

群组大小与密度可能产生误导

由于t-SNE会在局部自适应地调整带宽,它可能扩张密集区域并压缩稀疏区域。因此,群组所占的面积不能可靠地反映其原始方差、密度或内在延展范围。

形状、空白区域以及相对布局也取决于困惑度、优化过程、采样和预处理。有些看似独立的群组可能反映的是这些选择,而不是数据中稳健的划分。

可视化不等于聚类

t-SNE生成的是坐标,而不是聚类归属。视觉上彼此分离的岛状区域本身并不能证明存在离散类别;在某些设置下,连续数据也可能呈现碎片化外观。

对t-SNE坐标应用K均值聚类或其他聚类方法,分析的是嵌入空间的几何结构,而它可能与原始几何结构有很大差异。要得出定量结论,需要视觉分离之外的证据。

坐标轴没有固有的语义

平移、旋转和镜像反射不会改变目标函数所使用的成对距离。因此,水平轴和垂直轴通常没有内在含义。它们的方向通常不能解释为某个特征、主成分或有序的生物学变量。

新观测样本需要额外机制

标准t-SNE针对特定数据集优化坐标,并不会自动学习从输入特征到嵌入坐标的可复用映射。加入观测样本并重新运行算法,可能使先前已嵌入的点发生移动。

某些实现支持相对于固定的参考嵌入放置新观测样本。参数化t-SNE则学习一个显式映射,通常使用人工神经网络。这些扩展与原始非参数方法具有不同的性质。

与相关方法的比较

PCA提供线性投影,具有明确的方差解释方向,并可直接对新观测样本进行变换。它可能无法捕捉t-SNE能够呈现的非线性邻域关系。

**均匀流形近似与投影(UMAP)**也强调邻域关系,但采用不同的数学构造和目标函数。它通常支持高效地变换新观测样本。与t-SNE图一样,UMAP图也不会自动提供忠实的全局距离。

其他流形学习方法,如Isomap和局部线性嵌入,保留不同的结构性质,并对数据作出不同的假设。它们的输出回答的是不同的几何问题,而不是同一张映射图的可互换版本。

评估可以包括邻域重叠度量、可信度评分、多次运行之间的稳定性,以及与原始表示中的距离或标签进行比较。仅凭视觉效果醒目的布局,无法对底层结构进行定量验证。