DEIM Forum 2013 A8-4

クラウドソーシングにおけるワーカープライバシを保護した品質管理梶野洸†

荒井ひろみ††

鹿島 久嗣†† 東京大学大学院情報理工学系研究科 〒 113–8656 東京都文京区本郷 7–3–1†† 理化学研究所 生命情報基盤研究部門 〒 230–0045 神奈川県横浜市鶴見区末広町 1–7–22
E-mail: †{hiroshi kajino,kashima}@mist.i.u-tokyo.ac.jp, ††hiromi@base.riken.jp
あらましクラウドソーシングとは，不特定多数のワーカーに仕事を依頼するシステムの総称である．その特徴として人手を要するタスクを低コストかつ短時間で大量に処理をすることができる点が挙げられるが，得られる成果物の品質が保証できないという問題が指摘されており，冗長に得た成果物を統合することで品質を高めるという研究が主に行われてきた．本論文ではクラウドソーシングにおけるワーカーのプライバシ漏洩の問題に注目しその重要性を指摘するとともに，ワーカーのプライバシを保護した品質管理プロトコルを提案する．そして提案プロトコルの安全性を理論的に保証し，ワーカーのプライバシを考慮しない既存手法と比べて精度が劣らないことと，実用的な計算時間で計算可能であることを実験的に示す．
キーワード

クラウドソーシング, 機械学習, プライバシ保護データマイニング

Hiroshi KAJINO† , Hiromi ARAI†† , and Hisashi KASHIMA†† Graduate School of Information Science and Technology, The University of Tokyo,
7–3–1 Hongo, Bunkyo–ku, Tokyo 113–8656, Japan.
†† RIKEN Bioinformatics And Systems Engineering division, 1–7–22 Suehiro-cho, Tsurumi-ku, Yokohama,
Kanagawa, 230–0045, Japan.
E-mail: †{hiroshi kajino,kashima}@mist.i.u-tokyo.ac.jp, ††hiromi@base.riken.jp
Key words crowdsourcing, machine learning, privacy-preserving data mining

1.

序

論

測定するというタスクに特化している．後者の例として挙げられるのが Amazon Mechanical Turk（注 2）や CrowdFlower（注 3）にクラウドソーシングとは，不特定多数の人間 (ワーカーと呼代表される汎用的なクラウドソーシングである．タスクの依頼ぶ) に仕事 (タスクと呼ぶ) を依頼するシステムの総称である．

や検索のみならずタスク自体もウェブ上で行えること，どのよ

様々なクラウドソーシングが実現されているが，その多くに共うな種類のタスクでも依頼できることが特徴である．

通する仕組みは，ID でのみ管理される匿名化されたワーカー

このように様々な形態のクラウドソーシングが実現されていがクラウドソーシング上で公開されているタスクをいくつか選るが，その多くが抱えている問題として，クラウドソーシン

択し，そのタスクを完了することで対価として金銭的報酬，情グを通じて得られる成果物の品質に関する問題が挙げられる．

報，コミュニティ内での名声などを得るというものである．ク

ワーカーの能力は未知である上に，ワーカーはタスクの成果物

ラウドソーシングを用いて仕事を依頼する利点は，大量のワーの品質に対して責任を負う必要がないため，得られる結果の品

カーによって低コストでタスクを完了させることができること質は未知である．例としてデータにラベル付けを行うタスクをが挙げられる．そのため人の知能を必要とするタスクを大量に考え，得られる成果物の一例を図 1 の下部分に示した．図 1 で処理するのに適していると言える．

はワーカー 1,2,3 が同じデータにラベル付けを行なっているが，クラウドソーシングは特定のタスクに専門化したものと汎用

ワーカー 1 が正しいラベルを付けるのに対し，ワーカー 2 は的なものが存在する．前者の例は様々見られるが，その一例とデータによって誤ったラベルを返し，またワーカー 3 はデータして「測ってガイガー！」（注 1）という，放射線量の測定を依頼すに関係なく同じラベルを返している．クラウドソーシングで得るウェブサービスが挙げられる．これは特定地点の放射線量を（注 2）：https://www.mturk.com/mturk/welcome（注 1）：http://hakatte.jp/（注 3）：http://crowdflower.com/

する．またタスクの内容によっては成果物自体にワーカーの位
置情報や個人情報，その人の嗜好が反映される場合があり，それらを組み合わせるとワーカー個人が特定される恐れがある．
ワーカー個人が特定され，それに紐付く位置情報を含む個人情報も流出することで不利益を被る恐れがある．また能力の低い
ワーカーは，ワーカーの能力が推定され流出することで依頼者からブロックされてタスクにアクセス出来なくなる恐れがある．
以上の議論より品質管理問題に限定した場合でもワーカーのプライバシが侵害されることで様々な問題が生じ，ワーカーが不利益を被ることがわかる．クラウドソーシングにおけるプラ
イバシ問題を取り扱った論文はほとんどなく [3, 13]，特にワーカーのプライバシ問題を取り扱ったのは本論文が初めてである．
図 1 クラウドソーシングの例を示す．クラウドソーシングは依頼者とワーカーから成る．破線で参加者らの間で可能な通信を示したように，ワーカー同士で通信はできない．
タスク例として画像データに対するラベル付けタスクを考える．下部の表では各データに各ワーカーが与えるラベルを表す．ワーカープライベートデータモデルでは，各ワーカーが太枠で囲まれたラベルを秘密に保持している．従来のクラウドソーシングでは依頼者が全ラベルを知ることができるのに対し，提案モデルではラベルを付けたワーカー自身のみがラベルを知ることができる．

