Part II · Candidate generation · chapter 5 of 19

Collaborative filtering and similarity measures

The first approach to recommendation that worked, and still the basis of half the candidate generators in production. The whole construction rests on one substitution — the similarity measure — and the choice of that measure changes the output more than most architectural decisions do. We work through four measures on one numerical example where they give the opposite order, and then move from computed similarity to learned similarity.

What to take away

Every similarity measure is one formula with a different normalisation: $|A \cap B| / (|A|\,|B|)^{\alpha}$. Cosine is $\alpha = 0.5$, Jaccard is roughly linear, PMI is $\alpha = 1$.
The order of the pairs reverses. Cosine puts the pair of blockbusters first, PMI puts a pair based on fifteen observations first. Both measures are «right» in their own way.
PMI goes mad on rare pairs: two items watched by the same single person give PMI = 13.8 — three times more than an honest pair with six hundred observations.
Similarity can be learned rather than computed. EASE and SLIM use the same scoring formula, but the weights come from a regression, and that repairs three diseases of computed measures at once.

1. The idea of collaborative filtering

«Similar people like similar things». Formally there are two mirror-image approaches.

	User-based	Item-based
the logic	find similar users, take what they liked	find items similar to those the user already took
what we compute	similarity between users	similarity between items
how many objects	there are usually more users and they are less stable	there are fewer items, and similarities are more stable over time
in production	rarely	almost always: the matrix can be precomputed and stored as lists

The scoring formula and what is worth understanding in it

For item-based, the score of item $i$ for user $u$ is a sum over everything the user has already interacted with:

$$ \hat{s}(u, i) \;=\; \sum_{j \in H(u)} \mathrm{sim}(i, j) $$

where $H(u)$ is the user's history. That is: walk through everything the person has taken and add up how similar each of those is to the candidate.

Often a normalisation by $\sum_j \mathrm{sim}(i,j)$ is added, or the sum is limited to the top $k$ nearest neighbours — otherwise a long history dilutes the signal, and noisy weak links outweigh a few strong ones in the sum.

The key point: the whole model is the matrix $\mathrm{sim}$. What to put into it is what this chapter is about.

2. Similarity measures on one axis

For binary data (interacted / did not) the three classical measures are written almost identically.

$$ J(A,B) = \frac{|A \cap B|}{|A \cup B|}, \qquad \cos(A,B) = \frac{|A \cap B|}{\sqrt{|A|\,|B|}}, \qquad \mathrm{PMI}(A,B) = \log \frac{P(A,B)}{P(A)P(B)} $$

One axis: the strength of the normalisation

All three have the form $|A \cap B| \big/ (|A|\,|B|)^{\alpha}$ — only the exponent differs, that is, how harshly the measure penalises popularity.

Measure	Normalisation	A blockbuster of 10⁶ and a niche item of 10³, intersection 900
the raw number of co-occurrences	$\alpha = 0$ — none	900
cosine	$\alpha = 0.5$ — a square root	0.0285
Jaccard	roughly linear	0.0009
PMI and relatives	$\alpha = 1$ — full	9·10⁻⁷ before normalisation

It is clearest in the special case where the niche item is entirely contained in the blockbuster — everyone who watched $B$ also watched $A$. Then Jaccard equals $|B|/|A|$ and cosine equals $\sqrt{|B|/|A|}$:

$\|B\|/\|A\|$	Jaccard	Cosine
1 / 100	0.0100	0.1000
1 / 1 000	0.0010	0.0316
1 / 10 000	0.0001	0.0100

The numbers are reproduced by the script _tools/similarity.py in this repository.

Jaccard suppresses a gap in popularity linearly, cosine by a square root. Hence the practical point: cosine is gentler towards the popular, Jaccard harsher.

«But cosine penalises popularity» — it depends what you compare it with

It is easy to get confused here, because cosine appears in two different stories and ends up on opposite sides.

Cosine against the inner product — that is about trained embeddings. The inner product decomposes as $|a||b|\cos\theta$, and in matrix factorisation the norm learns popularity. Cosine divides by the norms and throws it out entirely. Here cosine penalises popularity.
Cosine against Jaccard — that is about raw interaction sets. Both measures have $|A \cap B|$ in the numerator; the denominator distinguishes them, and Jaccard's is harsher. Here cosine is gentler towards popularity, by more than thirty times: 0.0285 against 0.0009.

There is no contradiction: the comparisons are different. But in an interview the phrase «cosine removes popularity» without saying what it is compared with invites a follow-up question.

PMI: comparing against expectation, not against sizes

PMI answers a different question: how many times more often the items occur together than they would if they were independent.

