PYTHON

knn compute_distances_one_loop

def compute_distances_one_loop(self, X):
    """
    Compute the distance between each test point in X and each training point
    in self.X_train using a single loop over the test data.

    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))
    for i in range(num_test):
      # Note axis=1 computes norm along rows
      dists[i] = np.linalg.norm(X[i]-self.X_train, axis=1)

    return dists

Difference was: 0.000000
Good! The distance matrices are the same

knn compute_distances_two_loop

def compute_distances_two_loops(self, X):
    """
    Compute the distance between each test point in X and each training point
    in self.X_train using a nested loop over both the training data and the
    test data.

    Inputs:
    - X: A numpy array of shape (num_test, D) containing test data.

    Returns:
    - dists: A numpy array of shape (num_test, num_train) where dists[i, j]
      is the Euclidean distance between the ith test point and the jth training
      point.
    """
    num_test = X.shape[0]
    num_train = self.X_train.shape[0]
    dists = np.zeros((num_test, num_train))
    for i in range(num_test):
      for j in range(num_train):
        dists[i, j] = np.linalg.norm(X[i]-self.X_train[j])

    return dists

(500, 5000)

knn compute_distances_no_loop

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]

    # Expand ||x - y||**2 = ||x||**2 - 2 x.T ⋅y + ||y||**2,
    # where ||x||**2 = sum(x**2) (element-wise on matrix rows)
    # The final result is a (num_test, num_train) matrix
    # so the x**2 and y**2 intermediates must be reshaped appropriately
    x2 = np.sum(X**2, axis=1).reshape((num_test, 1))
    y2 = np.sum(self.X_train**2, axis=1).reshape((1, num_train))
    xy = -2*np.matmul(X, self.X_train.T)
    dists = np.sqrt(x2 + xy + y2)

    return dists

Difference was: 0.000000
Good! The distance matrices are the same