本論文はワーカーのプライバシを保護した品質管理手法を新たに提案することで上述の問題を回避する．はじめにワーカー
プライバシの概念を定義し，ワーカープライバシを保護した品
質管理問題を定義する．そしてその問題に対して，代表的な品質管理手法である潜在ラベル法 [5] の計算を分散化および秘匿化した手法を提案する．図 1 に示すように各ワーカーが自分の付けたラベルを秘密に保持した状態でワーカーと依頼者が協調して計算を行うことで，ワーカープライバシを保護しつつ依頼
者は真のラベルの推定が可能となる．さらに提案手法の安全性について理論的評価を行い，提案手法の計算時間及び計算精度について実験的に評価及び考察を行う．

られた品質が未知の成果物から正しい成果物を推定する問題を本論文では品質管理問題 [7] と呼ぶ．品質管理問題に対する手法は数多く提案されている．以下に紹介する手法はデータに対してラベルを付けるというタスクを取り扱っているため，以降タスクをラベル付けに限定し成果物をラベルと呼ぶことにする．
品質管理問題に対する代表的な手法は冗長化である．1 つのタ
スクを複数のワーカーに依頼して品質未知のラベルを複数得て，それを元に真のラベルを推定する手法である．Sheng ら [11]が品質管理問題に対して初めて冗長化法を用いた真のラベルの推定法を提案した．Sheng らは多数決を用いて冗長なラベルから真のラベルを推定した．これを発展させた手法として，ワーカーのラベル付けの過程をモデル化し，そのモデルの推定を通じて冗長なラベルから真のラベルを推定する手法がある．モデ
ルはワーカーの能力を考慮した潜在ラベルモデル [5] が代表的だが，これを拡張したモデルも様々提案されている [16, 17]．
このようなモデルを用いることで，真のラベルのみならずワー
カーの能力も推定することが可能になり，能力の劣るワーカーを排除することも可能になる．
従来より品質管理問題のようなタスクの依頼者の視点からの問題が考えられてきた一方で，ワーカーの視点からの問題はほとんど考えられていない．本論文ではワーカー視点の問題の 1
つとして，品質管理問題におけるワーカーのプライバシ問題に注目する．品質管理問題では依頼者がワーカーのラベルをすべて収集及び統合することで真のラベルを推定するが，その過程
で依頼者は，図 1 中の表のようなワーカーとラベルの対応の情報を取得し，それを用いて真のラベルやワーカーの能力を推定

以上をまとめると，本論文における成果は次の 4 点である．

(i) クラウドソーシングにおける品質管理問題に対するプライバシ問題を定義した．(ii) プライバシを保護した品質管理手法を提案した．(iii) 提案手法の安全性を理論的に保証した．(iv)
提案手法の性質について実験的に評価した．

2.

クラウドソーシングと品質管理問題

本章では品質管理問題において用いられる標準的なクラウド
ソーシングのモデルを紹介し，冗長な品質未知のラベルから真のラベルを推定するという品質管理問題を定義した後に，この問題に対する代表的な手法である潜在ラベル法 [5] を紹介する．

2.1

クラウドソーシング

図 1 のように，クラウドソーシングは依頼者と J (>= 1) 人のワーカー集合 J = {1, . . . , J} から成る．クラウドソーシング
では依頼者はタスクを依頼し，またワーカーはタスクを選択し完了することで報酬を得る．本論文では簡単のため，データに対して二値のラベルを与えるタスクのみを考える．ただし本論
文のアイデアは多値や連続値のラベル付けを含む様々なタスクに応用できることに注意する．各ワーカーは図 1 に示されるよ
うに依頼者とのみ通信を行うことが出来ると仮定する．実際のクラウドソーシングではワーカー間で通信を行うことは難しいため，この仮定は自然な仮定だと言える．
依 頼 者 は I (>= 1) 個 の デ ー タ か ら 成 る デ ー タ 集 合 I ={1, . . . , I} を保持し，各データ i ∈ I に対する真のラベル
yi ∈ {0, 1} を得ることを目的とする．真のラベルの集合をY ⋆ = {yi | i ∈ I} とする．J 人存在するワーカーはそれぞれj ∈ J で表される．各ワーカーはクラウドソーシング上でタス∑

クを探しラベルを付ける．ワーカー j がデータ i に付けるラベ

αj ←ルを yij ∈ {0, 1} と置き，これをクラウドラベルと呼ぶ．このラベルの品質は未知であるとする．つまり一般に yi = yij となるとは限らないとする．このラベルの性質についてはワー
カーのモデル化に伴い定義される．ワーカー j がラベルを付けたデータ集合を Ij ⊂=I (Ij ̸= ∅)，ワーカー j が付けたラベル集
合を Yj = {yij | i ∈ Ij }，データ i にラベルを付けたワーカー
集合を Ji ⊂=J (Ji ̸= ∅)，データ i に付けられたラベル集合を

Yi = {yij | j ∈ Ji }，クラウドラベル全体を Y とする．
品質未知の冗長なクラウドラベルから真のラベルを推定するという問題を品質管理問題と呼ぶ．その定義を問題 1 に示す．
ただしこの定義では真のラベルは定義されていないため，モデル化などを通じて定義を行うことが必要となることに注意する．
問題 1 (品質管理問題). 品質管理問題とは，クラウドラベル Yから，すべてのデータ I に対する真のラベル Y ⋆ を推定する問

品質管理問題に対する既存手法

本節では品質管理問題 (問題 1) に対する既存手法である潜在ラベル法 [5] を紹介する．この手法では真のラベルとクラウド
ラベルの間に確率モデル (潜在ラベルモデルと呼ぶ) を仮定し，モデルの推論を通じて真のラベルを推定する．

2.2. 1

潜在ラベルモデル

潜 在 ラ ベ ル モ デ ル で は ，各 デ ー タ i ∈ I が 真 の ラ ベ ル

