Algorithmic Recommender Systems
Speaker: Boaz Patt-Shamir , Tel Aviv University
Date: October 19 2010
Time: 4:15PM to 5:15PM
Location: 32-144
Host: Scott Aaronson, CSAIL, MIT
Contact: Be Blackburn , 3-6098, imbe@mit.edu
Relevant URL: Recommender systems help users identify objects they may find
interesting, where objects may be books to read, films to watch, web
pages to browse, and even other users to contact. Formally, the input
to the system is the known preferences of the users, as deduced
somehow from their past choices. While many interesting ideas have
been developed to analyze characteristics of users (or objects) based
on past choices, this approach suffers from a foundational theoretical
flaw: feedback is ignored. Put simply, this setting is such that
choices determine recommendations, but recommendations are supposed to
influence choices.
In a recent line of work this gap was bridged by a simple algorithmic
model that assumes that the system may ask the user's opinion on any
object, and not only make recommendations about supposedly `nice'
objects. Typically, algorithms in this model ask users for their
opinions on controversial objects, and in return, the output consists
of almost complete reconstruction of user preferences. In this talk we
discuss this model and survey some basic and recent
results. Surprisingly, it turns out that there are algorithms that can
reconstruct user preferences (with high probability), using only a
little (polylog factor) more questions than the minimum possible.
See other events that are part of Theory Colloquium 2010/2011
See other events happening in October 2010
