DEIM Forum 2013 C4-1

宣言的記述によるクラウドソーシングシステムの開発支援
権守

健嗣†

森嶋

厚行††,†††† 筑波大学 情報学群情報メディア創成学類 〒 305–8550 茨城県つくば市春日 1–2†† 筑波大学 図書館情報メディア系/知的コミュニティ基盤研究センター 〒 305–8550 茨城県つくば市春日 1–2††† JST さきがけ
E-mail: †s1113114@u.tsukuba.ac.jp ††mori@slis.tsukuba.ac.jp
あらまし

近年，クラウドソーシングによるデータ収集・整理・処理等が広く行われている．それに伴い，クラウド

ソーシングシステムの開発を支援するツールも多く登場している．一般に，クラウドソーシングは宣言的記述と相性が良いと考えられるが，既存のツールの多くは，手続き型言語によるクラウドソーシングシステムの実装を支援するものである．本論文では，宣言的記述によりクラウドソーシングシステムの開発を支援する手法を提案する．具体的には，クラウドソーシングシステムを宣言的に記述するための CTD(Condition-Task-Data) 抽象化を提案する．CTD
抽象化は，商用のクラウドソーシングプラットフォームなどで広く使われているタスクテンプレートの一般化になっている．本論文はさらに，CTD 抽象化が大きな表現力を持つ事を示すほか，CTD 抽象化を用いたクラウドソーシン
グシステム開発支援ツール Crapid についても説明する．
キーワード

クラウドソーシング，開発支援，宣言型プログラミング

1. は じ め には，次の 3 つの理由から，本質的に宣言的記述と相性がよいと考えられる．

計算機ネットワーク技術の発達に伴い，不特定多数の群衆に(1) 群衆は並列に非同期で作業すると仮定することが自然で仕事を委託するクラウドソーシングが広く行われるようになっあるが，手続き型のコードではその記述が容易ではない．例えている．一般に，クラウドソーシングを行うシステムは，クラば，fork 関数等を利用して同時実行を実現するなどの工夫が必

ウドソーシングシステムと呼ばれている [1]．例えば，画像のタ要である [5]．

グを人手で付与する ESP Game [2] や，OCR で正しく処理で(2) クラウドソーシングシステムを実現する手続き自体を記

きない画像から人手でテキスト抽出を行う reCAPTCHA [3] と述することが難しい場合が存在する．例えば，つくば市のカいったクラウドソーシングシステムがある．

フェの情報を集めて，駅に近い順に並べるクラウドソーシング

クラウドソーシングの重要性が認識されてきたことから，クを考える．この場合，つくば市のカフェを入力するタスク A を

ラウドソーシングのための基礎機能を提供するクラウドソー

N 回実行 (クラウドが作業) し，次に，入力されたカフェを近い

シングプラットフォームが登場してきた．例えば，Amazon

順に並べるタスク B を実行するという手続きが考えられる．しMechanical Turk [4]（以下，MTurk）は，少額の謝金が支払わかし，この手続きの記述において，N をいくつに設定するか，れる作業 (タスク) を群衆に割り当てるための市場を提供する

すなわち，いつタスク A を終了してタスク B に移行すれば良クラウドソーシングプラットフォームである．これらのプラッ

いかは自明ではない．一方，宣言的記述では N を指定しない

トフォームではソフトウェアから呼び出し可能な API を提供

記述が可能であり，インクリメンタルな実行も容易である．

しており，クラウドソーシングシステムのソフトウェアからタスクを登録することを可能としている．

(3) クラウドソーシングは本質的に人手での処理を必要とするため，一般に処理のコストが高い．したがって，計算機だけ

クラウドソーシングシステム実現のためのプログラミングにの処理と比較しても最適化の重要性が高いと考えられる．宣言は固有の頻出パターンがあるため，ソフトウェア開発を支援す的記述に関しては最適化の技法が数多く研究されているため，るためのツールがいくつか開発されてきた．例えば，TurKit [5]

これらの知見を適用することができると考えられる．

ではプログラムの再実行の効率化を図るための仕組みやタスク

以上の理由から，本質的にクラウドソーシングは宣言的記述を定義する関数などが定義されている．TurKit をはじめとすと相性が良いと考えられるが，Java 等の手続き型言語と比較しる既存の支援ツールの多くは，手続き型プログラミングの支援て，Prolog や Datalog のようなホーン節形式のルールによるを行う．例えば，手続き型プログラムから呼び出し可能なライ

宣言的記述は一般に普及していない．したがって，現在の多く

ブラリを提供するといったものがある．

のプログラマにとって単純なホーン節形式によるプログラミン

本研究では，宣言的記述によりクラウドソーシングシステム