yi ∈ {0, 1} を 1 つ持つと仮定し，各ワーカー j ∈ J がデータ iに対してラベル yij ∈ {0, 1} をi∈Ij µi, βj ←i∈Ij (1 − µi )(1 − yij )∑i∈Ij (1 − µi ),と更新．
こ こ で µi , ai , bi は そ れ ぞ れ Pr[yi = 1 | Y, Θ], Pr[Y |yi = 1, Θ], Pr[Y | yi = 0, Θ] の 推 定 値 で あ る ．以 降
µ = [µ1 , . . . , µI ] の よ う に ，太 字 で パ ラ メ タ の 集 合 を
表 す．ア ル ゴ リ ズ ム の 収 束 判 定 に は Q 関 数 Q(Θ, µ) =∑i∈I [µi log pai + (1 − µi ) log(1 − p)bi ] の 相 対 誤 差 を 用 い ，|Q(Θ(t+1) , µ(t+1) ) − Q(Θ(t) , µ(t) )|/|Q(Θ(t+1) , µ(t+1) )| < ϵ となった時に収束したと判断した（注 4）．ここで Θ(t) ∑は t 回目の反復で得られるパラメタを表す．初期化は µi ←j∈Ji yij

|Ji |

と

した．

3.

ワーカープライバシを保護した品質管理問題

潜在ラベル法を含む既存の品質管理手法はワーカーのプライ
めには依頼者がクラウドラベルを回収する必要があり，その結果ワーカーとラベルとの対応が依頼者に漏洩し，序論で議論したような不都合が生じうる．本章ではこのプライバシ問題を取り扱うため，ワーカーに対するプライバシモデルを定義し，ワーカープライバシを保護した品質管理問題を定義する．
プライバシモデルの定義は，誰がどのデータをどの範囲まで公開するかを定義することで行われる．ここで定義するワー
カープライベートモデルは，図 1 のように，各ワーカー j ∈ Jが自分の付けたラベルを秘密に保持し，それを依頼者や他のワーカー J \{j} に知られないという状況をモデル化する．まαj = Pr[yij = 1 | yi = 1, θj ],ずラベルがワーカープライベートである定義を次に示す．

βj = Pr[yij = 0 | yi = 0, θj ].

定義 1 (ワーカープライベート). 依頼者，ワーカーら J からというモデルに従って独立に与えるとする．ここで θj = {αj , βj }をワーカー j の能力パラメタとする．また任意の i ∈ I に対して p = Pr[yi = 1] が成り立つとする．モデルパラメタ全体をΘ = {θj }j∈J ∪ {p} とおく．
2.2. 2∑∑

バシを保護していない問題がある．品質管理手法を適用するた

題である．

2.2

i∈Ij µi yij

成るクラウドソーシングで，各ワーカー j ∈ J がラベル Yj を付けたとする．Yj に含まれるラベルが，ワーカー j のみに知られていて，依頼者，他のワーカーら J \{j} に知られないとき，ラベル Yj はワーカープライベートである．
各ワーカーのラベルがワーカープライベートに保たれるよう推論アルゴリズム

クラウドラベル Y が得られた時にモデルパラメタと真のラなモデルをワーカープライベートモデルと定める．クラウドラ

ベル Y ⋆ を推論するアルゴリズムを紹介する．推論アルゴリズ

ベル Y をワーカープライベートに保ちつつ真のラベル Y ⋆ を推

ムは，最尤推定量を用いてモデルパラメタを推定する．ただし定する問題を，ワーカープライバシを保護した品質管理問題と潜在変数 Y がモデルに含まれているため，最尤推定量を直接して次のように定義する．

⋆

計算することは困難である．そのため EM アルゴリズムを用いてモデルパラメタの推定を行う．アルゴリズムでは次に示す(E-STEP) と (M-STEP) を交互に繰り返す．
(E-STEP) それぞれの i ∈ I に対し
ai ←

∏

yij

(αj )

(1 − αj )

1−yij

,

j∈Ji

bi ←

∏

問題 2 (ワーカープライバシを保護した品質管理問題). 依頼
者，ワーカーら J から成るクラウドソーシングで，各ワーカー

j ∈ J がラベル Yj を付けたとする．ワーカープライバシを保護した品質管理問題とは，各ワーカー j のラベル Yj をワーカー
プライベートに保ちつつ，依頼者が真のラベル Y ⋆ を推定するという問題である．

(βj )

1−yij

(1 − βj )

j∈Ji

と更新．

(M-STEP) p ←∑i∈I µi

|I|

yij

pai
, µi ←,
pai + (1 − p)biと更新し，それぞれの j ∈ J に対し

4.

提案プロトコル

本章では問題 2 に対する品質管理手法であるワーカープライ（注 4）：実験では ϵ = 10−8 とした．

プロトコル 1 ワーカープライバシ保護潜在ラベルプロトコル

2) を用いる点である．潜在ラベル法の初期化と (E-STEP) で

参加者: 依頼者, ワーカーら J .

は各ワーカー j ∈ J が秘密に所持する値 αj , βj , Yj を用いた計ワーカー j (j ∈ J ) の秘匿入力: Yj , Ij .

算するが，提案プロトコルではこの各ワーカーの値を秘匿しつ

依頼者の秘匿入力: J .
(t)

(t)

(t)

公開出力: 各反復 t における {ai , bi , µi

つ計算結果を得るために秘匿加算プロトコルを用いる．秘匿加| i ∈ I}.
(t)

算プロトコルを用いずに複数の計算主体で実行する場合，潜在(t)

ワーカー j の秘匿出力: 各反復 t における αj , βj .
設定: 参加者は (J + 1, θ)-閾値暗号系を用い，すべてのワーカー J が
公開鍵 pk を共有し，各ワーカー j ∈ J が秘密鍵 skj を，依頼者が秘J+1

密鍵を skを保持する．

(t)
2: 参加者は，それぞれの i ∈ I に対して µi =

(∑

)

5:

依頼者が p(t) ←(∑(t)
i∈I µi(t)j∈Ji yij/|Ji |)

