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

Size: px

Start display at page:

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

ひとおちづ
4 years ago
Views:

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

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

3 次 3 研究背景 Copeland Two Stage Pairwise Model 較バンディット + Online CTSPM 実験まとめ今後の課題

4 クラウドソーシングクラウドソーシングとはインターネットを介して様々な仕事 Task を不特定多数の労働者 Worker に依頼し ( 安価に ) 成果物 Artifact を得る枠組み 4 AI に配される々クラウドソーシングの利例画像のアノテーション翻訳説明の成イベントロゴの作成

5 クラウドソーシングの課題 5 Worker の能にばらつきがある能やる気が異なる得意不得意がある複数の Artifact を統合して品質を上げる 2 値分類タスク多数決絶対評価値タスク平均英翻訳タスク??? Artifact が統合できない場合がある最も品質がい Artifact を選べばいい!! どうやって各 Artifact の品質を知る?

6 Two Stage Model [Baba+ 13] 6 各 Artifact の品質もクラウドソーシングで評価 1. Creation Stage Creator が Task に対する Artifact を成 2. Evaluation Stage Evaluator が Artifact に対する絶対評価を成 3. 最終成果物の決定複数の Evaluator の絶対評価を統合 (ex. 平均 ) 統合した評価から最も優れた Artifact を選択

7 Two Stage Model の課題絶対評価は難しい複数で評価基準を共有するのは困難全体的にく低く付けるがいる絶対評価はコストがい各 Artifact を注意深く評価する必要があるい専学 7

8 Two Stage Pairwise Model [Sunahase+ 17] 8 2 つの Artifact のうち優れたを選ぶ 1. Creation Stage Creator が Task に対する Artifact を成 2. Evaluation Stage Evaluator が Artifact に対する相対評価を成 3. 最終成果物の決定複数の較結果から最も優れた Artifact を選択

9 Two Stage Pairwise Model の課題 9 全対較はコストがい 1 回の較コストは低い全対較のコスト = O( Artifact 数の2 乗 ) 下に較を減らすと品質が下がる最終成果物の決定法が明ではない較結果と Artifact の品質の関係は?

10 本研究の的 10 的 Two Stage Pairwise Model のコストを減らす最終成果物の品質はできるだけ下げない提案法 Copeland Two Stage Pairwise Model 較バンディット + Online CTSPM

11 次 11 研究背景 Copeland Two Stage Pairwise Model 較バンディット + Online CTSPM 実験まとめ今後の課題

12 Notation 12 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 すべての集合

13 Two Stage Pairwise Model ( 再掲 ) 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 ) の関係に何らかの仮定が必要

14 Copeland Two Stage Pairwise Model 14 仮定 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 に関して不変

15 Copeland Two Stage Pairwise Model 15 仮定 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* ) ] が最もい

16 Copeland Two Stage Pairwise Model A, W をクラウドソーシングにより得る 2. 経験勝率 pʼi,j を計算 pʼi,j = Σ t [l] Σ k [m] w t,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]} を出

17 Copeland TSPM のコスト 17 C C : Creator 1 に Artifact 1 つを作成してもらうコスト C E : Evaluator 1 に Artifact 2 つを較してもらうコスト C CTSPM : Copeland TSPM を実するコスト C CTSPM = l (mc C + m(m-1)/2 nc E ) m 2 の項がネック à 無駄な較を減らしたい

18 Online CTSPM 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 を得る ( ラウンド ) を s 回繰り返す 5. s 個の較結果から何らかの法で経験 Copeland 勝者 cʼ を計算し,A final = {a t,cʼ t [l]} を出

19 Online CTSPM のコスト 19 C C : Creator 1 に Artifact 1 つを作成してもらうコスト C E : Evaluator 1 に Artifact 2 つを較してもらうコスト 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

20 次 20 研究背景 Copeland Two Stage Pairwise Model 較バンディット + Online CTSPM 実験まとめ今後の課題

21 Online CTSPM 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 を得る ( ラウンド ) を s 回繰り返す 5. s 個の較結果から何らかの法で経験 Copeland 勝者 cʼ を計算し,A final = {a t,cʼ t [l]} を出

22 較バンディットをいた OCTSPM ( 再掲 ) 22 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 を選ぶ問題較バンディット問題そのもの!!

23 確率的バンディット問題 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 学 23

24 較バンディット問題 m 個の選択肢 (今回は Creator の集合) pi,j = i の j に対する勝率 (観測できない) アルゴリズム各ラウンド sʼ で選択肢から２つ選び i(sʼ), j(sʼ) とする i(sʼ), j(sʼ) の勝敗 w(sʼ) {0,1} を得る [Yue+ 12] 24 的 w(sʼ) ~ Bernoulli(pi(sʼ),j(sʼ)) i(s ) Regret(s) = Σsʼ [s] (Li(sʼ) + Lj(sʼ) - 2Lmin) を最化 Li = {j [m] pi,j < ½} Lmin = min{li i 学 j(s )

25 貫性 (Strongly Consistent) 25 アルゴリズムが貫性を持つ E[ Regret(s) ] = o(s α ) を達成する仮説 c* cʼ が有意準 1/s で棄却できる OCTSPM + 貫性のあるアルゴリズム統計的に保証のあるコスト削減が可能

26 較バンディットによるコスト削減 26 無駄な較を減らす Copeland 勝者の候補だけに仕事を依頼 Copeland 勝者の特定だけに較を利推定に信があるときはコストを減らす現時点での Copeland 勝者の推定にがあるときはそもそも較をしない

27 較バンディットアルゴリズムランダム (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ʼ 以上のものを順に試す

28 次 28 研究背景 Copeland Two Stage Pairwise Model 較バンディット + Online CTSPM 実験まとめ今後の課題

29 実験設定 29 的 CTSPM vs Online CTSPM w/ Dueling Bandits コスト削減できていることを確認品質がきく低下しないことを確認データ TSPM で得られた実データ (A + W) 同時に TSM で各 Artifact に絶対評価 (5 段階評価 ) も取得詳細は後述結果経験負け数 Lʼi vs 平均品質 q(a i ) コスト削減率 R vs 経験負け数 Lʼc* コスト削減率 R vs 平均品質 q(a c* )

30 データセット 30 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

31 経験負け数 L i vs 平均品質 q(a i ) 31 両データとも Copeland 勝者が最品質 Description Translation

32 コスト削減率 R vs 負け数 L i 32 30~50% のコストで Copeland 勝者を推定 Description Translation

33 コスト削減率 R vs 平均品質 q(a c* ) 33 30~50% で CTSPM とほぼ同じ品質を達成 Description Translation

34 次 34 研究背景 Copeland Two Stage Pairwise Model 較バンディット + Online CTSPM 実験まとめ今後の課題

35 まとめ今後の課題 35 まとめ TSPM における品質コストトレードオフを動調整する法を提案 Online Copeland TSPM + 較バンディット実データにおいて 30~50 % のコスト削減最終的な品質はほぼそのまま今後の課題より弱い仮定の法を考える ex) Task 毎に分布が異なる Evaluator の能を考慮する今回は平均化により能の違いを吸収している

2

1 12123456789012345678901234 12123456789012345678901234 12123456789012345678901234 12123456789012345678901234 12123456789012345678901234 12123456789012345678901234 12123456789012345678901234 12123456789012345678901234

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

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