Scipy - como otimizar ainda mais o código de matriz esparsa para descida gradiente estocástica

Question

Estou trabalhando na implementação do algoritmo estocástico de descida gradiente para sistemas de recomendação usando matrizes esparsas com Scipy.

Esta é a aparência de uma primeira implementação 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

Infelizmente, meu código ainda é muito lento, mesmo para uma pequena matriz de classificações 4x5.Eu estava pensando que isso provavelmente se deve à matriz esparsa do loop.Tentei expressar as alterações q e p usando uma indexação sofisticada, mas como ainda sou muito novo em scipy e numpy, não consegui descobrir uma maneira melhor de fazer isso.

Você tem alguma dica sobre como eu poderia evitar a iteração explícita nas linhas e colunas da matriz esparsa?

Answer 1

Quase esqueci tudo sobre sistemas de recomendação, então posso ter traduzido erroneamente seu código, mas você reavalia self.model-np.dot(self.p,self.q.T) dentro de cada loop, embora eu esteja quase convencido de que deve ser avaliado uma vez por etapa.

Então parece que você faz a multiplicação de matrizes manualmente, o que provavelmente pode ser acelerado com a multiplicação direta de matrizes (numpy ou scipy farão isso mais rápido do que manualmente), algo assim:

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

Tem certeza de que está implementando o SGD?porque em cada etapa você tem que calcular o erro de uma única avaliação do usuário, não o erro de toda a matriz de classificação ou talvez eu não consiga entender esta linha do seu código:

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

E para a biblioteca Scipy, tenho certeza que você terá um gargalo lento se quiser acessar diretamente os elementos da matriz esparsa.Em vez de acessar elementos da matriz de classificação da matriz esparsa do Scipy, você pode trazer a linha e coluna específicas para a RAM em cada etapa e então fazer seu cálculo.