要があるが，2 行目で得たラベルの情報を用いるとワーカーのまたワーカープライバシ保護のためにはこの 2 点の拡張で十分であることを 5 章で議論する．
提案プロトコルは潜在ラベル法と比べると，ワーカープライ
バシを保護できる点で優れているが，計算時間と計算精度の面

6:

依頼者が t ← t + 1 と更新し全体に配信．

7:

参加者が，それぞれの i ∈ I に対して log ai

(t)

(t)

と log bi

で劣る．計算の分散化により通信が発生し，また秘匿加算プロ
を秘匿加算プロトコル (プロトコル 2) を用いて次のように計算:
∑
(t−1)
(t−1)
(t)
+ (1 − yij ) log(1 − αj)),log ai ← j∈Ji (yij log αj
∑
(t)
(t−1)
(t−1)
log bi ← j∈Ji ((1 − yij ) log βj+ yij log(1 − βj)).

トコルで鍵生成や暗号化，復号化が必要になるため計算時間が増加する．さらに秘匿加算プロトコルでは計算誤差が生じる．
これらの影響については 6 章で数値実験を用いて評価を行う．

4.2(t)p(t−1) ai
(t)
(t)
(t−1)
p
ai +(1−p(t−1) )bi

9:) | i ∈ I} を依頼者に送る必ある．以上の議論より，この 2 点の拡張は必要であると言える．

