Mallows Models for Top-k Lists
The classic Mallows model is a widely-used tool to realize distributions on permutations. Motivated by common practical situations, in this paper, we generalize Mallows to model distributions on top-k lists by using a suitable distance measure between top-k lists. Unlike many earlier works, our model is both analytically tractable and computationally efficient. We demonstrate this by studying two basic problems in this model, namely, sampling and reconstruction, from both algorithmic and experimental points of view.
The authors consider the sample generation problem, center (location permutation) construction, and learning mixture model parameters for Mallows models with a top-k distance function. While most proposals for top-k lists are not invariant to tail (i.e., n-k) ordering, require generating the entire permutation, and/or analyze this from the repeated insertion model (RIM) perspective, this work defines a top-k distance function (ostensibly the distance function presented in [Klementiev, Roth & Small; ICML08] from [Fagin, et al].) and analyze the resulting top-k Mallows model in depth. For generation, exact sampling is O(k^2 4^k _ k^2 log n) and an approximate Markov chain sampler is O(k^5 log k) — which is important as even though computationally intensive, does not include n as a term, which is crucial when k is generally in the 10s and n can be in the millions. Center permutation construction and learning mixtures are also computationally efficient with provable guarantees. The Markov chain based approach for generation is used to generate synthetic data, which is then used for center permutation (re)construction, which is contrasted with Borda count and a second simple baseline — showing greater likelihood of returning the center. Finally, they consider a dataset of top-10 movie lists from the Criterion collection and return the center permutation.   In summary, the problem studied in this paper is important and several theoretical findings are explained — thus, I believe it is likely that it will have some impact in the ‘rank aggregation’ community. However, the presentation and general writing is lacking, even if I think this is partially an effect of it really being a longer theoretical contribution that is compressed into conference format. Secondly, the experiments are underwhelming — the synthetic experiments perform exactly as expected and the Criterion dataset experiment doesn’t provide any meaningful evidence that this is useful. Given that there are multiple papers in this vein that have compelling experiments, a stronger paper would have empirical comparison (even possibly in terms of runtime in addition to performance) that contrasts this with the proposed method.  Below is the paper evaluated with respect to the requested dimensions:  [Quality]: The theoretical contribution is through and relatively compelling. By defining a different distance function, the authors provide a clever method for analysis that emits useful results and may be utilized by others for other potential structure aggregations. For example, with a suitable distance function for sequences, trees, and other structures, this is a more useful analytical framework than a RIM-style analysis. Conversely, the empirical evaluation is relatively weak. While this isn’t really the point of the paper, a stronger empirical analysis is possible and would make for a much more compelling paper (i.e., some of the examples given in the introduction). As the Criterion collection is mostly masterpieces, the resulting center permutation says almost nothing.  [Clarity]: The paper is relatively clear for those who have worked in this area, but is very dense for more casual readers. For example, the ‘p-parameterized’ discussion in lines 66-70 doesn’t make intuitive sense despite them providing an example. It isn’t until one draws a picture based on line 128-134 that the example even makes sense. Secondly, while space is at a premium, the paper is largely unreadable past certain points without referring to the appendices. It would be nice if some sketches or intuitive explanation for the general analysis method could be presented. Finally, there is a general sloppiness to the paper (that could be fixed for a camera-ready).  Line 4: work -> works Line 23: mode -> model Line 32: top -> top-k (twice) Line 51: [same] Line 182: section -> section, (comma) Line 284: top—k -> top-k (There are more, but this is just what I circled in the first reading)  The paper can be tightened in some sections (i.e., motivation) to given intuition and improve experiments and experiment discussion. It also doesn’t help that the experiment figures are essentially unreadable without zooming in on the PDF file.  [Originality]: People have clearly been thinking about top-k lists and (unless I am misunderstanding), this is the distance function from [KRS08], even if they do not analyze in nearly the same depth — as this wasn’t the point of that paper. Thus, the strength of this paper is in the execution of solving a ‘sort of known’ difficult open problem as opposed to being particularly original.  [Significance]: As stated above, the theoretical results are reasonably compelling and the proof methods have potential to inspire other work. Thus, while potentially a bit esoteric, it has the potential to be an influential work. I enjoyed reading the paper and it gave me some ideas on how to analyze some of the problems I have been thinking about related to these problems. Conversely, without stronger empirical evidence, they are likely to reach a smaller audience.   Overall, nice results -- but the paper needs work in general. Thus, I am inclined to 'weak reject' in its current form.  Comments after author feedback: After reading the other reviews and particularly the rebuttal (and paper again), I am much more inclined to accept. This is an important problem with interesting results. I would still encourage the authors to tighten up the writing to make it more approachable (even if it is essentially a math paper).