TIME: 1:30-2:20 pm,  Nov 6, 2007

PLACE: CSE 503  

SPEAKER: Robert Kleinberg
         Cornell University

TITLE:  Online learning algorithms for searching and ranking


ABSTRACT:
This talk discusses some algorithm design problems that
stem from the challenge of using implicit feedback from users
to optimize the ranking of documents in response to a query.
We will first consider the problem of inserting a new document
into its proper position in an already sorted list, using the
feedback from users' clicks.  This can be modeled as a noisy
binary search problem.  We present an algorithm whose query
complexity is information-theoretically optimal, up to a constant
factor.  The second part of the talk considers the problem of
learning a ranking which maximizes utility for a heterogeneous
user population.  We show how this can be formulated as a
generalization of the multi-armed bandit problem, and we give
an algorithm for one special case of the problem (corresponding
to the objective of minimizing abandonment) whose worst-case
performance cannot be improved without violating complexity-theoretic
lower bounds.

The first part of the talk is joint work with Richard Karp.  The
second part is joint work with Thorsten Joachims and Filip
Radlinski.