DEIM Forum 2017 E3-4

クラウドソーシングと計算機による処理の統合記述方式
林真史†

田島 敬史††

森嶋厚行†††† 筑波大学情報学群情報メディア創成学類, 〒 305-8550 茨城県つくば市春日 1-2†† 京都大学大学院情報学研究科, 〒 606-8501 京都府京都府京都市左京区吉田 36 番地 1 号††† 筑波大学 知的コミュニティ研究センター, 〒 305-8550 茨城県つくば市春日 1-2
E-mail: †masafumi.hayashi.2016b@mlab.info, ††tajima@i.kyoto-u.ac.jp, †††mori@slis.tsukuba.ac.jp
あらまし

近年，クラウドソーシングと計算機処理を組み合わせた処理が注目を集めている．本稿では，これらを組み合わせた実行プランを段階的・包括的に記述可能な手法の提案を行う．これにより，人と計算機を組み合わせた処理の最適化や，最初は人からスタートして徐々に計算機に置き換えると言った処理を体系的に議論することが容易になる．本稿では，このような実行プランの記述方式が満たすべき条件を示し，それらを満たす記述方式を提案する．また，人だけでなく計算機によるワーカ (アルゴリズムワーカ) を想定したシナリオを題材に，提案方式による実行プラ
ン記述を用いたコスト見積りや最適化などを行う際の課題について議論する．
キーワード クラウドソーシング，問い合わせ処理

1. は じ め に
近年，問題解決のために必要な作業（以下，タスク）を，ネッ
トワーク上の群衆（以下，ワーカ）に依頼するクラウドソーシ
ング [1] が注目を集めている．
クラウドソーシングは，計算機のみでは解決困難な問題に対し有効な手法として知られているが，単純な計算など，計算機の方が有効な手法となる場合も多い．そのため，単純な計算と計算機のみでは解決困難な問題の双方を含む問題に対しては，二つの手法を組み合わせて問題解決を行うことが重要である．
本稿では，人と計算機の組み合わさった処理を包括的に記述

図 1 CDFD を用いたタスク発行までの流れ

可能な「実行プラン」の記述方式を提案する．ここでいう実行プランとは，クラウドソーシングの依頼者 (リクエスタ) が，ク

たシナリオを題材に，提案方式による実行プラン記述を用いた

ラウドソーシングのタスクや計算機処理を組み合わせた複雑なコスト見積りや最適化などを行う際の今後の課題について議論処理を記述するものである．これにより，人と計算機の処理をする．クラウドソーシングでアルゴリズムワーカが存在すると組み合わせた複雑なクラウドソーシングの設計や処理の効率化

いう可能性自体はこれまでも広く認識されてきた．本稿では，を議論する事が容易になる．

実際にアルゴリズムワーカをオープンコールする際のコスト見

本稿では，まず，提案する実行プランの記述方式が満たすべ

積り等についての具体的な課題を議論する．

き条件と，それらの条件を満たす記法を提案する．また，その本稿の構成は次の通りである．まず，2. 節では人と計算機に記述の意味を定義する．次に，人だけでなく計算機によるワーよる処理を記述するのに求められる条件について述べる．3. 節

カ (アルゴリズムワーカ) を想定したシナリオを題材に，提案方

では，関連研究を述べ本稿の位置づけを明らかにする．4. 節で式による実行プラン記述を用いたコスト見積りや最適化などをは，人と計算機のよる処理の実行プランを書くための図である

行う際の課題について議論する．

Crowd Data Flow Diagram について述べる．5. 節では，伝統

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

的な実行プランとクラウドソーシングにて扱われる実行プラン(1) 複雑なクラウドソーシング記述のための汎用的な実行プの性質の違いについて述べる．6. 節では，我々の提案する評価

ラン記述方式の提案. これまで，クラウドソーシング処理の実式を用いた実行プランの見積もりについて述べる．7. 節では，

行プランについてはいくつか提案されてきているが [2] [3]，本

本稿で提案する実行プランを活用したシナリオの提示とその課稿で提案する実行プラン記述方式は，それらよりも記述力が高題について述べる．

いものである．

(2) 人間のワーカとアルゴリズムワーカを組み合わせた処理に関する議論．本稿では，提案する実行プランを用いて，人だ
けでなく計算機によるワーカ (アルゴリズムワーカ) を想定し2. 人と計算機による処理の記述に求められる条件
クラウドソーシングを通じて，人と計算機による処理を共にオープンコールし，これらによる処理を表す実行プランの設計・処理に利用する記法は，次の条件を全て満たす必要がある．
100yõ y• CN（ 1 ） 扱うデータを記述可能である．

1oyõ y• CNÐÐ1oyõ y• CN（ 2 ） 行う処理を記述可能である．

category（ 3 ） 処理を束ねた “タスク” の単位を記述可能である

•

ti

•

•

ti

ti

（ 4 ） 処理と，処理を行う主体 (人間，計算機) の独立性を
保つ

100

1

100

100yõ

1oyõ

1oyõ

(a)

(b)

(c)

（ 5 ） 処理を行う主体の条件を記述可能である．
通常のデータベース処理などで利用される実行プランでは，(1)，(2) に関しては記述可能であるが，(3)-(5) の条件が満たされれ
図2

ない．(3) は，クラウドソーシングにて，タスクの単位と処理

自然言語の CDFD：具体例 1の単位が異なることから，必要な条件である．(4) は，クラウ
ドソーシングに人もしくは計算機に依存した処理が存在しない

