プライバシ協調フィルタリングにおける 利用者評価行列の次元削減 ○木澤 寛厚，　菊池 浩明(東海大)

背景 ネットショップ 商品が多すぎ 見つからないorz

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

従来方式と提案方式の違い S 漏洩しない 漏洩 B’ B’ A A C C B A B C A C B A B C MAC MAC ？ ？ サーバ MAC S 漏洩しない 漏洩 暗号化 MAC A MAC A Windows C Windows C ？ B MAC A ？ B Windows C A C B A B C

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

協調フィルタリング(CF方式) A 5 ＊ 2 3.5 B 1 3 0.97 C 0.35 D 1.0 iPhone フィレオフィッシュ カレー 類似度S 平均 A 5 ＊ 2 3.5 B 1 3 0.97 C 0.35 D 1.0 Bとの類似度・Bの評価+Cとの類似度・Cの評価 ＊=Aの平均＋ 類似度の総和 0.97(1-3)+0.35(5-3) =3.5 +　　　　　　　　　　　　　　 =　2.6 0.97+0.35

提案方式：秘匿CF方式 準同型性暗号でCF方式を計算する 準同型性暗号でCF方式を計算する 評価値の正規化 欠損値をマスクするフラグ コサイン尺度を和と積で実現するために　　　　　　評価値を距離で割る 欠損値をマスクするフラグ 予測値のアイテムを評価していないユーザは　　推薦に利用しない 評価値の積の予備計算 準同型性暗号でCF方式を計算する 評価値の正規化 コサイン尺度を和と積で実現するために　　　　　　評価値を距離で割る 欠損値をマスクするフラグ 予測値のアイテムを評価していないユーザは　　推薦に利用しない 評価値の積の予備計算

秘匿CF方式 -予備計算 1024GB =(a1b1+a2b2+a3b3)(b2-b) Bとの類似度・Bの評価 = S(A,B)・(b2-b) =(a1b1+a2b2+a3b3)(b2-b) =(a1b1b2+a2b2b2+a3b3b2)-(a1b1b+a2b2b+a3b3b) Bとの類似度・Bの評価 = S(A,B)・(b2-b) =(a1b1+a2b2+a3b3)(b2-b) =(a1b1b2+a2b2b2+a3b3b2)-(a1b1b+a2b2b+a3b3b) 被推薦者 B A 1024GB 暗号文　m(m+1)/2個

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

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

評価実験 公開データベース(Group Lens)を使用し MAE・通信コスト・計算コストを調べる CCF方式はクラスタ数，SCF方式はコミュニティ数を　変動させMAE・通信コスト・計算コストを調べる 暗号文のサイズを256byteとして通信コストを導出する べき乗計算を1764(ms)として計算コストを導出する ユーザ数 943人 アイテム数 1682個 総評価数 100,000個

CCF方式 MAE クラスタ数1～19 MAE

CCF方式 通信コスト・計算コスト 2967秒 1024GB 156秒 3GB

結論 課題 プライバシを秘匿した秘匿CF方式を提案 通信コストを減少させるための3つの改良案を提案 各方式を実用可能なコストまで下げる CCF方式 SCF方式 (LL方式) 各方式を実用可能なコストまで下げる 課題

ご清聴ありがとうございました

関連技術 - 準同型性暗号 暗号化したまま計算できる E 割り算は行えない

関連技術 – 協調フィルタリング方式(CF法) 評価値 高10　9　8　7　6　5　4　3　2　1低 X=9？ itemA itemB itemC itemD itemE itemF user1 8 5 4 9 7 user2 X

協調フィルタリング(評価値計算) ユーザ集合 U={u1,u2,…,um} アイテム集合 I={i1,i2,…,in} ・Uk = i ∈ U|ri,k = φ(未評価のアイテムの評価) ・s(ui,uj) = uiとujの類似度(コサイン尺度) ・　　= uiの評価した評価値の平均

コサイン尺度(類似度) ・ユーザaとユーザbの類似度を求める ユーザaの各アイテムに対する評価値A={a1,a2,…an} 　　ユーザbの各アイテムに対する評価値B={b1,b2,…bn} これらを準同型性暗号で行う

秘匿CF方式 (分母) ２－２ A 「フィレオ」の予測値を 得るためには 「Flag フィレオ」の値を使って 分母を計算する ユーザB 暗号文 iPhone フィレオ カレー Flag iPhone 5 1 3 Flag フィレオ Flag カレー iPhone フィレオ カレー A 5 ？ 2 B 1 3 C D ユーザC iPhone フィレオ カレー Flag iPhone 1 5 3 Flag フィレオ Flag カレー 「フィレオ」の予測値を 得るためには 「Flag フィレオ」の値を使って 分母を計算する ユーザD iPhone フィレオ カレー Flag iPhone 5 2 Flag フィレオ Flag カレー

