DEIM Forum 2016 F6-4

グループローテーション型クラウドソーシングの制御手法の提案
熊井克仁†

白石 優旗††

張

建偉††

森嶋

厚行†††

† 筑波大学 情報学群情報メディア創成学類 〒 305–8550 茨城県つくば市春日 1-2†† 筑波技術大学産業技術学部 〒 305–8520 茨城県つくば市天久保 4 丁目 3-15††† 筑波大学図書館情報メディア系/知的コミュニティ基盤研究センター 〒 305–8550 茨城県つくば市春日 1-2
E-mail: †katsumi.kumai.2015b@mlab.info, ††{yuhkis,zhangjw}@a.tsukuba-tech.ac.jp,†††mori@slis.tsukuba.ac.jp
あらまし

多くの人々で分担して通訳などを行う際に，複数のグループにわけて，グループ毎に順次通訳を行うような仕組みが考えられる．これを本稿ではグループローテーションと呼び，この考え方を取り入れたクラウドソーシン
グをグループローテーション型クラウドソーシングと呼ぶ．本クラウドソーシングにおける問題は，参加者の出入りが激しいため，グループの構成を動的に変更しなければならないことである．しかし，好き勝手に構成を変更すれば，参加者が戸惑うことになる．本稿では，このような点を考慮したグループローテーション型クラウドソーシングにおけるグループ再構成の問題を提案し，複数の手法で比較を行う．
キーワード

クラウドソーシング，リアルタイム，割り当て制御

1. は じ め に
近年，計算機ネットワーク技術の発達により，ネットワーク
上の多くの人々へのアクセスが容易になった．このような背景のもと，注目を集めているのがクラウドソーシングである．ク
ラウドソーシングとは，計算機ネットワークを通じて不特定多数の人々（ワーカ）に業務 (タスク) を委託することである．そのクラウドソーシングの形式の一つに，マイクロタスク型クラウドソーシングがある．マイクロタスクとは一つ一つのタスクが小さく，短時間でこなせるものである．
一方，クラウドソーシングに限らないが，複数人数でマイクロタスク型の作業を行う作業の形態の一つに，本論文でグルー
プローテーションと呼ぶものがある．これは，図 1 のように，人々のグループを複数用意し，タスクを順にグループに割り当
図1てていくものである．複数人が各グループに所属するのはタス

グループローテーションモデル

ク結果の品質向上のためであり，例えば多数決などを用いて，グループ毎にタスクの作業結果を求める．

ループへのタスク割り当てを変更していく．例 1 と同様に，タ

本論文では，クラウドソーシングを用いてこのようなグルー

スク画面上には，自分がタスクを行うまでの残りタスク処理数

プローテーション型の作業を行う際に生じる問題について議論を表示する．グループ内の多数決などで，グループ毎の結果をする．そのようなクラウドソーシングの例としては，次のよう計算し，シーンを抽出する．

なものが考えられる．
例 1: 通訳． この場合，各タスクでは，講演などの音声を聞

このようなグループローテーションにおいては，次の条件を必ず満たす必要がある．

きながら，1 文ずつ通訳を行う作業を行う．そして，次の文になると，次のグループにタスクを割り当てる (図 1)．突然タス

条件 1:

クが割り当てられて戸惑わないように，自分の番でない場合に(d はアプリケーションによって決定)．

グループ内のワーカの人数が，常に d 人以上である

は，タスク画面上に「あと 10 タスク後にあなたが通訳を行います」などの案内を出す．各グループのワーカによる通訳結果
は，何らかの形で統合され，出力される．

本論文で扱う問題．グループローテーション作業をクラウド
ソーシングで行う場合には，ワーカの出入りを制御できないた

例 2: スポーツ中継のシーン抽出．この場合，各タスクでは，

め，人数の増減が避けられない．したがって，これを考慮する

中継動画を一定時間で区切り，その動画で例えば反則などと思ことが必要となる．まず，ワーカの人数が非常に多くなった場

われるタイミングでボタンを押してもらう．一定時間ごとにグ合，固定したグループ数でタスクを行うと，グループ内の人数

は増えるものの，各人の負担は変わらない．もしグループ数をを用いて，文字おこしを行う研究 [1] が存在する．この研究に増やすことができれば，ワーカの負担を軽減することができる．

おいて，Lasecki らは SCRIBE という文字おこしのためのアプ

