What is a recommender system?

The problem, stated#

Let $U$ be the set of users and $I$ the set of items. A recommender estimates a utility function

$$ \hat{r} : U \times I \rightarrow \mathbb{R} $$

and returns, for each user $u$, the top-$N$ set

$$ R_N(u) = \operatorname*{arg\,max}_{S \subseteq I \setminus I_u,\; |S| = N} \; \sum_{i \in S} \hat{r}(u, i) $$

Where:

• $I_u \subseteq I$ — the items user $u$ has already consumed, excluded from candidacy.
• $\hat{r}(u,i)$ — the estimated utility of item $i$ for user $u$.
• $N$ — the slate size, typically 10 to 50 per row of a page.

Writing the objective as a sum over $S$ makes top-$N$ selection separable, so greedy selection of the $N$ highest scores is optimal. That separability is an assumption, not a fact. The moment the objective rewards diversity or penalises near-duplicates, utility becomes set-valued, greedy selection stops being optimal, and the problem turns into submodular maximisation. See diversity and filter bubbles.

Why the industrial pipeline is staged#

Full scoring costs $O(|U| \cdot |I| \cdot c)$ per refresh, with $c$ the cost of one model evaluation. For $|I| \sim 10^8$ and a deep ranker, that is unaffordable by several orders of magnitude.

The standard decomposition was made canonical by Covington, Adams and Sargin (2016), Deep Neural Networks for YouTube Recommendations:

Retrieval must factorise into $f(u)^\top g(i)$ so item vectors can be precomputed and searched with approximate nearest neighbours. That constraint is why two-tower models dominate retrieval. The reason is architectural, not empirical.

Feedback loops make the data non-i.i.d.#

The training data of a deployed recommender is generated by the previous version of that recommender. Logged interactions are therefore missing-not-at-random: the exposure probability $p(o_{ui} = 1)$ is a function of the old policy, and is confounded with relevance.

Chaney, Stewart and Engelhardt (2018), How algorithmic confounding in recommendation systems increases homogeneity, formalise the consequence. Naive offline training amplifies whatever bias the previous policy carried, and supervised evaluation on logged data measures agreement with the old policy rather than utility.

Inverse propensity scoring corrects the estimator when exposure probabilities are known or modelled:

$$ \hat{R}{\text{IPS}}(\pi) = \frac{1}{|D|} \sum{(u,i) \in D} \frac{\mathbb{1}[\pi \text{ shows } i \text{ to } u]}{p(o_{ui}=1)} \; r_{ui} $$

Where $\pi$ is the policy under evaluation, $D$ the logged dataset, $r_{ui}$ the observed reward, and $p(o_{ui}=1)$ the logging propensity. The estimator is unbiased when propensities are correct and bounded away from zero. Variance explodes when they are small, which is why clipped and self-normalised variants are used in practice. Schnabel et al. (2016), Recommendations as Treatments, is the reference treatment.

The offline–online gap#

Offline metric improvements transfer to online lift unreliably. Three mechanisms account for most of it:

1. Exposure bias, above — the test set contains only items the old system chose to show.
2. Objective mismatch — offline metrics score a ranking, online metrics score user behaviour across sessions and weeks.
3. Presentation effects — click probability depends on slot, thumbnail and neighbouring items, none of which appear in an offline ranking metric.

Dacrema, Cremonesi and Jannach (2019), Are we really making much progress?, reproduced 18 neural recommender papers and found 11 were beaten by properly tuned simple baselines, most often item-kNN or a linear model. The methodological point survives whatever you conclude about the individual reproductions: tuning effort spent on baselines is systematically smaller than tuning effort spent on the proposed method.

Foundational reading#

• Resnick et al. (1994), GroupLens: An Open Architecture for Collaborative Filtering of Netnews — the first user-based collaborative filtering system.
• Linden, Smith and York (2003), Amazon.com Recommendations: Item-to-Item Collaborative Filtering — why item-item beat user-user in production.
• Koren, Bell and Volinsky (2009), Matrix Factorization Techniques for Recommender Systems — the Netflix Prize synthesis.
• Covington, Adams and Sargin (2016), Deep Neural Networks for YouTube Recommendations — the retrieval-then-ranking pipeline as deployed.
• Dacrema et al. (2019), Are we really making much progress? — arxiv.org/abs/1907.06902
• Chaney et al. (2018), How Algorithmic Confounding in Recommendation Systems Increases Homogeneity — arxiv.org/abs/1710.11214

What to learn next#

• Matrix factorisation — the model that defined the field for a decade.
• Two-tower retrieval models — the retrieval stage as it is built today.
• A/B testing a recommender — the only measurement that settles the offline–online gap.