Progressive Comparison forRanking Estimation (IJCAI-16)
Ryusuke Takahama Kyoto University / JST, ERATO
Toshihiro Kamishima AIST
Hisashi Kashima Kyoto University

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

2

The 1st All Japan Yatsuhashi Championship

The 1st All Japan Yatsuhashi Championship, 2014

私たちはお土産にどの八ッ橋を買えばよいのか
Which is the Best Yatsuhashi Brand for a Souvenir?
高濱 隆輔 ∗1

大谷 直樹 ∗1

横井 祥 ∗1

荒井 智裕 ∗1

則 のぞみ ∗2

鵜飼 紀衣 ∗2Ryusuke Takahama

Naoki Otani

Sho Yokoi

Tomohiro Arai

Nozomi Nori

Norie Ugai

中澤 巧爾 ∗2

鹿島 久嗣 ∗2

Koji Nakazawa

Hisashi Kashima∗1

京都大学工学部情報学科 計算機科学コース ソフトウェア基礎論分野

Group of Foundation of Software Science, Undergraduate Course Program of Computer Science
Undergraduate School of Infomatics and Mathematical Science, Faculty of Engineering, Kyoto University∗2

京都大学大学院情報学研究科 知能情報学専攻 ソフトウェア基礎論分野
Group of Foundation of Software Science, Department of Intelligence Science and Technology
Graduate School of Informatics, Kyoto University

れを買っても同じなのかという問いに答えるべく，数理モデルを用いた検証を行った。具体的には，先行研究 [e京都 10] に基づき，京都市内で販売されている八ッ橋のうち主要なもの 11 銘柄を，9 人の評価者が実際に試食，評価を行い，これを(1) 勝率(2) 主固有ベクトル [Keener 93](3) Bradley-Terry モデル [Bradley 52]`Pictures are reprinted from http://togetter.com/li/796213

5`

Pictures are reprinted from http://togetter.com/li/796213

5

Background:
The 1st All Japan Yatsuhashi Championship■ Estimate Yatsuhashi ranking using pairwise comparison data
■ Data-collection (e.g. eating) is very toughComparison
results

Objects

Score: high>Datacollection>

Estimatedranking

1stEstimation
algorithm

2nd>

3rd>

4thScore: low

Pictures are reprinted from http://www.oboco.net/6

Problem setting:
Estimate ranking from pairwise comparison data
■ Estimate objects ranking using pairwise comparison data
■ Efficient data-collection method is required
Comparison
results

Objects

Score: high>Datacollection>

Estimatedranking

1stEstimation
algorithm

2nd>

3rd>

4th
Score: low7

Problem setting:
Estimate ranking from pairwise comparison data
■ Estimate objects ranking using pairwise comparison data
■ Efficient data-collection method is required
Comparison
results

Objects

Score: high>Datacollection>

Estimatedranking

1stEstimation
algorithm

2nd>

3rdTime-consuming or>
expensive to obtain!

4th
Score: low

7

Problem setting:
Estimate ranking from pairwise comparison data
■ Estimate objects ranking using pairwise comparison data
■ Efficient data-collection method is required

Estimatedranking

Proposed to collect data
efficiently:
Comparison
results
・Progressive Comparison
Score: highObjects
・Active learning method for Progressive Comparison>

Datacollection>

1st

Estimation
algorithm

2nd>

3rd>

4th
Score: low7

Model of evaluators:
Evaluators evaluate objects and then compare them
■ Definition:■ Evaluation: giving an (internal) score to an object■ Comparison: determining the winner based on the two objects

scores to create one comparison result■ Assumption:■ The cost of an evaluation is substantially larger than that ofa comparison■ Evaluators can not remember many internal scores of objects
Comparison

Object A

Evaluation

Object B

Evaluation

8

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

EvaluationEvaluation

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
9

Standard pairwise v.s. Progressive:
Progressive Comparison needs fewer evaluations■ Standard pairwise comparison:■ N comparison results need 2N evaluations of objects
Object A

Object B

Object B

Object C

Object C

Object D

3 comparisons needs 6 evaluations■ Progressive Comparison:■ N comparison results need (N + 1) evaluations of objects■ However, this method has a constraint: each object must becompared in two consecutive comparisonsObject A

Object B

Object C

Object D

3 comparisons needs 4 evaluations

10

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 CObject D

Comparison

Next evaluated object
determined by utility value
11(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:12(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
Oi

Oj

ー 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 winsagainst oi:Oi

Ojー 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 ー13

Experiment settings:
Ranking estimation using Glicko Update Equation
EstimatedrankingComparison
results

Objects

Score: high>Datacollection>

1stEstimation
algorithm

2nd>

3rd>

4th
Score: low14

Experiment settings:
Ranking estimation using Glicko Update Equation
EstimatedrankingComparison
results

Objects

Score: high>Datacollection>>

Proposed:>
Progressive ComparisonActive learning

1stEstimation
algorithm

2nd

3rd
4th
Score: low

14

Experiment settings:
Ranking estimation using Glicko Update Equation
Estimatedranking

Comparisonresults

Objects

Score: high>Datacollection>>

1stEstimation
algorithm

2nd

3rd

Employed:>Glicko Update Equation 4thScore: low

14!

!!'!( #&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■>#$Onlineranking
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)

15Experiment results:
Progressive Comparison and active learning methods■ Experimental results demonstrate the efficiency of

Accuracy of ranking

Accuracy of ranking

Progressive Comparison and its active learning methods

Number of evaluations

Number of evaluations
16

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
16

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
16

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)
17