assignment1 k_nearest_neighbor.py memory overflow

[nhzc123]

in function compute_distances_no_loops(self, X)

T = np.sum(X**2,axis = 1)
F = np.sum(self.X_train**2,axis = 1).T
F = np.tile(F,(500,5000))
FT = X.dot(self.X_train.T)
print T.shape,F.shape,FT.shape,X.shape,self.X_train.shape
dists = T+F-2*FT`

the code

F = np.tile(F,(500,5000))

will make a matrix which contain 500 5000 5000 elements may be the code should be modified like

T = np.reshape(np.sum(X**2,axis = 1),(num_test,1))
F = np.sum(self.X_train**2,axis = 1).T
F = np.tile(F,(num_test,1))
FT = X.dot(self.X_train.T)
print T.shape,F.shape,FT.shape,X.shape,self.X_train.shape
dists = T+F-2*FT`

[ChienDuong]

This is another way, we dont need to use np.tile. Just remove the line, and the code still workable.

F=np.tile(F,(500,5000))

In the line: dists = T+F-2*FT (when we plus F, it automatically plus F's element through all 500 rows)

[wzirui]

The original code is wrong:

    T = np.sum(X**2,axis = 1)
    F = np.sum(self.X_train**2,axis = 1).T
    F = np.tile(F,(500,5000))
    FT = X.dot(self.X_train.T)
    print T.shape,F.shape,FT.shape,X.shape,self.X_train.shape
    dists = T+F-2*FT

But only remove the line F = np.tile(F,(500,5000)) can't fix the problem:

    T = np.sum(X**2,axis = 1)
    F = np.sum(self.X_train**2,axis = 1).T
    FT = X.dot(self.X_train.T)
    print T.shape,F.shape,FT.shape,X.shape,self.X_train.shape
    dists = T+F-2*FT

What we need to do is to transpose T but not F, so that broadcasting can work properly. Also, transposing a vector doesn't change anything. Instead we need to reshape the vector to a matrix:

    T = np.reshape(np.sum(X**2,axis = 1), (num_test,1))
    F = np.sum(self.X_train**2,axis = 1)
    FT = X.dot(self.X_train.T)
    print T.shape,F.shape,FT.shape,X.shape,self.X_train.shape
    dists = T+F-2*FT