Matrix Factorisation and Implicit Feedback

The Netflix Prize gave everyone a matrix of users by movies filled with one-to-five star ratings, 99% empty, and asked for the missing entries. Matrix factorisation won it: represent each user and each item as a vector in a shared \(d\)-dimensional space, and predict the rating as their dot product.

The bias terms do more work than people expect. \(b_u\) captures a user who rates everything highly, \(b_i\) an item everyone likes, and \(\mu\) the global mean. On the Netflix data, biases alone explained a substantial share of the variance, and the interaction term \(p_u^\top q_i\) handles only the part that is genuinely about this user's taste for this item (Koren, Bell and Volinsky, 2009, Matrix Factorization Techniques for Recommender Systems, IEEE Computer 42(8)).

The latent dimensions are not interpretable and do not need to be. They are whatever axes of variation the data supports, and they are identified only up to rotation, since \(P R\) and \(Q R^{-\top}\) give identical predictions for any invertible \(R\).

Why implicit feedback changes everything

Almost no production system has ratings. It has clicks, plays, purchases and dwell time, and that difference is structural rather than cosmetic.

There are no negatives. A rating of 1 star is explicit dislike. An unclicked item is ambiguous between "disliked", "never shown" and "not noticed". Training only on positives lets the model predict "interested" for everything, so negatives must be manufactured.

Confidence varies, preference is binary. Hu, Koren and Volinsky's formulation splits the observation into a binary preference \(p_{ui} = \mathbb{1}[r_{ui} > 0]\) and a confidence \(c_{ui} = 1 + \alpha r_{ui}\) that scales with the interaction count (Hu, Koren and Volinsky, 2008, Collaborative Filtering for Implicit Feedback Datasets, ICDM). Watching a show ten times is not ten times the preference; it is much higher confidence in the same preference. Unobserved entries get preference 0 with confidence 1, so they contribute weakly rather than not at all.

That formulation sums over all user-item pairs, which is \(|U|\times|I|\) terms, and the algorithmic contribution of the paper is that alternating least squares can exploit the structure to solve it in time linear in the observed entries rather than in the full matrix.

The objective becomes ranking, not regression. BPR takes the alternative route: for each user, sample an observed item \(i\) and an unobserved item \(j\), and maximise \(\log\sigma(\hat{x}_{ui} - \hat{x}_{uj})\), optimising the probability that the interacted item ranks above the non-interacted one (Rendle et al., 2009, BPR: Bayesian Personalized Ranking from Implicit Feedback, UAI). This targets ordering directly, which is what a recommendation list is.

Negative sampling strategy then becomes a central design decision. Uniform sampling mostly draws items the user would never have seen anyway, which teaches little. Popularity-weighted sampling produces harder negatives and corrects the popularity bias in the positives. In-batch negatives, using other users' positives within a minibatch, are the standard efficient approach in two-tower models and introduce their own popularity skew that requires a logQ correction.

When it breaks

Cold start is structural. A new user or item has no interactions, so its vector has no gradient and stays at initialisation. This is not a data-volume problem that resolves with scale; it is a permanent property of the formulation, and the answers are content features, hybrid models, or an explicit exploration policy.

Popularity dominates unless it is fought. Popular items appear in more interactions, get more gradient, and are recommended more, which creates more interactions. Without explicit debiasing, a recommender converges toward a popularity ranking with a personalisation veneer.

The dot product cannot express everything. A low-rank inner product imposes a specific geometry, and it cannot represent some intuitive preference structures, including certain forms of triangle inequality violation. This is the argument that motivated metric-learning and neural alternatives, and the empirical picture is contested: careful baselines have repeatedly matched or beaten neural collaborative filtering methods that claimed to supersede them.

Offline evaluation is optimistic in a specific way. Held-out interactions were generated under the deployed recommender, so a model that reproduces its predecessor's choices scores well. This is the same feedback loop as position bias in search, and it is why recommender research disagrees with online results as often as it does.