Unsupervised Rank Aggregation with Domain-Specific Expertise

1 Introduction

Consider the setting where judges are repeatedly asked to (partially) rank sets of objects, and assume that each judge tries to reproduce some true underlying ranking to the best of their ability. Rank aggregation aims to combine the rankings of such experts to produce a better joint ranking. Now, imagine that the judges' ability to generate rankings depends on the type of objects being ranked or the criteria they are asked to use while ranking. As a simple example, consider a group of people who are asked to rank a set of conference submissions written in English and another set written in French according to their relevance to the conference theme. One would expect that a bilingual expert in the field would produce reasonable rankings of both cases, while a judge who only speaks French and is unfamiliar with the conference topic may produce mediocre rankings (possibly, only using a set of keywords) for the French submissions and random rankings for the English set. We consider the problem of learning to aggregate these rankings by constituent judges with domain-specific expertise into a joint ranking.

The problem of aggregating rankings is ubiquitous in Information Retrieval (IR) and Natural Language Processing (NLP). In IR, for instance, meta-search aims to combine the outputs of multiple search engines to produce a better ranking. In machine translation (MT), aggregation of multiple systems built on different underlying principles has received considerable recent attention (e.g. [Rosti et al., 2007]). In many such applications, one would expect the expertise of the constituent components to depend on the input domain. In IR, the quality of rankings produced by search engines has been shown to be query type dependent (e.g. [Geng et al., 2008]): some may specialize on ranking product reviews while others on ranking scientific documents. In MT system aggregation, component systems may be trained on different corpora (e.g. multi-lingual Hansards, or technical manuals), and tend to be fragile when tested on data sampled from a different domain [Koehn and Schroeder, 2007]. Thus, the relative expertise of these systems depends on which distribution the test source language data is sampled from. Moreover, in these and many other aggregation examples, the input domain information in regards to the expertise of each judge is latent.

Supervised learning approaches to solving rank aggregation (e.g. [Liu et al., 2007]) are impractical for many applications as labeled ranking data is generally very expensive to obtain. In IR, for example, heuristics or indirect methods are often employed (e.g. [Shaw and Fox, 1994; Dwork et al., 2001; Joachims, 2002]) to produce a surrogate for true preference information. Needless to say, supervision for typed ranked data is even harder to obtain.

The principal contribution of this paper is a framework for learning to aggregate votes of constituent rankers with domain-specific expertise without supervision. Given only a set of constituent rankings, we learn an aggregation function that attempts to recreate the true ranking without labeled data. The intuition behind our approach is simple: rankers which are experts in a given domain are better at generating votes close to true rankings for that domain and thus will tend to agree with each other, whereas the non-experts will not. Given rankers' votes for a set of queries, we aim to discover patterns of rankers' agreement. Each distinct pattern corresponds to a specific (latent) domain, enabling us to deduce domain-specific expertise of each judge. The ability to identify expertise of a ranker for a specific query can potentially greatly improve accuracy of the model over simpler aggregation techniques. While our framework does not commit to any particular type of (partial) rankings, we show how to apply it to two kinds of rankings: permutations and top-k lists.

The remainder of the paper is organized as follows. Section 2 introduces relevant notation and reviews distancebased ranking models. Section 3 introduces our model for aggregating over rankers with domain-specific expertise and Section 4 derives an EM-based algorithm for learning model parameters, and describes methods to make the learning efficient. Section 5 applies the learning framework to two types of rankings: permutations (full rankings) and top-k lists. Finally, Section 6 discusses relevant work, and Section 7 concludes the work and gives ideas for future directions.

2 Distance-BasedModels

While there has been a significant research effort in the statistics community with regards to analyzing and modeling ranking data (e.g. [Marden, 1995]), we are specifically interested in distance-based models beginning with the Mallows model [Mallows, 1957].

2.1 Notation and Definitions

Let us first introduce the notation we will use throughout the paper. The models presented in this work do not commit to a particular type of (partial) ranking. Therefore, we will generally use the same notation for all (partial) ranking types, and the particular type we imply should be clear from context. However, since we apply the model to two particular types of rankings, permutations (full rankings) and top-k lists, let us start with the relevant definitions.

Permutations

