t-SNE 算法⚓︎

约 5602 个字预计阅读时间 19 分钟总阅读量次

这是一个在数据科学和机器学习领域非常流行且强大的降维可视化算法。

t-分布随机邻域嵌入 (t-SNE)⚓︎

1. 作用与解决的问题⚓︎

核心作用：t-SNE 的==主要目标是将高维数据集降维到2维或3维==，以便进行可视化。它非常擅长揭示数据中的局部结构，比如发现高维空间中存在的簇(cluster)或流形(manifold)结构。

它解决了什么关键问题？

在 t-SNE 之前，像 PCA 这样的方法是主流。PCA 是一种线性降维方法，它致力于保持数据的全局方差。这使得 PCA 在寻找一个能最大化方差的低维投影时非常有效，但它常常会破坏数据点之间的局部邻近关系。

想象一下高维空间中的一个“S”形曲线（一个流形）。PCA为了保持全局方差，可能会将这个“S”压扁成一条线，导致原本相距很远的点（如“S”的两端）在低维空间中变得很近。

t-SNE 则专注于解决这个问题，它是一种非线性的降维方法，其首要目标是：

保持局部结构：如果两个点在高维空间中是邻居，那么在低维的可视化中，它们也应该是邻居。
解决“拥挤问题”(Crowding Problem)：这是一个由 t-SNE 的前身 SNE (Stochastic Neighbor Embedding) 遗留下的问题。简单来说，高维空间可以容纳很多距离适中的点，但在低维空间（比如二维平面）中，没有足够的空间来“摆放”这些点，导致它们被错误地挤压在一起。t-SNE 通过一个巧妙的技巧解决了这个问题。

一句话总结：t-SNE 是一种强大的数据可视化工具，它通过保持数据的局部结构，能在二维或三维平面上画出高维数据清晰的“地图”，尤其擅长展示聚类效果。

2. 算法流程⚓︎

t-SNE 的核心思想是：将高维空间中数据点之间的相似度关系，转化为一个概率分布；然后在低维空间中，构建另一个概率分布，通过优化使得这两个概率分布尽可能地相似。

假设：我们有 $n$ 个高维数据点 $\mathbf{x}_1, \mathbf{x}_2, ..., \mathbf{x}_n \in \mathbb{R}^m$。

第1步：构建高维空间中的相似度概率分布

首先，t-SNE 将数据点之间的欧氏距离转化为条件概率 $p_{j|i}$，这代表了如果 $\mathbf{x}_i$ 要选择一个邻居，它会选择 $\mathbf{x}_j$ 的概率。这个概率服从以 $\mathbf{x}_i$ 为中心的高斯分布：

\[p_{j|i} = \frac{\exp(-||\mathbf{x}_i - \mathbf{x}_j||^2 / 2\sigma_i^2)}{\sum_{k \neq i} \exp(-||\mathbf{x}_i - \mathbf{x}_k||^2 / 2\sigma_i^2)}\]

此处的 $\sigma_i$ 是点 $\mathbf{x}_i$ 独有的高斯方差。它的值是通过一个叫做困惑度 (Perplexity) 的超参数来确定的。你可以将困惑度理解为“一个点有效的邻居数量”。t-SNE会为每个点通过二分搜索找到一个最优的 $\sigma_i$ 来满足用户设定的困惑度。
为了简化计算，t-SNE 将这个条件概率对称化，得到联合概率 $p_{ij}$：

\[p_{ij} = \frac{p_{j|i} + p_{i|j}}{2n}\]

这个 $P = \{p_{ij}\}$ 就是我们在高维空间中，描述数据点相似度关系的概率分布。

困惑度⚓︎

我们来详细解析一下 t-SNE 中非常关键的超参数——困惑度 (Perplexity)，以及它是如何与高斯方差 $\sigma_i$ 挂钩的。

困惑度 (Perplexity) 可以被理解为一个点有效邻居的数量。

