Collaborative Filtering

📝 Before You Continue: Please read first the discussion of "retrieval as the starting point of the three-stage funnel" in Part 1, Section 1.1, and the "retrieval: from billions to thousands" thread in 1.2. This chapter covers the most classic family of methods in the retrieval layer.

When you open a shopping app, how does the system decide "what else you might like"? The most naive yet most powerful intuition comes from Collaborative Filtering (CF): inferring individual preferences from the collective behavior of "people" and "items" — people who like the same things tend to have similar tastes; items liked by the same group of people tend to be similar in nature.

The idea of collaborative filtering is nearly as old as recommender systems themselves, but it goes far beyond "finding similar things". From neighborhood-based ItemCF / UserCF, to Swing built for industrial robustness, to matrix factorization mapping users and items into latent vectors, this chapter walks you through the evolution from statistical co-occurrence to vector representation.

After reading this chapter, you will be able to:

• Compute item and user similarity with cosine similarity / Pearson correlation, and articulate the difference between the two
• Explain how Swing filters random noise through bipartite-graph substructures, and how Surprise mines complementary items
• Describe the trade-offs between UserCF and ItemCF regarding user cold start and explainability
• Describe how matrix factorization (FunkSVD / BiasSVD) alleviates data sparsity with low-rank latent vectors
• Complete 5 graded practice problems, consolidating the full path from co-occurrence to vectorization

2.1.0 Two Perspectives on Collaborative Filtering

Collaborative filtering can be split along two directions: item-based (ItemCF) asks "what else is similar to the items you liked"; user-based (UserCF) asks "what else do people similar to you like". The former fits industrial scenarios better (item sets are stable and can be precomputed offline), while the latter feels more natural in scenarios with strong social flavor.

Whichever perspective you take, the core revolves around one concept — co-occurrence: two items interacted with by the same set of users, or two users interacting with the same set of items. The more frequent the co-occurrence, the higher the similarity. As we will see in the next three sections, all CF methods are just different answers to "how to define and exploit co-occurrence".

2.1.1 ItemCF: Item-Similarity-Based Collaborative Filtering

The core idea of ItemCF is that user interests are coherent: people who like an item tend to be interested in similar items. When recommending to a user, the system first identifies the items the user interacted with recently (seed items), then finds the most similar candidates for each seed, and finally aggregates the scores.

Computing Item Similarity

Most real-world scenarios have only implicit feedback (clicks, purchases), no ratings. ItemCF quantifies item similarity with cosine similarity:

$$w_{ij}=\frac{\mathbf{C}[i][j]}{\sqrt{|\mathcal{N}(i)|\cdot |\mathcal{N}(j)|}}$$

where $|\mathcal{N}(i)|$ is the total number of users who interacted with item $i$, and $\mathbf{C}[i][j]$ is the co-occurrence count of the two items (the number of users who interacted with both). The denominator normalizes the co-occurrence count, preventing popular items from dominating by sheer interaction volume — exactly the biggest trap of naive co-occurrence.

Recommending Candidate Items

Given the similarity matrix, the online flow has three steps: ① take a few hundred items the user recently interacted with as seeds; ② find the Top-10 similar items for each seed, quickly generating a large pool of candidates; ③ compute the user's interest score for candidate item $i$:

$$p(u,i)=\sum _{j\in \mathcal{N}(u)}{w}_{ij}\cdot r_{uj}$$

$\mathcal{N}(u)$ is the set of items the user interacted with, and $r_{uj}$ is the user's interest strength on item $j$ (set to 1, or weighted by interaction time/type). Finally, rank all candidates by score and take the Top-N.

🧠 Mental Model: A Borrower's Reading List

Think of items as "books" and users as "borrowers". ItemCF's logic: if Alice borrowed The Three-Body Problem and Ball Lightning, and Bob also borrowed The Three-Body Problem, then the system guesses Bob will probably like Ball Lightning too — because these two books are always borrowed by the same crowd. The point is not the content of the books, but "who reads them".

Computational Efficiency Optimizations

Brute-force computation of all item-pair similarities is $O(|\mathcal{I}{|}^2\cdot |\mathcal{U}|)$, but the vast majority of item pairs share no common users, so their similarity is necessarily 0. A user–item inverted index speeds this up dramatically: maintain an interaction list per user, and when traversing, pair up items within each list, accumulate the co-occurrence matrix $\mathbf{C}[i][j]$, then divide by the normalization terms. The optimized complexity is roughly $O(R\cdot \bar{m})$ ($R$ is the total number of interactions, $\bar{m}$ the average number of items per user), far below brute force in sparse settings.

Similarity for Rating Data (Pearson Correlation)

When the system has explicit ratings (e.g., 5 stars), the Pearson correlation coefficient is more robust than cosine, because centering removes differences in rating distributions across items:

