Progressive Comparison for Ranking Estimation

1 Introduction

Object ranking is a problem to order given objects by aggregating pairwise comparison data; It has various applications in optimizing Web services such as EC sites and search engines based on behaviors of customers or users. In sports or games played between multiple teams, match results during a particular period are aggregated into a team ranking list.

The pairwise comparison data is frequently discordant; when two players play chess, it naturally happens that one of the players wins in the first match and the other wins in the second match. In order to estimate a reasonable ranking list from such datasets, several existing approaches deal with such ambiguity using probabilistic models [Keener, 1993; Bradley and Terry, 1952; Glickman, 1999; Radlinski and Joachims, 2007; Elo, 1978; Herbrich et al., 2006].

Figure 1: (a) the standard pairwise comparison method and (b) the proposed progressive comparison method. In the standard pairwise comparison, an evaluator first evaluates two objects, and then submits the preferred one; therefore obtaining three pairwise comparison results requires six object evaluations. In the progressive comparison, the evaluator is asked if the current evaluated object is preferred to the previously evaluated object; therefore the evaluator needs only four object evaluations to obtain three pairwise comparison results, which means that the progressive comparison method can collect more comparison results with fewer evaluations than the standard pairwise comparison.

Estimation of a reasonably accurate ranking often requires many comparison results, and it is often costly to collect such datasets. Usually, an evaluator first evaluates two objects, and reports the preferred one to create one comparison result; to obtain K pairwise comparison results, we need 2K evaluations (Fig. 1(a)). In this paper, we especially consider the cases where the cost of an evaluation is much higher than that of a comparison; for example, ordering text documents by their quality, and ranking restaurants. An evaluation, i.e., reading a document or eating in a restaurant, is much more costly than comparing two of them. Moreover, increase in the number of evaluations also affects their quality and stability since the evaluator becomes tired or on a full stomach.

In this paper, we propose the progressive comparison method (Fig. 1(b)). Each time the evaluator makes an object evaluation, the evaluator is requested to answer whether or not the current evaluated object is preferred to the previous one. In contrast with the standard pairwise comparison, the progressive comparison requires only K + 1 evaluations to obtain K pairwise comparison results.

We also propose active learning methods for the progressive comparison to further reduce data collection efforts. These methods select the object to be evaluated next based on the amount of information gained from the object evaluation and comparison. We propose two measures of such information gain: the change in distributions and the change in winning probabilities.

We present experiments conducted using a synthetic dataset and two real datasets in order to verify the cost effectiveness of the proposed methods. We show progressive comparison achieves higher accuracy with a smaller number of evaluations than the standard pairwise comparison, and our active learning methods more effectively estimate rankings than the method that randomly selects the next object.

In summary, this paper makes the following three contributions: (i) the progressive comparison method which is an efficient data collection method for pairwise comparison data with a small number of evaluations, (ii) active learning methods for the progressive comparison using two measures of expected model changes, and (iii) the property of datasets that the active learning methods applied in the progressive comparison method operate effectively.

2 Ranking Estimation Problemwith High Evaluation Costs

We consider N objects o1↪ ▷ ▷ ▷ ↪ oN, and denote by (oi↪ oj) a pairwise comparison result indicating that object oi is preferred to object oj . We also denote by C the multiset consisting of the comparison results. In many cases, the elements of C are discordant; in other words, C contains both (oi↪ oj) and (oj ↪ oi). Our goal is to estimate an accurate ranking from C while keeping the collection cost of C as low as possible.

In this paper, we particularly focus on the cost in terms of the number of evaluations. An evaluation involves giving an (internal) score ✓i to an object oi, for example, the beauty of an image, impressiveness of an article, or the deliciousness of food. A comparison involves determining the winner based on the two object scores to create one comparison result. Our important assumption is that the cost of an evaluation is substantially larger than that of a comparison; therefore, reducing the collection cost of C requires reducing the number of evaluations.

3 Progressive Comparison

3.1 Progressive Comparison