一方，ワーカの人数が少なくなり，d 未満になった場合には，ア

リケーションを提案している．SCRIBE では，リテイナーシ

プリケーションによる要求を満たさなくなってしまう．その場

ステム [2] というリアルタイムなクラウドソーシングに特化し合には，グループを統合したり，人が余っているグループからたアイデアが採用されている．リテイナーシステムとは，あら足りないグループに移動する必要がある．

かじめワーカに報酬の一部を支払うことで，指定した時間にタしたがって，グループローテーション型クラウドソーシング
では，次の条件を満たす必要がある．

スクを行うことをワーカと契約するというアイデアである．リテイナーシステムを提案した論文 [2] では，２秒以内にワーカからのレスポンスが期待できると記されている．また，リテイ

条件 2: ワーカの人数に応じて，グループ数の増減や人の移動

ナーシステムを用いた論文 [3] [4] において，ワーカが契約通りを行う．

にタスクに協力するという信頼性が証明されている．そのため，

SCRIBE ではワーカが増減することを想定していない．本研究
この問題は，B 木の問題と似ているが，B 木と異なり，移動

では，リテイナーシステムによらないグループローテーション

するのはデータではなく人間である．例えば，あと 10 文後に型クラウドソーシングについて考察する．雇用関係のないワー

自分の番だと思っていたワーカのタスク割り当ての順番が，突カに対してグループの割り当てを行うことを想定し，ワーカの然あと 1 文後になってしまうなどすると，ワーカは戸惑うこと増減が起こってもワーカの戸惑いが大きくないような制御手法になる．したがって，次の条件を満たす必要がある．

を提案する．
また，本研究の分割や統合，移動の手法は B 木 [5] の分割や条件 3: ワーカが戸惑うような変化を避ける．

統合，移動の考え方に似ている．しかし，本研究では移動するのはデータではなくワーカであるため，できるだけワーカの戸本論文では，これらの条件 1,2,3 を全て満たすグループロー
テーション型のクラウドソーシング制御という問題に取組むことを提案し，複数のアルゴリズムの提案，比較実験を行う．特惑いが少ないようにグループ所属を変更する必要がある．

3. グループローテーションモデルの形式化に，条件 2 と条件 3 は互いに直感的にトレードオフの関係にあ

ここでは，グループローテーションモデルを定義する．そしり，これらをある程度両立する制御手法が存在するかどうかはて，グループローテーション型クラウドソーシングにおける自明ではない．

ワーカの出入りを問題として形式化する．

本研究の貢献は次の通りである．

3. 1 グループローテーションモデルにおける状態(1) 制御手法の問題提案．我々の知る限り，本論文は，グルー

グループローテーションモデルを定義するにあたり，まず，

プローテーション型クラウドソーシングにおけるワーカの出入

グループローテーションモデルの状態について述べる．グルー

りの問題に注目し，その制御を行うという問題を提起した初め

プローテーションモデルの状態とは，グループローテーションての論文である．目標となる具体的な条件を示し，これらを満モデルを用いた作業順序のスナップショットである．図 1 は，たす手法を開発することを提案している．

グループローテーションモデルの状態の例である．形式的には，(2) 問題の形式化．本論文では，グループローテーション型ク

次のように定義される．

ラウドソーシングにおけるワーカの出入りの問題を形式化する． ［定義 1］ グループローテーションモデルにおける状態 S は，

(3) 複数手法の提案．本論文では，ワーカが出入りする際のグループ割り当ての制御の手法を複数提案する．

(4) シミュレーション評価による比較．本論文では，提案した複数の手法について，様々にパラメータを変更して比較評価を行った結果を示す．それにより，条件 2 と 3 をある程度両立す
る優れた手法が存在することを示す．
本論文は次のように構成される．2 章では，関連研究について述べる．3 章では，グループローテーションモデルの定義に

5 項組 S = (W, G, p, Succ, Assign) である．ただし，•

W = {w1 , w2 , …, wn } は，現在参加しているワーカの集合である．図 1 では |W | = 9 である．

•

G = {g1 , g2 , …, gm } は，現在存在するグループの集合である．図 1 では G = {g1 , g2 , g3 } である．

•

p ∈ G は，現在タスク割り当て中のグループである．図

1 では p = g1 である．
•

