T. Kamishima, H. Kazawa, and S. Akaho "A Survey and Empirical Comparison of Object
Ranking Methods" In J. Fürnkranz and E. Hüllermeier, editors, Preference Learning, pp.
181–201. Springer (2010)
UNOFFICIAL VERSIONA Survey and Empirical Comparison of Object
Ranking Methods
Toshihiro Kamishima1 , Hideto Kazawa2 , and Shotaro Akaho1
1

National Institute of Advanced Industrial Science and Technology (AIST),AIST Tsukuba Central 2, Umezono 1–1–1, Tsukuba, Ibaraki, 305–8568 Japan,
mail@kamishima.net〈http://www.kamishima.net/〉, s.akaho@aist.go.jp
2
Google Japan Inc., Cerulean Tower 6F, 26-1 Sakuragaoka-cho, Sibuya-ku, Tokyo,
kazawa@google.com

Abstract. Ordered lists of objects are widely used as representational
forms. Such ordered objects include Web search results or bestseller lists.
In spite of their importance, methods of processing orders have received
little attention. However, research concerning orders has recently becomecommon; in particular, researchers have developed various methods forthe task of Object Ranking to acquire functions for object sorting fromexample orders. Here, we give a uniﬁed view of these methods and compare their merits and demerits.

1

Introduction

We survey methods for learning to estimate orders, and empirically compare
these methods. The term Order indicates a sorted sequence of objects according
to some property. For example, the responses from Web search engines are listsof pages sorted according to their relevance to queries. Best-seller lists, which are
item-sequence sorted according to sales volume, are used on many E-commercesites. In particular, several methods have been developed for learning functions
used to sort objects from example orders. We call this task Object Ranking andemphasize its usefulness for sensory surveys3 , information retrieval, and decision
making. We give a uniﬁed view of the object ranking task that are independently
proposed and discuss the connection with the other types of tasks dealing withorders. We then show experimental results to reveal the pros and cons of theseobject ranking methods.
We formalize the object ranking task in Section 2. We survey methods in
Section 3. Experimental results on artiﬁcial data and on real data are shown in
Sections 4 and 5, respectively. We discuss and summarize the results in Section 6.

2

Orders and Object Ranking

This section shows basic notions regarding orders and formalizes the object ranking task.
3

quantiﬁcation of respondents’ sensations or impressions

2

2.1

Kamishima, Kazawa, Akaho

Basics about Orders

We begin by deﬁning basic notations regarding orders. An object or entity
to be sorted is denoted by xj . The universal object set, X ∗ , consists of all
possible objects. Each object xj is represented by the attribute value vector
xj = [xj1 , xj2 , . . . , xjk ]⊤ , where k is the number of attributes. An order is denoted by O = xja ≻xjb ≻ · · · ≻xjc . Note that the subscript j of xj doesn’t mean
“The j-th object in this order,” but that “The object is uniquely indexed by j
in X ∗ .” An order x1 ≻x2 represents “x1 precedes x2 .” An object set X (Oi ) or
simply Xi is composed of all the objects in the order Oi . The length of Oi , i.e.,|Xi |, is shortly denoted by Li . An order of all objects, i.e., Oi s.t. X (Oi ) = X ∗ ,is called a complete order; otherwise, the order is incomplete. Rank, r(Oi , xj ) or
simply rij , is the cardinal number that indicates the position of the object xj inthe order Oi . For example, for Oi =x1 ≻x3 ≻x2 , r(Oi , x2 ) or ri2 is 3. For two orders, O1 and O2 , consider an object pair xa and xb such that xa , xb ∈X1 ∩X2 , a̸=b.
These two orders are concordant w.r.t. xa and xb if the two objects are placedin the same order, i.e., (r1a − r1b )(r2a − r2b ) ≥ 0; otherwise, they are discordant.
Further, O1 and O2 are concordant if O1 and O2 are concordant w.r.t. all object
pairs such that xa , xb ∈X1 ∩X2 , a̸=b.
We then describe the distance between two orders, O1 and O2 , composed of
the same sets of objects, i.e., X (O1 ) = X (O2 ) ≡ X . Various kinds of distancefor orders have been proposed [1]. Spearman distance dS (O1 , O2 ) is widely used.
It is deﬁned as the sum of the squared diﬀerences between ranks:dS (O1 , O2 ) =∑ ()2
r1j − r2j .

(1)

xj ∈X

By normalizing the range to be [−1, 1], Spearman’s rank correlation ρ is derived.
ρ=1−

6dS (O1 , O2 ),L3 − L(2)

where L is the length of orders, i.e., L = |X |. This exactly equals the correlationcoeﬃcient between ranks of objects. The Kendall distance dK (O1 , O2 ) is anotherwidely used distance. Consider a set of object pairs, {(xa , xb ) ∈ X × X }, a ̸=b, xa , xb ∈ X , including either (xa , xb ) or (xb , xa ). The Kendall distance isdeﬁned as the number of discordant pairs between O1 and O2 w.r.t. xa and xb .
Formally,dK (O1 , O2 )=

1(
M−
2

∑

(
))
sgn (r1a −r1b )(r2a −r2b ) ,(3){(xa ,xb )}where sgn(x) is a sign function that takes 1 if x>0, 0 if x=0, and −1 otherwise.
M = (L − 1)L/2 is the number of all object pairs. By normalizing the range toA Survey and Empirical Comparison of Object Ranking Methods3

be [−1, 1], Kendall’s rank correlation τ is derived.
2dK (O1 , O2 )
M
∑
(
)
1
=
sgn (r1a −r1b )(r2a −r2b ) .
Mτ =1 −(4){(xa ,xb )}The computational costs for deriving ρ and τ are O(L log L) and O(L2 ), respectively. The values of τ and ρ are highly correlated, because the diﬀerence
between two criteria is bounded by Daniels’ inequality [2]:−1 ≤3(L + 2)2(L + 1)τ−ρ ≤ 1.
L−2
L−2

(5)

Another inequality between dK and dS is Durbin-Stuart’s inequality:()
4
dK
dS ≥ dK 1 +.
3
LIn [1], you can ﬁnd further description about other types of distance, such as
Spearman’s footrule, Cayley distance, and Ulam distance, and their characteristics.
Note that dK is a metric, but dS is not due to the violation of the triangularinequality condition. If two or more objects are tied, we give the same midrankto these objects [1]. For example, consider an order x5 ≻x2 ∼x3 (“∼” denotes tie
in rank), in which x2 and x3 are ranked at the 2nd or 3rd positions. In this case,the midrank 2.5 is assigned to both objects.
2.2

An Object Ranking Task

S
O1 = x1 ≻x2 ≻x3

O2 = x1 ≻x5 ≻x2

randompermutation!