LÖ

1oyõ y• CN

üy<ことを表すために必要な条件である．この条件から，どんなタ
expert<•©¤ñÆ

スク・処理も人間か計算機に割り当てることができるようにな

1oyõ y• CNる．(5) は，処理の内容に応じて，どういったワーカに委託す

Ð

Ð

®ßti
LÖ

ü

• CN

るべきかが，プラン設計に重要な要素であることから，必要な•条件である．また，以上の性質に加え，実行プランの設計に利tik—y¹èÓV

•用する事を考えた場合，簡略的な処理から順次詳細化するよう

100

100

1oyõ

な設計で利用可能な仕組みである必要がある．

1oyõ

(d)

3. 関 連 研 究
図3

伝統的なデータベースでは，リレーショナル代数による問合

ti

(e)

自然言語の CDFD：具体例 2

せ最適化が行われてきた．実行プラン最適化における，Logical100yõ y• CN

Plan では，リレーショナル代数で表され，Phisical Plan は実装
レベルの詳細を記述した演算子が利用されてきた [4]．本稿では，

Ð

id

!<@ti

Logical Plan にあたる記述が可能であり，また Phisical Planにあたる実装に近い詳細も記述できる記述方式を提案する．

½®

½®

½®

½®É\ti½®É\ti½®É\ti

また，近年クラウドソーシングを組み込んだデータベースシ
ステムが提案されている [3] [2] [5]. Deco では，伝統的な問合せ
木に，Fetch Rules や Resolution Rules を導入したものを実行

100プランの議論に利用している．人が行う処理は Fetch Rules に

1oyõ

100

1oyõ

100

1oyõ

(f)

書かれている内容に限定されており，Fetch Rules に書かれて
図4

いる操作は計算機にはできないという仮定が置かれている．本

自然言語の CDFD：具体例 3

稿で提案する記述方式は，処理とその処理が行う主体がそれぞれ独立していることから，人が行う処理も計算機が行う処理もまとめて 1 つのルールに記述し議論できる．

4. Crowd Data Flow Diagram

本稿で提案する実行プランは，人と計算機による処理を共

本節では Crowd Data Flow Diagram (以下，CDFD) につにオープンコールする事を想定している．seti@home [6] では，いて説明する．CDFD は人と計算機による処理の実行プランを計算機による処理をオープンコールしているが，オープンコー

書くための図であり，2 節で説明した条件をすべて満たす．まルするものは計算機資源だけであり，アルゴリズムは依頼者がず，CDFD の例について説明した後 CDFD の意味を定義する．

与える．本稿では，人と計算機による処理を共にオープンコー

4. 1 CDFD の例と構成要素ルする事を想定している．言い換えれば，計算機だけでなく人

CDFD を利用してタスクを記述した例（図 2〜図 4）をもともタスクに取り組むことができ，そのタスクを解くためのアに，構成要素の説明を行う．なお，タスクは英語を日本語に翻ルゴリズムもワーカが自由に選定してよい．Generalized Task

訳するものを用いる．

Market [7] では，計算機もワーカとしてモデル化し，人による

4. 1. 1 ノ ー ド

処理と計算機による処理を区別しないというアイデアが提案さ

図 2(a) は「100 の英文を翻訳するタスク」からなるクラウド

れている．しかし，そのアイデアは翻訳システムの実装としてソーシング設計を表す CDFD である．CDFD はデータ，処理，実装されており，汎用的な仕組みは構築されていない．

タスクの 3 つのノードからなる．

•

データノード： 図中にて四角で表されるデータノード

は，問題の解そのものや問題の解を生成するのに必要なデータを表す．全てのデータはその構造を表すリレーションスキーマ

Ðを保持する．図 2(a) では，“100 の英文” が，問題の解を生成ÐJapanase(word,result:r)Japanase(word,result:r)Japanase(word,result:r)r=translate(word)r=translate(word)r=translate(word)

するのに必要なデータであり，“100 の英文の翻訳結果” が，問category

題の解を表すデータである．

•

処理ノード: 図中にて楕円で表される処理ノードは，データをもとにデータ自体を変更したり，新たなデータを生成する．

1

100

100
English(word)

English(word)

English(word,category)

(a)

(b)

(c)

図 2(a) では，“翻訳処理” が，100 の英文を翻訳する作業を表す処理である．

•

タスクノード: 図中にて角丸四角で表されるタスクノー
図 5 フォーマルな CDFD：具体例 1

ドは，クラウドソーシングのタスクとして行われる処理ノードをまとめたノードである．一つのタスクで複数の処理を行うこを行う必要がある．

4. 1. 2 データ集合と集約
図 2(b) は「100 の英文を 1 文ずつ翻訳し，100 文まとめて出

Ð

Count
(count:c)とが可能である．図 2(a) のタスクでは，100 文を翻訳する処理

Result(word,checked:c)expertc=count()ÐJapanase(word,result:r)c=check(result)
Person(word,person:p)Japanase(word,result:r)

力するタスク」の設計となる．(a) との違いは 100 の英文をまとめて翻訳していたところを，1 文ずつ翻訳している点と最終的なデータをまとめて出力している点である．データノードの左上にある番号は，データの個数を表す．また，データノードr=translateE2J(word)r=translate(word)

100

