[Colloquium] TTIC Talks: Sewoong Oh, MIT

[Liv Leader]

When:     Thursday, April 5 @ 11 a.m.

Where:   TTIC, 6045 S. Kenwood Avenue, Room 526

Who:     Sewoong Oh, MIT

Title:      Learning from the Wisdom of the Crowd: Efficient Algorithms and
Fundamental Limits

Abstract:

This talk is on designing extremely efficient and provably order-optimal
algorithms to extract meaningful information from societal data, the kind
of data that comes from crowdsourcing platforms like Amazon Mechanical
Turk, or recommendation systems like the Netflix Challenge dataset.
Crowdsourcing systems, like Amazon Mechanical Turk, provide platforms where
large-scale projects are broken into small tasks that are electronically
distributed to numerous on-demand contributors. Because these low-paid
workers can be unreliable, we need to devise schemes to increase confidence
in our answers, typically by assigning each task multiple times and
combining the answers in some way. I will present the first rigorous
treatment of this problem, and provide both an optimal task assignment
scheme (using a random graph) and an optimal inference algorithm (based on
low-rank matrix approximation and belief propagation) for that task
assignment. This approach significantly outperforms previous approaches
and, in fact, is asymptotically order-optimal, which is established through
comparisons to an oracle estimator. Another important problem in learning
from the wisdom of the crowd is how to make product recommendations based
on past user ratings. A common and effective way to model these user
ratings datasets is to use low-rank matrices. In order to make
recommendations, we need to predict the unknown entries of a ratings
matrix. A natural approach is to find a low-rank matrix that best explains
the observed entries. Motivated by this recommendation problem, my approach
is to provide a general framework for recovering a lowrank matrix from
partial observations. I will introduce a novel, efficient and provably
order-optimal algorithm for this matrix completion problem. The optimality
of this algorithm is established through a comparison to a minimax lower
bound on what the best algorithm can do.

Host: Raquel Urtasun, rurtasun at ttic.edu

-- 
Liv Leader
Human Resources Coordinator

Toyota Technological Institute Chicago
6045 S Kenwood Ave
Chicago, IL 60637
Phone- (773) 702-5033
Fax-     (773) 834-9881
Email-  lleader at ttic.edu <jam at ttic.edu>
Web-   www.ttic.edu
<http://www.ttic.edu/>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20120329/0f75a0e5/attachment.htm