regression orderŌ¯∗ = x1 ≻x5 ≻x2 ≻x4 ≻x3

O3 = x2 ≻x1!

!

concordant

Xu x
x3

1

x5 x4

unordered objects

rankingfunctionÔu = x1 ≻x5 ≻x4 ≻x3estimated orderFig. 1. The object ranking task

4Kamishima, Kazawa, Akaho

An Object Ranking task can be considered a regression or a ﬁtting task whosetarget variables are orders. Further, input samples comprise not a set of vectors,
but a set of orders, S = {O1 , . . . , ON }, where N is the number of samples. The
regression curve corresponds to a regression order. Analogous to the case of aregression function, a regression order is estimated so as to be concordant not
only with given sample orders in S, but also with orders that will be generated
in future. This task diﬀers from a regression in two ways. First, since the target variables are orders, the modeling methods of regression orders and errors
are needed. A regression order is modeled by a ranking function, ord(·), which
represents a rule for sorting objects. Given an object set Xu , a ranking function
outputs the ideal order that consists of all objects in Xu . Though errors of realvalues are modeled by an additive term of a random variable, errors in orders
are modeled by a random permutation ε(·). That is to say, a sample order Oi is
generated by ε(ord(Xi )). Second, since sample orders are generally incomplete,there may be objects not observed in given samples (e.g., x4 in Figure 1). Such
objects should be ranked under the assumption that the neighboring objects inthe attribute space would be close in rank. Object ranking is also diﬀerent fromclassiﬁcation, because no ordinal relations should be deﬁned between classes.
We say that a ranking function is absolute if outputs of the function areconcordant with each other; otherwise, it is relative. That is to say, for any
Xu ⊆ X ∗ , while an absolute ranking function outputs orders that are concordant
with orders a regression order that consists of all objects in X ∗ , a relative ranking
function does not. Being absolute is also equivalent to the condition 3, “Theindependence of irrelevant alternatives,” of the Arrow’s impossibility theorem[3]. Concretely, given unordered sets {x1 , x2 , x3 } and {x1 , x2 , x4 }, an absolute
ranking function outputs orders that are concordant w.r.t. x1 and x2 regardless ofthe existence of objects x3 or x4 . However, a relative ranking function diﬀerently
sorts x1 and x2 due to the existence of the other objects, e.g., x1 ≻ x2 ≻ x3 andx2 ≻ x4 ≻ x1 . An absolute ranking function would be preferable in applications
such as ﬁltering or recommendation. For example, if one prefers an apple to anorange, he/she will always rank an apple higher than an orange when sorting
any set of fruits according to degree of preference. One example application
appropriate for relative ranking can be found in [4]. When summarizing multidocuments, after extracting important sentences, these sentences are ordered. In
this case, appropriate order of sentences would be aﬀected by the other extracted
sentences.
Object ranking is closely related to a notion of a Center of Orders [1]; given
sample orders∑S, center Ō is deﬁned as the order that minimizes the sum of
the distances Oi ∈S d(Oi , P (Ō, Xi )). Note that P (Ō, Xi ) denotes the projectionof Ō on the set Xi , which is the order that consists of the objects in Xi andis concordant with Ō. This notion is also referred by the other terms, such as
aggregated ranking [5], in machine learning or information retrieval disciplines.
We here adopt the term “center of orders” in statistics, because this would be
the ﬁrstly given denotation. This center diﬀers from the above regression orderin the points that concordance only with given samples is considered and that

A Survey and Empirical Comparison of Object Ranking Methods

5

no description of objects, e.g., attribute values, is employed. The computation ofcenters is generally NP-hard, except for the cases such as employing Spearman’s
distance.
Object ranking is also related to Ordinal Regression [6, 7], which is a regression whose type of dependent variables is ordered categorical. Ordered categorical variables can take one of a ﬁnite set of predeﬁned values, like categoricalvariables, and order these values additionally; for example, a domain of a variable is {“good”,“fair”,“poor”}. Ordered categories and orders are diﬀerent in
two points. First, while orders provide purely relative information, ordered categorical values additionally include absolute information. For example, while
the category “good” means absolutely good, x1 ≻ x2 means that x1 is relatively better than x2 . Second, the number of grades that can be represented byordered categorical variables is limited. Consider that there are four objects. Because at least two objects must be categorized into one of the three categories,{“good”,“fair”,“poor”}, the grades of these two objects are indistinguishable.
However, orders can represent the diﬀerences of grades between any two objects.
Because a task of object ranking is more complicated than ordinal regression,
object ranking methods can be applicable to solve ordinal regression, but theconverse is not true. But, generally speaking, since it is not eﬃcient to solve toomuch complicated tasks, these two tasks should be carefully diﬀerentiated. For
example, the computational cost of SVMs for object ranking (see Table 3) isabout the square of O(N 2 L̄4 ), where L̄ is the mean length of sample orders. The
SVM specially designed for ordinal regression [8] demands less computational
cost O(N 2 |Y|2 ), where |Y| is the number of grades.

3

Object Ranking Methods

We present ﬁve object ranking methods. Their abbreviations are given in parentheses in the section titles.
3.1

Cohen’s method (Cohen)

Cohen’s method [9] is designed to ﬁnd the order Ôu that maximizes∑
P[xa ≻xb |xa , xb ],(6)xa ≻xb ∈Ôuwhere P[xa ≻xb |xa , xb ] is the conditional probability given the attribute vectorsof xa and xb , and xa ≻xb ∈ Ôu denotes all the ordered pairs concordant with Ôu .
Note that Ou consists of all the objects in a given set of unordered objects, Xu .
Unfortunately, because the maximization of Equation (6) is known as a linear
ordering problem [10], which is NP-hard, it is not tractable to ﬁnd the optimal
solution if |Xu | is large. Cohen et al. hence proposed a greedy algorithm that sequentially chooses the most-preceding object in Figure 2. They proposed a moreelaborate approximation method too, but any strict or approximation algorithms
to solve the linear ordering problem [10] can be applied for this optimization.

6

Kamishima, Kazawa, Akaho
1: Ôu ← ∅2: for all x ∈ XuPdo
3:
score(x) ← x′ ∈Xu P[x≻x′ |x, x′ ]4: end for
5: while Xu ̸= ∅ do
6:
xtop ← arg maxx score(x)7:Ôu ← Ôu ≻xtop , Xu ← Xu − {xtop }8:
for all x ∈ Xu do
9:score(x) ← score(x) − P[x≻xtop |x, xtop ]10:
end for
11: end while
12: return ÔuFig. 2. Cohen’s greedy sorting algorithm

