Chapter 01

Foundations & the Data Model

Recommender systems are, at their core, the problem of completing a giant, mostly-empty table. Before any algorithm you must agree on what goes in the cells, what the holes mean, and where the numbers come from — the URM, the ICM, explicit vs implicit feedback, and the sparsity that defines the field.

Reading: ~50 min Interactive: 3 widgets Source: Polimi Recommender Systems 2024/25 — Foundations & the Data Model · Aggarwal, Recommender Systems — The Textbook, Ch. 1

01 · Motivation

Catalogs grew faster than human attention.

A modern catalog — Netflix, Spotify, Amazon, a research-paper database — contains far more items than any user can browse in a lifetime. The classical interface, search, only helps when the user already knows what they want. Recommender systems fill the harder gap: surfacing relevant items a user does not yet know they want.

why

Mental model

A recommender is a function $f(u, i \mid \text{history}) \rightarrow \text{score}$ that ranks every (user, item) pair. The training data is the table of past interactions; the test is whether the user clicks, watches, or buys what we put on top.

Two empirical regularities make this both possible and hard:

sparsity — for any single user, the fraction of the catalog they have touched is tiny (often $< 10^{-4}$ ). Most of the table is empty.
the long tail — a few items get a huge share of interactions; the vast majority get almost none. Personalization is precisely the act of pulling items from the tail to the right user.

02 · Map of the field

A taxonomy of recommenders

One tree to keep in your head for the entire course.

The course follows a single decision tree — memorise this picture. The first split asks does the model use the identity of the target user? If no → Non-Personalized. If yes → Personalized, with sub-families distinguished by what signal they exploit.

The two top-level inputs to all of these are the matrices we define next: the URM (who interacted with what) and the ICM (what each item is). Content-Based mostly reads the ICM; Collaborative mostly reads the URM; Hybrids mix both; Context-Aware adds a third axis — time, location, device.

key

How to remember the split

Content-based = “find items similar to ones the user liked, by their features.” Collaborative = “find items liked by users similar to me, by their behaviour.” The first reads the ICM, the second reads the URM.

03 · The first matrix

The User Rating Matrix (URM)

Rows are users, columns are items, cells are interactions.

The URM is the central object of collaborative filtering. Each row is a user, each column is an item, and the value $r_{ui}$ records the interaction between user $u$ and item $i$ .

0 means unknown, not disliked

The URM stores observed interactions only. A zero is missing data — the user has never been shown the item, or simply never reacted. Treating $r_{ui}=0$ as a negative rating is the most common modelling mistake in this course.

Hands-on

URM / ICM explorer · the toy catalog

The same 6 users × 8 movies (× 9 attributes) reused across the whole course. Click a cell to edit it; switch to Implicit to watch 1–5 ratings collapse to 0/1, and to ICM to see what each movie is made of. A 0 is unknown, not disliked.

density: 64.6% (31/48)shape: 6 × 8

TopGunMIInterMartianNottingLoveActAvengLaLaAliceBobCarlaDanEvaFinn

TakeawayTwo matrices, two worldviews: the URM is what users did, the ICM is what items are. Collaborative filtering reads the URM, content-based reads the ICM, hybrids read both.

Formal Definition 1.1 — the URM

Let $\mathcal{U}$ be the set of users and $\mathcal{I}$ the set of items. The User Rating Matrix is

URM

R \in \mathbb{R}^{\lvert\mathcal{U}\rvert \times \lvert\mathcal{I}\rvert}, \qquad r_{ui} = \begin{cases} k \in \{1,\dots,K\} & \text{explicit feedback (e.g. } K=5) \\ 1 & \text{implicit feedback observed} \\ 0 & \text{unknown} \end{cases}

The notation $r_{ui}$ is the value at row $u$ , column $i$ . We use this symbol for the rest of the course.

04 · The second matrix

The Item Content Matrix (ICM)

Items described by their attributes — the side door into recommendation.

The ICM is orthogonal to the URM: instead of recording who liked what, it describes what each item is made of. Rows are items; columns are attributes (for movies: actors, genres, directors, decade, tags). A cell is 1 if the item has the attribute, 0 if not; weighted variants (e.g. TF-IDF) replace 1s with real numbers. Toggle the explorer above to ICM — those are exactly the rows you see: Top Gun has a 1 in the Cruise column, and so on.

why

Two matrices, two worldviews

