DEIM Forum 2013 C4-5

クラウドソーシングにおける回答収束点の検討
大久保佑紀†

北須賀輝明†

有次 正義†† 熊本大学大学院自然科学研究科情報電気電子工学専攻 〒 860–8555 熊本県熊本市中央区黒髪 2–39–1
E-mail: †ohkuboy@dbms.cs.kumamoto-u.ac.jp, ††{kitasuka,aritsugi}@cs.kumamoto-u.ac.jp
あらまし

近年，データの収集や処理にクラウドを用いるクラウドソーシングに関する研究が広く行われている．ク

ラウドソーシングには，正しい結果をどのように少ないコストや短いレイテンシでえるかといった課題がある．現在のクラウドソーシングでは，クラウドの回答者が行うマイクロタスクは，並列に作業を実行することができるように設計されており，全てのクラウドの回答を収集後，結果が出力される．本論文では，ある数以上の回答収集後，その後のクラウドの回答では結果が変化しない回答収束点について議論する．また，1 度収集したタスクから求めた回答者正答率を用いて，回答収束を早くする手法について検討する．
キーワードクラウドソーシング，回答削減

1. は じ め に近年，データベース内の画像並べ替えや比較などの計算機にるタスクが多くあると考えられる．多数決を用いる場合，過半数が同じ回答の HIT は，その時点で正答を定めることができる．

は困難であるタスクをするために，多数の人々（クラウド）にこれらのことから，各 HIT において割当数すべての回答をタスクを実行してもらうクラウドソーシングの研究が広く行わ収集した場合と同様の結果を割当数よりも少ない回答で求めるれている [1]．クラウド回答者に仕事を依頼する要求者は，情手法を検討することは有用であると考えられる．本論文では，報の入力を要求する HIT (Human Intelligence Task) をクラある数以上の回答収集後，その後の回答では結果が変化しないウドに送信する．1 つの HIT は人々にとっては簡単で，即座点を各 HIT の回答収束点と呼ぶ．例えば，多数決で回答を定に答えることができるように設計される．回答者は HIT を実める場合，割当の過半数が同回答となった時点が回答収束点で行し，回答を入力する．そして要求者は小額の報酬を回答者ある．に支払う．クラウドソーシングプラットフォームの 1 つである

回答収束点は，各タスクの回答の多様性によって大きく変わAmazon Mechanical Turk (AMT) [2] には，2006 年に 20 万人ると考えられる．本論文では，回答の多様性の中で，あるタス以上の人々が回答者と登録されていると示されている [3]．

クにおいて回答者が正答を選択する確率を正答率と呼ぶ．例え

従来のデータベースシステムでは，回答者によって与えられば，誰が見ても明らかである 1 組の画像マッチングでは，正答たクエリを構文解析し，クエリ処理コストを最小にするように率は 10 割になると考えられ，人によって捉え方が異なるよう最適化される．クエリ処理コストとは，I/O 及び CPU コスト

な曖昧な 1 組の画像マッチングでは，曖昧であるほど正答率がである [4]．それに対して，クラウドソーシングを用いるデータ5 割に近づくと考えられる．回答収束点を考えると，正答率がベースシステムでは，人を用いるため従来のデータベースシス

低いタスクは，同じ回答の割合が減り，各 HIT の回答収束はテムの処理コストに加えて，クラウドに支払う金銭的コストや遅くなると考えられる．しかし，正答率が高いタスクは，同じクラウドから回答が返ってくる時間を考慮しなければならない．

回答の割合が増え，各 HIT の回答収束は早くなると考えられ

通常クラウドから回答が返ってくる時間は，I/O 及び CPU コる．よって，本論文では，回答者の正答率を変化させた場合のストに比べると非常に大きい．例えば，文献 [5] で示されている回答収束点の変化について議論する．

ように，20 × 20 の画像比較に 30 分以上の時間を必要とする．

また，回答収束を早くするために，正答率が低い回答者の回

また，文献 [6] で述べられているように，回答者が人である答を除く手法，及び，高い正答率で正答している回答者の回答ために回答を間違えることや主観的な回答をする場合があるこを使用し，過半数よりも少ない回答で回答収束点を推定するとや，悪意のある回答をする回答者が存在するため，回答結果手法について検討する．各回答者の正答率は，収集した複数のの不確実性についても考慮する必要がある．現在，1 つの HITHIT 回答から求める．