P[xa ≻xb |xa , xb ] is learned by Cohen et al.’s Hedge algorithm. The Hedge isan online algorithm, which is a variant of the Winnow [11]. Pairwise preference
judgments are determined based on the linear combination of subordinate ordering functions. Given one preference feedback sample, a weight for an orderingfunction is increased according as the β parameter and the contribution of theordering function to the concordance with the feedback. We set the β to 0.9;
the attributes {xjl , −xjl }kl=1 are used as ordering functions in our experiments.
To use the Hedge algorithm in oﬀ-line mode, the objects in S are iteratively
given as feedback, and iterations are repeated until the loss becomes stationary.
Their Hedge algorithm is designed so that it takes only ordinal information of
attributes into account and discards the numerical values themselves. Hence, ourexperimental condition in which objects are represented by nominal or numericalattributes are rather disadvantageous to this method.
3.2

RankBoost (RB)Freund et al. proposed RankBoost [12, 13], that is a boosting algorithm targetingorders. Inputs of the RankBoost are the feedback function Φ(xa , xb ), which implies xb ≻ xa if Φ(xa , xb ) > 0, and a set of ranking features fl (xi ), which conveys
partial information about the target ordering. Given these inputs, RankBoost
returns the ﬁnal ranking H(xi ) that works as a score function. First, the initial distribution is calculated by D1 (xa , xb ) = max(Φ(xa , xb ), 0)/Z1 , where Z1
is a normalization coeﬃcient. Then, for each round t = 1, . . . , T , the algorithm
repeats the selection of weight αt and weak learner ht (x), and the update of
distribution by:
Dt+1 (xa , xb ) =()
1
Dt (xa , xb ) exp αt (ht (xa ) − ht (xb )) .
Zt

Weak learners capture some information about target orders from ranking features, and output hypotheses such that ht (xb )>ht (xa ) implies xb ≻xa . αt and ht
are selected so that the normalization factor Zt is minimized. Once these weights

A Survey and Empirical Comparison of Object Ranking Methods

7

and weak learners∑are acquired, unseen objects, x ∈ X ∗ , are sorted in descendingTorder of H(x) = t=1 αt ht (x).
In our experiment, as ranking features, we adopt all terms that appear in
n-order polynomials of object attributes after attribute values are transformed
so as to range in [0, 1]. Let Φ(xa , xb ) be 2P[xb ≻xa ] − 1. Weak learners are set toranking features themselves, i.e., h(x) = fl (x). Selection method of αt and ht isthe third option in section 3.2 in [13]. The number of rounds, T is set to 100.
3.3

SVM-based methods: Order SVM (OSVM) and Herbrich’s
method (SVOR)

We show two SVM-based methods: OrderSVM and SVOR. In summary, theformer is designed to discriminate whether or not a given object is ranked higher
than j-th, while the latter judges which of two objects precedes the other.
Since this paper concerns not categorical but ordinal rank, this method may
appear to be a groundless attempt to discriminate high-ranked objects from lowranked ones. However, we showed that the probability of ﬁnding an object sorted
above a ﬁxed rank is concordant with the true score function. Thus, if a classiﬁer
will discriminate the top j objects from the rest, its discrimination function must
be concordant to some extent with probability and therefore with the true scorefunction. This observation leads to the use of SVM as the estimator of a scorefunction in [14].
We ﬁrst show Order SVM [14]. To enhance the reliability of this estimation,
we proposed training multiple SVMs with diﬀerent threshold ranks and sorting
unseen objects using the average of those SVMs. Its learning is formulated as
the following optimization problem:
L−1
L−1
m ∑
L
∑∑
1
λ∑
∥w∥2 +∥vt ∥2 + C
ξij (t)w,vt ,bt 2
2 t=1
t=1 i=1 j=1

mins.t. sgn[j−t]((w+vt )·xji + bt ) ≥ 1 − ξij (t), ξij (t) ≥ 0,

(7)

forall i, j, t,

where xji is the feature vector of the j-th ranked object in the i-th order,{xji }j=1...L
i=1...m are the training samples, and C and λ are hyperparameters. In our
experiments, we set C = 0.1 and λ = 1 based on preparatory experiments ona small data set. The sgn[z] is 1 if z ≥ 0; otherwise, −1. The SVM that discriminates the top t objects
from the rest is ft (x) = (w + vt ) · x + bt . Thus,∑
the second regularizer t ∥vt ∥2 makes all ft (x) agree on the predicted orders asmuch as possible. The order is predicted by sorting objects according to the score
w · x. The dual problem of Equation (7) is similar to that of standard SVMs,
and any kernel function can be used instead of the inner products between feature vectors [14]. This method performs discriminations whether an object isranked higher than t for each t = 1, . . . , L−1. The number of failures in these
discriminations is equivalent to the absolute diﬀerence between object ranks inthe estimated order and sample order. These diﬀerences are then summed up

8Kamishima, Kazawa, Akaho

over all objects in orders. This sum can be considered as representing Spearman footrule [1], which is absolute distance between two orders. Therefore, thismethod aims minimizing the sum of distances in Spearman footrule between an
estimated order and each sample order.
We refer to the other SVM-based method as Support Vector Ordinal Regression (SVOR) [15] since its formulation is very similar to standard SVMs and thework on it appears to be inspired by that of past ordinal regression works [16].
This method was independently developed as Ranking SVM by Joachims [17]and was proposed in [18].
SVOR discriminates correctly ordered pairs from incorrectly ordered pairs. In
contrast to the Cohen method in which precedences are independently learned
from pairs and there is no guarantee that transitivity holds among the learned
preferences, SVOR uses a single score function for learning and thus avoids theintractability problem of the sorting process shown in [9].
SVOR’s learning is formulated as the following optimization problem:m∑1
min ∥w∥2 + C
w 2
i=1

s.t. w·(xij − xli )≥1−ξijl ,ξijl ≥0,

∑

ξijl

(8)

1≤j<l≤Lfor ∀ i, j < l,where the same notations as OSVM are used for xji , m, L, and C (In our experiments, C = 1). SVOR tries to ﬁnd the direction w along which sample objects
are ordered so that the narrowest separation between samples is maximal. The
prediction of orders is done by sorting objects according to the score w · x. As
in the case of OSVM, the dual problem of Equation (8) can be written using only
the inner products of x; thus we can use any kernel function in SVOR, as well.
This method is designed so that for each object pair in orders, the discrimination
whether one object precedes the other is performed. The number of failures inthese discriminations is equivalent to Kendall distance. Therefore, this method
aims minimizing the sum of distances in Kendall distance between an estimatedorder and each sample order.

3.4

Expected Rank Regression (ERR)

