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.

研究在线用户行为的推荐系统，介绍针对在线正面评级的一类协同过滤算法，分析了用户响应概率、探索用户喜好所需评级数和更新用户偏好所需评级数之间的相关性，探讨正负评级和正面评级之间相同和不同的方面对于评级数的影响。