Succ : G → G：あるグループ gx ∈ G が与えられたついて述べ，問題を形式化する．4 章では，具体的なワーカ参

とき，gx の次にタスクを割り当てられるグループ gx′ ∈ G を入時，離脱時の処理について述べる．5 章では，提案手法を用返す関数である．図 1 では，Succ(g1 ) = g2 , Succ(g2 ) = g3 ,いたシミュレーションについて述べる．6 章では，まとめと今

Succ(g3 ) = g1 である．

後の予定を述べる．

2. 関連研究・関連システム•

Assign : W → G：あるワーカ wx ∈ W が与えられたとき，所属するグループ gx ∈ G を返す関数である．
こ こ で ，Wgx を ，グ ル ー プ gx に 所 属 す る ワ ー カ の 集 合本論文では，グループローテーション型クラウドソーシング{w|Assign(w) = gx } とする．状態 S においては，全てのにおける制御手法ついて提案するが，グループローテーション

ワーカが必ず gx のいずれか一つに属し，グループ内のワーカ

の人数は 1 以上 でなければならない．すなわち，次の条件を必

Algorithm 1 ワーカの挿入の疑似コード

ず満たさなければならない．

Input: d, Si , Wi+1

（ 1 ） Wg1 ⊕ Wg2 ⊕ · · · ⊕ Wgm = W

Output: Si+1

（ 2 ） ∀gx ∈ G (|Wgx | >= 1)

1: win = Wi+1 − Wi3. 2 グループローテーションモデル
グループローテーションモデル M とは，ワーカの集合の列

W1 , W2 , . . . , Wt (ただし |Wi+1 − Wi | <= 1) を与えると，グルー

2: gx = pickup(Gi )3: if |Wgx | < max then4:

insert win to gx

5: else if |Wgx | == max then

プローテーションの状態の列 S1 , S2 , . . . , St を生成するもので6:

insert win to gx

あり，次のように定義される．

7:

divide gx［定義 2］ グループローテーションモデル M は 3 項組 M =8: end if(d, S0 , N ext) である．ただし，•d は，グループ内のワーカの最低人数である．

•

そのグループに所属させ，そのグループのサイズが規定値 max

S0 = (W0 , G0 , p0 , Succ0 , Assign0 ) は，グループロー
テーションモデルの初期状態である．ただし，∀g ∈ G0 (|Wg | >=を越えたらグループを分割する．

d) である必要がある．

動作する．

•

N ext は，状態 Si ，Wi+1 ，d が与えられたとき，次の状

態 Si+1 = N ext(d, Si , Wi+1 ) を求める関数である．

具体的な制御手法を Algorithm 1 に示す．これは次のように（ 1 ） ワーカを挿入すべきグループ gx を決定する．(2 行目)（ 2 ） もし，gx に所属しているワーカ数 |Wgx | が max 未満

3. 3 N ext 関数

ならば，gx にワーカを挿入して終了する．(3〜4 行目) それ以

N ext(d, Si , Wi+1 ) は次のように動作する．

外の場合は，（3）にすすむ．

•|Wi − Wi+1 | = 0 の場合，Si+1 は，Si と同じであるが，（ 3 ） gx に所属しているワーカ数 |Wgx | が max の時は (5〜

タスク割り当て中のグループを次に進めた状態になる．具体的7 行目)，グループの分割を行う．分割の処理を具体的に説明すには，Si における Succi に従い，現在タスク割り当て中のグる．まず，新たなグループ gnew を確保する．そして，挿入すループ p を次にタスクを割り当てるグループ Succi (p) に変更するワーカと gx に所属するワーカを合わせた max + 1 のワーカる．したがって，Si+1 = (Wi+1 , Gi , Succi (p), Succi , Assigni )の半分を gx に，残り半分を gnew に所属させる．

となる．

•

分割のためのパラメータ|Wi+1 − Wi | = 1 の場合，Si+1 は，Si に対してワーカ

グループローテーションでは，グループ内のワーカの最大人が増加した状態になる．タスク割当てグループは移動しない．

数 max の決め方によって，分割の頻度を調節できると考えら

N ext 関数 は，新ワーカ Win = Wi+1 − Wi を所属させるグれる．例えば，max = 3d とすると，max = 2d の場合よりもループを決定してそのグループにワーカを追加し，必要に応じ分割が生じにくくなる．また分割の際，グループは 2 分割されてグループの分割を行う (4. 1 節)．その結果を新たな状態 Si+1