グは敷居が高いと考えられる．また，SQL でクラウドソーシンの開発を支援する手法を提案する．具体的には，ルールベース

グを記述するアプローチも存在する [6] が，後述するようにその言語を用いてクラウドソーシングシステムを記述し，そこかの記述力は高くない．

ら実行可能なコードを生成する．クラウドソーシングシステム

本論文では，まず，クラウドソーシングシステム開発のため

の宣言的記述として CTD 抽象化 (Condition-Task-Data Ab-<?xml version="1.0" encoding="UTF-8"?>

straction) を提案する．CTD 抽象化は，クラウドソーシング<QuestionForm xmlns="http://mechanicalturk.

システムを，CTD ルールの集合として記述するものである．

amazonaws.com/AWSMechanicalTurkDataSchemas/

CTD ルールとは，3 章で説明するように，MTurk を含む多く

2005-10-01/QuestionForm.xsd">のクラウドソーシングプラットフォームで広く使われている<Question>

タスクテンプレートの一般化である．したがって，CTD 抽象<QuestionIdentifier>1</QuestionIdentifier>

化は，既存のクラウドソーシングプラットフォームの利用者に<QuestionContent><Text>How many movies have you seen thisとってなじみやすいと考えられる．
次に，本論文は CTD 抽象化の表現力について議論する．一

month?</Text>

般に，プログラミング言語の表現力を議論するにはチューリン</QuestionContent>

グ完全性が議論されるが，本論文では，記述可能な “人とのイ<AnswerSpecification>

ンタラクション” に着目した記述力の尺度 (ゲーム完全性と呼<FreeTextAnswer/>ぶ) を導入する．さらに，CTD 抽象化はチューリング完全であ</AnswerSpecification>

り，かつ，ゲーム完全である事を示す．

</Question>

最後に，CTD 抽象化を用いた開発支援ツール Crapid の説明</QuestionForm>を行う．Crapid は，フォームベースで CTD 抽象化によるクラウドソーシングシステムの記述から，実行可能なコードを出力

図 1 MTurk のタスクテンプレート例

するものである．具体的には，様々なタスクテンプレートのひな形を Crapid 側で用意する事により，容易にプログラムが書

スプログラミング言語である．しかし，単純なホーン節のルー

けるようになっている．

ルは，必ずしも一般のプログラマが書きやすいものではない．

本論文の構成は次の通りである．2 節では関連研究について(5) SQL 風記述として抽象化：CrowdDB [6] は，SQL 風言語

述べる．3 節では，CTD 抽象化について説明し，4 節でその表によるクラウドソーシングの記述をサポートする．詳細は 4. 3

現力について議論し，他の開発支援ツール等と CTD 抽象化の節で議論するが，CTD 抽象化の方が表現力が大きい．

表現力を比較する．5 節では，CTD ルールの集合をプログラミ

本研究で提案する CTD 抽象化に用いる CTD ルールは，ECA

ング言語 CyLog に変換するツール Crapid について説明する．

(Event-Condition-Action) ルールの組み合わせとして実装可能

6 節はまとめと今後の課題である．

と考えられる．すなわち，CTD ルールは，条件が成立するとマ

2. 関連研究・関連システム
近年，クラウドソーシングシステムの開発支援について，多イクロタスクを生成するための ECA ルール (Action 部でマイクロタスクを生成) と，マイクロタスクが実行されるとデータを格納する ECA ルール (Action 部でデータベースに格納) のくの論文で議論されている．これらは，クラウドソーシングの組み合わせと見なすことができるが，CTD ルールはタスクテ

ためのソフトウェアの抽象化の方法が異なる．

ンプレートの自然な拡張として定義していることが特徴である．

(1) 手続き型プログラムとして抽象化：TurKit [5] は，クラウドソーシングのための関数呼び出しと crash-and-rerun モデ
ルを提供する．

3. CTD 抽象化
本節では，本論文で提案する CTD 抽象化について説明する．

(2) MapReduce 風記述として抽象化：CrowdForge [9] は，まず，既存のクラウドソーシングプラットフォームで広く利用

MTurk 上で複雑で相互依存なタスクを行うための MapReduce

されているタスクテンプレートの説明を行い，次に，CTD 抽

風のフレームワークであり，クラウドソーシングシステムを象化の概要を説明する．最後に，CTD 抽象化の詳細について

partition, map, reduce を表すタスクの集合として抽象化する．

説明する．

CrowdForge と本研究との違いは，抽象化の方法とその表現力

3. 1 タスクテンプレートである．詳細は 4. 3 節で議論するが，CTD 抽象化の方が表現

商用クラウドソーシングプラットフォームでは，「タスクテン

力が大きい．

