随机邻域嵌入：SNE 与 t-SNE

小象实战讲义 · 机器学习算法精讲

降维与可视化这条线，我们已经讲了 Isomap、讲了 LLE——这一节讲收官的一种：随机邻域嵌入（SNE，Stochastic Neighbor Embedding），以及它的集大成改进 t-SNE。它跟 LLE 的思路一脉相承，但把「邻居」从一个数个数的概念，变成了一个概率；最后我们还会看到，这门课走到的这一站，恰好是高维数据可视化今天仍然站在前沿的方法。

💡 核心导读

• 邻居不再数个数：LLE 要选「取 3 个还是 5 个近邻」；SNE 干脆用概率——每个点对所有数据点都有一个权重，越近权重越大，越远趋近于零。
• 优化目标一句话：让低维空间的相似度分布 $Q$ 去逼近高维空间的相似度分布 $P$——衡量两个分布的差距，用的正是 16.1 节的 KL 散度。
• KL 不对称的后果：「好朋友在新空间变陌生人」损失很大，「陌生人变好朋友」损失很小——于是远处的点都往中间挤，这就是拥挤问题（crowding）的来源之一。
• 高维的球：高维球体里均匀采样的点，几乎全都贴在表面上——维度越高数据越挤在壳层，这是拥挤问题的几何根源（有代码实验）。
• t 分布的长尾：把低维空间的相似度从正态分布换成自由度为 1 的 t 分布——同样的概率变化要「走更长的路」，近的点在低维被放得相对舒展，拥挤问题就此解开。

从 LLE 到 SNE：邻居不再数个数

先看一个应用。讲师展示了一组用 MNIST 手写数字数据集做的可视化：每个手写数字就是一幅图片——写「3」，有笔画的位置是 1、没写到的地方是 0；一张 $10 \times 10$ 的图就是 100 维空间的数据。把这 100 维的点映射到二维平面（这就是降维），用 SNE 得到的图里，0、2、5、9、7 这些数字各自聚成了分开的一团——高维数据的结构，肉眼就能看出来了。

讲 SNE 之前，先说它的来历：深度学习的 Geoffrey Hinton——SNE 也是他的工作，按讲师的记忆大约是 2002 年提出的。它的想法跟 LLE 类似，但不用线性关系，用概率关系。

回忆 LLE 的一个别扭之处：我们要为每个点 $x_i$ 找最近的几个邻居——那到底取几个？3 个还是 5 个？ 这本身就成了一个重要的参数。用概率的方式，就不用关心「到底取几个近邻」了：我们关心的是 $i$ 和 $j$ 的直接关系——对任何一个 $j$，不管它是不是最近的那几个，所有的数据都考虑进来，只是越远的贡献越小。$x_i$ 周围有 $x_1$ 到 $x_N$：近处的点权重大一点，远处的点（比如很远的 $x_5$）权重很小，但都在范围内。

怎么定义？根据距离，用指数函数。以 $x_i$ 为中心、$\sigma$ 为方差的一个正态分布：

$$p_{j|i} = \frac{\exp\left(-\dfrac{\Vert x_i - x_j \Vert^2}{2\sigma_i^2}\right)}{\sum_{k \neq i} \exp\left(-\dfrac{\Vert x_i - x_k \Vert^2}{2\sigma_i^2}\right)}$$

分子是 $x_i$ 与 $x_j$ 的距离经过负指数的折算；分母把到所有其他点的折算值累加——所以它是一个 normalized distance（归一化的距离）。图上看很直观：$x_m$ 离 $x_i$ 最近，则 $p_{m|i}$ 远大于 $p_{j|i}$；很遥远的某个 $x_l$，正态分布在那里几乎为零，$p_{l|i}$ 也就约等于 0。另外规定 $p_{i|i} = 0$——自己跟自己，就是一个 0，没有歧义。

低维的 Q：一样的配方，归一的方差

