Progressive Comparison forRanking Estimation
Ryusuke Takahama Kyoto University / JST, ERATO
Toshihiro Kamishima AIST
Hisashi Kashima Kyoto University

Outline■ Problem setting■ Background■ Progressive Comparison■ Active learning of Progressive Comparison■ Change in Distributions■ Change in Winning Probabilities■ Experimental results

2Problem setting:
Estimate ranking from pairwise comparison data
■ Problem setting: estimate ranking of objects
using pairwise comparison results

Estimatedranking

Comparison
results

Objects

Score: high>Datacollection>

1stEstimation
algorithm

2nd>

3rd>

4th
Score: low3Problem setting:
Estimate ranking from pairwise comparison data
■ Problem setting: estimate ranking of objects
using pairwise comparison results

EstimatedrankingComparison
results

Objects

Score: high>Datacollection>

1stEstimation
algorithm

2nd>

3rd

Time-consuming or>
expensive to obtain!

4th
Score: low

3

4
http://www.dayofrest.co.uk/mast-brothers-chocolate/Background:
efficient data-collection method is needed■ Example: want to know taste ranking of chocolates■ Data-collection (eating) is very toughComparison
results

Objects

B-SUGAR

SMOKE

COFFEEALMONDScore: high>Datacollection>

Estimatedranking

1stEstimation
algorithm

2nd>

3rd>

4th
Score: low5

Background:
efficient data-collection method is needed■ Example: want to know taste ranking of chocolates■ Data-collection (eating) is very toughComparison
results

Objects

B-SUGAR

COFFEESMOKE

ALMOND>
Datacollection

Estimatedranking
Score: high

1st

Proposed toEstimationcollect data efficiently:
2nd>algorithm
・Progressive Comparison
・Activelearning method for3rd>
Progressive Comparison>

4th

Score: low

5

Progressive Comparison:
Data-collection method needing fewer evaluations■ Existing method (Standard pairwise comparison):Comparison: which is thebetter of the two?

Comparison

Comparison

Object A

Object B

Object B

Object C

Object C

Object D

Evaluation

Evaluation

Evaluation

Evaluation

Evaluation

Evaluation

3 comparisonsneed
6 evaluations■ Proposed method (Progressive Comparison):Comparison: which is the better
between the current object and thepreviously evaluated one?

Comparison

Comparison

3 comparisonsneed

Object A

Object B

Object C

Object D

Evaluation

Evaluation

Evaluation

Evaluation

4 evaluations
6Active learning for Progressive comparison:
Estimate ranking efficiently by selecting pairs■ Utilities calculated for each pair■ Priority given to a pair that has larger utility value■ Two definitions of utility proposed:(i) Change in Distributions (CiD):
expectation of changes in distributions of object scores(ii) Change in Winning Probabilities (CiWP):
expectation of changes in winning probability matrices
Object A

Object B

Comparison

Object C

Object D

Comparison

Next evaluated object
determined by utility value
7(i) Change in Distributions (CiD):
Calculate expectation of changes in distributions■ Expectation of changes in distributions calculated by
KL divergence between normal distributions:
Distribution of score ofobject oi

If oi wins
against oj:

Distribution of score ofobject oj

If oj wins
against oi:

8(ii) Change in Winning Probabilities (CiWP):
Calculate expectation of changes of matrices■ Expectation of changes in matrices calculated by
KL divergence between Bernoulli distributions:
Oi
Oi

Oj

ー 0.2 0.4 0.7 0.6
0.8 ー 0.8 0.3 0.9
0.6 0.2 ー 0.1 0.4

Oi
OiOj

ー 0.3 0.5 0.9 0.7
0.7 ー 0.8 0.4 0.9
0.5 0.2 ー 0.2 0.4

Oj 0.1 0.6 0.8 ー 0.6
0.3 0.1 0.6 0.4 ーOi

Oj 0.3 0.7 0.9 ー 0.7
0.4 0.1 0.6 0.3 ー

If oi wins
against oj:
If oj wins
against oi:OiOj

ー 0.1 0.3 0.5 0.5
0.9 ー 0.8 0.2 0.9
0.7 0.2 ー 0.1 0.4

Oj 0.5 0.8 0.9 ー 0.8
0.5 0.1 0.6 0.2 ー
9!

!!'!( #&HGG +(*)("!BG#CC%"!!"#/$#"!!
"#/$((( # .!( %Experiment (&Bsettings:!!'!( #&HGG*&B B ( BG&"

Ranking estimation using Glicko Update Equation>#'4 $;-,$44')( 3+1 %$ $0+56+"$. %1 64'(& (63$,'2+5 3$"#).4/ 462# +4 J)("'("$&,+"')(7 L(4"$+./ :$ .$"$,3'($ + 4$" )* 25)4$. *),3 2)3-6"+"')(4 "#+" +--,);'3■ Glicko-)4"$,'),
Update.$(4'"1Equation:3+,&'(+5'( $;-,$44')( EIF7 >#$ .$"+'54 )* "#$ .$,'0+"')( +,$ '( !-6-.+"'(&+5&),'"#3+--,);'3+"$4$;-,$44')(EIF %1 + (),3+5.$(4'"1 :'"# 3■>#$Online
ranking
estimation
algorithmof Bradley-Terrymodel))C+(.
$,$4-$2"'0$517 >#$ -+,+3$"$,4 +,$ &'0$( %10+,'+(2$-+,+3$"$,4#■

Update scores of object using comparison result)(& ##,CC# &#(-!$#*+'.!+"#/#/$(( #+/(*(B&$C ( B&'C (&B *&B)

Updated score

Old score$Comparison result%'B

B
Bpaired comparison experiments.”
Glickman, Mark E. "Parameter estimation($)Cin&large dynamicC'CStatistics) 48.3 (1999): 377-394.
Journal of the Royal Statistical Society: Series C $(Applied:#$,$■ Dataset:■ Synthetic (100 objects)■ Image comparison (50 objects)■ Wikipedia article comparison (30 objects)

10Experiment results:
Progressive Comparison and active learning methods■ Experimental results demonstrate the efficiency ofAccuracy of ranking

Accuracy of ranking

Progressive Comparison and its active learning methods

Number of evaluations

Number of evaluations
11Experiment results:
Progressive Comparison and active learning methods■ Experimental results demonstrate the efficiency ofProgressive Comparison and its active learning methods

Standard pairwise(existing method)

Progressive is more
efficient than pairwise
Number of evaluations

Accuracy of ranking

Accuracy of ranking

Progressive Comparison(proposed method)

Number of evaluations
11

Experiment results:
Progressive Comparison and active learning methods■ Experimental results demonstrate the efficiency ofProgressive Comparison and its active learning methods

Standard pairwise(existing method)

Progressive is more
efficient than pairwise
Number of evaluations(ii) CiWP (proposed method)

Accuracy of ranking

Accuracy of ranking

Progressive Comparison(proposed method)(i) CiD (proposed method)
RandomWinning Probabilities
is most efficient
Number of evaluations
11

Conclusions:
Progressive Comparison for Ranking Estimation■ Ranking estimation problem addressed■ Proposed:■ Progressive comparison■ Active learning method of Progressive Comparison■ Change in Distributions■ Change in Winning Probabilities■ Experimental results show:■ Superiority of Progressive Comparison to standard pairwise■ Efficiency of active learning methods for Progressive

Comparison (especially (ii) CiWP)
12