Recommendation

Open almost any app and a machine is quietly guessing your taste. Because you watched this… because you bought that… people like you also liked… Behind each of those rows sits one huge table: users down the side, items across the top, ratings in the cells — and almost every cell is empty, because nobody watches everything.

A recommender system is, at heart, a machine that fills in those empty cells. If it can guess that you'd give a film you've never seen a 4.7 out of 5, it puts that film at the top of your screen.

The trick that powers most of these systems is collaborative filtering: you don't need to understand the movies at all. You only need the pattern of who-liked-what. If your ratings line up with mine on twenty films, my opinion on the twenty-first is a surprisingly good guess for yours.

Here is a tiny ratings table: five users, five movies, scores from 1 to 5. One cell is missing — how would you rate it? Type your guess, then let two classic methods take a turn.

<p class="hint">{{hint}}</p>
<div id="table" class="table"></div>
<div class="guess">
  <label>{{guess_label}}: <input id="guess" type="number" min="1" max="5" step="0.1" value="3"></label>
</div>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="knn" type="button">{{btn_knn}}</button>
  <button id="mf" type="button">{{btn_mf}}</button>
  <button id="reveal" type="button" class="ghost">{{btn_reveal}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.table { display: grid; grid-template-columns: repeat(6, 1fr); gap: 4px; max-width: 420px; margin: .4rem 0; }
.c { padding: .45rem 0; text-align: center; border-radius: 7px; font: 600 14px system-ui, sans-serif; }
.head { background: #1d3557; color: #fff; font-size: 12.5px; }
.rowh { background: #e8eef3; color: #1d3557; font-size: 12.5px; }
.val { background: #f3f5f8; color: #1d3557; }
.hole { background: #ffe8b3; color: #b06a00; font-weight: 800; }
.hole.filled { background: #c8edd2; color: #0a7d33; }
.status { font-size: .98rem; font-weight: 600; margin: .55rem 0; min-height: 1.4em; line-height: 1.4; }
.status.ok { color: #0a7d33; } .status.bad { color: #c92f3c; }
.guess { font-size: .92rem; margin: .4rem 0; }
.guess input { width: 64px; font: 600 14px system-ui; padding: .25rem .4rem; border: 1px solid #adb1b8; border-radius: 6px; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice the asymmetry. Checking a single prediction is trivial: once a user actually rates the movie, you just compare. The hard part is choosing the model that fills every hole well at once. Nearest neighbors finds the users most similar to the target and borrows their opinion. Matrix factorization invents a few hidden "taste dimensions" (latent factors) and reconstructs the whole table from them — and finding the factors that fit best is where the difficulty hides.

How hard is recommendation, really? Not serving the result — fitting the model.

• Checking a prediction is trivial: when the true rating arrives, the error is one subtraction.
• Nearest neighbors is cheap to describe but doesn't scale: comparing every pair of users is roughly quadratic, painful when there are hundreds of millions of them.
• Matrix factorization is the heart of the matter. You assume the giant ratings table is approximately low rank — every user and every item is a short vector of latent factors, and a rating is just their dot product. Reconstruct those vectors and you've filled the whole table.
• It's NP-hard. Finding the best low-rank factorization that matches the observed entries is NP-hard in general — proven for matrix completion and weighted/low-rank approximation (for example Gillis & Glineur, 2011). The famous Netflix Prize (2006–2009, one million dollars for a 10% improvement) was won not by solving it exactly but by approximately optimizing factor models with gradient descent and blending hundreds of them.

That is the punchline: we don't compute the perfect recommender. We start from random factors and nudge them downhill, accepting a good-enough fit because the exact best one belongs to the same intractable family behind P vs NP.

"Fill in the missing values of a giant, mostly-empty table" turns out to be one of the most valuable shapes a problem can take:

• Streaming and video: Netflix and YouTube rank what to show next from your implicit and explicit ratings.
• Shopping and music: "customers who bought this" and Spotify's weekly mixes are the same factorization, different items.
• Advertising: predicting click-through is matrix completion over users and ads.
• Beyond media: the identical low-rank idea repairs gaps in images (inpainting), predicts drug–target interactions, and fills sensor readings.

Recommendation is one face of a broader optimization story — the same "minimize the error of a model with many knobs" engine drives neural-network training and countless non-convex optimization problems.

A recommender system hides a beautiful tension. Checking whether a prediction was right is a single subtraction once you know the truth. Finding the model that predicts every missing rating as well as possible — the best low-rank set of latent factors — is NP-hard, the very reason the Netflix Prize was won with clever approximations rather than an exact answer.

So the next time a feed seems to read your mind, remember what's underneath: a vast table of holes, a handful of invented taste dimensions, and an algorithm that gave up on perfection long ago and simply rolled downhill toward good enough — because perfect is hiding behind P vs NP.