Collaborative Filtering and Learning

我们建议为推荐系统开发一个理论框架和算法，其中的任务是根据用户过去的选择向用户推荐产品。在这个建议中，我们提出的初步结果明显优于以前的结果。具体来说，之前已知的最佳算法是集中式的，时间复杂度为O(mn)（其中m和n分别表示用户和产品的数量），并且依赖于一些关于用户偏好的强假设。我们演示了以下结果。首先是时间复杂度为0 （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.