Consensus ranking under the exponential model

Marina Meila; Kapil Phadnis; Arthur Patterson; Jeff A. Bilmes

Source-linked AI summary

Consensus ranking under the exponential model

Marina Meila, Kapil Phadnis, Arthur Patterson, Jeff A. Bilmes

arXiv:1206.5265v1Jun 20, 2012cs.LGcs.AIstat.ML

TL;DR

Consensus ranking asks for an order that best agrees with observed rankings, but finding it is NP-hard. The paper searches over partial rankings to estimate the central ranking and model parameters; SearchPi outperforms the other contenders when tractable.

Problem
Finding a consensus ranking that best agrees with observed rankings is NP-hard.
Source: §1 · p. 1, §3.2 · p. 3
Method
The paper uses search over partial orderings to estimate the central ranking, with SearchPi also extended to estimate model parameters.
Source: §4.1 · p. 4
Results
SearchPi outperforms the other contenders when it is tractable.
Source: §8 · p. 9
Takeaways & Limitations
Although consensus ranking is theoretically NP-hard, approximately minimizing its cost is practically easy in the reported settings.
Source: §8 · p. 9
BF-CSS is not presented as the ultimate approximate-search heuristic, and the FV and CSS algorithms could be improved.
Source: Experiments with almost uniform… · pp. 8–9

Abstract

from arXiv · show

We analyze the generalized Mallows model, a popular exponential model over rankings. Estimating the central (or consensus) ranking from data is NP-hard. We obtain the following new results: (1) We show that search methods can estimate both the central ranking pi0 and the model parameters theta exactly. The search is n! in the worst case, but is tractable when the true distribution is concentrated around its mode; (2) We show that the generalized Mallows model is jointly exponential in (pi0; theta), and introduce the conjugate prior for this model class; (3) The sufficient statistics are the pairwise marginal probabilities that item i is preferred to item j. Preliminary experiments confirm the theoretical predictions and compare the new algorithm and existing heuristics.

1 Introduction

Rank aggregation seeks a single order that best agrees with a set of rankings. The paper studies statistical estimation of that consensus using generalized Kendall distances.

1 Introduction

Rank aggregation finds a single ranking that best agrees with the rankings of judges or voters.It can also be viewed as a voting rule that selects a consensus order over candidates.Source: §1 · p. 1
The Kendall distance counts pairwise disagreements between two rankings.It compares which item precedes the other in each permutation.Source: §1 · p. 1
The paper studies estimating a consensus ranking under probabilistic models built from generalized Kendall distances.For a fixed central ranking, maximum-likelihood estimation is equivalent to finding the consensus ranking.Source: §1 · p. 1

2 Background: Generalized Mallows models

The generalized Mallows framework represents rankings through independent coordinates and assigns them probabilities using a parameterized generalized Kendall distance. Its parameters control both the weighting of ranking positions and the distribution’s concentration around its mode.

2 Background: Generalized Mallows models

A permutation can be specified by n−1 coordinates V_j, which can be chosen independently; V_j counts later-ranked elements placed before position j.Under a uniformly sampled permutation, the V_j values are uniformly distributed.Source: §2 · pp. 1–2

2.1 Generalized Kendall distance

The generalized Kendall distance weights the coordinates V_j by parameters θ_j, allowing ranking positions to receive different importance.The resulting distance may be asymmetric unless all θ_j are equal; the parameters can emphasize high-ranked items.Source: §2.1 · p. 2

2.2 Generalized Mallows models

The generalized Mallows model uses the parameterized divergence to define an exponential distribution over rankings.For θ_j ≥ 0, its mode is the central permutation; larger parameter values concentrate the distribution more strongly around that mode, while θ ≡ 0 gives the uniform distribution.Source: §2.2 · p. 2

3 The ML estimation problem

With a fixed central ranking, the model’s likelihood separates across parameters, enabling unique numerical estimates. Estimating the central ranking is the NP-hard consensus-ranking problem, for which the paper uses pairwise statistics and examines existing heuristics.

3.1 Parameter estimation.

For a fixed central ranking, the likelihood decomposes into terms depending on individual θ_j, and each parameter has a unique estimate obtainable numerically.The log-likelihood is log-concave in θ; the estimating equation generally has no closed-form solution.Source: §3.1 · pp. 2–3

3.2 The centroid estimation problem

