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 尝试降低维度，同时保留元素之间的距离分布。

这需要计算所有点之间的距离。成对距离矩阵有 N^2 个条目，其中 N 是示例数。