るため，max を 2d よりも大きくすると，グループの分割後のとする．

2 つのグループ内のワーカ数が d よりも十分大きくなると考え•|Wi − Wi+1 | = 1 の場合，Si+1 は，Si に対してワーカられる．グループ内のワーカ数が d よりも十分多い場合統合がが減少した状態になる．タスク割当てグループは移動しない．

生じにくくなる．そこで，グループのワーカの最大人数 max

N ext 関数 は，離脱ワーカ Wout = Wi − Wi+1 をグループかを様々な値に変化させることで結果の違いを考察する．max がら離脱させ，それにしたがい，ワーカの移動やグループの統合

大きくなればなるほど，分割や統合が起こりづらいが，グルーを行う (4. 2 節)．その結果を新たな状態 Si+1 とする．

プ数は増えづらくなると考えられる．シミュレーションでは，

上記において，ワーカを所属させるグループの決定にはいく
つかの方法が考えられる．本論文では，4. 1. 2 節で 3 種類の方

max のパラメータを変え，結果の違いを考察する．
4. 1. 2 グループの選択方法

法を説明する．実験結果が示すとおり，ワーカ挿入時のグルー

先述したように，ワーカ参入時のグループの選択方法の違い

プの選択方法の違いが，グループ数の増減と分割と統合の回数

が，グループ数の増減と分割と統合の回数に大きな影響を与えに大きな影響を与える．

る．そこでワーカ挿入時のグループ選択として３つの手法を提グループの分割，ワーカの移動，グループの統合に関しては，合理的な方法はそれぞれ一つに決まるため，それらを説明する．

案する．
単純追加法．単純追加法は，タスクが終わった直後のグループ

4. N ext 関数の処理に新しいワーカを所属させる手法である．この手法では，タ4. 1 ワーカ参入時の処理

ワーカの挿入により分割が起きたとしても，ワーカの戸惑いが

本節では，N ext 関数におけるワーカ参入時の処理について

小さい．図 2 に手法のイメージ図を示す．

説明する．

4. 1. 1 ワーカ参入時の処理とグループ分割
ワーカ参入時には，ワーカを所属させるグループを決定し，スクが終わった直後のグループにワーカを所属させることで，バランス優先法．バランス優先法は，グループ内のワーカ数が最小のグループにワーカを所属させる手法である．もし，グなった時，グループ間の移動や統合が行われることを考える．
ワーカの戸惑いを少なくするためには，移動や統合が起きたと
き，あるグループ gx がタスクを行うまでの残りグループ数（以降 Jgx と表す）の変化が出来るだけ少ないことが望ましい．そこで本手法では，隣接するグループとのみ移動や統合を行う．
隣接するグループは，gx の直後にタスクを行うグループ（gbackとする）と gx の直前にタスクを行うグループ（gf ront とする）
がある．
図2

単純追加法

ワーカの移動ワーカの移動を行う際，Jgf ront < Jgx < Jgback より，gx から gback に移動する場合は，タスクを行う順番が遅くなるため，
ワーカの戸惑いが少ない．しかし，gx から gf ront に移動する
場合は，タスクを行う順番が早まるため，ワーカの戸惑いが大きい．そこで本手法では，グループの移動を行う際は gx から

gback に移動することを優先する．
グループの統合図3

バランス優先法グループの統合を行う際は，統合が行われたグループよりもタスクを行う順番が遅いグループ全てに対して，タスクを行う
順番が早まるという変更が行われてしまう．そのため，gx と

gf ront が統合するよりも，gx と gback が統合したほうが全体としてのタスクを行う順番の変更は少なくなる．そこで本手法では，グループの統合を行う際は gx と gback を統合する．
例外処理
図4

分割優先法

gx がタスク割り当て中のグループの場合，これまでに説明した手法を適応してしまうと，gf ront のワーカが，gx に移動さ

ループ内のワーカ数が最小のグループが複数ある場合は，そのせられることがある．その場合，タスクを行うの順番を示す案

中でタスクを行うまでの残りグループ数が多いグループにワー

内が「あなたがタスクを行う番です」から「あと 10 回であな

カを挿入する．この手法では，おおよそ１グループのワーカのたがタスクを行う番です」に変わり，その後タスクが発行され人数が均等になり，グループの分割，統合が起こりにくくなる．

