# Multivariate Spearman’s rho for aggregating ranks using copulas

Justin<EMAIL_ADDRESS>
The Department of Computing and Information Systems, The University of
Melbourne, Australia Cheng Soon<EMAIL_ADDRESS>
Data61, CSIRO, Australia
Research School of Computer Science, the Australian National University
Department of Electrical and Electronic Engineering, The University of
Melbourne, Australia

###### Abstract

We study the problem of rank aggregation: given a set of ranked lists, we want
to form a consensus ranking. Furthermore, we consider the case of extreme
lists: i.e., only the rank of the best or worst elements are known. We impute
missing ranks and generalise Spearman’s to extreme ranks. Our main
contribution is the derivation of a non-parametric estimator for rank
aggregation based on multivariate extensions of Spearman’s , which measures
correlation between a set of ranked lists. Multivariate Spearman’s is defined
using copulas, and we show that the geometric mean of normalised ranks
maximises multivariate correlation. Motivated by this, we propose a weighted
geometric mean approach for learning to rank which has a closed form least
squares solution. When only the best (top-k) or worst (bottom-k) elements of a
ranked list are known, we impute the missing ranks by the average value,
allowing us to apply Spearman’s . We discuss an optimistic and pessimistic
imputation of missing values which respectively maximise and minimise
correlation, and show its effect on aggregating university rankings. Finally,
we demonstrate good performance on the rank aggregation benchmarks MQ2007 and
MQ2008.

##  1 Introduction

Ranking is a central task in many applications such as information retrieval,
recommender systems and bioinformatics. It may also be a subtask of other
learning problems such as feature selection, where features are scored
according to their predictiveness, and then the most significant ones are
selected. One major advantage of ranks over scores is that the resulting
predicted ranks are automatically normalised and hence can be used to combine
diverse sources of information. However, unlike many other supervised learning
problems, the problem of learning to rank (Lebanon and Mao, 2008; Liu, 2011)
does not have the simple one example one label paradigm. This has led to many
formulations of learning tasks, depending on what label information is
available, including pairwise ranking, listwise ranking and rank aggregation.

This paper considers a novel formulation of rank aggregation based on
multivariate extensions to Spearman’s . For a set of $n$ objects from the
domain $\Omega$, we are given a set of $d$ experts that rank these objects
providing rankings $R_{1},\ldots,R_{d}$. Each rank is a permutation of the $n$
objects, and can be represented as a vector of unique integers from 1 to $n$.
The problem of rank aggregation is to construct a new vector $R$ that is most
similar to the set of $d$ ranks provided by the experts. In this paper we use
Spearman’s correlation , a widely used correlation measure for ranks Spearman
(1904). Instead of decomposing the association into a combination of pairwise
similarities, $\rho(R,R_{1}),\rho(R,R_{2}),\ldots,\rho(R,R_{d})$, we directly
maximise the multivariate correlation

$R^{*}=\arg\max_{R}\rho(R,R_{1},R_{2},\ldots,R_{d}).$

Measures of association such as Spearman’s $\rho$ capture the concordance
between random variables (Nelsen, 2006). Informally, random variables are
concordant if large values of one tend to be associated with large values of
the other. Let $(x_{i},y_{i})$ and $(x_{j},y_{j})$ be two observations of a
pair of continuous random variables. We say that $(x_{i},y_{i})$ and
$(x_{j},y_{j})$ are _concordant_ if $x_{i}<x_{j}$ and $y_{i}<y_{j}$ or if
$x_{i}>x_{j}$ and $y_{i}>y_{j}$. If the inequalities disagree, we say that the
samples are _discordant_. The concept of concordance captures only the order
of the random variables, and is invariant to their values, and therefore is
ideal for analysing ranks. As will be described in section 3.3, Spearman’s is
based on the difference between the concordance and discordance of the
samples.

In short, Spearman’s correlation can be defined as the concordance $Q$ between
the copula $C$ corresponding to the data and the independent copula $\pi$

$\rho\propto Q(C,\pi).$

We review the concept of copulas in section 2 and derive our generalisation of
concordance in section 3. While the mathematical machinery to derive our
proposed algorithm relies on constructions which may not be familiar to some
machine learners, the resulting algorithm for rank aggregation is
straightforward. We solve a least squares problem for $n$ items,

$\min_{\omega}\sum_{x=1}^{n}{\left(l(x)-\sum_{j=1}^{d}\omega_{d}r_{d}(x)\right)}^{2},$

where we minimise the weights $\omega_{1},\dots,\omega_{d}$ corresponding to
the $d$ experts. It turns out that the appropriate transformation to learn
weights between experts is to use logarithmic scaled ranks. In the above
equation, $l(x)$ and $r(x)$ denote the logarithm of the labels and individual
expert ranks respectively, with all ranks normalised uniformly to the interval
$(0,1)$. Since it is a least squares problem, there is a closed form solution
for the optimal weights. This is in contrast to previous approaches to rank
aggregation which involve complex optimisation methods or sampling.

###  1.1 Our contributions

In the rest of this paper we will theoretically justify why the above least
squares problem provides a meaningful way to weight experts. We show that the
geometric mean of a set of normalised ranks maximises multivariate Spearman’s
. This motivates our method which finds a setting of weights that maximise
multivariate Spearman’s for a specific target (supervised rank aggregation).

As previously mentioned, in many applications of rank aggregation, only
extreme ranks are available, whereas the standard definitions of Spearman’s
require full ranks. For practical problems, the expert may only rank the most
liked (top-$k$) or most disliked (bottom-$k$) objects where $k$ can be
different for each expert. We propose a method for estimating Spearman’s for
extreme ranks by imputing the remaining ranks. We describe this method and
show that it is an unbiased estimator in section 4.

This results in a non-parametric approach for rank aggregation that learns the
weights of experts by solving a least squares problem. The weights in this
case model dependencies between the rankings, i.e., the rankings are not
independent. This is different to much prior work (see section 1.3) in that we
explicitly learn the dependencies between experts simultaneously and not in a
pairwise fashion. Our method thus offers significant computational benefits,
modelling flexibility in the presence of dependencies between experts, and
also interpretability due to the simplicity of the model. In section 6 we
describe our empirical results for rank aggregation and show that our simple
algorithm performs better than current state of the art results.

###  1.2 Multiple representations of ranks

There are a wide range of applications which benefit from rank analysis,
resulting in various equivalent ways to represent ranks and orderings. The
basic representation often used in introductory texts is to provide the list
of objects, for example [a, b, c, d, e, f], denoting the fact that a is the
most highly ranked object and f is the lowest ranked. It is often more
convenient to numerically represent the rank for computational purposes, that
is to keep a list of integers $1,\dots,n$ corresponding to the rank of a
particular object. For the example above, by maintaining the set of objects as
is, the ranks are then $[1,2,3,4,5,6]$. It turns out for empirical copula
modeling, it is important that the numerical values are in the interval
$(0,1)$, and therefore we normalise the numerical representation by $n+1$,
that is
$[\frac{1}{7},\frac{2}{7},\frac{3}{7},\frac{4}{7},\frac{5}{7},\frac{6}{7}]$.
However, note that the numerical representation is actually dependent on the
fact that we have maintained the set of objects in a particular fashion. In
fact by the above numerical list, we are saying that object a has rank
$\frac{1}{7}$, and object f has rank $\frac{6}{7}$. In other words, we are
defining a permutation mapping $R:\Omega\to(0,1)$ from the space of objects
$\Omega$ to the interval $(0,1)$.

###  1.3 Related Work

There are two related rank aggregation tasks: score based rank aggregation and
order based rank aggregation. For score based rank aggregation objects are
associated with scores, while for order based rank aggregation only the
relative order of objects are available. There has been recent work on
combining both scores and ranks (Sculley, 2010; Iyer and Bilmes, 2013). We
consider the learning task referred to as the listwise approach in Liu (2011),
where the input is a set of ranked lists of documents from multiple experts,
and the learner has to predict the final ranks. Numerous proposals for solving
the problem of combining multiple lists into a single list are surveyed in Liu
(2011). Niu et al. (2012) has focused on learning a good ranking from given
features. A good review of probability and statistics applied to permutations
is Diaconis (1988).

Spearman’s is a natural measure of similarity for distributions of
permutations (Mallows, 1957; Fligner and Verducci, 1986). Interestingly, there
has not been much work using Spearman’s for dealing with ranked data, but
instead the focus has been on Kendall’s . One difficulty of inference with the
Mallows model (Mallows, 1957) for Spearman’s is that it involves estimating
the permanent of a matrix. Our model is derived from the copula form of
Spearman’s and allows a simple formulation for aggregation that does not
require any computationally complex operations, thus providing a significant
computational advantage.

Other previous approaches (Klementiev et al., 2008; Iyer and Bilmes, 2012) to
rank aggregation considers pairwise comparisons between ranked lists. In
contrast, our approach does not consider pairwise combinations and operates
over all lists. We prove a result saying that the geometric mean of normalised
ranks maximise Spearman’s (theorem 17), which is similar in spirit to the
result in Iyer and Bilmes (2012), which shows that for Lovasz–Bregman
divergences the best aggregator is the arithmetic mean. This provides a
computational advantage over pairwise methods as the number of lists grows.

Our work builds heavily on copula theory, and we use results from Nelsen
(2006). Brief introductions to copulas can be found in Trivedi and Zimmer
(2005); Genest and Favre (2007); Elidan (2013). Further details on copula
modeling are available in a recent book (Joe, 2014). Many of these results are
presented for bivariate copulas only. There are fewer results on multivariate
copulas (Joe, 1990; Nelsen, 1996) and their relation to Spearman’s (Úbeda
Flores, 2005; Schmid et al., 2010) which we shall discuss later in this paper.

