Recommendation system

Item-based collaborative filtering, formally#

Let $R \in \mathbb{R}^{m \times n}$ be the rating matrix over $m$ users and $n$ items, with observed index set $\mathcal{O} = {(u,i) : r_{ui} \text{ is known}}$.

Adjusted cosine similarity between items $i$ and $j$ (Sarwar et al., 2001):

$$ s_{ij} = \frac{\sum_{u \in U_{ij}} (r_{ui} - \bar{r}i)(r{uj} - \bar{r}j)} {\sqrt{\sum{u \in U_{ij}} (r_{ui} - \bar{r}i)^2}\; \sqrt{\sum{u \in U_{ij}} (r_{uj} - \bar{r}_j)^2}} $$

Where:

• $r_{ui}$ — the rating user $u$ gave item $i$.
• $U_{ij}$ — the set of users who rated both $i$ and $j$.
• $\bar{r}_i$ — the mean observed rating of item $i$.
• $s_{ij} \in [-1, 1]$ — the resulting similarity.

The prediction for an unseen pair, over the top-$k$ neighbourhood $N_k(i)$ of items the user has rated:

$$ \hat{r}{ui} = \frac{\sum{j \in N_k(i)} s_{ij}\, r_{uj}}{\sum_{j \in N_k(i)} |s_{ij}|} $$

The implementation above clips $s_{ij}$ at zero, which makes the denominator $\sum \max(s_{ij}, 0)$. That is a deliberate departure from the formula: negative-similarity terms are poorly calibrated on sparse data and frequently degrade top-$k$ ranking quality even when they improve RMSE.

Shrinkage is the standard correction for thin overlaps. With $|U_{ij}|$ small, $s_{ij}$ is high-variance, so multiply by a shrink factor:

$$ \tilde{s}{ij} = \frac{|U{ij}|}{|U_{ij}| + \lambda}\, s_{ij}, \qquad \lambda \approx 100 $$

Omitting this is the most common reason a textbook implementation underperforms a popularity baseline.

Cost#

• Similarity matrix: $O(n^2 \bar{u})$ time and $O(n^2)$ memory, where $\bar{u}$ is the mean number of raters per item. Intractable beyond roughly $10^5$ items without truncation.
• Truncated to the top $k$ neighbours: $O(nk)$ memory, and scoring one user is $O(|I_u| k)$ for $|I_u|$ rated items.
• The matrix is recomputed offline. Online serving is a sparse lookup, which is why this method survived into production systems long after better-scoring alternatives appeared (Linden et al., 2003, describing Amazon).

Matrix factorisation#

The dominant alternative learns latent factors $p_u, q_i \in \mathbb{R}^f$ (Koren et al., 2009):

$$ \hat{r}_{ui} = \mu + b_u + b_i + q_i^{\top} p_u $$

$\mu$ is the global mean, $b_u$ and $b_i$ are user and item biases. Fitting minimises regularised squared error over observed entries only:

$$ \min_{p, q, b} \sum_{(u,i) \in \mathcal{O}} \left(r_{ui} - \hat{r}_{ui}\right)^2

• \lambda \left(|p_u|^2 + |q_i|^2 + b_u^2 + b_i^2\right) $$

Solved by SGD or by alternating least squares, which is convex in $p$ with $q$ fixed and vice versa, and parallelises cleanly across users.

The bias terms carry more weight than newcomers expect. On the Netflix Prize data, $\mu + b_u + b_i$ alone recovered a substantial share of the achievable improvement over the global mean. Report a bias-only baseline before claiming your factor model works.

Implicit feedback#

Explicit ratings are rare and non-random. For observed behaviour, Hu et al. (2008) split the signal into a binary preference $p_{ui} = \mathbb{1}[r_{ui} > 0]$ and a confidence $c_{ui} = 1 + \alpha r_{ui}$, then minimise over all cells, unobserved included:

$$ \min_{p,q} \sum_{u,i} c_{ui}\left(p_{ui} - q_i^{\top} p_u\right)^2 + \lambda\left(|p_u|^2 + |q_i|^2\right) $$

The sum over $m \times n$ cells is made tractable by an algebraic identity that reuses $Q^{\top}Q$ across users, giving $O(f^2 |\mathcal{O}| + f^3 n)$ per iteration rather than $O(f^2 mn)$.

