Introduction

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.

Rate Items and See Predictions

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">Five users have rated some films (★ = 1–5). <b>You are User 6.</b>
    Click the stars on the bottom row to rate films you know, then press <b>Predict</b>
    to fill in what the algorithm thinks you'd give the rest.</p>
<div id="app">
  <div id="table-wrap"></div>
  <div class="status" id="status">Rate at least one film, then click Predict.</div>
  <div class="btns">
    <button id="btn-predict" type="button">Predict</button>
    <button id="btn-reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Collaborative Filtering via Alternating Least Squares (ALS) matrix factorization.
// R[u][i] = known rating (1-5) or 0 (unknown). We factor R ≈ U * V^T where
//   U is (nUsers x K) user-factor matrix,  V is (nItems x K) item-factor matrix.
// ALS alternates fixing V to solve for U (closed-form least squares) and vice-versa.
// Predictions for unknown entries = row of U dotted with column of V.

const FILMS = ['Inception','The Matrix','Interstellar','Parasite','Spirited Away','Dune'];
const USER_LABELS = ['Alice','Bob','Carol','Dan','Eve','You'];
const K = 2; // latent dimensions
const LAMBDA = 0.1; // regularisation
const ITERS = 40;

// Known ratings (users 0-4, films 0-5); 0 = unrated.
const KNOWN = [
  [5, 4, 5, 0, 0, 4],
  [4, 5, 4, 0, 0, 5],
  [0, 0, 0, 5, 4, 0],
  [0, 0, 0, 4, 5, 0],
  [5, 0, 4, 3, 0, 3],
];

const nUsers = USER_LABELS.length;
const nItems = FILMS.length;

// You = row 5 (index 5), initially all 0.
let R = KNOWN.map(r => [...r]);
R.push(new Array(nItems).fill(0));

let userRatings = new Array(nItems).fill(0); // your ratings

function rand() { return (Math.random() - 0.5) * 0.5; }

function matMul(A, B) {
  // A: m x p, B: p x n -> m x n
  const m = A.length, p = B.length, n = B[0].length;
  const C = Array.from({length: m}, () => new Array(n).fill(0));
  for (let i = 0; i < m; i++)
    for (let k = 0; k < p; k++)
      for (let j = 0; j < n; j++)
        C[i][j] += A[i][k] * B[k][j];
  return C;
}

function dot(a, b) { return a.reduce((s, v, i) => s + v * b[i], 0); }

// Solve (V^T * V + lambda*I) * u = V^T * r_known  for user u's factor vector.
function solveUser(V, ratings) {
  const observed = ratings.map((r, i) => r > 0 ? i : -1).filter(i => i >= 0);
  if (observed.length === 0) return new Array(K).fill(0);
  // Build V_obs (observed x K) and r_obs vector.
  const Vo = observed.map(i => V[i]);
  const ro = observed.map(i => ratings[i]);
  // A = Vo^T * Vo + lambda * I
  const A = Array.from({length: K}, (_, a) =>
    Array.from({length: K}, (_, b) =>
      Vo.reduce((s, row) => s + row[a] * row[b], 0) + (a === b ? LAMBDA : 0)
    )
  );
  // b = Vo^T * ro
  const bv = Array.from({length: K}, (_, a) =>
    Vo.reduce((s, row, j) => s + row[a] * ro[j], 0)
  );
  // Solve 2x2 system A*x = b exactly.
  if (K === 2) {
    const det = A[0][0]*A[1][1] - A[0][1]*A[1][0];
    if (Math.abs(det) < 1e-9) return new Array(K).fill(0);
    return [
      (A[1][1]*bv[0] - A[0][1]*bv[1]) / det,
      (A[0][0]*bv[1] - A[1][0]*bv[0]) / det
    ];
  }
  return bv; // fallback K=1
}

function solveItem(U, ratings) {
  // ratings[u] = rating by user u for this item (0 = unrated).
  return solveUser(U, ratings); // symmetric role
}

function runALS(R_full) {
  // Initialise U, V randomly.
  let U = Array.from({length: nUsers}, () => Array.from({length: K}, rand));
  let V = Array.from({length: nItems}, () => Array.from({length: K}, rand));

  for (let iter = 0; iter < ITERS; iter++) {
    // Fix V, solve for each user row.
    for (let u = 0; u < nUsers; u++)
      U[u] = solveUser(V, R_full[u]);
    // Fix U, solve for each item row.
    for (let i = 0; i < nItems; i++) {
      const col = R_full.map(row => row[i]);
      V[i] = solveItem(U, col);
    }
  }
  return { U, V };
}

