Scipy - как дополнительно оптимизировать разреженный матричный код для стохастического градиентного спуска

Question

Я работаю над реализацией алгоритма стохастического градиентного спуска для рекомендательных систем, использующих разреженные матрицы со Scipy.

Вот как выглядит первая базовая реализация:

    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

К сожалению, мой код все еще довольно медленный, даже для небольшой матрицы рейтингов 4x5. Я думал, что это, вероятно, из-за разреженной матрицы для цикла. Я попытался выразить изменения q и p, используя причудливую индексацию, но, поскольку я все еще довольно новичок в суетливости и неряшливости, я не мог придумать лучшего способа сделать это.

Есть ли у вас какие-либо указатели на то, как я мог бы избежать итерации по строкам и столбцам разреженной матрицы явно?

Answer 1

Я почти забыл все о рекомендательных системах, поэтому я могу ошибочно перевести ваш код, но вы переоцениваете self.model-np.dot(self.p,self.q.T) внутри каждого цикла, хотя я почти уверен, что его следует оценивать один раз за шаг.

Тогда кажется, что вы выполняете умножение матриц вручную, что, вероятно, может быть ускорено с помощью прямого умножения матриц (numpy или scipy сделают это быстрее, чем вы вручную), что-то вроде этого:

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

Вы уверены, что внедряете SGD? потому что на каждом шаге вы должны вычислить ошибку одного отдельного рейтинга пользователя, а не ошибку всей матрицы рейтинга, или, может быть, я не могу понять эту строку вашего кода:

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

Что касается библиотеки Scipy, я уверен, что у вас будет медленное узкое место, если вы захотите получить доступ к элементам разреженной матрицы напрямую. Вместо того, чтобы обращаться к элементам матрицы рейтинга из Scipy-sparse-matrix, вы можете помещать определенные строки и столбцы в RAM на каждом шаге, а затем выполнять свои вычисления.