Replacing a nested loop

Question

I'm just starting with Python and I'm having trouble understanding how I'm supposed to achieve the following goal (I'm a Java programmer).

Here is the initial code:

  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):
        #####################################################################
        # TODO:                                                             #
        # Compute the l2 distance between the ith test point and the jth    #
        # training point, and store the result in dists[i, j]. You should   #
        # not use a loop over dimension.                                    #
        #####################################################################
        dists[i, j] = np.sum(np.square(X[i] - self.X_train[j]))
        #####################################################################
        #                       END OF YOUR CODE                            #
        #####################################################################
    return dists

Here is the piece of code that is supposed to have one less nested loop while still outputing the same array:

  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):
      tmp = '%s %d' % ("\nfor i:", i)
      print(tmp)

      print(X[i])
      print("end of X[i]")
      print(self.X_train[:]) # all the thing [[ ... ... ]]
      print(": before, i after")
      print(self.X_train[i]) # just a row
      print(self.X_train[i, :])

      #######################################################################
      # TODO:                                                               #
      # Compute the l2 distance between the ith test point and all training #
      # points, and store the result in dists[i, :].                        #
      #######################################################################
      dists[i, :] = np.sum(np.square(X[i] - self.X_train[i, :]))
      print(dists[i])
      #######################################################################
      #                         END OF YOUR CODE                            #
      #######################################################################
    return dists

It seems like this should have helped me, but I still can't figure it out.

You can see that my pitfall is, among other things, my poor understanding of how the ":" works exactly.

I've spent hours trying to figure this thing out, but it seems like I'm really lacking some core knowledge. Anyone can help me out? This exercise comes for a Stanford course on Visual Recognition: it's the first Assignment, but it isn't a real homework of mine since I'm only doing the course for pleasure, on my own.

Currently, my piece of code outputs the proper value of the diagonal of the two_loops, but for the whole row. I don't understand how I'm supposed to synchronize the : from dists[i, :] with the - self.X_train[i, :] part. How to compute X[i] minus an iteration that goes through the whole self.X_train ?

Note: num_test is 500x3072 and num_train is 5000x3072. The 3072 comes from 32x32x3 which are the RGB values of 32x32 pictures. dists[i,j] is a 500x5000 matrix that maps the L2 distance between the ith element of num_test and the jth element of num_train.

Eric Nordelo Galiano · Accepted Answer · 2018-08-17 21:48:59Z

2

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):
      tmp = '%s %d' % ("\nfor i:", i)
      print(tmp)

      #######################################################################
      # TODO:                                                               #
      # Compute the l2 distance between the ith test point and all training #
      # points, and store the result in dists[i, :].                        #
      #######################################################################
      dists[i] = np.sum(np.square(X[i] - self.X_train), axis=1)
      print(dists[i])
      #######################################################################
      #                         END OF YOUR CODE                            #
      #######################################################################
    return dists

Remove prints with self.X_train in the loop because is not the same length. (IndexOutOfRangeException) I'm not sure if this is removing the second loop but is a working solution.

Another comment, I think you are wrong with the euclidean distance formula. You are missing the sqrt at the end.

edited Aug 17, 2018 at 21:48

answered Aug 17, 2018 at 20:35

Eric Nordelo Galiano

4554 silver badges16 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

payne Over a year ago

This definitely looks like just another for loop, in some other way. I do not believe that this is the solution. And about your commentary on sqrt: "in a practical nearest neighbor application we could leave out the square root operation because square root is a monotonic function. That is, it scales the absolute sizes of the distances but it preserves the ordering, so the nearest neighbors with or without it are identical." (from the course)

Eric Nordelo Galiano Over a year ago

I think this is what you are looking for. I fixed the code.

payne Over a year ago

Indeed! Would you mind explaining why/how it works in your answer?

Eric Nordelo Galiano Over a year ago

X[i] - self.X_train returns an array which is the result of substract every two componenets point in self.X_train (that is the same as self.X_train[:] ) to the two components array in X[i] (the actual point and the same as X[i, :]) and keep every resulting point, after np.square computes the square on every number, and after the axis param to the np.sum tells numpy sum every row in the array (only the components in the row, detailed explanation in here ), returning the array we need for the component in dists.

Eric Nordelo Galiano Over a year ago

sorry for the very generic explanation and for my english.

|

Collectives™ on Stack Overflow

Replacing a nested loop

1 Answer 1

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related