Alternating Least Squares Step

Write the user half-step of alternating least squares (ALS) for matrix factorisation.

The matrix factorisation loss is not convex in P and Q together. But with the item vectors Q held fixed, it is a ridge regression for each user, which has an exact solution. ALS alternates: solve for every user with Q fixed, then for every item with P fixed, and repeat. Each user is independent, so the step runs in parallel, which is why large systems such as Spark use ALS.

For user u, let O be the items the user rated (mask[u, i] == 1), Q_O the rows of Q for those items, and r_O the ratings. Then

P[u] = solve(Q_O^T Q_O + reg * I, Q_O^T r_O)

A user with no ratings gets a zero vector.

Function signature

def als_update_users(R, mask, Q, reg):

Example

Input

R    = np.array([[4.0, 0.0, 2.0],
                 [0.0, 0.0, 0.0]])
mask = (R > 0).astype(float)
Q    = np.array([[1.0, 0.0], [0.5, 0.5], [0.0, 1.0]])
als_update_users(R, mask, Q, reg=1.0)

Output

array([[2., 1.],
       [0., 0.]])

Reasoning

User 0 rated items 0 and 2, whose vectors are (1, 0) and (0, 1). So Q_O^T Q_O = I, and the system is 2 I p = (4, 2), giving p = (2, 1). The penalty halves what plain least squares would give. User 1 rated nothing, so its vector is zero.

Constraints and notes

• R and mask have shape (n_users, n_items), and Q has shape (n_items, k).
• Use mask to find observed entries. A rating of 0 with mask = 1 is a real rating of zero.
• Return P with shape (n_users, k).