CS231n assignment 1中compute_distances_no_loops思路

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

数据维数
训练集： X_train -> (5000, 3072)
测试集： X_test -> (500, 3072)
距离矩阵：dist -> (500, 5000)

• 首先，目标是计算测试集中每一个图片与训练集中的所有图片的距离，那么就会有一个距离矩阵(500, 5000)，行表示测试集索引，列表示训练集索引，也就是(i, j)表示第i个测试图片到第j个训练图片的距离。

• 其次，计算距离用L2范数，例如第i个测试图片到第j个训练图片距离为

  (X_test[i] - X_train[j]) ** 2 
  

• 进一步，使用两层循环会很慢，因此可以使用向量方法运算，使用一层循环，直接对将一个测试图片对所有训练图片计算距离，

   (X_test[i] - X_train) ** 2
  

• 更近一步， 去掉循环，这个有些难度，初步想法是：
  将测试图片集提升维度 (500, 3072) -> (500, 5000, 3072)，训练集是 (5000, 3072)， 利用python的broadcasting（因为广播不是真正的复制数据，因此可以提高性能），这样

   # X_train提升维度到 (500, 5000, 3072)
   (X_test - X_train) ** 2
   # 结果的维度是 (500, 5000, 3072)
   # 然后压缩 3072 那个维度，就产生了最终的结果
  

  问题是要产生 (500, 5000, 3072) 需要真正复制，造成内存不够，python会报错 Memory Error
  解决方法：
  数学上， (x - y) ^ 2 = x ^ 2 + y ^ 2 - 2 * x * y，对于矩阵也是这样，首先计算 X_test ** 2，求和压缩为 (500, 1), 然后 X_train ** 2，求和压缩为 (1, 5000)，计算 X_test * X_train.T 得到 (500, 5000)， 进行最后运算求得结果，这样看来每一步的维度都限制在 (5000, 3072) 以下，因此不会造成内存不够的情况。