Collaborative Filtering and Learning

我们建议开发一个理论框架和算法的推荐系统，其中的任务是推荐产品给用户根据他们过去的选择。在这个建议中，我们提出的初步结果是惊人的比以前的更好。具体来说，以前已知的最好的算法是集中式的，时间复杂度为O（mn）（其中m和n分别表示用户和产品的数量），并且依赖于一些关于用户偏好的强假设。我们证明了以下结果。时间复杂度为O（m + n）的集中式算法。该算法在复杂性和消除关键的“间隙”和“可分性”的假设，放弃了以前的算法的基于代数的方法。其次，我们提出了第一个分布式推荐系统的算法，这也解决了以前的工作中提出的一个开放的问题。该算法是弹性的自适应拜占庭用户，这是很重要的电子商务的背景下。用户在任何异步调度下使用分布式算法完成的集体工作量都是O（n + mlogm）。如果用户满足“可分性”假设，我们的算法也可以在不增加复杂性的情况下完全表征每个用户。 我们的算法表明，传统上用于攻击这些问题的方法（特别是奇异值分解）是不必要的。此外，我们相信我们的方法简单到可以实施，从而对整个社会产生真实的影响。具体来说，惠普将与JHU和特拉维夫大学合作进行技术转让。该项目将通过将本科生和研究生紧密结合到项目中并通过讲座、笔记和出版物传播成果来促进知识和教育。

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.