$$ \mathbb{E}\bigl[|A \cap B|\bigr] \;=\; \frac{|A|\cdot|B|}{N}, \qquad \mathrm{PMI} \;=\; \log \frac{|A \cap B|}{\mathbb{E}\bigl[|A \cap B|\bigr]} $$

Dividing by the expectation is exactly the built-in penalty for popularity: the more often an item occurs on its own, the higher the bar it has to clear.

Four pairs, an audience of a million

Pair	$\|A\|$	$\|B\|$	intersection	expected	cosine	Jaccard	PMI	NPMI
two blockbusters	500 000	400 000	210 000	200 000	0.470	0.304	0.05	0.031
two niche items	2 000	3 000	600	6	0.245	0.136	4.61	0.621
niche + ultra-rare	2 000	20	15	0.04	0.075	0.007	5.93	0.534
blockbuster + niche	500 000	2 000	1 200	1 000	0.038	0.002	0.18	0.027

The numbers are reproduced by the script _tools/similarity.py in this repository.

The order comes out opposite:

cosine and Jaccard: blockbusters → niche → ultra-rare → blockbuster with niche;
PMI: ultra-rare → niche → blockbuster with niche → blockbusters.

Let us take apart the first row — it is the important one

The intersection of two blockbusters is enormous, 210 thousand people, and cosine and Jaccard declare this pair the most similar in the table.

But 200 thousand was expected by chance. That is, there is almost no actual link: people watched both films not because they are similar but because they watched everything. PMI sees this: $\ln(210000/200000) = 0.05$, practically zero.

Conversely, the two niche items have an intersection of only 600 people — ten times less. But six were expected. A hundredfold excess, $\ln 100 = 4.61$. That is a real link.

And immediately the other side: PMI goes mad on rare pairs

The third row of the table: the pair «niche + ultra-rare» gets 5.93 from PMI — more than the honest pair of niche items with its 4.61. And the whole estimate rests on fifteen observations.

Take it to the limit. Suppose exactly one person watched two items, and it is the same person:

$$ \mathrm{PMI} \;=\; \ln\frac{1 \cdot 10^{6}}{1 \cdot 1} \;=\; 13.8 $$

Three times more than a pair with a real link on six hundred observations. Pure noise takes first place.

The reason: PMI measures how many times the expectation is exceeded, and when the expectation is close to zero, any single co-occurrence gives an enormous ratio.

NPMI and what it does not repair

Normalising by $-\log P(A,B)$ penalises rarity specifically: the rarer the pair, the larger the denominator.

$$ \mathrm{NPMI}(A,B) \;=\; \frac{\mathrm{PMI}(A,B)}{-\log P(A,B)} \;\in\; [-1, 1] $$

The table shows that this works: NPMI puts the pair of niche items (0.621) above the pair with the ultra-rare one (0.534), restoring a sensible order. But it does not remove the problem entirely — 0.534 is still very high for fifteen observations.

What NPMI does not do — contrary to a widespread belief

People often say NPMI «removes popularity». That is wrong, and it can be checked directly: take three pairs with the same excess over expectation — a popular one, a middling one and a niche one. NPMI will give them different values, and the popular one will get more, because its denominator $-\log P(A,B)$ is smaller.

So NPMI is not neutral towards popularity — it introduces a preference of its own, the reverse of PMI's. In practice that is rather for the better (noise is suppressed), but the phrase «cleaned of popularity» is inaccurate.

That is why in production NPMI almost always comes with two additions: a threshold on the number of co-occurrences (pairs with $|A \cap B| < 10\ldots50$ are dropped entirely) and shrinkage towards zero for small counts.

What to look for here

Switch the measure and watch how the composition of the top neighbours changes, not just the numbers. Cosine has the popular at the top, PMI the rare.
Set a threshold on the number of co-occurrences: the noise disappears from PMI's top and the order becomes meaningful. That is precisely the trick used in production.
Note the normalisation of the embeddings: the inner product and cosine give a different top, because the norm learns popularity.

What to say in an interview: «All the measures are one formula with a different strength of normalisation. Cosine is gentler than Jaccard towards the popular, PMI compares against expectation rather than sizes and therefore explodes on rare pairs. In production — NPMI with a threshold on co-occurrences».

3. Similarity can be learned rather than computed

All the measures above share one thing: the formula was chosen by a human, and it looks at a pair of items in isolation from all the others. EASE and SLIM remove both limitations.

One problem in one line

We look for an item-item matrix $B$ that approximates the interaction matrix by itself:

$$ X \;\approx\; XB $$

Writing out a cell, we get the score of item $i$ for user $u$:

$$ \hat{x}_{ui} \;=\; \sum_{j\,:\,x_{uj}=1} B_{ji} $$