ると再び「あなたがタスクを行う番です」と変わり，ワーカを

図 3 に手法のイメージ図を示す．

戸惑わせる．また，Jgx = 1 の場合，同様に手法を適用すると，

分割優先法．分割優先法は，グループ内のワーカ数が最大のグ

gf ront に所属するタスクを処理している最中のワーカが gx に

ループにワーカを所属させる手法である．もし，グループ内の移動することがある．その場合，タスクを行うの順番を示す案

ワーカ数が最大のグループが複数ある場合は，その中でタスク

内が「あなたがタスクを行う番です」から「あと 1 回であなたを行うまでの残りグループ数が多いグループにワーカを挿入すがタスクを行う番です」に変わり，その後タスクが発行される

る．タスクこの手法では，グループの分割が早まり，グループと再び「あなたがタスクを行う番です」と変わり，ワーカを戸数が増加しやすくなる．図 4 に手法のイメージ図を示す．

惑わせる．そこで，例外的な処理を行う必要がある．本手法で4. 2 ワーカ離脱時の処理

は，Jgx = 0 の時または，Jgx = 1 の時は，gf ront との移動や本節では，N ext 関数におけるワーカ離脱時の処理について

統合は行わない．

説明する．ワーカの挿入時と同様に，ワーカが減少した際にも，

4. 2. 2 ワーカ離脱時の具体的な制御

N ext 関数によって，グループローテーションモデルの状態は

グループローテーションにおいて，グループ内のワーカ数が変化する．ただし，ワーカが離脱する際は，離脱するグループ

d 以上であるという条件を満たしつつ，できるだけワーカの戸はワーカの意志によって決定されるため，ワーカの挿入時とは惑いが少ない移動や統合の具体的な制御手法を Algorithm 2 に異なり，離脱するグループをこちらで制御することが出来な示す．また，図 5，図 6，図 7 にワーカ離脱時の具体的な制御い．このような条件のもと，あるグループ内のワーカ数が d をの主な動作のイメージを示す．Algorithm 2 は次のように動作

下回った場合，移動や統合を行い，グループ内のワーカ数が dする．

以上である条件を満たす必要がある．ここでは，グループロー（ 1 ） 離脱すべきワーカが所属するグループ gx を取得する．

テーションにおいて，条件を満たしつつ，できるだけワーカの(2 行目)

戸惑いが少ない移動や統合の手法を提案する．

（ 2 ） もし，gx に所属しているワーカ数 |Wgx | が d + 1 以上

4. 2. 1 ワーカの戸惑いが少ない移動や統合の制御

ならば，gx からワーカを離脱させて終了する．それ以外の場合あるグループ gx のグループ内ワーカ数が条件を満たさなくは，（3）または（5）にすすむ．(4 行目)

Algorithm 2 ワーカの離脱の疑似コード
Input: d, Si , Wi+1
Output: Si+1
1: wout = Wi − Wi+1
2: gx = pickup(Gi )3: if |Wgx | >= d + 1 thendelete wout from gx

4:

図 5 gf ront から gx へ移動時

5: else if |Wgx | == d then6:

delete wout from gx

7:

if Jgx == 0||Jgx == 1 then8:

if |Wgback | == d + 1 thenmove workers from gback to gx

9:else if |Wgback | == d then10:

merge gx and gback

11:

end if12:

図 6 gback から gx へ移動時

else

13:

if |Wgf ront | == d + 1 then14:

move workers from gf ront to gx

15:
16:

else if |Wgf ront | == d then17:

if |Wgback | == d + 1 thenmove workers from gback to gx

18:

else if |Wgback | == d then19:merge gx and gback

20:

end if21:

図 7 gback と gx の統合時

end if22:

end if23:［Jgx =0 または Jgx = 1 の時］(7〜12 行目)（ 3 ） gx に所属しているワーカ数 |Wgx | が d の時は，gx からワーカを離脱させ，gback を調べる．gback に所属している
ワーカ数 |Wgback | が d + 1 以上ならば，条件を満たすように

gback から gx にワーカを移動させる．(8〜9 行目)（ 4 ） gback に所属しているワーカ数 |Wgback | が d ならば，gx と gback を統合する．gback に所属するワーカの所属を gx に変更する．(10〜11 行目)［それ以外のグループの時］(14〜22 行目)（ 5 ） gx に所属しているワーカ数 |Wgx | が d の時は，gx からワーカを離脱させ，gf ront を調べる．gf ront に所属している
ワーカ数 |Wgf ront | が d + 1 以上ならば，条件を満たすように