We turn to our Expected Rank Regression method [19]. In this method, after
expected ranks of objects are derived, the function to estimate these expected
ranks is learned using a standard regression technique.
To derive expected ranks, assume that orders Oi ∈ S are generated as follows:First, a complete sample order Oi∗ , which cannot be observed and consists of all
objects in X ∗ , is generated. |X ∗ | − |Oi | objects are then selected uniformly at
random, and these are eliminated from Oi∗ ; then, the Oi is observed. Under thisassumption, a theoretical result in order statistics [20] shows that the conditional
expectation of rank of the object xj ∈ Xi in the unobserved complete order Oi∗
given the sample order Oi is
E[r(Oi∗ , xj )|Oi ] ∝r(Oi , xj ).
|Oi | + 1

(9)

A Survey and Empirical Comparison of Object Ranking Methods

9

These expected ranks are calculated for all the objects in all the orders in asample set S. Next, standard regression techniques are applied to derive weightsof regression function, f (xj ), which predicts the above expectation of ranks.
Samples for regression consist of the attribute vectors of objects, xj , and theircorresponding expected ranks, r(Oi , xj )/(|Oi | + 1); thus the number of samples∑
becomes Oi ∈S |X (Oi )|. Once weights of f (xj ) are learned, the order Ôu can be
estimated by sorting the objects xj ∈ Xu according to the corresponding valuesof f (xj ).
Below, we describe a rationale why this ERR works: We assume that sample
orders are generated according to the Thurstone’s model (case V) [21]. In thismodel, sample orders are generated by sorting objects x ∈ Xu in the ascendingorder of the scores, x, f ∗ (x), that follow the following normal distribution:f ∗ (x) ∼ N (µ(x), σ 2 ),(10)

where µ(x) and σ are mean and standard deviation, respectively. A complete
regression order, Ō∗ , is determined by sorting all objects in X ∗ in the ascendingorder of the mean scores µ(x), and random permutation is caused by the additivenoise in scores of objects; the above complete sample orders, Oi∗ , i = 1, . . . , |S|,are consequently generated. Next, we consider the probability that a pair of adjacent objects in Ō∗ permutes. We assume that such probabilities are equal over
all adjacent pairs, because there is no prior information that one pair is more
frequently permuted than the other pair. This assumption makes the diﬀerencesof the mean scores between these adjacent pairs, |µ(xi ) − µ(xj )|, to be constant.
Further, these mean can be replaced with rank in Ō∗ without loss of generality,
because an order derived based on scores is invariant for any linear transformation in scores. We then learn a function to predict rank r(Ô∗ , x) for any object
x. Expectations of these ranks over random elimination of objects can be obtained by equation (9), and noise in scores follows normal distribution as in 10.
Consequently, we can estimate ranks in Ō∗ by applying standard regression to
samples, (xj , r(Oi , xj )/(|Oi | + 1)).
In our experiments, n-order polynomials are adopted as a class of regressionfunctions. No regularization terms were adopted in regression.

4

Experiments on Artiﬁcial Data

To reveal the characteristics of object ranking methods, we applied these methods to artiﬁcial data.
4.1

Experimental Conditions

Artiﬁcial data were generated in three steps. First, we generated two types ofvectors: numerical (num) and binary (bin). Each numerical vector consists of5(≡k) attributes, which follow the normal distribution, N (0, 1). Binary vectors
are composed of 15(≡k) attributes, and are randomly generated so that every

10Kamishima, Kazawa, Akaho

object is represented by diﬀerent value vectors. Note that, when the methods
designed for numeric attributes, binary values are converted to the number, 0 or
1. Second, true regression orders are determined based on these attribute values.
Objects are sorted according to the values of the function:utility(xj )=(1 +k∑wl xjl )dim ,l=1

where wl are random weights that follow the normal distribution, N (0, 1). We
tested two settings: linear (dim=1) and non-linear (dim=2 or 3), denoted byli and nl, respectively. Finally, N sample orders Oi ∈ S were generated byrandomly eliminating objects from the true regression orders.
As an error measure, we used Spearman’s ρ (Equation (2)) between theestimated order and the above true regression order. If ρ is 1, the two orders arecompletely concordant; if it is −1, one order is the reverse of the other. We willshow the means of ρ over a 10-fold cross validation for 10 diﬀerent weight sets ofutility(xj ). Regardless of the length of training orders, the size of the unorderedset, |Xu |, is set to 10, because errors cannot be precisely measured if orders are
too short.
4.2

Experimental Results

As the basic experimental condition, we chose N =300, Li =5, and |X ∗ |=1000.
Under this condition, the probability that one object in Xu is unobserved in the
training samples seems rather low (25.8%). However, the probability that theobject pairs in Xu become unobserved, which is intrinsic to ordinal relations,is fully high (99.5%). Therefore, we consider that this data set is well suited
to evaluate the generalization ability. Note that algorithm parameter settings
described in Section 3 are tuned for this basic condition under a noisy condition
described later. By default, we used this basic condition in the following experiments. The other settings were: For Cohen, we adopt their Hedge and their greedy
search algorithm. Note that we also applied the exhaustive search to derive theoptimal orders that maximizes equation (6), but the results were rather inferior
to that by the greedy search in Figure 2. For RB, ranking features are all termsof a second-order polynomial. For SVOR and OSVM, Gaussian kernels with σ = 1
were used. For ERR, the second-order polynomials was used as class of regressionfunctions.
Table 1(a) shows the means of ρ under this basic setting. Each row corresponds to each of the four data sets described in Section 4.1, and each column
corresponds to each method in Section 3. The rank of each method is shown inbrackets. Except for the diﬀerence between RB and SVOR of nl/bin, the diﬀerence between each method and the next-ranked one is statistically signiﬁcant at
the level of 1% when using a paired t-test and a Bonferroni multiple comparison.
Defects of the Cohen would be due to the fact that only the ordinal informationof attributes is considered, as described in Section 3.1. The ERR methods wereinferior in bin cases, but were superior in num cases. The performance with

A Survey and Empirical Comparison of Object Ranking Methods

11

Table 1. Basic Results: |X ∗ |=1000, Li =10, N =300