を複数人にやってもらい，多数票を結果とすることで，答えの本論文の構成は次の通りである．2 章では関連研究について信頼性を高める手法などが用いられている．1 つの HIT に何人述べる．3 章では，各 HIT の回答収束点を求めるための手法に回答をしてもらうかは，割当数として HIT 送信時に要求者がついて述べる．4 章では，予備的な実験について説明し，5 章指定する．ただし，割当数を大きくすると，金銭的コスト及びでまとめと今後の課題を述べる．

実行時間が増加する．
現在のクラウドソーシングでは，多数決を用いて正答を求め2. 関 連 研 究
近年，計算機に困難なデータベース演算にクラウドソーシングを用いる手法について，多くの論文によって議論されている [5] [7] [8] [9]．

pi =回答者 i の正答数
回答者 i の正答数 + 回答者 i の誤答数

(1)

3. 3 回答収束点を早める手法
回答収束点を早める手法について説明する．ナイーブな回答収束点は，割当の過半数が同回答となった時点である．本節でFranklin ら [7] [8] は，クラウドを用いて主観的な比較をする

は，ナイーブな回答収束点よりもより少ない回答数で各 HIT のために，CrowdEqual と呼ばれる拡張 SQL を定義している．

同回答を過半数とする手法及び，各 HIT の回答収束点を過半

CrowdEqual では，割当で定めた複数の回答の多数票を正しい数とするより少ない回答数で，回答収束点を推定する手法につ結果としている．

いて述べる．どちらの手法も回答者の正答率を使用するため，Marcus らは，クラウドソーシングを用いるデータベースシステム，Qurk [9] を提案している．文献 [5] では Qurk で，デー結果が定まった複数の HIT から，式 (1) を用いて各回答者の正答率を求める必要がある．

タベース演算であるソートとジョインを実行する場合の効率化

まず，正答率が低い回答者からの回答を除くことで，ナイーについて述べている．この効率化手法は，複数の HIT を 1 つブな回答収束点よりも，少ない回答で回答収束とする手法につの HIT にまとめたり，フィルタリングすることによって比較すいて説明する．正答率が低い回答者からの回答を拒否することるための HIT の個数を減らしている．

で，同回答が増え，ナイーブな回答収束点よりも少ない回答数

しかし，Marcus らや Franklin らは，全ての HIT を割当数で過半数となり，回答収束を早めることができると考えられる．

まで収集している．本論文では，これ以上クラウドの回答を収よって，各回答者の正答率を用い，低い正答率の回答者からの集しても，回答が変わらないと考えられる回答収集点について回答を拒否する．そのため，3. 2 節で求めた回答者正答率で，議論する．

以下の両方の条件を満たす回答者からの回答は拒否する．

3. 提 案 手 法•

全 HIT の R%以上に回答している•

正答率が 60%以下

本章ではまず，今回想定しているクラウドソーシングを用い次に，信頼できる回答者を用いて回答収束点を推定する手法

たデータベース演算について説明する．その後，回答者の正答を説明する．本手法では，3. 2 節の手法で求めた回答者の正答率を求める手法について述べる．最後に，回答者の正答率を用率を用いて信頼できる回答者を定め，その後信頼できる回答者いて各 HIT の回答収束点を早める提案手法について述べる．

を使用して回答収束点を推定する．信頼できる回答者は，以降

3. 1 クラウドソーシングを用いたデータベース演算の HIT にも正しい回答をすると仮定し，過半数でない場合も本論文では，文献 [5] で提案されているジョイン演算子を処回答が収束したと推定する．

理するためのアプローチ Simple を用いて，各 HIT の回答収束点を議論する．

以下に示す条件を両方満たす回答者が，過半数より小さいα名回答すれば，回答が収束したと推定する．

Simple とは，各 HIT 毎にアイテムペアと質問，ペアが等•

全 HIT の R%以上に回答している

しいか評価するための 2 つのボタン (Yes，No) からなる web•

正答率が 90%以上ページを作成し，クラウドの回答者に回答してもらう手法である．M 個のアイテムと N 個のアイテムをもつ 2 つのテーブル

また，以下の両方の条件を満たす回答者からの回答は，α名より少ないβ名の回答で回答収束点と推定する．のアイテムをジョインするために，N × M 個の HIT を必要•

全 HIT の R%以上に回答しているとする．

•

正答率が 100%

文献 [5] では，複数の回答者からの同じ HIT への回答をまとめるため，多数決や文献 [10] で提案されているアルゴリズムを用いているが，本論文では多数決で結果を求める方法について議論する．

