Natural language research announcements

["Samdani, Rajhans" <rsamdan2 AT illinois.edu>]

Hi all,

Due to a good deal of interest expressed, the Prof. Oh is now giving a talk 
on his crowdsourcing work which is also relevant to trustworthiness, 
information networks, etc. Here are the changed title and abstract:

Title: Designing reliable crowdsourcing systems: efficient algorithms and 
fundamental limits

Abstract:
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 a 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. Therefore, in terms of the budget required to achieve a certain 
reliability, our approach is order-optimal. Further, we show that even if we 
use adaptive schemes to assign tasks based on all the responses collected 
thus far, the necessary budget to achieve a certain target reliability still 
scales in the same manner. Hence, perhaps surprisingly, the gain in using 
adaptive task allocation schemes is only marginal. 

________________________________________
From: Samdani, Rajhans
Sent: Monday, February 18, 2013 2:04 PM
To: 
aiis AT cs.uiuc.edu;
 
aivr AT cs.uiuc.edu;
 
vision AT cs.uiuc.edu;
 
eyal AT cs.uiuc.edu;
 
aistudents AT cs.uiuc.edu;
 Girju, Corina R; Blake, Catherine; nl-uiuc; Efron, Miles James
Subject: AIIS talk by Prof. Sewoong Oh on Friday, Feb 22

Hi all,

This week we're hosting Prof. Sewoong Oh 
(http://web.engr.illinois.edu/~swoh/) from the Industrial Engineering 
department. Prof. Oh has done a lot of interesting work in Machine Learning, 
amongst other things. Here are the talk details:

When: Friday, Feb 22, 2 pm.

Where: Siebel Center, 3405.

Title: Ranking from Pair-wise Comparisons

Abstract:
The question of aggregating pairwise comparisons to obtain a global ranking 
has been of interest for a very long time: be it ranking of online gamers 
(e.g. MSR's TrueSkill system) and chess players, aggregating social opinions, 
or deciding which product to sell based on transactions. In addition to 
obtaining a ranking, finding 'scores' for each object is of interest for 
understanding the intensity of the preferences. In this talk, I will describe 
a new approach for discovering scores for objects (or items) from pairwise 
comparisons. The algorithm has a natural random walk interpretation over the 
graph of objects with an edge present between a pair of objects if they are 
compared; the stationary probability of this random walk assigns a score to 
each objects. To establish the efficacy of our method, we consider the 
popular Bradley-Terry-Luce (BTL) model and provide an upper bound on the 
finite sample error rate. The number of samples required to learn the score 
well with high probability depends on the structure of the comparisongraph. 
When the Laplacian of the comparison graph has a strictly positive spectral 
gap, this leads to an order-optimal sample complexity. We also provide 
numerical results on real and synthetic data-sets to compare our approach to 
other popular approaches.

Bio: Sewoong Oh is an Assistant Professor of Industrial and Enterprise 
Systems Engineering at UIUC. His research interest is in understanding how to 
extract meaningful information from societal data, such as aggregating 
opinions on social computation platforms like Mechanical Turk, making 
recommendations from rating of individuals, and finding ranking from 
comparisons.

Hope to see you all!
Best,
Rajhans