Let {x1, x2, . . . , xn} be a set of objects to be ranked by a judge. A permutation π is a bijection from the set {1, 2, . . . , n} onto itself; we will denote by π(i) the rank assigned to object xi, and by π-1 (j) the index of the object assigned to rank j. Let us also define e to be the identity permutation (1, . . . , n). Finally, let us denote Sn to be the set of all n! permutations over n objects.

Let us define a distance between two permutations d : Sn × Sn → R and assume that, in addition to satisfying the usual metric properties, it is also right-invariant [Diaconis and Graham, 1977]. That is, we assume that the value of d(·, ·) does not depend on how the objects are indexed, a property natural to the applications we consider in this work. More specifically, if the objects are re-indexed by τ, the distance between two permutation over the objects does not change: d(π, σ) = d(πτ, στ) ∀π, σ, τ ∈ Sn, where πτ is defined by πτ(i) = π(τ(i)). Note that d(π, σ) = d(ππ-1 , σπ-1 ) = d(e, σπ-1 ). That is, the value of d does not change if we re-index the objects such that one of the permutations becomes e = (1, . . . , n) and the other ν = σπ-1 . Borrowing the notation from [Fligner and Verducci, 1986] we abbreviate d(e, ν) as D(ν). In the remainder of the paper, when we define ν as a random variable, we may treat D(ν) = D as a random variable as well: whether it is a distance function or a r.v. will be clear from the context.

Examples of common right-invariant distance functions over permutations include Kendall's tau distance 1 :

1 I(x) = 1 if x > 0, and 0 otherwise.

which can be also defined as the minimum number of adjacent transpositions required to turn π into σ, and the Spearman's footrule:

Top-k Lists

Top-k lists indicate preferences over different (possibly, overlapping) subsets of k ≤ n objects, where the elements not in the list are implicitly ranked below all of the list elements. They are used extensively in the IR community to represent the output of a retrieval system; a top-10 list, for instance, may represent the first page of a search engine output.

A number of distance measures over top-k lists have been proposed and studied (e.g. [Fagin et al., 2003]). Of particular relevance to us will be the generalization of the Kendall's tau distance (1) to top-k lists proposed in [Klementiev et al., 2008] which they defined as follows. First two top-k lists π and σ are augmented: items in σ which are not present in π are placed in the same position (k + 1) in π, and vice versa. The augmented Kendall's tau distance dA(π, σ) is then defined as the minimum number of adjacent transpositions to turn the augmented π into the augmented σ. They show that the distance is right-invariant.

2.2 Mallows Models

Distance-based models for ranking data were first introduced in [Mallows, 1957], and generate judge's rankings according to:

where θ ∈ R, θ ≤ 0 is the the dispersion parameter, the modal ranking σ ∈ Sn is the location parameter, and Z(θ, σ) = ∑π∈Sn exp(θ d(π, σ)) is a normalizing constant. The probability of ranking π decreases exponentially with distance from the mode σ. The distribution is uniform when θ = 0, and becomes sharper as θ grows more negative.

Let us note two properties of (3), which will be relevant later in the paper. Firstly, under the right invariance property of d(·, ·), the normalizing constant does not depend on σ, Z(θ, σ) = Z(θ) (see, e.g. [Lebanon and Lafferty, 2002]).

Secondly, [Fligner and Verducci, 1986] note that if the distance function can be expressed as D(π) = ∑mi=1 Vi(π), where random variables Vi(π) are independent (with π uniformly distributed), then the MLE of θ under (3), which is the solution to equation Eθ(D) = D, may be efficient to compute. [Klementiev et al., 2008] refer to such distance functions as decomposable.

[Mallows, 1957] first investigated the model with Kendall's and Spearman's metrics on fully ranked data, and the model was later generalized to other distance functions and for use with partially ranked data [Critchlow, 1985].

2.3 ExtendedMallows Models

Since the Mallows model was introduced, various extensions have been proposed in statistics and machine learning literature (e.g. [Fligner and Verducci, 1986; Murphy and Martin, 2003; Busse et al., 2007]). Of particular interest to us is the multiple input rankings scenario proposed by [Lebanon and Lafferty, 2002] in the context of supervised learning.

Assuming that a vector of votes σ = (σ1, . . . , σK) fromK individual judges is available, the generalized model assigns a probability to ranking π according to:

