An analysis of popularity biases in recommender system evaluation and algorithms

Résumé

Recommendation technologies have become increasingly commonplace in everyday applications for the general public. Recommender systems make individualized suggestions of products or choices that users would probably find interesting or useful. Implicit in the concept of recommendation is the idea that each user may draw further benefit from a recommendation that is tailored to her personal tastes, as it seems is reasonable to expect that personalized algorithms should be the most effective, be it just because they consider a larger output space than a one-size-fits-all recommendation. It has been recently found however that non-personalized majority-based recommendations are not as suboptimal as one might expect. A strong bias towards popular items has been furthermore found in the top-performing personalized algorithms. Therefore, it would be relevant to understand to what extent, and under what circumstances, popularity is really an effective signal when recommending, and whether its apparent effectiveness is due to, as seems likely, a bias in the current offline evaluation methodologies. This thesis addresses this question at a formal level, by identifying the factors that can affect the answer and modeling them in terms of dependencies between key random variables involving item rating, discovery and relevance. We find concrete conditions that guarantee popularity to be effective or quite the opposite, and settle the conditions under which there is a possibility of disagreement between observed and true accuracy. The clearest conclusions were reached for prototypical cases involving independence assumptions, without which we explain that any outcome is possible. Seeking further understanding of the general assumption-free case, we also study a particular case where item discovery is mainly a consequence of word-of-mouth in a social network. In addition, we provide a formal explanation of the bias towards recommending popular items that collaborative filtering methods present. We do so by developing a full probabilistic formalization of the k nearest neighbours scheme, upon which we also evidence the fundamental condition that makes this algorithm a personalized method and distinguishes it from pure popularity-based recommendations.