DEIM Forum 2016 D6-1

分類マイクロタスクにおけるタスク順序制御手法
根本千代之介 †田島敬史††

森嶋 厚行†††† 筑波大学大学院図書館情報メディア研究科 〒 305–8577 茨城県つくば市天王台 1 丁目 1 番 1 号†† 京都大学大学院情報学研究科 〒 606–8501 京都市左京区吉田本町††† 筑波大学 知的コミュニティ研究センター 〒 305–8550 茨城県つくば市春日 1 丁目 2 番地 1 号
E-mail: †s1521637@u.tsukuba.ac.jp, ††tajima@i.kyoto-u.ac.jp, †††mori@slis.tsukuba.ac.jp
あらましクラウドソーシングにおける典型的なタスクの一つにデータの分類がある．一般に，クラウドソーシング

では多くのワーカの存在を仮定する事が多いものの，タスク数が非常に多い場合など，実際には，必ずしも短時間で全てのタスクが処理されるとは限らない．本論文では，災害時に置ける災害箇所の発見など，あるクラスのデータを発見するケースに関して，できるだけ早く多くのデータを発見するためのタスク順序の制御手法について議論する．具体的には統計情報を利用した方法と機械学習を用いた方法を比較した. その結果, フィルタ数が多いとき, 機械学習を用いた手法よりも統計情報を利用した手法の方が再現率の立ち上がりにおいて優れている場合があることを発見した.
キーワード

クラウドソーシング, 分類, タスク割り当て制御

