Recursive Inversion Models for Permutations
We develop a new exponential family probabilistic model for permutations that can capture hierarchical structure and that has the Mallows and generalized Mallows models as subclasses. We describe how to do parameter estimation and propose an approach to structure search for this class of models. We provide experimental evidence that this added flexibility both improves predictive performance and enables a deeper understanding of collections of permutations.
Mallows models are a classically studied class of distributions overpermutations that can be viewed as a sequential model in which itemsare inserted one by one into a ranking.  This paper proposes an interestinghierarchical generalization of Mallows models in which groups of itemsare sequentially ``merged'' together (as they would be in mergesort).The model can also be viewed as a special case of a recently proposedclass of ``riffle independent'' models by Huang/Guestrin, but witha more tractable number of parameters in general and better computationalproperties.There are several nice contributions in this paper, including a simpleand elegant characterization of identifiability of the structure, as well asan interesting structure estimation algorithmbased on the inside-outside parsing algorithm for stochastic context freegrammars.The authors also discuss a few results on Sushi and Irish election datasetswhich seem promising.  I think that the tree visualizations of the distributionsare particularly intuitive, and should be an easy way to do aa preliminary analysis of any new ranking dataset.I would have been interested in the synthetic data experiments too, but these did not seem discussed.Though now there may be a lot of new space for the authors to discuss these (see below).It is interesting that the authors were able to reproduce the clusters that were found inthe Huang/Guestrin analysis --- which suggests a much simpler form of interaction wassufficient to capture most of the variation.  I would love to see a discussion ofwhat cannot be captured well by the proposed RIM model.Overall, the paper is well written, highly technical, and treatsan interesting class of models that should have broad applicationin ranking.   Given the structure of the model, this paper should alsolead to a number of easy extensions including mixtures models andlearning with partially ranked data (in the style of the Lu/Boutilier,Huang et al, or Lebanon/Mao papers).I heartily recommend acceptance to NIPS.some small errors:grep for: paramter, matricies, ``If if'', appraoch, interpretabtionThe algorithm for SASEARCH seems to appear twice in the paper.The authors could get significantly more space by deleting one :)