Finally, other well known measures of bivariate dependence have forms under
the copula framework and have multivariate extensions. In particular,
multivariate extensions of Kendall’s have been proposed
(joe_multivariate_1990). It is possible investigations into these copula
formulations results in other efficient aggregation methods with different
tradeoffs, however in this work we focus on Spearman’s .

The work on partial ranks goes back to at least Critchlow (1985), who
describes the rank aggregation task in terms of distances between rankings. We
have applied the results of this paper to rank aggregation (macintyre14assdrg)
and stability estimation (bedo14stabgb) in the domain of life sciences.

##  2 Copulas

Copulas are functions from the unit hypercube to the unit interval (Elidan,
2013). In this section we briefly review the bivariate setting, in preparation
for the multivariate setting in the next section. The expert reader may skip
directly to section 3 to see the definition of multivariate Spearman’s in
terms of the multivariate copula.

###  2.1 Definition of Copulas

Intuitively, for continuous random variables copulas model the dependence
component of a multivariate distribution after discounting for univariate
marginal effects. We let $\mathbb{R}$ denote the ordinary real line
$(-\infty,\infty)$, and $\overline{\mathbb{R}}$ denote the extended real line
$[-\infty,\infty]$. The following algebraic definition of bivariate copulas is
generalised to the multivariate setting in section 3. It essentially
constrains copulas to be functions that are “monotonically increasing” along
each dimension as well as towards the diagonal of the volume.

######  Definition 1.

Let $A_{1}$ and $A_{2}$ be nonempty subsets of $\overline{\mathbb{R}}$, and
let $H(\cdot,\cdot)$ be a real function such that the domain of $H=A_{1}\times
A_{2}$. Let $B=[x_{1},x_{2}]\times[y_{1},y_{2}]$ be a rectangle all of whose
vertices are in the domain of $H$. Then the _$H$ -volume of $B$_ is given by:

$V_{H}(B)=H(x_{1},y_{1})+H(x_{2},y_{2})-H(x_{1},y_{2})-H(x_{2},y_{1}).$

######  Definition 2.

A real function $H(\cdot,\cdot)$ is _2-increasing_ if its $H$-volume is non-
negative, that is $V_{H}(B)\geqslant 0$ for all rectangles $B$ whose vertices
lie in the domain of $H$.

######  Definition 3.

A _copula_ is a function $C\colon{[0,1]}^{2}\to[0,1]$ with the following
properties:

  1. 1.

For every $u,v\in[0,1]$,

$C(u,0)=0=C(0,v)$ $C(u,1)=u\quad\textrm{and}\quad C(1,v)=v$

  2. 2.

$C$ is 2-increasing.

###  2.2 Relation between bivariate CDFs and Copulas

Sklar’s theorem is central to the theory of copulas and is the foundation of
many applications in statistics. Indeed, Sklar’s theorem can be defined for
general distribution functions outside of probabilistic settings. However,
since we are interested in statistical applications we will consider
cumulative distribution functions.

######  Theorem 4 (Sklar’s theorem).

Let $H(\cdot,\cdot)$ be a cumulative distribution function with marginals
$F(\cdot)$ and $G(\cdot)$. Then there exists a copula
$C\colon{[0,1]}^{2}\rightarrow[0,1]$ such that for all $x,y$ in
$\overline{\mathbb{R}}$,

$H(x,y)=C(F(x),G(y)).$

If $F(\cdot)$ and $G(\cdot)$ are continuous then $C(\cdot,\cdot)$ is unique;
otherwise $C(\cdot,\cdot)$ is uniquely determined on the ranges of $F(\cdot)$
and $G(\cdot)$.

Conversely, if $C(\cdot,\cdot)$ is a copula and $F(\cdot)$ and $G(\cdot)$ are
cumulative distribution functions then the function $H(\cdot,\cdot)$ is a
bivariate cumulative distribution function with marginals $F(\cdot)$ and
$G(\cdot)$.

##  3 Spearman’s rho

We briefly review the bivariate model to lay out the approach for estimating
the copula using data, the so-called empirical copula.

###  3.1 Empirical bivariate Spearman’s

Let $R$ and $S$ be ranking functions, which are bijections mapping elements
$x$ in the domain $U$ to $[1,2,\dots,n]$. The domain $U$ represents the space
of objects that we are interested in ranking, such as documents retrieved in
response to a query or the biomarkers most associated with a disease. Since we
consider only the ranks of the object $R(x)$ and $S(x)$, the actual domain
does not affect the analysis. The sums below are over the $n$ objects $x$.
Similar to the approach of Pearson’s correlation for the measure of
dependence, Spearman’s is a measure of correlation between ranks, empirically
given by:

$\rho_{n}=\frac{\sum_{x}(R(x)-\bar{R})(S(x)-\bar{S})}{\sqrt{\sum_{x}{(R(x)-\bar{R})}^{2}\sum_{x}{(S(x)-\bar{S})}^{2}}}$
(1)

where $\bar{R}:=\frac{1}{n}\sum_{x}R(x)$ and
$\bar{S}:=\frac{1}{n}\sum_{x}S(x)$ are the empirical means of the respective
random variables. This is equivalent to applying Pearson’s correlation to the
ranks instead of the values of the score function itself. There is no direct
way to generalise this expression to more than two ranking functions, but as
we shall see in section 3.3 we can obtain an expression via the copula.

By substituting the definitions of the empirical means and rearranging the
terms, we obtain

$\rho_{n}=\left(\frac{n+1}{n-1}\right)\left[\frac{12}{n}\sum_{x}\frac{R(x)}{n+1}\frac{S(x)}{n+1}-3\right]$

The constants 12 and 3 seem strange, but are a natural consequence of the mean
and variance of a list of ranks. As we will see later, these constants are
dependent only on the dimension of the copula. Similar to the definition of an
empirical CDF, we define an empirical copula as:

$C_{n}(u,v)=\frac{1}{n}\sum_{x}\mathbf{1}\left(\frac{R(x)}{n+1}\leqslant
u,\frac{S(x)}{n+1}\leqslant v\right),$

where $\mathbf{1}$ is the indicator function. This allows us to re-express the
form of $\rho_{n}$ above in terms of an integral over the unit square,

$\rho_{n}=\left(\frac{n+1}{n-1}\right)\left[\frac{12}{n}\sum_{x}\frac{R(x)}{n+1}\frac{S(x)}{n+1}-3\right]=\left(\frac{n+1}{n-1}\right)\left[12\int_{{[0,1]}^{2}}uvC_{n}(u,v)-3\right]$

It can be shown (Nelsen, 2006; Genest and Favre, 2007) that $\rho_{n}$ is an
asymptotically unbiased estimator of

$\rho=12\int_{{[0,1]}^{2}}C(u,v)\;\mathrm{d}u\;\mathrm{d}v-3,$

where $C$ is the population version of $C_{n}$.

###  3.2 Multivariate copulas

We now generalise the definitions in section 2.1 to the multivariate case. The
concepts are essentially the same, constraining the copula to be
“monotonically increasing” in the interval $[0,1]$ and also towards the center
of the volume (durante10copti).

######  Definition 5.

Let $A_{j}$ be nonempty subsets of $\overline{\mathbb{R}}$ for $j=1,\dots,d$,
and let $H_{d}\colon A_{1}\times\cdots\times A_{d}\to\mathbb{R}$. Let
$B=[a_{1},b_{1}]\times\cdots\times[a_{d},b_{d}]$ be the $d$-box where all
vertices are contained in $\operatorname{Dom}H_{d}$. Then the _$H_{d}$ -volume
of $B$_ is the $d^{\text{th}}$ order difference:

$V_{H_{d}}(B)=\Delta_{a_{d}}^{b_{d}}\dots\Delta_{a_{1}}^{b_{1}}H_{d}(\vec{t}),$

where

$\displaystyle\Delta_{a_{i}}^{b_{i}}H(\vec{t})=$ $\displaystyle
H_{d}(t_{1},\dots,t_{i-1},b_{i},t_{i+1},\dots,t_{d})$ $\displaystyle-
H_{d}(t_{1},\dots,t_{i-1},a_{i},t_{i+1},\dots,t_{d})$

######  Definition 6.

A real function $H_{d}$ is _grounded_ if $H_{d}(\vec{t})=0$ for all
$t\in\operatorname{Dom}H_{d}$ such that $t_{j}=a_{j}$ for at least one
$j\in\\{1,\ldots,d\\}$.

######  Definition 7.

A real function $H_{d}$ is _d-increasing_ if $V_{H_{d}}(B)\geqslant 0$ for all
n-boxes $B$ whose vertices lie in the domain of $H$.

######  Definition 8.

A multivariate _copula_ has the following properties:

  1. 1.

$\operatorname{Dom}C={[0,1]}^{d}$

  2. 2.

$C$ has margins $C_{j}(u)=C(1,\dots,1,u,1,\dots,1)=u$ for all $j$ and $u\in I$

  3. 3.

$C$ is grounded

  4. 4.

$C$ is d-increasing.

There is an alternative probabilistic definition which may be more familiar to
readers with a statistical background.

######  Definition 9.

Let $U_{1},\dots,U_{d}$ be real uniformly distributed random variables on the
unit interval $\sim U([0,1])$. A copula function
$C\colon{[0,1]}^{d}\longrightarrow[0,1]$ is a joint distribution

$C(u_{1},\dots,u_{d})=P(U_{1}\leqslant u_{1},\dots,U_{d}\leqslant u_{d}).$

Let $X\sim F$ be a continuous random variable such that the inverse of the CDF
$F^{-1}$ exists. What is the distribution of $F(x)=P(X\leqslant x)$?

$\displaystyle P(F(X)\leqslant u)$ $\displaystyle=P(F^{-1}(F(X))\leqslant
F^{-1}(u))$ $\displaystyle=P(X\leqslant F^{-1}(u))$
$\displaystyle=F(F^{-1}(u))=u$

The above calculation shows that the distribution is uniform, i.e. $F(x)\sim
U([0,1])$. This can be considered to be the “copula trick”, as the user has
the freedom to choose the copula independently of the marginal distributions.