如果你将困惑度设置为 10，t-SNE 算法会尝试调整每个点的高斯分布方差 $\sigma_i$，使得每个点 $\mathbf{x}_i$ 平均能“覆盖”到 10 个邻近的点。
困惑度低（如 2）：算法只关注每个点的极少数最近邻。这会倾向于保留非常局部的结构，可能会把一些大的聚类拆分成多个小团块。
困惑度高（如 50）：算法会考虑更远的点作为邻居，更倾向于关注全局的结构，可能会把一些小簇合并成一个大簇。

困惑度是一个你需要手动设置的超参数。常用的取值范围是 5 到 50 之间。它对于 t-SNE 的最终可视化效果有非常大的影响。

困惑度的数学定义

困惑度是基于信息论中的香农熵 (Shannon Entropy) 来定义的。

我们先回顾一下在第1步中定义的条件概率 $p_{j|i}$： $$ p_{j|i} = \frac{\exp(-||\mathbf{x}i - \mathbf{x}_j||^2 / 2\sigma_i^2)}{\sum $$ 这个 } \exp(-||\mathbf{x}_i - \mathbf{x}_k||^2 / 2\sigma_i^2)$p_{j|i}$ 描述了以 $\mathbf{x}_i$ 为中心的高斯分布下，$\mathbf{x}_j$ 被选为邻居的概率。

计算香农熵：对于以点 $\mathbf{x}_i$ 为中心的这个概率分布 $P_i = \{ p_{j|i} \text{ for all } j \neq i \}$, 我们可以计算它的香农熵 $H(P_i)$：

\[H(P_i) = - \sum_{j \neq i} p_{j|i} \log_2 p_{j|i}\]

香农熵衡量了这个概率分布的“不确定性”。如果分布非常集中（只有一个邻居的概率接近1，其他都为0），那么熵很低。如果分布很均匀（很多邻居的概率都差不多），那么熵很高。

定义困惑度：困惑度 Perp(P_i) 就是这个熵的指数形式：
```
\[
\text{Perp}(P_i) = 2^{H(P_i)}
\]
```
- 如果熵为0（分布完全确定，只有一个邻居），困惑度为 $2^0 = 1$。
- 如果一个点有 $k$ 个邻居的概率都是 $1/k$，其他都为0，那么它的熵是 $\log_2 k$，困惑度就是 $2^{\log_2 k} = k$。
- 这就是为什么我们可以直观地将困惑度理解为“有效邻居数”。

现在是关键部分：我们是先设定困惑度，然后算法反过来为我们找到对应的 $\sigma_i$。

这个过程对每个数据点 $\mathbf{x}_i$ 都是独立进行的：

用户设定目标：用户指定一个全局的困惑度值，比如 perplexity = 30。
为每个点 $\mathbf{x}_i$ 寻找 $\sigma_i$：
- 对于某个点 $\mathbf{x}_i$，t-SNE 算法的目标是找到一个 $\sigma_i$，使得根据这个 $\sigma_i$ 计算出的概率分布 $P_i$ 所对应的困惑度 $\text{Perp}(P_i)$ 恰好等于用户设定的值。
- 也就是说，算法需要解下面这个关于 $\sigma_i$ 的方程：
```
\[
2^{H(P_i(\sigma_i))} = \text{perplexity}_{\text{user}}
\]
```
  或者等价地，在对数空间解：
```
\[
H(P_i(\sigma_i)) = \log_2(\text{perplexity}_{\text{user}})
\]
```
  注意，这里的 $H(P_i(\sigma_i))$ 是一个关于 $\sigma_i$ 的函数，因为 $p_{j|i}$ 依赖于 $\sigma_i$。
使用二分搜索 (Binary Search)：
- 上述方程没有解析解，只能通过数值方法求解。最常用的方法就是二分搜索。
- 我们可以观察到，$\sigma_i$ 与困惑度是单调递增的关系：
  - $\sigma_i$ 增大 $\implies$ 高斯分布更“胖” $\implies$ 更多点被覆盖，分布更均匀 $\implies$ 熵增大 $\implies$ 困惑度增大。
  - $\sigma_i$ 减小 $\implies$ 高斯分布更“瘦” $\implies$ 更少点被覆盖，分布更尖锐 $\implies$ 熵减小 $\implies$ 困惑度减小。
