python - t-SNE 的计算瓶颈是它的内存复杂度吗？

Question

我一直在探索不同的降维算法，特别是 PCA 和 T-SNE。我正在使用 MNIST 数据集的一小部分(大约 780 维)并尝试将原始数据减少到三个维度以可视化为散点图。 T-SNE 可以描述的很详细here .

我使用 PCA 作为 T-SNE 之前的中间降维步骤，正如 T-SNE 的原始创建者在 source code from their website. 上所描述的那样

我发现 T-SNE 需要很长时间才能运行(从 2000 x 25 到 2000 x 3 特征空间需要 10-15 分钟)，而 PCA 运行速度相对较快(2000 x 780 => 2000 X 20 几秒钟)。

为什么会这样？我的理论是，在 PCA 实现中(直接来自主要作者的 Python 源代码)，他利用 Numpy 点积符号来计算 X 和 X.T:

def pca(X = Math.array([]), no_dims = 50):
    """Runs PCA on the NxD array X in order to reduce its dimensionality to no_dims dimensions."""

    print "Preprocessing the data using PCA..."
    (n, d) = X.shape;
    X = X - Math.tile(Math.mean(X, 0), (n, 1));
    (l, M) = Math.linalg.eig(Math.dot(X.T, X));
    Y = Math.dot(X, M[:,0:no_dims]);
    return Y;

据我所知，这比标量运算效率高得多，也意味着只有 2N(其中 N 是行数)数据是加载到内存中(需要加载一行X和一列X.T)。

不过，我认为这不是根本原因。 T-SNE 当然也包含向量操作，例如，在计算成对距离时 D:

D = Math.add(Math.add(-2 * Math.dot(X, X.T), sum_X).T, sum_X);

或者，在计算 P(高维)和 Q(低维)时。然而，在 t-SNE 中，您必须创建两个 N X N 矩阵来存储每个数据之间的成对距离，一个用于其原始高维空间表示，另一个用于其降维空间。

在计算梯度时，您还必须创建另一个名为 PQ 的 N X N 矩阵，即 P - Q。

在我看来，这里的内存复杂度是瓶颈。 T-SNE 需要 3N^2 内存。这不可能适合本地内存，因此该算法会遇到严重的缓存行未命中，需要转到全局内存来检索值。

这是正确的吗？我如何向客户或合理的非技术人员解释为什么 t-SNE 比 PCA 慢？

合著者的Python实现被发现here .

Answer 1

t-SNE 比 PCA 慢的主要原因是没有针对正在优化的标准的解析解。相反，解决方案必须通过梯度下降迭代来近似。

实际上，这意味着很多 for 循环。至少不是第 129 行中的主循环 for 循环，它运行了 max_iter=1000 次。此外，x2p 函数使用 for 循环迭代所有数据点。

引用实现针对可读性而非计算速度进行了优化。作者链接到 optimised Torch implementation同样，这应该可以大大加快计算速度。如果你想留在纯 Python 中，我建议在 Scikit-Learn 中实现，这也应该快得多。