秘匿CF方式(コサイン尺度) B A カレー フィレオ iPhone 暗号化して 行う場合

SCF方式 MAE number of communities d

SCF方式 通信コスト number of communities d

協調フィルタリング方式 D B C A iPhone カレー A 1 ？ 2 B 5 3 C D ？の値を計算 サーバ 推薦依頼 値を返す フィレオフィッシュ カレー A 1 ？ 2 B 5 3 C D ？の値を計算 サーバ D 推薦依頼 値を返す B C A

協調フィルタリング方式(類似度) 類似度計算 s(A,B) iPhone フィレオフィッシュ カレー A a1 a2 a3 B b1 b2 b3 C c1 c2 c3 D d1 d2 d3 iPhone フィレオフィッシュ カレー A 5 ？ 2 B 1 3 C D サーバ 類似度計算　s(A,B) (5*5+0*1+2*3)/{√(52+02+22)*√(52+12+32)}=0.97

協調フィルタリング(予測値計算) pa,2=3.5+{0.97(1-3)+0.35(5-3)}/(0.97+0.35) =2.6 iPhone フィレオフィッシュ カレー A 5 ？ 2 B 1 3 C D pa,2=3.5+{0.97(1-3)+0.35(5-3)}/(0.97+0.35) =2.6 サーバ これらの計算を 準同型性暗号で計算する

提案方式：秘匿CF方式 A D C B iPhone カレー A 5 ？ 2 iPhone カレー A 5 ？ 2 B 1 3 C D 暗号化したまま ？を計算し 復号する iPhone フィレオフィッシュ カレー A 5 ？ 2 iPhone フィレオフィッシュ カレー A 5 ？ 2 B 1 3 C D A 暗号化した 評価値を 送信 推薦依頼 D C B

秘匿CF方式 – 手順 A 被推薦者は分子と分母をそれぞれ計算 (暗号化したまま) 分子と分母の値をそれぞれ復号 被推薦者は分子と分母をそれぞれ計算　　　(暗号化したまま) 分子と分母の値をそれぞれ復号 閾値復号する　　　　　　　　　　　　　　　　　　　　　　(鍵はm人のユーザで分散しているとする) 分子と分母の値を割り平均を足す　　　　　　

秘匿CF方式(分母) ポイント １．コサイン尺度には割り算があるのでそのままでは準同型性暗号の適用は不可能． ２．予測値を得たいアイテムを評価していないユーザの類似度は加算しない iPhone フィレオ カレー A 5 ？ 2 B 1 3 C D iPhone フィレオ カレー A 5 ？ 2 B 1 3 C D コサイン尺度

秘匿CF方式 (分母) １－１ コサイン尺度を準同型性暗号で計算 できるように和と積だけにする B コサイン尺度を準同型性暗号で計算　　できるように和と積だけにする 各ユーザが評価値をあらかじめノルムで割っておく(単位ベクトルにする) a3 a2 a1 A b3 b2 b1 B |u| カレー フィレオ iPhone B A カレー フィレオ iPhone 評価値とする

秘匿CF方式 (分母) １－２ A B A カレー フィレオ iPhone 暗号化して 行う場合

秘匿CF方式 (分母) ２－１ 0か1のフラグを用意して未評価を判断 B C D 一つ一つ暗号化して，全て被推薦者Aに送信する ※実際はノルムを割る iPhone フィレオ カレー D 5 2 iPhone フィレオ カレー Flag iPhone 5 2 Flag フィレオ Flag カレー 一つ一つ暗号化して，全て被推薦者Aに送信する

秘匿CF方式 (分母) ２－２ A 「フィレオ」の予測値を 得るためには 「Flag フィレオ」の値を使って 分母を計算する ユーザB 暗号文 iPhone フィレオ カレー Flag iPhone 5 1 3 Flag フィレオ Flag カレー iPhone フィレオ カレー A 5 ？ 2 B 1 3 C D ユーザC iPhone フィレオ カレー Flag iPhone 1 5 3 Flag フィレオ Flag カレー 「フィレオ」の予測値を 得るためには 「Flag フィレオ」の値を使って 分母を計算する ユーザD iPhone フィレオ カレー Flag iPhone 5 2 Flag フィレオ Flag カレー

秘匿CF方式 (分母) ２－３ A フィレオを評価していないユーザDの類似度が0になるため足されたことにならない ユーザB フィレオを評価していないユーザDの類似度が0になるため足されたことにならない iPhone フィレオ カレー A 5 ？ 2 B 1 3 C D iPhone フィレオ カレー Flag フィレオ 5 1 3 ユーザC iPhone フィレオ カレー Flag フィレオ 1 5 3 ユーザD iPhone フィレオ カレー Flag フィレオ 分母=S(A,B)+S(A,C)+S(A,D)=0.97+0.35+0=1.32