Scipy: cómo optimizar aún más el código de matriz dispersa para el descenso de gradiente estocástico

Question

Estoy trabajando en la implementación del algoritmo de descenso de gradiente estocástico para sistemas de recomendación que utilizan matrices dispersas con Scipy.

Así es como se ve una primera implementación básica:

    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

Desafortunadamente, mi código sigue siendo bastante lento, incluso para una matriz de clasificación pequeña de 4x5.Estaba pensando que esto probablemente se deba a la escasa matriz del bucle for.Intenté expresar los cambios q y p usando una indexación elegante, pero como todavía soy bastante nuevo en scipy y numpy, no pude encontrar una mejor manera de hacerlo.

¿Tiene alguna sugerencia sobre cómo podría evitar la iteración explícita sobre las filas y columnas de la matriz dispersa?

Answer 1

Casi me olvido de todo sobre los sistemas de recomendación, por lo que es posible que haya traducido erróneamente su código, pero lo reevalúe self.model-np.dot(self.p,self.q.T) dentro de cada bucle, aunque estoy casi convencido de que debería evaluarse una vez por paso.

Entonces parece que haces la multiplicación de matrices a mano, que probablemente se pueda acelerar con la multiplicación de matrices directa (numpy o scipy lo harán más rápido que tú a mano), algo así:

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

¿Está seguro de que está implementando SGD?Debido a que en cada paso, debe calcular el error de una sola calificación de usuario, no es el error de la matriz de calificación y tal vez, no puedo entender esta línea de su código:

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

y para la biblioteca Scipy, estoy seguro de que tendrá un cuello de botella lento si desea acceder directamente a los elementos de la matriz escasa.En lugar de acceder a elementos de la matriz de calificación de la matriz Scipy-Sparse-Matrix, puede llevar la fila y la columna específicas a la RAM en cada paso y luego realizar su cálculo.