Progressive Comparison for Ranking Estimation (IJCAI-16)

Progressive Comparison for
Ranking 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
鵜飼紀衣 ∗2
Ryusuke Takahama
Naoki Otani
Sho Yokoi
Tomohiro Arai
Nozomi Nori
Norie Ugai
∗1
中澤巧爾 ∗2
鹿島久嗣 ∗2
Koji Nakazawa
Hisashi Kashima
京都大学工学部情報学科計算機科学コースソフトウェア基礎論分野
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 tough
Comparison
results
Objects
Score: high
>
Data
collection
>
Estimated
ranking
1st
Estimation
algorithm
2nd
>
3rd
>
4th
Score: 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
>
Data
collection
>
Estimated
ranking
1st
Estimation
algorithm
2nd
>
3rd
>
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
Comparison
results
Objects
Score: high
>
Data
collection
>
Estimated
ranking
1st
Estimation
algorithm
2nd
>
3rd
Time-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
Estimated
ranking
Proposed to collect data
efficiently:
Comparison
results
・Progressive Comparison
Score: high
Objects
・Active learning method for Progressive Comparison
>
Data
collection
>
1st
Estimation
algorithm
2nd
>
3rd
>
4th
Score: low
7
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 of
a 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 the
better of the two?
Object A
Evaluation
Object B
Evaluation
Comparison
Object B
Evaluation
Comparison
Object C
Object C
Evaluation
Evaluation
Object D
Evaluation
3 comparisons
need
6 evaluations
■ Proposed method (Progressive Comparison):
Comparison: which is the better
between the current object and the
previously evaluated one?
Comparison
Comparison
Object A
Object B
Object C
Object D
Evaluation
Evaluation
Evaluation
Evaluation
3 comparisons
need
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 be
compared in two consecutive comparisons
Object 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 C
Object 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 of
object oi
If oi wins
against oj:
Distribution of score of
object 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 wins
against 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
Estimated
ranking
Comparison
results
Objects
Score: high
>
Data
collection
>
1st
Estimation
algorithm
2nd
>
3rd
>
4th
Score: low
14
Experiment settings:
Ranking estimation using Glicko Update Equation
Estimated
ranking
Comparison
results
Objects
Score: high
>
Data
collection
>
>
Proposed:
>
Progressive Comparison
Active learning
1st
Estimation
algorithm
2nd
3rd
4th
Score: low
14
Experiment settings:
Ranking estimation using Glicko Update Equation
Estimated
ranking
Comparison
results
Objects
Score: high
>
Data
collection
>
>
1st
Estimation
algorithm
2nd
3rd
Employed:
>Glicko Update Equation
4th
Score: low
14
!
!!'!( #&HGG +(*
)(
"
!BG
#
C
C
%
"!!"#/
$
#
"!!
"#
/
$
(
(
( # .!( %
Experiment (&B
settings:
!!'!( #&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'"1
Equation:
3+,&'(+5
'( $;-,$44')( EIF7 >#$ .$"+'54 )* "#$ .$,'0+"')( +,$ '( !-6-.+"'(&
+5&),'"#3
+--,);'3+"$4
$;-,$44')(
EIF %1 + (),3+5
.$(4'"1 :'"# 3
■>#$
Online
ranking
estimation
algorithm
of Bradley-Terry
model
)
)C
+(.
$
,$4-$2"'0$517 >#$ -+,+3$"$,4 +,$ &'0$( %1
0+,'+(2$
-+,+3$"$,4
#
■
Update scores of object using comparison result
)(
& #
#
,
C
C
# &#(
-!$
#
*+
'
.!+"#/
#
/
$
(
( #+/
(*
(
B&$C ( B&'C (&B *&B
)
Updated score
Old score
$
Comparison result
%'B
B
Bpaired comparison experiments.”
Glickman, Mark E. "Parameter estimation
(
$)Cin&large dynamic
C
'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 of
Progressive 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 of
Progressive 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)
Random
Winning 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

Download Report