[Dmbu-l] Talk this Friday Pranjal Awasthi (Princeton), 11/21, 10:30 am MCS 148

Dora Erdos edori at bu.edu
Mon Nov 17 10:58:13 EST 2014


Hi All,

this week Pranjal Awasthi from Princeton is going to give a talk on 
mictures of ranking models.

Best,
Dora

Title: Learning mixtures of ranking models

Probabilistic modeling of ranking data is an extensively studied
problem with applications ranging from understanding user preferences
in electoral systems and social choice theory, to more modern learning
tasks in online web search, crowd-sourcing and recommendation
systems. This work concerns learning the Mallows model -- one of the
most popular probabilistic models for analyzing ranking data. In this
model, the user's preference ranking is generated as a noisy version
of an unknown central base ranking. The learning task is to recover
the base ranking and the model parameters using access to noisy
rankings generated from the model.

Although well understood in the setting of a homogeneous population (a
single base ranking), the case of a heterogeneous population (mixture
of multiple base rankings) has so far resisted algorithms with
guarantees on worst case instances. In this talk I will present the
first polynomial time algorithm which provably learns the parameters
and the unknown base rankings of a mixture of two Mallows models. A
key component of our algorithm is a novel use of tensor decomposition
techniques to learn the top-k prefix in both the rankings. Before this
work, even the question of identifiability in the case of a mixture of
two Mallows models was unresolved.

Joint work with Avrim Blum, Or Sheffet and Aravindan Vijayaraghavan.


More information about the Dmbu-l mailing list