Scipy - how to further optimize sparse matrix code for stochastic gradient descent

Question

I'm working on implementing the stochastic gradient descent algorithm for recommender systems using sparse matrices with Scipy.

This is how a first basic implementation looks like:

    N = self.model.shape[0] #no of users
    M = self.model.shape[1] #no of items
    self.p = np.random.rand(N, K)
    self.q = np.random.rand(M, K)
    rows,cols = self.model.nonzero()        
    for step in xrange(steps):
        for u, i in zip(rows,cols):
            e=self.model-np.dot(self.p,self.q.T) #calculate error for gradient
            p_temp = learning_rate * ( e[u,i] * self.q[i,:] - regularization * self.p[u,:])
            self.q[i,:]+= learning_rate * ( e[u,i] * self.p[u,:] - regularization * self.q[i,:])
            self.p[u,:] += p_temp

Unfortunately, my code is still pretty slow, even for a small 4x5 ratings matrix. I was thinking that this is probably due to the sparse matrix for loop. I've tried expressing the q and p changes using fancy indexing but since I'm still pretty new at scipy and numpy, I couldn't figure a better way to do it.

Do you have any pointers on how i could avoid iterating over the rows and columns of the sparse matrix explicitly?

Answer 1

I almost forgot everything about recommender systems, so I may be erroneously translated your code, but you reevaluate self.model-np.dot(self.p,self.q.T) inside each loop, while I am almost convinced it should be evaluated once per step.

Then it seems that you do matrix multiplication by hand, that probably can be speeded up with direct matrix mulitplication (numpy or scipy will do it faster than you by hand), something like that:

for step in xrange(steps):
    e = self.model - np.dot(self.p, self.q.T)
    p_temp = learning_rate * np.dot(e, self.q)
    self.q *= (1-regularization)
    self.q += learning_rate*(np.dot(e.T, self.p))
    self.p *= (1-regularization)
    self.p += p_temp

Answer 2

Are you sure you are implementing SGD? because in each step, you have to calculate the error of one single user-rating, not the error of the all rating matrix or maybe I can not understand this line of your code:

e=self.model-np.dot(self.p,self.q.T) #calculate error for gradient

And for the Scipy library, I am sure you will have a slow bottleneck if you want to access the elements of the sparse matrix directly. Instead of accessing elements of rating matrix from Scipy-sparse-matrix, you can bring the specific row and column into RAM in each step and then do your calculation.