プレート」の形式で，クラウドソーシングを行いたいタスクを(3) 制御フローとデータフローとして抽象化：CrowdLang [10]登録する事が一般的である．例えば，図 1 は，今月何本の映画は，クラウドソーシングシステムで頻出するパターンを構成要を見たか作業者に自由記述で入力してもらうタスクの MTurk

素として制御フロー/データフローの形式で，クラウドソーシンのタスクテンプレートである．MTurk におけるタスクテンプ

グシステムを記述するためのフレームワークである．論文 [10]レートは XML で記述されるが，本質的には，タスクの画面にでは，CrowdLang は抽象レベルの高いコードを記述する目的

表示すべき文章や，その結果の型などが書かれているものがタで使われており，直接実行可能なコードを書くための言語には

スクテンプレートである．QuestionContent 要素には質問文を見えない．

書き，AnswerSpecification 要素には結果の値の型を記述する．

(4) Prolog 風ルールの集合として抽象化：CyLog [7] はクラウ

タスクテンプレートの記述に基づいてタスクプールにタスクがドソーシングシステムを記述するための Prolog 風ルールベー

登録され，ワーカはそのタスクプールに入っているタスクを処図4

図 2 クラウドソーシングの作業例：本に関するタグ付け

Condition Book(id : book id, title, author)
Task

Type

タプルが存在するときにタスクを生成する事を表す．例えば，Entry(tag[“タグ”]:text)

図 3 では，Book リレーションにタプルが存在する場合にタス

Question 「$author」が書いた「$title」という本

クを生成する事を表す．Condition の記述方法などの詳細につに関係するタグを入力してください

Count
Data

いては 3. 3 節で説明する．

3•

T ag(book id, tag)
図3

クラウドソーシングの作業例：飲食店の入力 (タスク 1)

Task はタスクテンプレートの指定である．タスクテン

プレートでは，ワーカへのタスクの指示文と，タスクの結果を本のタグ付けの場合の CTD ルール

格納する変数を指定する．図 3 では，後述するシステム Crapid
での構文に従って記述している．この構文においては，タスク

理することになる．

MTurk では，さらに，変数 (プレースホルダ) を中に記述することによって，このタスクテンプレートの一部を，書き換えたタスクを複数登録することが出来る．この場合，変数中に書かれた値によって複数のタスクが生成され，それらがタスク

本節では，まず CTD 抽象化の構成要素である CTD ルールの直感的な説明を行い，次に複数の CTD ルールを利用したやや複雑なクラウドソーシングシステムの記述を説明する．CTD

ボード入力を示す Entry が指定されている．ここでは，ひな形の引数として，(1) 入力フォーム画面には “タグ” と表示すること，(2) 値の型は text であること，(3) 結果は変数 tag に格納•

3. 2. 1 CTD 抽象化と CTD ルール
CTD 抽象化とは，クラウドソーシングシステムを CTD ルー
ルの集合として記述することである．CTD 抽象化では，リレー
ショナルデータベースの存在を仮定する．次の例で示すように，

CTD ルールからデータベースに格納されているリレーション

Data には，結果を格納するリレーションとその属性を指定する．図 3 では，本の id と入力されたタグを T ag リレー
ションに格納することが記述されている．
以上の様に，CTD ルールは，一般的なタスクテンプレート
記述の一般化になっている．直感的に言うと，CTD ルールは，
次の 4 つのタイプの処理を記述することが可能である．

を参照・更新可能である．

(1) ある条件によってタスクを生成し，タスク処理の結果をデー

例 1. 単純なクラウドソーシングシステム
図 2 のようなタスクを用いて，画面に示された本のタイトルと著者名を見て，関係するタグをワーカに入力してもらうクラ
ウドソーシングシステムを考える．具体的には次のようなもの

タベースに保存する処理．

(2) (Condition 部を省略すると) 無条件でタスクが生成され，タスク処理の結果をデータベースに保存する処理．

(3) (Task 部を省略すると) ある条件が満たされたとき，機械処である．
デ ー タ ベ ー ス に ，本 の 情 報 を 格 納 し た リ レ ー ション

理を行い，その結果をデータベースに保存する処理．

(4) (Condition 部，Task 部を共に省略すると) 無条件で機械処Book(id, title, author) が存在する．
ワーカは，Book リレーションに格納されている本ごと理を行い，その結果をデータベースに保存する処理．

3. 2. 2 より複雑なクラウドソーシング記述にタグを入力する．
その結果はリレーション T ag(book id, tag) に格納する．

2
例 1 のクラウドソーシングシステムは，図 3 の CTD ルール
ひとつだけで記述できる．CTD ルールは，タスクテンプレー
ト (Task) に加えて，そのタスクを生成するための条件 (Con-dition) と，タスクを行った結果として得られるデータ (Data)を合わせた，3 つの要素から構成されたものである．

