Generalized Method-of-Moments for Rank Aggregation
In this paper we propose a class of efficient Generalized Method-of-Moments (GMM) algorithms for computing parameters of the Plackett-Luce model, where the data consists of full rankings over alternatives. Our technique is based on breaking the full rankings into pairwise comparisons, and then computing parameters that satisfy a set of generalized moment conditions. We identify conditions for the output of GMM to be unique, and identify a general class of consistent and inconsistent breakings. We then show by theory and experiments that our algorithms run significantly faster than the classical Minorize-Maximization (MM) algorithm, while achieving competitive statistical efficiency.
This paper proposes a generalized method of moments 
      approach to rank aggregation, specifically by estimating the parameters of 
      a Plackett-Luce (PL) model from a sample of rankings. The proposed method 
      works by decomposing rankings into pairwise comparisons, which are then 
      used to build a transition matrix, the stationary distribution of which is 
      used to parameterize the PL model. The authors establish consistency 
      results for different ways of "breaking" the input rankings into pairwise 
      comparisons, and experimentally validate the efficiency of the approach on 
      two datasets. Overall, the paper is clearly written, and the 
      method seems sound. The "breaking" technique is both interesting and 
      intuitive. My two main concerns with this paper are the practical 
      applicability of the method, and the thoroughness of experimental 
      evaluation. In both the analysis and the experiments, the authors 
      focus on a small-m/large-n regime, where a large number of rankings are 
      given over a small set of items. While consistency is generally a 
      desirable property, I'm not convinced that it's the main quality of 
      interest for rank aggregation. Many of the practical applications 
      mentioned by the authors in the introduction (e.g., meta-search) are 
      large-m/small-n settings in which relatively few rankings are provided 
      over a large set of items. The authors do discuss the computational 
      complexity of inference, but there is no discussion or evaluation of 
      accuracy in this regime, and it's not clear how well the proposed method 
      would perform. The experiments on synthetic and real data do 
      illustrate qualitative differences between different breaking strategies, 
      both for speed and accuracy (RMSE and Kendall correlation). However, 
      neither metric seems specifically appropriate for top-k breakings (figure 
      4), as the scores may be polluted by errors low in the ranking which have 
      no qualitative effect in practice. It would be helpful to see at least one 
      position-dependent score here. Minor comments: Line 
      83: \gamma* is not used in the definition of Pr_PL. Should this be \gamma? 
      Line 95: should the norm ||a||_W be squared here? Is this intended 
      as a proper norm (i.e., W positive definite), or is it just meant as a 
      convenient notation? Is it necessary to introduce the W notation here 
      anyway, since it seems that the remainder of the paper sets W=I? 
      Line 102: GMM_g(D,W) is set-valued, should converge to the set 
      {\gamma*}, not the point \gamma*. Line 124: section 3 title 
      misspells "Plackett" Line 245, Eq. 2: should both the numerator 
      and denominator here be in terms of Pos(c, d)? Or Pos(c)? Line 
      377: broken reference in footnote 4