$$w_{ij}=\frac{{\sum }_{u\in {\mathcal{U}}_{ij}}(r_{ui}-{\bar{r}}_i)(r_{uj}-{\bar{r}}_j)}{\sqrt{{\sum }_{u\in {\mathcal{U}}_{ij}}(r_{ui}-{\bar{r}}_i{)}^2}\sqrt{{\sum }_{u\in {\mathcal{U}}_{ij}}(r_{uj}-{\bar{r}}_j{)}^2}}$$

Based on this, one can predict a user's rating for an unseen item:

$${\hat{r}}_{u,j}={\bar{r}}_j+\frac{{\sum }_{k\in {\mathcal{S}}_j}{w}_{jk}\left(r_{u,k}-{\bar{r}}_k\right)}{{\sum }_{k\in {\mathcal{S}}_j}{w}_{jk}}$$

In large-scale systems, for computational and sparsity reasons, most still use cosine similarity supplemented with weighted normalization.

Analysis: ItemCF can precompute the full item similarity matrix offline; online it only needs to fetch the Top-N similar items of the seed items, with very low latency and strong explainability. But it is powerless against item cold start (new items have no co-occurrence), and its similarity is fixed, hard to fuse with contextual features. It suits scenarios with stable item sets and dense interactions.

2.1.2 Swing: Similarity Optimization for Industrial Scenarios

ItemCF is naive and effective, but industrial deployment exposes clear problems: popular items dominate results due to high co-occurrence; noise such as random misclicks is treated equally. Swing offers an elegant answer — analyze substructures of the user–item bipartite graph to filter noise.

Its core insight: if multiple users bought the same pair of items despite sharing few other co-purchases, then the association between that pair is more trustworthy. In other words, the more "specific" the co-purchase behavior, the greater its contribution to similarity.

Computing Item Similarity

Let $U_i$ and $U_j$ be the sets of users who interacted with items $i$ and $j$. For each pair of common users $(u,v)$, if they share few other co-purchases (smaller $|I_u\cap I_v|$), then their joint choice of this item pair is more specific and should contribute a higher score:

$$s(i,j)=\sum _{u\in U_i\cap U_j}\sum _{v\in U_i\cap U_j}\frac{1}{\alpha +|I_u\cap I_v|}$$

$\alpha$ is a smoothing coefficient preventing tiny denominators from causing numerical instability. To reduce the excessive influence of active users, a user weight $w_u=1/\sqrt{|I_u|}$ is introduced:

$$s(i,j)=\sum _{u\in U_i\cap U_j}\sum _{v\in U_i\cap U_j}{w}_u\cdot w_v\cdot \frac{1}{\alpha +|I_u\cap I_v|}$$

As shown, users A and B have 4 swing subgraphs $[A,h,B]$, $[A,t,B]$, $[A,r,B]$, $[A,p,B]$. If $\alpha =1$ and A and B have 4 other shared behaviors, the user pair $[A,B]$ contributes $1/5$; h and p additionally share t and r, contributing two extra $1/3$ terms, so finally $s(h,p)=13/15$, higher than $s(h,t)=1/5$. Combinations with few but "exclusive" co-occurrences score higher — this is exactly how Swing filters popular-item noise.

Surprise: Complementary Item Recommendation

Swing scores already capture associations, but handling complementary items (buying a phone case after a phone) remains hard — complementary relations are directional and time-ordered. The Surprise algorithm measures complementary relevance at three levels: category, item, and cluster:

• Category level: compute conditional probabilities between categories with a user-category matrix, ${\theta }_{i,j}=N(c_{i,j})/N(c_j)$, and adaptively truncate the long tail using the maximum relative drop.
• Item level: consider purchase order and time interval — the closer in time, the stronger the complementarity:

$$s_1(i,j)=\frac{{\sum }_{u\in U_i\cap U_j}\frac{1}{1+|t_{ui}-t_{uj}|}}{\Vert U_i\Vert \times \Vert U_j\Vert }$$

• Cluster level: run label propagation on a graph of billions of items (edge weights are Swing scores) to cluster and alleviate sparsity, then combine linearly:

$$s(i,j)=\omega \cdot s_1(i,j)+(1-\omega )\cdot s_2(i,j)$$

Analysis: Swing significantly improves robustness while preserving ItemCF's efficiency, making it an evergreen of industrial I2I retrieval; the cost is building and traversing the bipartite graph, with higher computation than naive ItemCF. Surprise goes further for complementary scenarios, but introduces multi-level hyperparameters and clustering steps, raising engineering complexity.

2.1.3 UserCF: User-Similarity-Based Collaborative Filtering

Mirror to ItemCF, UserCF assumes: users with similar historical behavior will have similar future preferences. It first finds the "neighbors" most similar to the target user, then predicts the target user's interests from the neighbors' behavior.

