为什么这种欧几里德距离计算方法会导致 RAM 使用量激增？

Question

我正在研究 KNN 算法，使用 2017 年斯坦福课程中的一些 material 对图像进行分类。我们得到了一个由许多图像组成的数据集，稍后这些集合被表示为 2D numpy 数组，我们应该编写计算这些图像之间距离的函数。更具体地说，给定一个二维数组的测试图像和一个二维数组的训练图像，我被要求编写一个 L_2 距离函数，它将这两个集合作为输入和 returns 一个距离矩阵，其中每一行 i 代表一张测试图像，每一列 j 代表一张训练图像。

练习还要求我在不使用任何循环且不使用 np.abs 函数的情况下进行。所以我试了一下试了一下：

def compute_distances_no_loops(self, X):
    """
    Compute the distance between each test point in X and each training point
    in self.X_train using no explicit loops.

    Input / Output: Same as compute_distances_two_loops
    """
    num_test = X.shape[0]
    num_train = self.X_train.shape[0]
    dists = np.zeros((num_test, num_train))
    all_test_subs_sq = (X[:, np.newaxis] - self.X_train)**2
    dists = np.sqrt(np.sum(all_test_subs_sq), axis = 2)
    return dists

显然，由于分配了大约 60 GB 的 RAM，Google 的 Colab 环境在 6 秒内崩溃。我想我应该澄清训练集 X_train 的形状为 (5000, 3072)，而测试集 X 的形状为 (500, 3072)。我不确定这里会发生什么 RAM 密集型，但话又说回来，我不是最聪明的人来弄清楚 space 复杂性。

我在谷歌上搜索了一下，找到了一个无需 NASA 计算机即可运行的解决方案，它使用平方和公式：

    dists = np.reshape(np.sum(X**2, axis=1), [num_test,1]) + np.sum(self.X_train**2, axis=1)\
- 2 * np.matmul(X, self.X_train.T)
    dists = np.sqrt(dists)

我也不确定为什么这个解决方案没有像我的那样爆炸。我真的很感激这里的任何见解，非常感谢您阅读。

Answer 1

在 compute_distances_no_loops() 函数中，中间数组 all_test_subs_sq 的形状为 (500, 3072, 5000)，因此它由 500 * 3072 * 5000 = 7,680,000,000 个元素组成。假设X和X_train的dtype是float64，每个元素占8个字节，所以数组的总大小是61,440,000,000字节，即大约60 GB。

您提供的其他解决方案避免了这个问题，因为它不会创建如此大的中间数组。 np.reshape(np.sum(X**2, axis=1), [num_test,1])的形状是(500, 1)，np.sum(self.X_train**2, axis=1)的形状是(5000,)。添加它们时，您将获得一个形状为 (500, 5000) 的数组。 np.matmul(X, self.X_train.T) 也会生成一个相同形状的数组。

Answer 2

问题在

all_test_subs_sq = (X[:, np.newaxis] - self.X_train)**2

X[:, np.newaxis] 相当于 X[:, np.newaxis, :] 的形状 (50, 1, 3072)。广播后，X[:, np.newaxis] - self.X_train 会产生一个 dense (500, 5000, 3072) 数组，它非常庞大 500 x 5000 x 3072 x 8 bytes ≈ 61.44 GB 因为你有 np.float64.

为什么这种欧几里德距离计算方法会导致 RAM 使用量激增？

Why does this euclidean distance calculation method explodes RAM usage?

python

arrays

numpy

distance

space-complexity