較バンディットアルゴリズムを いた クラウドソーシングにおける 品質 コストトレードオフの 動調整 畠正和, 宮 純平, 場雪乃 北海道 学 /NTT, 東京 学, 京都 学

⽐較バンディットアルゴリズムを⽤いた

クラウドソーシングにおける

品質・コストトレードオフの⾃動調整

今⽇のお話（⼀枚概要）

•  問題 •  クラウドソーシングの 品質・コストトレードオフ を調整 •  最終成果物の品質をできるだけ下げず、コストを削減 •  ⼿法 •  ⽐較バンディットアルゴリズム を利⽤ •  有⽤な Worker を推定しながら Task を依頼 •  結果 •  実データでコストを 30~50% に削減 •  品質はほぼそのまま

2

⽬次

•

 

研究背景

• 

Copeland Two Stage Pairwise Model

• 

⽐較バンディット + Online CTSPM

• 

実験

• 

まとめ・今後の課題

クラウドソーシング

• 

クラウドソーシングとは

• 

インターネットを介して

• 

様々な仕事

Task

を

• 

不特定多数の労働者

Worker

に依頼し

• 

（安価に）成果物

Artifact

を得る枠組み

• 

クラウドソーシングの利⽤例

• 

画像のアノテーション

• 

翻訳⽂・説明⽂の⽣成

• 

イベントロゴの作成

4

AI_{に⽀配される⼈々}

クラウドソーシングの課題

•  Worker の能⼒にばらつきがある •  能⼒、やる気が異なる •  得意、不得意がある •  複数の Artifact を統合して品質を上げる •  ２値分類タスク → 多数決 •  絶対評価値タスク → 平均 •  英⽇翻訳タスク → ??? •  Artifact が統合できない場合がある •  最も品質が⾼い Artifact を選べばいい！！ •  どうやって各 Artifact の品質を知る？

5

Two Stage Model

[Baba+ 13]

各

Artifact

の品質もクラウドソーシングで評価

1.  Creation Stage

•  Creator が Task に対する Artifact を⽣成

2.  Evaluation Stage

•  Evaluator が Artifact に対する 絶対評価 を⽣成

3.  最終成果物の決定

•  複数の Evaluator の絶対評価を統合 (ex. 平均) •  統合した評価から最も優れた Artifact を選択

6

Two Stage Model の課題

• 

絶対評価は難しい

• 

複数⼈で評価基準を共有するのは困難

• 

全体的に⾼く・低く付ける⼈がいる

• 

絶対評価はコストが⾼い

• 

各 Artifact を注意深く評価する必要がある

• 

⾼い専⾨性が要求される

7

Two Stage Pairwise Model

[Sunahase+ 17]

２つの

Artifact

のうち優れた⽅を選ぶ

1.  Creation Stage

•  Creator が Task に対する Artifact を⽣成

2.  Evaluation Stage

•  Evaluator が Artifact に対する

相対評価

を⽣成

3.  最終成果物の決定

•  複数の⽐較結果から最も優れた Artifact を選択

Two Stage Pairwise Model の課題

• 

全対⽐較はコストが⾼い

• 

１回の⽐較コストは低い

• 

全対⽐較のコスト = O( Artifact数の２乗 )

• 

下⼿に⽐較を減らすと品質が下がる

• 

最終成果物の決定法が⾃明ではない

• 

⽐較結果と Artifact の品質の関係は？

9

本研究の⽬的

• 

⽬的

• 

Two Stage Pairwise Model のコストを減らす

• 

最終成果物の品質はできるだけ下げない

• 

提案⼿法

• 

Copeland Two Stage Pairwise Model

• 

⽐較バンディット + Online CTSPM

⽬次

• 

研究背景

•

 

Copeland Two Stage Pairwise Model

• 

⽐較バンディット + Online CTSPM

• 

実験

• 

まとめ・今後の課題

Notation

•  l = Task の数 t ∈ [l]

•  m = Creator の数 i, j ∈ [m] •  n = Evaluator の数 k ∈ [n]

•  a_t,i = Task t ∈ [l] に対する Creator i ∈ [m] の Artifact •  w_t,i,j,k = a_t,i と a_t,j の Evaluator k ∈[m] による⽐較結果

•  w_t,i,j,k = 1 : k は a_t,i の⽅がよいと判断 (a_t,i の勝ち) •  w_t,i,j,k = 0 : k は a_t,j の⽅がよいと判断 (a_t,i の負け)

•  A = 得られた a_t,i すべての集合 •  W = 得られた w_t,i,j,kすべての集合

Two Stage Pairwise Model (再掲)

1.  Creator が Artifact A を⽣成

2.  Evaluator が 全対⽐較結果 W を⽣成

3.  W から最終成果物 A

_final

⊆A を決定

–  q(A

_final

) = A