###  3.3 Multivariate extension of Spearman’s

We generalise the concept of concordance to the multivariate setting such that
we can define multivariate Spearman’s in an analogous way to the bivariate as
defined in Nelsen (2006).

Recall that two random variables are concordant if they tend to be in the same
order, that is $(x_{i},y_{i})$ and $(x_{j},y_{j})$ are concordant if
$(x_{i}-x_{j})(y_{i}-y_{j})>0$, and are discordant if
$(x_{i}-x_{j})(y_{i}-y_{j})<0$. The concordance function $Q$ denotes the
difference between the probabilities of concordance and discordance, and as
the following theorem shows, can be expressed in terms of the copulas. The
proof is in Nelsen (2006).

######  Theorem 10 (Concordance function).

Let $(X_{1},Y_{1})$ and $(X_{2},Y_{2})$ be two independent vectors with joint
distributions $H_{1}(x,y)=C_{1}(F(x),G(y))$ and $H_{2}(x,y)=C_{2}(F(x),G(y))$
respectively. Then the concordance function $Q$ is given by

$\displaystyle Q(C_{1},C_{2}):=$ $\displaystyle
P[(X_{1}-X_{2})(Y_{1}-Y_{2})>0]-P[(X_{1}-X_{2})(Y_{1}-Y_{2})<0]$
$\displaystyle=$ $\displaystyle
4\int_{{[0,1]}^{2}}C_{2}(u,v)\;\mathrm{d}C_{1}(u,v)-1$

We now state the generalisation of concordance to the multivariate case
(Nelsen, 1996; Joe, 1990). Further details of multivariate concordance can be
found in Taylor (2007); Schmid et al. (2010).

######  Definition 11 (Multivariate concordance).

Let $(X_{1},\ldots,X_{d})$ and $(Y_{1},\ldots,Y_{d})$ be two independent
$d$-vectors with joint distributions $C_{X}(F(x))$ and $C_{Y}(F(y))$ where
$F(x)=F_{1}(x_{1}),\ldots,F_{d}(x_{d})$ and
$F(y)=F_{1}(y_{1}),\ldots,F_{d}(y_{d})$ are the marginal distributions, and
$C_{X},C_{Y}$ are the respective $d$ copulas. Then the concordance function
$Q$ is given by

$\displaystyle Q(C_{X},C_{Y}):=$ $\displaystyle
2^{d}\int_{{[0,1]}^{d}}C_{X}(u)\;\mathrm{d}C_{Y}(u)-1.$

Note that although the integral is a straight forward generalisation of
theorem 10, it is no-longer equal to the difference between the probability of
concordance and discordance. Consequently, the properties posessed by $Q$ are
different for $d>2$.

There are three copulas which are of particular interest, the independent
copula $\pi(u):=\prod_{i}u_{i}$, and the upper and lower Fréchet–Hoeffding
bounds, $M$ and $W$ respectively (Joe, 2014, pg. 48). Note that
$M(u)=\min\\{u_{1},u_{2},\dots,u_{d}\\}$ is the upper Fréchet–Hoeffding bound,
and that $W(u)\geq\max\\{u_{1}+u_{2}+\cdots+u_{d}-(d-1),0\\}$ and is point-
wise sharp, though this lower bound is not itself a copula. Since the minimum
Fréchet–Hoefding bound $W$ is not a copula, the lower bound is not tight
(Úbeda Flores, 2005).

######  Theorem 12.

Let $C$, $C^{\prime}$, and $Q$ be given as in definition 11, $M$ and $W$ be
the upper and lower Fréchet–Hoeffding bounds respectively, and assume $d>2$.
Then

  1. 1.

$Q$ is symmetric in its arguments if $C=C^{\prime}$.

  2. 2.

$Q$ is non-decreasing in the first argument, and both arguments if
$C=C^{\prime}$.

  3. 3.

$-1\leq Q(W,W)\leq Q(C,C)\leq Q(M,M)=2^{d-1}-1$.

  4. 4.

$Q(\pi,\pi)=0$.

###### Proof.

##### Property 1

The first property is clear from the definition of $Q(C,C^{\prime})$ and the
properties of integration.

##### Property 2

Q is non-decreasing in the first argument by properties of integration. For
the second part, notice that

$\displaystyle\int C(u)\;\mathrm{d}C(u)=$ $\displaystyle C^{2}(u)-\int
C(u)\;\mathrm{d}C(u)$ $\displaystyle\Rightarrow\int C(u)\;\mathrm{d}C(u)=$
$\displaystyle\frac{1}{2}C^{2}(u)$

by applying integration by parts. The property now follows.

##### Property 3

It follows that

$\displaystyle Q(M,M)=$ $\displaystyle
2^{d}\int_{{[0,1]}^{d}}M(u)\;\mathrm{d}M(u)-1$ $\displaystyle=$ $\displaystyle
2^{d}\int_{0}^{1}u\;\mathrm{d}u-1$ $\displaystyle=$ $\displaystyle 2^{d-1}-1,$

and

$\displaystyle Q(W,W)=$ $\displaystyle
2^{d}\int_{{[0,1]}^{d}}W(u)\;\mathrm{d}W(u)-1$ $\displaystyle\geq$
$\displaystyle 2^{d}\int_{0}^{1}0\;\mathrm{d}u-1$ $\displaystyle=$
$\displaystyle-1.$

Property 3 now follows from the first two properties.

##### Property 4

$\displaystyle Q(\pi,\pi)=$ $\displaystyle
2^{d}\int_{{[0,1]}^{d}}\pi(u)\;\mathrm{d}\pi(u)-1$ $\displaystyle=$
$\displaystyle 2^{d}\int_{{[0,1]}^{d}}u\;\mathrm{d}u-1$ $\displaystyle=$
$\displaystyle\frac{2^{d}}{2^{d}}-1$ $\displaystyle=$ $\displaystyle 0$

It is clear from this theorem that $Q$ is well calibrated at $Q(W,W)$ and
$Q(\pi,\pi)$, however not for $Q(M,M)$. Consequently, with this
multidimensional extension it becomes increasingly difficult to estimate
discordance as $d$ increases.

######  Proposition 13.

Let $Q$ be given as in definition 11, and $M$ and $\pi$ be the upper
Fréchet–Hoeffding bound and the independent copula respectively, then

$Q(M,\pi)=Q(\pi,M)=\frac{2^{d}-(d+1)}{d+1}.$ (2)

###### Proof.

To show the symmetry,

$\displaystyle Q(M,\pi)=$ $\displaystyle
2^{d}\int_{{[0,1]}^{d}}M(u)\;\mathrm{d}\pi(u)-1$ $\displaystyle=$
$\displaystyle 2^{d}\int_{{[0,1]}^{d}}u_{1}u_{2}\cdots u_{d}\;\mathrm{d}u-1$

and

$\displaystyle Q(\pi,M)=$ $\displaystyle
2^{d}\int_{{[0,1]}^{d}}\pi(u)\;\mathrm{d}M(u)-1$ $\displaystyle=$
$\displaystyle 2^{d}\int_{{[0,1]}^{d}}u_{1}u_{2}\cdots u_{d}\;\mathrm{d}u-1.$

To obtain the second equality, we observe that

$\displaystyle\int_{{[0,1]}^{d}}u_{1}u_{2}\cdots u_{d}\;\mathrm{d}u=$
$\displaystyle\int_{0}^{1}u^{d}\;\mathrm{d}u$ $\displaystyle=$
$\displaystyle\left.\frac{1}{d+1}u^{d+1}\right|_{0}^{1}$ $\displaystyle=$
$\displaystyle\frac{1}{d+1},$

and therefore the expression for $Q(M,\pi)$ follows.

In terms of the concordance function, Spearman’s is given by the concordance
between the copula $C$ and the independent copula $\pi(u):=\prod_{i}u_{i}$.
However, unlike the symmetry in proposition 13, the concordance function is in
general not symmetric with respect to its arguments. This gives us two
possible ways of defining multivariate Spearmans’s , corresponding to
$Q(C,\pi)$ and $Q(\pi,C)$. Both generalisations are equivalent in the
bivariate case, and has been called $\rho_{d}^{-}$ and $\rho_{d}^{+}$ by
Nelsen (1996) and $\rho_{1}$ and $\rho_{2}$ by Schmid and Schmidt (2007)
respectively. Naturally, there is a third symmetric generalisation which is
the average of them.

######  Definition 14 (Multivariate Spearman’s ).

$\displaystyle\rho_{d}^{-}=h(d)Q(\pi,C)$
$\displaystyle=h(d)\left[2^{d}\int_{{[0,1]}^{d}}C(u)\;\mathrm{d}u-1\right],$
(3)

and

$\displaystyle\rho_{d}^{+}=h(d)Q(C,\pi)=h(d)\left[2^{d}\int_{{[0,1]}^{d}}\pi(u)\;\mathrm{d}C(u)-1\right].$
(4)

where $h(d)=\frac{d+1}{2^{d}-(d+1)}$ is the normalisation factor.

The scaling factor $h(d)$ is derived such that the maximum correlation is 1.
Thus, for Spearman’s , this is the concordance between the maximum copula $M$
and the independent copula $\pi$, which we obtain by proposition 13:

$h(d)=1/Q(M,\pi)=\frac{d+1}{2^{d}-(d+1)}.$ (5)

Spearman’s correlation can equivalently be seen as measuring average orthant
dependence, and the two versions $\rho_{d}^{+}$ and $\rho_{d}^{-}$ correspond
to whether we look at the upper or lower orthant (Nelsen, 1996). Positive
upper orthant dependence is defined as

$P(X>x)\geq\prod_{i=1}^{d}P(X_{i}>x_{i}),$

and positive lower orthant dependence is defined as

$P(X\leq x)\geq\prod_{i=1}^{d}P(X_{i}\leq x_{i}).$