Computing User Similarity

Given users $u$ and $v$ with item sets $N(u)$ and $N(v)$, three common measures:

• Jaccard coefficient (implicit feedback only):

$$w_{uv}=\frac{|N(u)\cap N(v)|}{|N(u)\cup N(v)|}$$

• Cosine similarity (accounting for activity differences):

$$w_{uv}=\frac{|N(u)\cap N(v)|}{\sqrt{|N(u)|\cdot |N(v)|}}$$

• Pearson correlation (with ratings; centering removes rating-habit differences):

$$w_{uv}=\frac{{\sum }_{i\in I}(r_{ui}-{\bar{r}}_u)(r_{vi}-{\bar{r}}_v)}{\sqrt{{\sum }_{i\in I}(r_{ui}-{\bar{r}}_u{)}^2}\sqrt{{\sum }_{i\in I}(r_{vi}-{\bar{r}}_v{)}^2}}$$

Recommending Candidate Items

Select the $K$ users with the highest similarity as the neighbor set ${\mathcal{S}}_u$. A simple weighted average predicts ratings:

$${\hat{r}}_{u,p}=\frac{{\sum }_{v\in S_u}{w}_{uv}{r}_{v,p}}{{\sum }_{v\in S_u}{w}_{uv}}$$

The bias-aware version further removes personal habits:

$${\hat{r}}_{u,p}={\bar{r}}_u+\frac{{\sum }_{v\in S_u}{w}_{uv}(r_{v,p}-{\bar{r}}_v)}{{\sum }_{v\in S_u}{w}_{uv}}$$

At serving time, find the $K$ most similar users for the target user, collect their interacted items as candidates, compute interest scores $p(u,i)={\sum }_{v\in S_u\cap N(i)}{w}_{uv}\cdot r_{vi}$, rank, and take the Top-N. The optimized complexity is roughly $O(R\cdot \bar{n})$, far below $O(|U{|}^2)$.

Analysis: UserCF excels in scenarios where user interests converge, such as "trending news" or "breaking events", and naturally supports social recommendation through "discovering similar people". But when users vastly outnumber items, computation and storage costs are high, and user cold start is hard (new users have no behavior). In industry, ItemCF is more common, because its item set is stable and can be fully precomputed offline.

2.1.4 Matrix Factorization: From Similarity to Vector Representation

Both UserCF and ItemCF face a fundamental challenge: data sparsity. Real interaction matrices are extremely sparse, leaving too few common ratings to compute reliable similarities. Matrix factorization takes a different route — instead of explicitly computing similarities, it learns latent vector representations for users and items, letting distances in the vector space naturally reflect preferences. This marks CF's shift from statistical methods to machine learning methods.

The Dawn of the Latent Vector Era

Matrix factorization rests on two assumptions: the low-rank assumption — the seemingly complex rating matrix is actually governed by a few latent factors (such as "male-oriented vs. female-oriented", "serious vs. light"); and the latent vector assumption — every user/item can be represented by a vector encoding these factors.

FunkSVD: The Basic Model

FunkSVD factorizes the rating matrix into a user feature matrix and an item feature matrix. User $u$ is represented by a $K$-dimensional vector $p_u$, item $i$ by $q_i$, and the predicted rating is their inner product:

$${\hat{r}}_{ui}=p_u^T{q}_i=\sum _{k=1}^K{p}_{u,k}\cdot q_{i,k}$$

The optimization objective makes predictions approximate true ratings (over known ratings only):

$$\underset{P,Q}{\min }\frac{1}{2}\sum _{(u,i)\in \mathcal{K}}{\left(r_{ui}-p_u^T{q}_i\right)}^2$$

Update with gradient descent, where the error is $e_{ui}=r_{ui}-p_u^T{q}_i$:

$$p_{u,k}\leftarrow p_{u,k}+\eta \cdot e_{ui}\cdot q_{i,k},q_{i,k}\leftarrow q_{i,k}+\eta \cdot e_{ui}\cdot p_{u,k}$$

In practice, add L2 regularization against overfitting: $\min \frac{1}{2}\sum (\dots {)}^2+\lambda (\Vert p_u{\Vert }^2+\Vert q_i{\Vert }^2)$.

🧠 Mental Model: Taste Axes

Plot every user and every movie on a 2D chart: the horizontal axis is "male-oriented ↔ female-oriented", the vertical axis "serious ↔ light". Users who like The Princess Diaries and the movie itself both land in the "female-oriented, light" corner, so the inner product is naturally large. Even if two users have never watched the same movie, as long as they are close on the latent factors, they can recommend for each other — this is the key to how vector representation overcomes sparsity.

BiasSVD: The Improved Model

