Learning Mixed Membership Mallows Models from Pairwise Comparisons
  We propose a novel parameterized family of Mixed Membership Mallows Models
(M4) to account for variability in pairwise comparisons generated by a
heterogeneous population of noisy and inconsistent users. M4 models individual
preferences as a user-specific probabilistic mixture of shared latent Mallows
components. Our key algorithmic insight for estimation is to establish a
statistical connection between M4 and topic models by viewing pairwise
comparisons as words, and users as documents. This key insight leads us to
explore Mallows components with a separable structure and leverage recent
advances in separable topic discovery. While separability appears to be overly
restrictive, we nevertheless show that it is an inevitable outcome of a
relatively small number of latent Mallows components in a world of large number
of items. We then develop an algorithm based on robust extreme-point
identification of convex polygons to learn the reference rankings, and is
provably consistent with polynomial sample complexity guarantees. We
demonstrate that our new model is empirically competitive with the current
state-of-the-art approaches in predicting real-world preferences.