The matrix Q summarizes the data through pairwise probabilities that one item precedes another.Its entries are rational for finite samples.Source: §3.2 · p. 3
The FV heuristic sorts items by their average pairwise precedence counts, then evaluates nearby rankings using estimated parameters and data likelihood.The starting permutation is formed by sorting the summed Q values in increasing order.Source: §3.2 · p. 3
Under the Mallows model (θ1 = θ2 = … = θn−1 ≥ 0), finding the consensus ranking is NP-hard; a randomized algorithm achieves a factor 11/7 approximation when minimizing the right-hand side of (12).Source: §3.2 · p. 3
The paper motivates exploiting distributional concentration because consensus estimation intuitively becomes easier near the mode, while a uniform distribution leaves every permutation equally qualified.Earlier approaches cited in the passage do not tie concentration to the problem’s hardness.Source: §3.2 · p. 3

4 Exact ML estimation for π0

SearchPi formulates central-ranking estimation as a search over partial orderings, with costs and lower bounds guiding expansion. The method extends to jointly estimating the central ranking and model parameters.

4 Exact ML estimation for π0

The data matrix Q contains information needed to find the likelihood-maximizing π0, including the pairwise information used to choose the first item.The passage describes extending this choice inductively to later positions.Source: §4.1 · p. 3
An exhaustive search over the permutation tree can identify the central ranking maximizing likelihood; each complete path represents a permutation.A node represents a partial ordering and the set of permutations sharing that prefix.Source: §4.1 · pp. 3–4
SearchPi stores the accumulated cost and a lower bound at each node, allowing optimal search to finish before the entire tree is expanded.The lower bound combines the cost so far with a bound on the remaining cost; the node cost is computed recursively.Source: §4.1 · p. 4
The search can jointly estimate π0 and θ by computing parameter estimates at each node from the corresponding sufficient statistics.Each θ_j estimate depends on its corresponding V_j statistic and can be computed by solving the parameter equation.Source: §4.2 · p. 4

5 Computational aspects

The search uses admissible lower bounds to prune a permutation tree, and its node count depends on the quality of those bounds. It has n! worst-case time but can explore far fewer nodes when the distribution is concentrated around its mode.

5.1 Admissible heuristics

An admissible heuristic must be easy to compute and lower-bound the remaining cost; unknown θ additionally requires lower bounds on future parameters.With known θ, bounds on future V values can be built from child values and column sums of submatrices of Q.Source: §5.1 · pp. 4–5
When θ is constant, sorting off-diagonal Q values and summing the required smallest values gives a level-dependent lower bound computable before search.This bound is described for consensus ranking, where θj ≡ 1.Source: §5.1 · p. 5

5.2 Number of node expansions

The search takes n! time in the worst case, but for some parameter values it explores only the nodes visited by greedy search.Large θ values correspond to distributions that decay quickly away from π0 and can make the search explore few nodes.Source: §5.2 · p. 5
Near-uniform or multimodal data can make the search intractable; in that setting, inadmissible heuristics such as beam search are a practical optimization avenue.The algorithm can also be stopped early, returning the best solution found so far.Source: §5.2 · p. 5

5.3 Number of operations per node.

Reusing previously computed sibling-node values can reduce node computation from O(n−j) operations to constant time, versus O(n^3) for a vertical path without that organization.Retaining needed V tables costs n−j storage per node; the implementation uses a binomial heap with logarithmic access time.Source: §5.3 · pp. 5–6

6 Identifiability and conjugate prior

The pairwise-preference matrix Q supplies sufficient statistics for the model, and the paper establishes properties of its identifiability. It also gives a conjugate prior for the joint exponential family in (π0, θ), with a boundary on what the prior can express.

6.1 Identifiability

Q is the sufficient-statistic matrix, and its admissible values form a convex polytope whose n! extreme points correspond to rankings.Any Q in the polytope can be approximated arbitrarily closely by sufficient statistics from finite data sets with large enough N.Source: §6.1 · p. 6
For any Q, some central permutation π0 has a non-negative θ estimate; nearly every Q determines a unique maximum-likelihood pair, but the converse does not hold.The uniqueness statement excludes Q matrices with ties in π0.Source: §6.1 · p. 6, §6.2 · p. 6

6.2 The conjugate prior

