Matrix Factorisation by SGD

Train a matrix factorisation recommender with stochastic gradient descent.

Matrix factorisation gives every user a vector P[u] and every item a vector Q[i], both of length k. The predicted rating is their dot product. The vectors are fitted to the observed ratings only, with an L2 penalty:

loss = sum over observed (u, i) of (R[u, i] - P[u] . Q[i])^2
       + reg * (|P[u]|^2 + |Q[i]|^2)

This is the model that won much of the Netflix Prize.

For each epoch, visit the observed entries (R[u, i] > 0) in row-major order: user 0's items left to right, then user 1's, and so on. For each entry:

e    = R[u, i] - P[u] . Q[i]
P[u] = P[u] + lr * (e * Q[i] - reg * P[u])
Q[i] = Q[i] + lr * (e * P[u] - reg * Q[i])

Both updates must use the values from before this entry's update. Keep a copy of the old P[u] for the Q[i] update.

Function signature

def mf_sgd(R, P, Q, lr, reg, epochs):

Example

Input

R = np.array([[5.0, 0.0],
              [0.0, 3.0]])
P = np.ones((2, 1))
Q = np.ones((2, 1))
mf_sgd(R, P, Q, lr=0.1, reg=0.0, epochs=1)

Output

(array([[1.4], [1.2]]), array([[1.4], [1.2]]))

Reasoning

The first observed entry is (0, 0). Its error is 5 - 1 = 4, so P[0] and Q[0] both become 1 + 0.1 * 4 * 1 = 1.4. The next is (1, 1), with error 3 - 1 = 2, so P[1] and Q[1] become 1.2.

Constraints and notes

• R has shape (n_users, n_items), with 0 meaning missing.
• P has shape (n_users, k) and Q has shape (n_items, k).
• Return new arrays (P, Q). Do not modify the inputs.