function predict(U, V, u, i) {
  return Math.min(5, Math.max(1, dot(U[u], V[i])));
}

// ── DOM ──────────────────────────────────────────────────────────────────────
let predictions = null;

function starHtml(rating, userId, filmIdx, interactive) {
  if (!interactive) {
    // Static display for known users.
    if (rating === 0) return '<span class="empty">·</span>';
    return '<span class="stars">' +
      [1,2,3,4,5].map(s =>
        `<span class="star ${s <= rating ? 'on' : ''}">★</span>`
      ).join('') + '</span>';
  }
  // Interactive stars for "you" row.
  const isPredicted = (rating === 0 && predictions !== null && predictions[filmIdx] > 0);
  const displayRating = isPredicted
    ? Math.round(predictions[filmIdx])
    : rating;
  const starClass = isPredicted ? 'predicted' : (rating > 0 ? 'on' : '');
  return '<span class="stars" data-film="' + filmIdx + '">' +
    [1,2,3,4,5].map(s =>
      `<span class="star ${s <= displayRating ? starClass : ''}">★</span>`
    ).join('') + '</span>';
}

function render() {
  const wrap = document.getElementById('table-wrap');
  let html = '<table><thead><tr><th>User</th>';
  FILMS.forEach(f => { html += '<th>' + f + '</th>'; });
  html += '</tr></thead><tbody>';

  USER_LABELS.forEach((label, u) => {
    const isYou = (u === nUsers - 1);
    html += '<tr>';
    html += '<td class="user-label' + (isYou ? ' you' : '') + '">' + label + '</td>';
    FILMS.forEach((_, i) => {
      const rating = isYou ? userRatings[i] : KNOWN[u][i];
      const isPred = isYou && userRatings[i] === 0 && predictions !== null;
      html += '<td class="' + (isYou ? 'you' : '') + (isPred ? ' predicted' : '') + '">';
      html += starHtml(rating, u, i, isYou);
      html += '</td>';
    });
    html += '</tr>';
  });
  html += '</tbody></table>';
  wrap.innerHTML = html;

  // Attach click listeners to your star rows.
  wrap.querySelectorAll('.stars[data-film]').forEach(starsEl => {
    const filmIdx = parseInt(starsEl.getAttribute('data-film'));
    starsEl.querySelectorAll('.star').forEach((star, s) => {
      star.addEventListener('click', () => {
        const newRating = (userRatings[filmIdx] === s + 1) ? 0 : s + 1;
        userRatings[filmIdx] = newRating;
        predictions = null; // clear predictions when user changes ratings
        setStatus('Rate at least one film, then click Predict.', '');
        render();
      });
    });
  });
}

function setStatus(t, cls) {
  const s = document.getElementById('status');
  s.textContent = t;
  s.className = 'status ' + cls;
}

document.getElementById('btn-predict').addEventListener('click', () => {
  const rated = userRatings.filter(r => r > 0).length;
  if (rated === 0) {
    setStatus('Please rate at least one film first.', 'bad');
    return;
  }
  // Build full matrix with your ratings in row nUsers-1.
  R[nUsers - 1] = [...userRatings];
  const { U, V } = runALS(R);
  predictions = FILMS.map((_, i) => userRatings[i] > 0 ? 0 : predict(U, V, nUsers - 1, i));

  const numPred = predictions.filter(p => p > 0).length;
  if (numPred === 0) {
    setStatus('You rated all films — nothing left to predict!', 'ok');
  } else {
    setStatus(
      fmt('Predicted %numPred% %v% (green stars) from %rated% %v2% you gave.', { numPred: numPred, v: numPred > 1 ? 'films' : 'film', rated: rated, v2: rated > 1 ? 'ratings' : 'rating' }),
      'ok'
    );
    console.log('ALS predictions for you:', FILMS.map((f, i) => f + ':' + (userRatings[i] > 0 ? fmt('%v%(known)', { v: userRatings[i] }) : predictions[i].toFixed(2))).join(', '));
  }
  render();
});

document.getElementById('btn-reset').addEventListener('click', () => {
  userRatings = new Array(nItems).fill(0);
  predictions = null;
  R[nUsers - 1] = new Array(nItems).fill(0);
  setStatus('Rate at least one film, then click Predict.', '');
  render();
});

render();
Result
Console

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.

The Real Complexity

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(n3)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.

Where It Matters

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.

Conclusion

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.

Share this article

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

Comments

Loading comments...

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