DEIM Forum 2014 E2-4

クラウドソーシングによるデータ列挙のための分割統治手法
青木

秀人†

森嶋

厚行††,†††† 筑波大学大学院 図書館情報メディア研究科 〒 305–8550 茨城県つくば市春日 1–2†† 筑波大学 図書館情報メディア系/知的コミュニティ基盤研究センター 〒 305–8550 茨城県つくば市春日 1–2††† JST さきがけ
E-mail: †{aoki,mori}@slis.tsukuba.ac.jp
あらまし 近年，Web 上の多くのサービスにおいて，クラウドソーシングによるデータ列挙が広く行われている．例
えば，レストランのレビューサイトにおけるレストラン名の列挙は，不特定多数の人々によって行われている．このように，クラウドソーシングによるデータ列挙は，機械的にデータを列挙することが困難である場合に有用である．
本論文では，マイクロタスク型のクラウドソーシングによるデータ列挙処理について焦点を当て，再現率が高くなる
ようにタスク分割を行いながらデータ列挙を行う手法を提案する．提案手法では，分割統治のプロセスに群衆が参加するという点に特徴がある．本論文は，提案手法の説明に加え，シミュレーションを用いた提案手法の詳細な評価について報告する．
キーワード

クラウドソーシング

1. は じ め に
近年，機械では検索困難な情報を人手で検索する人力検索(Human-powered Search) が広く使われている．本論文では特に，検索結果のデータ量が多く，かつ再現率を重視するような人力検索（例えば，日本の 1000m 以上の山を列挙すること）
を人力データ列挙 (Human-powered Data Enumeration) と呼ぶ．また，クラウドソーシングによって人力データ列挙を行う
ことをクラウドソーシングによるデータ列挙 (Crowdsourced

Data Enumeration) と呼ぶ．
クラウドソーシングによるデータ列挙は多くの Web アプリ
ケーションにとって重要な要素の１つとなっている．例えば，
レストランのレビューサイト [1] においてユーザの力を借りてレストラン名を列挙することや，Wikipedia のページなどにおいて，ある分野の項目を網羅的に列挙することが挙げられる．
本論文では，近年注目を集めている，マイクロタスク型のク
ラウドソーシングプラットフォームを用いたクラウドソーシン
グによるデータ列挙の処理について焦点を当てる．マイクロタ
スク型のクラウドソーシングプラットフォームとは，比較的短時間で処理可能なタスク (マイクロタスク) を格納するタスク
プールを持つソフトウェアプラットフォームである．リクエス
タと呼ばれるタスクの依頼者がマイクロタスクをタスクプー
ルに登録しておき，ワーカはこのタスクプールに格納されているタスクを行う．Amazon Mechanical Turk [2] や，国内ではYahoo!クラウドソーシング [3] などが代表的なものである．
マイクロタスク型のクラウドソーシングプラットフォームでデータ列挙を行う場合，単純には図 1 のようなタスクをワーカに処理してもらうことが考えられる．しかし，このような単純なデータ列挙タスクでは，日本で一番高い山を聞くような，一般的な Human-powered Search のように少数のデータを集める場合には有効であるが，再現率が重要なデータ列挙タスクに

図 1 データ列挙を行なうためのタスクの例

は適していない．なぜならば，列挙されるべきデータが多くな
るとワーカは既に入力されているデータの中から未入力のデー
タや間違いがあるデータを認識することが困難になり，結果として，データの入力が少なくなり，再現率が低くなってしまうからである．
我々は，大規模な問題を解決する重要なアプローチである分割統治を適用する事を提案している [4] [5]．具体的には，マイクロタスク型のクラウドソーシングプラットフォームに，列挙の範囲を限定したタスクを多数登録し，全体として広い範囲のデータ列挙を行うというものである．例えば，図 2 のように，ある市の病院の名前のデータ列挙を行いたい場合を考える．この時，市全体の病院のデータ列挙をしてもらうのではなく，区ごとに病院の名前のデータ列挙を行う複数のタスクをタスク
プールに登録し，全体として市全体のデータ列挙を行う．
しかし，分割統治手法によるデータ列挙には二つの問題がある．第一に，問題分割の方法は問題ごとに異なるので，あらかじめ分解された多数のタスクをリクエスタが用意することは現実的でないことである．第二に，分割統治した結果が単純な
データ列挙処理と同じ結果になることを保証しなければならな
いことである．
これらの問題の解として，我々は，論文 [4] [5] において，ワーカがデータ列挙の問題分割に参加する手法の提案を行い，マイらの手法と組み合わせてデータ列挙を行うことは今後の興味深
い課題の 1 つである．
クラウドソーシングにおけるタスク分割の研究では，Kulka-

rni ら [14] の研究がある．Kulkarni らは一般的な設定でクラウ
ドソーシングのタスクに分割統治法を適用をし実験・評価を行った．彼らは考察として，ワーカだけでは，適切なガイドな
図 2 小さなタスクを使ったデータ列挙

しに問題を分割する事が困難であることを報告している．我々

クロタスク型クラウドソーシングプラットフォーム上でのアルが提案する手法は彼らの考察を基に，ワーカがタスク分割する