把 $x_i$ 映射到低维空间的 $y_i$，我们希望保留的关系是：所有的这套权重关系。于是在低维空间构造一个一模一样的 $q_{j|i}$——以 $y_i$ 为中心、$y_j$ 的折算距离，除以到所有 $y_k$ 的累加。有一点不同：低维空间里我们可以做归一化，所以把 $\sigma$ 去掉、默认方差为 1：

$$q_{j|i} = \frac{\exp\left(-\Vert y_i - y_j \Vert^2 / 2\right)}{\sum_{k \neq i} \exp\left(-\Vert y_i - y_k \Vert^2 / 2\right)}$$

这里值得跟 LLE 对照一下，讲师专门点过：LLE 是求最近的几个邻居之间的权重，而 SNE 求的是一个数据对几乎所有数据的权重——考虑的情况更完整。打个比方：LLE 会说「这几个是我最好的朋友」；SNE 不挑——我跟班上每一个同学都有一个权重，这个权重自动调整，代表每个同学对我的 contribution。

那优化目标也很简单：使 $P$ 和 $Q$ 尽可能接近——$P$ 是高维空间里数据之间的关系，$Q$ 是低维空间里的关系；LLE 里要保的是那份 $W$，这里要保的是整个分布。而衡量两个概率分布相近程度的数学工具——大家还记得的话，就是 KL 散度（KL divergence）（16.1 节）：$\int p(x) \log \frac{p(x)}{q(x)} dx$，离散情形把积分换成加和。于是 SNE 的代价函数：

$$C = \sum_i \sum_{j \neq i} p_{j|i} \log \frac{p_{j|i}}{q_{j|i}}$$

最小化它，就是让 $q_{j|i}$ 不断逼近 $p_{j|i}$、两个概率分布越来越相近。

KL 的不对称：朋友变陌生人，损失大

用 KL 做代价函数，马上会撞上一个我们已经知道的性质：KL 不对称——$KL(P\Vert Q)$ 根本不等于 $KL(Q\Vert P)$（一个是 $p \log \frac{p}{q}$、一个是 $q \log \frac{q}{p}$，被积函数都不同）。落到这个场景里，不对称会造成一个不均衡的损失，讲师花了很长时间把这件事掰开揉碎：

方向一：本来近的，映射变远了。 高维空间里 $x_i$、$x_j$ 很近，$p_{j|i}$ 比较大；映射到低维后距离拉大了，$q_{j|i}$ 变小。此时 $\log \frac{p_{j|i}}{q_{j|i}}$ 是大数除以小数，再被大的 $p_{j|i}$ 一乘——损失很大。

方向二：本来远的，映射变近了。 $p_{j|i}$ 本来就小，就算 $q_{j|i}$ 变得很大、对数项变成负的，整个乘积也大不起来——损失非常小。

讲师的原话可以背下来：「关系好的两个朋友，在新的空间里变成陌生人，这个损失是比较大的；但本来是陌生人，映射成新的关系里变成好朋友了，那这个没什么大的问题，损失比较小。」

把优化过程推演下去，趋势就很清楚了：既然「把远点拉近」几乎不罚，「把近点推远」罚得很重，那么所有的点都会尽量往中间集中——远方的点判错一点没关系，可以尽量往中间聚；而近的点绝不敢往远处扩散，一扩散损失就大。整个低维空间里，点会越挤越拢。

拥挤的几何根源：高维的球

上面是 KL 不对称带来的「挤」。拥挤问题（crowding）还有一个更深层的几何根源，讲师用一个小实验讲透了——在高维空间里，圆和球有不一样的脾气。

先想清楚「圆」的推广：一维空间里的「圆」是什么？是一条线上到圆心距离相等的点的集合——就是两个点。二维空间是圆，三维空间是球，如此往高维延伸。

现在做实验：在二维的圆里均匀地随机取点，再在三维的球里均匀取点……看这些点到圆心的距离分布成什么样。用代码直接跑（在 $m$ 维单位球内均匀采样 2000 个点，统计平均距离、以及落进最外壳层 $r > 0.9$ 的比例）：

