User-Based Collaborative Filtering

On one dataset, recommending the same chart to everybody beat a recommender that studies each person. On Epinions, in Ferrari Dacrema, Cremonesi and Jannach's 2019 measurements, the non-personalised TopPopular baseline — which knows nothing about any individual — scored HR@10 = 0.6644 and NDCG@10 = 0.4547. UserKNN, a user-neighborhood recommender of exactly the kind described here, scored HR@10 = 0.3922 and NDCG@10 = 0.3117 on the same data.

The comparison comes from a 2019 reproducibility study. It put user neighborhoods and the methods that were supposed to have superseded them on the same footing. Its authors could reproduce only 7 of 18 published neural recommenders, and 6 of those 7 could often be outperformed by simple nearest-neighbour or graph-based heuristics. They state the result without hedging: “In one case, even a non-personalized method that recommends the most popular items to everyone was the best one in terms of certain accuracy measures.”

Epinions is also where the catalogue is most lopsided. Its popularity distribution had a Gini index of 0.69, against 0.37 for CiteULike-a. The neighborhoods there were mathematically well-formed. They were built on co-ratings of the items nearly everyone touches. That is why the policy that skipped the neighborhood entirely did better.

The method compares a target user's interaction pattern with other users, selects a neighborhood, and aggregates the neighbors' preferences for unseen items. It can be intuitive and effective when the overlap is meaningful. The difficulty is defining comparable histories. The field's own benchmark shows how little material there is to compare.

MovieLens publishes the density of every rating matrix it has released. ML-100K — 943 users, 1,682 movies, 100,000 ratings, collected 9/1997-4/1998 — stands at 6.30%. ML-1M is at 4.47%. ML-10M at 1.34%. ML-20M — 138,493 users, 27,278 movies, 20,000,263 ratings, 1/1995-3/2015 — at 0.54%. Harper and Konstan define exactly what that column is: “The sole computed column, Density, represents the percentage of cells in the full user-item matrix that contain rating values.”

Density falls by more than an order of magnitude as the population grows. Two users sharing a handful of titles is the ordinary case, not the pathological one. Raw cosine similarity, Pearson correlation, centered ratings, implicit overlap, significance weighting, time windows: six answers to the question of what to do with that 0.54%. They select different neighborhoods from it.

Neighborhood methods spend most of their effort before any item is proposed. Four of the five steps decide how histories are represented, where overlap may be measured, and how much a thin overlap deserves to be trusted. Only the last step, aggregate items, produces something to show.

Measure overlap is the step the MovieLens densities describe. At ML-20M scale only 0.54% of the cells of the user-item matrix carry a rating. Two histories are nearly always compared on a handful of co-rated titles. Control confidence is the step that decides what to do about that, and Koren gives it a published form rather than a preference. The similarity actually used is scaled down in proportion to how few users rated both items, so a coefficient with almost no support contributes almost nothing. Represent histories and select neighbors sit on top of that thin evidence rather than repairing it.

The whole arrangement costs what Amazon's engineers named: O(MN) in the worst case, with M the number of customers and N the number of catalog items.

Tiny-overlap certainty is the failure that looks like a result: two shared items produce a perfect correlation and outrank a neighbor with real support. Scale collapse is the failure that looks like an engineering problem and is really a modeling one. The failure teams almost never measure is what the preference matrix discloses about the people in it.

Netflix released the Prize ratings matrix with the names taken off. Narayanan and Shmatikov ran a de-anonymisation algorithm against it. Eight movie ratings, of which 2 may be completely wrong, with dates carrying up to a 14-day error, uniquely identify 99% of the records. Two ratings and dates within 3 days suffice for 68%. With no dates at all, 84% of subscribers are uniquely identified from 8 known titles outside the 500 most-rated movies, 2 of which may be wrong. What they did with that: “Using the Internet Movie Database as the source of background knowledge, we successfully identified the Netflix records of known users, uncovering their apparent political preferences and other potentially sensitive information.” The FTC staff closing letter later cited the paper as demonstrating re-identification within the Prize 1 data set of over 480,000 customers.

The same distribution is at work in both directions. The popular titles that carry the overlap say little about anyone. The obscure ones that say almost nothing about taste identify people.

Comparable events have to be defined before two users can be called similar. Normalization and support shrinkage follow. Then somebody reads the neighbor lists by hand. The baselines settle whether any of it earned its place.

Step 3 does not have to be improvised. Koren stated the problem in 2008: “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 similarity he then uses is s_ij = (n_ij / (n_ij + lambda2)) * rho_ij, where n_ij is the number of users who rated both items and lambda2 is typically 100. Put support through it and the vague instruction becomes arithmetic. A correlation resting on 2 co-ratings keeps about 2 percent of its value. One resting on 400 co-ratings keeps 80 percent. That is what downweighting by the amount of evidence means once it is written down.

Step 5 decides whether the model ships, and the Epinions result is the reason it cannot be a formality. Popularity, item-item and matrix-factorization policies all have to be measured under the same protocol. A user-neighborhood policy can look reasonable in isolation and still be the wrong thing to serve. UserKNN's HR@10 = 0.3922 sat well below the TopPopular baseline's 0.6644. And the item-oriented family is the one credited with “Better scalability and improved accuracy”. A margin that has only been measured against nothing is not a margin.

Star ratings were all a film service's nearest neighbours shared: they lived in different markets, spoke different languages, watched for different households and purposes, rated only blockbusters, used the scale differently, and one perfect correlation rested on two co-rated titles; small profile changes replaced most of the selected neighbours from one week to the next. The service is invented, and the quiz below asks about it. Here is the routine run on it. All numbers are invented for the exercise.