English(word)の右上には，データの集約の条件を指定することが出来る．こ4. 1. 3 タスクにおける作業の集約
図 2(c) は「100 の英文をカテゴリごとに翻訳し，100 文まとめて出力するタスク」の設計となる．(b) との違いは 1 タスクの粒度がカテゴリーごとになっている点である．例えば英文がある物語の台本とし，人物をカテゴリとする．この場合，人物ごとのセリフを英文翻訳するタスクを設計できる．このように，タスクの右上に集約条件を記述した場合には，その条件を満たす処理を集めたタスクを行う事を示す．一方で，処理の右上に直接集約条件を記述した場合には，その条件を満たすデータをまとめて処理することを表す．

4. 1. 4 複数の処理を含むタスク
図 3(d) は「100 の英文を 1 文ずつ翻訳と，その英文がどの人物のセリフかを入力し，翻訳結果と，人物別のセリフ数を出力するタスク」を表す CDFD である．このように，全く別の処理をまとめて１つのタスクとしてもよい．また，一つのデー
タノードから，複数の処理ノードに矢印があっても良い．

4. 1. 5 他のタスクの結果に依存したタスク
図 3(e) は「100 の英文の中から 1 文を翻訳，その後翻訳が行われた文が正しいか確認を行い，確認されたもののみを出力するタスク」を表す CDFD である．(d) のようにタスクを 1 つにまとめることも (e) のように 2 段階に分けることも可能である．

4. 1. 6 タスクをする主体の条件
図 3(e) の確認タスクは，(e) の翻訳処理と異なり，英語翻訳の上級者 (expert) のみが行うタスクとなっている．このように，タスクノードの左上にはタスクを割り当てる主体の条件をEnglish(word)(e)

図 6 フォーマルな CDFD：具体例 2

結果” を全て集約したものが，最終的なデータとなる事を指定なる値毎に集約が行われる．

100

(d)

の例では，“1 つの英文” が 100 個存在し，“1 つの英文の翻訳している．*でなく，属性が書かれた場合には，その属性の異

p=identifyPerson(word)

指定することが可能である．条件の例としては，人間ワーカのみ，アルゴリズムワーカのみ，特定のスキルを持つ人のみ，正答率 80%以上のワーカのみ，ブラックリストに載っていない人
のみ，等が挙げられる．

4. 1. 7 結合

図 4 は「100 の英文の中の 1 文に対し，誰のセリフかというタグ付けを 3 人のワーカに行ってもらい，その中で多数決を行って最終的なデータを出力するタスク」を表す CDFD である．複数ノードの矢印が一つのノードに合流 (この場合は，複数の “タグ付け処理” の結果が “多数決処理” に合流) する場合，合流する組合せを指定 (ここでは，“同じ id を持つデータの組
み合わせ”) する．特に指定が無い場合には，全ての組合せ (直積) が渡される．

4. 2 フォーマルな CDFD
CDFD 自体は自然言語で書いて良いものであるが，我々は「フォーマルな CDFD」を定義する．フォーマルな CDFD では，ノード内に定められた形式の式を書く必要がある．図 5〜

7 は，図 2〜4 の CDFD に対応するフォーマルな CDFD である．これを例に，説明を行う．

4. 2. 1 データノード
データノードには，リレーションスキーマを記述する．ここで，リレーションスキーマとは，リレーション名の後ろに，属性名を並べたものである．図 7 においては，EnglishTag(id,word) は，翻訳前の英語タグを格納するリレーションを表す．ま た ，JapaneseTag(id, result) は ，翻 訳 後 の 日 本 語
タ グ を 格 納 す る リ レ ー ション を 表 す．ま た 図 7 に お い て ，

ン値) が入っている．特別な原子式として， リレーション R のÐ

計算が終了している事を表す R.，リレーション R の全てのタ

Result(id,result:r)

プルを変数 p に格納する R(x,y):p と行った書き方が許されて
r=majorityVote(r1,r2,r3)

いる．

JapanaseTag(id,result:r as r2)

JapanaseTag(id,result:r as r1)

JapanaseTag(id,result:r as r3)

CDFD ルールでタスクを生成するには，タスクインスタンス
毎に 1 タプルを格納する特別なリレーションを利用する．これ

r=tagging(word)

100

100

EnglishTag(id,word)r=
tagging(word)r=tagging(word)

EnglishTag(id,word)

100

EnglishTag(id,word)(f)

は，!で開始するリレーションである．次の式は，Japanase で
オープン値を含むタプル毎に，タスクを生成する事を表す．[ ]の中には，タスクの依頼対象を記述する．[*] は誰でも良いことを示す．

図 7 フォーマルな CDFD：具体例 3!Task1(word)[*] <- Japanese(word, result:@w);
JapanaseTag(id,result:r as r1 ) とあるが，ここでの “：”は，親ノードの処理結果をそのデータノードの属性に挿入することを表し，“as” は，子ノードで扱う変数として属性の名前を再定義している．

また，タスク本体を，次のような “タスクテンプレート定義”
で定義する．

4. 2. 2 処理ノード
処理ノードには，その処理を表す関数を用いた代入文を記述!Task(word) {する．例えば，result1=tagging(word1) は，英文 word1 に，

ask @w <- translate(word);

タグ付け tagging() を行い，結果を出力先データノードの属

return Japanese(word, result:@w)

性 result1 に格納することを表す．

}

4. 2. 3 結 合 条 件
結合条件は論理式で表す．例えば，id1==id2 and id1==id3
は，id1 と id2 と id3 が同じ値であることを表す．同じ名前のタスクテンプレート定義の中では，そのタスク中で聞く質問と，変数は，同じ値に束縛されるので，もし 3 つのデータノードに結果表すタプルを記述する．複数の異なるタプルを一つのタス

