Collaborative Filtering and Learning

Johns Hopkins University, Baltimore MD

Investigators

Abstract

We propose to develop a theoretical framework and algorithms for recommendations system, where the task is to recommend products to users based on their past choices. In this proposal we present preliminary results that are strikingly better than previous ones. Specifically, the best previously known algorithm was centralized, had time complexity O(mn) (where m and n denote the number of users and products, respectively), and relied on some strong assumptions about the preferences of users. We demonstrate the following results. First, a centralized algorithm whose time complexity is O(m + n). This algorithm improves on the previous one both in complexity and in removing key "gap" and "separability" assumptions by abandoning the algebra-based approach of prior algorithms. Second, we present the first distributed algorithm for recommendation systems, which also solves an open problem posed in previous work. The algorithm is resilient against adaptive Byzantine users, which is important in the context of e-commerce. The collective work done by the users using the distributed algorithm under any asynchronous schedule is O(n + mlogm). Our algorithms can also, without increase in complexity, completely characterize each user, if the users satisfy the "separability" assumption. Intellectual merit and broader impact. Our algorithms demonstrate that the methods traditionally used to attack these problems (in particular, singular value decomposition) were not necessary. In addition, we believe that our methods are sufficiently simple to be implementable, thus having a real impact on society at large. Specifically, Hewlett Packard will be collaborating with JHU and Tel-Aviv University on technological transfer. The project will advance knowledge and education by tightly integrating undergraduate and graduate students into the project and by disseminating the results via lectures notes and publications.