Блог

Я пытаюсь сделать это самостоятельно по заданиям из курса CNN Stanford CS231n 2017.

Я пытаюсь вычислить расстояние L2, используя только умножение матрицы и суммирование с помощью Numpy. Расстояние L2 равно:

И я думаю, что смогу это сделать, если использую эту формулу:

В следующем коде показаны три метода вычисления расстояния L2. Если я сравниваю выходные данные метода compute_distances_two_loops с выходными данными метода compute_distances_one_loop , оба равны. Но я сравниваю выходные данные метода compute_distances_two_loops с выходными данными метода compute_distances_no_loops , где я реализовал расстояние L2, используя только матричное умножение и суммирование, они разные.

 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 xrange(num_test):
        for j in xrange(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.sqrt(np.sum((X[i, :] - self.X_train[j, :]) ** 2))
            dists[i, j] = np.sqrt(np.sum(np.square(X[i, :] - self.X_train[j, :])))
            #####################################################################
            #                       END OF YOUR CODE                            #
            #####################################################################
    return dists

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 xrange(num_test):
        #######################################################################
        # TODO:                                                               #
        # Compute the l2 distance between the ith test point and all training #
        # points, and store the result in dists[i, :].                        #
        #######################################################################
        dists[i, :] = np.sqrt(np.sum(np.square(self.X_train - X[i, :]), axis = 1))
        #######################################################################
        #                         END OF YOUR CODE                            #
        #######################################################################
    print(dists.shape)
    return dists

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))
    #########################################################################
    # TODO:                                                                 #
    # Compute the l2 distance between all test points and all training      #
    # points without using any explicit loops, and store the result in      #
    # dists.                                                                #
    #                                                                       #
    # You should implement this function using only basic array operations; #
    # in particular you should not use functions from scipy.                #
    #                                                                       #
    # HINT: Try to formulate the l2 distance using matrix multiplication    #
    #       and two broadcast sums.                                         #
    #########################################################################
    dists = np.sqrt(-2 * np.dot(X, self.X_train.T)  
                    np.sum(np.square(self.X_train), axis=1)  
                    np.sum(np.square(X), axis=1)[:, np.newaxis])
    print(dists.shape)
    #########################################################################
    #                         END OF YOUR CODE                              #
    #########################################################################
    return dists
 

Вы можете найти полный рабочий тестируемый код здесь.

Знаете ли вы, что я делаю не так compute_distances_no_loops или где-то еще?

Обновить:

Код, который выдает сообщение об ошибке:

 dists_two = classifier.compute_distances_no_loops(X_test)

# check that the distance matrix agrees with the one we computed before:
difference = np.linalg.norm(dists - dists_two, ord='fro')
print('Difference was: %f' % (difference, ))
if difference < 0.001:
    print('Good! The distance matrices are the same')
else:
    print('Uh-oh! The distance matrices are different')
 

И сообщение об ошибке:

 Difference was: 372100.327569
Uh-oh! The distance matrices are different
 

Вот как вы можете вычислить попарные расстояния между строками X и Y без создания каких-либо трехмерных матриц:

 def dist(X, Y):
    sx = np.sum(X**2, axis=1, keepdims=True)
    sy = np.sum(Y**2, axis=1, keepdims=True)
    return np.sqrt(-2 * X.dot(Y.T)   sx   sy.T)
 

Это поздний ответ, но я решил его по-другому и хотел опубликовать его. Когда я решал эту проблему, я не знал о вычитании вектора столбца-строки numpy из матрицы. Как оказалось, мы можем вычесть вектор nx1 или 1xm из nxm, и когда мы это делаем, вычитает из каждого вектора строки-столбца. Если кто-то работает с библиотекой, которая не поддерживает такое поведение, он / она может использовать мою. Для этой ситуации я рассчитал математику, и результат следующий:

 sum_x_train=np.sum(self.X_train**2,axis=1, keepdims=True)
sum_x_test=np.sum(X**2,axis=1, keepdims=True)
sum_2x_tr_te=np.dot(self.X_train,X.T)*2
sum_x_train=np.dot(sum_x_train,np.ones((1,X.shape[0])))
sum_x_test=np.dot(sum_x_test,np.ones((1,self.X_train.shape[0])))
dists=np.sqrt(sum_x_test.T sum_x_train-sum_2x_tr_te).T
 

Недостатком этого подхода является то, что он использует больше памяти.

Я думаю, что вы ищете попарное расстояние.

Существует удивительный трюк, позволяющий сделать это в одной строке. Вы должны умно играть с борадкастингом:

 
X_test = np.expand_dims(X, 0) # shape: [1, num_tests, D]
X_train = np.expand_dims(self.X_train, 1) # shape: [num_train, 1, D]
dists = np.square(X_train - X_test) # Thanks to broadcast [num_train, num_tests, D]
dists = np.sqrt(np.sum(dists, axis=-1)) # [num_train, num_tests]
 

Это мое решение для функции compute_distances_no_loops() , которую запросил OP. Я не использую эту sqrt() функцию по соображениям производительности:

 def compute_distances_no_loops(self, X):
    num_test = X.shape[0]
    num_train = self.X_train.shape[0]
    dists = np.zeros((num_test, num_train))
    #---------------
    # Get square of X and X_train
    X_sq = np.sum(X**2, axis=1, keepdims=True) 
    Xtrain_sq = np.sum(self.X_train**2, axis=1, keepdims=True)
    # Calculate (squared) dists as (X_train - X)**2 = X_train**2 - 2*X_train*X   X**2
    dists = -2*X.dot(self.X_train.T)   X_sq   Xtrain_sq.T
    #---------------  
    return dists
 

Я считаю, что проблема возникает из-за несогласованных форм массива.

 #a^2 matrix (500, 1) 
alpha = np.sum(np.square(X), axis=1)
alpha = alpha.reshape(len(alpha), 1)
print(alpha.shape)
#b^2 matrix (1, 5000) 
beta  = np.sum(np.square(self.X_train.T), axis=0)
beta = beta.reshape(1, len(beta))
print(beta.shape)
#ab matrix (500, 5000)
alphabeta = np.dot(X, self.X_train.T)
print(alphabeta.shape)

dists = np.sqrt(-2 * alphabeta   alpha   beta)