全て EnglishTag(id, word) と書かれている場合には，条件

ク本体で記述することが許される．

式を書かなかったとしても，同じタグか否かを結合条件とする．

4. 3. 2 ルール集合への変換

4. 3 フォーマルな CDFD の意味

図 5〜7 の CDFD をルール集合に変換したものを図 8〜10 に

本節では，フォーマルな CDFD の意味を定義する．まず，示す．これは，中間データを表す各ノード毎に，次の規則によフォーマルな CDFD をルール集合に変換し，次に，そのルー

りルールを導出することにより作成したものである．次のルール集合の意味を定義する．

ルでは，矢印でつながるノードの元側を親，先側を子と呼ぶ．

4. 3. 1 CDFD ルール言語

また，これらの閉包をそれぞれ祖先，子孫と呼ぶ．親の居ない

CDFD ルール言語は，CyLog に似た言語である．CyLog とノードを始端ノード，子の居ないノードを末端ノードと呼ぶ．

は，Datalog [8] 風の構文を持つ，クラウドソーシング用のプロ

以下の説明では，次の記号を用いる．

グラミング言語である．フォーマルな CDFD の意味は，CDFD•

CDFD のノードを n と表記する．

ルールの集合として表されるため，ここではまず CDFD ルー•n の祖先ノードのうち，最も n に近いデータノードをルについて説明する．

CDFD のルールは，Datalog ルールと似ている．例えば，
データベースに格納されている英文を，人で翻訳する処理を考える．次の処理は，図 12(a) を CDFD ルール言語として表した例 (図 8(a)) の一部である．

nd1 , nd2 , . . . , ndk とする．
••

ndi と n に 挟 ま れ た タ ス ク 内 の 処 理 ノ ー ド を

tp1 , tp2 , . . . , tpk とする．
•

Japanase(word,result:@r) <- English(word)ndi と n に 挟 ま れ た タ ス ク 外 の 処 理 ノ ー ド を

np1 , np2 , . . . , npk とする．

ノード n に書かれている式を exp(n) と表現する．

このとき，始端以外のデータノード n それぞれに対して，次のルールを導出する．

ここで，English は英文を表す述語である．これらの述語を用いて記述された English(word) などの式を原子式 (Atom)exp(n) ←exp(nd1 ), exp(nd2 ), . . . exp(ndk ),[exp(np1 ), exp(np2 ) . . . exp(npm )]と呼ぶ．原子式は左から評価され，引数に指定された変数が束

ただし，処理ノード npi がタスクノードに含まれている場合縛される．ここで@で始まる変数はタスクを通じて人間が値をには，exp(npi ) は代入する変数の先頭に@マークを付け，後述