li/numli/binnl/numnl/bin(a) under noiseless conditions
Cohen
RB
SVOR
OSVM
0.860 [5] 0.959 [2] 0.914 [3] 0.886 [4]0.966 [2] 0.978 [1] 0.885 [4] 0.868 [5]0.682 [5] 0.763 [4] 0.911 [2] 0.878 [3]0.786 [5] 0.875 [1] 0.866 [2] 0.842 [3]ERR
0.982 [1]0.895 [3]0.935 [1]0.830 [4]nl/numnl/bin(b) under noisy conditions
Cohen
RB
SVOR
OSVM
0.652 [5] 0.719 [4] 0.818 [1] 0.797 [3]0.764 [5] 0.842 [1] 0.817 [2] 0.809 [3]ERR
0.813 [2]0.796 [4]nl/bin data was unstable because the weights of a regression function haveto be determined based on two points, 0 and 1. The SVM-based method could
avoid this problem by adopting the regularization property. The two SVM-based
methods, OSVM and SVOR, also bear a resemblance to each other. The RB was
rather inferior for the nl case, but it could be improved by increasing the numberof rounds T . For example, when we tried the number of iterations T = 1000 for
basic data under a noisy condition in Table 1(b), the ρ improved from 0.720 to
0.765. However, it was too slow compared with other methods, so we had to set
T = 100 when performing our experiments.
Table 1(a) shows the results under a noiseless condition; that is to say, all
the sample orders are perfectly concordant with the corresponding regression
order. To test the robustness of the methods against the noise in the orders, wepermuted two randomly selected pairs of adjacent objects in the original sample
orders. By changing the number of times that objects are permuted, the noiselevel could be controlled. The order noise level is measured by the probability
that the ρ between the original order and the permuted one is smaller than the ρ
between the original order and a random one. This probability can be computedby using the statistical property of Spearman’s ρ. We generated four types ofdata whose noise levels were 0%∼10%. Note that the 0% level noise is equivalent
to the noiseless case.
Figure 3 shows the means of ρ in accordance with the order noise level for thenl/num data. In accordance with the increase of noise, the empirical ρ (between
the estimated order and the permuted sample order) drastically became worse,
whereas true ρ (between the estimated order and the noiseless order that cannot
be observed in non-artiﬁcial data) did not decrease to a signiﬁcant degree. For
example, at the 10% noise level, the empirical ρ by the ERR for the nl/num data
is 0.409, while the true ρ is 0.904. We then examined the robustness of thesemethods against noise in attribute values. For the numerical attributes, the α%
level of noise is obtained by multiplying the true values by the random factorsthat follow N (1, α/100). Note that sample orders were calculated based on noiseless attribute values. Figure 4 shows the means of ρ in accordance with the level12

Kamishima, Kazawa, Akaho

ρ 1

ρ 1

0.9

0.9

0.8

0.8

0.7

0.7

0.6
0.5

Cohen
RB
SVOR
OSVM
ERR
0%

0.6
0.5
0.1%

1%

10%

Fig. 3. Variation in the order noise

Cohen
RB
SVOR
OSVM
ERR
0%

20%

40%

80%

160%

Fig. 4. Variation in the attribute noiseof attribute noise for the nl/num data. We generated ﬁve types of data whose α
values were set to 0%∼160%. The results shown in Figures 3 and 4 indicate aclear contrast. The SVM-based methods were robust against attribute noise, but
not against order noise. Conversely, the other methods were robust against ordernoise, but not against attribute noise. This could be explained as follows: The
SVM-based methods are sensitive to order noise because the exchanged orderedpairs tend to become support vectors, while perturbation of attribute values does
not aﬀect the support vectors as much. Inversely, the non-SVM-based methods
can learn correctly if correct orders constitute the majority of the sample orders;thus, these methods are robust against order noise. However, any perturbation
in attribute values aﬀects their performance.
The noiseless setting of Table 1(a) is unrealistic, because real data generally
include noise. We therefore investigated the behavior of object ranking methods under more realistic noisy conditions. According to the above results, therelative superiority of the prediction performance among the methods heavily
depended on types of noise. That is to say, while the non-SVM-based methods
were superior for data with more order noises, the SVM-based ones were superior
for data with more attribute noises. Instead of comparing the relative superiorityof methods, we investigated the patterns of the changes of the relative predictive performance in accordance with the variation of data properties. To checkthese, noise levels were selected so that ERR and SVOR gave roughly equal performance. In both the nl/num and the nl/bin data sets, order noise levels were
set to 1%. While the attribute noise level of the nl/num was 40%, binary values
were ﬂipped with a probability of 1% for the nl/bin. We however used noiselessdata when testing the variation in the predictive performance according to thelength of sample orders (Figure 5(c)), because the shorter sample orders weremore seriously inﬂuenced by order noise. Along with ﬁxing the algorithm parameter settings, we tested the changes of the prediction performance according
to variation in the number of objects |X ∗ |, the number of sample orders N , andthe length of orders Li .

A Survey and Empirical Comparison of Object Ranking Methods

nl/numnl/bin

ρ 1

ρ 1

0.9

0.9

0.8

0.8

0.7

0.7
Cohen
RB
SVOR
OSVM
ERR

0.6
0.5
100

13

Cohen
RB
SVOR
OSVM
ERR

0.6
0.5

1000

10000

100

1000

10000

∗

ρ 1
0.9

(a) |X |={100, 1000, 10000}
ρ 1

Cohen
RB
SVOR
OSVM
ERR

0.9

0.8

0.8

0.7

0.7

0.6

0.6

0.5

Cohen
RB
SVOR
OSVM
ERR

0.5
50

100

300

500

1000

50

100

300

500

1000

7

10

(b) N ={50, 100, 300, 500, 1000}
ρ 1

ρ 1
0.9

0.9

0.8

0.8

0.7

0.7
Cohen
RB
SVOR
OSVM
ERR

0.6
0.5
2

3

5

Cohen
RB
SVOR
OSVM
ERR

0.6
0.5
7

10

2

3

5

(c) Li ={2, 3, 5, 7, 10}
Fig. 5. Variation in the number of objects |X ∗ |, the number of sample orders N , andthe length of sample orders Li

14

Kamishima, Kazawa, Akaho

Table 1(b) shows the results under this noisy condition for the basic data.
Except between SVOR and ERR of nl/num, the diﬀerence between each method
and the next-ranked one is statistically signiﬁcant at the level of 1% when usinga paired t-test and a Bonferroni multiple comparison. Figure 5 shows the meansof ρ in accordance with the variations in the other properties of samples sets.
The results for the nl/num and the nl/bin data are shown in each column. Rows(a), (b), and (c) show results when the number of objects |X ∗ |, the number ofsample orders N , and the length of orders Li were varied, respectively.
In terms of Figure 5(a), the probability that an object in test orders has notbeen included in training samples decreases in accordance with the increase of|X ∗ |; accordingly, a greater generalization ability is required. SVM-based methods were better if |X ∗ | was small, but their performance dropped for larger |X ∗ |.
Adoption of soft-margin parameter C tuning for |X ∗ | was required in order for
the SVM-based methods to work well. The non-SVM-based methods results wererather ﬂat. This would be because the number of model parameters to determine
is fewer in these methods than in the SVM-based ones.
Turning to Figure 5(b) and (c), the Cohen method performed more poorly forthe larger Li . This would be because the paired comparison model used in the
Cohen method assumes independence among ordered pairs. For small N or Li ,the performance of the SVM-based methods was inferior to those of the others.
However, the performance was improved in accordance with the increase of N
or Li . This might be because the SVM-based methods are over-ﬁtted when thesample set is so small that the learned functions are not sparse. We also expectedthat this observation arises from the strength of model biases. Hence, we further
checked the performance by changing the parameters of the methods, but wecould not ﬁnd a simple relation between the number of parameters to learn andthe number of observed samples.