This is exactly the same formula as item-based CF at the start of the chapter. There is one difference: the weights used to come from a ready-made similarity measure, and now column $j$ of the matrix $B$ holds the coefficients of a linear regression predicting column $j$ of $X$ from all the other columns.

Everything else follows from that: the regression sees the predictors together rather than one at a time.

EASE: the analytic solution

$$ \min_{B}\ \lVert X - XB\rVert_F^2 + \lambda \lVert B \rVert_F^2 \qquad \text{subject to } \operatorname{diag}(B) = 0 $$

The constraint on the diagonal is mandatory: without it there is a trivial solution $B = I$ — every item is perfectly predicted by itself, the error is zero and the usefulness is zero.

The problem is solved in closed form. Writing $G = X^{\top}X + \lambda I$ and $P = G^{-1}$:

$$ B_{ij} = -\frac{P_{ij}}{P_{jj}}\ (i \ne j), \qquad B_{jj} = 0 $$

No gradient descent at all — one matrix inversion.

What $-P_{ij}/P_{jj}$ means

The formula looks like an artefact of the derivation, but it has a precise meaning. $P = (X^{\top}X + \lambda I)^{-1}$ is an estimate of the precision matrix, the inverse of the covariance.

A known fact from graphical models: the conditional expectation of one variable given all the others equals $\mathbb{E}[x_j \mid x_{-j}] = x_{-j} \cdot B_{-j,j}$ — that is, exactly the prediction rule of EASE.

Hence a strict distinction from cosine. A zero in the covariance matrix is marginal independence: «they occur together no more often than by chance». A zero in the precision matrix is conditional: «they add nothing about each other beyond the rest of the catalogue». Cosine, Jaccard and PMI live in the first world, EASE in the second.

What this gives in numbers

A synthetic log of 20 000 baskets where the generating process is known. We predict «cereal»:

Predictor	Share of baskets	Cosine	EASE
milk	0.373	0.720	0.319
light milk (almost a duplicate)	0.359	0.705	0.245
a bag (almost everyone takes one)	0.901	0.499	0.083
coffee (unrelated)	0.301	0.302	0.024
competing muesli (a substitute)	0.197	+0.135	−0.115

The numbers are reproduced by the script _tools/ease_demo.py in this repository.

Three breakages of computed similarity are visible at once:

Popularity pretends to be a link. The «bag» comes third by cosine, above coffee. It does not predict cereal — it simply lies in every basket.
Duplicates are counted twice. Cosine gives milk and light milk 1.426 between them; EASE splits the weight between collinear predictors: 0.564.
Negative links do not exist. The substitute gets +0.135 by cosine and −0.115 by regression. A similarity formula cannot produce a negative weight by construction.

SLIM and how EASE differs from it

SLIM came earlier (2011) and solves the same problem with two additions: $L_1$ regularisation, which gives a sparse $B$, and the constraint $B \ge 0$.

What Steck's experiment showed

NDCG@100 on three standard datasets:

Model	ML-20M	Netflix	MSD
EASE	0.420	0.393	0.389
EASE with negative weights zeroed out	0.402	0.373	0.379
SLIM	0.401	0.379	did not finish

Table 1 from Steck, 2019.

The second row is the key. It is the same EASE with its negative weights simply crossed out, and it drops immediately to the level of SLIM. The whole gap is explained by the constraint $B \ge 0$ — the very one because of which the substitute in the example above got a zero instead of −0.115.

The figure that overturns intuition: about 60% of the learned weights are negative, on all three datasets. The model spends most of its capacity saying what the user does not want.

What no item-item method can do

Cold start is not solved at all. A new item has a zero column in $X$, so it has a zero column in $B$ too: recommending it is impossible under any circumstances.
No context whatsoever. No time, no device, no user features — only the set of their items.
The order of the history is ignored. $x_u$ is a set, not a sequence.
Memory is quadratic in the catalogue. For EASE the matrix $B$ is dense: 30 thousand items in float64 is about 7 GB, a million is impossible. SLIM was invented for exactly this.

So in production they are used not as the final model but as a candidate generator and a source of features: strong, cheap and completely explainable — you can always show which purchases contributed to the score.

Interview questions

How do Jaccard, cosine and PMI differ?

By the strength of the normalisation. All three have the form $|A\cap B| / (|A||B|)^{\alpha}$: cosine $\alpha = 0.5$ (a square root), Jaccard roughly linear, PMI $\alpha = 1$ (full normalisation).

In practice: cosine is gentler towards the popular than Jaccard — in the example with a blockbuster of 10⁶ and a niche item of 10³ with an intersection of 900, cosine gives 0.028 and Jaccard 0.0009, a difference of thirty times.

