CS 789 THEORY SEMINAR [home]

Speaker:  Mark Sandler  
Affiliation: Computer Science, Cornell University
Date: Monday, April 22, 2002
Title: Convergent Algorithms for Collaborative Filtering

Abstract: 

A collaborative filtering system analyzes data on the past behavior of its users so as to make recommendations --- a canonical example is the recommending of books based on prior purchases. The full potential of collaborative filtering implicitly rests on the premise that, as an increasing amount of data is collected, it should be possible to make increasingly high-quality recommendations. Despite the prevalence of this notion at an informal level, the theoretical study of such convergent algorithms has been quite limited.

To investigate such algorithms, we generalize a model of collaborative filtering proposed by Kumar et al., in which the recommendations made by an algorithm are compared to those of an omniscient algorithm that knows the hidden preferences of users. Within our generalized model, we develop a recommendation algorithm with a strong convergence property --- as the amount of data increases, the quality of its recommendations approach those of the optimal omniscient algorithm. We also consider a further generalization, a mixture model proposed by Hofmann and Puzicha; here we prove that, in a natural sense, no recommendation algorithm can achieve convergent behavior with respect to the optimum.

Joint work with Jon Kleinberg

--------------