5

Experiments Using Real Data

We applied the methods described in Section 3 to real data from the following
questionnaire surveys. The ﬁrst data set was a survey of preferences in sushi(Japanese food), and is denoted as SUSHI 4 [22, 19]. In this data set, N = 500,
Li = 10, and |X ∗ | = 100. Objects are represented by 12 binary and 4 numericalattributes. By using the k-o’means clustering method [23, 24], we generated two
sample orders whose ordinal variances were broad and narrow. The probabilities that objects were selected in Oi were not uniform, as assumed in an ERR
method. Objects were selected independently with probabilities that range from
3.2% to 0.13% from X ∗ . The second data set was a questionnaire survey of news
articles sorted according to their signiﬁcance, and is denoted as NEWS. These
news articles were obtained from “CD-Mainichi-Newspapers 2003.” In this dataset, N = 4000, Li = 7, and |X ∗ | = 11872. The variance among sample orders
was slightly broader than the tight SUSHI data. Articles were represented by
4This data set can be downloaded from http://www.kamishima.net/sushi/

A Survey and Empirical Comparison of Object Ranking Methods

15

keyword and document frequencies, and these 22297 elements were compressed
to 20 attributes using latent semantic indexing (a contribution ratio is about
0.9). Additionally, we used 8 binary attributes to represent article categories.
For both data sets, the N or Li were varied by eliminating sample orders or
objects. Orders became diﬃcult to estimate as N and/or Li decreased. Errors
were measured by the empirical ρ between the sample order and the estimatedone. The algorithm’s parameters were set to the practical setting in Section 4.2.
Ideally, these parameters should be tuned by using cross validation, but somemethods were too slow to perform such ﬁne tuning. Therefore, these experiments reveal not the relative superiority among methods but the changes in
performance along with the variation in N and/or Li .

NEWS

SUSHI

Table 2. Results on real data sets
N :Li
Cohen
RB
500:10(b) 0.364 [5] 0.384 [4]100:5(b)0.354 [2] 0.356 [1]
100:2(b)0.337 [1] 0.281 [2]500:10(n) 0.543 [5] 0.583 [4]100:5(n)0.548 [5] 0.612 [4]100:2(n)0.577 [1] 0.542 [2]4000:7−0.008 [5] 0.350 [3]1000:5−0.009 [5] 0.340 [3]1000:2−0.009 [5] 0.338 [3]SVOR
0.393 [3]0.284 [4]0.115 [4]0.719 [1]0.646 [2]0.522 [4]0.244 [4]0.362 [1]0.349 [1]OSVM
0.400 [1]0.315 [3]0.208 [3]0.708 [2]0.655 [1]0.540 [3]0.366 [2]0.353 [2]0.344 [2]ERR
0.397 [2]0.271 [5]0.010 [5]0.705 [3]0.617 [3]0.421 [5]0.386 [1]0.312 [4]0.149 [4]In Table 2, we show the means of ρ. The column labeled N :Li represents
the number and the length of sample orders, and the letter, “b” or “n” denotes
the types of variance, broad or narrow, respectively. In the SUSHI case, thediﬀerences among methods were less clear than those in artiﬁcial data. Though
we expected that the SVM would work well for a tight data set, the variance insample orders was less aﬀected. We could say that this is due to the ﬁtness of the
SUSHI data to a linear model; we observed that the other method worked wellwhen using a linear model. ERR showed good performance for large N or Li ,but poorer results for small N or Li . This is due to too complicated model for
regression, because the mean ρ increased to 0.249 by adopting a simpler linear
regression model for 100:2:(b). Inversely, RB was better for small N or Li . This isdue to the setting of T = 100, the number of rounds. When T = 300, we observedthat performance for large N or Li improved, but it was depressed for small N
or Li because of over-ﬁtting. In the case of NEWS, sample orders were tight, but
the correlation between sample orders and attributes were remarkably weak.
Thus, all methods performed poorly. For such weak attributes, Cohen performed
very poorly, even though we tuned β parameters. Again, ERR was better forlarge N or Li , but was poorer for small N or Li . However, this was due to themodel complexity as in the above SUSHI case. In summary, the performances of16

Kamishima, Kazawa, Akaho

four methods other than Cohen were roughly equal, when dealing with these real
data.

6

Discussion and Conclusions

We ﬁrst discuss the relation between object ranking methods and the probabilistic generative models for orders (see appendix A). These models can be
categorized as four types [1, 25]:
– Thurstonian: Objects are sorted according to the corresponding score.
– Paired comparison: Objects are compared in pairwise, and all objects are
sorted based on these comparison results.
– Distance-based : Orders are generated with the probability that is determinedbased on the distance from a modal order.
– Multistage: Objects are sequentially arranged top to end.
Object ranking methods are commonly designed by incorporating a way to deal
with attributes into these models. Error or loss in orders are designed based onthese generative models. In Cohen, because the precedence between object pairs
is ﬁrstly determined based on the learned model, we consider that this method
adopts a paired comparison model. Regarding RB and SVM methods, a modal
order is determined by sorting the outputs of a score function. Loss functions
between a modal order and sample orders are deﬁned based on the discordance
between them. Therefore, these methods can be considered to be related to the
distance-based model. While RB and SVOR adopt Kendall distance, OSVM adopts
Spearman footrule. Finally, ERR is based on the Thurstonian model as describedin section 3.4.
Table 3. Computational complexities
Cohen
2

RB
2

SVOR

OSVM

2

2

4

ERR

4

Learn N L̄ k N L̄ k N L̄ k N L̄ k N L̄k2
Sort
L2 L log L L log L L log L L log L

We next summarize computational complexities of learning and soring timein the ﬁrst and second rows of Table 3. We assume that the number of orderedpairs and of objects in S are approximated by N L̄2 and N L̄, respectively, whereL̄ is the mean length of the sample orders. The SVM’s learning time is assumed
to be quadratic in the number of training samples. The learning time of Cohen’s
Hedge algorithm or the RB is linear in terms of the N L̄2 , if the number of
iteration T is ﬁxed. However, if T is adaptively chosen according to N L̄2 , theirtime complexity becomes super-linear. In terms of the number of attributes k, theSVM-based methods depend on the number of non-zero attribute values; thus
it is practically sub-linear. Standard regression used in ERR can be computed

A Survey and Empirical Comparison of Object Ranking Methods

17

