Collaborative Filtering

Every time a streaming service suggests a film you hadn't heard of, or a bookstore places a title in your path just before you would have searched for it, something quietly uncanny has happened: an algorithm inferred your taste without ever analyzing what you actually like.

This is collaborative filtering. It does not read the plot of a film or listen to a song. Instead it watches a giant table of ratings — millions of users, millions of items, mostly blank — and asks: which users rated things similarly to me? What did they rate highly that I haven't seen yet?

The key insight, established as a practical framework by Goldberg, Nichols, Oki and Terry in their 1992 Tapestry email system, is that you don't need to understand the content. Taste is structure hidden in a sparse matrix of numbers, and that structure can be recovered by linear algebra alone.

Modern systems go further. Rather than just finding similar users, they factor the ratings matrix into low-rank products — essentially inventing a small set of hidden "taste dimensions" that explain most of what everyone rated. This matrix-factorization approach, popularized by the $1 million Netflix Prize (2006–2009), sits at the heart of nearly every recommendation engine running today.

Five users have already rated some films. You are User 6. Click the stars to rate the films you know — then press Predict to see the algorithm fill in what it thinks you'd give the ones you haven't rated yet.

<p class="hint">{{hint}}</p>
<div id="app">
  <div id="table-wrap"></div>
  <div class="status" id="status">{{status_initial}}</div>
  <div class="btns">
    <button id="btn-predict" type="button">{{btn_predict}}</button>
    <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  </div>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
#table-wrap { overflow-x: auto; }
table { border-collapse: collapse; width: 100%; min-width: 460px; }
th, td { padding: 5px 7px; text-align: center; border: 1px solid #dde3ea; }
th { background: #e8eef3; color: #1d3557; font-weight: 700; font-size: .82rem; }
td.user-label { text-align: left; font-weight: 600; color: #1d3557; white-space: nowrap; }
td.you { background: #f0f7ff; }
td.you.predicted { background: #e0f0e8; }
.stars { display: inline-flex; gap: 1px; cursor: pointer; }
.star { font-size: 17px; color: #ccc; line-height: 1; transition: color .1s; }
.star.on { color: #f4a100; }
.star.predicted { color: #3bb065; cursor: default; font-size: 15px; }
.empty { color: #bbb; font-size: .8rem; }
.status { font-size: .95rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

The algorithm factors the ratings matrix into two smaller matrices — one capturing each user's hidden "taste profile", one capturing each film's hidden "genre fingerprint". Their dot product reconstructs missing entries. Notice that films you haven't rated appear with a predicted score: the model infers your taste from users who rated things similarly to you.

Collaborative filtering sits in an interesting place on the complexity map.

• Status: solved in practice, NP-hard in the worst case. The exact problem — find the rank-k factorization of a partial matrix that minimizes squared error — is NP-hard without assumptions (Gillis & Glineur, 2011). Yet practical systems work extremely well.
• The trick: relaxation. Instead of demanding an exact low-rank factorization, systems minimize a regularized loss with stochastic gradient descent (SGD) or alternating least squares (ALS), both of which converge to good local minima in polynomial time.
• Checking is easy; finding the global optimum is hard. Given a complete factorization, verifying its quality is a simple sum of squared errors. Finding the globally optimal factorization over all possible rank-k matrices is not. This mirrors the gap between P and NP that appears throughout P vs NP.
• Scale is the real enemy. Netflix has hundreds of millions of users and tens of thousands of items. Even with polynomial-time algorithms, a naive SVD on the full dense matrix would take $O(n^{3})$ time. Practical systems exploit sparsity — only observed ratings appear in the loss — and achieve near-linear scaling.
• Cold start remains hard. A new user or item with no ratings offers the algorithm nothing to factor in. This is not a complexity limitation but a fundamental information-theoretic one: you cannot predict preferences from an empty row.

The gap between theoretical worst-case hardness and practical polynomial-time performance is what makes collaborative filtering a triumph of applied machine learning.

The ability to fill in a sparse matrix of interactions — without understanding what the items actually are — is one of the most broadly useful ideas in data science:

• Streaming and e-commerce: Netflix, Spotify, Amazon, YouTube, and TikTok all use variants of collaborative filtering at their core. The Netflix Prize accelerated the entire field and produced techniques still in production today.
• Social feed ranking: "posts you might like" on every major platform is powered by a collaborative signal — what users with overlapping engagement histories interacted with.
• Drug–target interaction prediction: the same matrix factorization applied to a user–item matrix of drug-protein binding experiments predicts which untested pairs are likely to interact — dramatically narrowing experimental search spaces.
• Knowledge base completion: in knowledge graphs, predicting missing (subject, relation, object) triples is formally identical to collaborative filtering on a three-dimensional rating tensor.
• Ad click-through rate: predicting whether user u will click ad a given their browsing history is a low-rank matrix completion problem at internet scale.

Understand matrix factorization and you understand the computational core of dimensionality reduction, latent semantic analysis, and topic modelling — the same structure appears wherever meaning hides in sparse co-occurrence data.

Collaborative filtering is a small philosophical provocation dressed as engineering: you can predict what someone wants without knowing anything about what they're being offered. Taste, it turns out, lives in the patterns of agreement and disagreement among people — not in the items themselves.

The mathematics is elegant: a sparse matrix of ratings, factored into two thin matrices of latent dimensions, reconstructs the missing entries with remarkable accuracy. The exact problem is NP-hard, but the practical relaxations converge well enough to power the most-visited services on the internet.

So the next time an algorithm surfaces exactly the book you needed before you knew you needed it, remember: somewhere, a matrix was factored, a latent taste dimension aligned, and the dot product came out in your favor.