4. 実

験

本章では，はじめに本論文の実験で想定している人工的なクラウド回答の作成方法について述べる．次に，回答者の割合を3. 2 各回答者の正答率変化させ，回答収束点がどのように変化するかを示す．最後に，

本節では，回答を収集した複数の HIT から各回答者の正答usual の正答率を変えて，低い正答率の回答者からの回答を除率を求める方法について説明する．
本論文では，各 HIT の回答は多数決で求めるため，各 HIT

く手法と求めた信頼できる回答者を用いて回答収束点を推定する手法を用いた場合に，どの程度回答を減少できたかを示す．の”o”及び”x”の回答の過半数を，その HIT の結果として用い

4. 1 回答の作成方法と想定している回答者ることができる．HIT の結果と同じ回答をしている回答者の回

本論文では，各 HIT の回答は人工的に作成する．本節では，答を正答と呼び，違う回答を誤答と呼ぶ．結果が定まった HIT人工的な回答を作成する方法について説明した後，人工的な回の回答から，各回答者の正答数及び誤答数を調べる．よって，答者について説明する．

回答者 i(1, · · · , N ) の正答率を pi とすると，式 (1) で各回答者の正答率を求めることができる．

まず，ジョインのためのアイテム比較 HIT への回答として，Yes の場合”o”，No の場合”x”を入力する場合を考える．
タスクに対して，正しい回答ができるかの割合を本稿では

正答率と呼ぶため，回答者の正答率が 10 割の場合，すべての•HIT に対して，正しい回答をする．

回答者割合– spam=8 人

回答者の正答率 8 割の場合を例に，正答率が 10 割より低い– usual=32 人

場合の処理について説明する．回答者が HIT に回答をすると

表 2 各回答正答率での回答収束点

き，8 割の確率で正しい回答をする．しかし，2 割の確率で，usual 正答率 回答収束点誤った回答をする．誤った回答では，”o”が正しい結果の HIT5割4.13であった場合，”x”と答える．

6割

4.09

7割

3.98

類のパターンで回答すると仮定する．

8割

3.81

perfect：10 割の確率で正しい回答をする．

9割

3.58

usual：5-10 割の確率で正しい回答をする．

10 割

3.32

本論文では，回答者は N 人いるとし，各回答者は以下の 3 種

spam：5 割の確率で正しい回答をする．
N 人の各回答者がどのパターンで回答するかは最初に設定す表 1 と表 2 を比較すると，spam がいる場合回答収束点を求る．また，各回答者固有の番号を振ることで，同一回答者が同めるのが遅くなることが確認できる．よって，spam がいる場

じ HIT に複数回答できないようにする．各回答者がどの HIT合は，余分な回答を必要とする．にいつ回答するかの順序はランダムとしている．

4. 2 正答率による回答収束点の変化

4. 3 提案手法による回答収束点変化
本節では，低い正答率の回答者からの回答を除く手法及び信本節では，回答者の割合を変えた場合の各 HIT の回答収束頼できる回答者を用いて収束点を推定する手法で，どの程度回点の平均を usual 正答率毎に示す．今回は以下に示すパラメー

答を減らせるかと回答収束点がどのように変化するか実験する．

タでタスクを出した場合を想定し，実験する．

まず，usual の正答率を変化させた場合に，提案手法で回答の•割当数=5数をどの程度減らすことができたかを示す．信頼できる回答者•

テーブル数=2を用いて収束点を推定する手法を用いる場合は，減少数と回答•

各テーブルのアイテム数=20

収束点で求めた結果に違いがあるかを示す．

•

回答者数 = 40•

提案手法パラメータ

提案手法は以下に示すパラメータで，タスクを出した場合を想定し，実験する．

– 必要回答数 R = 5%•

割当数=5– α= 2 人•

テーブル数=2– β= 1 人•

テーブルアイテム数=20

上記より HIT 数はテーブル数×アイテム数=400 種類，必要と•回答者数 = 40

する総回答数は HIT 数×割当数=2000 である．

•回答者割合– spam=8 人

表 1 に，全ての回答者 (40 人) が usually の場合の usual 正答率毎の全 HIT の回答収束点の平均を示す．値は 100 回試行– usual=24 人した時の平均を示している．

– perfect=8 人•

表 1 各回答正答率での回答収束点

usual 正答率 回答収束点
5割

4.12

6割

4.07