faster, if attributes are sparse. Generally, in practical use, the learning time of
the SVM-based methods is slow, that of Cohen and RB is intermediate, and thatof ERR are much faster. In terms of time for sorting of xj ∈ X , the Cohen greedy
requires O(L2 ) while the others perform more quickly, O(L log L).
We ﬁnally summarize the pros and cons of each method. Our new ERR
method was practically the fastest without sacriﬁcing its prediction performance.
This quickness make it to try many parameter settings in relatively short times.
Even for the result where ERR were poor, e.g., SUSHI:100:2(b), we observed thatit could be improved by re-tuning. In this method, the uniform distribution of
the object observation is assumed, but SUSHI result demonstrated the robustness against the violation of this assumption to an extent. However, this method
requires quadric time in terms of k, if attribute vectors are dense.
The most prominent merit of Cohen is to be an on-line method. For online learning purposes, the other methods cannot be used. Though the Cohen
performed rather poorly in our experiments, this is because the Hedge algorithm
is designed to take into account as its attributes only ordinal information. We
observed that the performance could be improved by using other classiﬁer, suchas the naive Bayes, instead of the Hedge, because this method was designed
to deal with categorical or numerical attributes. Further, our experiments wereabsolute ranking task (see section 2.2), but the Cohen acquires relative ranking
function, because this method adopts a paired comparison model.
The unique property of the RB is rich options of weak learners. Because of thisproperty, various types of attributes can be used. If objects are represented byvectors whose attribute types are mixtures of ordinal and numerical/categorical,
the other algorithm cannot be used. Our experimental results of RB were rather
inferior, but we observed that this could be considerably improved by adaptively
increasing T . Due to too slow convergence, we had to stop iterations after the endof the drastic error drops at the beginning stage. However, it takes as same ormore computation time as the SVM-based methods until complete convergence,and it should be also noted that too large T would cause over-ﬁtting.
Like a standard SVM, the SVOR and OSVM are advantageous if k is large.
The our experimental results demonstrated that the two SVM-based methods
and the others are robust against diﬀerent types of noise. Hence, for data inwhich orders are permuted, the non-SVM-based methods are preferable, while
for data whose attributes are disturbed, the SVM-based methods are preferable.
The demerit of the SVM-based methods are slowness. The learning complexityof the two SVM-based methods is the same, but the OSVM is practically slower.
However, it was more robust against order noise than SVOR.

A

Probabilistic Generative Models for Orders

We brieﬂy summarize the probabilistic generative models for orders. Readersthat needs further information should refer a textbook [1] or a survey paper [25].
As described before, these models can be categorized into four types: Thurstonian, paired comparison, distance-based, and multistage. All these are generative

18

Kamishima, Kazawa, Akaho

model for complete orders, in which all objects are included. We sequentially introduce these four types.
As seen in the name Thurstonian, this type of models are ﬁrstly proposedby Thurstone [21] and are also called by order statistics models. In this model,
objects, xi ∈ X ∗ , are sorted according to their corresponding scores. This scoreis a real value probabilistic function that is deﬁned asscore(xi ) = µ(xi ) + ϵ(xi ),where µ(xi ) is the mean score for the object xi and ϵ(xi ) follows the distribution
with zero mean. In original Thursone’s model, the normal distribution is used asϵ(xi ). Especially, the “case V”, in which the variance of the normal distribution
is constant over all objects, is widely used. In this case, the probability the object
xi precedes the xj is simply computed by [26]:()µ(xi ) − µ(xj )√,P[xi ≻ xj ] = P[score(xi ) > score(xj )] = Φ
2σwhere Φ(·) is the normal c.d.f. and σ 2 is its variance.
In a paired comparison model , which object precedes the other is determinedfor each pair of objects. Accordingly, L(L − 1)/2 ordered pairs are generated,
where L is the total number of objects, i.e. L = |X ∗ |. If this set of ordered pairs
is cyclic, i.e., xi ≻xj , xj ≻xk , and xk ≻xi , then this set is discarded, and all pairs
are re-generated; otherwise, a total order is uniquely determined. The saturated
model having L(L − 1)/2 parameters, which represent the probabilities that one
object precedes the other, is called by Babington Smith model. Babington Smithﬁrstly showed the moments of this model in [27]. After that, some models withfewer parameters have been proposed. The next model having L parameters iscalled Bradley-Terry model [28]:P[xi ≻ xj ] =f (xi ),f (xi ) + f (xj )where f (·) is positive real function.
In distance-based model , orders, O, follows the following distribution()
1
P[O] =
exp −λd(O0 , O) ,Z(λ)
where λ is a concentration parameter, which is non-negative real value, theO0 is a modal ranking, at which this distribution is peaked, d(·, ·) denotes the
distance between orders, and Z(λ) is a normalization factor. Especially, thismodel is called Mallows φ-model and Mallows θ-model if Kendall and Spearman
distance are adopted, respectively. This is because these are the special cases ofthe Mallows model [29], which is a kind of a paired comparison model. If i-thand j-th ranked objects in a generated order are xi and xj , respectively, Mallows
model is deﬁned asθi−j φ−1,
P[xi ≻ xj ] = i−j −1
θ φ + θj−i φA Survey and Empirical Comparison of Object Ranking Methods

19

where θ and φ are positive real parameters. If θ = 1 (resp. φ = 1), this model
becomes Mallows φ-model (resp. Mallows θ-model).
Finally, in multistage model , objects are sequentially arranged top to end.
Plackett-Luce model [30], which is a kind of a multistage model, generates an order, O = xi1 ≻xi2 ≻ · · · xiL , with the following procedure. The top ranked object,
xi1 , is chosen with the probability:f (xi1 ),x∈X ∗ f (x)∑the second ranked object, xi2 , is chosen with the probability:∑f (xi2 )x∈X ∗ ,x̸=xi1 f (x),and these procedures are iterated L − 1 times. Orders generated by this modelsatisﬁes Luce’s choice axiom: Roughly speaking, the probability that an object
is top-ranked equals to the product of the probability that the object is topranked in any subset and the probability that the subset contains the object.
More formally, PX [x] denotes the probability that an object x is top ranked
among the object set, X , and PX [X ′ ], X ′ ⊂X , denotes the probability that the
top object in X is contained in X ′ . A set of choice probabilities is said to satisfy
Luce’s choice axiom if ∀X ⊂ X ∗ with at least two objects, xi and xj , satisfy:– If P{xi ,xj} [xi ] > 0 ∀xi , xj ∈ X then ∀xk ∈ X ′ ⊂ X , PX [xk ]=PX ′ [xk ]PX [X ′ ],– If P{xi ,xj} [xi ] = 0 ∃xi , xj ∈ X then if xj ∈ X , xj ̸= xi , PX [xj ]=PX \{xi } [xj ].
This Plackett-Luce model is equivalent to the above Thurstonian model, if ϵ(·)
follows Gumbel distribution, whose c.d.f. is 1 − exp(− exp(x)).
Acknowledgments: A part of this work is supported by the grant-in-aid
14658106 and 16700157 of the Japan society for the promotion of science. Thanks
are due to the Mainichi Newspapers for permission to use the articles.

