Skip to content
AI.info

Recommender systems

Similarity, Normalization, Shrinkage, and Sparsity

Choose and audit similarity measures for sparse recommendation data, including centering, significance weighting, shrinkage, and popularity correction.

By the end you can

Similarity combines geometry with an evidence model

Cosine, Pearson, Jaccard, adjusted cosine, lift, and learned distance functions emphasize different aspects of behavior. None is universally correct. What a score can mean is fixed by two things: how the data is represented, and what the missing entries are assumed to mean. So start with the matrix underneath, and with how little of it exists.

That figure gets published. Every MovieLens release carries a density number in a table, and Harper and Konstan's caption defines the column exactly: “The sole computed column, Density, represents the percentage of cells in the full user-item matrix that contain rating values.”

ML-100K was collected between September 1997 and April 1998. It holds 100,000 ratings from 943 users on 1,682 movies. Density: 6.30%. ML-20M covers January 1995 to March 2015. It holds 20,000,263 ratings from 138,493 users on 27,278 movies. Density: 0.54%. The field's own standard benchmark grew 200x in ratings and got roughly twelve times emptier. Every similarity computed on it is computed from that 0.54%.

Thin support has to be handled or it wins. The reference implementations handle it in the formula, not in a caveat. Koren's 2010 item-item recommender does not use a raw Pearson correlation as its similarity. It uses a shrunk one: s_ij = (n_ij / (n_ij + lambda_4)) * rho_ij. Here n_ij is the number of users who rated both items i and j, and the paper gives 100 as a typical value for lambda_4.

The reason is the one this lesson keeps returning to: “Since many ratings are unknown, it is expected that some items share only a handful of common raters. Computation of the correlation coefficient is based only on the common user support. Accordingly, similarities based on a greater user support are more reliable.”

The constant does the arguing. At lambda_4 = 100, a pair with 10 common raters keeps under a tenth of its raw coefficient. A pair with 1,000 keeps over 90%.

Shrinkage, a minimum-overlap rule, significance weighting, Bayesian smoothing, and uncertainty-aware thresholds all do one job between them. They stop a tiny coincidence from outranking evidence that has held up.

Choosing a similarity function commits you to an assumption about what the missing entries mean, whether or not anyone writes that assumption down.

Case

Amazon’s correction for the recommendation that was always the bestseller

The popularity correction was already in place before the famous item-to-item algorithm arrived. It sat inside the user-based system that item-to-item replaced, and Amazon's engineers wrote it down themselves in 2003: “To compensate for best-selling items, the algorithm typically multiplies the vector components by the inverse frequency (the inverse of the number of customers who have purchased or rated the item), making less well-known items much more relevant.”

Scale is why it mattered. The same paper reports Amazon.com at more than 29 million customers and several million catalog items. MovieLens at the time had 35,000 customers and 3,000 items. EachMovie had 4,000 and 1,600.

The paper also names the cost of the cheap answer to sparsity. Discarding the most popular or the most unpopular items makes the problem tractable, and destroys recommendations for the customers who bought only those items. Trimming the head and the tail is not a neutral simplification. It is a decision about whose recommendations stop working.

Amazon's later retrospective states the failure mode without the formula: “Simply counting how often purchasers of item A also bought item B wouldn’t do; that would make a few bestsellers like Harry Potter books and trash bags the top recommendations for every customer on every purchase”. Relatedness was defined instead against a baseline — “Item B is related to item A if purchasers of A are more likely to buy B than the average Amazon customer is” — and heavy buyers were discounted later, “according to the heaviness of their buying”.

The two corrections are not one correction applied twice. The average-customer denominator is a per-item baseline, and it takes item popularity out. Damping heavy buyers takes user activity out. A customer who buys in enormous quantities stands behind nearly every pair in the table.

The same hazard turns up on the implicit-feedback side, where there are no ratings on a shared scale at all. Koren and two co-authors, in 2008: “Frequencies for disparate users might have very different scale depending on the application, and it is less clear how to calculate similarities”.

Key idea

Precision without support is not evidence