•「ひな形」とよばれ，データの入力方法などを指定することにすること，が指定されている．Count はタスクの生成数である．

抽象化の定義については，3. 3 節に示す．

•

明するが，Type 項目に書かれるものはタスクテンプレートの図 3 では，タスクテンプレートのひな形として，データのキー

3. 2 CTD 抽象化の概要•

納する変数 (tag) は，Type 項目に書かれている．3.3.2 節で説より，タスクテンプレートの簡単な記述を支援するものである．

プールに登録されることになる．

•の指示文は Question 項目に書かれており，タスクの結果を格

Condition には，タスクテンプレートに書かれたタスクを生成し，タスクプールに登録するための条件を記述する．具
体的には，DB 中のリレーションに，指定された条件を満たす

本節では，複数の CTD ルールによって記述されるより複雑なクラウドソーシングの例として，飲食店の評価を行うクラウ
ドソーシングシステムを考える．作業者が行うタスクは次の 2つである．
タスク 1: 飲食店の入力 (図 4)．何店舗でも入力できる．
タスク 2: 入力された飲食店に対しての 5 段階での評価 (図5)．各店につき 3 人が入力する．
ここでは，タスク 1 の結果として得られるデータをリレーショ
ン Restaurant(id, name) に格納し，タスク 2 の結果として得られるデータをリレーション Rating(restaurant id, value) に格納するとする．このとき，タスク 1 の CTD ルールを図 6 に，並び，ȳ はタスクの結果を格納する変数の並びである．

•

Di は，原子式の並び Q1 (y11 , . . . , y1n1 ), . . . ,Qm (ym1 , . . . , ymnm )．ただし，yjk は Ci にて束縛される変数，ȳ 中の変数，もしくは定数のいずれかである．また，各原子式
図5

クラウドソーシングの作業例：飲食店の評価 (タスク 2)

2

Condition
Task

Type

Entry(name[“飲食店名”]:text)

Question 紹介したい飲食店の名前を入力してくだ
Count
Data

の後ろに/update もしくは/delete をつけることが可能である．

3. 3. 2 CTD ルール構文上の糖衣式を簡潔に書くため，CTD ルールに対していくつかの構文

さい．

上の糖衣を導入する．

*(1) 原子式の属性. Prolog や Datalog と異なり，CTD ルール

Restaurant(name)
図 6 タスク 1. 飲食店の入力の CTD ルールの記述における Condition および Data 部に現れる原子式の記
述では，その引数の記述において明示的に属性名を記述する．
具体的には，次の様に記述する．

Condition Restaurant(id, name)•

引数指定では，“属性名:変数名もしくは値” と記述する．

Task

•

属性を参照しない場合，“属性名：変数名” を省略できる．

•

変数名と属性名が同じ場合，属性名を省略できる．

Type

Choice(value,[1, 2, 3, 4, 5])

Question 飲食店「$name」を 5 段階で評価してく
ださい．

Count
Data

3

Rating(restaurant id : id, value)
図 7 タスク 2. 飲食店の評価の CTD ルール

例えば，スキーマ Restaurant(name, zipcode) を持つリレーションが存在するとき，Restaurant(name:x, zipcode:305)
や Restaurant(name:y) は ，そ の リ レ ー ション に 関 す る
原 子 式 で あ る ．ま た ，Restaurant(name:name, zip:y) はタスク 2 の CTD ルールを図 7 に示す．

Restaurant(name, zip:y) と省略できる．

タスク 1 の Condition 部には，何も指定されていない．この(2) Task 部の記述. Task には頻出パターンが存在するため，

場合，タスクは無条件に生成される．また，Task 部にて Count

繰り返しを避けるためにタスクテンプレートのひな形 Type と属性に*を指定しているが，これは無限回タスクを生成するこCount を導入する．

とを表す．

•

Type には，利用するタスクテンプレートのひな形の名

タスク 2 の Condition 部では，Restaurant に格納されたタ

前と引数を記述する．本論文では，Crapid (5. 節で説明) がサ

プル毎に，タスクを生成する事を指定している．したがって，ポートするタスクテンプレートのひな形の存在を仮定する．ひタスク 1 で入力された飲食店毎にタスク 2 が生成されることにな形を利用する事により，実際のタスクテンプレートは，ひななる．

形の指定と，Question 部に書かれた質問文から導出される．

以上のように，CTD 抽象化では，CTD ルールの集合として•Count にタスクの生成数 N が指定されているときには，

クラウドソーシングシステムを記述する．これらは宣言的な記

CTD ルールを N 個コピーする．

述であり，各タスクはルールの Condition の条件が成立したと

3. 4 CTD 抽象化の計算モデル

きに生成される．クラウドソーシングではワーカによる非同期

