Please use this identifier to cite or link to this item: https://doi.org/10.1023/A:1022961719072
Title: A theoretical analysis of query selection for collaborative filtering
Authors: Dasgupta, S.
Lee, W.S. 
Long, P.M.
Keywords: Approximation algorithms
Collaborative filtering
Inapproximability
Membership queries
Recommender systems
Issue Date: 2003
Source: 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. https://doi.org/10.1023/A:1022961719072
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
URI: http://scholarbank.nus.edu.sg/handle/10635/39516
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.

SCOPUSTM   
Citations

10
checked on Dec 13, 2017

WEB OF SCIENCETM
Citations

4
checked on Dec 13, 2017

Page view(s)

46
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


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