A high similarity without support is a precise-looking statement about very little data. Koren's shrinkage constant is that sentence written as arithmetic. At lambda_4 = 100, a coefficient resting on 10 common raters survives at under a tenth of its computed value.

Shrinkage can stop a thin coefficient from dominating, but it cannot manufacture the evidence that was never collected.

Example

In the Netflix Prize data, most records have no similar record at all

Someone measured what sparsity does to a real recommendation dataset. They were trying to break it, not recommend from it. Narayanan and Shmatikov, on the Netflix Prize data: “As a real-world example, in appendix E we show that the Netflix Prize dataset is overwhelmingly sparse: for the vast majority of records, there isn't a single similar record in the entire 500,000-record dataset.” The same property is what makes rare items so identifying. Six rare titles are enough to identify 84% of the half a million people in that set.

Read that from the similarity side. If most records have no genuine neighbour, a strong neighbour score is not the common case being reported. It is the exception, and the exception is where the thin evidence collects. Two users whose entire overlap is one play of the same obscure track have a maximal Jaccard similarity, because every observed event does overlap. A system that transfers a large set of unrelated preferences on that basis has been fooled by a numerator that told the truth and a denominator nobody looked at.

  • Numerator: The shared evidence looked strong because every observed event overlapped — the coefficient is arithmetically correct and states nothing false.
  • Denominator: The profiles were tiny, so the score ignored severe uncertainty; Koren's shrinkage answers precisely this, multiplying the coefficient by n_ij / (n_ij + 100) instead of trusting it as computed.
  • Popularity context: Rare and popular overlaps carry different information — 6 rare titles identify 84% of the half a million people in the Netflix Prize set, and that is the same property that makes a single rare co-occurrence look like proof of shared taste.
  • Normalization: Raw counts, binary vectors, centered ratings, and TF–IDF-like weights imply different geometries. The TF–IDF-like weight has a name and a date here: inverse user frequency, f_j = log(n/n_j), published in 1998 by Breese and colleagues.
  • Decision cost: A noisy similarity can contaminate many recommendations when reused as a retrieval primitive, and a table computed once is read by everything downstream of it.

Visual

The anatomy of a defensible similarity score

A similarity score is defensible when someone can say where each part of it came from, and every part has a published instance to point at. Representation fixes the coordinates. Normalization takes activity and popularity out of them: Amazon's user-based algorithm multiplied vector components by inverse frequency, and the inverse user frequency f_j = log(n/n_j) is the same idea with a measurement attached. Overlap support records how much evidence there was — n_ij, in Koren's notation, the number of users who rated both items. Shrinkage pulls the thin cases back toward a neutral baseline, through the factor n_ij / (n_ij + 100). The decision threshold then rules on whether the number may be used at all. Church and Hanks refused to discuss any pair whose joint count did not exceed 5. That is the crudest version of this stage, and still an explicit one.

FigureProcess · 5 steps
  1. 1

    Representation

    Define binary, count, rating, recency, or weighted coordinates.

  2. 2

    Normalization

    Control user activity, item popularity, scale use, or vector magnitude.

  3. 3

    Overlap support

    Record how many comparable observations contribute.

  4. 4

    Shrinkage

    Pull weak estimates toward a prior or neutral baseline.

  5. 5

    Decision threshold

    Use the score only when support and downstream risk are acceptable.

Example

Geometry mistakes