Finite sufficient statistics make the model an exponential family jointly in (θ, π0), and the paper provides a conjugate prior for those parameters.The prior is closed under sampling, but its normalization constant has no known closed-form formula.Source: §6.2 · p. 6
When Γ is an expectation matrix under the model, ν and Γ correspond to ν samples from a distribution centered at π* with spread θ*; other Γ values correspond to samples from outside the model class.Source: §6.2 · p. 7
Using Γ0, with 0.5 in every off-diagonal entry, smooths the parameters while remaining non-informative about the central permutation; other Γ values inform both.The paper says the conjugate-prior framework cannot express ignorance about π0 while expressing knowledge about θ.Source: §6.2 · p. 7

7 Experiments

The experiments compare exact and approximate search with existing consensus-ranking heuristics in concentrated and nearly uniform settings, plus tests on random Q matrices. Exact search and the five-minute BF-CSS continuation perform well in different settings, while the heuristic comparison depends on the distribution.

7 Experiments

The experiments also consider random Q matrices with independent entries, and treat consensus estimation as the core difficulty because estimating θ adds only a small constant time per search step.The authors identify large θ_j values at late ranking stages as an exception to that focus, describing this setting as rather unrealistic in practice.Source: §7 · p. 7, Experiments with almost uniform… · p. 8

Experiments with concentrated distributions

With N = 5000 and θ ≡ 1, 1.5, 2, or 3, all heuristics returned the optimal permutation; Figure 1a tracks BF nodes expanded across n and θ.Each setting was replicated 10 times.Source: Experiments with concentrated… · p. 7, Figure 1 · p. 7
With θ = 0.3 (only moderately concentrated), experiments at n = 10, …, 50 were replicated 100 times; for n up to 40, all heuristics returned the true permutation π0.The optimal permutation was not known except for n ≤ 15; the passage says large N makes it highly probable that the optimum coincides with the true π0.Source: Experiments with concentrated… · p. 8

Experiments with almost uniform distributions

In the almost-uniform comparison, greedy CSS was consistently best among the heuristics, while its advantage over ACN increased with n; true π0 was never optimal and FV did better but still lost.The shrinking cost range at larger n reflects Q values near 0.5.Source: Experiments with almost uniform… · p. 8, Figure 2 · p. 8
Across the experiments, suboptimal BF-CSS outperformed all other algorithms in a large number of cases and improved on closely related CSS greedy; optimal BF was included only for n = 8, 10.Costs are plotted as fractions of BF-CSS cost. BF-CSS runs SearchPi for five minutes, then continues with greedy search from the largest level attained.Source: §7 · p. 7, Experiments with almost uniform… · p. 8
The authors present BF-CSS as evidence that search trees can improve cost, not as the ultimate approximate search; FV and CSS also have proposed improvements.They mention beam search, FV local search, and CSS strongly connected components as possible improvements.Source: Experiments with almost uniform… · pp. 8–9
On random Q matrices, exact BF improved on all heuristics for small n, while BF-CSS improved on CSS by a few percent for larger n.Figure 1b reports costs as fractions of BF-CSS cost; the experiments were replicated 10 times.Source: Figure 1 · p. 7, Experiments with almost uniform… · p. 8

8 Related work and Discussion

The discussion positions SearchPi against earlier consensus-ranking and generalized Mallows work, highlighting its optimality, practical trade-offs, and potential extensions. It distinguishes the difficulty of finding the best permutation from the relative ease of approximately minimizing cost.

8 Related work and Discussion

Earlier generalized Mallows work treated the model as exponential in θ alone; its prior is not conjugate when π0 and θ are modeled jointly.The cited work's posterior normalization is not computable in closed form, with similarities to the normalization constant for the joint model.Source: §8 · p. 9
Earlier consensus-ranking procedures used greedy, branch-and-bound, and linear-programming approaches, and reported shorter compute times as concentration increased.The discussion names and for these procedures.Source: §8 · p. 9
SearchPi is optimal but by far the slowest; when tractable, it outperforms other contenders at finding the best permutation.The discussion distinguishes exact optimization from approximate cost minimization, for which heuristic differences can be minute.Source: §8 · p. 9
Finding the individual permutation that achieves the best consensus is hard, whereas approximately minimizing the cost is practically easy.In the combinatorial regime, cost differences are described as minute enough that almost any heuristic, even no optimization, can be acceptable.Source: §8 · p. 9
The Greedy-Order algorithm is the greedy counterpart of SearchPi, and CSS results for larger n suggest adding search may be worthwhile.The authors report this correspondence without presenting its proof in the passage.Source: §8 · p. 9
The authors expect few unimodal distributions in real ranking data and plan to pursue parametric and nonparametric mixture estimation.Mixture estimation is described as a future, more ambitious goal.Source: §8 · p. 9