24: end ifの変更によるワーカの戸惑いが大きくなると考えられる．そこ
で，Jgx < L(L は自然数) のグループに対しては，分割や統合，移動は行わないという制御を行う．具体的には，L = 1 とした
場合，Jgk = 0 のグループ gk に対しては，グループ内の人数|Wgk | が max を上回っても分割を行わない．また，|Wgk | が dを下回っても統合，移動は行わない．そして，タスクの割り当てが変更され，Jgk = |G| − 1 となった時，つまり，gk がタス
クから最も遠くなった時に，分割，統合，移動の処理を行う．
シミュレーションでは，L のパラメータを変え，比較を行う．

5. シミュレーション

gf ront から gx にワーカを移動させる．(14〜15 行目)（ 6 ） gf ront に所属しているワーカ数 |Wgf ront | が d ならば，gback を調べる．gback に所属しているワーカ数 |Wgback | が d+1以上ならば，条件を満たすように gback から gx にワーカを移動させる．(16〜18 行目)（ 7 ） gf ront に所属しているワーカ数 |Wgf ront | が d かつ，gback に所属しているワーカ数 |Wgback | が d ならば，gx と gbackを統合する．gback に所属するワーカの所属を gx に変更する．

(19〜20 行目)
4. 3 タスク直前のグループの分割や統合，移動を禁止
本節では，ワーカの戸惑いを削減するためにワーカ参入時，離脱時に共通して行う制御方法について述べる．
グループローテーションでは，あるグループ gx のタスクが割り当てらるまでの回数 Jgx が小さいほど，グループの所属

本章では，4. 1. 2 節で述べた提案手法を用いて行ったシミュ
レーションについて述べる．

5. 1 概要4. 1. 2 節で述べたワーカ参入時におけるグループの選択方法である単純追加法，バランス優先法，分割優先法についてシ
ミュレーションを行い，グループ数とタスクを行う順番の変更
によるワーカの戸惑いの 2 点からそれぞれの手法の考察を行う．

5. 1. 1 設

定

シミュレーションの際には，次のように設定を行った．

•

M

=

(2, S0 , N ext)，た だ し ，初 期 状 態 S0=

(W0 , G0 , p0 , Succ0 , Assign0 ) では，|W0 | = 60, |G0 | = 20,
および ∀gx ∈ G0 (|Wgx | = 3)•

N ext 関数では，3 種類のグループ選択手法をそれぞれ行い，比較する．

•

50

単純追加法
バランス優先法
分割優先法

ワーカ集合の列 W1 , W2 , . . . については，次の手法で計算する．まず，W0 からスタートして，λ = 1.5 のポアソン分

40

Wi+1 を追加する．それと平行して，一定時間毎にタスクが移動すると仮定し，10 秒毎に Wi+1 = Wi となるような Wi+1 を追加する．この列を，タスクが 100 個移動するまで生成する．

グループ数

布に従いワーカの増減を決定し，増減が行われるたびに新しい30

20

5. 1. 2 ワーカの戸惑い（P EN ALT Y ）ここで，分割と統合によってタスクを行う順番が変更される

10

ことで生じるワーカの戸惑いを，計算式によってスコアとして数値化する．ワーカの戸惑いはワーカの所属するグループ gx

0
0

1
(0 <
= Jgx <
= |G| − 1)
Jgx + 1

(1)

40

60

80

100

タスク数

のタスクまでの残りグループ数 Jgx を用いて次のように表す．

P EN ALT Y =20

図 8 グループ数の推移考えられる．一方で，バランス優先法はグループ数があまり増えず，ある程度一定のグループ数を保っている．このことから，

ワーカの戸惑いは Jgx が小さければ小さいほど大きくなる．

1 人のワーカのタスクの処理回数は多いが，グループの分割や(1) 式はこの考え方に従い，Jgx が小さければ小さいほど値が統合はあまり起こらないため，ワーカの順番の変更による戸惑

大きくなるように，Jgx の逆数をとり，ワーカの戸惑いを数値

いは少ないと考えられる．

化している．

図 9 に，提案手法ごとの P EN ALT Y の合計値の推移を示