Scale mismatch is visible in the vectors and context mixing is not. One shows up when a feature family with a wider numeric range dominates distance. The other hides in a similarity table that averages relations from surfaces and eras nobody separated.

  • Scale mismatch: One feature family dominates distance because its numeric range is larger, and the range is readable off the vectors themselves.
  • Popularity leakage: Common items create similarity that reflects exposure rather than preference. “The idea is that universally liked items are not as useful in capturing similarity as less common items,” Breese and colleagues wrote in 1998 — and then they measured the fix. Inverse user frequency improved the ranked score in all 24 experiments, 12 each for vector similarity and for correlation (3 datasets x 4 protocols). It was significant in 23 of those 24 cases, and the average gain was 1.9%: 2.2% for vector similarity, 1.5% for correlation. On EachMovie under absolute-deviation scoring the average over 8 experiments was 11%, significant in 6 of 8, at 15.5% and 6.5%. The correction is real and mostly modest. Worth doing, not a result on its own.
  • Rare-event explosion: A single unusual overlap receives an extreme lift or PMI value. The people who brought the measure into corpus linguistics shipped a guard against it in 1990. Church and Hanks set the window size w to five words and refused to discuss any word pair with f(x,y) <= 5, because “the association ratio becomes unstable when the counts are very small”. They named the better instrument too — t-scores, throwing out pairs that were not significant — but it needs an estimate of the variance of f(x,y). So for the rest of the paper they “adopt the simple but arbitrary threshold, and ignore pairs with small counts”.
  • Support hidden: Serving stores only the score and not n_ij, so explanations omit the uncertainty that the score was computed with.
  • Context mixing: Relations from different surfaces or eras are averaged into one table, and nothing in the coordinates records which was which.

Steps

Calibrate a similarity primitive

Specify what the score must ignore before choosing how to compute it. Scale, popularity, and raw activity are the usual candidates. The final step asks whether the calibrated primitive changed anything a user would notice.

That final step is the one a whole field can skip at once. Eighteen deep-learning papers on top-n recommendation appeared between 2015 and 2018 at four major venues. In 2019 Ferrari Dacrema and two colleagues tried to reproduce them. Their abstract: “Only 7 of them could be reproduced with reasonable effort. For these methods, it however turned out that 6 of them can often be outperformed with comparably simple heuristic methods, e.g., based on nearest-neighbor or graph-based techniques.”

7 out of 18 is 39%, and the rate moved by venue: KDD 3 of 4, RecSys 1 of 7, SIGIR 1 of 3, WWW 2 of 4. The one remaining method clearly outperformed the baselines. It did not consistently outperform a well-tuned non-neural linear ranking method.

The comparably simple heuristic in that sentence is the primitive this lesson is about. Calibrating a similarity function is not the cheap preliminary underneath the interesting model. On this evidence it is frequently where the result actually lives.

FigureProcess · 5 steps

  1. 1. Specify invariances

    Decide which scale, activity, or popularity differences should not matter.

  2. 2. Choose representation

    Match binary, count, rating, or time-weighted vectors to the event semantics.

  3. 3. Add support features

    Retain overlap count, recency, and confidence with the score.

  4. 4. Stress rare and head cases

    Inspect extreme similarities under sparse and popular conditions.

  5. 5. Validate downstream value

    Measure candidate recall, ranking lift, coverage, and instability.

Support should travel with similarity

A neighbor table should store score, overlap, relation window, source policy, and freshness. Downstream models can then learn when to trust the relation, instead of treating all similarities as equally certain.

Implicit-feedback models make the same separation at the level of a single observation. Koren and his 2008 co-authors split what the user did from how much it tells you: “as rui grows, we have a stronger indication that the user indeed likes the item”. So confidence is set to “cui = 1 + αrui”, which also leaves “some minimal confidence in pui for every user-item pair”.

Spark's MLlib documentation implements the same contract independently. It describes the observed numbers as ones that “are then related to the level of confidence in observed user preferences, rather than explicit ratings given to items”, with alpha as the parameter that “governs the baseline confidence in preference observations”. A preference and the confidence in it are two fields, not one number.

Offline evaluation should compare both relation accuracy and the effect on candidate coverage. A conservative similarity may reduce noisy pairs while increasing tail-item opportunity.

A bare score gives the downstream model no way to tell a well-supported relation from a lucky one.

Key idea

The confidence rule

Do not expose or explain a similarity without enough evidence to defend both its geometry and its support. Every serious version of this rule is a number somebody wrote down: Koren's lambda_4 of 100, Church and Hanks' refusal of any pair with f(x,y) <= 5, the confidence term cui = 1 + αrui. None of them is a caveat in prose.

Exposing an unsupported relation as an explanation spends user trust on a coincidence, and the explanation is what they remember.

Key takeaways