The Sample Complexity of Online One-Class Collaborative Filtering

2017-05-31 · ICML 2017 8 · Reinhard Heckel, Kannan Ramchandran

We consider the online one-class collaborative filtering (CF) problem that consists of recommending items to users over time in an online fashion based on positive ratings only. This problem arises when users respond only occasionally to a recommendation with a positive rating, and never with a negative one. We study the impact of the probability of a user responding to a recommendation, p_f, on the sample complexity, i.e., the number of ratings required to make `good' recommendations, and ask whether receiving positive and negative ratings, instead of positive ratings only, improves the sample complexity. Both questions arise in the design of recommender systems. We introduce a simple probabilistic user model, and analyze the performance of an online user-based CF algorithm. We prove that after an initial cold start phase, where recommendations are invested in exploring the user's preferences, this algorithm makes---up to a fraction of the recommendations required for updating the user's preferences---perfect recommendations. The number of ratings required for the cold start phase is nearly proportional to 1/p_f, and that for updating the user's preferences is essentially independent of p_f. As a consequence we find that, receiving positive and negative ratings instead of only positive ones improves the number of ratings required for initial exploration by a factor of 1/p_f, which can be significant.

📄 PDF Abstract BibTeX arXiv:1706.00061

Code (1)

Atomu2014/product-nets-distributed tf

Tasks

Collaborative Filtering Recommendation Systems

Broad Recommender System: An Efficient Nonlinear Collaborative Filtering Approach

2022-04-20 · Ling Huang, Can-Rong Guan, Zhen-Wei Huang, Yuefang Gao 외

Recently, Deep Neural Networks (DNNs) have been widely introduced into Collaborative Filtering (CF) to produce more accurate recommendation results due to their capability of capturing the complex nonlinear relationships…

Collaborative Filtering Recommendation Systems

Thy Friend is My Friend: Iterative Collaborative Filtering for Sparse Matrix Estimation

2017-12-01 · NeurIPS 2017 12 · Christian Borgs, Jennifer Chayes, Christina E. Lee, Devavrat Shah

The sparse matrix estimation problem consists of estimating the distribution of an $n\times n$ matrix $Y$, from a sparsely observed single instance of this matrix where the entries of $Y$ are independent random variable…

Collaborative Filtering Community Detection Graphon Estimation Matrix Completion+1

Graph Contrastive Learning with Multi-Objective for Personalized Product Retrieval in Taobao Search

2023-07-10 · Longbin Li, Chao Zhang, Sen Li, Yun Zhong 외

In e-commerce search, personalized retrieval is a crucial technique for improving user shopping experience. Recent works in this domain have achieved significant improvements by the representation learning paradigm, e.g.…

Collaborative Filtering Contrastive Learning Graph Learning Representation Learning+1

Streaming Variational Monte Carlo

2019-06-04 · Yuan Zhao, Josue Nassar, Ian Jordan, Mónica Bugallo 외

Nonlinear state-space models are powerful tools to describe dynamical structures in complex time series. In a streaming setting where data are processed one sample at a time, simultaneous inference of the state and its n…

Gaussian Processes State Space Models Time Series Time Series Analysis+2

Fast Variational AutoEncoder with Inverted Multi-Index for Collaborative Filtering

2021-09-13 · Jin Chen, Defu Lian, Binbin Jin, Xu Huang 외

Variational AutoEncoder (VAE) has been extended as a representative nonlinear method for collaborative filtering. However, the bottleneck of VAE lies in the softmax computation over all items, such that it takes linear c…

Collaborative Filtering