CODEWITHSUNDEEP
pythonnumpyscipysparse-matrixmatrix-factorization
Ana Todor
Ana Todor

Reputation: 801

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

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?

Upvotes: 4

Views: 1858

Answers (2)

soroush
soroush

Reputation: 59

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.

Upvotes: 0

alko
alko

Reputation: 48317

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

Upvotes: 1

Related Questions