Convergent algorithms for collaborative filtering

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 Puzichaomt; here we prove that, in a natural sense, no recommendation algorithm can achieve convergent behavior with respect to the optimum.