Linear ordering and pairwise comparison are two typical data formats in ranking estimation problems. In the linear ordering, each evaluator evaluates all objects o1↪ ▷ ▷ ▷ ↪ oN, and submits a ranking list of the N objects. Since the evaluators have to remember the scores of all objects before creating the ranking list, this is difficult for a large N.

In the pairwise comparison, as shown in Figure 1(a), each evaluator evaluates two objects, and then reports the preferred one. For example, the evaluator receives objects oi and oj, and submits either (oi↪ oj) or (oj↪ oi). The evaluator needs only to remember the two objects to make a comparison. This method requires 2K evaluations to obtain K pairwise comparison results.

To reduce the evaluation costs of the standard pairwise comparison method, we propose the progressive comparison. As shown in Fig. 1(b), when an evaluator evaluates an object, she compares it with the preceding evaluated object and judges which one is preferred. This means that an evaluator first evaluates objects o1 and o2, and submits the comparison result for o1 with o2, and then evaluates object o3 and submits the comparison result for o2 with o3. The evaluator repeatedly carries out the above operation. In order to compare K pairs of objects, this method requires only K+1 evaluations of objects. As compared with pairwise comparison, we can obtain more comparison results with fewer evaluations 1 .

3.2 Ranking Estimation

We employ the Bradley-Terry model which is a popular probabilistic model for pairwise comparison [Bradley and Terry, 1952]. The Bradley-Terry model gives the probability an evaluator prefers object oi to oj as P((oi↪ oj)) = λi ◁ (λi + λj), where λi↪ λj > 0 are positive parameters that represent the object scores of oi↪ oj, respectively.

The glicko update equations are an approximate Bayesian estimation procedure for the Bradley-Terry model proposed by Glickman (1999). Following the original notations, we rescale λi as λi = 10✓i◁400 using the (scaled) object score ✓i. We assume that ✓i follows a Gaussian prior distribution N(θi↪ σ2 i ) where θi and σ2 i are the mean and variance parameters, respectively. In the progressive comparison scenario, when an object oi is evaluated, ✓i is sampled from the Gaussian prior distribution N(θi↪ σ2 i ); then ✓j for the next object oj is sampled fromN(θj↪ σ2 j ), and a comparison result of oj and oi is determined with P((oi↪ oj)). Similarly, another object ok is evaluated to obtain ✓k, which is then compared with ✓j to give another comparison result. Note that every time an object oi is evaluated, ✓i is re-sampled from the corresponding Gaussian distribution.

The glicko update equations update parameters θ(oi ↪oj ) i and σ(oi ↪oj ) i 2 using comparison result (oi↪ oj) as follows:

1 One might wonder if the progressive comparison method is in fact a new idea; however, we are not aware of the method having been previously proposed in the literature.

⇥q2 g(σ2 j )2E(θi↪ θj ↪ σ2 j )¶1 - E(θi↪ θj ↪ σ2 j )♦⇤-1 . We repeatedly update each θi by using each comparison result in C, and finally obtain an object ranking list by sorting the conclusive ¶θ1↪ ▷ ▷ ▷ ↪ θN♦ in descending order.

Note that since the results of pairwise comparisons obtained by the progressive comparison method are not i.i.d., the standard estimation methods are not applicable in the strict sense, which means that we approximate the likelihood or posterior by making the independence assumption. In the experimental section, we will see this approximation is effective in practice.

4 Active Learning for Progressive Comparison

4.1 Active Learning

To further reduce the number of evaluations and accelerate the estimation, we resort to active learning, which actively selects the unlabeled data to be labeled [Settles, 2012].

In active learning for the standard pairwise comparison, a learning algorithm actively selects two objects to be compared next. Conversely, an active learning algorithm in the progressive comparison selects one subsequent object. Let us assume that the preceding evaluated object is oi. We first calculate uij for all j, where uij is the expected information gain by selecting oj as the next object, and then oj ⇤ that maximizes uij is selected. In this study, we consider two types of information gain: change in distributions and change in winning probabilities.

4.2 Change in Distributions

