Recommendations by matrix factorization

Four thousand readers gave a thousand popular books 277,181 ratings from one to five. If they are written into a table “reader × book”, fewer than seven per cent of the cells are filled: each reader knows a few dozen books out of a thousand. A recommendation is a guess at what stands in an empty cell. Matrix factorization guesses like this: it assigns each reader and each book ten numbers, and the rating is their dot product. Nobody sets the numbers in advance; they come out of the ratings. And for books loved by the same people they turn out alike: next to The Hobbit is The Lord of the Rings, next to Pride and Prejudice the other novels of Austen.

Mark a few books, and the model will find your vector and suggest the books it points to. The dots on the map are all thousand books along the two main directions of their vectors (as in principal component analysis); the arrow is your taste in the same axes. The model knows no genres: books end up next to each other only because the same readers love and dislike them. The map shows just two directions of the ten, so closeness on it is approximate; the model looks for “similar books” across all ten numbers, and that is how The Hobbit finds the three volumes of The Lord of the Rings.

The idea

A prediction is made of four parts:

r̂_ui = μ + b_u + b_i + p_u · q_i.

μ is everyone’s mean rating, b_u how much more generous the reader is than average, b_i how much more the book is loved than average, and p_u · q_i the match of tastes: vectors of k numbers. If all this is taken to hold for every known rating, the result is a table of rank k with biases, hence “matrix factorization”: the table of ratings ≈ P · Q^T.

The numbers are chosen so that on the known ratings the sum of squared errors plus the penalty λ·(|p|² + |q|² + b²) is smallest. As a whole this problem is not convex, but if the book vectors are frozen, then for each reader it is an ordinary linear regression with k + 1 unknowns, and it is solved exactly. So it is solved alternately: with the books known, all the readers; with the readers known, all the books. This is ALS, alternating least squares.

The value converges, but not necessarily to the best possible: the problem is not convex, and ALS may stop at a point where the signs of the vectors have “failed to agree”. In practice it is run several times from different random vectors. And a new reader who arrives after training does not require retraining the model: their vector is the solution of the same system over the vectors of the books they rated. That is how the scene above works.

Code

The listing takes the 200 most often rated books and 2890 readers with 25 ratings among them; every tenth rating is held out for checking. The error is the root mean square miss on the held-out ratings. If everyone is given the mean, 3.95, the miss is 1.024 stars. The book’s mean gives 0.977. Reader and book biases, 0.902: the bias for the reader’s generosity took more off the error than the book’s mean before it. Vectors of five numbers, 0.865. The gain of the last stage seems modest, but it is exactly what tells “popular” from “yours”: the closest to The Hobbit are the three books of The Lord of the Rings, to Twilight its sequels, and to a reader of Austen, Brontë and Fitzgerald who dislikes Dan Brown the model suggests Wuthering Heights, The Grapes of Wrath and Romeo and Juliet.

The recommendations are ordered by the match of taste p · q, without the book’s bias. With the bias, books loved by everyone come to the top, comic collections and favourite fantasy series, and different readers get the same recommendations.

How many numbers and what penalty

The scene’s model is trained on the whole sample, and the chart shows its error on the held-out ratings for vectors of 0 to 40 numbers. With a noticeable penalty, λ = 15, long vectors help a little: from 0.887 without vectors to 0.851 with forty numbers. With a weak penalty, λ = 1, it is the other way round: with 40 numbers the error is 1.130, worse than giving everyone the mean, 1.006. Forty numbers for a reader who has 69 ratings on average is almost as many unknowns as equations, and the model memorises noise. The penalty keeps the numbers from growing where the data does not back them up.

What it costs

An ALS round assembles a (k + 1) × (k + 1) system for each reader and each book, O(k²) per rating for the assembly, and solves it by Gaussian elimination in O(k³). In all, O(N·k² + (u + i)·k³) per round, and there are usually few rounds. All the systems of one half-round are independent, so ALS splits well across machines; that is why it is chosen for big data. A new reader is one system, microseconds.

The other way is gradient descent one rating at a time (Simon Funk, 2006): a step is cheaper and needs less memory, but the learning rate and the number of passes have to be tuned. On implicit data, “watched”, “listened”, where an empty cell also means something, ALS is more advantageous: the empty cells enter the system as one shared matrix.

Where it is easy to go wrong

• Empty cells as zeros. If zeros are written into the gaps and the whole table is factorized (say, by the singular value decomposition), the model will predict zeros, since they are the majority. The error is computed only over known ratings.
• No penalty. A reader with three ratings has ten unknowns: without λ the system is degenerate, and with a small λ the vectors fit every rating and predict the rest at random.
• Checking on the same ratings. On the ratings used for training the error falls with every number added to the vector; the honest error is only on held-out ones.
• Popularity instead of taste. The book bias b_i honestly predicts the rating, but in recommendations it pulls the same things to the top for everyone. For “you may also like” it is weakened or removed.
• The cold start. A new book has no ratings and no vector; a new reader has none until they mark something. Here the features of the book itself come to the rescue: genre, author, text.

Where it works

Recommendations. Films, books, music, goods: “you may also like” and “watched together with this” are built on taste vectors or their descendants, models that add time, context and features.

Big and implicit data. Spark MLlib has ALS for explicit and implicit ratings, and the implicit library has ALS after the work of Yifan Hu, Yehuda Koren and Chris Volinsky (2008) for clicks and plays, where the “ratings” are how many times a person opened something.

Similar items. Close book vectors are books loved by the same people; this is the basis of “similar products”, even when their descriptions are entirely different.

Gaps in measurements. A table of sensors over time with some measurements lost, or a table of network distances measured not for all pairs: the same recovery of a low-rank matrix from some of its cells.

History

In October 2006 Netflix released a hundred million film ratings and announced a contest: improve its recommendation system by ten per cent. Two months later Brandyn Webb, writing as Simon Funk, described on a blog a factorization of ratings by gradient descent one rating at a time, and it became the basis of almost all strong solutions. In 2008 Yunhong Zhou and co-authors proposed for the same contest ALS with a penalty, which splits well across machines. Yehuda Koren, Robert Bell and Chris Volinsky added reader and film biases, time and implicit data; their team, together with co-authors, won the contest in September 2009 by improving the original system by 10.06%. The 2009 survey by Koren, Bell and Volinsky, “Matrix Factorization Techniques for Recommender Systems”, became the standard introduction to the topic. And the idea of the best approximation of a matrix by a low rank itself goes back to the 1936 theorem of Carl Eckart and Gale Young, for a fully known matrix.

Problems

Fit vectors to known cells so that the error with the penalty is as small as possible.