利用者のプライバシを保護す る協調フィルタリング方式の 提案 7adrm011 木澤寛厚. 背景 商品の量が多い 見つからな い orz ネットショップ.

Presentation on theme: "利用者のプライバシを保護す る協調フィルタリング方式の 提案 7adrm011 木澤寛厚. 背景 商品の量が多い 見つからな い orz ネットショップ."— Presentation transcript:

1 利用者のプライバシを保護す る協調フィルタリング方式の 提案 7adrm011 木澤寛厚

2 背景 商品の量が多い 見つからな い orz ネットショップ

3 情報推薦システム 他の利用者の嗜好に 基づき，利用者の嗜好 を予測 利用者の嗜好に合う 商品を提示する http://www.amazon.co.jp/ amazon

4 Windows C MAC A A Windows C 従来方式の問題点と 提案方式 BAC S サーバ 従来方式 MAC A ？ B Windows C B’ 嗜好情報 漏洩の可能性 提案方式 BAC ？ B MAC B’ 漏洩しない 暗号化

5 精度 MAE コスト GB １．秘匿 CF 方式 PCF ◎ 0.72 × 1024 ２．アイテム クラスタリング CCF○ 0.75 △ 28 ３．ユーザ サンプリング SCF △ 0.99 △ 36 ４．最尤法 LL× 1.0 ◎ --- ５．秘匿積集合を 利用した方式 ○ 0.83 ◎ 0.8 精度 MAE コスト GB １．秘匿 CF 方式 PCF ◎ 0.72 × 1024 ２．アイテム クラスタリング CCF○ 0.75 △ 28 ３．ユーザ サンプリング SCF △ 0.99 △ 36 ４．最尤法 LL× 1.0 ◎ --- ５．秘匿積集合を 利用した方式 ○ 0.83 ◎ 0.8 提案方式

6 要素技術：一覧 協調フィルタリング方式 (CF 方式 )  嗜好の評価値を予測する  一般的な推薦システムに利用されている技 術 2 者間秘匿積集合プロトコル  お互いが評価したアイテムの数 s(u i,u j ) を得 る  お互いどのアイテムを評価しているか秘密 Oblivious Transfer( 紛失通信 ) 準同型性暗号

7 提案方式 1/3 2 者間秘匿積集合プロトコルを使用し、 s(a,*) の値をそれぞれ出す 閾値 T を決める、 T ≦ s(a,*) の式を満た すユーザの集合を B とする  今回は T=1 、 B={c,d} i1i1 i2i2 i3i3 i4i4 s(a,*) a ＊ 25 b130 c231 d2152 i1i1 i2i2 i3i3 i4i4 a ＊ 25 b130 c231 d2152

8 提案方式 2/3 -1 a i1i1 i2i2 i3i3 i4i4 a ＊ 25 i1i1 i2i2 i3i3 i4i4 d212.75 dc i1i1 i2i2 i3i3 i4i4 c2.5 23 n out of 1 OT

9 提案方式 2/3 -2 a i1i1 i2i2 i3i3 i4i4 a ＊ 25 i1i1 i2i2 i3i3 i4i4 d1101 dc i1i1 i2i2 i3i3 i4i4 c0011 n out of 1 OT

10 提案方式 3/3 i1i1 i2i2 i3i3 i4i4 類似度 s(a,*) 平均 a ＊ 253.5 c2312.5 d21522.7 ＊ =a の平均＋ d との類似度・ d の評価 類似度の総和 分子 = s(a,c)(r 1,c -r c )+s(a,d)(r 1,d -r d ) = 1(2.5-2.5)+2(2-2.7) = -0.7 分母 = h 1,c s(a,c)+h 1,d s(a,d) = 0×1+1×2 = 2 ＊ = a の平均 + 分子 / 分母 =3.5+(-0.7)/2 = 3.15 ・ 準同型性暗号では割り算は計算できない → 分子と分母を計算し，復号してから割り算を計算する

