A Theoretical Analysis of Query Selection for Collaborative Filtering |
| |
Authors: | Sanjoy Dasgupta Wee Sun Lee Philip M. Long |
| |
Affiliation: | (1) Computer Science Department, University of California, San Diego, USA;(2) Computer Science Department and Singapore-MIT Alliance, National University of Singapore, Singapore;(3) Genome Institute of Singapore, Singapore |
| |
Abstract: | We consider the problem of determining which of a set of experts has tastes most similar to a given user by asking the user questions about his likes and dislikes. We describe a simple algorithm for generating queries for a theoretical model of this problem. We show that the algorithm requires at most opt(F)(ln(|F|/opt(F)) + 1) + 1 queries to find the correct expert, where opt(F) is the optimal worst-case bound on the number of queries for learning arbitrary elements of the set of experts F. The algorithm runs in time polynomial in |F| and |X| (where X is the domain) and we prove that no polynomial-time algorithm can have a significantly better bound on the number of queries unless all problems in NP have nO(log log n) time algorithms. We also study a more general case where the user ratings come from a finite set Y and there is an integer-valued loss function on Y that is used to measure the distance between the ratings. Assuming that the loss function is a metric and that there is an expert within a distance from the user, we give a polynomial-time algorithm that is guaranteed to find such an expert after at most 2opt(F, ) ln + 2( + 1)(1 + deg(F, )) queries, where deg(F, ) is the largest number of experts in F that are within a distance 2 of any f F. |
| |
Keywords: | collaborative filtering recommender systems membership queries approximation algorithms inapproximability |
本文献已被 SpringerLink 等数据库收录! |
|