CTD 抽象化によるクラウドソーシング記述 d (CTD ルール

な並列作業が一般的であるため，この程度の例であっても，宣の集合) が与えられたとする．その時，d の計算とは，データ

言型記述が手続き型と比較してより自然であることがわかる．

ベースの状態に応じた CTD ルールのボトムアップな評価の事

3. 3 CTD 抽象化の詳細
本節では，まず CTD 抽象化の定義を示し，次に本論文において簡潔にルールを書くための構文上の糖衣について説明する．

3. 3. 1 CTD 抽象化の定義である．具体的には次の様に行われる．

•

デ ー タ ベ ー ス の 値 を 参 照 し ，各 CTD ル ー ル 各(Ci , Ti , Di ) ∈ d の Ci の評価を行う．具体的には，Ci の条
件を満たすような，変数への束縛が存在しうるタプルがデータ

定義 1. プログラムを CTD (Condition-Task-Data) ルール

ベース中に存在するかどうか，Ci 中の左の原子式から順に評

Ri = (Ci , Ti , Di ) の集合で記述することを CTD 抽象化と呼ぶ．

価を行う．

ここで，Ci は Ti を生成するための条件，Ti はタスクの記述，•

Di は Ti の処理結果として得られるデータであり，詳細は下記を行う．

で定義する．

•

Ci は 0 個以上の原子式の並び P1 (x11 , . . . , x1n1 ), . . . ,Pm (xm1 , . . . , xmnm ) である．原子式のいくつかは算術原子式(x11 = 3 等) であっても良い．
•

Ti は，3 つ組み (d, x̄，̄y) もしくは null である．ここで，d はワーカへのタスク指示，x̄ は Ci にて束縛されている変数の

条件部 Ci の原子式が全て成立するものがある場合，次– Ti =| null であれば，タスク Ti を生成し，タスクプールに登録する．

– Ti = null であれば Di に応じてデータベースへのデータの追加，更新 (/update 指定時)，削除 (/delete 指定時) を行う．

•

Ti が処理されれば，Di に応じてデータベースへのデータの追加，更新 (/update 指定時)，削除 (/delete 指定時) を行う．

•

データの変更がある度に，Ci が成立するルールが新たに

要素 1 機械の内部状態を記憶するメモリ

Condition Image(i, size, type : “photo”), Large(size)
Task

Type

Choice(category, [landscape, portrait,
animal, food, etc.])

Question $i のカテゴリを選択して下さい．
Count
Data
図8

要素 2 テープに格納された情報を読み書きするヘッド
要素 3 無限に長いテープ1

要素 1 は，リレーション M achineCurrentStatus(st, head) のLargeP hoto(i, category)st に機械の内部状態を格納することによって表現する．

複数の原子式から成る Condition を持つ CTD ルール

要素 2 は，M achineCurrentStatus(st, head) の head にヘッ
ルール 1

ドの位置を格納することによって表現する．

MachineCurrentStatus(st, head),

要素 3 は，リレーション T ape(pos, sym) とルール 2 によっ

Tape(pos, sym),て表現する．T ape(pos, sym) はテープ上のある位置 pos に記

Condition Rule(st, sym, new_st, new_sym, dire),号 sym が書かれていることを格納する．ルール 2 は無限に長new_pos = pos + dire

いテープを表現するためのルールである．リレーションにあらTask-

かじめ無限個数のタプルを格納することはできないので，ヘッ

MachineCurrentStatus(st, head)/delete,

ドが初めてその位置を指したときに記号が空白であるタプルを

MachineCurrentStatus(

生成することにした．その処理はルール 2 によって表現され，

st:new_st, head:new_pos

Data

テープを無限に伸ばすことを可能にする．この表現によって無)/update,

限に長いテープを用意するのと同等の処理が可能である．

Tape(pos, sym:new_sym)/update

図 9 で は ，ル ー ル 1 に 遷 移 規 則 に 基 づ い た チュー
リ ン グ マ シ ン の 動 作 を 表 現 し て い る ．リ レ ー ション

ルール 2

Condition

MachineCurrentStatus(head)

Rule(st, sym, new st, new sym, dire) は遷移規則を表す．機械の内部状態が st かつ，ヘッドの現在位置の記号が sym のと

Task

-

き，現在位置に記号 new sym を書き込み，内部状態を new stTape(pos:head)/update

Dataに移し，dire 方向にヘッドを移動するという規則である．
図9以上により，CTD 抽象化によってチューリングマシンを記

チューリングマシンを記述する CTD ルール

2

述できるので，CTD 抽象化はチューリング完全である．

4. 2 人とのインタラクションに着目したプログラミング言

生じればその処理を行い，そのようなルールがなくなるまで処語の表現力の尺度

