Fast and Accurate Inference of Plackett-Luce Models
We show that the maximum-likelihood (ML) estimate of models derived from Luce's choice axiom (e.g., the Plackett-Luce model) can be expressed as the stationary distribution of a Markov chain. This conveys insight into several recently proposed spectral inference algorithms. We take advantage of this perspective and formulate a new spectral algorithm that is significantly more accurate than previous ones for the Plackett-Luce model. With a simple adaptation, this algorithm can be used iteratively, producing a sequence of estimates that converges to the ML estimate. The ML version runs faster than competing approaches on a benchmark of five datasets. Our algorithms are easy to implement, making them relevant for practitioners at large.
Via a connection to Markov Chains, the paper exploits spectral techniques for learning Placket-Luce models efficiently and with lower error than existing methods.The summary mostly says it all.To the best of my knowledge the algorithmic contributions of the paper are novel as well as the theorem proving convergence.The results are also practically useful when compared to existing work and the paper is well-situated w.r.t. general related work and trends.Perhaps the icing on the take then is that the algorithm is straightforward to implement.For this reason, I believe that other researchers and practitioners will find strong reasons to use this work and build on it.I have two (minor) questions:(1) One question relates to the error metric above Eq (9): I don't fully understand the definition of the theta vector... it appears that a scalar is assigned to a vector... I am intepreting the notation as the assignment to the i'th element of theta.What is most confusing though is the purpose of t... why is it necessary to "center" the theta_i purpose of error comparison?(2) The authors state in Figure 2 that I-LSR is robust to changes in graph structure.While I agree that the impact of graph structure is more prominent for MM, I-LSR's RMSE is not immune to changes in graph structure... am I missing something?And one simple comment:Because the implementation of the stationary distribution computation is critical to the efficiency of Algorithms 1 and 2, some discussion of this should ideally be moved from the Appendix and into the main body of the paper (perhaps as a footnote to save space).