提案手法パラメータ– 必要回答数 R = 5%– α= 2 人– β= 1 人

7割

3.90

上記より HIT 数はテーブル数×アイテム数=400 種類，必要8割3.63とする総回答数は HIT ×割当数=2000 である．以降は以下の9割

3.32

パラメータで，タスクを出した場合を想定し，実験する．また，

10 割

3.00

提案手法を用いるために一度上記のパラメータのタスクを実行し，回答者の正答率を求める．

表 1 より，回答者の正答率が上がるごとに回答収束点が早くはじめに，提案手法と比較するために，過半数が同回答と収束することが確認できる．また，usual の正答率が 10 割と 5なった HIT の回答を止める場合の回答収束点と減少数を示す．

割の回答収束点の差は，1 つの HIT で 1 回答早く収束してい表 3 に usual の正答率を 5 割から 10 割に変更し，各正答率でる．よって，正答率が 10 割の場合は 5 割に比べ，HIT 数と同100 回試行した場合の平均の回答収束点と減少数を示す．

じ数だけ回答を減少できる．
表 2 に，spam が 20%いると想定した場合に，上記のパラメータで 100 回試行し，各 usual 正答率毎の全 HIT の回答収束点の平均を示す．

表 3 を見ると，表 2 よりも，回答収束が早くなっているがこれは常に正しい回答を選ぶ，perfect の影響である．
次に，回答収束点と減少数の平均を表 4 に低い正答率の回答者からの回答を除く手法を用いた場合，表 5 に信頼できる回答

表 3 過半数での減少数
正答率

回答収束点

5. お わ り に

減少数

5割

4.07 372.92

6割

3.98 407.38

7割

3.86 457.28

8割

3.69 522.60

9割

3.51 594.68の結果 usual の正答率が高い場合収束が早くなることが確認で

10 割

3.32 672.13

きた．我々の知る限り既存の研究では，回答収束点を議論する

5. 1 ま と め
本論文では，タスクの正答率による回答収束点の違いを確認するために，一般的な回答者 usual の正答率を変化させた．そものは存在しないため，多数決を使って正答を求めるようなク
表 4 低い正答率の回答者からの回答を除く手法
正答率

回答収束点

減少数

ラウドソーシングのタスクにおいて，今回の検討は有用であると考えられる．

5割

4.06 377.69

6割

3.96 414.05

7割3.80 480.23

8割

3.56 574.26

9割

3.31 674.28

として，今回の実験で用いたパラメータでは，低い正答率の回

10 割

3.04 784.07

答者からの回答を除く手法は，少ない回答で回答が収束するこ

また，本論文では，正答率が低い回答者からの回答を除くことで少ない回答で回答収束となる手法，及び，信頼できる回答者を用いて回答収束点を推定する手法について検討した．結果とを確認できた．信頼できる回答者を用いた回答収束点推定手
表5

求めた信頼できる回答者を用いて回答収束点を推定する手法

法では，非常に少ない回答数で回答収束点と推定することがで

正答率 推定回答収束点減少数

回答違い

5割

4.07

370.67

0.00

6割

3.97

411.23

0.53

7割

3.73

506.52

2.60

8割

3.36

656.56

5.65

5. 2 今後の課題

9割

2.71

916.4014.37

今後の課題について述べる．

10 割

1.33 1468.24

2.21

きた．しかし，実際の回答収束点の回答と比べると，回答の違いがある HIT が存在し，正確に回答収束点を推定できない場合があった．

回答者の正答率：本実験ではタスク全ての回答を収集した時点で，正しい回答者の正答率を求めている．低い正答率の回答者者を用いて収束点を推定する手法を用いた場合を示す．また，信頼できる回答者を用いて収束点を推定する手法では，ナイー
ブな回答収束点の結果と比べて回答違いが何個あったかを示す．
表 4 と表 5 は usual の正答率が高い場合，表 3 と比べて多くの回答を減少できている．この結果から，回答者の正答率を用いて回答収束点を求める事で，多くの回答数を減らせることが分かる．また，正答率が 6 割や 5 割の場合は表 3 と同様の減少数となっているが，これは信頼できる回答者や正答率の低い回答者を見つけられなかったためである．
表 5 を見ると，表 4 よりも多くの回答を減少できていることが分かる．信頼できる回答者が回答していれば，同回答の回答が過半数にならない場合でも，回答収束点と推定し，残りの回答を減少することができるためである．また，正答率が 1.00 である信頼できる回答者が HIT のはじめに回答した場合，残りの回答 4 つ全てを減らすことができる．しかし，正答率が 9 割の場合に過半数で止めた場合と比べ，14HIT で回答が違っていることが確認できる．
これにより，求めた信頼できる回答者を用いて回答収束点を推定する手法で定めた条件では，正答率が 9 割の場合には，回答収束点を推定できていないことが分かる．よって，求めた信頼できる回答者を用いて回答収束点を推定する手法は，回答収束点の収束には利用できない場合があることが分かる．