理を続ける．

本論文では，プログラムがどのような人とのインタラクショ

例えば，図 8 に示す CTD ルールでは，まず，Image(i, size, type :”photo”) を評価し，Image 中の type が “photo” であるタプンを記述できるかに着目した，プログラミング言語の表現力のルによって i と size が束縛される．次に, 束縛された size に尺度を提案する．まず，その言語によるプログラムがどのよう

よって Large(size) が成り立つかを確認する．そして，成り立な人とのインタラクションを記述できるかによって，処理可能つ場合には束縛された i に対してカテゴリを選択するタスクがなプログラムのクラスを分類し，これらが有意に異なるクラス

生成され，その処理結果が LargeP hoto に格納される．

である事を示す．
定義 2. 全ての入力者が他者の入力に影響されずデータ入力を

4. CTD 抽象化の表現力行うプログラムのクラスを G1 と呼ぶ．
本節では，CTD 抽象化の表現力について議論する．まず，

G1 に属するプログラムの例として，アンケートを行うプロ

CTD 抽象化による記述がチューリング完全である事を示す．次に，チューリング完全性とは独立したプログラミング言語の表
現力の尺度を導入する．これは，その言語で表現可能な人と計2グラムが挙げられる．例えば，好きな食べ物を聞くプログラム
では入力者は他者の入力に影響されずにデータ入力を行う．

算機のインタラクションに着目したものである．いくつかのク

定義 3. 入力のタイミングが 2 段階に分かれており，後者が何ラスを定義し，各クラスで記述可能なプログラムが有意に異なを入力するかが前者の入力に影響されるようなプログラムのクる事を示す．最後に，CTD 抽象化と他のクラウドソーシング

ラスを G2 と呼ぶ．また，その一般化である入力のタイミング

開発支援ツールの表現力を比較する．

が i 段階 (i > 1) に分かれており，i 段階の入力が i − 1 段階以前の入力に影響されるようなプログラムのクラスを Gi と呼ぶ．

4. 1 CTD 抽象化のチューリング完全性
定理 1. CTD 抽象化はチューリング完全である．

2

証明. 図 9 に CTD 抽象化によるチューリングマシンの記述を示す．
チューリングマシンは，次の 3 つの構成要素から成る．

2
Gi に属するプログラムの例として，前者の入力の検証を含むプログラムが挙げられる．例えば，好きな食べ物を聞くプログ
ラムでは，各入力者によって表記ゆれが発生し，正しい集計が行うのが難しい．その場合，表記ゆれを正すための検証のタス

表1クが必要となり，プログラムはアンケートを取るタスクと検証を行うタスクの 2 段階の入力作業を行うため，G2 に属するもクラウドソーシング開発支援ツールの表現力の比較

記法

チューリング 記述可能な「人とのインタ
完全性

ラクション」のクラス

MTurk 単体

×

G1

CrowdForge

×

のとなる．
定義 4. GN に属するプログラムの繰り返しであり，繰り返し

GN の一部（基本的なもの
は G3 の一部）

回数 (すなわちデータ入力の回数) の最大数を事前に決めることが不可能であって，各入力の内容がそれまでのすべての入力

CrowdDB×

GN の一部に影響されるようなプログラムのクラスを G∗ と呼ぶ．

CTD 抽象化◯G∗ (ゲーム完全)

MTurk を手続き型 ◯G∗ (ゲーム完全)

2

G∗ の例として，リレー小説を作るプログラムが挙げられる．

言語で書かれた外部

リレー小説を作るプログラムでは各入力者が交代で文章を入力

プログラムから呼びする．このタスクは事前のタスクの結果に影響されるものであ出す

り，また，いつ終了するかは事前にわからない．
以上の定義をしたときに成り立つ 2 つの定理とその証明を次定理 2. Gi+1 は Gi より真に大きいクラスである．

チューリング完全であるため，条件 2 を満たす

22

証明. 定義より，Gi ⊂=Gi+1 ．Gi に属する任意のプログラム Piを考えた時，Pi に結果を検証するタスクを加えたプログラム

Pi+1 は Gi+1 に属する．Pi+1 ∈/ Gi なので Gi ⊂ Gi+1 ．

– GN であるプログラムを再帰で呼び出せる．
•

に示す．

2

4. 3 表現力の比較
本節では，CTD 抽象化と他のクラウドソーシング開発支援
ツールの表現力を比較する (表 1)．MTurk のように人とのイン
タラクションを一回だけ行うものは G1 である．また，Crowd-

定理 3. ある定数 N が与えられた時，G∗ は GN より真に大きForge のように Partition, Map, Reduce といった 3 回のイン

2

タラクションの場合は G3 である．CrowdForge では Partition,