References
1. Marden, J.I.: Analyzing and Modeling Rank Data. Volume 64 of Monographs on
Statistics and Applied Probability. Chapman & Hall (1995)
2. Kendall, M., Gibbons, J.D.: Rank Correlation Methods. ﬁfth edn. Oxford University Press (1990)
3. Arrow, K.J.: Social Choice and Individual Values. second edn. Yale University
Press (1963)
4. Bollegala, D., Okazaki, N., Ishizuka, M.: A machine learning approach to sentenceordering for multidocument summarization and its evaluation. In: Proc. of the
Natural Language Processiong society of Japan. (2005)
5. Dwork, C., Kumar, R., Naor, M., Sivakumar, D.: Rank aggregation methods for
the Web. In: Proc. of The 10th Int’l Conf. on World Wide Web. (2001) 613–622
6. Agresti, A.: Categorical Data Analysis. second edn. John Wiley & Sons (1996)

20

Kamishima, Kazawa, Akaho

7. McCullagh, P.: Regression models for ordinal data. Journal of The Royal StatisticalSociety (B) 42(2) (1980) 109–142
8. Shashua, A., Levin, A.: Ranking with large margin principle: Two approaches. In:
Advances in Neural Information Processing Systems 15. (2003) 961–968
9. Cohen, W.W., Schapire, R.E., Singer, Y.: Learning to order things. Journal of
Artiﬁcial Intelligence Research 10 (1999) 243–270
10. Grötschel, M., Jünger, M., Reinelt, G.: A cutting plane algorithm for the linear
ordering problem. Operations Research 32(6) (1984) 1195–1220
11. Littlestone, N.: Learning quickly when irrelevant attributes abound: A new linearthreshold algorithm. Machine Learning 2 (1988) 285–318
12. Freund, Y., Iyer, R., Schapire, R.E., Singer, Y.: An eﬃcient boosting algorithm
for combining preferences. In: Proc. of The 15th Int’l Conf. on Machine Learning.
(1998) 170–178
13. Freund, Y., Iyer, R., Schapire, R.E., Singer, Y.: An eﬃcient boosting algorithm for
combining preferences. Journal of Machine Learning Research 4 (2003) 933–969
14. Kazawa, H., Hirao, T., Maeda, E.: Order SVM: a kernel method for order learning
based on generalized order statistics. Systems and Computers in Japan 36(1)(2005) 35–43
15. Herbrich, R., Graepel, T., Bollmann-Sdorra, P., Obermayer, K.: Learning preference relations for information retrieval. In: ICML-98 Workshop: Text Categorization and Machine Learning. (1998) 80–84
16. Herbrich, R., Graepel, T., Obermayer, K.: Support vector learning for ordinal
regression. In: Proc. of the 9th Int’l Conf. on Artiﬁcial Neural Networks. (1999)
97–102
17. Joachims, T.: Optimizing search engines using clickthrough data. In: Proc. of The
8th Int’l Conf. on Knowledge Discovery and Data Mining. (2002) 133–142
18. Luaces, O., Bayón, G.F., Quevedo, J.R., Dı́ez, J., del Coz, J.J., Bahamonde, A.:
Analyzing sensory data using non-linear preference learning with feature subset
selection. In: Proc. of the 15th European Conf. on Machine Learning. (2004) 286–
297 [LNAI 3201].
19. Kamishima, T., Kazawa, H., Akaho, S.: Supervised ordering — an empirical survey.
In: Proc. of The 5th IEEE Int’l Conf. on Data Mining. (2005) 673–676
20. Arnold, B.C., Balakrishnan, N., Nagaraja, H.N.: A First Course in Order Statistics.
John Wiley & Sons, Inc. (1992)
21. Thurstone, L.L.: A law of comparative judgment. Psychological Review 34 (1927)
273–286
22. Kamishima, T.: Nantonac collaborative ﬁltering: Recommendation based on order
responses. In: Proc. of The 9th Int’l Conf. on Knowledge Discovery and Data
Mining. (2003) 583–588
23. Kamishima, T., Fujiki, J.: Clustering orders. In: Proc. of The 6th Int’l Conf. on
Discovery Science. (2003) 194–207 [LNAI 2843].
24. Kamishima, T., Akaho, S.: Eﬃcient clustering for orders. In Zighed, D.A.,
Tsumoto, S., Ras, Z.W., Hacid, H., eds.: Mining Complex Data. Volume 165 ofStudies in Computational Intelligence. Springer (2009) 261–280
25. Critchlow, D.E., Fligner, M.A., Verducci, J.S.: Probability models on rankings.
Journal of Mathematical Psychology 35 (1991) 294–318
26. Mosteller, F.: Remarks on the method of paired comparisons: I — the least squares
solution assuming equal standard deviations and equal correlations. Psychometrika
16(1) (1951) 3–9

A Survey and Empirical Comparison of Object Ranking Methods

21

27. Babington Smith, B.: Discussion on professor ross’s paper. Journal of The Royal
Statistical Society (B) 12 (1950) 53–56 (A. S. C. Ross, “Philological Probability
Problems”, pp. 19–41).
28. Bradley, R.A., Terry, M.E.: Rank analysis of incomplete block designs — i. themethod of paired comparisons. Biometrika 39 (1952) 324–345
29. Mallows, C.L.: Non-null ranking models. I. Biometrika 44 (1957) 114–130
30. Plackett, R.L.: The analysis of permutations. Journal of The Royal StatisticalSociety (C) 24(2) (1975) 193–202

Indexaggregated ranking, see center of orders
Babington Smith model, 18
Bradley-Terry model, 18
Bradley-Terry/Mallows
model,
Bradley-Terry modelsee

Mallows model, 18
Mallows φ model, 18
Mallows θ model, 18
midrank, 3
multistage model, 19
object ranking, 4order statistics model, see Thurstonian
model
OrderSVM, 7
ordinal regression, 5center of orders, 4Cohen’s method, 5
Daniels’ inequality, 3
distance-based model, 18
Durbin-Stuart’s inequality, 3paired comparison model, 18
Plackett-Luce model, 19

ERR, see expected rank regression
expected rank regression, 8

RankBoost, 6
Ranking SVM, see SVOR

Hedge algorithm, 6
Kendall distance, 2Kendall τ , see Kendall’s rank correlation
Kendall’s rank correlation, 3
law of comparative judgement,
Thurstonian model
linear ordering problem, 5Luce’s choice theorem, 19

see

Spearman distance, 2Spearman ρ, see Spearman’s rank correlation
Spearman’s rank correlation, 2
support vector ordinal regression, see
SVOR
SVOR, 8Thurstonian model, 18