where σ ∈ S K n , θ = (θ1, . . . , θK) ∈ RK , θ ≤ 0, p(π) is a prior, and normalizing constant Z(θ,σ) = ∑π∈Sn p(π) exp(∑Ki=1 θi d(π, σi)). The free parameters θi represent the degree of expertise of the individual judges: the closer the value of θi to zero, the less the vote of the i-th judge affects the assignment of probability.

Under the right-invariance property assumption on d(·, ·), the model has the following associated generative story:

That is, π is first drawn from prior p(π), and the votes of the K individual judges are produced by drawing independently from K Mallows models p(σi|θi, π) with the same location parameter π.

[Klementiev et al., 2008] propose an ExpectationMaximization (EM) [Dempster et al., 1977] based algorithm for learning the parameters of the extended Mallows model from Q vectors of votes {σ(j) }Qj=1 . Their intuition is that better rankers tend to exhibit agreement more than poor ones (assumed not to collude), which was supported empirically.

In the meta-search setting, for example, the observed data is comprised of the rankings σ(j) produced by K search engines for each of the Q queries, and the goal is to infer the joint ranking π.

3 Distance-BasedModels with Domain Expertise

Up to this point, we have only considered type agnostic models. These models assume that the expertise of the constituent rankers do not depend on the input data domain (e.g. types of queries in the meta-search setting, or the distributions of the test sentences in the MT aggregation setting), or equivalently, that all input comes from the same domain. In the following discussion we will correspondingly refer to input data domains as types.

As we have argued, in practical applications, it is more natural to model the data generation process such that domainspecific expertise of the rankers is accounted for explicitly. We now proceed to the task we set out to investigate: the case of aggregating votes of rankers with domain-specific expertise. We propose a mixture of the extended distance-based models (4) as a means to formalize and model this setting.

3.1 Mixture Model

We begin by augmenting the generative story (5) to include the notion of types. First, a type t is selected from T types with probability αt. Then, the location parameter (true ranking) π is drawn uniformly, and the votes of individual experts are drawn independently from K Mallows models p(σi|θt,i, π) with the same location parameter π. That is,

The right-invariance property of the distance function can be used to derive the corresponding conditional model:

where σ = (σ1, . . . , σK) ∈ S K n , θ ∈ RT×K , θ ≤ 0, and normalizing constant Z(θ,σ) = ∑Tt=1 ∑π∈Sn αt exp(∑Ki=1 θt,i d(π, σi)).

The free model parameters are a T ×K matrix θ, where θt,i represent the degree of expertise of the judge i for type t, and T mixture weights α. Note that this model is more expressive than the type agnostic model which has a single free parameter θi to model the expertise of each judge.

4 Learning and Inference

We now derive an EM-based algorithm for learning the free model parameters α and θ, and propose methods to make both learning and inference efficient.

4.1 Learning

Let us denote the estimates of parameters in the previous EM iteration with α′ and θ′ . In our setting, the examples we observe are vectors of rankings {σ(j) }Qj=1 , where σ(j) i is the ranking produced by i-th ranker for example j. The unobserved data are the corresponding true rankings with the associated types: {(t(j) , π(j) )}Qj=1 .

In order to make the learning process more stable we use a symmetric Dirichlet prior Dir(β) on the topic distribution α. Now, following the generative story in Section 3.1 and taking into account the prior defined on α, we derive the M step (proofs are omitted due to space restrictions):

Proposition 1 The expected value of the complete data loglikelihood under (7) is maximized by α and θ such that:

Thus, on each iteration of EM, (8) is used to update α (T updates) and (9) are used to update θ parameters (T × K updates).

Evaluating (8), estimating the right-hand side of (9), and then solving the left hand side for θt,i directly are all computationally intractable. However, learning can be made efficient when particular properties of the distance function discussed in Section 4.1 are satisfied.

The ideas presented so far can be applied to any kind of (partial) rankings. However, in order to propose efficient alternatives to direct estimation of α and θ, we need to commit to specific ranking types. Let us consider the cases of combining permutations and combining top-k lists as two examples, and address the three problems individually.

Estimating the right-hand side of (9)