BPR (Rendle et al., 2009) takes the ranking view instead, optimising a pairwise objective over triples $(u, i, j)$ with $i$ observed and $j$ sampled:

$$ \max_{\Theta} \sum_{(u,i,j)} \ln \sigma!\left(\hat{x}{uij}\right) - \lambda |\Theta|^2, \qquad \hat{x}{uij} = \hat{r}{ui} - \hat{r}{uj} $$

This optimises AUC directly, which matches the top-$k$ task better than squared error does.

Evaluation, and the traps in it#

Offline metrics: recall@k, precision@k, MAP@k, NDCG@k. Rating-error metrics (RMSE, MAE) are weakly correlated with top-$k$ ranking quality and should not be the headline number.

Four systematic biases distort offline evaluation:

1. Missing not at random. Users rate what they chose to consume. $\Pr(\text{observed})$ depends on the rating itself, so the test set is not a random sample of the truth. Marlin and Zemel (2009) established this empirically.
2. Popularity bias. Cremonesi et al. (2010) showed that a plain popularity ranking beats several published personalised methods under common protocols. Report it as a baseline; if you do not beat it, say so.
3. Sampled metrics. Ranking the true item against 100 sampled negatives, rather than the full catalogue, produces metrics that are not monotone in the full-catalogue metric (Krichene and Rendle, 2020). Several reported improvements dissolve under full ranking.
4. Feedback loops. Training data is generated by the previous model. Chaney et al. (2018) show this drives homogenisation. Logged propensities and inverse-propensity weighting (Schnabel et al., 2016) are the standard partial correction.

Dacrema et al. (2019) reproduced eighteen neural recommendation papers from top venues and found that most were beaten by well-tuned nearest-neighbour or linear baselines. Treat that as the prior when reading new architecture claims in this area.

Current practice#

Industrial systems are two-stage. Retrieval narrows millions of items to hundreds using a two-tower encoder — separate user and item towers trained with sampled softmax, so item vectors precompute into an ANN index (Covington et al., 2016; Yi et al., 2019). Ranking then scores those hundreds with a heavy model that can afford cross-features, trained on the exact objective the product cares about.

Sequential models treat the interaction history as an ordered sequence: SASRec (Kang and McAuley, 2018) applies causal self-attention, BERT4Rec (Sun et al., 2019) applies masked-item prediction. They help most where order genuinely carries signal, such as short-video and music.

Rendle et al. (2020) showed that a properly tuned dot product outperforms the learned MLP similarity of Neural Collaborative Filtering. The dot product remains the default for retrieval, and it is what makes ANN indexing possible at all.

Papers#

• Sarwar et al., Item-Based Collaborative Filtering Recommendation Algorithms, WWW 2001
• Linden et al., Amazon.com Recommendations: Item-to-Item Collaborative Filtering, IEEE Internet Computing 2003
• Hu, Koren and Volinsky, Collaborative Filtering for Implicit Feedback Datasets, ICDM 2008
• Rendle et al., BPR: Bayesian Personalized Ranking from Implicit Feedback, UAI 2009 — arxiv.org/abs/1205.2618
• Koren, Bell and Volinsky, Matrix Factorization Techniques for Recommender Systems, IEEE Computer 2009
• Cremonesi, Koren and Turrin, Performance of Recommender Algorithms on Top-N Recommendation Tasks, RecSys 2010
• Covington, Adams and Sargin, Deep Neural Networks for YouTube Recommendations, RecSys 2016
• Schnabel et al., Recommendations as Treatments, ICML 2016 — arxiv.org/abs/1602.05352
• Kang and McAuley, Self-Attentive Sequential Recommendation, ICDM 2018 — arxiv.org/abs/1808.09781
• Dacrema, Cremonesi and Jannach, Are We Really Making Much Progress?, RecSys 2019 — arxiv.org/abs/1907.06902
• Krichene and Rendle, On Sampled Metrics for Item Recommendation, KDD 2020
• Rendle et al., Neural Collaborative Filtering vs. Matrix Factorization Revisited, RecSys 2020 — arxiv.org/abs/2005.09683

What to learn next#

• Model evaluation — ranking metrics and honest baselines.
• Embeddings — the representation two-tower retrieval depends on.
• Vector databases — approximate nearest neighbour search at catalogue scale.