_final

の平均品質 (

観測できない

)

–  q(A

_final

) が⾼くなるように A

_final

を選択

–

 

W と q(A

_final

) の関係に何らかの仮定が必要

Copeland Two Stage Pairwise Model

• 

仮定1: W の分布

• 

w

_t,i,j,k

~ Bernouli(p

*_k,i,j

)

•  P*_k ∈ [0,1]m×m : k の 選好⾏列

•  p*_k,i,j = (P*_k )_i,j : k の Creator i, j に関する選好

• 

解釈

• 

勝率 p

*_k,i,j

は Task t によらない

•  Creator i, j の Evaluator k の判断による勝率は Task に関して不変

Copeland Two Stage Pairwise Model

• 

仮定2: W と q(A) の関係

• 

L

*_i

< L

*_j

⇒ E[q(A

_i

)] > E[q(A

_j

)]

•  P* = P*_k の平均 : 真の選好 •  L*_i = |{j ∈ [m] | p*_i,j < ½}| : P* 上での負け数 •  A_i = {a_t,i | t ∈ [l]}

• 

解釈

• 

Copeland 勝者 : c

*

= argmin

_i∈[m]

L

*_i

•

 

E[ q(A

_c*

) ] が最も⾼い

Copeland Two Stage Pairwise Model

1.  A, W をクラウドソーシングにより得る

2.  経験勝率 p

ʼ i,j

を計算

–  pʼ i,j = Σt∈[l] Σk∈[m] wt,i,j,k / lm

3.  経験負け数 L

ʼ i

を計算

–  Lʼ i = |{j ∈ [m] | pʼi,j < ½ }|

4.  経験 Copeland 勝者 cʼ を計算

–  cʼ = argmin_i∈[m] Lʼ i

5.  A

_final

= {a

_t,cʼ

| t ∈[l]} を出⼒

16

Copeland TSPM のコスト

• 

C

_C

: Creator １⼈に Artifact １つを作成して

もらうコスト

• 

C

_E

: Evaluator １⼈に Artifact ２つを⽐較して

もらうコスト

• 

C

_CTSPM

: Copeland TSPM を実⾏するコスト

• 

C

_CTSPM

= l (mC

_C

+ m(m-1)/2 nC

_E

)

• 

m

2

の項がネック à

無駄な⽐較を減らしたい

17

Online CTSPM

1.  t, i, j, k を

何らかの⽅法

で選ぶ

2.  Creator i, j に Task t を依頼して a

_t,i

, a

_t,j

を得る

3.  Evaluator k に a

_t,i

, a

_t,j

の⽐較を依頼して w

_t,i,j,k

を

得る

4.  1.-3. （ラウンド）を s 回繰り返す

5.  s 個の⽐較結果から

何らかの⽅法

で経験 Copeland

勝者 cʼ を計算し，A

_final

= {a

_t,cʼ

| t ∈[l]} を出⼒

Online CTSPM のコスト

• 

C

_C

: Creator １⼈に Artifact １つを作成してもらう

コスト

• 

C

_E

: Evaluator １⼈に Artifact ２つを⽐較してもら

うコスト

• 

C

_CTSPM

: Copeland TSPM を実⾏するコスト

•  C_CTSPM = l (mC_C + m(m-1)/2 nC_E)

• 

C

_OCTSPM

: Online CTSPM を実⾏するコスト

•  C_OCTSPM ＜ s(2C_C + C_E) + lC_C

19

⽬次

• 

研究背景

• 

Copeland Two Stage Pairwise Model

•

 

⽐較バンディット + Online CTSPM

• 

実験

• 

まとめ・今後の課題

Online CTSPM

1.  t, i, j, k を

何らかの⽅法

で選ぶ

2.  Creator i, j に Task t を依頼して a

_t,i

, a

_t,j

を得る

3.  Evaluator k に a

_t,i

, a

_t,j

の⽐較を依頼して w

_t,i,j,k

を

得る

4.  1.-3. （ラウンド）を s 回繰り返す

5.  s 個の⽐較結果から

何らかの⽅法

で経験 Copeland

勝者 cʼ を計算し，A

_final

= {a

_t,cʼ

| t ∈[l]} を出⼒

⽐較バンディットを⽤いた OCTSPM (再掲)

• 

Copeland TSPM の仮定

1.  w

_t,i,j,k

~ Bernouli(p

* k,i,j

)

2.  E[ q(A

_c*

) ] が⼀番⾼い

•  c* = P* の Copeland 勝者 •  P* _{= Σ P}* k / n

•  à

t, k はランダムに選んで良い

•  à

効率よく c

*

を推定できれば良い

• 

各ラウンドでc

*

らしい Creator i, j を選ぶ問題

•

 

⽐較バンディット問題

そのもの！！

22

確率的バンディット問題