When it turns out that an evaluator prefers object oi to object oj, the glicko update equations update the posterior distributions N(θi↪ σ2 i ) and N(θj↪ σ2 j ) to N(θ(oi↪oj) i ↪ σ(oi ↪oj ) i 2 ) and N (θ(oi ↪oj ) j ↪ σ(oi ↪oj ) j 2 ), respectively, where θ(oi↪oj) i , σ(oi↪oj) i 2 , θ(oi ↪oj ) j ↪ and σ(oi↪oj) j 2 are the parameters of the Gaussian distributions updated by assuming that an evaluator gives a comparison result (oi↪ oj). As shown in Fig. 2, a possible choice of our information gain is the amount of changes of the two Gaussian distributions, which is measured in the sum of the

Kullback-Leibler (KL) divergences, that is,

where DKL(P k Q) is the KL divergence between two probability distributions P and Q.

Taking the expectation of F((oi↪ oj)) over two cases (oi↪ oj) and (oj↪ oi), we define an expected information gain measure called change in distributions as

where P((oi↪ oj)) is the probability that an evaluator prefers object oi to oj, which is readily calculated with

where Φ(·) is the cumulative Gaussian distribution [Mackay and Chaiy, 1982].

4.3 Change inWinning Probabilities

Since what we are interested in is the ranking list of objects which summarizes relative merits between any two objects, it seems a reasonable idea to consider the change in winning probabilities among objects as the information gain measure. Since a winner determination is a Bernoulli trial, such changes are measured in the KL divergences between Bernoulli distributions, that is,

where B(·) denotes a Bernoulli distribution, and pxy is the probability that an evaluator prefers object ox to oy, and p(oi ↪oj ) xy is the probability updated by the glicko update equations with a comparison results (oi↪ oj). Similar to Eq. (1), pxy and p(oi↪oj) xy are readily calculated with

In contrast with measuring the change in two Gaussian distributions, changes in two Bernoulli distribution cause changes in all of the related winning probabilities, namely, they affect the winning probability one of whose objects is either oi or oj. Therefore, as shown in Figure 3, the total amount of changes in the winning probabilities is given as

Now we define an expected information gain measure called change in winning probabilities defined as

where P((oi↪ oj)) is the probability that an evaluator prefers object oi to oj, which is calculated with Eq. (1).

5 Experiments

5.1 Experimental Settings

We conducted two experiments using a synthetic dataset and two real datasets to examine the effectiveness of our proposed approach. The first experimental result demonstrates that the progressive comparison requires fewer numbers of evaluations than the standard pairwise comparison method. The second result demonstrates that our proposed active learning approach is more efficient than the baseline method which randomly samples objects to be evaluated.

Throughout the experiments, the parameters are initialized θi = 1↪ 500 and σ2 i = 1472 = 21↪ 609 by following the settings of the glicko update equations [Glickman, 1999]. Every time the parameters are updated, we compare the current estimated ranking list with the true one. The estimated ranking list is obtained by sorting values θ1↪ ▷ ▷ ▷ ↪ θN in descending order. The similarity between two ranking lists is measured using Spearman's rank correlation ⇢ [Spearman, 1906]. Let T and E be the rank vectors of the true ranking and the estimated ranking, respectively; ⇢ is given as ⇢ = 1 - 6 ⇥ dSpear(T↪ E) ◁ (N 3 - N), where dSpear(T↪ E) is the Spearman distance which is the squared Euclidean distance between T and E.

5.2 Datasets

The first dataset is a synthetic dataset comparing 100 objects. The true scores of object i is given as θi = i - 1, and its true variance as σ2 i = 100. Each evaluation draws a score ✓i from the Gaussian distribution N(θi↪ σ2 i ), and the winner of oi and oj is determined by comparing ✓i and ✓j.

The image comparison dataset includes 25↪ 500 pairwise comparison results of 50 scenery images collected by using Lancers crowdsourcing marketplace 2 . Each crowdsourcing task presents ten pairs of images, and a crowdsourcing worker is asked to tell which picture of each pair is better for a postcard 3 . The true scores of the objects are defined as follows;

2 http://www.lancers.jp/

3 The dataset is available at http://goo.gl/6MS9MK.

