Please use this identifier to cite or link to this item:
|Title:||A theoretical analysis of query selection for collaborative filtering|
|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. 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|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Oct 11, 2018
WEB OF SCIENCETM
checked on Oct 2, 2018
checked on Oct 6, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.