import random

print("m 维单位球内均匀采样 2000 个点, 看它们到球心的距离:")
for m in (2, 3, 5, 8, 100):
    rng = random.Random(42)
    rs = [rng.random() ** (1.0 / m) for _ in range(2000)]  # 均匀球内采样点半径 = U^{1/m}
    mean_r = sum(rs) / len(rs)
    shell = sum(1 for r in rs if r > 0.9) / len(rs)
    print("维度 m=%3d | 平均距离=%.4f | 落在最外 10%% 壳层(r>0.9)的比例=%.1f%%" % (m, mean_r, shell * 100))

m 维单位球内均匀采样 2000 个点, 看它们到球心的距离:
维度 m=  2 | 平均距离=0.6723 | 落在最外 10% 壳层(r>0.9)的比例=18.7%
维度 m=  3 | 平均距离=0.7550 | 落在最外 10% 壳层(r>0.9)的比例=27.2%
维度 m=  5 | 平均距离=0.8371 | 落在最外 10% 壳层(r>0.9)的比例=41.5%
维度 m=  8 | 平均距离=0.8916 | 落在最外 10% 壳层(r>0.9)的比例=58.4%
维度 m=100 | 平均距离=0.9904 | 落在最外 10% 壳层(r>0.9)的比例=100.0%

结果跟讲师口头描述的完全一致：$m=2$（圆）的时候取得还算均匀，有近有远；$m=3$ 就已经很少有概率取到离圆心近的点了；$m=5$ 趋势加强；$m=8$ 时几乎取到的点都离圆心特别远、快到边缘了；到 $m=100$ 这样的高维——几乎所有的点都贴在球面上（落进最外 10% 壳层的比例达到 100%）。

这就是高维空间的一个神奇特性：球体的「质量」大量集中在表面。而真实的高维数据（尤其某些流形）在高维空间里的分布本来就是非常聚集的——数据全都挤在薄薄一层壳上。再叠加上一节 KL 不对称把所有点往中间推的脾气——拥挤（crowding） 就此成形：我们需要在低维空间里，把这些挤成一团的数据尽量分散开来，同时还不破坏它们该保的特性。

换 t 分布：长尾的从容

怎么解？先看正态分布的一个弱点。给一组集中分布的数据，配一条正态曲线，本来是很不错的——所有数据都在分布的范围之内。可一旦数据里混进一个 outlier（离群的错误点），再想用一条正态分布同时满足所有数据，整条曲线就被这一个点拉偏了：中心挪了、形状胖了——一个 outlier 对整体的影响特别大。

我们其实还学过另一种分布：t 分布（Student t distribution）——检验统计量的老朋友（正态对上卡方，比值就是 t；概率书和统计书里都有）。t 分布有不同的自由度，它的一大好处就是能容忍这些离群的点：数据集中时它跟正态分布相当接近；有 outlier 的时候，t 分布还稳稳待在原地，正态分布已经跑偏了。凭什么是它？因为 t 分布是长尾（long tail）分布：在很小概率的地方，它仍然保留着一份不小的概率。看数值对比（正态取 $\exp(-d^2/2)$，t 取自由度 1 的 $(1+d^2)^{-1}$）：

import math

print("距离 d | 高斯 exp(-d^2/2) | t(自由度1) (1+d^2)^{-1}")
for d in (0.5, 1.0, 2.0, 3.0, 4.0, 6.0, 8.0):
    g = math.exp(-d * d / 2)
    t = 1.0 / (1.0 + d * d)
    print("%6.1f  | %.6f | %.6f" % (d, g, t))

print()
print("要降到同样的相似度 0.1, 各需要走多远:")
print("  高斯:    d = %.4f" % math.sqrt(-2 * math.log(0.1)))
print("  t(df=1): d = %.4f" % math.sqrt(1.0 / 0.1 - 1.0))