we apply the glicko update equations to all of the pairs of the dataset in random order, and obtain final estimates. This procedure is repeated ten times, and the averaged final estimates are used as the ground truths of the ranking 4 .

The Wikipedia article comparison dataset consists of 8↪ 700 pairwise comparison results of 30 Wikipedia articles. The dataset includes 15 featured articles and 15 non-featured articles selected randomly from "Wikipedia: Featured articles" 3 . Each crowdsourcing task presents five pairs of article links, and a crowdworker is asked to tell the more substantial article. Some exemplars are also presented in order to illustrate the evaluation criteria. Similar to the image comparison dataset, the average of ten sweeps of the whole dataset with different orders is used to create the ground truth ranking.

Figure 4 shows the histograms of the true object scores in the three datasets. Figure 4(a) corresponds to the synthetic dataset; the histogram is flat. On the other hand, the histogram for the image comparison dataset is unimodal (Fig. 4(b)). Figure 4(c) shows the histogram for the Wikipedia dataset; the objects with high scores and those with low scores are rather separated.

5.3 Results

Pairwise Comparison vs. Progressive Comparison

To compare the standard pairwise comparison and the proposed progressive comparison. we investigate the accuracy of the estimated ranking in terms of the numbers of comparisons and evaluations using the synthetic dataset.

Figures 5(a) and 5(b) show the accuracy of the ranking versus the number of comparisons and evaluations, respectively. We denote the performance of the progressive comparison by 'Progressive' and the standard pairwise comparison by 'Pairwise.' We denote by 'Distribution' active learning using the change in distributions measure, 'WinProb' by the one using the change in winning probabilities measure, and by 'Random' the random sampling method.

Figure 5(a) shows the performance depending on the number of comparisons. The standard pairwise comparison method performs better than the progressive comparison in all of the random sampling method and two active sampling methods; this is because the progressive comparison has fewer options in selecting the next pair. In contrast, Figure 5(b) shows the progressive comparison method significantly outperforms the standard pairwise comparison in terms of the number of evaluations. This is because the standard pairwise comparison obtains K◁2 comparison results by K evaluations, whereas the progressive comparison method can obtain K - 1 comparison results by K evaluations. As discussed earlier, the progressive comparison method collects comparison data in a non-i.i.d. manner, we need to approximate the likelihood or posterior by making the independence assumption. The result suggests this approximation is effective in practice. Due to the space limitation, we omit the results for the real datasets in Figure 5. We confirmed that they led to the same conclusion as the synthetic dataset.

4 The estimates were stable regardless of the presentation order.

• (b) Estimation accuracy vs. number of evaluations

Figure 5: Accuracy of ranking lists by the standard pairwise comparison and the progressive comparison for the synthetic dataset.

Efficiency of Active Learning Methods

We compare the proposed active learning methods using the two information gain measures: the change in distributions measure and the change in winning probabilities measure, with a baseline approach using uniform sampling. Figure 6 shows the comparison results of the accuracy of these methods. The accuracy of the estimated ranking lists is measured using Spearman's rank correlation between a true ranking list and an estimated ranking list. We denote the active learning method using the change in distributions measure by 'Distribution', and the one using the change in winning probabilities measure by 'WinProb', and the random sampling method by 'Random.' A solid line, a broken line, and a one-point broken line show the accuracy averages, and the transparently painted areas around these lines represent standard deviations. Figure 6(a) shows the result for the synthetic dataset. Our active learning methods obtain accurate ranking lists faster than the randommethod, and the method using the change in winning probabilities performs better than the one using the change in distributions. In terms of standard deviation, the area of the baseline method and those of active learning methods are clearly separated. However, for the image comparison dataset, the standard deviation areas of the three methods extensively overlap in Figure 6(b), and therefore we find no clear advantage of the proposed methods over the baseline method. The inconsistency of the two results is explained by the histograms of the true scores. Figure 4(a) shows the true scores of the synthetic dataset distribute uniformly, which means the true ranking is rather clear, and the proposed sampling methods are quite effective. On the other hand, Figure 4(b) shows the true scores of the image comparison dataset rather concentrate around the average, which means the dataset has many pairs whose winners are ambiguous, and the proposed sampling methods have no advantage in such datasets. Figure 6(c) shows the result for the Wikipedia dataset; the proposed methods outperform the baseline method especially after 200 evaluations, and there is no overlap between standard deviation areas. The method using the change in winning probabilities outperforms the one using the change in distributions when the number of evaluation is relatively small. In Fig. 4(c), the high-scored objects and the low-scored objects are separated in this dataset, that is, this dataset includes many pairs whose winners are readily determined as well as the synthetic dataset.

