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 到 需要 10-15 分钟2000 x 3 特征 space)，而 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 矩阵来存储每个数据之间的成对距离，一个用于其原始高维 space 表示，另一个用于它的降维 space。

在计算梯度时，您还必须创建另一个名为 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 循环遍历所有数据点。

参考实现针对可读性而非计算速度进行了优化。作者 link 到 optimised Torch implementation as well, which should speed up the computation a lot. If you want to stay in pure Python, I recommend the implementation in Scikit-Learn，应该也会快很多。

Answer 2

t-SNE 试图在保持元素之间距离分布的同时降低维度。

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

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

Is t-SNE's computational bottleneck its memory complexity?

python

arrays

algorithm

numpy

dimensionality-reduction