いクラスである．

証明. ある有名人 A さんの似顔絵を入力するプログラム PA を考える．PA は，次のステップで実行される．

再帰を表現できないので，その場合には GN となる．我々が提案する CTD 抽象化は CTD ルールにより再帰を表現できるの(1) 誰かが元となる似顔絵を描く

で，G∗ クラスを表現可能である．

(2) 他の誰かがより似るように修正する(3) 似顔絵が十分似ていると判断されるまで繰り返し，他のCrowdForge はチューリング完全ではない．MTurk を手続き型言語で書かれた外部プログラムから呼び出せば，チューリン

誰かがより似るように修正する

グ完全かつ G∗ となり，CTD 抽象化と同じ表現力を持つことが(4) 似顔絵が十分似ていると判断され，終了する
PA は何段階の入力で終了するか決定できず，G∗ に属するが，GN には属しない．

Map, Reduce を複数組み合わせることが出来るが，ループや2

最後に，プログラミング言語の表現力のクラスを次の様に定義する．
定義 5. あるプログラミング言語が次の条件を共に満たすとき，出来る．CrowdDB は SQL をベースとした言語を用いるためチューリング完全でなく，クラスは GN である．

5. CTD 抽象化によるクラウドソーシングシス
テム開発ツール Crapid
本節では，我々が実装した，CTD 抽象化によるクラウドソー
シング記述から実行可能なコードを出力する Crapid について

その言語はゲーム完全 (Game Complete) である．

•

条件 1: クラス G∗ のインタラクションを表現可能である．

説明する．まず概要を説明し，次に，3. 2. 2 節で紹介したクラ•

条件 2:人に対する報酬を表す値を，入力されたデータのウドソーシングシステムの例を用いて，Crapid の使い方を説明する．最後に，現在の Crapid の実装の制限について議論する．

並びからチューリングマシンで計算可能である．

2

5. 1 Crapid の概要
Crapid は CTD ルールの集合を入力として受け付け，実行可

ゲーム完全は，ゲーム理論における，長さ不定の逐次ゲームのうち，チューリングマシンで表現可能なものを表すクラスである．ゲーム完全であるためには，プログラミング言語が，クラス G∗ のインタラクションを表現可能であること，および，チューリング完全である事の両方が必要である．
定理 4. CTD 抽象化はゲーム完全である．
証明. CTD 抽象化は次のことから G∗ を記述可能である．

•

次の理由により条件 1 を満たす

– GN であるプログラムを全て書くことができる．

能な CyLog [7] のコードを生成する．Crapid では，CTD ルー
ルを直接テキストで入力させるのではなく，選択したタスクテ
ンプレートのひな形に応じて，HTML フォームベースのイン
ターフェースを提供する．

Crapid が現在サポートするタスクテンプレートのひな形を2

表 2 に示す．CTD ルールを記述するときにタスクテンプレー
トのひな形を選択すると，各ひな形に応じた引数を記述するための HTML フォームが現れる．

5. 2 Crapid の利用方法
Crapid は次の 3 つのステップに従ってシステムを生成する．

表 2 Crapid が現在サポートするタスクテンプレートのひな形

Entry

引数で指定された型のデータの入力．引数は「属性
名 [“画面に表示する名前”]:データの型」という形式で指定する．カンマ区切りで複数指定可能である．

Choice引数で指定された選択肢からの選択．引数は「属性名, [値 1, 値 2, …]」という形式で 1 つ指定する．

Decision

YES, NO の判断．引数は YES, NO の結果を格納する属性名を 1 つ指定する．

Comparison 値の比較．引数は「比較する属性名 1[画面に表示する属性名], 比較する属性名 2[画面に表示する属性名], 結果を格納する属性名」という形式で指定する．

(1) リレーションの登録(2) CTD ルールの登録(3) コードの表示
3. 2. 2 節の飲食店の評価を行う例を用いて，3 つのステップについて説明する．

5. 2. 1 リレーションの登録

図 10 リレーションの登録

このステップでは，ユーザは CTD ルール中で使用するリレー
ションの登録を行う．リレーションの登録にはリレーション名とその属性を登録する．属性には，必須項目として属性名，オ
プション項目としてキー，auto increment の設定項目がある．
例では，レストランを格納するリレーション Restaurant(id, name)と評価を格納するリレーション Rating(restaurant id, value)
を 登 録 す る ．登 録 画 面 を 図 10 に 示 す．ユ ー ザ は ，ま ず，Restaurant の登録のために，「リレーション名」に Restaurant, 「属性名」に id, name を入力する．id は主キーかつauto increment なので，それぞれのチェックボックスにチェッ
クを入れ，「作成」ボタンを押す．次に，Rating の登録のために，「リレーション名」に Rating, 「属性名」に restaurant id,