- 利用这个单调性，算法可以设定一个 $\sigma_i$ 的搜索范围（比如 [1e-4, 1e4]），然后通过二分搜索高效地找到满足 Perp(P_i) ≈ perplexity 的那个 $\sigma_i$ 值。

总结

困惑度不是被计算出来的，而是用户设定的超参数。
算法的工作是：对于每一个数据点 $\mathbf{x}_i$，通过二分搜索来找到一个唯一的高斯方差 $\sigma_i$，使得以该点为中心构建的概率分布的困惑度，恰好等于用户设定的值。
结果是：数据稀疏区域的点，会有较大的 $\sigma_i$ 值，去“够到”足够多的邻居；数据密集区域的点，会有较小的 $\sigma_i$ 值，因为它周围本身就有很多邻居。这使得 t-SNE 能够自适应地处理不同密度的区域，这也是它强大的原因之一。

第2步：构建低维空间中的相似度概率分布

我们将高维点 $\mathbf{x}_i$ 映射到低维空间（比如2维）得到 $\mathbf{y}_i, \mathbf{y}_2, ..., \mathbf{y}_n \in \mathbb{R}^2$。这些低维点的初始位置是随机的。
关键创新：t-SNE 在低维空间中使用自由度为1的 t-分布 (Student's t-distribution) 来衡量相似度。t-分布有一个“重尾巴”的特性。 $$ q_{ij} = \frac{(1 + ||\mathbf{y}i - \mathbf{y}_j||²⁾{\sum}_l||} (1 + ||\mathbf{y}_k - \mathbf{y²⁾ $$}

为什么用t-分布？

这正是为了解决拥挤问题。

高斯分布的尾部衰减很快，意味着中等距离的点在高维空间中已经有很低的相似度概率。
t-分布的尾部很重，衰减慢。这意味着，为了在高维空间中获得一个中等大小的相似度 $p_{ij}$，低维空间中的点 $\mathbf{y}_i$ 和 $\mathbf{y}_j$ 需要被拉得非常远才能匹配上。
这就为那些在高维空间中靠得比较近的点腾出了空间，缓解了“拥挤”。

第3步：最小化两个分布之间的差异

我们的目标是让低维的概率分布 $Q=\{q_{ij}\}$ 尽可能地匹配高维的概率分布 $P=\{p_{ij}\}$。
这个“匹配度”是通过KL散度 (Kullback-Leibler Divergence) 来衡量的。t-SNE 的目标函数（也叫损失函数）就是最小化所有点对的KL散度之和：

\[\text{Cost} = \sum_{i} \sum_{j} p_{ij} \log \frac{p_{ij}}{q_{ij}}\]

通过梯度下降 (Gradient Descent) 算法来最小化这个损失函数。算法会不断调整低维点 $\mathbf{y}_i$ 的位置，直到KL散度最小化（或达到最大迭代次数）。
KL散度的梯度有一个非常优雅和直观的形式：它由两部分组成，一部分是吸引力（由 $p_{ij}$ 决定），另一部分是排斥力（由 $q_{ij}$ 决定）。如果两个点在高维空间中很近（$p_{ij}$ 大），它们在低维空间中就会互相吸引；反之，所有点之间都存在一个排斥力，防止所有点都挤在一起。

3. 算法复杂度分析⚓︎

假设有 $n$ 个样本，每个样本 $m$ 维，目标是降到 $d$ 维（通常 $d=2$ 或 $3$）。

朴素 t-SNE 复杂度：$O(n^2m)$⚓︎

计算高维相似度 ($p_{ij}$)：
- 需要计算所有点对之间的距离，这是一个 $n \times n$ 的距离矩阵。复杂度为 $O(n^2 m)$。
- 对于每个点，通过二分搜索确定 $\sigma_i$ 以匹配困惑度。这步的复杂度大约是 $O(n^2 \log k)$ （$k$是二分搜索步数）。
- 总的来说，这一步是 $O(n^2 m)$。
梯度下降优化：
- 在每次迭代中，都需要计算所有低维点对之间的相似度 $q_{ij}$，这需要计算一个 $n \times n$ 的距离矩阵。复杂度为 $O(n^2 d)$。
- 计算归一化因子（分母）的复杂度是 $O(n^2)$。
- 计算每个点的梯度，需要遍历所有其他点，所以单次迭代的梯度计算复杂度是 $O(n^2)$。
- 如果进行 $T$ 次迭代，这部分的复杂度是 $O(T n^2)$。

综合来看，朴素t-SNE的整体复杂度是 $O(n^2m)$ 量级，计算成本非常高，当 $n$ 超过几千时就变得非常缓慢。

优化后的 t-SNE (Barnes-Hut t-SNE): $O(n \log n)$

$O(n^2)$ 的复杂度是 t-SNE 实用性的主要障碍。幸运的是，现代 t-SNE 的实现（如 scikit-learn 中的）几乎都使用了 Barnes-Hut 近似方法来解决这个问题。

核心思想：在计算梯度时的排斥力部分，我们不必为每个点都精确计算与其他 $n-1$ 个点的相互作用力。
方法：
1. 在低维空间中，使用一种四叉树（2D）或八叉树（3D）的数据结构来划分点。
2. 对于一个给定的点 $\mathbf{y}_i$，离它很远的一簇点可以被看作一个“超级节点”。我们可以计算 $\mathbf{y}_i$ 与这个超级节点的质心之间的排斥力，而不是逐一计算簇内每个点的排斥力。
3. 这样，每个点的力计算从 $O(n)$ 降到了 $O(\log n)$。

最终，使用 Barnes-Hut 近似的 t-SNE 的复杂度被大幅优化到了 $\mathbf{O(n \log n)}$。 这使得 t-SNE 能够处理数十万甚至上百万个样本，使其成为一个非常实用和流行的工具。

梯度下降⚓︎

当然没问题。梯度下降在 t-SNE 中是一个非常有趣的过程，理解它能帮你彻底搞懂 t-SNE 的工作机制。我们可以把它分解成“计算什么”和“如何迭代”两个部分。

1. 目标：计算梯度⚓︎

梯度下降的核心是计算损失函数关于待优化变量的梯度（偏导数）。

损失函数 $C$：KL 散度

\[
C = \sum_{i} \sum_{j \neq i} p_{ij} \log \frac{p_{ij}}{q_{ij}}
\]

待优化变量：低维空间中所有数据点的位置 $\mathbf{y}_1, \mathbf{y}_2, ..., \mathbf{y}_n$。高维概率 $p_{ij}$ 是预先计算好的常数。
目标：计算损失函数 $C$ 对于某一个低维数据点 $\mathbf{y}_i$ 的梯度 $\frac{\partial C}{\partial \mathbf{y}_i}$。这个梯度是一个向量，它指向了能使损失函数 $C$ 增长最快的方向。

梯度的推导与直观解释⚓︎

对复杂的 KL 散度公式求导，经过一系列推导（这里省略繁琐的代数过程），可以得到一个非常优美且直观的梯度表达式：

\[
\frac{\partial C}{\partial \mathbf{y}_i} = 4 \sum_{j \neq i} (p_{ij} - q_{ij})(1 + ||\mathbf{y}_i - \mathbf{y}_j||^2)^{-1}(\mathbf{y}_i - \mathbf{y}_j)
\]

这个公式看起来复杂，但我们可以把它拆解成非常有物理意义的两部分：

\[
\frac{\partial C}{\partial \mathbf{y}_i} = \underbrace{4 \sum_{j \neq i} p_{ij}(1 + ||\mathbf{y}_i - \mathbf{y}_j||^2)^{-1}(\mathbf{y}_i - \mathbf{y}_j)}_{\text{Attractive Force (吸引力)}} - \underbrace{4 \sum_{j \neq i} q_{ij}(1 + ||\mathbf{y}_i - \mathbf{y}_j||^2)^{-1}(\mathbf{y}_i - \mathbf{y}_j)}_{\text{Repulsive Force (排斥力)}}
\]

让我们来解读一下这个梯度公式的含义：

向量 $(\mathbf{y}_i - \mathbf{y}_j)$：这是一个从点 $\mathbf{y}_j$ 指向点 $\mathbf{y}_i$ 的向量。它定义了两个点之间相互作用力的方向。
吸引力部分:
- 与高维概率 $p_{ij}$ 成正比。如果两个点在高维空间中很近（$p_{ij}$ 大），那么它们之间的吸引力就强。
- 梯度下降是沿着梯度的相反方向移动。这部分的梯度项会使得 $\mathbf{y}_i$ 朝着 $\mathbf{y}_j$ 的方向移动，从而使它们在低维空间中相互靠近。
- 这就像用弹簧把在高维空间中是邻居的点连接起来。
排斥力部分:
- 与低维概率 $q_{ij}$ 成正比。这个力存在于所有点对之间。
- 这部分的梯度项因为带有负号，所以最终的移动方向是沿着 $(\mathbf{y}_j - \mathbf{y}_i)$ 的方向，使得 $\mathbf{y}_i$ 远离 $\mathbf{y}_j$。
- 这个力确保了所有点不会挤成一团，即使它们在高维空间中不是邻居，在低维空间中也会互相排斥，从而展开形成清晰的结构。

总结：在每个迭代步中，对于每个点 $\mathbf{y}_i$，我们都计算一个合力。这个合力是它与所有其他点 $\mathbf{y}_j$ 之间吸引力与排斥力的总和。然后，我们让这个点沿着合力的方向移动一小步。

P大Q小：高维很近，低维很远 $\rightarrow$ 产生强大的吸引力。
P小Q大：高维很远，低维很近 $\rightarrow$ 产生强大的排斥力。

2. 梯度下降的迭代流程⚓︎

现在我们有了计算梯度的“罗盘”，接下来就是如何一步步“寻宝”（找到最优的低维表示）。

算法流程如下：

初始化：
- 计算所有高维点对的联合概率 $p_{ij}$。这步只做一次。
- 在低维空间中（比如一个二维平面上），随机生成 $n$ 个点 $\mathbf{y}_1^{(0)}, \mathbf{y}_2^{(0)}, ..., \mathbf{y}_n^{(0)}$ 作为初始位置。通常是从一个均值为0，方差很小的高斯分布中采样。
迭代优化 (Loop for T steps)：对于迭代的每一步 $t=1, 2, ..., T$： a. 计算低维相似度：基于当前所有低维点的位置 $\{\mathbf{y}_i^{(t-1)}\}$，计算所有点对的低维联合概率 $q_{ij}$。 b. 计算梯度：对于每一个数据点 $\mathbf{y}_i$，使用上面优美的公式计算出总梯度 $\frac{\partial C}{\partial \mathbf{y}_i^{(t-1)}}$。 c. 更新位置：使用梯度来更新每个点的位置。

实际更新中的技巧⚓︎

标准的梯度下降 new_pos = old_pos - learning_rate * gradient 在 t-SNE 中效果不佳。实际实现中会使用两个非常重要的技巧：

A. 动量 (Momentum)

为了加速收敛并帮助“冲出”不好的局部最小值，t-SNE 使用了动量法。

更新公式变为： $$ \mathbf{Y}^{(t)} = \mathbf{Y}^{(t-1)} - \eta \frac{\partial C}{\partial \mathbf{Y}^{(t-1)}} + \alpha(t) (\mathbf{Y}^{(t-1)} - \mathbf{Y}^{(t-2)}) $$ 这里的 $\mathbf{Y}$ 代表所有低维点的集合 $\{\mathbf{y}_i\}$。
- $\eta$ 是学习率 (learning rate)。
- $\alpha(t)$ 是在第 $t$ 步的动量系数。它是一个随迭代变化的超参数，比如初始时设为 0.5，在几百步后增加到 0.8。
直观理解：点的位置更新不仅取决于当前这一步的梯度（合力），还部分地保留了上一步的移动方向和速度。这就像一个滚下山的小球，它带有惯性，不会因为一点小的颠簸就停下或改变方向。

B. 早期夸张 (Early Exaggeration)

这是一个非常巧妙的“启动”技巧。

做法：在迭代的前期（比如前250步），将所有高维概率 $p_{ij}$ 的值乘以一个比较大的数（比如12）。
目的：
- 这会极大地增强所有弹簧的“吸引力”，让那些在高维空间中确实属于同一个簇的点迅速地聚集在一起，形成松散的、但大致正确的聚类结构。
- 它使得数据点之间的空隙被拉得更开，为后续的精细调整（取消夸张后）留出空间，防止点挤在一起陷入不好的局部最优解。
在早期夸张阶段结束后，恢复使用原始的 $p_{ij}$ 值，进行后续的“微调”，让簇的内部结构和簇之间的相对位置变得更加清晰。

综上，t-SNE的梯度下降是一个带有物理直觉（吸引力与排斥力）、并结合了动量和早期夸张等工程技巧的迭代优化过程，最终将高维数据的复杂结构优美地呈现在低维空间中。

你的理解非常到位，完全正确！这正是 t-SNE 算法的精髓。我们可以把你精彩的理解再梳理一遍：

$p_{ij}$ 是一个概率分布： 是的。所有点对 $(i, j)$ 的 $p_{ij}$ 值构成了一个联合概率分布。这个分布是 t-SNE 构建的高维“相似度地图”。它通过高斯分布和困惑度，捕捉了原始高维数据中每个点周围的局部邻域结构。
KL散度是桥梁： 是的。KL散度是我们的目标函数或损失函数。它衡量了低维“地图” $Q = \{q_{ij}\}$ 与高维“地图” $P = \{p_{ij}\}$ 之间的差异。我们的目标就是最小化这个差异。
匹配分布以保持相似度： 是的。整个算法的优化过程（梯度下降），就是不断调整低维点 $\{\mathbf{y}_i\}$ 的位置。每调整一次，低维的 $q_{ij}$ 分布就会改变。算法的目标就是找到一组合适的低维点位置，使得由此产生的 $q_{ij}$ 分布，与我们事先计算好且固定不变的 $p_{ij}$ 分布尽可能地相似（即KL散度最小）。

一言以蔽之，你可以把 t-SNE 的过程想象成：高维的 $p_{ij}$ 是一张设计蓝图（描述了点之间理想的亲疏关系），低维的 $q_{ij}$ 是我们随机撒下一些点后实际的工地图。KL散度和梯度下降就是施工过程，我们不断地挪动工地图上的点，直到它最大程度地符合设计蓝图的要求。

t-SNE 是一种强大的非线性降维算法，主要用于高维数据的可视化。它的首要目标是在低维空间（通常是2D或3D）中保持数据的局部结构，非常擅长展示高维数据中的簇。

它将高维空间中数据点间的相似度（基于高斯分布）转化为一个联合概率分布 $P$。然后，在低维空间中构建另一个基于t分布的联合概率分布 $Q$。最后，通过梯度下降最小化这两个分布之间的KL散度，来找到最佳的低维数据表示。

为什么用 t-分布？(Why t-distribution?)

为了解决拥挤问题 (Crowding Problem)。相比于高斯分布，t-分布具有重尾 (heavy tails) 的特性。这意味着，为了匹配一个中等大小的高维相似度 $p_{ij}$，低维空间中的点需要被拉得更远。这为那些本应靠得很近的点腾出了空间，使得簇与簇之间能够形成更清晰的间隔。

(How is it different from PCA?) 这是一个必考点，最好用表格来对比记忆。

特性	PCA	t-SNE
算法类型	线性 (Linear)	非线性 (Non-linear)
核心目标	保持全局方差最大化	保持局部邻域结构
应用场景	数据预处理、去噪、特征提取	数据可视化、探索性数据分析
确定性	确定性 (Deterministic)	非确定性 (Non-deterministic)
计算速度	快 (基于SVD)	慢 (迭代优化)
结果解释	主成分有明确的数学含义	簇间距离、大小等不具明确含义