入力するという指定である．@r の場所には，特別な値 (オープするように，タスク本体の定義に含める．このルールでは，そ(a),=L=J=OA SKN@á NAOQHPã 7NAOQHP Z 'JCHEOD SKN@ áè 6=OG SKN@O Û Z 'JCHEOD SKN@ á ,=L=J=OA:SKN@á NAOQHPã 7NAOQHP;è 6=OG SKN@ <=OG 7NAOQHP Z PN=JOH=PA:SKN@;
NAPQNJ ,=L=J=OA:SKN@á NAOQHPã 7NAOQHP;=(b),=L=J=OA SKN@á NAOQHPã 7NAOQHP Z 'JCHEOD SKN@
è 6=OG SKN@ Û Z 'JCHEOD SKN@ á ,=L=J=OA:SKN@á NAOQHPã 7NAOQHP;è 6=OG SKN@ <=OG 7NAOQHP Z PN=JOH=PA:SKN@;
NAPQNJ ,=L=J=OA:SKN@Oá NAOQHPã 7NAOQHP;=
6=>HA SKN@á NAOQHPOã N Z ,=L=J=OAä á ,=L=J=OA SKN@á ”‡•—Ž– ã ˜á >” Z =CC R ?
,=L=J=OA SKN@á NAOQHPã 7NAOQHP Z 'JCHEOD SKN@O áè 6=OG SKN@ Û Z 'JCHEOD SKN@ á ,=L=J=OA SKN@á NAOQHPã 7NAOQHP á

distinct English(category)

(c)

(d)

,=L=J=OA SKN@á NAOQHPã 7NAOQHP Z 'JCHEOD SKN@
2ANOKJ SKN@á LANOKJã 7LANOKJ Z 'JCHEOD SKN@%KQJP ?KQJPã ?KQJP Z 2ANOKJ SKN@á LANOKJ ã Iá ?KQJP L ?KQJP I
è 6=OG SKN@ Û Z 'JCHEOD SKN@
è 6=OG SKN@ <=OG 7N Z PN=JOH=PA't, SKN@
=OG 7L Z E@AJPEBU2ANOKJ SKN@
NAPQNJ ,=L=J=OA SKN@á NAOQHPã 7N á 2ANOKJ:SKN@á LANOKJã 7L;=
ƒ„Ž‡ SKN@á NAOQHPã N Z ,=L=J=OAä á ,=L=J=OA SKN@á ”‡•—Ž– ã ˜á >” Z =CC R ?

(e),=L=J=OA SKN@á NAOQHPã 7N Z 'JCHEOD SKN@
4AOQHP SKN@á ?DA?GA@ã 7? Z ,=L=J=OA SKN@á NAOQHPã 7N
è 6=OGs SKN@ Û Z 'JCHEOD SKN@
è 6=OGs SKN@ <=OG 7N Z PN=JOH=PA SKN@
NAPQNJ ,=L=J=OA SKN@á NAOQHPã 7N=
è 6=OGt NAOQHP ATLANP Z ,=L=J=OA SKN@á NAOQHPè 6=OGt NAOQHP <=OG 7? Z ?DA?G NAOQHP
NAPQNJ 4AOQHP SKN@á ?DA?Gã 7?
=‡•—Ž– SKN@á NAOQHPã N Z 4AOQHPä á 4AOQHP SKN@á ”‡•—Ž– ã ˜á >” Z =CC R ?

è 6=OG SKN@ <=OG 7NAOQHP Z PN=JOH=PA:SKN@;
NAPQNJ ,=L=J=OA:SKN@Oá NAOQHPã 7NAOQHP;=
6=>HA SKN@á NAOQHPOã N Z ,=L=J=OAä á ,=L=J=OA SKN@á ”‡•—Ž– ã ˜á >” Z =CC R ?

図 8 CDFD の式表現：具体例 1

図 9 CDFD の式表現：具体例 2の結果を格納する変数名に@マークを付ける．
例えば，図 6(a) の CDFD からは，次のルールが導出される．

Japanese(words, result : @result) ←,=L=J=OA6=C E@á NAOQHPã 7N =O Ns Z 'JCHEOD6=C E@á SKN@,=L=J=OA6=C E@á NAOQHPã 7N =O Nt Z 'JCHEOD6=C E@á SKN@,=L=J=OA6=C E@á NAOQHPã 7N =O Nu Z 'JCHEOD6=C E@á SKN@
è 6=OG SKN@ Z 'JCHEOD6=C:SKN@;(f) è 6=OG SKN@ <=OG 7N Z P=CCEJC SKN@
NAPQNJ ,=L=J=OA6=C:E@á NAOQHPã 7N;=

English(words)

4. 3. 3 データの集約
データノード ndi に対して集約が指定されている場合には，次のルールを導出する．

4AOQHP E@á NAOQHP Z ,=L=J=OA6=C E@á Ns á ,=L=J=OA6=C E@á Nt ,=L=J=OA6=C E@á Nu ,NAOQHP Z I=FKNEPU8KPA Nsá Ntá Nu
6=>HA E@á NAOQHPã N Z 4AOQHPä á 4AOQHP E@á ”‡•—Ž– ã ˜á >” Z =CC R ?

S(a, y) ← distinct R(y), R(x, y) : v, [a ← agg(v)]ここで，exp(ndi ) = R(x, y) とし，集約条件として y が指定

図 10 CDFD の式表現：具体例 3

されているとする．また，exp(n) = S(a, y) とし，a は集約結果を格納する変数とする．集約条件が*の場合には，distinct

5. 1 ワーカに関する要素

R(y) は指定されず，次の様になる．

データベースシステムにて行われる処理は，正しいことが検証されたアルゴリズムによって全て行われることが一般的であS(a, y) ← R., R(x, y) : v, [a ← agg(v); ]る．一方で，クラウドソーシングの処理においては，スパムが混じる可能性もあり，スパムでなくても一般に処理結果が正し

ここで，R. は，R の結果が全てそろうと true を返す述語である．

4. 3. 4 タ ス ク
各タスクノードに対して，次のルールを導出する．ここで，nti は，タスクの中に処理ノード，?exp(nti ) は，タスクの結果が格納されたタプルを表す．

いとは限らない．また，実際に処理を開始したときに，どれぐ
らいのワーカが参加可能かは一般には不明である．これらの点も，適した実行プランを最初から選択することを困難にする一因となる．

5. 2 データに関する統計情報の有無
一般にデータベースシステムは既にデータが存在し，そこから得られた統計情報を元に実行プランを評価できる．しかし，!T askk (id) ←?exp(nt1 ), ?exp(nt2 ), . . . , ?exp(ntn );また，タスク本体を定義し，タスク中の処理ノードの全ての質問文とその結果を返すタプルを記述する．

4. 3. 5 タスクの集約

クラウドソーシングを処理に含む場合，データが処理の初期段階では存在しない場合がある．従って，処理開始時には統計情報が得られず，適した実行プランを選択することが困難である．

6. 実行プランの見積り

タスクの集約が指定されているときには，次のルールを導出する．ここで，R(y) は，集約の属性値を提供するデータノードのリレーションであり，y が集約の属性値とする．

本節では，前節で説明した，データに関する統計情報や，ワーカに関する情報は既知として，CDFD で記述された実行プラ
ンから，タスク数，費用，実行時間を見積もる方法を検討する．

!T askk (id, v) ← Rel(exp(nt1 ))., . . . Rel(exp(nt2 ))., distinctR(y)5. 伝統的な実行プランとの性質の違い
提案する記述方式による実行プランを利用した各種コストの見積りや最適化を行う際には，データベースシステムを対象とした伝統的な実行プランを扱う場合と比べて，次の 2 つの大きな違いがある．

データに関する統計情報などの議論は次節で行う．
ある CDFD が与えられたとき，ここでは次の表記を用いる．

•

T = {t1 , t2 , . . . , tn } をそこに含まれるタスクノードの集合とする．例えば，図 11 の場合，T = {t1 , t2 , t3 } である．

•

各 タ ス ク ノ ー ド ti に 入 次 す る デ ー タ ノ ー ド の 集 合を，In(ti ) = {di,1 , di,2 , . . . , di,n } と表記する．図 11 の場合，

T otalcost(ti ) = Count(ti ) ∗ Cost(ti )Datacategory
Process

6. 3 時間の見積り

t1

実行プランの時間を見積もるうえで重要なのはタスクの並列

d.name1,1 =d.name1,2 =d.name1,3

d1,1

d1,2

Process

Process性である．タスクが並列に処理できる場合，かかる時間は並列

d1,3にこなされるタスクの中で最も処理時間が長いものになる．そt2

Processt3

こで，次の仮定を置く．

•
100

100

d2,1

d3,1

図 11 CDFD に関する見積りで利用する例

データノード di,j が保持するタプル数を N (di,j ) と表記

する．図 11 の場合，N (d2,1 ) = 100 である．

•

タスクノード ti に入次するデータノードが表すリレー

ションのうち，結合結果のタプルの数を #Jointi (In(ti )) とする．図 11 の場合，t1 にて，In(t1 ) のデータノードのリレーショ
ン “name” がそれぞれ一致するタプルの数が #Jointi (In(ti ))である．

•の集合を P red(ti ) とする．図 11 の場合，P red(t1 ) = t2 , t3 である．

•

タスク ti の処理時間は T ime(ti ) とする．

•

末端のタスクノードから ti までを処理するために必要な処理時間を T otaltime(ti ) と表現する．ti が末端の時は，In(t1 ) = {d1,1 , d1,2 , d1,3 } である．
•

あるタスクノード ti に最も近い子孫となるタスクノード

タスク ti の集約条件として属性名が記述されている

T otaltime(ti ) = T ime(ti ) である．
•

P red(ti ) に含まれるタスクノードのうち，最も長い To-

taltime を持つ tj を M ax(P red(ti ) と表現する．P red(ti ) = ϕの場合は T (P red(ti )) = nil を返す． ここで，T ime(nil) = 0と定義する．
以上のとき，末端のタスクノードから ti までを処理するために必要な処理時間は，次のように再帰的に表すことができる．
実行プランの合計処理時間を求めることができる．

場合，その属性値を用いて集約を行う．その結果のタスク数

T otaltime(ti ) = T ime(ti ) + M ax(P red(ti ))#Aggattr (ti ) とする．図 11 の場合，t1 のタスクは，入次されたデータノードのリレーションの中で，属性 “category” のデー
タに集約を行い，そのデータごとにタスクが行われる．その時のタスク数を #Aggcategory (t1 ) と表記する．

•

タスクノード ti が表現するタスクを一つ実行するために必要なコスト (費用) を Cost(ti ) と表記する．

7. シナリオ例と課題
本節では，翻訳を行う実行プランを題材に，提案した記述方
式の実行プランを活用する際の課題について議論する．

7. 1 シナリオ例
本シナリオでは，10 万の英文のうち，観光に関する文を日本

6. 1 タスク数の見積り
タスクノード ti が表すタスクのタスク数の見積り Count(ti )は，タスクノードに集約条件 attr が記述されているかどうか語に翻訳する問題を扱う．ワーカは，人であっても，アルゴリ
ズムであってもよいとする．

7. 2 実行プランの例に依存する．
タスクノードに集約条件 attr が記述されている場合，

このシナリオを実現するための実行プランの例をいくつか示Count(ti ) = Aggattr (ti ) となる．しかし，#Aggcategory (t1 ) のす．ここでは異なる二つの状況で有効と考えられる実行プラン

数は，データに依存する．データがデータベースにあらかじめ

を示す．

•

格納されている場合は求めることが可能であるが，クラウド
ソーシング等で入手する場合は，正確に求めることはできない．
したがってそのような場合には，タスク数は attr を含むリ
レーションのタプル数と同じであると見積もる．

•

タスクノードに集約条件が記述されていない場合，

Count(ti ) = #Join(ti ) となる．リレーションの統計値を用第一に，人による作業は信頼できるという状況で有効と考えられるプランは次が考えられる．

•

図 12(プラン 1) は，まず，すべての文にタグをつけ，その後，観光に関する文だけを翻訳する．これらの作業はともに人手で行う．

•

図 12(プラン 2) は，プラン 1 と同じであるが，タグ付け

いて見積もることが可能な場合にはそれを利用する [9] が，不はアルゴリズムで行う．これは，タグ付けを行うアルゴリズム

可能な場合には，最悪，データの数はそれぞれのタプルの直積

ワーカの品質が良い場合に適していると考えられる．

となる．したがって，従って次の式となる．

Count(ti ) =∏N (di,j )di,j ∈In(ti )6. 2 費用の見積り
タスク ti で必要とされる費用 T otalcost(ti ) は次の式で表現できる．

•

図 12(プラン 3) は，タグ付けの結果を人手で確認する実行プランである．タグ付けを行うアルゴリズムワーカの品質があまりよくない場合に適していると考えられる．
第二に，人による作業が必ずしも信頼できないという状況でのプランは次のようなものが考えられる．

•

図 13(プラン 4) は，タグ付けを複数人のワーカの多数決によって決定した後，翻訳処理を行うプランである．このプラ表 1 人間ワーカとアルゴリズムワーカの違い
人間ワーカ

アルゴリズムワーカ

タスクの処理速度

低速

高速

本人の自信度

信頼できない信頼できる判定し，高ければ採用する．

7. 4 問題 2: データ統計情報や単価情報の取得
クラウドソーシングによって入力が行われるデータに関しては，事前に統計情報を得ることは困難である．例えば，このシナリオ例では，10 万文のそれぞれが観光に関する文か否かのタンは，ワーカの品質がそれほど高くない状況でも有効と考えらグは既知でないため，どれだけの文を日本語に翻訳する必要がれる．理由は，タグ付けは不正解の数が多く，不正解のもの同

あるかわからない．したがって，ランダムサンプリングなどで士で一致することがすくないからである．

タスクの一部をワーカに回答してもらい，その結果から全体の•図 14(プラン 5) は，図 13(プラン 4) と同じであるが，多数決の一員をアルゴリズムで行う．

データの推定を行う方法が考えられる．その推定作業を実行プ
ランの一部として含めることが必要と考えられる．

7. 3 問題 1: アルゴリズムワーカの扱い

各タスクを行う際の単価についても取得する必要があるが，まず，オープンコールによって参加するアルゴリズムワーカ

人間とアルゴリズムでは，コストモデルが異なることにも注意を評価する仕組みが必要である．アルゴリズムワーカと人間が必要である．人間は，タスク処理数に比例して支払いを行う

ワーカでは，ワーカとしての性質が異なる (表 1)．異なる性質

ことが一般的と思われるが，アルゴリズムは一定の開発コストの一つとして，回答者であるワーカの自信の信頼度がある．人がかかり，実行時のタスク数だけに比例した支払いは必ずしも間ワーカの回答とその自信度には相関が無いことが知られてい適切でないかもしれない．これらに関しては，ワーカ側が提案

る [10]. 一方で，アルゴリズムワーカは定められた処理から答

するか，こちら側が提案して納得のいくワーカのみが参加する

えを導き出すため，その自信度には信頼性があるといえる．タなど，何らかの調整の仕組みが必要と考えられる．

スクの種類にもよるが，人間による処理を前提としたクラウド

7. 5 問題 3: 実行プランの選択

ソーシングタスクの多くでは，一般に，アルゴリズムワーカの実行プランを評価するための各種情報の入手や推定が終了しタスクの正解率は低くなりがちである．したがって，ゴールド

たら，次のステップとして，適切な実行プランを選択することスタンダードデータ（既知の解答）を用いたテストなどの成績になる．本来は，同じ結果をもたらす実行プランを列挙する必は必ずしも高くなく，スパムではないにもかかわらず，人間の要があるが，本稿では，7. 1 節で説明した実行プランを対象とワーカでなければ採用されない可能性がある．

する．ここでは下記を仮定する．まず，人のタスク処理の費用

しかし，必ずしも平均して正解率が低いわけではなく，特定と時間を表 2 と仮定する．次に，アルゴリズムワーカはタスクのパターンの場合には得意であるという状況も存在する．例えとごとではなく，固定で 1M(M は 106 を意味する) の費用を必ば，計算機を使って多くの漢字と少数の英数字の混じる画像を要とし，タスクの処理時間を 1 とする．また，観光に関する文

1 文字ずつ文字におこすタスクを考える．平均のタスク正解率

が 10 万の場合と 10 の場合のそれぞれを検討することとし，実が低かったとしても，英数字に限って言えば，認識精度が高い

行プランの 3 つの評価軸で比較する．

といったケースが考えられる．

この仮定の下で，プラン 1〜3 を比較した結果を表 3 に示し，また，タスクの処理コストが人間に比べて圧倒的に安いため，
少しでも活用できるなら活用してもトータルとしては安上がりになる可能性もある．

を意味し，時間の単位は秒，費用の単位は円とする．
この表からわかるように，費用，時間，人の行うタスク数のしたがって，アルゴリズムワーカを活用するには，次を気をつける事が必要と考えられる．(1)

プラン 4〜5 を比較した結果を表 4 に示す．ここで，K は 103

すべてにおいて優れたプランは必ずしも存在しない場合がある．

正解率が低くてもスパム

例えば，タスクの数が 10 の場合，プラン 1 が最もタスクの費用として扱うのではなく，活用出来る機会を検討する．(2) 得意が少なく，プラン２が最も処理時間が短く人間が行うタスク数な問題では正解率が高い可能性が高いという性質を利用する．

が少ない．したがって，一概にどちらが良いとは判断できない．

そこで，上記のような点を考慮した，アルゴリズムワーカの

この問題の解決策として考えられるのは，依頼者が何を希望

採用判定方法が考えられる．ポイントは次の通りである．(1)

するかを事前に取得する方法である．例えば，依頼者が時間の得意なものをアルゴリズムワーカ自身に申告させる．(2) 単純

速さを最重視する場合は，タスク 10 のプランの中で最適なプに正解率の高低を問題にするのではなく，選択肢からランダム

ランはプラン 2 となる．反対に，依頼者が費用の安さを最重視に解答を行うワーカ（以下，ランダムワーカ）と比べて有意にする場合は，最適なプランはプラン 1 となる．

正解率が高ければワーカとして採用する．

以上から，複数の視点を元にそのシナリオで求められる実行

具体的には，次の手順で，判定を行う．

プランを選択することが要求される．また，一般のデータベー（ 1 ） 計算機に既に正解が既に得られているタスクを渡し，ス問合せと比較して長時間の処理時間が必要になることから，その回答を得る．回答のうち，正解率の計算対象として欲しい

動的な最適化の必要性がより高いと考えられる．

回答にはフラグを付ける．
（ 2 ） フラグがついている回答と，正解を比較し，正解率を求める．
（ 3 ） ランダムワーカよりも統計的に有意に高いかどうかを

8. まとめと今後の課題
本稿では，人と計算機による処理を包括的に記述可能な「実行プラン」記述方式を提案した．また，人と計算機の処理をと

表 2 タスクの費用・時間

½®ÉX•

費用 時間

!<@

翻訳タスク

100

100

½®ÉX•

タグ付けタスク

60

60

!<@

確認タスク

30

30
½®ÉX•

CN

human

½®ÉX•

時間

人間が行うタスク数

プラン 1

100K

16M

16M

200K

プラン 2

100K

11M

10.1M

100K

プラン 3

100K

14M

13.1M

200K

プラン 1

10

1.6K

1.6K

20

プラン 2

10

1001K

1.01K

10

プラン 3

10

1001.3K

1.31K

20

CN

½®ÉX•

CN

CN

human

human
y½®É\

表 3 実行プラン１〜３の評価
英文の数 タスクの費用

*

CN

y½®É\

y½®É\

•

CN

•

ti

human
100000²oyõ

Õçñ5

図 14 実行プラン例：３謝

表 4 実行プラン４〜５の評価

辞本 研 究 の 一 部 は ，JST CREST お よ び JSPS 科 研 費
英文の数 タスクの費用

時間

人間が行うタスク数

プラン 4

100K

23M

16M

300K

プラン 5

100K

28M

16M

400K

プラン 4

10

2.3K

1001.6K

30

プラン 5

10

2.8K

1.6K

40

-½®yoOjõ
• CN

human

*

y

-½®yoOjõ
• CN

*

y

½®ÉX•

CN

-½®yoOjõ

-½®yoOjõ*• ti-½®ÉX•

• ti

文

human

human
• ti

CN

-½®yÅ–½•®T½®yoOjõ
-½®yÅ–½•®Thuman-½®yÅ–½•®T®ßti½®yoOjõ

human½®yoOjõ

½®yoOjõ

Algorithm
y½®É\

100000Algorithm

y½®É\

y½®É\

100000
²oyõ

²oyõ

Õçñ1

Õçñ2

100000²oyõ

Õçñ3

図 12 実行プラン例：１-½®yoOjõ
• CN

y

*

human
•

ti

-½®yoOjõ
-½®yÅ–½•®T½®yoOjõ

!<@

½®ÉX•

CN

human

½®ÉX•

CN

human
y½®É\

100000½®ÉX•

CN

Algolithm
y½®É\

y½®É\

²oyõ

Õçñ4

図 13 実行プラン例：2もにオープンコールして行う場合を想定し，提案した実行プランを用いた処理や最適化について議論を行った．今後は，各種
統計情報の推計手法や，同等の実行プランを数え上げる体系的な手法の開発が必要である．

(#25240012) の支援による．
献[1] Jeﬀ Howe. The rise of crowdsourcing. Wired Magazine,
Vol. 14, No. 6, 06 2006.
[2] Aditya Parameswaran, Hyunjung Park, Hector GarciaMolina, Neoklis Polyzotis, and Jennifer Widom. Deco:
Declarative crowdsourcing. Technical report, Stanford University, 2012.
[3] Michael J. Franklin, Donald Kossmann, Tim Kraska, Sukriti
Ramesh, and Reynold Xin. Crowddb: Answering queries
with crowdsourcing. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data,
SIGMOD ’11, pp. 61–72, New York, NY, USA, 2011. ACM.
[4] Hector Garcia-Molina, Jeﬀrey D. Ullman, and Jennifer
Widom. Database Systems: The Complete Book. PrenticeHall, 2002.
[5] Atsuyuki Morishima, Norihide Shinagawa, Tomomi Mitsuishi, Hideto Aoki, and Shun Fukusumi. Cylog/crowd4u: A
declarative platform for complex data-centric crowdsourcing. Proc. VLDB Endow., Vol. 5, No. 12, pp. 1918–1921,
August 2012.
[6] David P. Anderson, Jeﬀ Cobb, Eric Korpela, Matt Lebofsky,
and Dan Werthimer. Seti@home: An experiment in publicresource computing. Commun. ACM, Vol. 45, No. 11, pp.
56–61, November 2002.
[7] Dafna Shahaf and Eric Horvitz. Generalized task markets
for human and machine computation. In Proceedings of theTwenty-Fourth AAAI Conference on Artificial Intelligence,
AAAI’10, pp. 986–993. AAAI Press, 2010.
[8] Stefan Ceri, Georg Gottlob, and Letizia Tanca. What you
always wanted to know about datalog (and never daredto ask). IEEE TRANSACTIONS KNOWLEDGE AND
DATA ENGINEERING, Vol. 1, No. 1, pp. 146–166, 1989.
[9] Gregory Piatetsky-Shapiro and Charles Connell. Accurate
estimation of the number of tuples satisfying a condition.
SIGMOD Rec., Vol. 14, No. 2, pp. 256–276, June 1984.
[10] Satoshi Oyama, Yukino Baba, Yuko Sakurai, and Hisashi
Kashima. Accurate integration of crowdsourced labels using workers’ self-reported confidence scores. In Proceedingsof the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI ’13, pp. 2554–2560. AAAI Press,2013.