The URM is what users did. The ICM is what items are. Content-Based Filtering only needs the ICM; pure Collaborative Filtering only needs the URM; hybrids combine both.

Formal Definition 1.2 — the ICM

Let $\mathcal{A}$ be the set of attributes. The Item Content Matrix is

ICM

F \in \mathbb{R}^{\lvert\mathcal{I}\rvert \times \lvert\mathcal{A}\rvert}, \qquad f_{ia} = \begin{cases} 1 & \text{item } i \text{ has attribute } a \\ w_{ia} \in (0,1] & \text{weighted version} \\ 0 & \text{otherwise} \end{cases}

An item is represented by the row vector $f_i \in \mathbb{R}^{\lvert\mathcal{A}\rvert}$ . Content-based similarity between items reduces to a cosine (or Jaccard) similarity between these rows — Chapter 4.

05 · Where the numbers come from

Explicit vs. implicit feedback

Two ways to fill the URM — with very different statistics.

The URM can be populated in two fundamentally different ways. explicit feedback means the user actively expresses an opinion: a 1–5 star rating, a thumbs up/down, a written review score. implicit feedback means we infer preference from behaviour: a click, a play, the fraction of a video watched, a purchase, dwell time.

Design choices for explicit scales

Large scales (1–10) carry more information per rating but require more effort, so users give fewer ratings.
Small scales (thumbs up/down) need almost no effort, so users give many more ratings — at the cost of resolution.
Even scales (1–4) force the user to pick a side; odd scales (1–5) include a neutral middle users gravitate toward — a real source of bias.

Examples of implicit signals — viewing time and fraction watched, streaming and skip counts, purchases and returns, clicks, dwell time, scroll depth.

Hands-on

Feedback lens · explicit vs implicit

One user's activity over four days. Apply the explicit lens to keep only star ratings; the implicit lens to keep any behavioural signal. Watch the coverage change — explicit is sparser but signed; implicit is denser but ambiguous (a click is not a like).

coverage 30% · 6/20

TopGunMIInterMartianNottingDay 1click★4view★5·Day 2click·view★2buyDay 3·click·★5viewDay 4view★4click·★5

TakeawayExplicit feedback (stars) is scarce but carries a clear sign; implicit feedback (clicks, plays, buys) is abundant but has no observed negatives — the one-class problem that BPR (Ch. 7) is built to handle.

The one-class problem

Implicit feedback usually has no negatives — we observe presence but never explicit absence. Algorithms designed for explicit data (e.g. RMSE-trained matrix factorization) often misbehave on implicit data. Chapter 7 (BPR) is exactly the response to this asymmetry.

06 · The shape of real data

Sparsity & the long tail

Why “the matrix is empty” is the defining challenge of the field.

Real URMs are spectacularly sparse. Typical URM density is $< 0.01\% \approx 10^{-4}$ ; the Netflix Prize URM is $\approx 0.002\%$ ; MovieLens is $\approx 0.005\%$ . Roughly 99.99% of the table is unknown. Every recommendation algorithm is, in some sense, a principled way to guess about that 99.99%.

Sparsity is not uniform: a handful of items dominate and most have very few interactions — the long tail. The recommender’s job is to serve the head and bring the tail to life, but the tail is also where the cold start problem lives (items with too few interactions for collaborative signals to work).

Hands-on

Sparsity & the long tail

Our toy URM is 64.6% dense — already mostly empty. Real catalogs are thousands of times sparser. Drag the sliders to feel how density and skew scale up, and how the cold-start zone grows.

Users10,000

Items5,000

Density0.2000%

Skew (tail)1.80

cells: 50,000,000observed: 100,000cold items (<3): 3,750 (75%)

TakeawayReal URMs are below 0.01% dense — 99.99% of the table is unknown. The skew means most items live in the cold-start tail, where collaborative signals are too thin to help.

Formal Definition 1.3 — density & sparsity

Given a URM $R$ , denote the set of observed interactions $\Omega = \{(u,i) : r_{ui} \neq 0\}$ . Then

Density

\text{density}(R) = \frac{\lvert\Omega\rvert}{\lvert\mathcal{U}\rvert \cdot \lvert\mathcal{I}\rvert}, \qquad \text{sparsity}(R) = 1 - \text{density}(R).

For real catalogs density is $\ll 1\%$ . This single number is the reason every algorithm we study is either a way of generalizing across the empty cells, or a way of coping with them being empty.

07 · Self-check

Three questions before you move on

In a URM, a value of 0 in cell r(u,i) means:

