随机邻居嵌入

随机邻居嵌入（Stochastic Neighbor Embedding, SNE）是降维和数据可视化领域最具革命性的算法之一。它由 Geoffrey Hinton（深度学习教父）和 Sam Roweis 于 2002 年提出。

虽然现在大家更熟知它的升级版t-SNE，但 SNE 才是真正的奠基流派。它的核心思想彻底改变了降维领域的游戏规则：将高维空间中的“欧氏距离”，转化为代表两点间相似度的“条件概率”。

1. 核心思想：概率化的“邻居关系”

传统的降维算法（如 PCA 或 MDS）试图在低维空间中硬生生地保持点与点之间的绝对距离（Euclidean Distance）。但高维数据往往是非线性的，这种生拉硬拽会导致严重的失真。

SNE 换了个思路：我不在乎绝对距离是多少，我只在乎你是不是我的亲密邻居。

• 在高维空间：以点x i x_ixi​为中心建立一个高斯分布。如果点x j x_jxj​离x i x_ixi​很近，那么x i x_ixi​挑选x j x_jxj​做邻居的概率p j ∣ i p_{j|i}pj∣i​就会很高；反之，如果离得很远，概率就会趋近于 0。
• 在低维空间：同样为映射后的点y i y_iyi​和y j y_jyj​建立高斯分布，计算出低维空间的邻居概率q j ∣ i q_{j|i}qj∣i​。
• 优化的目标：如果高维空间中x i x_ixi​和x j x_jxj​是亲密邻居（p j ∣ i p_{j|i}pj∣i​很大），那么在低维空间中，SNE 就会拼命拉近y i y_iyi​和y j y_jyj​的距离，让q j ∣ i q_{j|i}qj∣i​也变得很大。

2. 数学原理与代价函数

SNE 的目标是让低维空间的概率分布Q QQ尽可能逼近高维空间的概率分布P PP。为了衡量这两个概率分布之间的差异，SNE 引入了KL 散度（Kullback-Leibler Divergence）。

其代价函数（Loss Function）定义为所有点对的 KL 散度之和：

C = ∑ i K L ( P i ∣ ∣ Q i ) = ∑ i ∑ j p j ∣ i log ⁡ p j ∣ i q j ∣ i C = \sum_{i} KL(P_i || Q_i) = \sum_{i} \sum_{j} p_{j|i} \log \frac{p_{j|i}}{q_{j|i}}C=i∑​KL(Pi​∣∣Qi​)=i∑​j∑​pj∣i​logqj∣i​pj∣i​​

• 高维相似度（高斯分布）：

p j ∣ i = exp ⁡ ( − ∥ x i − x j ∥ 2 / 2 σ i 2 ) ∑ k ≠ i exp ⁡ ( − ∥ x i − x k ∥ 2 / 2 σ i 2 ) p_{j|i} = \frac{\exp(-\|x_i - x_j\|^2 / 2\sigma_i^2)}{\sum_{k \neq i} \exp(-\|x_i - x_k\|^2 / 2\sigma_i^2)}pj∣i​=∑k=i​exp(−∥xi​−xk​∥2/2σi2​)exp(−∥xi​−xj​∥2/2σi2​)​

(其中σ i \sigma_iσi​是由用户指定的困惑度 Perplexity 动态决定的方差。)

• 低维相似度（高斯分布）：

q j ∣ i = exp ⁡ ( − ∥ y i − y j ∥ 2 ) ∑ k ≠ i exp ⁡ ( − ∥ y i − y k ∥ 2 ) q_{j|i} = \frac{\exp(-\|y_i - y_j\|^2)}{\sum_{k \neq i} \exp(-\|y_i - y_k\|^2)}qj∣i​=∑k=i​exp(−∥yi​−yk​∥2)exp(−∥yi​−yj​∥2)​

(在低维空间，方差被固定为KaTeX parse error: Undefined control sequence: \ref at position 10: \frac{1}{\̲r̲e̲f̲{}}，无需引入额外变量。)

通过梯度下降（Gradient Descent）算法，低维空间中的点y yy会不断移动位置，直到代价函数C CC降到最低。

3. SNE 的非对称性：宁放过，勿贴贴

仔细观察 KL 散度的公式中关于惩罚系数的部分：p j ∣ i log ⁡ p j ∣ i q j ∣ i p_{j|i} \log \frac{p_{j|i}}{q_{j|i}}pj∣i​logqj∣i​pj∣i​​。由于这种非对称性，导致 SNE 在降维时有极强的偏向性：

• 高维近，低维远（p j ∣ i p_{j|i}pj∣i​大，q j ∣ i q_{j|i}qj∣i​小）：
  此时p j ∣ i q j ∣ i \frac{p_{j|i}}{q_{j|i}}qj∣i​pj∣i​​非常大，再乘以很大的p j ∣ i p_{j|i}pj∣i​，整个 Loss 会极其巨大。因此，SNE 会受到严重的惩罚，绝不允许原本离得近的点在低维被拆散。
• 高维远，低维近（p j ∣ i p_{j|i}pj∣i​小，q j ∣ i q_{j|i}qj∣i​大）：
  此时p j ∣ i → 0 p_{j|i} \to 0pj∣i​→0，无论log ⁡ \loglog项怎么变，整体的 Loss 依然接近于 0。这意味着，原本离得很远的不同类别，如果不小心在低维被压在了一起，SNE 对其施加的惩罚却微乎其微。

这种“宁可把远处的点错误地聚在一起，也绝不拆散近处的邻居”的特性，让它非常擅长保留局部结构，但同时也带来了一个致命缺陷。

4. 经典 SNE 的两大痛点（为什么被 t-SNE 取代？）

尽管 SNE 的构想非常惊艳，但它在实际应用中却饱受两个问题的折磨：

① 拥挤问题（Crowding Problem）

高维空间可容纳的体积远大于低维空间。比如，在高维空间里可以有 10 个点两两等距离（构成高维正多面体），但在 2D 空间里，你最多只能让 3 个点两两等距离（等边三角形）。
当高维中的海量邻居被映射到 2D 空间时，由于低维高斯分布的尾部太薄，所有的点为了维持邻居概率，都会被迫挤在圆心附近，导致不同类别的簇全部糊成一团，无法清晰分辨。

② 梯度计算极其困难（不对称概率）

因为p j ∣ i ≠ p i ∣ j p_{j|i} \neq p_{i|j}pj∣i​=pi∣j​（由于每个点的σ i \sigma_iσi​不同），这种不对称性导致在计算关于y i y_iyi​的全量梯度时，数学公式极其复杂且非常不稳定，容易陷入局部最优解。

5. 进化：从 SNE 到 t-SNE

为了解决上述问题，Hinton 团队在 2008 年对其进行了史诗级升级：

1. 对称 SNE（Symmetric SNE）：将条件概率改为联合概率（让p i j = p j i p_{ij} = p_{ji}pij​=pji​），极大地简化了梯度公式，使优化更稳定。
2. 引入 t 分布：在低维空间，用长尾的t tt分布（自由度为 1，即柯西分布）代替了高斯分布。由于t tt分布的尾部比高斯分布厚得多，在低维空间中离得远的点会被推得更远，从而彻底解决了“拥挤问题”，拉开了不同聚类之间的边界。

总结

SNE 首次将流形学习与概率分布结合，确立了“局部邻居优先”的降维范式。它是现代无监督降维可视化的核心基石，理解了 SNE 的概率对齐机制，就等于真正理解了 t-SNE。