距离 d | 高斯 exp(-d^2/2) | t(自由度1) (1+d^2)^{-1}
   0.5  | 0.882497 | 0.800000
   1.0  | 0.606531 | 0.500000
   2.0  | 0.135335 | 0.200000
   3.0  | 0.011109 | 0.100000
   4.0  | 0.000335 | 0.058824
   6.0  | 0.000000 | 0.027027
   8.0  | 0.000000 | 0.015385

要降到同样的相似度 0.1, 各需要走多远:
  高斯:    d = 2.1460
  t(df=1): d = 3.0000

对照讲师课堂上的口头数字：正态分布「过了 4 几乎就是 0」——表里 $d=4$ 时只剩 0.000335；t 分布「过了 6、甚至到 8，还有 0.03、0.02 左右的概率」——表里 $d=6$ 是 0.027027、$d=8$ 是 0.015385，几乎逐字兑现。往回看更关键的一行：要降到同样的相似度 0.1，高斯走到 $d=2.15$ 就够了，t 分布要走到 $d=3.00$。

这就给出了 t 分布解决拥挤问题的机制：想让 $q$ 产生同样一点变化，t 分布需要「走很长的路」；而正态分布稍稍一移动，概率就剧烈变化。 于是：高维空间里靠得很近的一组点，映射到用 t 分布描述的低维空间后，它们之间的距离会相对舒展开一些（走远一点，相似度才掉得下来），数据之间的差别也就更明显——做 visualization 更清楚，拥挤问题就此解开。

所以 t-SNE 把低维空间的 $q$ 整个换成 t 分布——自由度取 1：

$$q_{ij} = \frac{\left(1 + \Vert y_i - y_j \Vert^2\right)^{-1}}{\sum_{k \neq l} \left(1 + \Vert y_k - y_l \Vert^2\right)^{-1}}$$

两个改进，一个新名字

把 SNE 到 t-SNE 的两处改动收拢：

改动一（治不对称）：原先的条件概率 $p_{j|i}$ 是非对称的，重新构造一个两者之间的量：

$$p_{ij} = \frac{p_{j|i} + p_{i|j}}{2}$$

（论文里的完整版还会再除以 $n$ 做全局归一化、让所有 $p_{ij}$ 加起来等于 1——这个常数因子不影响优化的方向，口播时省略了。）由此 KL 那一侧的不均衡得到缓解。

改动二（治拥挤）：低维空间的分布从正态换成自由度为 1 的 t 分布（上一节的 $q_{ij}$ 公式）。

命名也随之清楚：用条件概率直接构造、最小化 KL 散度的，叫 SNE（stochastic neighbor embedding）；引入对称的 $p_{ij}$、又把低维换成 t 分布的，就是新算法 t-SNE（t-distributed SNE）。

效果怎么样？讲师放了一组对比图（都是公开的经典实验图）：SNE 的结果（Hinton 他们提出时的图）已经把 MNIST 的数字分得不错；再看别的数据集——用 Isomap，有好多区域重叠（overlap）夹在一起；用 LLE（这是在 COIL-20 数据集上的结果），也没区分得那么好；还有一种 Sammon mapping（讲师没讲过，「就不用说了」）也比较乱；而 t-SNE 的结果「超级好」：聚成非常清晰的小团，红一片黑一片泾渭分明。到今天，t-SNE 仍然是高维流形降维、可视化领域最好的办法之一（前沿方法）——算法、代码、论文，网上都很多。

降维全景：这一程的地图

到这里，流形学习的主要部分讲完了。讲师最后把整条降维线收了一遍，值得完整记下——

线性降维：PCA 也好、SVD 也好，都是用一个线性的矩阵，把数据降到低维度。

非线性降维：LLE、Isomap、SNE——想法惊人的相似，一句话：高维空间里数据的特性，在低维空间要保留。差别只在「保的是什么关系」：