• 

⼊⼒

•  m 個の選択肢 •  μ_i ∈[0,1] : 選択肢 i の期待値 (観測できない)

• 

アルゴリズム

•  各ラウンド sʼ で選択肢から １つ 選び i(sʼ) とする •  i(sʼ) から報酬 R(sʼ) ∈ {0, 1} を得る •  R(sʼ) ~ Bernoulli(μ_i(sʼ))

• 

⽬的

•  Regret(s) = Σ_sʼ∈[s] ( μ_max – μ_i(sʼ) ) の最⼩化 •  μ_max = max{μ_i | i ∈[m]}

⽐較バンディット問題

[Yue+ 12] •  ⼊⼒ •  m 個の選択肢 (今回は Creator の集合) •  p_i,j = i の j に対する勝率 (観測できない) •  アルゴリズム •  各ラウンド sʼ で選択肢から ２つ 選び i(sʼ), j(sʼ) とする •  i(sʼ), j(sʼ) の勝敗 w(sʼ) ∈{0,1} を得る •  w(sʼ) ~ Bernoulli(p_{i(sʼ),j(sʼ)}) •  ⽬的

•  Regret(s) = Σ_sʼ∈[s] (L_i(sʼ) + L_j(sʼ) - 2L_min) を最⼩化 •  L_i = |{j ∈ [m] | p_i,j < ½}|

•  L_min = min{L_i | i ∈ [m]}

24

⼀貫性 (Strongly Consistent)

• 

アルゴリズムが⼀貫性を持つ

• 

E[ Regret(s) ] = o(s

α

) を達成する

• 

仮説「c* ≠ cʼ」が有意⽔準 1/s で棄却できる

• 

OCTSPM + ⼀貫性のあるアルゴリズム

• 

統計的に保証のあるコスト削減が可能

25

⽐較バンディットによるコスト削減

• 

無駄な⽐較を減らす

• 

Copeland 勝者の候補だけに仕事を依頼

• 

Copeland 勝者の特定だけに⽐較を利⽤

• 

推定に⾃信があるときはコストを減らす

• 

現時点での Copeland 勝者の推定に⾃⾝がある

ときは、そもそも⽐較をしない

26

⽐較バンディットアルゴリズム

1.  ランダム (baseline)

•  ランダムに i(sʼ), j(sʼ) を選ぶ •  ⼀貫性なし

2.  Copeland Confidence Bound (CCB) [Zoghi+ 15]

•  Upper Confidence Bound (UCB) の拡張 •  楽観的に Copeland 勝者である確率を推定

3.  ECW-RMED [Komiyama+ 16]

•  Minimum Empirical Divergence (MED) の拡張

•  Copeland 勝者である確率が 1/sʼ 以上のものを順に試す

⽬次

• 

研究背景

• 

Copeland Two Stage Pairwise Model

• 

⽐較バンディット + Online CTSPM

•

 

実験

• 

まとめ・今後の課題

実験設定

•  ⽬的

•  CTSPM vs Online CTSPM w/ Dueling Bandits

•  コスト削減できていることを確認 •  品質が⼤きく低下しないことを確認 •  データ •  TSPM で得られた実データ (A + W) •  同時に TSM で各 Artifact に絶対評価(５段階評価)も取得 •  詳細は後述 •  結果 •  経験負け数 Lʼ_i vs 平均品質 q(A_i) •  コスト削減率 R vs 経験負け数 Lʼ_c* コスト削減率 R vs 平均品質 q(A )

29

データ・セット

• 

Translation

•  Task = 英⽇翻訳 •  l, m, n = 20, 20, 187 •  |A| = 200 •  |W| = 16,314

• 

Description

•  Task = 画像説明 •  l, m, n = 20, 17, 68 •  |A| = 190 •  |W| = 15,980

30

経験負け数

_L

’

i

vs 平均品質 q(A

i

)

31

Description Translation

コスト削減率 R vs 負け数 L

_i

30~50%のコストで Copeland 勝者を推定

32

コスト削減率 R vs 平均品質 q(A

_c*

)

30~50%で CTSPM とほぼ同じ品質を達成

33

⽬次

• 

研究背景

• 

Copeland Two Stage Pairwise Model

• 

⽐較バンディット + Online CTSPM

• 

実験

•

 

まとめ・今後の課題

まとめ・今後の課題

• 

まとめ

•  TSPMにおける品質・コストトレードオフを⾃動調整す る⼿法を提案 •  Online Copeland TSPM + ⽐較バンディット •  実データにおいて 30~50 % のコスト削減 •  最終的な品質はほぼそのまま

• 

今後の課題

•  より弱い仮定の⼿法を考える •  ex) Task 毎に分布が異なる •  Evaluator の能⼒を考慮する •  今回は平均化により能⼒の違いを吸収している

35