ゴリズムを示した．また，提案アルゴリズムが，ある条件の下ためのガイドとして，タスク生成プランを与えている．

で単純なデータ列挙処理と同じ結果になることの証明を行った．

データ中心型のクラウドソーシングにおける一般的な問題と本論文では，シミュレーションによる提案アルゴリズムの詳して，データ品質の管理がある．データ品質を向上させる手法

細な評価結果を報告する．実験結果より，全体として，ワーカ

はこれまでにいくつか提案されている．例えば，多くのクラウのエラー率がよほど高くならない限り，提案手法が高い再現率

ドソーシングでは大数の法則を使った多数決 [6] を採用しデーを示すことがわかった．

タの品質向上を行っている．別のアプローチとしては，合理

本論文の構成は次の通りである．2. 節では関連研究について的なワーカが適切な値を入力する同調ゲーム [15] [16] がある．

説明する．3. 節ではマイクロタスク型のクラウドソーシングプ

論文 [17] では，GWAP（Game With A Purpose）に対して，

ラットフォームとタスクの表現方法について説明する．4. 節でゲーム理論による分析，および，インセンティブ構造を変えるはマイクロタスク型のクラウドソーシングプラットフォームにことで得られるデータが変化することについて議論している．

おけるデータ列挙処理について説明する．5. 節では提案手法に

我々の提案手法とこれらのデータ品質向上のための手法は，組ついて説明する．6. 節ではシミュレーション評価について説明

み合わせて利用することができる．

2. 関連研究3. マイクロタスク型のクラウドソーシングプ
ラットフォームとタスク表現

1. 節で説明した通り，Human-powered Data Enumeration

本節では，まず，マイクロタスク型のクラウドソーシングプ

は Human-powered Search の一種である．Human-powered

ラットフォームのモデルについて説明する．次に本論文で用い

Search 以外の人の力を用いた (Human-powered) データ処理

るタスクの表現方法について説明する．

する．7. 節はまとめと今後の課題である．

としては，選択 (filtering)，結合 (join)，ソート (sort) などのデータベース演算の処理が知られており，これらの演算についての効率化の議論が行われてきた. [6] [7] [8] [9]．

3. 1 マイクロタスク型のクラウドソーシングプラットフォーム
マイクロタスク型のクラウドソーシングプラットフォームで

特に，Human-powered Search と Human-powered Filtering

はワーカはタスクプールに存在するマイクロタスク（以下，タは関係が深く，どちらも条件を満たすデータを集める処理であスク）を処理する (図 3)．本論文では個々のタスクを ti , 個々のる．Human-powered Filtering と Human-powered Search のワーカを wj , タスクプール P と表す．タスク ti はタスクプー

違いは，条件を満たすデータを絞る際に元となる対象のデー

ル P に格納される．格納されているタスクは明示的にタスクタの違いである．Human-powered Filtering では計算機に格プール P から削除する処理があるときのみタスクプール P か納されたデータから条件を満たすデータを選択する．一方，

ら削除される．したがって，タスクプール P 中のタスク ti は

Human-powered Search は，データが格納されている場所を限

複数のワーカによって処理されることがある．

定せずに，データを収集する．

マイクロタスク型のクラウドソーシングプラットフォームのHuman-powered Search の処理は多くのシステムで使われてアルゴリズムを図 4 に示す．1 行目ではタスクプール P に初期いる [10] [11] [12]．1. 節で説明した通り，もし，Human-powered

タスク T0 を格納している．2 行目では，タスクプール P にタ

Search の結果で再現率を重視せず，いくつかのデータだけが欲

スク ti が格納されている間，次の 3-6 行目の処理を繰り返す：

しい場合は単純なタスクでも十分であると言える．しかし，再タスクを処理するワーカ wj を決定（3 行目）し，ワーカ wj に現率が重要である場合や条件を満たすデータが多く欲しい場合，対してタスク ti を割り当てる（4 行目）．ワーカ wj によって一般的な Human-powered Search ではなくデータ列挙毎に焦タスク処理が行われるのを待ち（5 行目），ti の処理が行われ点を当てた方法が必要である．

たら，タスク結果をデータベースに格納するなどの後処理を行

クラウドソーシングによるデータ列挙は既に先行研究においう (6 行目)．

て研究がなされている．Trushkowsky ら [13] は生物学や 統計

図 4 のアルゴリズムではタスクを割り当てられたワーカがタ学の分野のテクニックを用いて列挙クエリ (データ列挙) の完スクを行うまで，他のワーカがタスクを行うことがないように了を推定する手法を提案している．本研究との違いは，本研究単純化している．しかし，ワーカがタスク完了を待つ必要のなではデータ列挙するためのタスク生成に焦点を当てていること

い，イベント駆動型のアルゴリズムに拡張することも可能であや，タスクの完了を推定していないことである．Trushkowsky

る．本論文ではどちらのアルゴリズムにおいても適用可能な議1. postprocess(t, r){
2.
Let r be the result of
3.
t:TaskEntry(item_type, scope)4.
switch r.pressed_button {5.
case insert:
6.
DB.insert(item_type, r.dataitem);7.
break;
8.
case delete:
9.
DB.delete(item_type, r.dataitem);10.
break;
11.
case completed:
12.
P.remove(t);
13.
}
14.}
図 5 単純なデータ列挙処理の後処理
図3