/|I| と更新し全体に配信．
)
) (∑
(∑
(t)
(t)
(t)
，
各ワーカー j ∈ J が αj ←i∈Ij µi
i∈Ij µi yij /
)
) (∑
(∑
(t)
(t)
(t)
βj =
i∈Ij (1 − µi ) とi∈Ij (1 − µi )(1 − yij ) /依頼者がそれぞれの i(t−1)+ yij log(1 − βj

能力に関するパラメタ αj , βj も依頼者に知られてしまうためで

更新．

8:

(t)

の 7 行目の計算で，{yij log αj + (1 − yij ) log(1 − αj ), (1 −yij ) log βjを秘匿加算プロトコル (プロトコル 2) を用いて計算．
4:の 2 行目の計算でクラウドラベルが漏洩し，またプロトコル 1(t−1)

1: 依頼者が t ← 0 と更新し全体に配信．

3: repeat

ラベル法と同じように情報漏洩する．なぜなら，プロトコル 1∈(t)

I に 対 し て µi←と更新し全体に配信．

依頼者が Q 関数の値を計算し，収束判定を行う．
[
]
∑
(t)
(t)
(t)
(t)
Q(t) = i∈I µi log p(t) ai + (1 − µi ) log(1 − p(t) )bi .

10: until |Q(t) − Q(t−1) |/|Q(t) | < ϵ

秘匿加算プロトコル

プロトコル 1 で補助的に用いる秘匿加算プロトコルをプロト
コル 2 で提案する．ここで提案する秘匿加算プロトコルは既存の秘匿加算プロトコルと比較すると参加者間の通信方式が新規である．クラウドソーシングではワーカーと依頼者間の通信のみが許容され，ワーカー間の通信を行うことができないため，
これを考慮した通信方式を用いた．以降，暗号方式として採用

バシ保護潜在ラベルプロトコルを提案する (以降，提案プロト
コルと呼ぶ)．プロトコルとは，複数の参加者が通信を行いながら計算を行うアルゴリズムのことを指す．提案プロトコルは，
潜在ラベル法 [5] の計算を分散化および秘匿化したものである．
つまり依頼者とワーカーら J が共に計算主体となってクラウドラベルを秘匿しつつ潜在ラベル法 [5] を実行する．4.1 節でワーカープライバシ保護潜在ラベルプロトコルを提案した後，提案プロトコルで補助的に用いる秘匿加算プロトコルを 4.2 節
で提案する．秘匿加算プロトコルとは，参加者 j ∈ {1, . . . , J}がそれぞれデータ vj を秘密に保持しているとき，これを他の∑参加者に知られることなくデータの総和 Jj=1 vj を計算するプ
ロトコルのことを指す．

4.1

ワーカープライバシ保護潜在ラベルプロトコル

提案プロトコルをプロトコル 1 に示す．潜在ラベル法を次の2 点で拡張して問題 2 を解決する．1 点目は計算の分散化である．従来の潜在ラベル法では，依頼者がすべてのクラウドラベ

する公開鍵暗号の性質を紹介をした後，秘匿加算プロトコルを提案する．

4.2. 1

公開鍵暗号

平文を整数 m ∈ ZN (= {0, 1, . . . , N − 1}) (N ∈ N) とし，対応する暗号文を c = Encpk (m; r) ∈ Z∗N 2 (= ZN 2 \{0}) とする．
公開鍵暗号では公開鍵 pk と乱数 r を用いて暗号化を行う．公
開鍵暗号では，乱数 r が Z∗N から一様ランダムに選択されると暗号文 c も Z∗N 2 上を一様ランダムに分布する．故に秘密鍵 skを知ることなく元の平文を得ることはできない．ここで提案する秘匿加算プロトコルでは，一般化 Paillier 暗号 [4] を用いる．
なぜならば，この暗号は加法準同型暗号と (n, θ)-閾値暗号の性質を兼ね備えているからである．以降その両性質と必要性を紹介する．
加法準同型暗号は暗号文を復号せずに平文の加算を実行できる．つまり平文 m1 , m2 の加算は暗号文同士の乗算を用いてEncpk (m1 + m2 mod N ; r) = Encpk (m1 ; r1 ) · Encpk (m2 ; r2 )ルを所有し，依頼者のみが計算主体となって真のラベルの推定を行うのに対し，提案プロトコルでは，ワーカーら J がそれぞとして得られる．ここで r1 または r2 のどちらかが一様ランダ

れクラウドラベルを秘密に所有し，ワーカーら J と依頼者がムであれば r は一様ランダムとなるため加算後に得られる暗号

共に計算主体となって真のラベルの推定を行う．クラウドラベ
ルをワーカープライベートに保つためにはワーカーが計算に参加する必要がある．2 点目は秘匿加算プロトコル (プロトコル

文からも平文を推定できない．以降簡単のため乱数を省略する．

(n, θ)-閾値暗号とは，n 人の参加者が秘密鍵を分散して所有
し，θ 人以上の参加者が協力をしない限り効率的な復号が行えない性質を持つ暗号である．秘密鍵を分散させる性質により参る安全性評価). |J | >= 3 と仮定し，それぞれの i ∈ I に対して，

プロトコル 2 秘匿加算プロトコル
参加者: 依頼者，ワーカーら J = {1, . . . , J}．

yij ̸= yij ′ ∈ {0, 1, ⊥} となる j, j ′ ∈ J が存在すると仮定する．

ワーカー j ∈ J の秘匿入力: vj ∈ R．

また各参加者は semi-honest モデルに従うと仮定する．これら

公開入力: ∀j ∈ J に対して vj L ∈ ZN となるような L ∈ ZN ．
設定: θ <= J を満たす (J + 1, θ)-閾値加法準同型暗号を用い，全参加者の仮定のもとで，ワーカープライバシ保護潜在ラベルプロトコ

が秘密鍵を分散所持し公開鍵を共有する．

匿ラベルを一意に決定できない．

(暗号文を用いた加算)
1: 各ワーカー j ∈ J は vj L の暗号文 cj ← Enc(vj L) を計算．
2: 各ワーカー j ∈ J は暗号文 cj を依頼者に送信．
3: 依頼者は χ ←∏j∈J cj (= Enc(∑

ル (プロトコル 1) を実行した後，どの参加者も他の参加者の秘j∈J vj )) を計算．

(復号)
1: 依頼者は |J˜| = θ − 1 を満たす J の部分集合 J˜⊂J を選択し，J˜=

定理 1 の 2 番目の仮定は強い仮定ではない．なぜならば，通常では 1 つのデータに対してすべてのワーカーがラベル付けをすることはなく，いずれかのワーカーのラベルは ⊥ となるためである．定理 1 を示すために，秘匿加算プロトコル (プロトコル 2) の安全性に関する補題 2 が必要となる．

に χ を送信．
2: 各ワーカー j̃ ∈ J˜ は依頼者に Decj̃ (χ) を送信．

補題 2 (秘匿加算プロトコルに関する安全性評価). |J | >=3と3: 依頼者は全ての j̃ ∈ J˜ から復号シェア Decj̃ (χ) を受信．

し，依頼者とワーカーらが semi-honest モデルにしたがってプ

4: 依頼者は復号シェア Decθ (χ) を計算．
5: 依 頼 者 は 復 号 シェア Decj̃ (χ) (∀j̃∑j∈J vj L を計算．

6: 依頼者は定数 L を用いて∑∈ J˜) と Decθ (χ) か ら

1 ∑j∈J vj ← L
j∈J vj L を計算．

ロトコルを実行すると仮定する．またワーカー同士で共謀することはないと仮定する．秘匿加算プロトコルの実行後，依頼者は最終的な計算結果のみを得るが，他の情報を推定することはできない．また，ワーカーらは計算過程で得られた情報から他のワーカーに関する情報を推定することはできない．

加者が復号することを防ぐことができる．暗号文 c を復号する
際には，参加者 j は自身の秘密鍵 skj を用いてそれぞれ復号

補題 2 の略証は secure multiparty computation [6] におけシェア Decskj (c) (平文の部分情報に相当) を計算し，θ 以上のる証明と同様にして与えられる．ここではワーカー同士の共謀

復号シェアを組み合わせることによって暗号文が復号される．

がないことを仮定しているが，クラウドソーシングではワー

4.2. 2

提案秘匿加算プロトコル

提案する秘匿加算プロトコルをプロトコル 2 に示す．EM ア
ルゴリズムを秘匿に実行する既存プロトコル [8, 18] で用いら

カーは他にどのワーカーがプロトコルに参加しているか知ることができないため，共謀しないという仮定は自然である．
補題 2 を用いると，プロトコル 1 の安全性評価を行う際には，
(t)

(t)

(0)

れている秘匿加算プロトコルとは通信方式の点で異なる．クラ{log ai , log bi , µi

ウドソーシングでは依頼者とワーカーの間での通信のみ許容さ

匿情報からの情報漏洩のみを考慮すればよいことがわかる．な| i ∈ I, t ∈ {1, . . . , T }} と，推測者の秘れているため，既存プロトコルで用いられている秘匿加算プロ

ぜなら，他の公開出力は補題 2 より保護されているか，これらトコルを適用することはできない．

の値から求めることができるからである．

プロトコル 2 の公開入力として，すべての j ∈ J に対して

vj L ∈ ZN となるような L を与える必要があるが，現実にはこのような L を与えることは難しい．そのため依頼者が十分大き
い L を取り，ワーカーらが vj L を整数値に丸めてプロトコル∑を実行する必要がある．故に得られる結果は j∈J vj の近似値となる．この近似がワーカープライバシ保護潜在ラベルプロ
トコルに与える影響については 6 章で議論する．

定理 1 の証明. プロトコル上の反復が T 回で収束するとする(T >= 1)．どの秘匿ラベル yij も次の変数群から一意に決定することができないことを示せば良い．
∑
j∈Ji yij(0)µi =(∀i ∈ I),
(1)
|Ji |
(
(
))
∑
(t)
(t−1)
(t−1)
log ai =yij log αj+ (1 − yij ) log 1 − αj
,
j∈Ji

5.

安全性評価

本章ではプロトコル 1, 2 の安全性評価を行う．その際に，各参加者は semi-honest モデルに従うとする．つまり，各参加者

(2)
))
(
(
∑
(t−1)
(t−1)
(t)
,
(1 − yij ) log βj+ yij log 1 − βjlog bi =j∈Ji(3)はプロトコルで定められた通りに行動するが，プロトコル実行
中に得たすべての情報を蓄積し，秘匿情報を推測しようとするとする．本章では表記の都合上 “⊥” というラベルを導入する．

yij = ⊥ であるとは，ワーカー j がデータ i にラベルを付けていないことを示すラベルである．よってラベルは {0, 1} の二値ではなく {0, 1, ⊥} の三値を取るとする．ワーカープライバシ
保護潜在ラベルプロトコル (プロトコル 1) の安全性に関して，
定理 1 が成立する．
定理 1 (ワーカープライバシ保護潜在ラベルプロトコルに関す(∀i ∈ I, ∀t ∈ {1, . . . , T }).
はじめに依頼者が秘匿ラベルを一意に決定できないことを示
(t)

(t)

す．依頼者が，式 (1), (2), (3) を満たす解 {log αj , log βj|j ∈ J , t ∈ {1, . . . , T }}，{yij ∈ {0, 1, ⊥} | i ∈ I, j ∈ J } を得たとする．これらの解から，他の解で同様に式 (1), (2), (3) を満たす解を導出できることを示すことで，秘匿ラベルを一意に決定することができないことを証明する．
仮定より，任意の i ∈ I, j ∈ J に対して，yij ̸= yij ′ とな

るような j ′ ∈ J \{j} が必ず存在する．{log αj , log βj
(t)

(t)

|j∈

表1

実データに対して各手法を適用した際の精度の比較．パJ , t ∈ {1, . . . , T }} と {yij ∈ {0, 1, ⊥} | i ∈ I, j ∈ J } のすべ

ラメタ L を 100 , 101 , . . . , 1014 の範囲で変化させたが，いての変数に対して j と j ′ を入れ替えることによって，式 (1),ずれのパラメタでも精度は変化しなかった．

(2), (3) を満たす解で，yij の値が異なる解が得られる．この操

多数決法

作は任意の i ∈ I, j ∈ J に対して行うことができるため，すべ0.752

潜在ラベル法 [5] 提案プロトコル

0.761

0.761

ての秘匿ラベル yij は一意に決定できないことが示された．
次にワーカー j ∈ J が秘匿ラベルを一意に決定できないこ

ラベルが得られた元での真のラベルに関する事後確率 µ が得らとを示す．J は依頼者の秘匿情報であるため，ワーカー j はれたとき，µi > 0.5 ならば yi = 1，µ <= 0.5 ならば yi = 0 と知り得ない．故に，式 (1), (2), (3) を満たす解とプロトコルに参加したワーカー集合 J˜ を得たとしても，新たなワーカー

真のラベルを推定した．また多数決を用いてラベルを推定する

j

new

∈
/ J˜ を考えて，そのワーカーと J˜ 中のワーカーとを入れ手法 (多数決法) は秘匿加算プロトコルを用いて簡単に実現できるため比較手法として精度を計算した．
結果

替えることで，式 (1), (2), (3) を満たす解で，yij の値が異な

6.2. 2

る解が得られる．

図 2 にパラメタ L とモデルパラメタの推定値の相対誤差の以上より定理 1 は示された．

グラフを示す．これを見ると，パラメタ L の値を大きくするに従って相対誤差が減少することがわかる．µ に関する相対誤差

6.

数値実験

は L = 107 まではあまり大きく減少しなかったが，これはアルゴリズムの収束までの反復回数の違いが寄与していると考えら

提案プロトコルの性能は潜在ラベル法 [5] と比較すると計算時間と計算精度の点で異なる．提案プロトコル (プロトコル 1)
で依頼者とワーカーの間で通信が必要となり，秘匿加算プロト
コル (プロトコル 2) において通信，鍵生成，暗号化及び復号化が必要となるため，その分計算時間が必要となる．また 4.2. 2
節で議論したように，実際には秘匿加算プロトコルでは和の近似値しか得られず丸め誤差の問題が生じる．本章ではこれらの問題について，提案プロトコルと潜在ラベル法 [5] を用いて数値実験で評価し，実用上問題とならないことを示す．

6.1

データセットWhitehill ら [17] が作成した “Duchenne Smiles Data Set”を用いた．このデータセットでのタスクは，1 枚の顔画像に対して，愛想笑いか否かのラベルを 1 つ付けるというタスクである．すべての顔写真に対して専門家によるラベルが付いているため，専門家によるラベルを真のラベルとして手法の性能を評価した．データセット中の画像数 (本論文の用語ではデータ
数) は I = 159 で，専門家によるラベルでは 159 枚の画像のうち 58 枚の画像は愛想笑いでないと判断された．ワーカー数はJ = 20，全クラウドラベル数は |Y| = 3, 513，そのうち愛想笑
いでないというクラウドラベルは 1, 804 である．

6.2

実験 1: 近似精度

実験 1 では，各手法で得られたパラメタの相対誤差と秘匿加算プロトコルのパラメタ L との関係を調べた．

6.2. 1

実験設定

パ ラ メ タ L を L = 100 , 101 , . . . , 1014 と 変 化 さ せ て 提案 プ ロ ト コ ル を 実 行 し ，パ ラ メ タ α = [α1 , . . . , αJ ], β =[β1 , . . . , βJ ], µ = [µ1 , . . . , µI ], p に対して次に定める相対誤差を計算して近似精度を評価した．潜在ラベル法で得られたパラメタの推定値を x ∈ {α, β, µ, p} とし，提案プロト
コルで得られた対応するパラメタの推定値を x̃ とした時に，∥ log x − log x̃∥/∥ log x∥ を相対誤差とした．
さらに各手法で推定した真のラベルの精度 (推定値と真の値が一致したデータの割合) を比較した．各手法ともにクラウドれる．図 3 に，パラメタ L と各アルゴリズムでの反復回数のグラフを示した．図 3 から，L = 107 より小さい時には潜在ラ
ベル法と提案手法とで反復回数が異なることがわかる．故に近似計算を行った際の計算誤差に加えて反復回数による影響が加わったためこのような結果になったと考えられる．
また表 1 にこのデータセットに各手法を適用した際の精度を示す．提案プロトコルではパラメタ L を L = 100 , 101 , . . . , 1014と変化させたが精度は変化しなかった．
以上の実験より，真のラベルの推定値は L にはあまり左右されないということ，モデルパラメタの推定値も L を大きくする
ことで許容できる誤差以下にすることができることが示された．

6.3

実験 2: 計算時間

実験 2 では提案プロトコルと潜在ラベル法 [5] との計算時間を比較する．提案プロトコルは，秘匿加算プロトコルにおける鍵生成，暗号化および復号化に関する計算時間と，ワーカーと依頼者間の通信に必要な時間の分余計に計算時間が必要となる．
通信時間は環境に大きく依存するため，暗号に必要な計算時間に限定して議論する．計算の分散化により αj , βj の計算が高速化される可能性があるが，その影響は十分無視できるものとして今回は取り扱わない．

6.3. 1

実験設定

秘匿加算は通常の加算と比較すると，鍵生成に必要な時間 1回分と，暗号化および復号化に必要な時間がアルゴリズムの反
復回数分余計に必要となる．どちらも秘匿加算プロトコルの参加者の人数 (本論文ではワーカー数 J) と鍵長 k に依存する．通
例鍵長を k = 1024 と固定するため，ワーカー数 J との関係を調べた．1 タスクに関与するワーカー数 J は現実には高々100 人程度であるため J = 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, . . . , 100 と変化させて，鍵生成 1 回に必要な時間と，暗号化および復号化 1 回に必要な時間を計測した．各ワーカー数で 10 回の試行を行い，その平均を計算した．(J + 1, ⌈ 23 (J + 1)⌉)-閾値暗号系を用いて，パラメタ L は計算時間に関係しないため L = 1010 とした．
秘匿加算プロトコルは UTD Paillier Threshold Encryption

図 2 パラメタ L と，潜在ラベル法と提案 図 3 パラメタ L と，潜在ラベル法と提案 図 4

ワーカー数 J と鍵生成に必要な時間

プロトコルとで得られたモデルパラ

プロトコルの反復回数のグラフ．横(keygen) および，1 回の暗号化と復メタの相対誤差のグラフ．横軸がパ軸がパラメタ L，縦軸が反復回数を号化に必要な時間 (one update) との7

ラメタ L，縦軸が各パラメタの対数表す．L = 10 までは反復回数が一

グラフ．横軸がワーカー数 J ，縦軸の相対誤差を表す．パラメタ L を大致しないため，尤度にも誤差が生じが計算時間をミリ秒で表す．いずれ

きくすることで相対誤差が減少する．

ていることがわかる．

も実用的な範囲内だと言える．

Library（注 5）を用いて Java 1.6.0 で実装した．実験は 3.20 GHz

張にあたるモデル [12, 16, 17] を用いた統計処理が研究されて(CPU)，4 GB (RAM) のマシンで Linux 上で行った．

いる．本研究は品質管理問題から派生した，ワーカープライバ

6.3. 2結果

図 4 にワーカー数 J と鍵生成 1 回に必要な時間 (keygen) とシを保護した品質管理問題という新しい問題設定を考えている点でこれらの研究とは異なる．

暗号化および復号化 1 回に必要な時間 (one update) とのグラ

またクラウドソーシングにおけるプライバシの問題を指摘

フを示す．いずれもワーカー数 J に対してほぼ線形に大きくしたのは Bernstein ら [3] が我々の知る限りはじめてである．

なることがわかる．ただしプロトコルを実行する際に鍵生成は

Varshney [13] はタスクのプライバシ問題を取り扱ったが，本1 回行えばよく，また反復回数も今回用いた実データであって研究はワーカーのプライバシ問題を取り扱ったためこの研究とも 15 回程度であるため，これらの計算時間は十分実用の範囲は差別化される．
プライバシ保護 EM プロトコル

内に収まっていると言える．実データと同じようにワーカー数

7.2

J = 20，反復回数 15 回としたときに，鍵生成および 15 回の反プライバシ保護データマイニングの概念は同時期に 2 つのグ

復計算に必要な計算時間は 789.3 ms であった．このことから

ループによって提案された [1, 9]．これ以降この分野においても，提案手法を用いた場合でも計算時間は実用上問題ないこと

様々な研究が盛んに行われているが，その中で本研究と関連すが示された．

るものは，プライバシを保護して EM アルゴリズムを実行する

7.

関連研究

本論文はクラウドソーシングとプライバシ保護データマイニ

手法に関する研究である．

Luong と Ho [10] は，混合ガウス分布のパラメタ推定を目的とした．この手法は参加者が 2 人の場合に特化した手法である

ングという 2 つの研究分野と関連している．それぞれの分野とため，本論文の問題設定には適用できない．Lin ら [8] も混合

本論文との関係について論ずる．

ガウス分布のパラメタ推定を目的とした．3 人以上の参加者が7.1

クラウドソーシング

それぞれデータを保持し，補助プロトコルとして準同型暗号に2005 年周辺に Amazon Mechanical Turk，ESP ゲーム [14]，基づく秘匿加算プロトコル [2] を用いる．このプロトコルでは

reCAPTCHA [15] を含むインターネットを利用した様々なク

参加者 {1, 2, . . . , J} の中で，1 → 2 → · · · → J → 1 という順

ラウドソーシングサービスが登場して以来，クラウドソーシン

番で環状に通信を行う必要がある．しかし環状の通信はクラウグに関する研究が盛んに行われてきた．そのなかで最も研究さドソーシングでは行えないため，この手法を適用することはでれている問題は成果物の品質管理問題 [7] である．代表的な手きない．Yang ら [18] は，ネットワーク上のノードのクラスタ

法は，1 つのタスクを複数のワーカーに依頼して複数の品質未リングを目的とした．補助プロトコルとして Lin ら [8] と同様知の成果物を得て，その成果物を統計処理することで真の成果の通信方式の秘匿加算プロトコルを用いるため，この手法も適物を推定する手法である．Sheng ら [11] がこの手法を初めて用することはできない．

クラウドソーシングに適用した．Sheng らの用いた統計処理はさらに安全性評価の観点で見ると，アルゴリズムの実行中に単純な多数決であったが，その後は Dawid と Skene [5] が医共有される情報は本論文も他の関連研究も同様であるが，本論師の診断統合問題の文脈で提案した潜在ラベルモデルやその拡

文では数学的な安全性評価を行なっている一方で，他の関連研
究ではその安全性について明確な議論は行われていない．

（注 5）：http://utdallas.edu/~mxk093120/paillier/これら 2 つの点において本研究は既存研究と差別化される．

8.

結

論

[9] Y. Lindell and B. Pinkas. Privacy Preserving Data
Mining. In Advances in Cryptology–CRYPTO ’00, pp.
36–54, 2000.

本論文ではクラウドソーシングで生じるワーカープライバシ問題を紹介し，ワーカープライバシを考慮した品質管理問題を定義し，潜在ラベル法を拡張することで提案した問題を解決した．更に提案プロトコルの安全性について理論的に評価を行い，その実行速度，性能ともに実データを用いて実験的に評価した．
これらの評価により，提案手法の有効性を確認した．

謝

辞[10] T. D. Luong and T. B. Ho. Privacy Preserving EMBased Clustering. In 2009 IEEE-RIVF International
Conference on Computing and Communication Technologies, pp. 1–7, 2009.
[11] V. S. Sheng, F. Provost, and P. G. Ipeirotis.

Getanother label? Improving data quality and data mining using multiple, noisy labelers. In Proceedings of

本研究の一部は、内閣府最先端研究開発プログラム (FIRST)

the 14th ACM SIGKDD International Conference on「超巨大データベース時代に向けた最高速データベースエンジ

Knowledge Discovery and Data Mining, pp. 614–622,

ンの開発と当該エンジンを核とする戦略的社会サービスの実

2008.

証・評価」の助成を受けたものである。

[12] Y. Tian and J. Zhu. Learning from crowds in the pres-文

献[1] R. Agrawal and R. Srikant. Privacy-Preserving Data
Mining. In Proceedings of the 2000 ACM SIGMOD
international conference on Management of data, pp.
439–450, 2000. ISBN 1581132182.
[2] J. C. Benaloh. Secret sharing homomorphisms: keeping
shares of a secret secret. In Advances in Cryptology–
CRYPTO ’86, pp. 251–260, 1987.
[3] M. Bernstein, E. H. Chi, L. Chilton, B. Hartmann,
A. Kittur, and R. C. Miller. Crowdsourcing and human computation: systems, studies and platforms. In
Proceedings of 2011 ACM Conference on Human Factors in Computing Systems, pp. 53–56, 2011.
[4] I. Damgård and M. Jurik. A Generalisation, a Simplifi-

ence of schools of thought. In Proceedings of the 18th
ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 226–234, 2012.
[13] L. R. Varshney. Privacy and Reliability in Crowdsourcing Service Delivery. In 2012 Annual SRII Global Conference, pp. 55–60, 2012.
[14] L. von Ahn and L. Dabbish. Labeling images with acomputer game. In Proceedings of the SIGCHI conference on Human factors in computing systems - CHI’04, pp. 319–326, 2004.
[15] L. von Ahn, B. Maurer, C. McMillen, D. Abraham,and M. Blum. reCAPTCHA: human-based character
recognition via Web security measures. Science, 321(5895):1465–1468, 2008.

cation and Some Applications of Paillier’s Probabilistic
Public-Key System. In Proceedings of the 4th International Workshop on Practice and Theory in Public Key
Cryptography: Public Key Cryptography, pp. 119–136,
2001.

[16] P. Welinder, S. Branson, S. Belongie, and P. Perona. The multidimensional wisdom of crowds. In Advances in Neural Information Processing Systems 23,
pp. 2424–2432, 2010.

[5] A. P. Dawid and A. M. Skene. Maximum likelihood[17] J. Whitehill, P. Ruvolo, T. Wu, J. Bergsma, andestimation of observer error-rates using the EM algo-

J. Movellan. Whose vote should count more: optimal

rithm. Journal of the Royal Statistical Society. Series

integration of labels from labelers of unknown exper-

C (Applied Statistics), 28(1):20–28, 1979.

tise. In Advances in Neural Information Processing
Systems 22, pp. 2035–2043, 2009.

[6] O. Goldreich. Foundations of cryptography: basic applications. Cambridge University Press, 2004.

[18] B. Yang, I. Sato, and H. Nakagawa. Privacy-Preserving
EM Algorithm for Clustering on Social Network. In[7] M. Lease. On Quality Control and Machine Learning
in Crowdsourcing. In Proceedings of the third Human
Computation Workshop, pp. 97–102, 2011.
[8] X. Lin, C. Clifton, and M. Zhu. Privacy-preserving
clustering with distributed EM mixture modeling.
Knowledge and Information Systems, 8(1):68–81, 2005.

Advances in Knowledge Discovery and Data Mining 16th Pacific-Asia Conference, PAKDD 2012, volume 1,
pp. 542–553, 2012.