In order to estimate the right-hand side of (9) we need to obtain samples from the model (7). For high dimensional multimodal distributions such as (7), standard sampling methods (e.g. Metropolis-Hastings [Hastings, 1970]) do not converge in a reasonable amount of time. Annealing methods [Neal, 1996] are still computationally expensive, and additionally require careful tuning of free parameters (i.e. annealing schedule). Therefore, we use the fast approximate sampling algorithm described below.

We start by obtaining a sample from each mixture component t. This is done using the Metropolis-Hastings algorithm applied to the extended Mallows model (4). The chain is constructed as follows: denoting the most recent value sampled as τ(t), two indices i, j ∈ {1, . . . , n} are chosen at random and the objects τ -1 (t) (i) and τ -1 (t) (j) are transposed forming a new permutation ˜ τ(t). If a = p(˜ τ(t), t|σ, θ′ ,α′ )/p(τ(t), t|σ, θ′ ,α′ ) ≥ 1 the chain moves to ˜ τ(t). If a < 1, the chain moves to ˜ τ(t) with probability a; otherwise, it stays at τ(t).

Once the sampling is complete for each chain, we sample permutations from the obtained set of pertopic permutations (τ(1), τ(2), . . . , τ(T)) with probability ∝ α′t exp (∑Ki=1 θ′t,i d(τ(t), σi)). The underlying assumption for this approximate sampling algorithm is that the probability mass of a mixture component is proportional to the probability of a sample generated from this component. The sampling procedure is repeated for all Q examples, and the average per-type distance is used as the estimate of the right-hand side of (9).

This procedure is easily extended to top-k lists: when forming the next chain element ˜ τ(t), we may either transpose two elements of τ(t), or replace one of its elements with an element not in τ(t) (i.e. from the pool of all elements in the constituent rankings of the given example).

While convergence results have been presented in statistics literature (e.g. [Diaconis and Saloff-Coste, 1998]) for some distances when sampling from (3), no results are known for the extended models (4) and (7) we have considered in this work. However, we found experimentally that chains converge rapidly for the two settings we are considering. Moreover, as the chain proceeds, we only need to compute the incremental change in distance due to a single swap at each step, which results in substantial computational savings.

Estimating α

Following (8), we estimate the type mixture coefficients α as the proportions of the types in all of the Q sampled rankings (with the additional pseudocounts β).

Solving the left-hand side of (9) for θ

As we noted in Section 2.2, solving Eθ(D) = D under (3) for θ may be efficient for decomposable distance functions. Indeed, for (decomposable) Kendall's tau distance over permutations, Eθ(DK) is efficient to compute and is monotone decreasing, so line search for θ converges quickly [Fligner and Verducci, 1986]. An analogous result was derived by [Klementiev et al., 2008] for the augmented Kendall's tau over top-k lists (Section 2.1). Thus, requiring distance functions to satisfy the decomposability property may enable us to solve the left-hand side of (9) efficiently.

4.2 Inference

We use the sampling procedure described in Section 4.1 during inference to estimate the most likely permutation for a given set of votes.

5 Evaluation

In the absence of available labeled ranked data exhibiting domain variability, we construct our own data sets representative of a realistic application scenario. We evaluate the proposed framework on two types of rankings we have considered so far: permutations and top-k lists.

5.1 Aggregating Typed Permutations

We first consider the case of rank aggregation for typed permutations using Kendall's tau as the distance function in (7).

For this first set of experiments, we considered K = 10 judges, producing rankings over n = 30 objects for Q = 100 examples. Each example was associated with one of T = 5 types, according to α∗ = (0.4, 0.2, 0.2, 0.1, 0.1). Roughly half of the judges are chosen to be experts (i.e. produce good rankings) for each of the T types.

More precisely, the votes of individual judges were produced by sampling models (3), with the same location parameter σ∗ = e (an identity permutation over n = 30 objects). We chose their concentration parameters as follows: we first flip a coin to decide whether or not the i-th ranker is an expert for type t. If the ranker is an expert, its parameter θ∗ t,i is randomly chosen from a small interval close to -1, otherwise it is chosen to be around -0.05.

At the end of each EM iteration, we sampled the current model (7), and computed the Kendall's tau distance between the generated permutation π and the true permutation σ∗ for each of the Q examples, and report the performance in terms of the average distance.