また，分割や統合によりワーカのグループ所属が変更される

す．グラフの傾きがが大きければ大きいほど，分割や統合，移際，タスクまでの残りグループ数が増える場合にはワーカの戸動によりタスクを行う順番の変更が起きた回数が多いと言える．

惑いが少ないが，減る場合にはワーカの戸惑いは大きくなる．

または，ワーカの戸惑いが大きい順番の変更が起こったと言え

例えば，グループ所属の変更により，あるワーカがタスクまで

る．図から，分割優先法は傾きが大きく，バランス優先法は傾の残りグループ数を 3 から 4 に変更される場合，タスクまできが小さいことが確認できる．このことから，分割優先法は比の時間的余裕が生まれ，ワーカにとって大きな戸惑いにはなら較的，分割や統合の回数が多くグループ数が安定しないが，バない．しかし，タスクまでの残りグループ数が 3 から 2 に変ランス優先法は分割や統合の回数が少なく，グループ数が安定更される場合，急にタスクを行うまでの時間が短くなり，ワーしていると考えられる．

カにより大きな戸惑いを与える．このことを踏まえて，タス

図 10 に，100 回のシミュレーションを行った結果を「グルークまでの残りグループ数が減る場合と増える場合について重プ数の平均」と「P EN ALT Y の合計値」の 2 項目でプロットみをつける必要がある．本シミュレーションでは，減る場合のした散布図を示す．分割優先法ではグループ数を増加させる

P EN ALT Y を 2 倍にして計算を行う．したがって，(1) 式はことは実現できたが，P EN ALT Y の合計値が大きくなってし

次のようになる．

まった．一方，バランス優先法ではグループ数を増加させるこP EN ALT Y =とはできなかったが，P EN ALT Y の合計値をかなり抑えるこ
1
Jgx +1(増えるとき)2 × 1Jg +1x(減るとき)とができた．

(0 <= Jgx <
= |G|−1)(2)

5. 2 シミュレーション結果の考察
5. 2. 1 ワーカ参入時におけるグループの選択方法
グループ内のワーカの最大人数を max = 2d とし，それぞれの手法ごとに 100 回のシミュレーションを行った．シミュレー
ションによって得られたグループ数 (図 8) と P EN ALT Y の合計値 (図 9) の推移を手法ごとに示す．
図 8 に，各手法ごとのある１回のシミュレーションにおけるグループ数の推移を示す．ここから分割優先法が最もグループ数が多くなり，ワーカの１人あたりのタスク処理回数が少なくなると分かる．しかし，分割優先法では頻繁にグループ数が変化している．この結果から，ワーカの１人当たりタスク処理回数は少ないが，グループの分割や統合が頻繁に生じているため，
ワーカの順番の変更が多くなり，ワーカの戸惑うことが多いとバランス優先法と分割優先法を比較すると，バランス優先法のグループ数の平均は分割優先法より約 30 ％の減少となったが，P EN ALT Y の合計値の平均を約 90 ％削減した．また，バランス優先法と単純追加法を比較すると，バランス優先法はグ
ループ数の平均を約 19 ％の低下にとどめ，P EN ALT Y の合計値の平均を約 84 ％削減することができた．これらの結果から，バランス優先法は他の手法よりも相対的に優れた手法であると言える．また，分散を比較するとバランス優先法は分散が小さく他の手法よりも信頼度が高いと考えられる．

5. 2. 2 分割のためのパラメータを比較
図 11，図 12，図 13 にワーカ参入時におけるグループの選択の各手法において，グループ内のワーカ数の最大値 max を変更し，それぞれ 100 回のシミュレーションを行った結果を「グループ数の平均」と「P EN ALT Y の合計値」の 2 項目でプロットした散布図を示す．図 11 と図 13 より，単純追加法，

500

50

単純追加法
バランス優先法
分割優先法

40

グループ数の平均PEANLTYの合計値

400

2d
3d
4d

300

200

100

30

20

10

0

0
0

20

40

60

80

100

0

100

タスク数

図9

P EN ALT Y の合計値の推移

50

図 12

300

400

500

グループ内のワーカ数の最大値を変更（バランス）

50

単純追加法
バランス優先法
分割優先法

2d
3d
4d

40

グループ数の平均

40

グループ数の平均

200

PEANLTYの合計値

30

20

10

30

20

10

0

0
0

100

200

300

400

500

