(57)【要約】【課題】情報の漏洩を防ぎつつ、高い精度で迅速にリコメンドを提供すること。【解決手段】サーバ１０が、属性毎にユーザ識別子を抽出して暗号化する（第１演算結果）。リコメンド支援装置３０が、選択肢毎にユーザ識別子を抽出して暗号化する（第２演算結果）。サーバ１０が、第２演算結果を暗号化する（第３演算結果）。リコメンド支援装置３０が、第１演算結果を暗号化する（第４演算結果）。リコメンド支援装置３０が、属性と選択肢との全ての組み合わせについて、第３演算結果と第４演算結果とで一致する暗号文の数を集計して第１集計値を求め、第３演算結果と第４演算結果とで一致する暗号文から１つ以上の暗号文をランダムに除いた複数の集合を作成し、当該複数の集合の各々について第４演算結果と一致する暗号文の数を集計して第２集計値を求め、第１集計値と第２集計値とに基づいて商品のリコメンド値を求めるためのパラメータを算出する。【選択図】図１
2013210933.tif 000002
【特許請求の範囲】
【請求項１】
端末のユーザを識別するためのユーザ識別子と、当該ユーザの属性を表す属性情報とが対応付けられたユーザ情報を記憶するサーバと、
前記ユーザによって選択された選択肢と、当該ユーザに対応する前記ユーザ識別子とが対応付けられた選択履歴を記憶するリコメンド支援装置と、
自装置のユーザの属性を表す属性情報を記憶する端末と
によって実行されるリコメンド支援方法であって、
前記サーバが、前記属性毎に当該属性に対応付けられたユーザ識別子を前記ユーザ情報から抽出し、当該ユーザ識別子を第１暗号化方式で暗号化した第１演算結果を前記リコメンド支援装置に送信する第１演算ステップと、
前記リコメンド支援装置が、前記選択肢毎に当該選択肢に対応付けられたユーザ識別子を前記選択履歴から抽出し、当該ユーザ識別子を前記第１暗号化方式で暗号化した第２演算結果を前記サーバに送信する第２演算ステップと、
前記サーバが、前記リコメンド支援装置から受信した第２演算結果を前記第１暗号化方式で暗号化した第３演算結果を前記リコメンド支援装置に送信する第３演算ステップと、
前記リコメンド支援装置が、前記サーバから受信した第１演算結果を前記第１暗号化方式で暗号化した第４演算結果を算出する第４演算ステップと、
前記リコメンド支援装置が、前記属性と前記選択肢との全ての組み合わせについて、前記第３演算結果と前記第４演算結果とで一致する暗号文の数を集計して第１集計値を求める第１集計ステップと、
前記リコメンド支援装置が、前記属性と前記選択肢との全ての組み合わせについて、前記第３演算結果と前記第４演算結果とで一致する暗号文から１つ以上の暗号文をランダムに除いた複数の集合を作成し、当該複数の集合の各々について前記第４演算結果と一致する暗号文の数を集計して第２集計値を求める第２集計ステップと、
前記リコメンド支援装置が、前記第１集計値と前記第２集計値とに基づいて前記商品に対応するリコメンド値を求めるためのパラメータを算出するパラメータ算出ステップと
を有することを特徴とするリコメンド支援方法。
【請求項２】
前記端末が、自装置に記憶された属性情報を加法準同型性を満たす第２暗号化方式で暗号化した暗号化属性情報を前記リコメンド支援装置に送信する属性情報暗号化ステップと、
前記リコメンド支援装置が、前記暗号化属性情報を前記端末から受信し、前記パラメータ算出ステップにおいて算出されたパラメータと当該暗号化属性情報とに基づいて、前記リコメンド値を加法準同型性を満たす第３暗号化方式で暗号化した暗号化リコメンド値を算出し、当該暗号化リコメンド値を前記端末に送信するリコメンド値暗号化ステップと、
前記端末が、前記暗号化リコメンド値を前記リコメンド支援装置から受信し、当該暗号化リコメンド値を復号してリコメンド値を算出する復号ステップと
を有することを特徴とする請求項１に記載のリコメンド支援方法。
【請求項３】
前記サーバ及び前記リコメンド支援装置は、前記第１暗号化方式として冪剰余計算を用いて暗号化を行うことを特徴とする請求項１又は２に記載のリコメンド支援方法。
【請求項４】
前記第１演算ステップにおいて、前記サーバは、前記ユーザ識別子を一方向関数で演算してから冪剰余計算を行い、
前記第２演算ステップにおいて、前記リコメンド支援装置は、前記ユーザ識別子を一方向関数で演算してから冪剰余計算を行う
ことを特徴とする請求項３に記載のリコメンド支援方法。
【請求項５】
前記第１演算ステップにおいて、前記サーバは、前記第１演算結果に含まれる暗号文を並べ替えて前記リコメンド支援装置に送信し、
前記第３演算ステップにおいて、前記サーバは、前記第３演算結果に含まれる暗号文を並べ替えて前記リコメンド支援装置に送信する
ことを特徴とする請求項１乃至４のいずれかに記載のリコメンド支援方法。
【請求項６】
前記リコメンド値暗号化ステップにおいて、前記リコメンド支援装置は、前記第３暗号化方式として加法準同型性を満たす冪剰余計算を用いて前記リコメンド値を暗号化することを特徴とする請求項２乃至４のいずれかに記載のリコメンド支援方法。
【請求項７】
端末のユーザを識別するためのユーザ識別子と、当該ユーザの属性を表す属性情報とが対応付けられたユーザ情報を記憶するユーザ情報記憶手段と、前記属性毎に当該属性に対応付けられたユーザ識別子を前記ユーザ情報から抽出し、当該ユーザ識別子を第１暗号化方式で暗号化した第１演算結果を外部に送信する第１演算手段と、外部から受信した第２演算結果を前記第１暗号化方式で暗号化した第３演算結果を外部に送信する第３演算手段とを有するサーバとの間、及び、
自装置のユーザの属性を表す属性情報を記憶する属性情報記憶手段と、当該属性情報を加法準同型性を満たす第２暗号化方式で暗号化した暗号化属性情報を外部に送信する属性情報暗号化手段と、暗号化リコメンド値を外部から受信し、当該暗号化リコメンド値を復号してリコメンド値を算出する復号手段とを有する端末との間
で通信を行う通信手段と、
前記ユーザによって選択された選択肢と、当該ユーザに対応する前記ユーザ識別子とが対応付けられた選択履歴を記憶する選択履歴記憶手段と、
前記選択肢毎に当該選択肢に対応付けられたユーザ識別子を前記選択履歴から抽出し、当該ユーザ識別子を前記第１暗号化方式で暗号化した第２演算結果を前記サーバに送信する第２演算手段と、
前記サーバから受信した第１演算結果を前記第１暗号化方式で暗号化した第４演算結果を算出する第４演算手段と、
前記属性と前記選択肢との全ての組み合わせについて、前記第３演算結果と前記第４演算結果とで一致する暗号文の数を集計して第１集計値を求める第１集計手段と、
前記属性と前記選択肢との全ての組み合わせについて、前記第３演算結果と前記第４演算結果とで一致する暗号文から１つ以上の暗号文をランダムに除いた複数の集合を作成し、当該複数の集合の各々について前記第４演算結果と一致する暗号文の数を集計して第２集計値を求める第２集計手段と、
前記第１集計値と前記第２集計値とに基づいて前記商品に対応するリコメンド値を求めるためのパラメータを算出するパラメータ算出手段と
を有することを特徴とするリコメンド支援装置。
【請求項８】
前記暗号化属性情報を前記端末から受信し、前記パラメータ算出手段によって算出されたパラメータと当該暗号化属性情報とに基づいて、前記リコメンド値を加法準同型性を満たす第３暗号化方式で暗号化した暗号化リコメンド値を算出し、当該暗号化リコメンド値を前記端末に送信するリコメンド値暗号化手段を有することを特徴とする請求項７に記載のリコメンド支援装置。
【請求項９】
端末のユーザを識別するためのユーザ識別子と、当該ユーザの属性を表す属性情報とが対応付けられたユーザ情報を記憶するユーザ情報記憶手段と、前記属性毎に当該属性に対応付けられたユーザ識別子を前記ユーザ情報から抽出し、当該ユーザ識別子を第１暗号化方式で暗号化した第１演算結果を外部に送信する第１演算手段と、外部から受信した第２演算結果を前記第１暗号化方式で暗号化した第３演算結果を外部に送信する第３演算手段とを有するサーバとの間、及び、
自装置のユーザの属性を表す属性情報を記憶する属性情報記憶手段と、当該属性情報を加法準同型性を満たす第２暗号化方式で暗号化した暗号化属性情報を外部に送信する属性情報暗号化手段と、暗号化リコメンド値を外部から受信し、当該暗号化リコメンド値を復号してリコメンド値を算出する復号手段とを有する端末との間
で通信を行う通信手段を有するコンピュータを、
前記ユーザによって選択された選択肢と、当該ユーザに対応する前記ユーザ識別子とが対応付けられた選択履歴を記憶する選択履歴記憶手段と、
前記選択肢毎に当該選択肢に対応付けられたユーザ識別子を前記選択履歴から抽出し、当該ユーザ識別子を前記第１暗号化方式で暗号化した第２演算結果を前記サーバに送信する第２演算手段と、
前記サーバから受信した第１演算結果を前記第１暗号化方式で暗号化した第４演算結果を算出する第４演算手段と、
前記属性と前記選択肢との全ての組み合わせについて、前記第３演算結果と前記第４演算結果とで一致する暗号文の数を集計して第１集計値を求める第１集計手段と、
前記属性と前記選択肢との全ての組み合わせについて、前記第３演算結果と前記第４演算結果とで一致する暗号文から１つ以上の暗号文をランダムに除いた複数の集合を作成し、当該複数の集合の各々について前記第４演算結果と一致する暗号文の数を集計して第２集計値を求める第２集計手段と、
前記第１集計値と前記第２集計値とに基づいて前記商品に対応するリコメンド値を求めるためのパラメータを算出するパラメータ算出手段
として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ユーザの属性に応じたリコメンドを行う技術に関する。
【背景技術】
【０００２】
商品に関する情報をコンパクト且つ迅速に提供することは、商品の販売において重要である。また、計算機の高速化、記憶装置の大容量化、統計処理技術の発展等に伴い、近年では顧客の属性や購買行動の統計的な分析に基づいた商品の推薦（以下、リコメンドという。）の有用性が注目されている。
しかし、小規模な商店などでは、適切なリコメンドを行うのに十分な売上記録を保有しているとは限らない。売上記録が少ないと、リコメンドの精度が低下してしまうコールドスタート問題と呼ばれる状況に陥りやすい。また、商店へは、該当する売上記録のない新規の客もやってくる。
【０００３】
このような環境においては、商店が、大量の情報を保有する組織と連携してリコメンドを行うことが有用であると考えられる。例えば、携帯電話の通信サービスを提供する通信事業者や、電子マネーの発行者など、個人の属性情報（性別、住所、年齢など）を管理する事業者と、商品の売上記録を保有する商店とが連携することにより、商店への来訪客の属性に応じたリコメンドを行うことが可能になる。しかし、プライバシ保護への要求が高まってきている昨今、個人の属性情報の取扱いには慎重さが求められる。
そこで、暗号化技術や統計的開示制御技術などを用いたプライバシ保護データマイニング（ＰＰＤＭ）技術が提案されている。ＰＰＤＭ技術を適切に用いることにより、組織の枠を超えたリコメンドを安全に提供することが可能になると期待される。例えば、非特許文献１、２では、垂直分割データベースにおいて各データベースが互いにデータを開示し合うことなくベイズアプローチによる識別を行う技術が提案されている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Vaidya, J., Kantarcioglu, M. and Clifton, C. :Privacy-preserving Naive Bayes classication,The VLDB Journal, Vol. 17, pp. 879-898 (2008).
【非特許文献２】菊池浩明，香川大介，石井一彦，寺田雅之，本郷節之，組織間プライバシー保護データマイニングの考察，電子情報通信学会暗号と情報セキュリティシンポジウム2010，pp. 1-5 (2010).
【非特許文献３】Thomas P. Minka, : Estimating a Dirichlet distribution, 2000 revised 2003, 2009,http://research.microsoft.com/en-us/um/people/minka/papers/dirichlet/
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上記の従来技術を用いて来訪客へのリコメンドを実施することは実用上容易ではない。その主な理由として、来訪客のプライバシ保護の問題、精度の問題、学習と識別にかかる計算コストの問題が挙げられる。すなわち、１）従来技術はプロバイダ・商店間でのデータ開示を防止するが、リコメンドを受ける来訪客のプライバシを保護する手段が十分でないこと、２）スムージング最適化などの識別精度向上のための方法が適用困難であり、過剰適合などによるリコメンド精度の低下が避けられないこと、３）来訪客へのリコメンドの度に商店がプロバイダと計算コストの高いマルチパーティ計算を行う必要があること、などの問題がある。
そこで、本発明は、情報の漏洩を防ぎつつ、高い精度で迅速にリコメンドを提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明は、端末のユーザを識別するためのユーザ識別子と、当該ユーザの属性を表す属性情報とが対応付けられたユーザ情報を記憶するサーバと、前記ユーザによって選択された選択肢と、当該ユーザに対応する前記ユーザ識別子とが対応付けられた選択履歴を記憶するリコメンド支援装置と、自装置のユーザの属性を表す属性情報を記憶する端末とによって実行されるリコメンド支援方法であって、前記サーバが、前記属性毎に当該属性に対応付けられたユーザ識別子を前記ユーザ情報から抽出し、当該ユーザ識別子を第１暗号化方式で暗号化した第１演算結果を前記リコメンド支援装置に送信する第１演算ステップと、前記リコメンド支援装置が、前記選択肢毎に当該選択肢に対応付けられたユーザ識別子を前記選択履歴から抽出し、当該ユーザ識別子を前記第１暗号化方式で暗号化した第２演算結果を前記サーバに送信する第２演算ステップと、前記サーバが、前記リコメンド支援装置から受信した第２演算結果を前記第１暗号化方式で暗号化した第３演算結果を前記リコメンド支援装置に送信する第３演算ステップと、前記リコメンド支援装置が、前記サーバから受信した第１演算結果を前記第１暗号化方式で暗号化した第４演算結果を算出する第４演算ステップと、前記リコメンド支援装置が、前記属性と前記選択肢との全ての組み合わせについて、前記第３演算結果と前記第４演算結果とで一致する暗号文の数を集計して第１集計値を求める第１集計ステップと、前記リコメンド支援装置が、前記属性と前記選択肢との全ての組み合わせについて、前記第３演算結果と前記第４演算結果とで一致する暗号文から１つ以上の暗号文をランダムに除いた複数の集合を作成し、当該複数の集合の各々について前記第４演算結果と一致する暗号文の数を集計して第２集計値を求める第２集計ステップと、前記リコメンド支援装置が、前記第１集計値と前記第２集計値とに基づいて前記商品に対応するリコメンド値を求めるためのパラメータを算出するパラメータ算出ステップとを有することを特徴とするリコメンド支援方法を提供する。
【０００７】
前記リコメンド支援方法において、前記端末が、自装置に記憶された属性情報を加法準同型性を満たす第２暗号化方式で暗号化した暗号化属性情報を前記リコメンド支援装置に送信する属性情報暗号化ステップと、前記リコメンド支援装置が、前記暗号化属性情報を前記端末から受信し、前記パラメータ算出ステップにおいて算出されたパラメータと当該暗号化属性情報とに基づいて、前記リコメンド値を加法準同型性を満たす第３暗号化方式で暗号化した暗号化リコメンド値を算出し、当該暗号化リコメンド値を前記端末に送信するリコメンド値暗号化ステップと、前記端末が、前記暗号化リコメンド値を前記リコメンド支援装置から受信し、当該暗号化リコメンド値を復号してリコメンド値を算出する復号ステップとを有するようにしてもよい。
【０００８】
また、前記リコメンド支援方法において、前記サーバ及び前記リコメンド支援装置は、前記第１暗号化方式として冪剰余計算を用いて暗号化を行うようにしてもよい。
【０００９】
また、前記第１演算ステップにおいて、前記サーバは、前記ユーザ識別子を一方向関数で演算してから冪剰余計算を行い、前記第２演算ステップにおいて、前記リコメンド支援装置は、前記ユーザ識別子を一方向関数で演算してから冪剰余計算を行うようにしてもよい。
【００１０】
また、前記第１演算ステップにおいて、前記サーバは、前記第１演算結果に含まれる暗号文を並べ替えて前記リコメンド支援装置に送信し、前記第３演算ステップにおいて、前記サーバは、前記第３演算結果に含まれる暗号文を並べ替えて前記リコメンド支援装置に送信するようにしてもよい。
【００１１】
また、前記リコメンド値暗号化ステップにおいて、前記リコメンド支援装置は、前記第３暗号化方式として加法準同型性を満たす冪剰余計算を用いて前記リコメンド値を暗号化するようにしてもよい。
【００１２】
また、本発明は、端末のユーザを識別するためのユーザ識別子と、当該ユーザの属性を表す属性情報とが対応付けられたユーザ情報を記憶するユーザ情報記憶手段と、前記属性毎に当該属性に対応付けられたユーザ識別子を前記ユーザ情報から抽出し、当該ユーザ識別子を第１暗号化方式で暗号化した第１演算結果を外部に送信する第１演算手段と、外部から受信した第２演算結果を前記第１暗号化方式で暗号化した第３演算結果を外部に送信する第３演算手段とを有するサーバとの間、及び、自装置のユーザの属性を表す属性情報を記憶する属性情報記憶手段と、当該属性情報を加法準同型性を満たす第２暗号化方式で暗号化した暗号化属性情報を外部に送信する属性情報暗号化手段と、暗号化リコメンド値を外部から受信し、当該暗号化リコメンド値を復号してリコメンド値を算出する復号手段とを有する端末との間で通信を行う通信手段と、前記ユーザによって選択された選択肢と、当該ユーザに対応する前記ユーザ識別子とが対応付けられた選択履歴を記憶する選択履歴記憶手段と、前記選択肢毎に当該選択肢に対応付けられたユーザ識別子を前記選択履歴から抽出し、当該ユーザ識別子を前記第１暗号化方式で暗号化した第２演算結果を前記サーバに送信する第２演算手段と、前記サーバから受信した第１演算結果を前記第１暗号化方式で暗号化した第４演算結果を算出する第４演算手段と、前記属性と前記選択肢との全ての組み合わせについて、前記第３演算結果と前記第４演算結果とで一致する暗号文の数を集計して第１集計値を求める第１集計手段と、前記属性と前記選択肢との全ての組み合わせについて、前記第３演算結果と前記第４演算結果とで一致する暗号文から１つ以上の暗号文をランダムに除いた複数の集合を作成し、当該複数の集合の各々について前記第４演算結果と一致する暗号文の数を集計して第２集計値を求める第２集計手段と、前記第１集計値と前記第２集計値とに基づいて前記商品に対応するリコメンド値を求めるためのパラメータを算出するパラメータ算出手段とを有することを特徴とするリコメンド支援装置を提供する。
前記リコメンド支援装置において、前記暗号化属性情報を前記端末から受信し、前記パラメータ算出手段によって算出されたパラメータと当該暗号化属性情報とに基づいて、前記リコメンド値を加法準同型性を満たす第３暗号化方式で暗号化した暗号化リコメンド値を算出し、当該暗号化リコメンド値を前記端末に送信するリコメンド値暗号化手段を有するようにしてもよい。
【００１３】
また、本発明は、端末のユーザを識別するためのユーザ識別子と、当該ユーザの属性を表す属性情報とが対応付けられたユーザ情報を記憶するユーザ情報記憶手段と、前記属性毎に当該属性に対応付けられたユーザ識別子を前記ユーザ情報から抽出し、当該ユーザ識別子を第１暗号化方式で暗号化した第１演算結果を外部に送信する第１演算手段と、外部から受信した第２演算結果を前記第１暗号化方式で暗号化した第３演算結果を外部に送信する第３演算手段とを有するサーバとの間、及び、自装置のユーザの属性を表す属性情報を記憶する属性情報記憶手段と、当該属性情報を加法準同型性を満たす第２暗号化方式で暗号化した暗号化属性情報を外部に送信する属性情報暗号化手段と、暗号化リコメンド値を外部から受信し、当該暗号化リコメンド値を復号してリコメンド値を算出する復号手段とを有する端末との間で通信を行う通信手段を有するコンピュータを、前記ユーザによって選択された選択肢と、当該ユーザに対応する前記ユーザ識別子とが対応付けられた選択履歴を記憶する選択履歴記憶手段と、前記選択肢毎に当該選択肢に対応付けられたユーザ識別子を前記選択履歴から抽出し、当該ユーザ識別子を前記第１暗号化方式で暗号化した第２演算結果を前記サーバに送信する第２演算手段と、前記サーバから受信した第１演算結果を前記第１暗号化方式で暗号化した第４演算結果を算出する第４演算手段と、前記属性と前記選択肢との全ての組み合わせについて、前記第３演算結果と前記第４演算結果とで一致する暗号文の数を集計して第１集計値を求める第１集計手段と、前記属性と前記選択肢との全ての組み合わせについて、前記第３演算結果と前記第４演算結果とで一致する暗号文から１つ以上の暗号文をランダムに除いた複数の集合を作成し、当該複数の集合の各々について前記第４演算結果と一致する暗号文の数を集計して第２集計値を求める第２集計手段と、前記第１集計値と前記第２集計値とに基づいて前記商品に対応するリコメンド値を求めるためのパラメータを算出するパラメータ算出手段として機能させるためのプログラムを提供する。
【発明の効果】
【００１４】
本発明によれば、情報の漏洩を防ぎつつ、高い精度で迅速にリコメンドを提供することができる。
【図面の簡単な説明】
【００１５】
【図１】リコメンド支援システム１の構成を示す図。
【図２】リコメンド支援装置３０のハードウェア構成を示す図。
【図３】サーバ１０のハードウェア構成を示す図。
【図４】端末５０のハードウェア構成を示す図。
【図５】実施形態の動作を示すシーケンス図。
【図６】１ヶ月あたりの売上人数と処理時間との関係を示す図。
【図７】商店が利用できるＰＣの台数と、リコメンドの遅延との関係を示す図。
【発明を実施するための形態】
【００１６】
（１）実施形態の構成
図１は、本発明の一実施形態に係るリコメンド支援システム１の構成を示す図である。リコメンド支援システム１は、サーバ１０、リコメンド支援装置３０および端末５０を有する。
図２は、リコメンド支援装置３０のハードウェア構成を示す図である。リコメンド支援装置３０は、ＣＰＵ（Central Processing Unit）などの演算装置とＲＯＭ（Read Only Memory）及びＲＡＭ（Random Access Memory）などの記憶装置とを備えた制御部３０１と、ハードディスク装置などの記憶装置を備えた記憶部３０２と、通信インターフェースを備えた通信部３０３とを備える。記憶部３０２には、ＯＳ（Operating System）やアプリケーションプログラムが記憶されており、制御部３０１がこれらのプログラムを実行することによってリコメンド支援装置３０の動作を制御する。制御部３０１は、通信部３０３を制御することにより、サーバ１０及び端末５０との間で通信を行う。
【００１７】
図３は、サーバ１０のハードウェア構成を示す図である。サーバ１０も、リコメンド支援装置３０と同様に、制御部１０１と記憶部１０２と通信部１０３とを有する。制御部１０１が記憶部１０２に記憶されたプログラムを実行することによってサーバ１０の動作を制御する。制御部１０１は、通信部１０３を制御することにより、リコメンド支援装置３０との間で通信を行う。
【００１８】
図４は、端末５０のハードウェア構成を示す図である。端末５０は、ＣＰＵなどの演算装置とＲＯＭ及びＲＡＭなどの記憶装置とを備えた制御部５０１と、ＳＲＡＭ（Static Random Access Memory）などの記憶装置を備えた記憶部５０２と、アンテナや無線通信インターフェースを備えた通信部５０３と、スピーカ、マイクロホン及び音声処理回路を備えた音声入出力部５０４と、複数のキーやタッチスクリーンなどの操作子を備えた操作部５０５と、液晶パネルや液晶駆動回路を備えた表示部５０６とを備えている。記憶部５０２には、ＯＳやアプリケーションプログラムが記憶されており、制御部５０１がこれらのプログラムを実行することによって端末５０の動作を制御する。また、制御部５０１は、操作部５０５が受け付けたユーザの操作に応じて通信部５０３を制御することにより、リコメンド支援装置３０との間で通信を行う。
【００１９】
本実施形態では、プロバイダと商店と来訪客の三者を想定する。プロバイダは、例えば、先払い式又は後払い式の電子マネーやクレジットカード等の決済業務に関連する情報を管理する事業者や、携帯電話等の通信サービスを提供する通信事業者等であり、サーバ１０を運用する。商店は、リコメンド支援装置３０を運用する。リコメンド支援装置３０は、店舗に備えられていてもよいし、電子商取引における仮想店舗のウェブサイトを運営するサーバであってもよい。来訪客は、端末５０を所持して商店にやってきた客、又は、端末５０から仮想店舗のウェブサイトにアクセスした客である。
三者の各々が保有する情報の構成は次のとおりである。なお、情報の具体的な内容は一例にすぎない。
【００２０】
プロバイダは、ユーザ情報（表１）を保有する。ユーザ情報は、プロバイダとの間で電子マネー、クレジットカード、通信サービス等の利用に関する契約を結んだユーザを識別するためのユーザ識別子と、当該ユーザの属性（ユーザの年代、性別、住所など）を表す属性情報とが対応付けられた情報である。
【表１】
2013210933.tif 000003
【００２１】
商店は、売上記録（表２）を保有する。売上記録は、ユーザによって購入された商品を表す商品情報と、当該ユーザに対応するユーザ識別子とを対応付けた情報である。この例では、商品は本であり、商品情報は、本Ａと本Ｂの２種類である。
なお、売上記録は、本発明に係る選択履歴の一例である。本発明に係る選択履歴は、ユーザによって選択された選択肢と、当該ユーザに対応するユーザ識別子とが対応付けられた情報である。選択肢とは、例えば、ユーザが購入した商品でもよいし、購入する商品の候補としてユーザが選択した商品でもよいし、複数種類の試供品のうちユーザが選択した試供品でもよい。また、選択肢は、物品に限定されず、例えば、通信事業者が提供する通信サービスや、旅行代理店が販売するツアー等、有形又は無形のサービスでもよい。つまり、本発明に係る選択肢とは、物品、情報、サービス等、商店からユーザに提供されるあらゆるものを含む概念であり、また、ユーザが選択した選択肢は、有償で提供されてもよいし、無償で提供されてもよい。
【表２】
2013210933.tif 000004
【００２２】
来訪客は、自身の属性を表す属性情報（表３）を保有する。なお、端末５０は、サーバ１０を運用するプロバイダとの間で利用契約が結ばれた端末でもよいし、他のプロバイダとの間で利用契約が結ばれた端末でもよいし、どのプロバイダとも利用契約が結ばれていない端末でもよい。つまり、サーバ１０を運用するプロバイダは、来訪客のユーザ識別子に対応するユーザ情報を保有していなくてもよく、端末５０がユーザの属性情報を保有さえしていれば、プロバイダとの利用契約の有無は問わない。
【表３】
2013210933.tif 000005
【００２３】
2013210933.tif 000006
【表４】
2013210933.tif 000007
【００２４】
2013210933.tif 000008
【００２５】
2013210933.tif 000009
【表５】
2013210933.tif 000010
【００２６】
2013210933.tif 000011
【００２７】
2013210933.tif 000012
【表６】
2013210933.tif 000013
2013210933.tif 000014
【００２８】
（２）リコメンドに要求される条件
仮に情報漏洩に対する対策を講じる必要がないならば、来訪客の属性に基づくリコメンドは次のようにして達成可能である。
＜手順１＞  商店又はプロバイダは、プロバイダが保有する属性情報と商店が保有する商品情報をユーザ識別子によって対応付ける。
＜手順２＞  商店は、商品情報と対応付けられた属性情報から、ユーザの属性とユーザが購入した商品との関係を統計的に推定する。
＜手順３＞  来訪客は、来店時に商店に対して自身の属性を提示する。
＜手順４＞  商店は、手順３で推定した属性と商品との関係と、来訪客から提示された属性とから、来訪客が購入する可能性が高い商品を推定し、来訪客に対して推薦する。
＜手順５＞  来訪客がプロバイダのユーザであった場合には、来訪客が商品を購入したならば、商店は、来訪客からユーザ識別子の提供を受け、売上記録を追加する。
【００２９】
しかし、プロバイダと商店と来訪客は、それぞれの立場の違いから、リコメンドに対して次のような条件を要求する。プロバイダはユーザから預かっているユーザ情報の漏洩を防ぎたい。商店は、的確なリコメンドを提供したいが、売上記録の漏洩を防ぎたい。来訪客は、初めて立ち寄った商店でも的確で迅速なリコメンドを受けたいが、自身の属性の漏洩を防ぎたい。また、プロバイダと商店は、ユーザ数や売上記録数が増加した場合でも計算コストを抑えたい。表７は、これらの要求条件をまとめたものである。
【表７】
2013210933.tif 000015
【００３０】
（３）従来方式
ここで、プライバシ保護データマイニングの従来方式の問題点について説明する。
表７で示した要求条件を満たした上でリコメンドを実現するためには、垂直分割データベースにおいて各データベースが保持する値を互いに開示することなくリコメンド値を計算する必要がある。その実現方法としては、決定木に基づく方法、協調フィルタリングに基づく方法、k-meanクラスタリングに基づく方法などが挙げられるが、ここでは、計算コストやコールドスタート問題（売上記録が少ない状況や来訪客が新規の客であった場合などに、リコメンドの精度が低下してしまったり、リコメンド値がそもそも計算できなくなってしまったりするという問題）の回避などの観点から、ベイズアプローチに基づく方法である垂直分割プライバシ保護ナイーブベイズ識別器に着目する。
垂直分割プライバシ保護ナイーブベイズ識別器は、垂直分割された複数のデータベース
2013210933.tif 000016
の元でベイズアプローチによる識別を行う。その構成法は、Vaidyaら（非特許文献１）、および菊池ら（非特許文献２）によってそれぞれ提案されている。以下、両方式による識別器の構成について説明する。
【００３１】
2013210933.tif 000017
【００３２】
2013210933.tif 000018
【００３３】
2013210933.tif 000019
【００３４】
非特許文献２で提案された方式（以下、文献２方式という。）では、文献１方式と同様に、式（１）、式（２）のモデルに従って識別器を構成する。ただし、文献１方式の識別
2013210933.tif 000020
つきセキュアマッチングを用いてこれを計算する。チャフつきセキュアマッチングは、セキュアマッチング（たとえば、Agrawal, R., Evmievski, A. and Srikant, R.: Information sharing across private databases,Proceedings of the 2003 ACM SIGMOD international conference on Management of data,SIGMOD '03, New York, NY, USA, ACM, pp. 86[97 (2003).）の変種であり、送信暗号文を確率的にダミーデータ（チャフ）に挿げ替えて送信することにより、マッチング結果に人為的なノイズを与える。チャフつきセキュアマッチングの演算結果はチャフによる確率的なバイアスを含むため、マルチパーティ計算を用いてこのバイアスを復元する。これにより、プロバイダが保持する顧客の集合と商店が保持する顧客の集合が一致しない（双方のデータベースが同期していない）場合や、それぞれのデータベースに欠損値がある場合などの効率を改善している。
【００３５】
2013210933.tif 000021
【００３６】
ただし、この仮定が成立しない状況においても、商店の売上記録に対して、プロバイダのユーザのうち商店の顧客以外ユーザのレコードをダミーレコードとして追加する事前処理によりレコード数を仮想的に一致させれば、文献１方式を適用することが可能である。
なお、ダミーレコードを追加する代わりにプロバイダのユーザ情報から商店の顧客以外のユーザのレコードを除去する方法でもレコード数を一致させることが可能であり、且つ、処理対象のデータ量を大幅に削減することが可能である。しかし、これは安全性の面で問題がある。すなわち、プロバイダのユーザ情報から不要なレコードを削除するために、プロバイダに対して商店の顧客リストを開示する必要がある。すなわち、プロバイダに対し、どのユーザがその商店で買い物をしたことがあるかという情報が開示される。そのため、商店の営業上の秘密がプロバイダに対して開示されるのみならず、商店の顧客のプライバシも保護されなくなる。
【００３７】
そのため、これ以降の文献１方式に関する説明においては、あらかじめ商店の売上記録に対して、プロバイダのユーザのうち商店の顧客以外のユーザのレコードをダミーレコードとして追加する事前処理が施されているものとする。
なお、文献２方式は秘匿内積計算ではなく、（チャフつき）セキュアマッチングに基づくことから、データベースの同期の問題は生じない。
【００３８】
（４．２）安全性
次に、プロバイダ、商店、来訪客のそれぞれに対する安全性について説明する。なお、以下の説明においては、離散対数問題や準同型暗号などの暗号プリミティブは十分に安全であるものとする。
まず、文献１方式は、前述のデータベースの同期が保たれているという仮定のもとでは、商店による来訪客のリコメンド値算出の過程において、商店が保有する売上記録がプロバイダに開示されることはない。また、プロバイダが保有するユーザ情報について、来訪客へのリコメンド結果自体より多くの情報が商店や来訪客に対して開示されることはない。以上のことから、プロバイダおよび商店の情報は十分に安全に保護されると考えられる。
しかし、その一方で、来訪客のプライバシはプロバイダや商店に対して保護されない。式（１）のマルチパーティ計算は、プロバイダと商店との間で実施される。来訪客の属性に応じたリコメンドを行うためには、マルチパーティ計算の入力とするためにをプロバイダか商店のいずれかに開示する必要がある。
【００３９】
文献２方式は、プロバイダと商店間でチャフつきセキュアマッチングを実施した後に、マルチパーティ計算を用いてリコメンド値を算出する。チャフつきセキュアマッチングの結果は、最終的なリコメンド結果より多くの情報を含む（チャフの割合に依存する。チャフの割合が多ければ開示される情報量は少なくなるが、精度に悪影響を与える。）ため、商店に開示されるプロバイダの情報は、文献１方式よりも多くなる。そのため、文献１方式と比較して、商店がユーザ情報の内容を統計的に推定しやすくなると考えられる。
しかし、実際に扱われる情報を考慮すると、商店が入手可能なのは、たかだか（仮にチャフの割合を０としても）ある商品を購入した男性は何人かなどの集計値から構成される、Ｖ×Ｌの集計表である。集計値がごく小数になるなどの特殊な場合を除き、集計表から個人の情報を特定することは困難であると言われている（たとえば、瀧  敦弘  集計表におけるセル秘匿問題とその研究動向，統計数理， Vol. 51, pp. 337-350 (2003))。
なお、来訪客のプライバシに関しては、文献２方式も文献１方式と同様に保護されない。リコメンド値の算出にあたり、来訪客の属性情報はマルチパーティ計算のためにプロバイダもしくは商店に開示されることになる。
【００４０】
（４．３）精度
次に、精度に関して説明する。文献１方式、文献２方式のいずれも、条件付き確率を用いた最尤推定である。Play Tennisデータセットを用いて実験を行ったところ、提案方式では79%の正解率が得られたが、文献１、２の方式では36%の正解率しか得られなかった。なお、文献２は、実際には安全性を確保するためにチャフを混入するため、さらに精度が低下する懸念がある（精度低下は混入させるチャフの量による）。
【００４１】
2013210933.tif 000022
【００４２】
文献１方式は、プロバイダと商店が、ユーザの人数Ｎだけの秘匿内積計算を、属性の区分の総数Ｖと商品の種類の数Ｌだけ繰り返す必要がある。これは合計で２ＮＶＬ回の冪剰余計算を必要とする。一方、文献２方式は、合計でＮＷ＋ＭＧ＋ＭＧＶ＋ＮＷＬ回の冪剰余計算を必要とする。すなわち、プロバイダはＮ人Ｗ項目のユーザ情報についてＮＷ回の冪剰余計算を行い、商店はＭ人Ｇ種類の売上記録についてＭＧ回の冪剰余計算を行い、互いに計算結果を交換する。その後、プロバイダは商店から受け取ったデータをＶ回繰り返してＭＧＶ回の冪剰余計算を行い、商店はプロバイダから受け取ったデータをＬ回繰り返してＮＷＬ回の冪剰余計算を行う。例えば、１００万人（Ｎ）の会員を有するプロバイダと、１００種類（Ｌ）の商品からリコメンドを提供したい商店との間で学習を行うとすると、１回の冪剰余計算に要する時間が１．５ｍｓの計算機を用いた場合、文献１方式では１００日以上かかってしまうが、文献２方式では１０日以内で済む。
【００４３】
式（１）によるリコメンド値の算出は、来訪客が商店に来店するたびに実施される。そのため、この計算は来訪客の来店後、可能な限り速やかに行う必要がある。識別の処理に何分も要するようでは、推薦商品を提示する頃には来訪客は既に買い物を終えてしまっており、リコメンドが全く意味をなさなくなる可能性がある。しかし、学習結果と来訪客の属性情報を用いた識別過程では、文献１方式も文献２方式も来訪客からプロバイダまで含めてのマルチパーティ計算が必要である。来訪客の端末にリコメンドを提示する度にマルチパーティ計算を行うのは、レスポンスの観点から現実的であるとは言えない。
【００４４】
（５）実施形態の計算モデル
本実施形態の計算モデルについて説明する。
第１に、精度の問題に対しては、経験ベイズ法の導入により精度の向上を図る。しかし、経験ベイズ法で一般に用いられる交差検定は、或る特定のレコードを除去した差分データを用いて処理を行うため、差分データを用いた残差開示により個人データが特定され得るという問題が発生する。そこで、本実施形態では、セキュアマッチングで得られる秘匿されたデータからパラメータ学習を行うことによって、差分データを用いずに経験ベイズ法に基づくベイズ識別器を構築する。
第２に、来訪客のプライバシ保護の問題に対しては、来訪客の属性情報を商店やプロバイダに開示することなくリコメンドを実施するために、秘匿内積計算を導入する。
【００４５】
（５．１）計算モデルの概要
最初に、経験ベイズ法に基づくベイズ識別器の計算モデルについて、その概要を説明する。
経験ベイズ法は、ベイズ推定における事前確率の問題を回避する方法の一つである。経験ベイズ法は、パラメトリックなベイズモデルにおいて、その事前確率を客観的に設定するために、モデルのパラメータに加えて、ハイパーパラメータと呼ぶ未知変数を導入する。経験ベイズ法では、このハイパーパラメータにも、観測したデータから客観的に適切な値を設定することで高い精度が得られる。
【００４６】
2013210933.tif 000023
【００４７】
2013210933.tif 000024
【００４８】
2013210933.tif 000025
【００４９】
2013210933.tif 000026
【００５０】
2013210933.tif 000027
【００５１】
2013210933.tif 000028
【００５２】
2013210933.tif 000029
【００５３】
2013210933.tif 000030
【００５４】
2013210933.tif 000031
【００５５】
2013210933.tif 000032
【００５６】
2013210933.tif 000033
2013210933.tif 000034
【００５７】
2013210933.tif 000035
【００５８】
2013210933.tif 000036
【００５９】
2013210933.tif 000037
【００６０】
2013210933.tif 000038
2013210933.tif 000039
【００６１】
2013210933.tif 000040
【００６２】
2013210933.tif 000041
【００６３】
2013210933.tif 000042
2013210933.tif 000043
【００６４】
2013210933.tif 000044
【００６５】
2013210933.tif 000045
【００６６】
2013210933.tif 000046
【００６７】
2013210933.tif 000047
【００６８】
2013210933.tif 000048
【００６９】
2013210933.tif 000049
【００７０】
2013210933.tif 000050
【００７１】
2013210933.tif 000051
【００７２】
2013210933.tif 000052
【００７３】
2013210933.tif 000053
【００７４】
2013210933.tif 000054
【００７５】
2013210933.tif 000055
【００７６】
2013210933.tif 000056
【００７７】
（５．３）リコメンド値の算出式
最後に、リコメンド値の算出式について説明する。
本実施形態では、来訪客のプライバシを保護するために、リコメンド支援装置３０と端末５０との間で秘匿内積計算を行うが、冪剰余計算が必要になるため、リコメンドに遅延が生じる。そこで、端末５０で行う冪剰余計算は事前に済ませることによって、遅延を抑える。本実施形態では、プロバイダのユーザ数や売上記録の増加によらず、１つの商品の周辺尤度を１回の冪剰余計算で算出する。
【００７８】
2013210933.tif 000057
【００７９】
2013210933.tif 000058
【００８０】
（６）実施形態の動作
図５は、実施形態の動作を示すシーケンス図である。以下で説明する動作は、サーバ１０の制御部１０１とリコメンド支援装置３０の制御部３０１と端末５０の制御部５０１がそれぞれプログラムに記述された手順に従って実行する動作であるが、ここでは、図１に示した機能ブロックを動作の主体として説明する。
以下で説明する動作は、リコメンド支援装置３０に対して、リコメンド値算出の指示が入力されたことを契機として実行される。具体的には、当該指示が入力されたならば、リコメンド支援装置３０がサーバ１０に対してステップＳ０１の処理の開始を指示するとともに、リコメンド支援装置３０がステップＳ０２の処理を開始する。
【００８１】
なお、パラメータの算出（ステップＳ０１からＳ０７までの処理）は、リコメンド値算出の度に実行してもよいが、例えば1ヶ月といった間隔で定期的に実行してもよい。あるいは、第１集計値及び第２集計値に有意な変化が現れることが予想されるタイミングで、商店側の判断により随時、パラメータの算出を実行するようにしてもよい。例えば、新商品の発売後に或る程度の期間が経過した後に実行してもよいし、実際に特定の商品の売れ行きに変化が現れた場合に実行してもよい。このように定期的又は随時にパラメータを算出した場合、算出されたパラメータをリコメンド支援装置３０の記憶部３０２に記憶させておき、リコメンド支援装置３０に対してリコメンド値算出の指示が入力されたならば、記憶部３０２からパラメータを読み出して、ステップＳ０８以降の処理を実行する。
なお、ステップＳ０１からＳ０５までの内容は説明済みであるから、ここでは説明を省略する。
【００８２】
2013210933.tif 000059
【００８３】
2013210933.tif 000060
【００８４】
2013210933.tif 000061
【００８５】
2013210933.tif 000062
【００８６】
2013210933.tif 000063
【００８７】
（７）具体例
（７．１）Book-Crossingデータセット
Book-Crossingデータセット（以下、ＢＣＤＳという。）は、Book-Crossing communityにおける本の評価のデータセットである。このデータセットは、Cai-Nicolas Zieglerによって２００４年８月から９月のうちの４週間クローリングされたものであり、271,379冊の本に対する1,149,780件の評価値を含む。
ＢＣＤＳのユーザは匿名化されているが、年齢と居住地の情報は有している。本実験では、年齢については８０歳を超えるデータは取り除き、１０歳刻みの年代にして用いる。また、居住地については、国際標準化機構（ISO）によって公表されている２４９ヶ国の国名にして用いる。国名を割り当てる際は、まず、ISO3166-1における英語名（アメリカ合衆国の場合であればUnited Statesを含むデータに国名を割り当て、もしもISO3166-1における英語名を含まない場合は、ISO3166-1 alpha-3（アメリカ合衆国の場合であればUSA）を含むデータに国名を割り当てる。
【００８８】
ＢＣＤＳの評価値は１０点満点で付与されている。本具体例では、ユーザが５点を超える評価値を与えた本を、ユーザが満足した本であるとみなす。
本具体例では、それぞれの本ごとに満足したユーザの属性を学習しておき、未知のユーザの属性を元に、そのユーザが満足できる本を推薦できるかを計測する。本具体例では、一般的な三交差検定を用いて学習に用いるユーザとテストに用いるユーザとを分けて、リコメンドの精度を測定する。ＢＣＤＳには多くの評価値が得られているベストセラーの本もあれば、そうではない本もある。交差検定に用いるデータ数を確保するため、本具体例では、評価値が１０件を超える本（4,518種類）を対象とする。
【００８９】
表８は、ＢＣＤＳに対して文献１方式と本実施形態でリコメンドの実験を行った結果である。本実施形態は文献１方式より平均で1.5点高い評価値を得られた。
【表８】
2013210933.tif 000064
【００９０】
（７．２）Play-Tennisデータセット
表９に、Play-Tennisデータセットを示す（縦二重線の左側）。Play-Tennisデータセット（以下、ＰＴＤＳという。）は、１４日間のそれぞれの日付の属性の条件下において、テニスを行ったか休んだかを記したものである。
【表９】
2013210933.tif 000065
【００９１】
このＰＴＤＳを用いて、それぞれの属性の条件下においてテニスを行ったか休んだかを適切に識別できるか、本実施形態と文献１方式による精度を定量的に明らかにする。本具体例での精度の測定は、少ないデータから精度良く精度測定を行うため、1日ずつ順に抜き出したデータをテストデータとし、残りを学習データとする、Leave One Outを用いる。
【００９２】
ここで、ＰＴＤＳの日付を実施形態におけるユーザ識別子とみなし、属性（空模様、気温、湿度、風）を実施形態における属性情報Ｘとみなし、テニスを行ったか休んだかを実施形態における商品情報Ｙとみなす。すなわち、属性情報Ｘの項目は、空模様、気温、湿度、風の４種類であるから、属性情報Ｘの項目の数Ｗは４である。属性情報Ｘの区分は、空模様が３種類、気温が３種類、湿度が２種類、風が２種類の合計１０種類であるから、属性情報Ｘの区分の総数Ｖは１０である。すなわち、プロバイダは、Ｎ＝１４人、Ｗ＝４項目からなるユーザ情報を保有する。プロバイダが保有するユーザ識別子ｔは、長さＮ＝１４のベクトルである。プロバイダが保有する属性情報Ｘは、Ｎ＝１４行、Ｖ＝１０列のマトリクスである。
商店は、学習データに相当するデータを保有する。商店は、売上１人あたりＧ＝１種類の商品を含むＭ＝１３件の売上記録を保有する（Ｎ≠Ｍより、プロバイダと商店のデータは非同期である）。商店が保有するユーザ識別子ｕは、長さＭ＝１３のベクトルである。商店が保有する商品情報Ｙは、Ｍ＝１３行、Ｌ＝２列のマトリクスである。
2013210933.tif 000066
【００９３】
ＰＴＤＳに対する文献１方式と本実施形態による識別結果を表９（縦二重線の右側）に示す。ＢＣＤＳのときと同じく、文献１方式は、識別結果に偏りが見られる結果となった。この結果から、精度を定量的に示す正解率を算出する。識別結果については、識別が正解でリコメンドが「行った」である場合をTrue Positive、識別が不正解でリコメンドが「休んだ」である場合をFalse Negative、識別が不正解でリコメンドが「行った」である場合をFalse Positive、識別が正解でリコメンドが「休んだ」である場合をTrue Negativeとそれぞれ数える。正解率は、（True Positive + True Negative）／（True Positive＋False Negative＋False Positive＋True Negative）で求められる。表１０に、正解率の算出結果を示す。本実施形態は、文献１方式より１５％高い正解率を得られた。
【表１０】
2013210933.tif 000067
【００９４】
（７．３）計算コスト
本実施形態で想定しているデータの規模について、最近の電子マネー利用サービスの動向を鑑みて具体化する。ただし、電子マネーには、先払い式電子マネーと後払い式電子マネーがある。先払い式電子マネーは属性が正しく登録されているとは限らないことから、ここでは、利用者と支払者が一致すると考えられる後払い式電子マネーに着目する。
【００９５】
まず、ユーザ情報について、２０１０年３月末時点のユーザ数はＡ社が１４２０万人、Ｂ社が４８６万人、Ｃ社が１１０万人である。これより、ユーザ情報の数Ｎは、１００万〜１０００万人を想定する。ユーザの属性については、年代と性別と住所を想定し、属性情報Ｘの項目数Ｗは、３項目を想定する。また、年代は８区分、性別は２区分、住所は４７区分（都道府県）とし、属性情報Ｘの区分の総数Ｖは、５７種類を想定する。
【００９６】
次に、売上記録について、全国で１ヶ月に７８万６千箇所で１６８万件の電子マネー決済が行われていることから、１ヶ月１箇所あたりの売上情報の記録数の平均は２１８件である。この値は商店の規模、所在地、業種、来訪客のリピート率などにより大きく異なると考えられるため、売上記録に含まれる人数Ｍは、１００〜１０万人を想定する。商品の種類数については、飲食店のメニューはせいぜい１００種類も道程すれば十分かと考えられるが、コンビニエンスストアの商品は２５００種類ある。商店の規模、所在地、業種などにより大きく異なると考えられるため、商品の種類数Ｌは、１００〜１万種類を想定する。また、全国で１回あたりの決済金額は８３０円であるので、一度の来店で購入する商品は数種類であると考えられる。売上記録を月単位に締めるとすると、来訪客が毎週来店したとしても１ヶ月にユーザが購入する商品は十数種類であると考えられるので、売上記録に含まれる１人あたりの商品の種類数の平均Ｇは、１０種類を想定する。
【００９７】
次に、上記の規模を踏まえて、シミュレーションにより従来方式と本実施形態の計算コストを明らかにする。なお、プロバイダと商店はそれぞれ４コアのＣＰＵを備えた計算機を利用でき、来訪客は１コアのＣＰＵを備えた端末を利用できると仮定し、１回の冪剰余にかかる計算時間は６ｍｓ／コアと仮定する。
【００９８】
図６は、１ヶ月あたりの売上人数と処理時間との関係を示す図である。学習にかかる計算コストとして、１ヶ月あたりの売上人数（単位：人）に対して処理時間（単位：日）をプロットすると、プロバイダのユーザ数が１００万人の場合は図６（ａ）のようになり、１，０００万人の場合は図６（ｂ）のようになる。実験の結果、本実施形態は文献１方式に対して１０倍以上速いという結果が得られた。プロバイダのユーザ数が１００万人で商品が１００種類の場合は、文献１方式では１００日以上かかってしまうが、本実施形態であれば１０日以内で計算できるという結果となった。
【００９９】
図７は、商店が利用できる計算機の台数と、来訪客へのリコメンドの遅延との関係を示す図である。飲食店など商品の種類数Ｌが１００種類程度であれば、商店が利用できる計算機の台数が１台の場合に１０秒弱の遅延となる。計算機の台数を増やせば、商店が行うＶＬ回の冪剰余を並列実行できるので、遅延は減少する。しかし、来訪客の端末が行うＬ回の冪剰余は並列実行できないので、商店が計算機の台数を増やしても、遅延は１００×６×１０−３＝０．６秒に漸近するだけである。商品の種類Ｌを１００種類から１，０００種類、１０，０００種類へと増やすと、遅延も約１０倍、約１００倍へと増える結果となった。
【０１００】
（８）本実施形態と従来方式との比較
（８．１）安全性
本実施形態の学習過程の安全性、識別仮定の安全性について説明する。なお、以下の説明において、離散対数問題や準同型暗号などの暗号プリミティブは十分に安全であるとする。
本実施形態の学習過程は、以下の２つの過程により構成される。
学習過程１  プロバイダと商店でのセキュアマッチングによる集計値の計算
学習過程２  商店におけるパラメータおよびハイパーパラメータの計算
【０１０１】
学習過程１の安全性は、セキュアマッチングの安全性に依存する。本実施形態では、片方向のセキュアマッチング、すなわち商店のみが集計値を得るプロトコルを用いているため、プロバイダは商店の売上記録に含まれる人数Ｍ、商品の種類数Ｌ、１人あたりの売上に含まれる商品数Ｇ以外の情報を得ることはない。商店は、セキュアマッチングの出力で
2013210933.tif 000068
情報を得ることはない。Ｍ、Ｌ、Ｇ、Ｎ、Ｗ、Ｖはいずれも公開パラメータであるから、プロバイダと商店がこれらの情報を得ても、ユーザのプライバシーの侵害にはならない。
【０１０２】
学習過程２は、商店により学習過程１の出力である集計値と、学習過程１で得られる暗号文のみを用いてハイパーパラメータが最適化される。すなわち、商店は新たにプロバイダのユーザ情報に関する情報を得ることはない。
本実施形態の識別過程は、商店と来訪客での秘匿内積計算によって構成され、商店は、新たに来訪客のプライバシに関する情報を得ることはない。来訪客は、秘匿内積計算の出力である各商品の周辺尤度と、商品の種類数のみを得る。
以上より、大域的なパラメータであるＭ、Ｌ、Ｇ、Ｎ、Ｗ、Ｖを除き、本実施形態の実行によって、プロバイダはいかなる情報も得ることはない。商店は集計値を、来訪客は周辺尤度をそれぞれ得ることになる。ここで、集計値はプロバイダのユーザ情報の保護に、周辺尤度は商店の売上記録の保護にそれぞれ関係する。
【０１０３】
2013210933.tif 000069
【０１０４】
商店の売上記録の保護については、文献１方式や文献２方式が推薦する商品のみを来訪客に開示するのに対し、本実施形態は商品ごとの周辺尤度を開示する。これは、来訪客のプライバシ保護とのトレードオフである。しかし、現実的には単一のユーザの属性に対する周辺尤度から商店の売上記録を推定することは困難である。また、たとえ攻撃者が結託して多数の来訪客の属性に対する周辺尤度を収集できたとしても、高々属性ごとの商品の売上の割合を推測することしかできず、個々の来訪客がどの商品を購入したかを推測することはできない。なお、来訪客の端末として携帯電話機を利用する場合は、携帯電話機が備えるＩＣカードであるＳＩＭ／ＵＩＭを用いて推薦商品の導出を行わせることも考えられる。この場合、文献１方式及び文献２方式と同様に、推薦する商品以外の情報が来訪客に開示されることはない。
以上のとおり、来訪客のプライバシは、本実施形態で完全に保護される。これに対して、文献１方式と文献２方式では、前述のように来訪客の属性が商店に開示される。
【０１０５】
2013210933.tif 000070
【０１０６】
（８．２）精度
本節では、本実施形態の精度について、ＢＣＤＳとＰＴＤＳを用いた実験結果を踏まえて説明する。
ＢＣＤＳを用いた実験では、表８に示したとおり、推薦した本に対する各ユーザの評価値は本実施形態が平均６．０点で、文献１方式は平均１．６点となった。ここで、評価値の標準偏差を考慮すると、本実施形態は概ね（前後１σ以内）５〜７点の評価値を得ており、本実験ではユーザが５点を超える評価値を与えた本を学習させてリコメンドを行ったため、概ねユーザの満足を得られたといえる結果が得られた。同様に、文献１方式、文献２方式の結果を鑑みると、文献１方式、文献２方式は概ね０〜３．２点の評価値を得ており、多くのユーザの満足を得られたとは言い難い結果となった。
【０１０７】
また、両者の違いは、評価値以外にも、推薦に含む本の種類にも現れた。本実施形態は３３７種類の本を推薦したが、文献１方式、文献２方式は６０種類の本しか推薦せずに、偏ったリコメンドとなった。本実施形態は、ユーザの属性に応じて多くの種類の本を薦める傾向が現れている。皆に同じ商品を薦める単調なリコメンドよりも、属性に応じてバラエティに富んだリコメンドの方が良いと言える。ＢＣＤＳを用いた実験では、本実施形態が文献１方式よりもより多くの商品を推薦し，かつ精度も高い傾向を確認できた。
ＰＴＤＳを用いた実験では、文献１方式、文献２方式は３６％の正解率しか得られなかったが、本実施形態では７９％の正解率が得られた。
【０１０８】
（８．３）計算コスト
本実施形態の計算コストについて、学習過程と識別過程に分けて説明する。
学習過程の計算コストは、文献１方式では２ＮＶＬ回の冪剰余計算が必要であるが、文献２方式と本実施形態ではＮＷ＋ＭＧ＋ＭＧＶ＋ＮＷＬ回で済む。文献２方式と本実施形態は、商店で行うＮＷＬ回の計算コストが支配的であるため、主にプロバイダの秋因数Ｎと商店の商品の種類の数Ｌによって処理時間が変動する。（４．４）で示したのと同じ条件下では、１００万人のユーザ情報を保有するプロバイダと１００種類の商品を扱う商店は１０日以内に学習を行うことができる。この計算は、並列度が極めて高いため、並列処理による計算時間の短縮が容易である。１，０００台分の計算能力を持つクラウドを利用してスケールアウトする場合は、１，０００万人のユーザ情報を保有するプロバイダと１０，０００種類の商品を扱う商店は１０日以内に学習を行うことができる。
【０１０９】
識別過程の計算コストは、文献１方式と文献２方式ではマルチパーティ計算が必要であるが、本実施形態ではＶＬ＋Ｌ回の冪剰余計算で済み、プロバイダのユーザ数や商店の売上記録数により影響を受けない。（４．４）で示したのと同じ条件下では、１００種類の商品を扱う商店は１０秒程度の遅延で来訪客へリコメンドを提供できる。しかし、来訪客は商店よりもスケールアウトが困難であるため、来訪客の端末で行うＬ回の計算がボトルネックとなり、主に商品数Ｌによって処理時間が変動する。たとえ商店が１，０００台分の計算能力を持つクラウドを利用したとしても、１０，０００種類の商品を扱う商店では１００秒程度の時間を要する。だが、リコメンドの提示にあたり、全商品に対する推薦値の計算終了を待つことなく、計算途中でも、その時点までに最も高い周辺尤度を得た商品を逐次入れ替えて表示するなどの工夫により対応は可能である。
【０１１０】
（９）変形例
実施形態を以下の変形例のように変形してもよい。また、複数の変形例を組み合わせてもよい。また、実施形態と変形例を組み合わせもよい。
（９．１）変形例１
実施形態では、セキュアサンプリングの過程で１人分のデータに相当するＷ個の暗号文を順に除いて第２集計値を求める例を示したが、ｎ（２＜ｎ）人分のデータに相当するｎＷ個の暗号文を順に除いて第２集計値を求めるようにしてもよい。この場合、１人分ずつ除く場合と比べて精度は低下するが、差分攻撃が成功しても複数人までしかユーザを絞り込めないため、安全性では上回ると考えられる。
要するに、第２集計値は、属性と選択肢との全ての組み合わせについて、第３演算結果と第４演算結果とで一致する暗号文から１つ以上の暗号文をランダムに除いた複数の集合を作成し、当該複数の集合の各々について第４演算結果と一致する暗号文の数を集計して求めればよい。
【０１１１】
2013210933.tif 000071
【０１１２】
（９．３）変形例３
端末５０は、携帯電話機等の携帯端末でもよいし、いわゆるパーソナルコンピュータ等の据え置き型の情報処理装置でもよい。
【０１１３】
（９．４）変形例４
実施形態では、サーバ１０、リコメンド支援装置３０、端末５０の各制御部がプログラムを実行することによって動作する例を示したが、実施形態と同様の機能をハードウェアで各装置に実装するようにしてもよい。また、このプログラムを、光記録媒体、半導体メモリ等、コンピュータで読み取り可能な記録媒体に記録して提供し、この記録媒体からプログラムを読み取って各装置の記憶部に記憶させるようにしてもよい。また、このプログラムを電気通信回線経由で提供してもよい。
【符号の説明】
【０１１４】
１０…サーバ、１０１…制御部、１０２…記憶部、１０３…通信部、１１…ユーザ情報記憶部、１２…第１演算部、１３…第３演算部、３０…リコメンド支援装置、３０１…制御部、３０２…記憶部、３０３…通信部、３１…売上記録記憶部、３２…第２演算部、３３…第４演算部、３４…第１集計部、３５…第２集計部、３６…パラメータ算出部、３７…リコメンド値暗号化部、５０…端末、５０１…制御部、５０２…記憶部、５０３…通信部、５１…属性情報記憶部、５２…属性情報暗号化部、５３…復号部
【図１】
2013210933.tif 000072
【図２】
2013210933.tif 000073
【図３】
2013210933.tif 000074
【図４】
2013210933.tif 000075
【図５】
2013210933.tif 000076
【図６】
2013210933.tif 000077
【図７】
2013210933.tif 000078