PMI answers a different question: not «how large is the intersection» but «how many times larger is it than expected under independence». So two blockbusters with an intersection of 210 thousand against 200 thousand expected get almost zero from PMI, while two niche items with an intersection of 600 against six expected get 4.61.

Why can't PMI be used as it is?

It explodes on rare pairs. A pair built on fifteen observations gets a PMI of 5.93 — more than an honest pair on six hundred observations with its 4.61. In the limit: two items watched by exactly the same single person give $\ln 10^6 = 13.8$, that is, pure noise takes first place.

The reason is that PMI measures a ratio to the expectation, and when the expectation is close to zero any single co-occurrence gives an enormous ratio.

The cure is NPMI (normalising by $-\log P(A,B)$, which penalises rarity) plus, mandatorily, a threshold on the number of co-occurrences and shrinkage for small counts. NPMI alone is not enough: a pair of fifteen observations still gets 0.534.

Is it true that NPMI cleans similarity of popularity?

No, and this is a common inaccuracy. It is checked directly: take three pairs with the same excess over expectation — a popular one, a middling one and a niche one. NPMI will give them different values, and the popular one will get more, because its denominator $-\log P(A,B)$ is smaller.

So NPMI introduces a preference of its own, the reverse of what PMI does. In practice that is rather useful — noise is suppressed — but the phrase «cleaned of popularity» is wrong.

Why is a learned item-item matrix better than a computed one?

The scoring formula is the same for both: walk through the history and add up the weights. The difference is where the weights come from. A computed measure looks at a pair of items in isolation; a regression sees all the predictors together.

That repairs three things. Popularity stops pretending to be a link: an item that lies in every basket gets a near-zero weight, because it adds nothing beyond the rest. Duplicates stop being counted twice: the regression splits the weight between collinear predictors. And negative weights appear — substitutes, which a similarity formula cannot express in principle.

Formally $B_{ij} = -P_{ij}/P_{jj}$ is the coefficient of a partial regression, that is, the move from marginal to conditional dependence.

EASE or SLIM: what is the difference and which to choose?

EASE is SLIM with the $L_1$ and the constraint $B \ge 0$ removed. In exchange there is a closed-form solution: one matrix inversion instead of coordinate descent column by column.

In quality the gap is entirely explained by the sign constraint: EASE with its negative weights zeroed out falls exactly to the level of SLIM (0.402 against 0.401 on ML-20M). About 60% of the weights in EASE are negative — the model spends most of its capacity on «what you do not want».

The choice is by resources: EASE costs $O(|I|^3)$ in time and $O(|I|^2)$ in memory, but does not depend on the number of users. For tens of thousands of items, take EASE. If the catalogue is such that a dense matrix does not fit, take SLIM with its sparsity.

One-screen cheat sheet

The CF formula

$\hat s(u,i) = \sum_{j \in H(u)} \mathrm{sim}(i,j)$. The whole model is the sim matrix.

One axis

$|A\cap B|/(|A||B|)^\alpha$. Cosine 0.5, Jaccard ~1 linear, PMI 1. Cosine is gentler towards the popular.

PMI

Compares against the expectation $|A||B|/N$, not against sizes. Explodes on rare pairs: noise gives 13.8.

NPMI

Divides by $-\log P(A,B)$. Repairs the order, does not remove popularity. Needs a threshold on co-occurrences.

EASE

$X \approx XB$, $B_{ij} = -P_{ij}/P_{jj}$ — a partial regression. Catches substitutes: 60% of weights are negative.

The shared limit

Cold start is not solved at all, there is no context, memory is $O(|I|^2)$. Hence a candidate generator, not the final model.

Primary sources

G. Linden, B. Smith, J. York. Amazon.com Recommendations: Item-to-Item Collaborative Filtering, IEEE Internet Computing 2003.
G. Bouma. Normalized (Pointwise) Mutual Information in Collocation Extraction, 2009 — where the NPMI normalisation comes from.
H. Steck. Embarrassingly Shallow Autoencoders for Sparse Data, WWW 2019 — EASE, the derivation and the comparison with SLIM.
X. Ning, G. Karypis. SLIM: Sparse Linear Methods for Top-N Recommender Systems, ICDM 2011.
The numbers in this chapter: _tools/similarity.py and _tools/ease_demo.py in this repository.

Measure	Normalisation	A blockbuster of 10⁶ and a niche item of 10³, intersection 900
the raw number of co-occurrences	\(\alpha = 0\) — none	900
cosine	\(\alpha = 0.5\) — a square root	0.0285
Jaccard	roughly linear	0.0009
PMI and relatives	\(\alpha = 1\) — full	9·10⁻⁷ before normalisation