The Item Content Matrix (ICM) has:

Roughly, the density of the Netflix Prize URM is closest to:

08 · Recap

One-screen summary

Chapter 01 — load-bearing ideas

The URM holds interactions (users × items). 0 = unknown, never “disliked”.
The ICM holds item content (items × attributes). It is the back door for content-based methods.
Real URMs are $< 0.01\%$ dense. Sparsity and the long tail are not bugs of the data — they are the problem statement of the entire course.
Explicit feedback is signed but scarce; implicit feedback is abundant but positive-only (the one-class problem).
Notation to keep: $R$ for the URM, $F$ for the ICM, $r_{ui}$ for a single cell, $\text{density}(R)=\lvert\Omega\rvert/(\lvert\mathcal U\rvert\cdot\lvert\mathcal I\rvert)$ .

09 · Exam · past papers

Past-paper questions

A curated bank of real Polimi past-paper items for this chapter. Each opens to a model answer of the standard graders look for.

Past paper Exam 2020 · 2 pts — personalized vs non-personalized

Q. Discuss the main differences between personalized and non-personalized recommenders, give an example algorithm for each, and explain why it belongs there.

Model answer. Non-personalized recommenders produce the same ranking for everyone: the score depends only on aggregate item statistics, $f(i)$ , not on the target user. Example — Top-Popular: it ranks items by total interactions (column sums of the URM); user $u$ never enters the formula. Personalized recommenders tailor the list: the prediction $\hat r_{ui}=f(u,i)$ uses user $u$ ‘s own history. Example — user-based CF: it recommends items liked by users similar to $u$ . The core difference is the dependency on $u$ .

Past paper FT-Jan26 · 4+2 pts — implicit vs explicit ratings; multi-stage recommenders

Q (4 pts). Describe the differences between implicit and explicit ratings; give an algorithm designed for each and explain why. Q (2 pts). What is a multi-stage recommender and what is the purpose of each stage?

Model answer. Explicit ratings are stated preferences (1–5 stars): informative and signed (a low rating is a real negative) but scarce and biased toward motivated users. Implicit ratings are inferred from behaviour: abundant but noisy and positive-only — a 0 means “unknown”, so there are no observed negatives, only confidence. Explicit → Funk SVD / MF with RMSE on the observed entries (it predicts the rating value). Implicit → BPR (or ALS with confidence weighting): it optimises a ranking from “positive > unobserved” pairs, precisely because true negatives are missing. Multi-stage recommender — a pipeline that trades scale for accuracy: (1) candidate generation / retrieval (cheap, recall-oriented, scans the whole catalog → a few hundred candidates); (2) ranking (expensive, precision-oriented, re-scores only that small set); (3) re-ranking (optional: diversity, freshness, business rules). You cannot run a heavy model over millions of items per request.

Past paper FT-Feb26 · 2 pts — model-based vs memory-based

Q. Discuss the main differences between model-based and memory-based algorithms; give an example of each and explain why.

Model answer. Memory-based methods keep the raw URM and compute recommendations directly at query time from similarity heuristics — no learned parameters. Example — user/item-based KNN CF. Model-based methods learn a compact parametric model offline by minimising a loss; predictions come from the fitted parameters. Example — Matrix Factorization (or SLIM). Trade-off: memory-based is lazy, interpretable, costly at query time and degrades under sparsity; model-based trains offline, generalises, and is compact and fast at inference.

Past paper Practice Exam · popularity bias, diversity, novelty, serendipity

Q. Describe popularity bias and its effect, and discuss the importance of diversity, serendipity and novelty.

Model answer. Popularity bias is the tendency to over-recommend already-popular items because they carry the most interactions — a rich-get-richer feedback loop that starves the long tail and drops coverage and novelty. Diversity = how dissimilar items within a list are (avoids redundancy). Novelty = how unknown / non-obvious an item is to the user. Serendipity = relevant and surprising. They matter because accuracy alone yields obvious, repetitive lists; these qualities drive discovery, long-term satisfaction and catalog coverage.

Why recommend at all?

A taxonomy of recommenders

The User Rating Matrix (URM)

URM / ICM explorer · the toy catalog

The Item Content Matrix (ICM)

Explicit vs. implicit feedback

Feedback lens · explicit vs implicit

Sparsity & the long tail

Sparsity & the long tail

Three questions before you move on

One-screen summary

Chapter 01 — load-bearing ideas

Past-paper questions