We also investigate the average number of evaluations required for Spearman's rank correlation to reach 0▷9. The number of evaluations is the largest for the random sampling method and the smallest for the active sampling method using change in winning probabilities. The Wilcoxon signed-rank test [Wilcoxon, 1945] with 0▷01 significance level shows statistically significant differences for all pairs of the methods except for the difference between the active sampling using the change in distributions and the random sampling method in the image comparison dataset. The method using change in winning probabilities is superior to the random sampling method for all datasets with the statistical significance. In summary, the method using change in winning probabilities is the most promising to reduce the number of evaluations among the three methods.

6 RelatedWork

There has been much existing work in object ranking by aggregating the pairwise comparison results; to name a few, Keener proposed a method based on the eigenvector of the matrix that contains the comparison results [Keener, 1993]. Bradley and Terry proposed the Bradley-Terry model, which is a stochastic model of pairwise comparison, and its maximum likelihood estimation method [Bradley and Terry, 1952]. In addition, Glickman proposed an approximated Bayesian estimation method of the model [Glickman, 1999]. Based on Glickman's update equations, Radlinski and Joachims proposed an algorithm that estimates the Web page ranking ordered by relevance for a search query [Radlinski and Joachims, 2007]. The Elo rating system, which is a rating system for measuring the ability of chess players, was proposed by Elo [Elo, 1978]. Herbrich et al. proposed TrueSkill TM [Herbrich et al., 2006], which is another rating system for estimating the ability of online game players, based on the Elo rating system.

To estimate a ranking list from the results of pairwise comparisons collected from crowdsourcing workers, the CrowdBT model, which is an extension of the Bradley-Terry model to consider the ability of evaluators, was presented by Chen and Bennett [Chen and Bennett, 2013]. Matsui et al. proposed a method to aggregate linear orders collected by using crowdsourcing [Matsui et al., 2014]. Wu et al. proposed a method that considers the reliability of labels annotated by multiple evaluators [Wu et al., 2011].

There has been existing work on active learning from pairwise comparison data; for example, Pfeiffer et al. proposed adaptive information aggregation method for ranking estimation [Pfeiffer et al., 2012]. The criterion that they employed for active sampling is essentially same as one we showed in Section 4.2. Brinker proposed active learning criteria [Brinker, 2004] for both the constraint classification [Har-Peled et al., 2002] and the pairwise decomposition [F¨urnkranz and H¨ullermeier, 2003] which are approaches to reduce ranking problems to binary classification problems. Ailon discussed theoretical guarantees of active learning for ranking from pairwise preferences [Ailon, 2011].

7 Conclusion

We addressed the ranking estimation problem where the cost of object evaluation is large. We proposed a new pairwise comparison data collection method called progressive comparison, which reduces the number of evaluations to almost a half of that of the ordinary pairwise comparison method. We also proposed the active learning methods to determine which object should be evaluated next in the progressive comparison. We proposed two measures of expected model changes, one considering the changes in the evaluation score distributions and the other the changes in the winning probabilities. The experiments demonstrated that the progressive comparison achieved higher estimation accuracy with a smaller number of evaluations than the standard pairwise comparison, and the active learning methods further reduced the number of evaluations as compared with the random sampling method, especially for datasets with relatively clear true ranking.

In this study, we collected our crowdsourced datasets by using the standard pairwise comparison, and simulated the progressive comparison using them; however, it is still not clear if such experimental arrangement is always valid because evaluations in progressive comparison are possibly biased compared with the standard pairwise comparison. Further investigations regarding human cognition depending on sampling methods would be required.