1. は じ め に
計算機だけでは解決が困難な問題に対するアプローチとして,クラウドソーシングが多くの分野で用いられている.
クラウドソーシングの一形態として, 短時間で処理可能なタ
スク (マイクロタスク）を用いるマイクロタスク型クラウドソー
シングがある．マイクロタスクの例を図 1 に示す. 図 1 は航空
写真に写っている家屋が倒壊しているか否かを判別するマイク
ロタスクである. このような，分類を行うためのタスクを本論
文では分類タスクと呼ぶ．

図1

マイクロタスクの例

本論文では，大量の分類タスクに対して，十分な数のワーカが存在せず，タスクを順次処理していかなければならないような状況において，どのような順序でタスクを処理すべきかという問題について議論する. そのような問題が重要な応用はいく
つか存在する．そのような例を次に示す．(例 1) 被災地の救援を目的として，航空写真群に写っている被災家屋を見つけたい

2. フィルタを利用し，次のタスクを決定

1.タスクの処理結果をもとにフィルタを選別
タスク

場合, 最終的には全ての被災家屋を発見したいとしても, でき

タスク

タスク

タスク

タスクの割り当て順

るだけ早く多くの被災している箇所を発見したい．(例 2) デー

3. 次のタスクを割り当て

タセットの中から，条件を見たす少数の例を発見できればよく,
かつ, データセットの量が膨大である場合には，ワーカに支払
う報酬の合計額を少なくするために, できるだけ少ないタスク

図 2 フィルタを利用した, タスク処理順序決定手法

でそれらの例を発見したい．
タスクの処理順序を決定するために，各タスクが扱うデータして処理する．

の特徴に関するヒューリスティクスを利用するというアプロー

しかし, どのフィルタが効果的であるかどうかはデータセッチが考えられる．これは，具体的には特徴量に関する真偽値をトの性質に依存する. 例えば, 土砂崩れの被災地と津波の被災返す判定という形で表現されるため，本稿では特徴量フィルタ

地では, 同じ図 1 のような被災家屋発見タスクでも有効な特徴(以下, フィルタとよぶことがある) と呼ぶ．例えば, 土砂崩れ

量フィルタは異なると予想される. このように, どのフィルタの被災地の航空写真群から多数の倒壊家屋を発見する場合, 茶を適用すべきかはデータセットの性質に応じて判断する必要が色がかった箇所から優先してタスクを処理することにより, よある. しかし, あらかじめどのフィルタが有効であるかどうか

り少ないタスク数で多数の倒壊家屋を発見できると予想される.

を調査する作業は必ずしも容易ではなく, その作業により, タス

この例では, 「画像が茶色がかっているれば真」というフィルクの依頼開始が遅れる可能性がある.

タを利用し, その条件にマッチしたデータを持つタスクを優先そこで, 本稿では, あらかじめ大量のフィルタを用意し，その得るためのものである．MCS に関する研究は複数のアプロー

中から効果的なものを動的に取捨選択しながら適用しタスクのチで行われているが，本手法に最も関連するアプローチとし順序を決定する手法について述べる. 図 2 にこの手法の概要をて Classifier Selection がある．Classifier Selection は複数の示す. 近年, クラウドソーシングを用いて有効そうな特徴量をClassifier から，優れている Classifier を選ぶ問題であり, 我々

発見する研究が行われており [7] [4], このような手段で入手したが複数のフィルタから, 優れたフィルタを選ぶのと本質的には大量のフィルタを利用するというアプローチは必ずしも非現実

同じ構造を持つ.

的ではない. 具体的には，統計情報を利用して取捨選択を行う

しかし，本研究における「優れた特徴量フィルタ」と, 一般

手法と，既存の機械学習アルゴリズムを用いて取捨選択をするに Classifier Selection における「優れた Classifier」では選択手法について述べ, それらを比較し，それぞれの特性を明らかの基準が異なる．Classifier Selection が選別の尺度として主ににする．

正確率 (Accuracy) を用いるのに対し，我々は，分類タスクに

本論文の貢献は次のとおりである．

おいて早く正例を見つけることを問題にしているため，フィル(1) クラウドソーシングの中間結果に注目した研究．これま

タの選別に適合率 (Precision) を用いる. そのため，フィルタで，クラウドソーシング結果の品質に関しては, 個々のタスクの選別では, フィルタにマッチするデータのみを収集すれば十の結果や, 最終的な結果の品質を対象としていた. しかし, 一般

分であり, フィルタにマッチしないデータについては考慮するにクラウドソーシングは全タスクの終了までに時間がかかるた必要が無い. 例えば, 赤いデータにマッチするフィルタと黄色め, 中間時点でのデータ品質も重要と考えられる. 本研究は中いデータにマッチするフィルタの間で適合率の比較を行う場合,

間時点でのデータ品質に着目して, タスク割り当て順の制御を

赤いデータと黄色いデータだけ収集すればよい.

行うものである. また, これまで情報検索の分野において，検また, 与えられたデータセットに対して正しそうな Classifier

索のランキングの評価などにおいて，上位に望ましい結果が来を予測して選択するような Classifier Selection は Dynamic

ることを目的とする研究が数多く行われてきた. 本研究は，そClassifier Selection と呼ばれている．Dynamic Classifier Se-のような視点を，クラウドソーシングにおけるタスクの割り当

lection の研究としては，[5] がある. [5] はトレーニング済みのて順制御に導入しようとするものである．

データから分類するデータに近いものをいくつか集め，それに(2) 実データを用いた複数手法の比較．本論文では，実デー

対する正確度を用いて，Classifier を選別する手法を提案してタを用いて，統計情報に基づく手法と機械学習に基づく手法のいる．Dynamic Classifier Selection は全体の候補からデータ比較を行った．その結果, 大量のフィルタが存在する場合には，セットに合わせて適したものを選ぶという点で本研究と共通す

次元の呪いによって機械学習の学習に時間がかかるため，統計る．しかし，Dynamic Classifier Selection は Classifier の選別

情報に基づく手法が，再現率の立ち上げにおいて優れている場と適用の 2 フェーズに分かれているのに対し，本手法はフィル合があることを発見した．

タの選別と適用を 1 フェーズで行うものである.

なお, 本研究では, ワーカはタスクに対し必ず正しい回答をす

群衆によるフィルタの提案と作成 群衆にフィルタの提案や作成

ると仮定する. 実際, これは現実的ではないが, タスク結果の品を行わせた研究として Cheng らの研究 [4] や, Zou らの研究 [7]

質向上に関する研究はすでに行われていて, それらで述べられがある. これらの研究は, 人間に判定の手がかりとなる特徴のている手法を用いれば, 比較的高い確率で正しい回答が得られ発見と特徴量の付与を行わせ, 人間が作成した特徴量と機械的る. そのため, 本研究では, タスク結果の品質については議論のに作成した特徴量を組み合わせた分類器を作成するものである.

対象としない.

これらの研究では, 特徴の発見とラベル付けを人間に行わせて本稿の構成は以下のようになる. 第 2. 節では関連研究についいる. これは本研究におけるフィルタの発見と作成に相当する.

て述べる. 第 3. 節ではヒューリスティクスのモデル化に用いる

これらの研究ではフィルタの発見と作成を不特定多数のワーフィルタについて述べる. 第 4. 節では, 本論文で扱う問題につカに行わせているのに対し, 本研究ではどちらもリクエスタ (タいて形式的に述べる. 第 5. 節では統計情報を用いたタスク割り

スクを作成する人) 自身が機械的な手法を用いて行う. したがっ当てアルゴリズムについて説明する. 第 6. 節では機械学習を利て, 本研究は, 機械的に導出できるようなフィルタを発見する必用したタスク割り当てアルゴリズムについて説明する. 第 7. 節

要があるという点で, これらの研究と比べ適用範囲が狭い. しでは実験とその結果について述べる. 第 8. 節はまとめである.

かし, そのかわり, 人間に特徴量を付与させることを必要とし

2. 関 連 研 究
本論文と同様の課題設定での研究 [8] と比較して，本論文はない.

3. 特徴量フィルタ

統計情報に基づく手法のアルゴリズムが異なり，また，既存の

本節では, ヒューリスティクスのモデル化に使用する特徴量

機械学習アルゴリズムとの比較を行っているところに新規性がフィルタを定義する．なお，以降では単に「フィルタ」と呼ぶある．その他の関連研究は次の通りである．

ことがある．

Multiple Classifier System (MCS) 本手法におけるフィ

特徴量フィルタ fi とは， データ dj が性質 pi を満たせば 1

ルタの選別と関連する研究として，MCS [6] がある．MCS に関を, そうでなければ 0 を返す関数である. 例えば，茶色い画像する研究は，複数の Classifier を用いて，よりよい分類結果をにマッチするフィルタ fbrown (dj ) は, dj が茶色い画像データであれば 1 を, そうでなければ 0 を返す. 形式的には次のように定義される．

入力 ある時点 k までに行われたタスク列 Tk′ と，Tk′ に含まれる分類タスクを処理した結果 Resultsk ，および特徴量フィル

定義 3.1 (特徴量フィルタ). D = {d1 , . . . , dn } をデータ集合とし，pi を判定したい性質とする．このとき，あるデータ dj ∈ D
が性質 pi を満たすか否かを判定する特徴量フィルタは，関数

fi : D → {1, 0} である．ただし，1fi (dj ) =0

if dj satisfies pi
if dj dosen′ t satisfy pi

空フィルタ femp は全てのデータにマッチする特徴量フィル
タであり，次のように定義される．
定義 3.2 (空フィルタ). 空フィルタ femp : D → {1, 0} は次である．

(∀di ∈ D) femp (di ) = 1
次に，複数の特徴量フィルタを用いて，特徴量ベクトルを定

タの集合 Fall = {f1 , . . . , fm }．
′出力 Tk+1= Tk + [tp ]．ただし，tp は，特徴量フィルタを用

いて，T − Tk′ から選ばれる．
出力される T ′ の善し悪しは，いかに少ないタスク数で多くの
正例 (クラス c に属するデータ) を発見できたかで評価される．
以降では，統計情報を利用したアルゴリズムと，既存の機械学習手法を利用したアルゴリズムを説明する．これらは，上記(3) において，tp を選ぶために利用する特徴量フィルタをどう選別するかの部分が異なる．

5. 統計情報を利用したタスク割り当てアルゴリ
ズム
統計情報を利用した手法では, 時点 k までのタスク処理結果に関する特徴量フィルタの統計情報をもとに，tp を選択するために利用するフィルタの選別を行う.

5. 1 概義する．

要

統計情報を利用した手法のアルゴリズム SFSelect (Statistics
定義 3.3 (特徴量ベクトル). 性質の列 p1 . . . pm に関するデー

based Filter Select) を Algorithm 1 に示す. SFSelect の入力

タ di ∈ D の特徴ベクトル xi とは次である．

はタスク集合 T とフィルタ集合 Fall であり, 出力はタスク処理

xi = (f1 (di ), f2 (di ), · · · , fm (di ))4. 本論文で扱う問題

結果の列 Results である.
このアルゴリズムにおけるフィルタの選別手法は，Backward

stepwise selection の一種である．具体的には，Fall 中のフィルタをまず Factive というフィルタ集合に所属させ，他のフィル

本論文で扱う，分類タスクの割当て順序制御の問題は次のタと比べて相対的に有効でないと一時的に判断されたフィルタ通りである．まず，データ集合 D = {d1 , d2 . . . , dn } 中の各を順次 Finactive に移動させる．また，マッチするデータを全てデータが，クラス c に属するか否か分類するためのタスク集合

見つけたフィルタは Ff inish というフィルタ集合に移動させる

T = {t1 , t2 , . . . , tn } を用意する．ここで，各 ti は di がクラス

(図 3). Ff inish の詳細は, 5. 2 節で説明する.

c に所属するか否か分類するためのタスクである (図 1)．
このとき，本論文における分類タスクの割当て順序制御とは，

本アルゴリズムは次のように動作する．まず，Fall 中のフィルタを全て Factive に所属させ, Finactive , Ff inish は空にする

タスクの処理順序を表す列 T ′ を動的に作る事である．ここで，(1 行目, 2 行目) . つまり, 全てのフィルタが有効なものである

T ′ は T 中の全てのタスクをそれぞれ一度含む列である．例えとみなす.

ば，T = {t1 , t2 , t3 } の時，T ′ = [t2 , t1 , t3 ] などが考えられる．
′′

そして未処理のタスクのうち, Factive に属するフィルタに最T を動的に作るとは，T を先頭から順に作る際に，時点 k

も多くマッチするデータを持つタスクを選ぶ (5 行目) . 5 行目のまでに割り当てたタスク列 Tk′ (最終的な T ′ の部分列) のタスク

getMaxMatchTasks 関数は, 未処理のタスク集合から, Factive

結果を見て，次のタスク tp を決定すると言う事である (図 2)．

に属するフィルタに最も多くマッチするタスクの集合を返す関また，本論文では，次のタスクの決定の際に，与えられた (複数である. マッチするフィルタの数が多いデータを持つタスク数の) 特徴量フィルタを利用する．したがって，本論文で扱うを優先して割り当てるのは, マッチするフィルタが多いほど, 正

手法は，次の手順になる．

例である確率が高いと期待するためである. getMaxMatchTask（ 1 ） 入力として，データ集合 D = {d1 , . . . , dn }，タスク集

関数から返された結果からワーカに割り当てるタスクをランダ

合 T , および特徴量フィルタの集合 Fall = {f1 , . . . , fm } をとる．

ムに 1 つ選択する (11 行目) . そして選択されたタスクをワー（2）

時点 0 でのタスク列を T0′ = [] とする．

カに割り当て, 回答を得る (12 行目) .

（ 3 ） タスクを行ってもらいながら，時点 k + 1 のタスク列

ワーカから回答が得られたら, その結果を Results に加え′Tk+1を順次計算する．
（ 4 ） T ′ (= Tn′ ) と，T ′ に含まれる分類タスクを処理した結(13 行目) , タスク処理結果保存テーブル RTable の内容を更新

果の列 Results を出力する．

フィルタの選別を行い, 再びタスクの処理を開始する.

′
上記 (3) において Tk+1
を求める際の入出力は次の通りである．

する (14 行目). RTable の例を表 1 に示す. RTable を利用して

5. 2 フィルタの選別
本節ではフィルタの選別方法 (15 行目〜21 行目) について説明する. フィルタの選別は Factive に属するフィルタに対して,

Algorithm 1 SFSelectフィルタの性能を比較

Input : T, Fall
Output : Results

Factive
適合率の劣ったフィルタを
Finactiveに移す

マッチするタスクがなくなったフィルタをFfinishへ移す

1: Factive ⇐ Fall
2: Finactive ⇐ ∅, Ff inish ⇐ ∅3: Results ⇐ []4: while |Results| != |T| do
5:candidateTasks ⇐ getMaxMatchTasks(T, Factive )6:

if candidateTasks.empty? then7:

Ff inish ⇐ Ff inish ∪ Factive

8:

Factive ⇐ Finactive

9:

next

10:

end if負例

11:task ⇐ getRandom(candidateTasks)

10

12:

result ⇐ ask(task) //タスクをワーカに割り当て, 回答を入手

1

13:

Results.add(result)14:

updateTable(RTable, Results)

15:

for all f1 , f2 s.t. f1 ∈ Factive ∧ f2 ∈ Factive ∧ f1 =| f2 doFinactive

Ffinish図 3 3 つのフィルタ集合とフィルタ選別
表 1 RTable の例
フィルタ名 正例

f1
f2

1
8

f3

4

4

f4

5

2

16:

/*フィルタの性能をペアワイズで比較*/

17:

if existSignificantDiﬀ(RTable, f 1, f 2) thenRTable を用いて行う (15 行目) . そして選別の結果, 取り除く18:

inferiorF ⇐ getInferiorF(f1 , f2 )フィルタを Factive から Finactive に移す. この動作は図 3 の左

19:

Factive .delete(inferiorF), Finactive .add(inferiorF)側に示されている.

20:

end if21:

end for

具体的には, Factive に属する 2 つのフィルタの組み合わせ全てについて, 適合率に有意差があるか検定を行う. 17 行目の22: end while

existSignificantDiﬀ 関数は, 与えられた 2 つのフィルタについて検定を行い, 2 つのフィルタの適合率に有意差が有るか否かを況を指す.

返す関数である. この関数は RTable の値をもとに検定を行う.

この場合, Factive 中のフィルタの適用を終了し, Finactive に

RTable には各フィルタにマッチしたタスクに関して, 正例の個属するフィルタを対象に選別を開始する. つまり, 残っている数と負例の個数が保存されており, これを用いてフィルタの適フィルタ集合を対象に, フィルタの選別を再び始める. 具体的合率を計算する. 検定の結果, 2 つのフィルタの適合率に有意差には, まず, 図 3 の右側のように, Factive 中のフィルタを全てが存在するとされた場合, 適合率が劣っている方のフィルタを

Ff inish へと移す (7 行目) . Ff inish は, 未処理のタスクのいず

Factive から Finactive に移す (18 行目, 19 行目). つまり, 適合

れにもマッチしないフィルタの集合である. そして, Finactive率が有意に劣ったフィルタを, タスク処理順の変更に用いるフィ

中のフィルタを全て Factive に移し (8 行目) , 再びタスクの処

ルタの集合 (Factive ) から取り除く. 18 行目の getInferiorF 関理とフィルタの選別を開始する.

数は 2 つのフィルタを引数としてとり, 適合率が低い方のフィ

5. 4 SFSelect の拡張

ルタを返す関数である.

SFSelect を拡張することにより, 「他の結果に依存するフィ

仮説検定の手法としては, フィッシャーの正確確率検定とカイルタ」も扱えるようになる. 「他の結果に依存するフィルタ」

二乗検定を用い, Precision(f1 ) = Precision(f2 ) という帰無仮とは, 例えば, 図 1 のような被災家屋判定タスクの場合, 「壊れ説を検定する. フィッシャーの正確確率検定は標本数が少ないている家屋が周囲 100m 以内に存在する」といったものである.

場合にも正確な検定が行えるが, 標本数が大きくなると計算量

この例の場合, 他のタスクが処理され, 壊れている家屋が発見さが膨大になることが知られている. そのため本手法では, 標本れた場合, その家屋の周囲 100m 以内にある画像がこのフィル

数が少ない場合にはフィッシャーの正確確率検定を用い, 多い

タにマッチするようになる. すなわち, 他のタスクの処理結果場合にはカイ二乗検定を用いる.

によって, あるデータに対するフィルタの出力が変化する.

5. 3 割り当てるタスクがない場合の処理
SFSelect では, ワーカに割り当てるタスクが存在しない場合「他の結果に依存するフィルタ」を扱えるよう SFSelect を拡張するには, RTable を更新するタイミングを増やすことと,が生じる. その場合の処理 (6 行目から 9 行目) について説明

一度 Ff inish に所属させたフィルタを Factive へ戻すことが必要する.

となるが, ここではその詳細は省略する. 詳しくは権守らの論

まず, 割り当てるタスクが存在しないとは, Factive 中のフィルタにマッチするデータをもつ, 未処理のタスクが存在しないということである. すなわち, (現時点において) 有効なフィル
タにマッチするデータを持つタスクを全て処理し終えている状

文 [8] を参照されたい.

6. 機械学習を用いたタスク割り当てアルゴリ
ズム
本節では, 機械学習を用いたタスク割り当てアルゴリズム MLについて説明する. このアルゴリズムでは各フィルタを特徴量とみなし, タスクの処理結果をもとに各フィルタに重みづけを

Algorithm 2 ML
Input : T, Fall
Output : Results
1: TrainingData ⇐ ∅2: Results ⇐ ∅3: while |Results| != |T| do
4:

行う. そしてフィルタの重みをもとに各タスクのスコアを計算

candidateTasks ⇐ Classifier.getMaxScoreTask(tasks)

5:

task ⇐ getRandom(candidateTasks)

し, スコアが最も高いタスクをワーカに割り当てる.

6:

result ⇐ ask(task) //タスクをワーカに割り当て, 回答を入手

機械学習を用いたタスク割り当てアルゴリズム ML を Algo-

7:

Results.add(result)

rithm2 に示す. このアルゴリズムの入力は, 統計情報を利用し

8:

TrainingData.add(result)た手法のアルゴリズムと同じく, タスク集合 T とフィルタ集合

9:

Classifier.learn(results, Fall ) //現在までのタスク処理結果をFall である. 出力はタスク処理結果の列 Results である.
ML では, ワーカからの回答を訓練データと見なし, 訓練デー

利用し再学習10: end while

タをもとに学習を行う. そして学習結果をもとに各フィルタに対し重みづけを行う (8 行目). 訓練データは第 3. 節で述べた特7. シミュレーション

徴ベクトルと同じ形式をとり, ワーカからの回答を正解ラベルとして持つ. そして得られた重みを用いて未処理のタスク全て

本節では, SFSelect と ML の差異を調査するために行ったシのスコアを計算し, スコアが最も高いタスクをワーカに割り当

ミュレーションについて述べる. シミュレーションでは 2 種類

てる (4 行目, 5 行目, 6 行目). スコアが高いほど, 正例である確のデータを利用した. 1 つは E メールのスパム判定データであ率が高いとする. 4 行目の getMaxScoreTask 関数は未処理のり, もう 1 つは台風被害の実データである. E メールのデータ

タスク全てについてスコアを計算し, スコアが最も高いタスクについては, フィルタ数の影響を調査するため, フィルタ数がの集合を返す関数である. なお, スコアが最も高いタスクが複100 の場合と 200 の場合それぞれについてシミュレーションを数存在した場合, それらのタスクからワーカに割り当てるタス

行った.

クをランダムに 1 つ選択する (5 行目) .
ワーカから新たな回答が得られると (6 行目), そのデータを訓練データに加え (8 行目) 再学習を行い, 各フィルタの重みをなお, SFSelect と ML はいずれも結果がランダムな要素の影響を受けるため, それぞれ 3 回実験を行い, 3 回のデータの平均を求めた.

更新する (9 行目). 以上のようなステップを全てのタスクを処

7. 1 問題 1. E メールのスパム判定

理するまで繰り返す.

7. 1. 1 シミュレーション設定

疑似コード中の Classifier に対応する分類器としてはロジス

CS MINING GROUP [1] にある, 多数のメールとそれらがティック回帰分析を用いた. Support Vector Machine 等の別のスパムであるか否かを判定したデータを用いた. データの件数分類器を用いることも可能ではあったが, 今回は簡単のため, ロは 4,327 件であり, そのうちの約 31.8% (1,378 件) がスパムとジスティック回帰分析を用いた. 具体的には統計解析ソフト R判定されている.
なお, フィルタを選別する際, 有意水準 0.05 の両側検定をの glm 関数を用いた.

glm 関数を用いると, 各タスクのスコアは次のように計算で行った.

きる. すなわち, まず, glm 関数に引数として訓練データの集

7. 1. 2 用いたフィルタ

合をわたすと, 各フィルタの重みが返される. このとき, ある空フィルタも含め, 100 個または 200 個のフィルタを用いた.

タスク t において使用するデータを d とするとき, t のスコア

用いたフィルタの一部を表 2 に示す. 表 2 に示した以外のフィscore(t) は以下のように計算される.

ルタもこの 5 つのフィルタと同様のものである. ただし, 単語の部分をそれぞれ変更している.

score(t) = w1 f1 (d) + w2 f2 (d) + · · · + wm fm (d),wi ∈ R, fi (d) ∈ {0, 1}

フィルタの作成に用いる単語としては, GSL (General Service

List) [2] の単語を頻度順に並べた際の上位の語を用いた. ただ
し, CoreNLP のストップワードリスト [3] を用いて事前にストッ

ここで, wi はフィルタ fi の重みであり, 実数である. 例えば,

プワードを除去した. フィルタ数が 100 の場合には上位 99 語

フィルタ数が 3 でそれらの重みが (w1 , w2 , w3 ) = (2, 1, 1) であり,を, フィルタ数が 200 の場合には上位 199 語を用いてフィルタあるタスク t に対応するデータ d ついて (f1 (d), f2 (d), f3 (d)) =を作成した.

(1, 0, 1) であるとき, t のスコアはscore(t) = w1 f1 (d) + w2 f2 (d) + w3 d3 (d) = 2∗1+1∗0+1∗1 = 3となる

7. 1. 3 シミュレーション結果
図 4, 図 5, 図 6, 図 7 にシミュレーション結果を示す. これらの図は横軸が処理されたタスク数, 縦軸が正例に対する再現率であり, タスク数の増加に伴う再現率の推移を示している. 図

4, 図 5 はフィルタ数が 100 の場合の結果であり, 図 6, 図 7 は

表 2 問題 (1) のシミュレーションに用いるフィルタ (一部)
適合率

再現率

femp

（空フィルタ）

31.8%

100%

f1

本文に「church」が含まれている 85.1%

2.9%

f2

本文に「public」が含まれている

84.5%

42.8%

f3

本文に「name」が含まれている

83.9%

48.1%

f4

本文に「city」が含まれている

76.6%

5.5%

1
0.9
0.8
0.7
Recall

内容

0.6
0.5
0.4
0.3
0.2
0.1
0

フィルタ数が 200 の場合の結果である. また, 図 4, 図 6 は全て

0

500

1000

1500

2000

2500

3000

3500

4000

4500

# tasksのタスクが終了するまでの結果を示したものであり, 図 5, 図 7

Randomは 500 タスク目までの途中結果を示したものである. 本研究で

図4

SFSelect

ML

再現率の推移 (E メール, フィルタ数 100, 全体)

は, 少ないタスク数で多くの正例を収集したいという状況を想定しているため, 処理されたタスク数が少ない時点での, 正例に0.5対する再現率が重要となる.
0.4

でタスクを処理する場合よりも少ないタスク数で比較的多くの正例を発見できていることが分かる.

Recall

図 4, 図 6 より, SFSelect と ML はいずれも, ランダムな順番

0.3

0.2

また, 図 5, 図 7 より, SFSelect と ML とでは, 約 400 タスク
0.1

目まででは SFSelect の再現率が ML のそれよりも高くなっていることが分かる.

0

0

100

200

さらに, 図 5, 図 7 を比較すると, フィルタ数を増やした場合,
Random

タスク数が少ない時点において, 両手法の差が大きくなっていることが分かる. 特に, 200 タスク目を処理した時点での両手法

300

400

500

# tasks
SFSelectML

図 5 再現率の推移 (E メール, フィルタ数 100, 500 タスク目まで)の再現率の差は, フィルタ数が 200 の場合の方が 100 である場
1

合と比べ大きくなっている. これは, ML が次元の呪いの影響を0.9受けたためであると予想される. この実験では 200 個のフィル

0.8
0.7

の呪いの影響を受け, フィルタの重みを学習するのに多くの訓練データを要し, 再現率の上昇が鈍くなったと予想する.

Recallタ, すなわち 200 個の特徴量を用いた. そのため ML では次元

0.6
0.5
0.4
0.3

一方, 図 4, 図 6 から, 約 400 タスク目以降においては ML の

0.2

方が常に再現率が高くなっていることが分かる. これは (1) 分

0.1
0

類器の学習に必要な訓練データがある程度集まったことと, (2)

0

500

1000

1500

2000

2500

3000

3500

4000

4500

# tasks

両手法の間でフィルタに対する重みのつけかたが異なっていた

Random

ことが原因であると予想する. 以下では (2) について詳しく説

図6明する. SFSelect では, あるフィルタに対し, そのフィルタを使用するか否か, すなわち 0 か 1 かという離散的な重みづけを行

SFSelect

ML

再現率の推移 (E メール, フィルタ数 200, 全体)

0.5

う. 一方, ML では, あるフィルタに対し, 連続的な実数値の重0.4

フィルタ間の優劣を決定でき, 正例である確率がより高いデー
タを持つタスクを選択できる. このような理由から, タスク数がRecall

みづけを行う. そのため, ML は SFSelect と比べ, より詳細に

0.3

0.2

増加するにつれ, ML の方が SFSelect よりも再現率が高くなったと予想する.

7. 2 問題 2. 建物の倒壊判定
7. 2. 1 シミュレーション設定
2013 年に発生した台風 26 号の伊豆大島における台風被害の実データを用いた. この実データは 11,350 件の画像からなって

0.1

0

0

100

200

300

400

500

# tasks
RandomSFSelectML

図 7 再現率の推移 (E メール, フィルタ数 200, 500 タスク目まで)おり, その内の約 1% (118 件) に倒壊家屋が含まれている. な
お, 家屋が倒壊しているか否かの判定は事前に人手で行った. このデータから図 1 のような分類タスクが作成される.

7. 2. 2 用いたフィルタ
表 3 に示す 4 つのフィルタを使用した. 各フィルタの作成方
法については本稿における議論と関係しないため省略する. な表 3 問題 2. のシミュレーションに用いるフィルタ

1

内容

適合率

再現率

0.9

femp

（空フィルタ）

1.0%

100%

0.8

f1

建物周辺の画素の色がまばらである

0.9%

44%

f2

建物周辺の画素の多くが茶色である

4.8%

53.4%

f3

壊れている建物の 100m 以内にある 28%

85.6%

0.7
Recall

0.6
0.5
0.4
0.3
0.2

1

0.1

0.9

0

0.8

0

100

Recall

200

300

400

500

600

700

800

900

1000

# tasks

0.7

Random

0.6
0.5

図9

SFSelect

ML

再現率の推移 (建物の倒壊判定, 1,000 タスク目まで)

0.4
0.3
0.2

5

0.1

4
3
0

2000

4000

6000

8000

10000

12000

# tasks
Random

図8

SFSelect

ML

再現率の推移 (建物の倒壊判定, 全体)

2weight value

0

1
0
-1
-2
-3

お, 表 3 にあるフィルタ f3 は他のタスクの結果に依存するフィ-4-5

ルタである.

0

100

300

400

500

600

700

800

900

1000

# tasks

7. 2. 3 シミュレーション結果
図 8, 図 9 にシミュレーション結果を示す. 図 8 は全 11,350

200

f0

図 10

f1

f2

f3

各フィルタにつけられた重みの推移 (1,000 タスク目まで)

タスクにわたる結果であり, 図 9 は 1,000 タスク目までの結果
である.
図 8 より, SFSelect と ML のいずれも, タスク数が少ない時点でも, ランダムな順でタスクを処理する場合と比べ再現率が高くなっていることが分かる. 特に, 図 9 から, どちらの手法も1,000 タスクの処理を終えた時点で再現率が 0.8 近くに達していることがわかる. 一方, ランダムな順でタスクを処理する場
合では, 1,000 タスクの処理を終えた時点での再現率が 0.1 未満となっている.
これは両手法とも, 他のフィルタと比べ適合率が比較的高い

f2 , f3 を重視したためである. 実際, SFSelect では, f3 にマッチするデータが存在する時点では, 適合率の最も高い f3 だけを Factive に所属させることが多く, f3 にマッチするデータが存在しない時点では, 2 番目に適合率の高い f2 だけを Factiveに所属させることが多かった. また, 図 10 から分かるように,

ML では約 50 タスク目以降において f2 と f3 に比較的大きな
重みを付与している. 図 10 の横軸は処理されたタスク数, 縦軸
は各フィルタに付与されて重みであり, タスク数の変化に伴う各フィルタの重みの変化を示している. この図から, f2 , f3 に対し, 比較的大きな重みが付与され, f2 , f3 にマッチするデータを持つタスクが優先的に処理されたことがわかる.
一方, SFSelect と ML では, タスク数に関わらず, 顕著な差は見受けられなかった. 顕著な差がみられなかった要因として
は, フィルタ数が少なかったことが予想されるが, これを確認するためのデータは現時点で得られていない. そのため, このよ
うな結果となった要因について, さらに実験と分析を行う必要がある.

8. お わ り に本研究では, 大量のデータ中から少ないタスク数で多くの正例を発見することを目的とし, 大量のフィルタ中から選別したフィルタを用いてタスクの割り当て順を変更する問題を扱った.
そして, 実データを用いたシミュレーションにより, 機械学習を利用した手法と統計情報を用いた手法の比較を行った. シミュレーションの結果, フィルタ数が多いときには, 機械学習を用いた手法よりも統計情報を利用した手法の方が再現率の立ち上がりにおいて優れている場合があることを発見した.
今後の課題としては，第一に，今回用いたデータ以外での実験がある．次元の呪いにより機械学習の立ち上げが遅れるという現象が，どのような条件でより顕著に出現するのかを検討する．また，今回はフィルタの作りやすさから E メールのスパム
判定のデータセットを利用したが，本研究で想定する「立ち上げが重要」という応用で利用されるデータでの実験をさらに追加する．第二に，計算機で判断可能な大量のフィルタを入手する方法が存在すれば，本アプローチが有効な場面が増えると考えられるため，そのような手法の検討が重要である.

謝

辞本研究の一部は科研費 (#25240012) による．
文

献[1] http://csmining.org/index.php/spam-email-datasets-.html.
[2] http://jbauman.com/aboutgsl.html.
[3] https://github.com/stanfordnlp/CoreNLP/blob/master/data/
edu/stanford/nlp/patterns/surface/stopwords.txt.

[4] Justin Cheng and Michael S. Bernstein. Flock: Hybrid
crowd-machine learning classifiers. In Proceedings of the
18th ACM Conference on Computer Supported Cooperative
Work & Social Computing, CSCW 2015, Vancouver, BC,
Canada, March 14 - 18, 2015, pp. 600–611, 2015.
[5] Kevin S. Woods, Kevin W. Bowyer, and W. Philip
Kegelmeyer. Combination of multiple classifiers using local accuracy estimates. In 1996 Conference on Computer
Vision and Pattern Recognition (CVPR ’96), June 18-20,
1996 San Francisco, CA, USA, pp. 391–396, 1996.
[6] Michal Wozniak, Manuel Graña, and Emilio Corchado. A
survey of multiple classifier systems as hybrid systems. Information Fusion, Vol. 16, pp. 3–17, 2014.
[7] James Y. Zou, Kamalika Chaudhuri, and Adam Tauman
Kalai. Crowdsourcing feature discovery via adaptively chosen comparisons. In Proceedings of the Third AAAI Conference on Human Computation and Crowdsourcing, HCOMP
2015, November 8-11, 2015, San Diego, California., p. 198,2015.
[8] 権守健嗣, 森嶋厚行, 歳森敦, 北川博之. クラウドソーシング
ヒューリスティクスの一般化選択フィルタによるモデル化と動的選択. DEIM2015 第 7 回データ工学と情報マネジメントに関するフォーラム, 2015.