Please use this identifier to cite or link to this item:
Title: A theoretical analysis of query selection for collaborative filtering
Authors: Dasgupta, S.
Lee, W.S. 
Long, P.M.
Keywords: Approximation algorithms
Collaborative filtering
Membership queries
Recommender systems
Issue Date: 2003
Citation: Dasgupta, S., Lee, W.S., Long, P.M. (2003). A theoretical analysis of query selection for collaborative filtering. Machine Learning 51 (3) : 283-298. ScholarBank@NUS Repository.
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)(1n(|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, η) 1n |F|/1+deg(F, η) + 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.
Source Title: Machine Learning
ISSN: 08856125
DOI: 10.1023/A:1022961719072
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Jun 8, 2021


checked on Jun 8, 2021

Page view(s)

checked on Jun 11, 2021

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.