• Isomap：我周围有几个最近邻，到了下边（低维）还是那几个最近邻；
• LLE：我跟最近邻的关系保持一样——跟他好的程度是 0.5、跟他好是 0.3，低维空间同样要满足这种配比；
• SNE：不只是最近的那几个了——用概率的方式，我跟班上所有同学都有一个自动调整的权重，代表每个人对我的 contribution。

SNE 后来被发现有两个大问题：一是不对称（根子是 KL 距离不对称）；二是特别拥挤（高维球的实验告诉我们，高维数据的分布本来就非常聚集）。解法就是上面两处改动：对称化 $p_{ij}$，低维换长尾的 t 分布——把挤在一起的数据变稀疏一些，还保持住特性——这就是 t-SNE。

最后退一步看这一整段（也是无监督学习这一程的定位）：我们再不做分类，也没有做任何预测——做的事情是对整个数据的分析：把高维空间里冗余的维度去掉，映射到低维空间，可以线性，也可以非线性。

📝 动手练一练

1. 概念辨析：从 SNE 到对称 SNE 再到 t-SNE，每一步各改了什么？各自解决的是什么问题？哪一个问题是从 KL 散度「继承」来的、哪一个是从高维几何「继承」来的？

2. 代码实验：t 分布有不同的自由度，尾巴的长短也随之变化。算一算：要降到同样的相似度 0.1，高斯、$t(\text{df}=1)$、$t(\text{df}=2)$、$t(\text{df}=5)$ 各需要走多远？随着自由度增大，t 分布的尾巴在往哪个方向变、极限趋近于谁？

# 为保证本块可独立运行, 重写相似度与反解距离
import math

target = 0.1
print(f"要降到相似度 {target}, 各需要走多远:")
print("  高斯:        d = %.4f" % math.sqrt(-2 * math.log(target)))
for df in (1, 2, 5):
    d = math.sqrt(df * (target ** (-2.0 / (df + 1)) - 1.0))
    print("  t(df=%d): d = %.4f" % (df, d))

要降到相似度 0.1, 各需要走多远:
  高斯:        d = 2.1460
  t(df=1): d = 3.0000
  t(df=2): d = 2.6987
  t(df=5): d = 2.4025

本章小结

这一节补完了降维工具箱的最后一块。SNE 的立意：不再数「几个近邻」，用正态分布把每个点对所有点的相似度都算出来，高维一份分布 $P$、低维一份分布 $Q$（方差归一），优化目标就是让 $Q$ 逼近 $P$——工具是 KL 散度。两个病灶：KL 不对称（朋友变陌生人损失大、陌生人变朋友损失小，远点全往中间挤）+ 高维几何（均匀采样的高维球，点几乎全贴在表面——数据本来就挤）；两者合谋造成了拥挤问题。两剂药：对称化 $p_{ij}=(p_{j|i}+p_{i|j})/2$ 治不对称；低维换自由度 1 的 t 分布治拥挤——同样的相似度变化，t 分布要走约 1.4 倍的路（0.1 的相似度：高斯 2.15、t 走 3.00），挤在一起的点得以舒展，可视化效果「超级好」。收尾的地图值得记：线性（PCA/SVD）到非线性（Isomap/LLE/SNE），想法惊人地一致——高维数据的特性，低维要保留；而无监督学习这一程，不做分类、不做预测，做的是把数据看清楚。

📋 行动清单

• 一句话谱系：合上讲义，把 Isomap、LLE、SNE 各自「保什么」用一句话说出来，再说出 SNE 的两处改动各治什么病。
• 跑改球实验：把高维球代码的维度改成 20、50，观察平均距离和壳层比例的变化节奏。
• 复述金句：用「朋友/陌生人」的语言，向同学解释 KL 不对称为什么导致拥挤。
• 看一眼原作：检索 t-SNE 的原始论文和开源实现，对照本节的 $p_{ij}$、$q_{ij}$ 公式（讲师说：网上很多）。

—— 小象教研组