Fast Collaborative Filtering from Implicit Feedback with Provable Guarantees
This addresses the problem of scalable recommendation systems for web applications with large implicit feedback datasets, though it is incremental as it builds on existing factorization methods.
The paper tackles the challenge of building recommendation systems from implicit feedback, where only user-item interactions are available, by proposing a Method of Moment-based algorithm that is globally convergent and requires only three passes through the dataset, scaling to millions of users on limited hardware while achieving competitive performance.
Building recommendation algorithms is one of the most challenging tasks in Machine Learning. Although most of the recommendation systems are built on explicit feedback available from the users in terms of rating or text, a majority of the applications do not receive such feedback. Here we consider the recommendation task where the only available data is the records of user-item interaction over web applications over time, in terms of subscription or purchase of items; this is known as implicit feedback recommendation. There is usually a massive amount of such user-item interaction available for any web applications. Algorithms like PLSI or Matrix Factorization runs several iterations through the dataset, and may prove very expensive for large datasets. Here we propose a recommendation algorithm based on Method of Moment, which involves factorization of second and third order moments of the dataset. Our algorithm can be proven to be globally convergent using PAC learning theory. Further, we show how to extract the parameters using only three passes through the entire dataset. This results in a highly scalable algorithm that scales up to million of users even on a machine with a single-core processor and 8 GB RAM and produces competitive performance in comparison with existing algorithms.