When $d=2$, the two definitions are the same and are called positive quadrant
dependence (lehmann66somcd), as we have already observed for the concordance
function:

$\displaystyle P(X_{1}>x_{1},X_{2}>x_{2})$ $\displaystyle\geq
P(X_{1}>x_{1})P(X_{2}>x_{2})$ $\displaystyle\geq[1-P(X_{1}\leq
x_{1})][1-P(X_{2}\leq x_{2})]$ $\displaystyle\geq 1-P(X_{1}\leq
x_{1})-P(X_{2}\leq x_{2})+P(X_{1}\leq x_{1})P(X_{2}\leq x_{2}).$

Rearranging gives

$P(X_{1}>x_{1},X_{2}>x_{2})+P(X_{1}\leq x_{1})+P(X_{2}\leq x_{2})-1\geq
P(X_{1}\leq x_{1})P(X_{2}\leq x_{2}).$

The left hand side is $P(X_{1}\leq x_{1},X_{2}\leq x_{2})$.

Observe that the scaling factor $h(d)$ is the same for both $\rho^{-}_{d}$ and
$\rho^{+}_{d}$ due to Proposition 13. Furthermore, since
$P(X_{i}>x_{i})=1-P(X_{i}\leq x_{i})$ for each random variable, the two
versions of Spearman’s correspond to looking at whether we interpret the ranks
as top down or bottom up. Converting from one version to the other can be done
by reinterpreting the data. For a particular application, the choice of which
version to use depends on the ranks that are available. We will focus on
$\rho_{d}^{+}$ henceforth.

Recall that for a set of $n$ objects from the domain $\Omega$, we are given a
set of $d$ experts that rank these objects providing ranks
$R_{1},\ldots,R_{d}$, where each $R_{j}$ is a bijection to $(0,1)$. Putting
(4) and (5) together, we obtain the following expression for multivariate
Spearman’s correlation:

$\rho(R_{1},\ldots,R_{d})=h(d)Q(C,\pi)=\frac{d+1}{2^{d}-(d+1)}\left[2^{d}\int_{{[0,1]}^{d}}\pi(u)\;\mathrm{d}C(u)-1\right].$
(6)

In practice, we do not have access to the population version of the copula
$C(u)$ but have the empirical copula $C_{n}(u)$. We discuss this further in
section 5.

Unlike the bivariate case, as the number of dimensions increases, the lower
bound of Spearman’s tends to zero. This counterintuitive fact can be
understood by considering the three dimensional case. Consider three rankings
$R_{1},R_{2},R_{3}$. If $R_{1}$ and $R_{2}$ are anti-correlated (=-1), and at
the same time $R_{1}$ and $R_{3}$ are also anti-correlated, this implies that
$R_{2}$ and $R_{3}$ must be perfectly correlated (=1). Hence the overall 3
dimensional correlation is no longer -1. This can be made precise by
considering the inclusion-exclusion principle, which results in the following
relation from Nelsen (1996):

$\frac{1}{2}(\rho_{d}^{-}(R_{1},R_{2},R_{3})+\rho_{d}^{+}(R_{1},R_{2},R_{3}))=\frac{1}{3}(\rho(R_{1},R_{2})+\rho(R_{1},R_{3})+\rho(R_{2},R_{3})).$

The following corollary defines the lower bound as the number of dimensions
increases.

######  Corollary 15.

Under the minimum Fréchet–Hoefding bound $W$, $Q(W,\pi)\geq-1$ and

$\lim_{d\to\infty}\rho(R_{1},\dots,R_{d})\geqslant h(d)Q(W,\pi)=0.$

In particular, for dimension $d$,

$\rho(R_{1},\dots,R_{d})\geqslant\frac{2^{n}-(n+1)!}{n!(2^{n}-(n+1))}.$

###### Proof.

This follows immediately from the bound $-1\leq Q(W,\pi)\leq 0$ (from theorem
12) since $h(d)$ goes to zero as $d\to\infty$. The lower bound has also been
observed in Nelsen (1996); Schmid et al. (2010).

In summary the multivariate extension of Spearman’s correlation is still
calibrated at the top, having a maximum value of 1, but it becomes
increasingly difficult to observe anti-correlated sets of ranks as the number
of lists to be aggregated increases. In the next section, we investigate an
aggregation algorithm that maximises correlation. The effect of the lower
bound is discussed with respect to imputing missing values in section 5.

##  4 Optimal aggregation with Spearman’s $\rho$

The empirical copula requires $R$ and $S$ to comprise of ranks for the same
set of elements, that is $\operatorname{Dom}R=\operatorname{Dom}S$. Recall
from section 3.1 that ranks map to the range $\\{1,\ldots,n\\}$, but the
empirical copula is expressed in terms of fractional ranks (divided by $n+1$).
In the following it is convenient to work with normalised ranks, that is to
consider $R$ and $S$ as bijections to $(0,1)$. The expression for the
empirical copula then simplifies to

$C_{n}(u,v)=\frac{1}{|\Omega|}\sum_{x\in\Omega}\mathbf{1}\left(R(x)\leqslant
u,S(x)\leqslant v\right),$ (7)

where is the domain of the objects we are interested in ranking.
Correspondingly, the $d$ dimensional empirical copula for $n$ objects given by

$C_{n}(u)=\frac{1}{n}\sum_{x}\prod_{j=1}^{d}\mathbf{1}\left(R_{j}(x)\leqslant
u_{j}\right),$ (8)

where $R_{1}(x),\ldots,R_{d}(x)$ is the rankings of the $d$ experts. Plugging
the empirical copula (8) expression into Spearman’s $\rho$ (6), and observing
that integrating the product over the copula is the product of the ranks
Schmid and Schmidt (2007), we obtain an empirical expression for multivariate
Spearman’s correlation:

$\rho_{n}(R_{1},\ldots,R_{d})=h(d)\left[\frac{2^{d}}{n}\sum_{x}\prod_{j=1}^{d}R_{j}(x)-1\right].$
(9)

###  4.1 Geometric mean is optimal

We are now in a position to derive the deceptively simple result: the ranking
$R$ that maximises correlation with a given set of rankings
$\\{R_{1},\ldots,R_{d}\\}$ is given by the geometric mean of
$R_{1},\ldots,R_{d}$. The following definition is needed to capture the notion
that ranks only depend on the order.

######  Definition 16 (Rank generator).

$\sigma\colon\mathbb{R}^{|\Omega|}\to{[0,1]}^{|\Omega|}$ is a rank generator
if:

  * •

for all $x,y\in\Omega$ and $R$ with domain $\Omega$, $R(x)<R(y)\iff\sigma\circ
R(x)<\sigma\circ R(y)$;

  * •

for any rankings $R,R^{\prime}$ with domain $\Omega$ there exists a
permutation $\xi$ such that $\sigma\circ R^{\prime}=\sigma\circ\xi\circ R$;

  * •

for any permutation $\xi$, $\xi\circ\sigma=\sigma\circ\xi$.

A rank generator formalises the idea of generating a rank: the ranks it
generates must be invariant to scale and only dependent on the ordering of
elements. The standard ranking functions from statistics such as fractional
ranking and dense ranking fit into this framework.

######  Theorem 17.

Let $\\{R_{1},R_{2},\dots,R_{d}\\}$ be a set of rankings with common domain
$\Omega$ and $\sigma$ be a rank generator. Then

$\arg\max_{R\in\operatorname{codom}\sigma}\rho_{n}(R,R_{1},R_{2},\dots,R_{d})=\sigma\left(\prod_{j=1}^{d}R_{j}\right).$

###### Proof.

Consider the expression for Spearman’s $\rho_{n}$ (9):

$\rho_{n}(R,R_{1},R_{2},\dots,R_{d})=h(d+1)\left[\frac{2^{d+1}}{n}\sum_{x}\left(R(x)\prod_{j=1}^{d}R_{j}(x)\right)-1\right]$

Focusing on the terms in the sum, showing that the best possible $R(x)$ is
$\prod_{j=1}^{d}R_{j}(x)$ reduces to showing

$\sum_{x\in U}\sigma\circ P(x)P(x)$

is maximal, where $P:=\prod_{j}R_{j}$. Suppose there exists an $P^{\prime}$
such that

$\sum_{x\in U}\sigma\circ P^{\prime}(x)P(x)>\sum_{x\in U}\sigma\circ
P(x)P(x).$

By definition of $\sigma$, there exists a permutation $\xi$ such that

$\displaystyle\sum_{x\in U}\sigma\circ P^{\prime}(x)P(x)$
$\displaystyle=\sum_{x\in U}\sigma\circ\xi\circ P(x)P(x)$
$\displaystyle=\sum_{x\in U}\xi\circ\sigma\circ P(x)P(x)$
$\displaystyle>\sum_{x\in U}\sigma\circ P(x)P(x).$

This however is a contradiction for any permutation $\xi$ as $\sigma$ is order
preserving.

######  Corollary 18.

The converse applies, that is:

$\arg\min_{R\in\operatorname{codom}\sigma}\rho_{n}(R,R_{1},R_{2},\dots,R_{d})=\sigma\left(\prod_{j=1}^{d}(1-R_{j})\right).$

###### Proof.

Proof follows from a similar argument.

##  5 Empirical copulas with partial lists

In many applications it is prohibitive to obtain complete annotations of the
object ranks. For example, in the document retrieval setting, this amounts to
providing ranks for all documents. The empirical copula requires the set of
rankings $\\{R_{1},\ldots,R_{d}\\}$ to comprise of ranks for the same set of
elements, that is $\operatorname{Dom}R_{1}=\cdots=\operatorname{Dom}R_{d}$.
Hence a key challenge in applying Spearman’s to rank aggregation is to
estimate the statistic on incompletely labeled lists.