からの回答を除く手法では，正答率が低い回答者からの回答を拒否しているが，まだ回答をしていない回答者の回答は拒否できない．各回答者の正答率をタスク終了時に求めるのではなく，タスク実行中に求めることができれば，低い正答率の回答者からの回答を除く手法を用いることで，タスク実行中に正答率が低い回答者からの回答を拒否できる．よって，回答者の正答率を早く正確に求める手法について検討する必要がある．
信頼できる回答者について：信頼できる回答者を用いて回答収束点を推定する手法では，90%以上の正答率と 100%正答率回答者の 2 種類の信頼できる回答者を定めた．しかし，表 5 に示したように，ナイーブな回答収束点と結果の違いがあるためパラメータについて見直す必要がある．
パラメータ：今回の実験は，限定した状況のみでしか実験を行っていない．何人の回答者が答えたかやアイテム数，割当数を変化させることにより，回答収束点が変化すると考えられる．
よって，様々なパラメータで実験をする必要がある．
回答者：各回答者は本論文では，回答の数にバラツキがないとしている．しかし，各回答者によって回答数が大きく変わることを考慮する必要がある．また，今回はシミュレーション結果であるため，実際の人間を使ったケーススタディで検証する必要がある．
正答の定め方：今回の実験では，各 HIT の割当過半数が同回答である場合，正しい回答としている．過半数以外の正答の定め方以外にも，様々な正しい回答を求める方法があると考えられる．例えば，各 HIT 同士が関係がある場合，関係がある HIT同士の回答を基に正答を定めることができると考えられる．

スパマー回答の削除：本実験では，スパマーが 20%と少なく設定し，さらに 5 割の確率で正しい回答をするとしている．ス
パマーが増えた場合過半数で正答を定める場合，正しい結果ではない答えを正解としてしまう可能性が高くなる．さらに，今回は正答率が低い回答者が増えた場合，良い回答をしている回答者が間違った回答をしていると推定してしまう．これらより，スパマーの影響を削減することが必要になってくると考えられる．
文

献[1] Sihem Amer-Yahia, AnHai Doan, Jon Kleinberg, Nick
Koudas, and Michael Franklin. Crowds, clouds, and algorithms: exploring the human side of ”big data” applications.
In SIGMOD, 2010, pp. 1259–1260.
[2] Amazon Mechanical Turk. http://www.mturk.com. 2012 年
2 月確認.
[3] Amazon. AWS Case Study: Smartsheet. http://aws.amazon.com/jp/solutions/case-studies/smartsheet/. 2012 年 2 月確認.
[4] 増永良文，「データベース入門」，サイエンス社.
[5] Marcus Adam, Wu Eugene, Karger David R., Madden
Samuel, Miller Robert C.. Human-powered Sorts and Joins.
In PVLDB, 2011, vol. 5, no. 1, pp. 13–24.
[6] Aditya Parameswaran and Neoklis Polyzotis. Answering
Queries using Humans, Algorithms and Databases. In
CIDR, 2011, 160–166.
[7] Michael J. Franklin, Donald Kossmann, Tim Kraska, Sukriti
Ramesh, and Reynold Xin. CrowdDB: answering queries
with crowdsourcing. In SIGMOD, 2011, pp. 61–72.
[8] Amber Feng, Michael J. Franklin, Donald Kossmann, Tim
Kraska, Samuel Madden, Sukriti Ramesh, Andrew Wang,and Reynold Xin. CrowdDB: Query Processing with the
VLDB Crowd. In PVLDB, 2011, Vol. 4, No. 12, pp. 1387–1390.
[9] Adam Marcus, Eugene Wu, Samuel Madden, and Robert
C. Miller. Crowdsourced databases: Query processing withpeople. In CIDR, 2011, pp. 211–214.
[10] P. G. Ipeirotis, F. Provost, and J. Wang. Quality management on amazon mechanical turk. In HCOMP, 2010, pp.
64–67.