value を入力し，「作成」ボタンを押す．属性を複数入力する際には「属性の追加」ボタンをクリックする．

5. 2. 2 CTD ルールの登録
このステップでは，ユーザはシステムを記述する CTD ルー

図 11 CTD ルールの登録

ルの登録を行う．例では，図 6 および図 7 に示した CTD ルー
ルを登録する．登録画面を図 11 に示す．ユーザはまず，レス示される．Crapid によって生成された CyLog コードは，クラトランの入力のタスクを表す CTD ルールを登録する．Type

ウドソーシングプラットフォーム Crowd4U [8] で実行可能でのセレクトボックスでは「Entry」を選択し，テキストボック

ある．

スに「name[”飲食店名”]:text」を入力する．そして，Question

5. 3 現在の Crapid 実装における制限に「紹介したい飲食店の名前を入力してください」，Count に

現在，Crapid では，各タスクテンプレート毎にワーカへの「*」，Data に「Restaurant(name)」を入力し，最後に追加ボ

固定報酬 (ポイント) を指定できる．一般には報酬は，クラウド

タンを押す．次に，評価のタスクを表す CTD ルールを登録す

ソーシングシステムを構成する要素として重要な要素であり，る．Condition に「Restaurant(id, name)」を入力する．Type

入力されたデータなどに応じた報酬の変更が重要であると考えのセレクトボックスでは「Entry」を選択し，テキストボック

られるが，Crapid における，より柔軟な報酬の指定は今後のスに「value, [1,2,3,4,5]」を入力する．そして，Count に「3」，課題である．

Data に「Rating(restaurant id:id, value)」を入力し，最後に追加ボタンを押す．

5. 2. 3 コードの表示

6. まとめと今後の課題
本論文は，宣言的記述によるクラウドソーシングシステムのこのステップでは，CTD ルールの集合から生成された Cy-

開発を支援するため，CTD 抽象化およびそれに基づく開発支Log [7] のコードを表示する．例では図 12 に示したコードが表

援ツール Crapid の提案を行った．CTD 抽象化は，クラウド

ソーシングプラットフォームにおいてよく利用されるタスクテ
ンプレートを一般化したものであり，十分な記述力を持つ．また，Crapid は様々なタスクテンプレートのひな形を提供する
ことにより，効率よいクラウドソーシングシステム開発を支援する．
今後の課題としては，クラウドソーシングの頻出パターンを考慮したタスクテンプレートのひな形ライブラリの構築が挙げられる．また，CTD 抽象化によって記述されたコードの最適化や，データクオリティなどの要件を考慮したコードの変形等も今後の課題である．

謝辞

本論文の一部は JST さきがけ「情報環境と人」による．
文

図 12

生成された CyLog コード

献[1] Doan AnHai, Ramakrishnan Raghu, Halevy Alon Y..
“Crowdsourcing systems on the World-Wide Web. Commun.ACM. 2011, vol. 54, no. 4, p. 86-96.
[2] gwap.com. “ESP Game”.
http://www.gwap.com/gwap/gamesPreview/espgame/[3] reCAPTCHA. “What is reCAPTCHA?”.
http://recaptcha.net/learnmore.html[4] Amazon Mechanical Turk,
https://www.mturk.com/.
[5] Little,G.,Chilton, L.B., Goldman, M.,and Miller, R.C.
“Turkit: human computation algorithms on mechanicalturk”. In Proceedings of UIST (2010), ACM, New York,57-66.
[6] Franklin Michael J., Kossmann Donald, Kraska Tim,
Ramesh Sukriti, Xin Reynold.. “CrowdDB: answering
queries with crowdsourcing”. SIGMOD Conference. 2011,
p. 61-72.
[7] Atsuyuki Morishima, Norihide Shinagawa, Shoji Mochizuki.
“The Power of Integrated Abstraction for Data-centric Human/MachineCurrentStatus Computations.” First International Workshop on Searching and Integrating New Web
Data Sources (VLDS2011) Co-located with VLDB 2011, pp.
5-9.
[8] Atsuyuki Morishima, Norihide Shinagawa, Tomomi Mitsuishi, Hideto Aoki, Shun Fukusumi. “CyLog/Crowd4U:
A Declarative Platform for Complex Data-centric Crowdsourcing”. PVLDB 5(12): 1918-1921 (2012).
[9] A. Kittur, B. Smus, and R. E. Kraut, “CrowdForge: Crowdsourcing Complex Work”, Technical Report. CMUHCII-11,
2011.
[10] Patrick Minder and Abraham Bernstein.. “A Programming
Language for the Systematic Exploration of Human Computation Systems”, Fourth International Conference on Social
Informatics (SocInfo 2012), 2012.