11 評価実験 公開データベース (Group Lens) を使用し MAE ・通信コスト・計算コストを調べる  100 個の評価値を未評価とみなし推薦値を求め MAE を調べる ユーザ数 943 人 アイテム数 1682 個 総評価数 暗号文のサイズ べき乗計算 100,000 個 256byte 1764(ms)

12 精度 Proposed SCF[3] 推薦者数

13 計算コスト 推薦者数 570000s 6.5 日 337s 5 分

14 通信コスト 推薦者数 104.3GB 0.8GB

15 結論 利用者のプライバシ情報を保護しなが ら協調フィルタリング方式を行った  5 つの方式を提案した 秘匿協調フィルタリング方式 CCF 方式 SCF 方式 LL 方式 秘匿積集合プロトコルを利用した方式

16 今後の課題 通信コスト・計算コストの削減 精度の向上

17

18 要素技術： 協調フィルタリング方式 (CF 方式 ) i1i1 i2i2 i3i3 i4i4 類似度 S 平均 a ＊ 253.5 b1302 c230.882 d2150.962.7 ＊ =a の平均＋ b との類似度・ b の評価 +d との類似度・ d の評価 類似度の総和 = 3.5 + = 2.8 0(1-2)+0.96(2-2.7) 0+0.96 アイテム

19 要素技術： 2 者間秘匿積集合プロトコル 復号 0 の数 =|A∩B|=1 A={2,3} B={1,2} ab

20 関連技術 ・準同型性暗号 ・ OT 準同型性暗号  暗号化したまま計算できる Oblivious Transfer ab B={1,2,3} 2 1･31･3

21 紛失通信 サーバ クライアン ト

22 通信コスト・計算コストまと め ※類似度 s(u i,u j ) が被推薦者に漏れる SCF( 従来 ) 提案方式 精度 ×○ 通信コスト ×○ 計算コスト ×○ 漏洩する情報 ○ × ※× ※

23 考察：類似度 1/2 従来方式 → コサイン尺度 提案方式 → 積集合の大きさ 提案方式の精度が なぜ向上したのか検討

24 考察：類似度 2/2 相関係数 =0.922 → 提案方式の類似度はユーザ間の 類似度を反映している コサイン尺度 交わりの大きさ

25 考察： 2 者間秘匿積集合プロトコル 2 者間秘匿積集合プロトコルのコスト  推薦者の評価値の数を秘匿する場合， 1 推薦者あたり n の計算コストが生じる ユーザ数 943 ，アイテム数 1682 だと 1 推薦者あたり 48 分計算コストが生じる  通信コストは (m-1)n ユーザ数 943 ，アイテム数 1682 だと 682GB 実験ではこれらのコストを除いている → セキュリティとコストのトレードオフ

26 提案方式 D

27 アプローチ 評価行列の次元削減 １２３４５ A B C D E １３５ A B C D E １２３４５ A C E CCF 方式 SCF 方式

28 323β 4 フィレ オ 24α カレー iPhone CCF 方式 第 3 次的な情報から アイテムをクラスタリ ング そのクラスタ中でのみ 秘匿 CF 方式を適用 何人かサンプリングす る コミュニティに分割す る 評価値を決め秘匿 CF 方 式を適用 ２１ クラス アイテム集合 I iPhone フィレ オ A5 ＊ B51 C15 D5 SCF 方式 ユーザ集合 U αβ コミュニティ iPhone フィレ オ カレー α442 β323 A5 ＊ 2

29

30 推薦システム：問題点 BAC S サーバ MAC A ？ B Windows C B’ 嗜好情報漏洩の可能性 嗜好情報が漏洩せず 推薦結果を出したい

31 従来研究 Canny の方式 [1]  共役勾配法を用いて特異値分解を準同型性暗号 で行う 秘匿 CF 方式 [5]  準同型性暗号を用いて協調フィルタリングを行 う  欠損値を秘匿するために O(n 2 ) の通信コスト ユーザ数 943 人，アイテム数 1682 個で 1TB の通信コス ト 莫大な計算コスト・通信コスト

32 目的 秘匿積集合プロトコル [3] というアプロー チで、個人情報を秘匿したまま嗜好を予 測する 手法を提案する  計算コスト・通信コストを削減する