0

100

PEANLTYの合計値

図 10

200

300

400

500

PEANLTYの合計値

グループ数の平均と PENALTY の合計値の散布図

50

図 13

グループ内のワーカ数の最大値を変更（分割）の各手法において，分割や統合，移動を禁止するグループ数を

2d
3d
4d

変更し，100 回のシミュレーションを行った結果を「グループ40

グループ数の平均数の平均」と「最終 P EN ALT Y 」の 2 項目でプロットした散布図を示す．L はタスク作業直前の分割や統合，移動を禁止す30

るグループの個数 L を示す．
今回のシミュレーションでは，分割や統合，移動の禁止がワー

20

カへの戸惑いを軽減することに有効であるかは確認できなかった．おそらく，グループ数が多数あるような場合，タスク直前

10のたかだか L 個のグループに対して分割や統合，移動を行わな
0
0

100

200

300

400

500

PEANLTYの合計値

図 11

グループ内のワーカ数の最大値を変更（単純）

分割優先法では，max の値を大きくすると，「グループ数の平いという制御を行ったとしても，必ずしも制御を行う L 個のグ
ループにワーカの挿入や離脱の操作が生じるわけではないため，有効な手段にならなかったのではないかと考えられる．

6. まとめと今後の課題

均」と「P EN ALT Y 」の値がどちらも低くなっている．これ

本論文では，グループローテーション型クラウドソーシング

は，max の値を大きくすることで分割が起こりづらくなったたの制御手法の提案をおこなった．グループの増減やワーカの移めだと考えられる．一方で，図 12 より，バランス優先法では

動と，それに伴うワーカの戸惑いはトレードオフの関係にある「P EN ALT Y の合計値」，「グループ数の平均」ともにほとんが，単純追加法，バランス優先法，分割優先法の 3 手法の比較

ど変化がなかった．これは，バランス優先法がもともと分割がにより，バランス優先法がそれらをある程度両立することを示

起こりづらい手法であるため，max の大小があまり影響しな

した．

かったのではないかと考えられる．

今後の課題としては，(1) 全体のペナルティの削減だけでな

5. 2. 3 分割や統合，移動を禁止するグループ数を比較

く，個々人のペナルティに配慮した手法の検討，および (2) 現

図 14，図 15，図 16 にワーカ参入時におけるグループの選択

実により即したペナルティの計算方法を明らかにするための実

50

L=0
L=1
L=2
L=3

グループ数の平均

40

[2]
30

20

[3]
10

[4]

0
0

100

200

300

400

500

PEANLTYの合計値

図 14

分割や統合，移動を禁止 (単純)

50

L=0
L=1
L=2
L=3

グループ数の平均

40

30

20

10

0
0

100

200

300

400

500

PEANLTYの合計値

図 15

分割や統合，移動を禁止 (バランス)

50

L=0
L=1
L=2
L=3

グループ数の平均

40

30

20

10

0
0

100

200

300

400

500

PEANLTYの合計値

図 16

分割や統合，移動を禁止 (分割)験，などがあげられる．

謝辞

本論文の一部は JSPS 科研費 (25240012, 26870090)，並びに筑波技術大学平成 27 年度学長のリーダーシップによる教育研究等高度化推進事業による助成の成果であり，ここに記して謝意を表すものとする．

文

献[1] W.S. Lasecki, C.D. Miller, A. Sadilek, A. Abumoussa, D.

[5]

Borrello, R. Kushalnagar, J.P. Bigham. Real-time Captioning by Groups of Non-Experts. In Proceedings of the
ACM Symposium on User Interface Software and Technology (UIST 2012). Boston, MA. p23-34.
M. S. Bernstein, J. R. Brandt, R. C. Miller, and D. R.
Karger. Crowds in two seconds: Enabling realtime crowdpowered interfaces. In Proc. of the 24th annual ACM Symp.
on User Interface Software and Technology, UIST 11, p3342. 2011.
L. Chilton. Seaweed: A web application for designing economic games. Master s thesis, MIT, 2009.
L. von Ahn and L. Dabbish. Labeling images with a computer game. In Proc. of the Conf. on Human Factors in
Computing Systems, CHI 04, p319-326. 2004.
Bayer, R. and McCreight, E. M. : Organization and Maintenace of Large Ordered Indexes. Acta Informatica, 1(3),pp.173-189. 1972.