In addition to the sampling procedure we proposed to estimate the right-hand side of (9), we also tried using the true permutation σ∗ along with the corresponding true type t∗ in place of the sampled values to see how well the learning procedure can do.

Figure 1 shows that our model significantly outperforms the type agnostic model proposed in [Klementiev et al., 2008] for this setting. While the type agnostic model (UnTyped Sampling) achieves an average distance of 34, our model (Typed Sampling) requires an average distance of 19, representing about 44% reduction in the number of adjacent transpositions at convergence. Moreover, the model converges quickly, and its performance approaches the case when true permutations and their corresponding types are known.

5.2 Aggregating Typed Top-KLists

We now consider the case of combining typed top-k lists using the augmented Kendall's tau distance (see Section 2.1) in (7). The setup and the data was produced similarly to permutations experiments in Section 2.1. However, when generating top-k, k = 30 objects were selected from a pool of n = 100.

We compare our top-k list instantiated model against the corresponding type agnostic model, reporting results in Figure 2 in terms of the average augmented Kendall's tau distance from the true top-k lists. Again, our framework significantly outperforms the type agnostic model, reducing the average augmented Kendall's tau distance to true lists by approximately 31, resulting in 47% reduction in the number of adjacent transpositions.

5.3 Discussion

In many practical applications, constituent rankers are likely to specialize in some input domains, while performing poorly in others. Both experiments demonstrate that the model we proposed can take advantage of the latent type information to learn to aggregate the votes of such rankers effectively. It produces better joint rankings than the type agnostic model of [Klementiev et al., 2008].

The EM-based learning algorithm we propose is robust, converging quickly with just Q = 100 examples across multiple runs. It is worth emphasizing that the additional expressivity of the model we propose does not prevent it from learning from a small number of examples successfully. Additionally, the computational requirements scale linearly with the number of topics.

6 Relevant Work

Modeling ranked data is an extensively studied problem in statistics, information retrieval, and machine learning literature. Distance-based models with Kendall's and Spearman's metrics for fully ranked data were introduced and investigated in [Mallows, 1957]. A number of new metrics for partial rankings were since introduced and analyzed (e.g. [Critchlow, 1985; Estivill-Castro et al., 1993; Fagin et al., 2003]), and various extensions to the model itself have been proposed (e.g. [Fligner and Verducci, 1986]); see [Marden, 1995] for an excellent overview. [Murphy and Martin, 2003] used mixtures of Mallows models (3) to analyze ranking data from heterogeneous populations, and [Busse et al., 2007] propose a method for clustering such data. A large body of work also exists on mixture models (or LCA, [Lazarsfeld and Henry, 1968]).

While a number of heuristic [Shaw and Fox, 1994; Dwork et al., 2001] and supervised learning approaches [Liu et al., 2007] exist for rank aggregation, few learn to combine rankings without supervision.

Most directly related to our work is the generalization to multiple input rankings proposed and studied in [Lebanon and Lafferty, 2002]; [Klementiev et al., 2008] derived an EMbased algorithm to estimate its parameters. We extend their model to include the notion of domain expertise.

7 Conclusions

In this work, we propose an unsupervised learning framework for rank aggregation over votes of rankers with domainspecific expertise. We introduce a model, derive an EM-based algorithm to estimate its parameters, and propose methods to make learning efficient. Finally, we evaluate the framework on combining full rankings and on combining top-k lists, and demonstrate that it significantly and robustly outperforms the domain agnostic model proposed in [Klementiev et al., 2008]. This approach is potentially applicable to many problems in Information Retrieval and Natural Language Processing, e.g. meta-search or aggregation of machine translation systems' output, where domain variability presents a major challenge [Koehn and Schroeder, 2007; Geng et al., 2008]. Developing unsupervised techniques is particularly important as annotated data is very difficult to obtain for ranking problems, especially for multiple domains.

Acknowledgments

We thank Ming-Wei Chang, Vivek Srikumar, and the anonymous reviewers for their valuable suggestions. This work is supported by NSF grant ITR IIS-0428472, DARPA funding under the Bootstrap Learning Program, Swiss NSF scholarship PBGE22-119276, and by MIAS, a DHS-IDS Center for Multimodal Information Access and Synthesis at UIUC.