Recall the definition of the empirical copula (7). We now consider the case
where $\operatorname{Dom}R\neq\operatorname{Dom}S$, but $R$ and $S$ are
generated from two top ranked lists. We define extended rankings
$R^{\prime},S^{\prime}$ with codomain $[0,1]$ such that
$\operatorname{Dom}R^{\prime}=\operatorname{Dom}R\cup\operatorname{Dom}S=\operatorname{Dom}S^{\prime}$.
One way to impute the missing values is to set them to a constant value for
all the ranks below the top-$k$ ranks. This value is chosen to be the mid
point between the start and end of the missing section. The values in the
top-$k$ are retained to be the original values in the extension. The
definition below formally defines this notion. Note that we have to
renormalise the values.

######  Definition 19 (non-informative extension).

Let $R$ be a ranking operator and $R^{\prime}$ be its extension to domain
$\operatorname{Dom}R^{\prime}$. Then,

$\displaystyle
R^{\prime}(x)=\left\\{\begin{array}[]{lr}\frac{|\operatorname{Dom}R|}{|\operatorname{Dom}R^{\prime}|}R(x)&x\in\operatorname{Dom}R\\\
\frac{|\operatorname{Dom}R|+|\operatorname{Dom}R^{\prime}|}{2|\operatorname{Dom}R^{\prime}|}&\text{otherwise}\end{array}\right.$
(12)

$\forall x\in\operatorname{Dom}R^{\prime}$.

We call this the noninformative extension since it assumes that all items that
are not ranked have the same rank (the mean of the missing ranks). Note that
the two experts $R_{i}$ and $R_{j}$ may have ranked different numbers of
objects. An advantage of this extension is that it can easily deal with the
case of more than two experts. Consider $d$ experts $R_{1},\ldots,R_{d}$, each
which may have ranked a different subset of the objects. Hence the extension
has to impute values on the union of items from all experts. Denote
$\operatorname{Dom}R^{\prime}:=\operatorname{Dom}R_{1}\cup\ldots\cup\operatorname{Dom}R_{d}$,
then we can apply definition 19 to complete each ranking operator $R_{j}$. An
additional advantage to the noninformative extension is that it results in a
consistent ranking.

######  Definition 20.

An extended ranking $R^{\prime}$ of $R$ is called consistent if the following
axioms hold:

  1. 1.

$R^{\prime}(x)<R^{\prime}(y)$ $\forall x,y\in\operatorname{Dom}R$ with
$R(x)<R(y)$

  2. 2.

$R^{\prime}(x)=R^{\prime}(y)$ $\forall x,y\in\operatorname{Dom}R$ with
$R(x)=R(y)$

  3. 3.

$R^{\prime}(y)>R^{\prime}(x)$ $\forall
x\in\operatorname{Dom}R,\,y\in\operatorname{Dom}R^{\prime}$

If $E[R]=E[R^{\prime}]$ also holds, then $R^{\prime}$ is called strictly
consistent.

######  Lemma 21.

definition 19 produces a consistent ranking. If $E[R]=\frac{1}{2}$ then (12)
produces a strictly consistent ranking.

###### Proof.

The notation $|\operatorname{Dom}R|$ can become unwieldly in following proof.
We therefore adopt the shorthand notations $r:=|\operatorname{Dom}R|$ and
$r^{\prime}:=|\operatorname{Dom}R^{\prime}|$ for the size of the respective
sets.

Axioms 1 and 2 are satisfied by definition as the map
$x\mapsto\frac{r}{r^{\prime}}x$ is monotonic. For all
$x\in\operatorname{Dom}R^{\prime}\setminus\operatorname{Dom}R$,

$R^{\prime}(x)=\frac{r+r^{\prime}}{2r^{\prime}}\leqslant
2R(y)\frac{r+r^{\prime}}{2r^{\prime}}\leqslant\frac{2R(y)r}{2r^{\prime}}=\frac{r}{r^{\prime}}R(y)=R^{\prime}(y)$

for any $y\in\operatorname{Dom}R$, satisfying axiom 3.

Furthermore, as

$\displaystyle E[R^{\prime}]$
$\displaystyle=\frac{1}{r^{\prime}}\left(\sum_{x\in\operatorname{Dom}R}R^{\prime}(x)+\sum_{x\in\operatorname{Dom}R^{\prime}\setminus\operatorname{Dom}R}R^{\prime}(x)\right)$
$\displaystyle=\frac{1}{r^{\prime}}\left(\frac{r}{r^{\prime}}\sum_{x\in\operatorname{Dom}R}R(x)+(r^{\prime}-r)\frac{r+r^{\prime}}{2r^{\prime}}\right)$
$\displaystyle=\frac{1}{r^{\prime}}\left(\frac{r^{2}}{r^{\prime}}E[R]+(r^{\prime}-r)\frac{r+r^{\prime}}{2r^{\prime}}\right)$
$\displaystyle=\frac{r^{2}(2E[R]-1)+r^{\prime}}{2r^{\prime 2}},$

$R^{\prime}$ is strictly consistent if $E[R]=\frac{1}{2}$.

Definition 19 is called a non-informative extension as it uses no additional
information and does not bias the imputed elements in anyway: imputed values
are all considered tied and mapped to the same value. Futhermore, the strictly
consistent property that definition 19 satisfied is important when using
fractional ranking as it guarantees no introduction of bias.

Note also that there is a dual imputation whereby missing values are assigned
to the top of the list rather than the bottom. This is equivalent to the above
imputation applied to reverse rankings. The choice of top or bottom imputation
is application dependent.

###  5.1 Empirical upper and lower bounds

######  Proposition 22.

For top-$k$ lists where $k$ of $n$ items are ranked by all $d$ experts with
codomain $\\{1,\dots,n\\}$ (i.e., un-normalised ranks), the Spearman’s is
bounded by

$\rho_{n}(R_{1},R_{2},\dots,R_{d})=\rho_{k}(R_{1},R_{2},\dots,R_{d})+C$

where

$\displaystyle\frac{{2}^{d}\,\mathrm{h}\left(d\right)\,\left(\left(k\,{\left(k+1\right)}^{d}-n\,{\left(n+1\right)}^{d}\right)\,\left(\sum_{i=1}^{k}\prod_{j=1}^{d}\frac{{R}_{j}\left(i\right)}{k+1}\right)+k\,\sum_{i=k+1}^{n}{i}^{\frac{d}{2}}\,{\left(k-i+n+1\right)}^{\frac{d}{2}}\right)}{n\,{\left(n+1\right)}^{d}\,k}$
$\displaystyle\leq C\leq$
$\displaystyle\frac{{2}^{d}\,\mathrm{h}\left(d\right)\,\left(\left(k\,{\left(k+1\right)}^{d}-n\,{\left(n+1\right)}^{d}\right)\,\left(\sum_{i=1}^{k}\prod_{j=1}^{d}\frac{{R}_{j}\left(i\right)}{k+1}\right)+\left(\sum_{i=k+1}^{n}{i}^{d}\right)\,k\right)}{n\,{\left(n+1\right)}^{d}\,k}$

###### Proof.

Proof sketch: the definition of for unnormalised rankings is

$\rho_{n}(R_{1},R_{2},\dots,R_{d})=h(d+1)\left[\frac{2^{d+1}}{n}\sum_{i=1}^{n}\left(\prod_{j=1}^{d}\frac{R_{j}(i)}{n+1}\right)-1.\right]$

By considering the difference
$\rho_{n}(R_{1},R_{2},\dots,R_{d})-\rho_{k}(R_{1},R_{2},\dots,R_{d})$ and
factorising out the common terms, we obtain

$C=\frac{\left(d+1\right)\,{2}^{d}\,\left(k\,\left(\sum_{i=1}^{n}\prod_{j=1}^{d}\frac{{R}_{j}\left(i\right)}{n+1}\right)-\left(\sum_{i=1}^{k}\prod_{j=1}^{d}\frac{{R}_{j}\left(i\right)}{k+1}\right)\,n\right)}{\left({2}^{d}-d-1\right)\,k\,n}.$

The term $\sum_{i=1}^{n}\prod_{j=1}^{d}\frac{{R}_{j}\left(i\right)}{n+1}$ can
be bounded above by

$\sum_{i=1}^{n}\prod_{j=1}^{d}\frac{{R}_{j}\left(i\right)}{n+1}=\sum_{i=1}^{k}\prod_{j=1}^{d}\frac{{R}_{j}\left(i\right)}{n+1}+\sum_{i=1+k}^{n}\prod_{j=1}^{d}\frac{{R}_{j}\left(i\right)}{n+1}\leq\sum_{i=1}^{k}\prod_{j=1}^{d}\frac{{R}_{j}\left(i\right)}{n+1}+\sum_{i=1+k}^{n}{\left(\frac{i}{n+1}\right)}^{d}.$

and below by

$\sum_{i=1}^{n}\prod_{j=1}^{d}\frac{{R}_{j}\left(i\right)}{n+1}=\sum_{i=1}^{k}\prod_{j=1}^{d}\frac{{R}_{j}\left(i\right)}{n+1}+\sum_{i=1+k}^{n}\prod_{j=1}^{d}\frac{{R}_{j}\left(i\right)}{n+1}\geq\sum_{i=1}^{k}\prod_{j=1}^{d}\frac{{R}_{j}\left(i\right)}{n+1}+\sum_{i=k+1}^{n}\left(\prod_{j=i}^{\lceil\frac{d}{2}\rceil}\frac{i}{n+1}\right)\,\prod_{j=\lceil\frac{d}{2}\rceil}^{d}\frac{n-i+1+k}{n+1},$

giving us the bounds in the proposition.

###  5.2 Optimal imputation

An alternative to the previously presented imputation method is to impute such
that is maximised or minimised. In general this is a NP-hard problem as it
involves searching all permutations. In this section, we formulate this as an
optimisation problem.

Let $\mathbb{I}=\\{1,\dots,n\\}\times\\{1,\dots,d\\}$ be indices over $n$
items and $d$ experts. Let $\mathbb{O}\subset\mathbb{I}$ be the observed
indices (for which we have a rank) and define
$\mathbb{U}:=\mathbb{I}\setminus\mathbb{O}$. We then have a rank function
$R\colon\mathbb{O}\to\\{1,\dots,n\\}$. Recall that Spearman’s is determined by
a sum of the products over ranks. By introducing a log transformation, we
convert the product into a sum using the logarithm rule:

$\sum_{i=1}^{n}\left(\prod_{j=1}^{d}\frac{R_{j}(i)}{n+1}\right)=\sum_{i=1}^{n}\left(\exp\log\prod_{j=1}^{d}\frac{R_{j}(i)}{n+1}\right)=\sum_{i=1}^{n}\left(\exp\sum_{j=1}^{d}\log\frac{R_{j}(i)}{n+1}\right)$

####  5.2.1 Imputing to maximise correlation

We can maximise Spearman’s by introducing binary indicators $x_{i,j,k}$
indexed over $\mathbb{I}\times\\{1,\dots,n\\}$ that denote item $i$ in list
$j$ is assigned rank $k$.

$\max_{x_{i,j,k}}\sum_{i=1}^{n}\exp\left[\sum_{j=1}^{d}\sum_{k=1}^{n}x_{i,j,k}\log\left(\frac{k}{n+1}\right)\right]$

such that

$\displaystyle\sum_{k}x_{i,j,k}$ $\displaystyle=1$ $\displaystyle\forall i,j$
(13) $\displaystyle\sum_{i}x_{i,j,k}$ $\displaystyle=1$ $\displaystyle\forall
k,j$ (14) $\displaystyle\sum_{k}x_{i,j,k}k$ $\displaystyle=R(i,j)$
$\displaystyle\forall(i,j)\in\mathbb{O}$ (15) $\displaystyle x_{i,j,k}$
$\displaystyle\in\\{0,1\\}$ $\displaystyle\forall i,j,k$ (16)

Constraint (13) ensures an item is only assigned one rank per expert, and
constraint (14) ensures a rank is only assigned once per expert. Finally, the
third constraint (15) ensures known ranks are assigned.

####  5.2.2 Imputing to minimise correlation

Analogously, we can consider the problem of minimising Spearman’s .

$\min_{x_{i,j,k}}\sum_{i=1}^{n}\exp\left[\sum_{j=1}^{d}\sum_{k=1}^{n}x_{i,j,k}\log\left(\frac{k}{n+1}\right)\right]$
(17)

such that

$\displaystyle\sum_{k}x_{i,j,k}$ $\displaystyle=1$ $\displaystyle\forall i,j$
$\displaystyle\sum_{i}x_{i,j,k}$ $\displaystyle=1$ $\displaystyle\forall k,j$
$\displaystyle\sum_{k}x_{i,j,k}k$ $\displaystyle=R(i,j)$
$\displaystyle\forall(i,j)\in\mathbb{O}$ $\displaystyle x_{i,j,k}$
$\displaystyle\in\\{0,1\\}$ $\displaystyle\forall i,j,k$

By considering the relaxation of $x_{i,j,k}\in\\{0,1\\}$ to
$x_{i,j,k}\in[0,1]$, we obtain a convex optimisation problem.

######  Proposition 23.

The relaxation of optimisation problem (17) such that $x_{i,j,k}$ is in the
interval $[0,1]$ is a convex optimisation problem.

###### Proof.

Note that as the objective has the form $\sum_{i}\exp(\langle
x_{i},\omega\rangle)$ with
$\omega\in{[\log\left(\frac{1}{n+1}\right),\dots,\log\left(\frac{n}{n+1}\right)]}^{nd}$.
Thus, as each term in the sum is convex, and as the sum of convex functions is
convex, the objective is convex. The constraints are all linear, hence this is
a convex optimisation problem.

However, as a consequence of corollary 15, as $d\to\infty$ we know that
$\rho\geq 0$, hence the minimum $\rho$ will approach the $\rho$ when using the
non-informative extension (the non-informative extension has $\rho=0$), thus
there is little need to solve the optimisation problem after a sufficient
number of dimensions is reached.

###  5.3 Experiments on University Ranking

The optimal imputation algorithm presented in section 5.2 is difficult to
solve due to the integer constraints. We evaluated the performance of a
relaxed version of the program, whereby the constraints are relaxed such that
the variables may take a value in the range $[0,1]$. To solve the relaxed
problem, we used a BFGS based optimiser by shifting the equality constraints
into the objective function with high penalties. Final ranks were determined
by ranking item $i$ in list $j$ based on the score $\sum_{k}x_{i,j,k}k$.

We evaluated this relaxed solution on imputing rankings for universities. To
this end, the top-200 universities ranked by QS in 2014, Shanghai in 2014, and
Times in 2015 were obtained. In aggregating these three lists, there are a
total of 266 ranks that need to be imputed.

Measuring multivariate Spearman’s on all three lists imputing the missing
elements using the non-informative extension gives $\rho=0.632$. In
comparison, the relaxed optimal imputation found a solution that obtained
$\rho=0.683$, a modest increase in the correlation. We also developed an
interactive website111http://uni.cua0.org showing the detailed results for all
universities, which also allows the user to alter the weights of each of the
original experts. The top 36 aggregate rankings for the universities are given
in section B.

##  6 Supervised learning to rank

We now consider the task of learning rank aggregation from extreme ranks.
theorem 17 and definition 19 provide the core of our algorithm. Using theorem
17, we can find an “average” rank that aggregates a set of ranks, and by
extending top-$k$ and bottom-$k$ ranks to a common domain, we can apply it to
partially labelled data.

###  6.1 Weighted mixture of experts

As a result of theorem 17 we have a way of finding the ranking (according to
some rank generator) that is closest to a set of ranks. Consider the learning
problem where we have a ranking $L$ which comprise our labels, and a set of
$d$ experts $\\{R_{j}\\}$. During training, we would like to find a weighting
of the input rankings such that it gives the label. Given a target ranking
$L$, we would like to optimise the weights $\omega$,

$\max_{\omega}\rho_{n}(L,R_{1}^{\omega_{1}},R_{2}^{\omega_{1}},\ldots,R_{n}^{\omega_{d}})$

Here we have introduced weights $\omega$ over each rank to control the
influence of each rank over the final consensus rank; the intuition here is
that ranks with $\omega_{i}>1$ are “replicated” with more influence, which is
easy to see when $\omega_{i}$ are natural numbers. For example, a weight of
$2$ would mean the ranked list has appeared twice in the calculation of the
consensus rank. While it is convenient to have integer weights for
interpretability, the weights $\omega$ could be any real number in general. In
the following, we consider $\omega\in\mathbb{R}^{n}$. Instead of performing
this high-dimensional optimisation, we decompose it into a pairwise
(bivariate) comparison between the label $L$ and the weighted geometric mean,
where we now explicitly show the fact that the ranks are a function of the $n$
objects $x$

$\max_{\omega}\sum_{x}\rho_{n}(L(x),\,\sigma(R_{1}^{\omega_{1}}\otimes
R_{2}^{\omega_{2}}\otimes\dots\otimes R_{d}^{\omega_{n}})(x))$

where the notation $\otimes$ indicates the product operator. Observe that we
have used theorem 17 to convert the $d$ dimensional problem into the product
of ranks $R_{j}$ and the Spearman’s correlation above is only two dimensional.
For bivariate Spearman’s , this can be expressed in terms of the squared
difference (1). We further assume that $\sigma$ is the identity mapping to
simplify the problem, giving us:

$\min_{\omega}\sum_{x}{\left(L(x)-R_{1}^{\omega_{1}}(x)R_{2}^{\omega_{2}}(x)\dots
R_{d}^{\omega_{n}}(x)\right)}^{2}.$ (18)

The objective (18) minimises the distance between the label ranks and the
weighted expert ranks.

###  6.2 Least squares method on logarithm of ranks

Recall that we consider normalised ranks (divided by $n+1$). By using the
logarithm identity, we convert the power scaling in (18) into a multiplicative
scaling. Our algorithm is:

  1. 1.

Extend incomplete ranks $\\{R_{i}\\}$ to $\\{R^{\prime}_{i}\\}$ by imputing
the average missing value such that
$\operatorname{Dom}R^{\prime}_{i}=\operatorname{Dom}L$;

  2. 2.

Convert to log-ranks $r^{\prime}_{i}=\log\circ R^{\prime}_{i}$ and
$l=\log\circ L$;

  3. 3.

Learn weights $\omega$ by minimising

$\sum_{x}{\left(l(x)-\sum_{j=1}^{d}\omega_{j}r^{\prime}_{j}(x)\right)}^{2},\qquad\mbox{where
the outer sum is over the $n$ examples $x$.}$

A log transformation of the ranks is used as it naturally encodes the weights
as a power scaling in the framework of theorem 17, i.e., the weighted
consensus rank is given by $\prod_{i}{r^{\prime}_{i}(x)}^{\omega_{i}}$. Note
that this is still solving (18) as we are optimising Spearman’s , which is
sensitive only to ordering, and therefore though the final weights are
different is maximised via (1).

In the following experiments we also included a bias/offset term in the least
squares problem which can be interpreted as adding a ranking that is constant
(gives all objects the same rank). It is interesting to note that the final
step in this procedure is closely related to Borda Count, except our consensus
rank is the geometric mean instead of the arithmetic mean. Since this is a
least squares estimation problem, we directly use the closed form solution.

###  6.3 Benchmarking on LETOR 4.0

(a) MQ2007

(b) MQ2008

Figure 1: Results on MQ2007-agg (left) and MQ2008-agg (right): NDCG@k. Our
method is labelled RAGS-⊤ and RAGS-⊥ corresponding to top and bottom non
informative imputation respectively. The results for CPS-S was the best
reported in Qin et al. (2010a). The results of $\theta$-MPM was the best among
the reported results in Volkovs and Zemel (2012) from BordaCount, CPS, SVP,
Bradley-Terry model, and Plackett-Luce model. The results of St.Agg was the
best among the reported results in Niu et al. (2013) and was the best among
MCLK, SVP, Plackett-Luce model, $\theta$-MPM, BordaCount and RRF. The actual
numbers of each point are in the supplement.

We tested our method on the MQ2007-agg and MQ2008-agg list aggregation
benchmarks Qin et al. (2010b). The goal in these challenges is to aggregate 21
and 25 different rankers respectively over a set of query-document pairs. Each
dataset has 5 pre-defined cross-validation folds with each fold providing a
training, testing and validation dataset (60%/20%/20%). We trained our model
on the training set and tested on the testing set, leaving the validation set
unused since we have no hyperparameters.

In the following we consider two types of experts: either experts
$\\{R_{j}\\}$ are top-$k$ experts, that is they only rank the best $k$ samples
from $\Omega$, or experts are bottom-$k$ experts, that is they identify the
worst $k$ samples from $\Omega$. We call our proposed method RAGS-⊤ and RAGS-⊥
respectively. We assume that the ranked documents in the benchmark datasets
are either top-$k$ or bottom-$k$ respectively, with potentially different
numbers of documents $k$ labeled by each expert. Ties are given the average
rank of tied documents.

To evaluate the agreement, we use the standard evaluation tool from the LETOR
website222http://research.microsoft.com/letor, which implements the Normalised
Discounted Cumulative Gain (NDCG). In fig. 1a, we see that our approach RAGS-⊤
performs better than all other methods at any selection size on the MQ2007-agg
dataset. Indeed, we also perform better than Qin et al. (2010a) where the best
result uses a coset-permutation distance based stagewise (CPS) model with
Spearman’s in a probabilistic model. Recall that our approach considers the
multivariate Spearmans’ whereas Qin et al. (2010a) uses bivariate Spearman’s
in a pairwise fashion. For MQ2008-agg (fig. 1b), again our approach performs
better than all other methods.

Table 1: Results on MQ2007-agg: NDCG. Our method is labelled RAGS-⊤ and RAGS-⊥ corresponding to top and bottom non informative imputation respectively. The results for CPS-S was the best reported in Qin et al. (2010a). The results of $\theta$-MPM was the best among the reported results in Volkovs and Zemel (2012) from BordaCount, CPS, SVP, Bradley-Terry model, and Plackett-Luce model. The results of St.Agg was the best among the reported results in Niu et al. (2013) and was the best among MCLK, SVP, Plackett-Luce model, $\theta$-MPM, BordaCount and RRF. Fold | @1 | @2 | @3 | @4 | @5 | @6 | @7 | @8 | @9 | @10
---|---|---|---|---|---|---|---|---|---|---
RAGS-⊤ | 0.45986 | 0.46078 | 0.45744 | 0.45838 | 0.46102 | 0.46512 | 0.4703 | 0.47538 | 0.48042 | 0.4858
RAGS-⊥ | 0.32804 | 0.3448 | 0.34836 | 0.35114 | 0.3552 | 0.36132 | 0.36656 | 0.37402 | 0.37952 | 0.38458
CPS-S |  | 0.332 |  | 0.341 |  | 0.352 |  | 0.362 |  |
-MPM | 0.4177 | 0.4191 | 0.4192 | 0.4234 | 0.4279 |  |  |  |  |
St.Agg |  |  |  |  | 0.4195 |  |  |  |  | 0.4404
GeoMean | 0.42264 | 0.42528 | 0.42570 | 0.42834 | 0.42886 | 0.43342 | 0.43664 | 0.44004 | 0.44648 | 0.45216

Table 2: Results on MQ2008-agg: NDCG Fold | @1 | @2 | @3 | @4 | @5 | @6 | @7 | @8 | @9 | @10
---|---|---|---|---|---|---|---|---|---|---
RAGS-⊤ | 0.41158 | 0.44898 | 0.47118 | 0.4922 | 0.50696 | 0.51706 | 0.52416 | 0.48732 | 0.24498 | 0.24768
RAGS-⊥ | 0.35156 | 0.40338 | 0.42624 | 0.45326 | 0.4706 | 0.48352 | 0.48994 | 0.45336 | 0.22138 | 0.22514
CPS-S |  | 0.314 |  | 0.376 |  | 0.419 |  | 0.398 |  |
-MPM | 0.3817 | 0.4057 | 0.4219 | 0.4307 | 0.4399 |  |  |  |  |
St.Agg |  |  |  |  | 0.4515 |  |  |  |  | 0.2157
GeoMean | 0.38470 | 0.41600 | 0.44142 | 0.45976 | 0.47938 | 0.49042 | 0.49986 | 0.46108 | 0.22334 | 0.22812

To tease apart the effect of imputing missing ranks and the effect of
weighting the experts, we compared our proposed method with and without
training (uniform weights). GeoMean denotes the results for the geometric mean
(uniform weights on the experts) after performing imputation assuming top-$k$
ranking by the experts. First we observe that our proposed approach
outperforms the geometric mean which is a good sanity check. It is surprising
that the geometric mean performs quite well in MQ2007. The major difference is
that we are imputing the missing ranks, and the other methods suffer from
assigning them to an arbitrary value. This demonstrates the importance of
imputation.

###  6.4 Strictly ordered labels

One issue with the benchmark aggregation dataset is that the labels are only
{0,1,2} relevance scores, and hence it is unclear exactly what the rankings
are within the relevance classes. We create a new dataset which is formed by
taking the intersection between the documents retrieved by a particular query
between MQ2007-agg and MQ2007-list. This new dataset contains the strictly
ordered labels from MQ2007-list, but uses the aggregation data from
MQ2007-agg. The same procedure is used to create the corresponding dataset for
MQ2008-agg and MQ2008-list. These datasets are available for download at the
LETOR website. We maintain exactly the same 5-fold cross validation splits and
report our results in table 3.

Considering the results for Spearman’s , we observe that our learning method
performs well. Note that the geometric mean outperforms Borda count on both
datasets, which confirms that our theoretically justified model performs
better than the heuristic model. It is interesting to observe that optimising
for Spearman’s could result in a decrease in Kendall’s . This demonstrates the
importance of choosing the appropriate objective function for learning.

Table 3: Results on MQ2007-agglist and MQ2008-agglist. The left column shows the results for multivariate Spearman’s and the right column shows the result for Kendall’s . | MQ2007-agglist | MQ2008-agglist
---|---|---
Method |  |  |  |
RAGS-⊤ | 0.4394 | 0.6201 | 0.7235 | 0.6931
RAGS-⊥ | 0.2992 | 0.2488 | 0.6349 | 0.5560
GeoMean | 0.2457 | 0.3011 | 0.5777 | 0.6578
Borda | 0.2217 | 0.1790 | 0.5519 | 0.5869

##  7 Discussion and Conclusion

We propose an approach for learning weights between experts for the task of
rank aggregation. By generalising the derivation of concordance functions, we
obtain an expression for multivariate Spearman’s . Furthermore we show that
the geometric mean of the expert ranks is the optimal aggregator under
Spearman’s correlation. Motivated by this, our method solves a least squares
estimation problem for logarithmic normalised ranks to find optimal weights.

One possible extension of our work is to compute the correlation for all
possible subsets of rankings. While corollary 15 shows that the overall
correlation cannot be negative as the number of rankings increase, there may
be subgroups which are positively correlated within groups but negatively
correlated between groups. By computing the correlation on the power set, we
could use a clustering method to find such subgroups.

Though we have focused on $\rho_{d}^{+}$, our results are equally applicable
to $\rho_{d}^{-}$; indeed it is a simple reversal of ranks that give
$\rho_{d}^{-}$. The choice between $\rho_{d}^{+}$ and $\rho_{d}^{-}$ is thus
problem dependent: for tasks where being ranked highly is more informative
$\rho_{d}^{+}$ is a better choice; conversely $\rho_{d}^{-}$ is more suitable
for tasks where being ranked lowly is more informative.

In contrast to other rank aggregation approaches, our method is very
computationally efficient. However, the core of our method requires a complete
set of rankings and hence does not handle missing variables. To resolve this,
we propose three imputation methods (unbiased, optimistic, pessimistic) for
completing top-$k$ ranked lists that allows us to apply Spearman’s to
aggregate ranks from partial lists. Our method is thus applicable for large
scale applications with top-$k$ rankings that arise in areas such as text
mining and bioinformatics. One subtlety is that imputation from top-$k$ should
not be confused with the choice of using $\rho_{d}^{+}$, which is an separate
design choice.

Surprisingly, our weighted geometric mean shows state of the art results on
benchmark datasets, without the need for tuning hyperparameters or expensive
computation. The simplicity of our model makes it easier to interpret, and the
weights give a direct estimate of the influence of each expert. This problem
has wide applications to ensemble learning, voting, text mining, recommender
systems and bioinformatics.

##  8 Acknowledgements

This work was completed when both authors were employed by NICTA. NICTA was
funded by the Australian Government through the Department of Communications
and the Australian Research Council through the ICT Centre of Excellence
Program.

##  A Bivariate Spearman’s and Squared Distance

This well known
result333http://en.wikipedia.org/wiki/Spearman’s_rank_correlation_coefficient
accessed on 20 May 2014 shows that Spearman’s can be expressed in terms of the
squared distance between ranks.

In the following derivation, we use the expressions for the sum of integers
and the sum of squares of integers:

$\sum_{k=1}^{n}k_{i}=\frac{n(n+1)}{2}\qquad\sum_{k=1}^{n}k_{i}^{2}=\frac{n(n+1)(2n+1)}{6}.$

Recall that Spearman is defined (1) as:

$\rho_{n}=\frac{\sum_{x}(R(x)-\bar{R})(S(x)-\bar{S})}{\sqrt{\sum_{x}{(R(x)-\bar{R})}^{2}\sum_{x}{(S(x)-\bar{S})}^{2}}}$

Since there are no ties, both $R(x)$ and $S(x)$ consist of integers from 1 to
$n$ inclusive, and the two squared sums in the denominator are the same.
Recall that the mean rank is

$\bar{R}=\bar{S}=\frac{n+1}{2},\quad\mbox{and}\quad\sum_{x}R(x)=\frac{n(n+1)}{2}=n\bar{R}.$

Therefore the denominator can be expressed as a function of $n$.

$\displaystyle\sqrt{\sum_{x}{(R(x)-\bar{R})}^{2}\sum_{x}{(S(x)-\bar{S})}^{2}}$
$\displaystyle=\sum_{x}{(R(x)-\bar{R})}^{2}$
$\displaystyle=\sum_{x}({R(x)}^{2}-2R(x)\bar{R}+\bar{R}^{2})$
$\displaystyle=\sum_{x}{R(x)}^{2}-2\bar{R}\sum_{x}R(x)+n\bar{R}^{2}$
$\displaystyle=\sum_{x}{R(x)}^{2}-n\bar{R}^{2}$
$\displaystyle=\frac{n(n+1)(2n+1)}{6}-n{\left(\frac{n+1}{2}\right)}^{2}$
$\displaystyle=n(n+1)\left(\frac{2n+1}{6}-\frac{n+1}{4}\right)$
$\displaystyle=n(n+1)\left(\frac{n-1}{12}\right)$
$\displaystyle=\frac{n(n^{2}-1)}{12}$

Since both $R(x)$ and $S(x)$ consists of the same integers, we can express the
squared difference in terms of the product.

$\displaystyle\sum_{x}\frac{1}{2}{(R(x)-S(x))}^{2}$
$\displaystyle=\sum_{x}\frac{1}{2}({R(x)}^{2}-2R(x)S(x)+{S(x)}^{2})$
$\displaystyle=\sum_{x}\frac{1}{2}({R(x)}^{2}+{S(x)}^{2})-\sum_{x}R(x)S(x)$
$\displaystyle=\sum_{x}{R(x)}^{2}-\sum_{x}R(x)S(x)$

where the first term is a function of $n$.

We express the product of the means, which appears in the numerator later, to
match the denominator:

$\displaystyle n{\left(\frac{n+1}{2}\right)}^{2}$
$\displaystyle=\frac{n(n+1)}{12}3(n+1)$
$\displaystyle=-\frac{n(n+1)}{12}[(n-1)-(4n+2)]$
$\displaystyle=-\frac{n(n+1)(n-1)}{12}+\frac{n(n+1)(2n+1)}{6}$
$\displaystyle=-\frac{n(n^{2}-1)}{12}+\sum_{x}{R(x)}^{2}$

where the last term in the sum is the expression for the sum of squares. We
can now derive the expression for the numerator:

$\displaystyle\sum_{x}(R(x)-\bar{R})(S(x)-\bar{S})$
$\displaystyle=\sum_{x}R(x)S(x)-\bar{R}\sum_{x}S(x)-\bar{S}\sum_{x}R(x)+n\bar{R}\bar{S}$
$\displaystyle=\sum_{x}R(x)S(x)-n\bar{R}\bar{S}$
$\displaystyle=\sum_{x}R(x)S(x)-n{\left(\frac{n+1}{2}\right)}^{2}$
$\displaystyle=\sum_{x}R(x)S(x)+\frac{n(n^{2}-1)}{12}-\sum_{x}{R(x)}^{2}$
$\displaystyle=\frac{n(n^{2}-1)}{12}-\sum_{x}\frac{1}{2}{(R(x)-S(x))}^{2}$

where the last line uses the expression of the sum of squared differences
above. Putting together the expressions for the numerator and denominator
together gives the desired result:

$\rho_{n}=1-\frac{6\sum_{x}{(R(x)-S(x))}^{2}}{n(n^{2}-1)}$

##  B University aggregate rankings

Rank | University
---|---
1 | Harvard University
2 | Massachusetts Institute of Technology
3 | Stanford University
4 | California Institute of Technology
5 | University of Cambridge
6 | University of Oxford
7 | Princeton University
8 | University of Chicago
9 | University of California, Berkeley
10 | Imperial College London
11 | ETH Zurich
12 | University College London
13 | Yale University
14 | Columbia University
15 | Johns Hopkins University
16 | Cornell University
17 | University of California, Los Angeles
18 | University of Pennsylvania
19 | University of Michigan
20 | University of Toronto
21 | Duke University
22 | Northwestern University
23 | University of Edinburgh
24 | University of California, San Diego
25 | King’s College London
26 | University of Washington
27 | University of Tokyo
28 | National University of Singapore
29 | New York University
30 | École Polytechnique Fédérale de Lausanne
31 | McGill University
32 | University of Melbourne
33 | University of Illinois at Urbana–Champaign
34 | University of Wisconsin–Madison
35 | University of British Columbia
36 | University of Manchester
37 | Australian National University

## References

  * Critchlow (1985) Douglas E. Critchlow.  _Metric Methods for Analyzing Partially Ranked Data_.  Springer-Verlag, 1985.
  * Diaconis (1988) Persi Diaconis.  _Group representations in probability and statistics_ , volume 11 of _Lecture Notes – Monograph Series_.  Institute of Mathematical Statistics, 1988.
  * Elidan (2013) Gal Elidan.  Copulas in machine learning.  In _Copulae in Mathematical and Quantitative Finance_ , 2013.
  * Fligner and Verducci (1986) M.A. Fligner and J.S. Verducci.  Distance based ranking models.  _Journal of the Royal Statistical Society. Series B (Methodological)_ , pages 359–369, 1986.
  * Genest and Favre (2007) Christian Genest and Anne-Catherine Favre.  Everything you always wanted to know about copula modeling but were afraid to ask.  _Journal of Hydrologic Engineering_ , 12(4):347–368, 2007.
  * Iyer and Bilmes (2012) Rishabh Iyer and Jeff Bilmes.  The submodular Bregman and Lovász-Bregman divergences with applications.  In _NIPS_ , 2012.
  * Iyer and Bilmes (2013) Rishabh Iyer and Jeff Bilmes.  The Lovász-Bregman divergence and connections to rank aggregation, clustering and web ranking.  In _UAI_ , 2013.
  * Joe (1990) Harry Joe.  Multivariate concordance.  _Journal of Multivariate Analysis_ , 35:12–30, 1990.
  * Joe (2014) Harry Joe.  _Dependence Modeling with Copulas_.  CRC Press, 2014.
  * Klementiev et al. (2008) Alexandre Klementiev, Dan Roth, and Kevin Small.  Unsupervised rank aggregation with distance-based models.  In _International Conference on Machine Learning_ , 2008.
  * Lebanon and Mao (2008) Guy Lebanon and Yi Mao.  Non-parametric modeling of partially ranked data.  _Journal of Machine Learning Research_ , 9:2401–2429, 2008\.
  * Liu (2011) Tie-Yan Liu.  _Learning to Rank for Information Retrieval_.  Springer-Verlag, 2011.
  * Mallows (1957) C. L. Mallows.  Non-null ranking models.  _Biometrika_ , 44(1):114–130, 1957.
  * Nelsen (1996) Roger B. Nelsen.  Nonparametric measures of multivariate association.  _Distributions with Fixed Marginals and Related Topics_ , 28:223–232, 1996.
  * Nelsen (2006) Roger B. Nelsen.  _An Introduction to Copulas_.  Springer, second edition, 2006.
  * Niu et al. (2012) Shuzi Niu, Jiafeng Guo, Yanyan Lan, and Xueqi Cheng.  Top-k learning to rank: Labeling, ranking and evaluation.  In _SIGIR_ , pages 751–760, 2012.  ISBN 9781450314725.
  * Niu et al. (2013) Shuzi Niu, Yanyan Lan, Jiafeng Guo, and Xueqi Cheng.  Stochastic rank aggregation.  In _UAI_ , 2013.
  * Qin et al. (2010a) Tao Qin, Xiubo Geng, and Tie-Yan Liu.  A new probabilistic model for rank aggregation.  In _NIPS_ , 2010a.
  * Qin et al. (2010b) Tao Qin, Tie-Yan Liu, Jun Xu, and Hang Li.  LETOR: A benchmark collection for research on learning to rank for information retrieval.  _Information Retrieval Journal_ , 2010b.
  * Schmid and Schmidt (2007) Friedrich Schmid and Rafael Schmidt.  Multivariate extensions of spearman’s rho and related statistics.  _Statistics & Probability Letters_, 77:407–416, 2007\.
  * Schmid et al. (2010) Friedrich Schmid, Rafael Schmidt, Thomas Blumentritt, Sandra Gaisser, and Martin Ruppert.  Copula-based measures of multivariate association.  In _Copula Theory and Its Applications_ , pages 209–236, 2010.
  * Sculley (2010) D. Sculley.  Combined regression and ranking.  In _KDD_ , 2010.
  * Spearman (1904) C. Spearman.  The proof and measurement of association between two things.  _The American Journal of Psychology_ , 15(1):72–101, 1904.
  * Taylor (2007) Michael. D. Taylor.  Multivariate measures of concordance.  _Annals of the Institute of Statistical Mathematics_ , 59(4):789–806, 2007.
  * Trivedi and Zimmer (2005) Pravin K. Trivedi and David M. Zimmer.  Copula modeling: An introduction for practitioners.  _Foundations and Trends in Econometrics_ , 1(1):1–111, 2005.
  * Úbeda Flores (2005) Manuel Úbeda Flores.  Multivariate versions of blomqvist’s beta and spearman’s footrule.  _Annals of the Institute of Statistics and Mathematics_ , (4):781–788, 2005.
  * Volkovs and Zemel (2012) Maksims N. Volkovs and Richard S. Zemel.  A flexible generative model for preference aggregation.  In _WWW_ , 2012.