Introduction

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.

Predict the Missing Rating

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">A ratings table: 5 users rate 5 movies from 1 to 5. One cell is missing (<b>?</b>) — it's how <b>You</b> would rate <b>Nebula</b>. Type your guess, then let the algorithms fill the hole. Checking a guess is one subtraction; finding the model that fits the <i>whole</i> table is the hard part.</p>
<div id="table" class="table"></div>
<div class="guess">
  <label>Your guess for the <b>?</b>: <input id="guess" type="number" min="1" max="5" step="0.1" value="3"></label>
</div>
<div class="status" id="status">Make a guess, then try a method.</div>
<div class="btns">
  <button id="knn" type="button">Nearest neighbors</button>
  <button id="mf" type="button">Matrix factorization</button>
  <button id="reveal" type="button" class="ghost">Reveal truth</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// A 5x5 ratings table. R[u][i] = rating, or null for the missing cell.
// Target hole = user 4 (You), movie 4 (Nebula). True rating = 5 (You love sci-fi).
const USERS = ['Ana','Beto','Cleo','Deri','You'];
const MOVIES = ['Comedy','Drama','Action','Romance','Nebula'];
const TRUTH = 5;
const R = [
  [5,1,5,1,5],   // Ana  - sci-fi/action fan
  [1,5,1,5,1],   // Beto - drama/romance fan
  [4,2,5,1,4],   // Cleo - action-leaning
  [2,5,1,4,2],   // Deri - drama/romance-leaning
  [5,1,4,1,null] // You  - looks like Ana/Cleo; Nebula unknown
];
const HU = 4, HI = 4; // hole coordinates

function render(filled){
  const t = document.getElementById('table'); t.innerHTML='';
  const add=(txt,cls)=>{ const d=document.createElement('div'); d.className='c '+cls; d.textContent=txt; t.appendChild(d); };
  add('','head');
  MOVIES.forEach(m=>add(m,'head'));
  for(let u=0;u<5;u++){
    add(USERS[u],'rowh');
    for(let i=0;i<5;i++){
      if(u===HU&&i===HI){
        if(filled==null) add('?','hole');
        else { const d=document.createElement('div'); d.className='c hole filled'; d.textContent=filled.toFixed(1); t.appendChild(d); }
      } else add(R[u][i],'val');
    }
  }
}
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }

// ---- Nearest neighbors: cosine similarity on shared (non-hole) movies ----
function knnPredict(){
  const target = R[HU];
  const idx = [0,1,2,3]; // movies we both rated (exclude the hole at 4)
  let best=[]; // {u, sim}
  for(let u=0;u<4;u++){
    let dot=0,a=0,b=0;
    idx.forEach(i=>{ dot+=target[i]*R[u][i]; a+=target[i]*target[i]; b+=R[u][i]*R[u][i]; });
    best.push({u, sim: dot/(Math.sqrt(a)*Math.sqrt(b))});
  }
  best.sort((x,y)=>y.sim-x.sim);
  const top = best.slice(0,2); // 2 nearest neighbors
  let num=0,den=0; top.forEach(n=>{ num+=n.sim*R[n.u][HI]; den+=n.sim; });
  return { pred: num/den, who: top.map(n=>USERS[n.u]) };
}

// ---- Matrix factorization: R ~ P (5xK) . Q (5xK), learned by gradient descent ----
function mfPredict(){
  const K=2, lr=0.02, reg=0.02, EPOCHS=4000;
  let seed=42; const rnd=()=>{ seed=(seed*1103515245+12345)&0x7fffffff; return (seed/0x7fffffff-0.5)*0.4; };
  const P=Array.from({length:5},()=>Array.from({length:K},rnd));
  const Q=Array.from({length:5},()=>Array.from({length:K},rnd));
  const obs=[]; for(let u=0;u<5;u++)for(let i=0;i<5;i++) if(!(u===HU&&i===HI)) obs.push([u,i,R[u][i]]);
  const dot=(u,i)=>{ let s=0; for(let k=0;k<K;k++) s+=P[u][k]*Q[i][k]; return s; };
  for(let e=0;e<EPOCHS;e++) for(const [u,i,r] of obs){
    const err=r-dot(u,i);
    for(let k=0;k<K;k++){ const pu=P[u][k], qi=Q[i][k];
      P[u][k]+=lr*(err*qi-reg*pu); Q[i][k]+=lr*(err*pu-reg*qi); }
  }
  return Math.max(1,Math.min(5,dot(HU,HI)));
}

document.getElementById('knn').addEventListener('click',()=>{
  const {pred,who}=knnPredict(); render(pred);
  setStatus(fmt('Nearest neighbors borrows from %who% (most similar to You) → %pred%. Checking it needs the real rating.', { who: who.join(' & '), pred: pred.toFixed(1) }),'ok');
});
document.getElementById('mf').addEventListener('click',()=>{
  const p=mfPredict(); render(p);
  setStatus(fmt('Matrix factorization learned 2 latent factors from the other 24 cells → %p%. Fitting those factors optimally is NP-hard.', { p: p.toFixed(1) }),'ok');
});
document.getElementById('reveal').addEventListener('click',()=>{
  render(TRUTH);
  const g=parseFloat(document.getElementById('guess').value);
  const err=Math.abs(g-TRUTH);
  setStatus(fmt('Truth = %TRUTH%. Your guess was off by %err%. See? Checking one prediction is a single subtraction.', { TRUTH: TRUTH, err: err.toFixed(1) }), err<=1?'ok':'bad');
});
render(null);
Result
Console

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.

The Real Complexity

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.

Where It Matters

"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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/recommendation/Content licensed under CC BY-NC 4.0.