The basic model ignores a fact: some people are naturally generous raters ("pushovers"), others strict; some movies universally rate high due to star casts. BiasSVD introduces bias terms:

$${\hat{r}}_{ui}=\mu +b_u+b_i+p_u^T{q}_i$$

$\mu$ is the global average rating, $b_u$ the user bias, $b_i$ the item bias. The optimization objective updates the biases as well:

$$\underset{P,Q,b_u,b_i}{\min }\frac{1}{2}\sum _{(u,i)\in \mathcal{K}}{\left(r_{ui}-\mu -b_u-b_i-p_u^T{q}_i\right)}^2+\lambda (\Vert p_u{\Vert }^2+\Vert q_i{\Vert }^2+b_u^2+b_i^2)$$

$$b_u\leftarrow b_u+\eta (e_{ui}-\lambda b_u),b_i\leftarrow b_i+\eta (e_{ui}-\lambda b_i)$$

Analysis: Matrix factorization handles sparse data naturally (two users can be linked through latent factors without any shared rating), and inner-product retrieval is efficient. But it remains a linear model, hard to fuse with side information or complex feature crossings. This leads directly to the two-tower and deep models of later chapters.

⚠️ Common Mistakes in 2.1

Chapter Summary

📌 Key Takeaways

❓ FAQ

Q1: When should I use ItemCF vs. UserCF?

A: Use ItemCF when the item set is stable and you need to explain "why this similar item is recommended" (the industrial mainstream); use UserCF when user interests strongly converge (e.g., breaking news) or for social "similar people" recommendation. In user cold-start scenarios, ItemCF is more robust.

Q2: What exactly is the difference between cosine similarity and Pearson correlation?

A: Cosine only looks at the angle between interaction vectors and is affected by absolute item popularity; Pearson first centers (subtracts respective means), removing rating-habit differences between "pushovers vs. strict graders" and focusing on relative trends. Prefer Pearson with rating data; use cosine for implicit feedback.

Q3: Why does matrix factorization handle sparse data better than ItemCF?

A: ItemCF needs two items to share interacting users before similarity can be computed; matrix factorization, through a shared latent-factor space, lets two users with no common ratings recommend for each other via close latent vectors, generalizing to unseen combinations.

🔗 Connections to Later Chapters

• 2.2 (Vector Retrieval I2I) ports sequence modeling (Word2Vec) into similarity learning, and uses item attention to solve MF's difficulty in fusing side info.
• 2.3 (Two-Tower Model) upgrades MF's inner-product idea to deep-network encoding, enabling efficient U2I retrieval.
• 2.4 (Sequential Retrieval) further captures temporal interest dynamics ignored by ItemCF/MF.
• 3.x (Ranking) later applies complex deep models to finely rank the thousands of candidates retrieved in this chapter.

Practice Problems

Work through all problems in order — they get progressively harder. Each has a complete solution you can reveal after trying it yourself.

Problem 2.1.1 — Similarity Normalization 🟢 Easy

User A has interacted with 100 items, user B with 10 items, and they share 5 common items. Compute the Jaccard coefficient, and explain what would go wrong if you instead used "raw co-occurrence count = 5" as the similarity.

Problem 2.1.2 — ItemCF Scoring 🟢 Easy

User $u$ has interacted with items $\{j_1,j_2\}$, with interest strengths $r_{u{j}_1}=1$ and $r_{u{j}_2}=0.5$. Item $i$ has similarity $0.8$ with $j_1$ and $0.3$ with $j_2$. Compute the user's interest score $p(u,i)$ for candidate item $i$.

Problem 2.1.3 — The Specificity Intuition of Swing 🟡 Medium

Consider two item pairs $(h,p)$ and $(h,t)$. Users A and B both interacted with both pairs, and A and B's other shared behavior counts are 4 (for h,p) and 2 (for h,t). Let $\alpha =1$. Suppose $(h,p)$ has only this single pair of common users, while $(h,t)$ additionally receives a contribution of the same structure from another common user pair C and D. Compare $s(h,p)$ and $s(h,t)$, and explain what Swing is trying to filter.

Problem 2.1.4 — FunkSVD Gradient Update 🔴 Hard

Given a known rating $r_{ui}=4$, current $p_u=[0.5,0.2{]}^T$, $q_i=[1.0,0.5{]}^T$, $\eta =0.1$, no regularization. Compute by hand $p_u$ and $q_i$ after one gradient descent step (keep 3 decimal places).

🏆 Challenge: Design a Retrieval Combination

A short-video platform adds tens of millions of items daily, with an enormous long tail. Write about 150 words explaining how you would combine this chapter's ItemCF, Swing, and matrix factorization as multi-channel retrieval (what each channel is responsible for, how they complement each other), and identify which channel should backstop long-tail new items and why.