マイクロタスク型のクラウドソーシングプラットフォームの概要

1. P.store(T_0);

データを列挙することである．
例えば，筑波大学の研究トピックの集合を

2. While !P.isEmpty() {Items(Research topic,"University of Tsukuba") と す る

3.

w_j=getWorker();と，この集合のデータを列挙することが，筑波大学の範囲

4.

t_i=P.assignTask(w_j);

における研究トピックのデータ列挙である.

5.

wait until we get r=t_i.performedBy(w_j);

4. 2 単純データ列挙の処理の流れ

6.

postprocess(t_i, r);

本節では単純なデータ列挙 (simple crowdsouced data enu-

7. }
図4

2

meration, 以下，S-DE) について説明する．この説明では，筑マイクロタスク型のクラウドソーシングプラットフォームのアル

波大学の研究トピック (Items(Research topic, "University

ゴリズム

of Tsukuba")) を例に用いる．

論を行う．

（ 1 ） 初 期 タ ス ク T0 を {EntryTask(Research topic,

3. 2 タスク表現"University of Tsukuba")} としてタスクプール P に格納

本手法において，ワーカに割り当て・処理されるタスク ti は，する（図 4 の 1 行目）．

タスククラスのインスタンスとしてモデル化する．タスククラス（ 2 ） タスクプール P に格納されたとはパラメータを与えることでインスタンスを作成するための{EntryTask(Research topic, "University of Tsukuba")}

テンプレートである．例えば，EntryTask(item type, scope) ををワーカに割り当てる（図 4 の 3,4 行目）．

データ列挙を意味するタスククラスとすると，item type, scope（ 3 ） ワーカが処理したタスクの結果の後処理を行う．ワーの 2 つがインスタンスを作成するためのパラメータである．

カが行った処理によって次の 3 つの後処理のうち 1 つを行う

ここで item type は列挙するデータのタイプを意味し，scope（図 4 の 6 行目，図 5）．

はデータを列挙する範囲を意味している．この時，ニューヨーク市の病院名を列挙するタスク（インスタンス）は Entry-

Task(Hospital name, "NYC") と表現される．(図 1) EntryTask
ではワーカに次の 3 つの処理のうち 1 つを行ってもらう．

•

データの追加: 入力済みの病院名のリストに存在してない病院名を入力し，“Insert” ボタンを押す．

•

データの削除: 入力済みの病院名のリストの中の間違ったデータや重複データを選択し，“Delete” ボタンを押す．

•

タスクの完了: 入力済みの病院名のリストが完成していると判断した場合．“Completed” ボタンを押す．

•

ワーカが新しくデータ入力した場合は結果をデータベースに格納する（図 5 の 5-7 行目）．

•

ワーカが既に入力されているデータを削除した場合はデータベースからデータを削除する（図 5 の 8-10 行目）．

•

ワーカがタスクが完了していると判断した場合，タスク

プール P から対応するタスクを削除する（図 5 の 11-12 行目）．

4. 3 単純な手法における問題
単純なデータ列挙では適切にタスクを完了させることは難し
く，再現率も低くなる可能性が高い．なぜならば，入力済みのリストのデータが増加し，ワーカは次の 3 つのことが難しくな

4. マイクロタスク型のクラウドソーシングプ
ラットフォームにおけるデータ列挙

るからである．(1) 現在の入力済みのリストから不足している

本節では，本論文で扱うデータ列挙について定義し，単純なから不適切なデータを削除すること．(3) 現在の入力済みのリデータ列挙について説明する．初めにデータ列挙の定義について説明する．次に単純なデータ列挙の処理の流れを説明し，最後に単純なデータ列挙の問題について説明する．

データを見つけて追加すること．(2) 現在の入力済みのリスト
ストのデータが全て揃っているか判断することが．

5. 提 案 手 法
本節では，提案する分割統治によるデータ列挙 (divide-and-4. 1 データ列挙

conquer crowdsourced data enumaeration, 以下 DC-DE) に

データ列挙を次のように定義する．

ついて説明する．まず，初めに提案手法の 2 つの特徴について

定義 1. scope が表す範囲の item type のデータが全て揃ってい説明する．次に提案手法で用いるタスク生成プランについて説る集合を Items(item type, scope) するとき，scope 範囲におけ明し，最後にタスクを生成するアルゴリズムについて説明する．

る item type のデータ列挙は Items(item type, scope) の全ての

5. 1 提案手法の概要
提案手法の特徴は分割統治をしてデータ列挙を行うことと，
ワーカがタスク生成に参加することである．まず，タスク分割について説明し，次にワーカによるタスク生成を説明する．

(1) タスク分割.
定義 2. s をデータ列挙をする範囲，item type を列挙するデー

図6

提案手法の概要

タのタイプ，s1 , . . . sn を item type の別のデータ列挙範囲とする．このとき，{s1 , . . . sn } が s の item type を分割するとは次列挙を行い，単純な手法よりも再現率が高くなることやマイクの式を満たすことである．

ロタスク型のクラウドソーシングに適していること [4]．

5. 2 タスク生成プラン

Items(item type, s) = Items(item type, s1 ) ∪. . . ∪ Items(item type, sn ).

2

タスク生成プランとはデータ列挙のための小さなタスクを生成する設計図である．具体的には，データ列挙範囲の階層を記もし，{s1 , . . . sn } が s の item type を分割していた場合，タス述している．例えば，筑波大学の研究トピックでは，筑波大学

ク分割を用いて，データ列挙するには，{ EntryTask(item type,の全ての研究科によって階層を構成することができる．図 7 にs1 ), . . ., EntryTask(item type, sn )} のタスクを用意し，全てタスク生成プランのイメージを示す．この図のタスク生成プラのタスクを行えば良い．例えば，筑波大学が A，B . . . の研究科

ンはある大学の研究トピックをデータ列挙するための階層が書から構成されていると仮定し，筑波大学の研究トピックのデー

かれている．ここで末端の “Topic” ノードだけ形が異なるの

タ列挙をする場合 { EntryTask(ResearchTopic, "Instituteは，これが最終的に収集したいデータであることを示している

A"), EntryTask(ResearchTopic, "Institute B") , . . .} を用からである．

意して，全てのタスクを行うことで，筑波大学の研究トピック

図 7 の各ノード間のエッジは異なるデータのタイプのデータのデータ列挙ができる．

列挙タスクに対応する．つまり，ここでは 4 つのエッジがあり，(2) ワーカによるタスク生成の参加. 一般に，タスク分割を行

次の 4 つの種類の EntryT ask(詳細は 5. 2. 1 節) を生成する．

うことで再現率が高くなることが予想される．しかし，どのよ(Task1) それぞれの大学の研究科のデータ列挙を行うタスク

うに分割したタスクを用意するかは明らかではない．なぜなら(Task2) それぞれの研究科の専攻のデータ列挙を行うタスク

ば，タスクを分割・生成するためにはデータ列挙をする範囲の(Task3) それぞれの研究科の研究トピックのデータ列挙を行う

知識が必要になるが，その知識は問題によって異なり，予め分タスク割されたタスクを用意しておくことは難しいからである．

(Task4) それぞれの専攻の研究トピックのデータ列挙を行うタ

そこで，提案手法ではワーカがタスクの生成に参加することスクを提案する．これはタスクを処理することができるワーカは，次に，各ノードの横に書かれている !x は完了同意回数であり，そのタスクに関する知識を持っているという想定の下，そのそのデータ列挙が完了したことを x 名のワーカで確認する必要

ワーカが持つ知識を利用して，データ列挙の問題を小さなタスがあることを表している．例えば，図 7 においては，研究科のクに分割を行っていくものである．そのため，リクエスタは予研究トピックが既に全て列挙されたかの確認は 2 名のワーカでめ，タスクを分割して用意しておく必要がない．

同意を取る必要があることが書かれている．

しかし，どのようにワーカにタスク生成に参加してもらうか

また，エッジの横に書かれている ?y は生成同意回数 であり，はマイクロタスク型クラウドソーシングでは明らかではない．

タスクを生成する前に DivisionT ask(詳細は 5. 2. 1 節) を用い本手法では分割統治によるワーカのタスク生成を実現するためて，そのタスクを行う必要があることを y 名のワーカで同意をに予めシステムにタスク生成プランを与える（図 7. 詳細につ得なければならないことを表している．例えば，図 7(Task5)

いては 5. 2 節で説明する）．タスク生成プランとは，データ列においては，研究科を専攻に分割するかタスク判断するタスク

挙する範囲に合わせた階層構造を持ち，ワーカからの入力を基は 2 名のワーカで同意を取る必要があることを表している．

にタスクを生成するための設計図である．

DivisionT ask を導入する目的は，データ収集分割のための

図 6 は，提案手法の概要である．提案手法は，単純なマイク

階層構造が必ずしも均一とは限らない場合があるからである．

ロタスク型クラウドソーシングプラットフォーム (図 3) と次の

例えば，物理研究科には専攻があるが，社会学研究科には専攻２つの点が異なる．
（1）リクエスタがシステムにタスク生成プ

がない場合，全ての場合に専攻に分割すると，社会学研究科にランを入力すること．
（2）ワーカが処理したタスク結果とタス関して不適切なタスク生成を行なってしまう．

ク生成プランを基に，新しいタスクを生成し，タスクプールに記 法.

追加すること（詳細については 5. 3 節で説明する）．

[n1 , n2 , . . . , nm ] と記述する．これは，基本的には図 7 と同

実 際 に は ，タ ス ク 生 成 プ ラ ン は 図 8 の よ う に

本手法は 1. 節で説明した通り，既に次の 2 つの事を確認しじ情報を保持しており，各 ni は各ノードを表す．T opic だけている. (1) 理論的評価においてワーカが正しくタスク処理を

は，先頭に*が着いているが，これは末端ノードであることをする場合に提案手法と単純手法のデータ列挙の結果が等しくな表す．各ノードの直後の [] の中には，完了同意回数，生成同意ること [5]．(2) 被験者実験による評価において，実際にデータ

回数，末端ノードへのエッジが存在するか (*) を記入する．

Completed が正しく処理されるかどうかは特に重要である．
(2) 範 囲 分 割 タ ス ク (DivisionTask) 範 囲 分 割 タ ス ク
DivideT ask(scope, ni ) は，scope の収集範囲をさらに ni 単位のタスクに分割する前に，そのタスクが必要かどうかに関する同意を求めるものである．図 9 は，数学研究科が専攻に分割できるか問い合わせるタスク DivideT ask("数学研究科", Department)の画面である．ワーカは「分割できる」か「分割できない」の
図 7 タスク生成プランのイメージ[Univ{University of Tsukuba}<uname>,
Grad-Sch[!2, *]<gname>,
Department[!2, ?2]<dname>,*Topic[!2]<topic>]]
図 8 タスク生成プランの表記

2 つから 1 つを選択する．
5. 3 タスク生成アルゴリズム
本節では，タスク生成プラン [n1 {v1 }, n2 , . . . , nm ] が与えられた時のタスク生成アルゴリズムについて説明する．本アルゴ
リズムは，図 4 に沿った流れで行われる．具体的には次の通りである．
（ 1 ） 1 行目では，初期タスク T0 = {EntryT ask(n2 , v1 )}を 格 納 す る ．こ の と き v1 は n1 の 初 期 の 値 で あり，デ ー タ 列 挙 す る 範 囲 を 示 し て い る ．ま た n2 は

n1 の 子 ノ ー ド に あ た る ．例 え ば ，図 8 の 場 合 は ，
図 9 範囲分割タスク (DivisionT ask) の例

EntryT ask(Grad-Sch, "Tsukuba University") を T0 に登録する．

さらに，実際のタスク生成プランは，図 7 には存在しない次（ 2 ） 4 行 目 で は ，ワ ー カ へ の タ ス ク の 割 り 当 ての 2 つの追加情報を持つ．

(P.AssignTask(w)) を行う．このとき，割り当てるタスクはタ（ 1 ） 最も上位のタスク (Univ-Grad-Sch) の Univ の初期

スクプール P にもっとも早く追加されたタスクとする．つま値 (この例では “University of Tsukuba”) が {. . .} に書かれてり，この割り当て方法はデータ列挙を階層化したときに幅優先いる．

で行って実行していることになる．

（ 2 ） 各ノードが表すデータを格納するリレーションの属性名（ 3 ） 6 行 目 で は ，ワ ー カ が 処 理 し た タ ス ク の 後 処 理が，’< . . . >’ に書かれている (例えば，リレーション Grad-Sch（postprocess(t, r)）を行う．ワーカが行った処理により次は属性として gname という研究科名を格納する属性を持っての 4 つの異なった後処理を行う (図 10)．

いる)．

[Case 1: EntryTask においてワーカが “Insert” を行った

5. 2. 1 生成するタスク場合] 図 10 の 6 行目では，追加されたデータをデータベース

提案手法では，そのプロセスにおいて 2 種類のタスクを生成に格納する. 7-11 行目では，追加されたデータが末端ノードのする．1 つ目のタスクはデータの入力を求めるタスクである．2

データ nm でなければ，子ノードと追加されたデータから新しつ目のタスクは新しくタスクを生成を行っていいか確認するタ

くタスクを生成する．このとき，新しく生成されるタスクは次スクである．本節ではそれらを説明する．

の 2 つの場合には分かれる．

(1) データ列挙タスク (EntryTask) このタスク (図 1) では次(1) 対応するエッジに生成同意回数 (?y) が記述されていないの 3 つのうち 1 つをワーカが行う．

場合は EntryT ask をタスクプール P に追加する (7-8 行目)．

•

(Insert) 対象となるデータを入力(2) 対応するエッジに生成同意回数 (?y) が記述されている場合，•(Delete) 既に入力されたデータを削除

DivisionTask をタスクプール P に追加する（9-10 行目）．

•

(Completed) 対象のデータが全て揃っているか判断[Case 2: EntryTask においてワーカが “Delete” を行った

例えば，筑波大学の研究トピックのデータ収集を行うタスク

場合] まず，ワーカによって「削除する」と選択されたデータ

EntryT ask(T opic, "University of Tsukuba") の場合 , 具体をデータベースから削除する (13 行目)．次に，削除されたデー

的にワーカが行うことができる行動は次の通りである．

タを基に生成されたタスクをタスクプール P から削除する (14•(Insert) 筑波大学の研究トピックである「クラウドソー

シング」などを入力する．

•

行目)．

[Case 3: EntryTask においてワーカが “Completed” を(Completed) 入力されている研究トピックを見て，これ行った場合] ワーカが「完了している」と判断したタスクが完らのデータで筑波大学の研究トピックが全て揃っているか判断

了同意回数（!x）を満たしている場合，タスクプール P からタする．

•

スクを削除する (16-17 行目)．

(Delete) 入力されている研究トピックを見て，間違っている研究トピックや重複している研究トピックを削除する．
提案手法においては，上位のタスク (研究科の収集等) で漏れがあると最終的なデータ収集に大きな影響を与えるため，

[Case

4:

DivisionTaskを 行った 場 合] ワ ー カ がDivisionT ask(r.data item, ni ) で「分割できる」と生成同意
回数 (?y) を満たした場合，EntryT ask(ni , r.dataitem) を生成
し，タスクプール P に追加する（21-22 行目）．

1. postprocess(t, r){

表 1 シミュレーションにおけるワーカモデルの行動の種類

2. Let [n_1{scope}, ..., item_type] be the task generation plan.
3.

If t is EntryTask(n_i, scope) {4.

switch(r.pressed_button) {5.

case Insert:

タスクの種類

EntryT ask（A）正しい処理

DivisionT ask// Case 1

6.

DB.insert(n_i, r.dataitem);7.

if ((n_{i+1}.?y==0) && (n_i != n_m)){

8.

処理の正誤

（B）間違った処理

EntryT ask
DivisionT ask

処理内容
不足しているデータを追加
入力されているリストから間違ったデータを削除
タスクの完了判断
正しい分割判断
不適切なデータの追加
入力されているリストから正しいデータを削除
タスクの完了判断
間違った分割判断

P.insert(EntryTask(n_{i+1},r.dataitem));

9.

}else if (n_i != n_m){

10.

P.insert(DivisionTask(n_{i+1}, r.dataitem));

11.

}

12.

case Delete:

13.

// Case 2

DB.delete(n_i, r.dataitem);

14.

P.delete(EntryTask(n_{i+1}, r.dataitem));

15.

case completed:16.

// Case 3

if(completion is agreed) {17.

P.delete(t);

18.

}

19.

}

20.

} else if t is DivisionTask(n_i, r.dataitem) {21.

if (scope division is agreed) {22.

P.insert(EntryTask(n_i, r.dataitem));23.

図 11 error rate が変動する場合の関数// Case 4}

ため，不足しているデータの追加か間違ったデータの削除がそ
れぞれ 0.5 の確率で行う．

}(2-B) (1) で (B) に決定した場合，表 6. 1. 1 の下部の中からタ25. }スクの種類に応じて具体的な処理を行う．このとき具体的な処

24.

図 10

提案手法の後処理

理内容は（2-A）と同様に処理可能な処理の中から均等な確率で決定する．

6. シミュレーション評価

6. 1. 2 error rate の与え方

論文 [4] では，提案手法をクラウドソーシングプラットフォー

error rate は，次の 2 種類の方法で与えた．

ムで実装して実際に適用した結果を報告したが，本論文では，(1．固定) シミュレーション中は常に一定させる.

パラメータを様々に変更したした場合の影響を調べるため，シ(2．変動) 入力済みのデータ数に応じて変化させる．error rate

ミュレーションによる評価の結果を説明する．本シミュレーショ

が変動する場合は入力済みのデータ数 item num を引数とする

ンでは，ワーカがタスクを実際に行う事はせず，確率的に振る

次の 3 つの関数 (図 11) を用いた．

舞うワーカのモデルを用いて結果を計算する．
本シミュレーションでは，次の評価を行う．
（1） ワーカがタスクを間違えて処理する確率をいろいろと変化させた場合，提案手法は単純な手法と比べて再現率は高くなるのか．また，適合率はどうなるか．
（2） 分割が多いタスク生成プランと分割が少ないタスク生成プランのどちらが高い再現率になるのか．また，適合率はどうなるか．

F unc1：線 形 関 数 error rate = min(4.21875 ∗ 10−3 ∗item num, 0.3)
F unc2：指 数 関 数 error rate = min(6.59180 ∗ 10−5 ∗item num2 , 0.3)
F unc3：対 数 関 数 error rate = min(1.48931 ∗ 10−1 ∗log(item num + 1), 0.3)
上記 3 つの関数においては，被験者実験の結果 [4] を元に

6. 1 シミュレーション方法

item num = 64 の時に error rate ≑ 0.27 になるように定数

6. 1. 1 シミュレーションの概要項を決めた．また，error rate の上限は 0.3 と設定した．なぜ本シミュレーションではワーカが本来行うタスクについて，

ならば，S-DE においては入力すべきデータ数が多いため，入ワーカの行動が確率的に決定するモデルを用いてシミュレー

力済みのデータ数も多くなり，error rate が非常に高くなっションを行う．最初に，シミュレーションにおいてはワーカがてしまい現実的な値でなくなってしまうからである．つまり，間違った処理をする確率 error rate を与えておく．シミュレー

error rate が非常に高く，絶対に間違った処理を行う状態にな

ションの手順は次の通りである．

る．このような状態は実際にワーカに行ってもらう場合では発(1) error rate に基づき次のいずれかに決める．(A) ワーカが生しないため，error rate に上限を設けた．

正しい処理を行う．この場合は次の (2-A) を行う．(B) 間違っ

6. 2 データセット

た処理を行う．この場合は次の (2-B) を行う．

データ列挙の対象として次の 3 種類のデータセットを利用し(2-A) (1) で (A) に決定した場合，表 6. 1. 1 の上部の中からタた．

スクの種類に応じて具体的な処理を行う．このとき具体的な処(データセット A): 新潟県の公営 (国営・県営・市営・町営・外

理内容は処理可能な処理の中から均等な確率で決定する．例え

部委託を含む) のプール名．新潟県の公営 (国営・県営・市営・

ば，EntryT ask において入力済みのリストに不足データや間

町営・外部委託を含む) のプール名のデータである．正解集合の違ったデータがある場合は，タスク完了判断はできない．そのデータ数は 101 個である．このデータセットは本提案手法を用いて被験者実験の際に使用されたデータ [5] と同様であり，タ
スク生成プランについても同様のものを使用する．

(データセット B): 国連の加盟国の国名．国連に加盟している国名のデータである．正解集合のデータ数は 193 個（ [18] の 2011年加盟まで）である．国連の加盟国のデータは Trushkowsky
ら [13] の実験でもデータ列挙の対象としている．タスク生成プ
ランについては，外務省のサイト [19] に記載されている地域を用いて，3 階層とし，各階層の完了合意回数は 2 回とするタス
ク生成プランを作成し，使用する．

図 12(データセット C): 256 個の要素からなる合成データ．機械的

error rate が固定の場合のデータセット A のシミュレーショ
ン結果に作成した合成データである．このデータセットは末端ノード
がデータ数と同じ 256 の完全 2，4，16 分木で構成できる構造を持つ．タスク生成プランについては，その構造（2，4，16 分木）を用いて，9, 5, 3 階層とし，各階層の完了合意回数は 2 回とするタスク生成プランを作成し，使用する．

6. 3 比 較 方 法
単純手法と提案手法の再現率と適合率を比較する際に，条件を合わせるために，単純手法では，提案手法のデータ生成プランの完了合意回数と同じ回数の完了合意が行われるた時にタスクが完了するように設定をした．つまり，本シミュレーション

図 13

error rate が固定の場合のデータセット B のシミュレーショ
ン結果

においては全てのタスク生成プランにおいて完了合意回数は 2回なので，単純手法でタスクが完了する際には 2 回の完了合意を必要とする．また，それぞれのシミュレーションは 1000 回
実行し，それぞれの結果を平均したもので比較をする．ただし，シミュレーションの出力結果が 0 になる場合の適合率について
は 1 として扱う．なぜならば，出力がなく，間違ったデータも出力していないからである．

6. 4 シミュレーション実験の結果
6. 4. 1 データセット A, B のデータ列挙終了時の再現率と適合率
本節では，ワーカがタスクを間違えて処理する確率をいろい

図 14

error rate に F unc を用いた場合のデータセット A，Ｂのシ
ミュレーション結果

ろと変化させた場合の提案手法と単純手法のシミュレーション
結果（再現率と適合率）について説明する．

はワーカがタスクを間違える確率 (error rate) が入力されてerror rate が固定の場合．図 12, 13 は error rate が固定の場いるデータ数に応じてどのように振る舞うか予測は困難であ合のデータセット A, B の再現率と適合率を示したグラフである．しかし，シミュレーションを行った 3 つの関数においてはる．再現率の共通の特徴として error rate が高い時と低い時でDC-DE のほうが S-DE より再現率が高く，適合率においてはは S-DE と DC-DE がともに 1 または 0 に収束している．これどちらも 0.9 以上の高い値であることから，S-DE より DC-DE

は，タスクの完了の合意に多数決を用いているからである．なのほうが一定の有用性があることが言える．

ぜならば，error rate が 0 に近いときは，間違いが非常に起き

6. 4. 2 データセット C のデータ列挙終了時の再現率にくいため再現率は 1 となり，逆に error rate が 1 に近いとき

本節では，提案手法における分割数の違いによるデータ列挙

は正しい処理が非常に起きにくいため，再現率は 0 となるからの再現率をシミュレーションした結果について説明する．デーである．そのため，error rate が 0.2 − 0.4 程度の中間に注目

タセット C において error rate が一定の場合に階層が 9，5，

すると，DC-DE は S-DE よりも高い再現率であることが確認

3（2,4,16 分木）のタスク生成プランを用いて，シミュレーショ

できる．一方，適合率については，S-DE のほうが DC-DE よンを行った．その結果を図 15 に示す．error rate = 0.1 までりも高い値になった．なぜならば，DC-DE は出力されるデー

は全ての木においての DC-DE の再現率に大きな違いは見られタも多く，間違いも多く含まれるため適合率は低くなるからでないが 0.2 のあたりから他のプランと比較して 4 分木の再現率ある．逆に，S-DE では入力されるデータ数が少なく，全体的が高くなっていることがわかる．

にも間違いの数は少ないため適合率は高くなる．

4 分木の再現率が高い原因を詳しく調べるために，データセッ

error rate が変動の場合．error rate を 6. 1. 2 節の関数を用

トを木構造にした場合の各高さ（階層）における最終結果の最

いて変化させた場合の再現率・適合率を図 14 に示す．実際に大再現率を調べた．ここで，各高さにおける最終結果の最大再シミュレーションの結果，（1）ワーカがタスクを間違えて処理する確率がよほど高くならない限り，提案手法のほうが再現率が高くなることが確認できた．
（2）何階層に分割すれば，高い再現率になるかは，各タスクで列挙すべきデータ数と階層数が関係するため，一概に分割を多くした方が良いことや少なくした方が良いことは言えないことがわかった．今後の課題としては，タスク生成プランの作成支援やタスク生成プランの妥当性の判断手法の検討，他の関連問題 (インセンティブなど) と組
み合わせた検証などがあげられる．

謝
図 15 データセット C のシミュレーション結果

辞ゼミなどにおいてコメントいただきました，筑波大学 杉本重雄教授，阪口哲男准教授，永森光晴講師に感謝いたします．本研
究の一部は JST さきがけおよび科研費基盤研究 (#25240012)の支援による．
文
[1]
[2]
[3]
[4]

[5]

[6]
図 16 error rate = 0.2 の時の各高さにおける最終結果の最大再現率

現率とは，ある高さのデータ列挙が終了したときに，この高さ[7]の結果から末端ノードまで間違いがない場合に得られる最大の再現率のことである．各高における最終結果の最大再現率の変[8]化を図 16 に示す．各階層毎に 2，4，16 分木はそれぞれ各階層毎に平均で 0.017 ，0.024，0.054 ずつ再現率が下がっているこ[9]とがわかる．この結果から，集めるデータ数（分木数）が大きいほど，各階層毎に下がる再現率は大きくなる．また，最終的な再現率は 1 − (各階層で下がる再現率の値 × 階層の高さ) で求めることができることがわかる．このように，何階層に分割すれば高い再現率になるかは，各タスクで列挙すべきデータ数

[10]
[11]
[12]
[13]

と階層数が関係するため，一概に分割を「多くした方が良い」
や「少なくした方が良い」等は言えない．

[14]

今回のシミュレーションにおいては，4 分木で 5 階層のタス
ク生成プランを用いたシミュレーションが各階層毎で下がる再[15]

現率の値と階層の高さの掛け合わせた値が一番小さく，一番再現率が高いという結果となった．

[16]

7. お わ り に
本稿では，マイクロタスク型クラウドウドソーシングクラ
ウドソーシングプラットフォームにおいて分割統治法を用いた

[17]
[18]

データ列挙の手法について説明した．また，本提案手法において次の 2 つを確認するためのシミュレーションを行った．
（1）
ワーカがタスクを間違えて処理する確率をいろいろと変化させた場合，提案手法は単純な手法と比べて再現率は高くなるのか．
（2）分割が多いタスク生成プランと分割が少ないタスク生成プ
ランのどちらが高い再現率になるのか．

[19]

献

食べログ. http://tabelog.com/
Amazon Mechanical Turk. https://www.mturk.com/mturk/
Yahoo!クラウドソーシング. http://crowdsourcing.yahoo.co.jp/
青木秀人，森嶋厚行，三津石智巳 ”クラウドソーシングによるデータ収集のためのタスク生成手法の提案” deim2013, pp. 1-7,
2013-3
Aoki Hideto, Atsuyuki Morishima. A Divide-and-Conquer
Approach for Crowdsourced Data Enumerataion. SocInfo
2013, pp. 60-74, November 2013
Adam Marcus, Eugene Wu, David R. Karger, Samuel Madden, Robert C. Miller: Human-powered Sorts and Joins.
PVLDB 5(1), 13-24 (2011)
Adam Marcus, Eugene Wu, Samuel Madden, Robert C.
Miller: Crowdsourced Databases: Query Processing with
People. CIDR 2011, 211-214 (2011)
Michael J. Franklin, Donald Kossmann, Tim Kraska, Sukriti
Ramesh, Reynold Xin: CrowdDB: answering queries withcrowdsourcing. SIGMOD 2011, 61-72 (2011)
Aditya G. Parameswaran, Neoklis Polyzotis: Answering
Queries using Humans, Algorithms and Databases. CIDR
2011, 160-166 (2011)Yahoo! ANSWERS. http://answers.yahoo.com/
OK Wave. http://okwave.jp/
人力検索はてな．http://q.hatena.ne.jp/
Beth Trushkowsky, Tim Kraska, Michael J. Franklin, Purnamrita Sarkar: Crowdsourced enumeration queries. ICDE
2013, 673-684 (2013)
Anand Pramod Kulkarni, Matthew Can, Bjorn Hartmann:
Collaboratively crowdsourcing workflows with turkomatic.
CSCW 2012, 1003-1012 (2012)
Atsuyuki Morishima, Norihide Shinagawa, Shoji Mochizuki.
“The Power of Integrated Abstraction for Data-Centric Human/Machine Computations”. VLDS 2011: 7-10
gwap.com. “ESP Game”
http://www.gwap.com/gwap/gamesPreview/espgame/
Shaili Jain, David C. Parkes: A Game-Theoretic Analysis
of Games with a Purpose. WINE 2008: 342-350
国 際 連 合 広 報 セ ン タ ー 国 連 加 盟 国 加 盟 年 順 序.
http://www.unic.or.jp/info/un/
un organization/member nations/chronologicalorder/
外務省 各国・地域情勢. http://www.mofa.go.jp/mofaj/area/index.html