(57)【要約】【課題】サポートベクトルマシン学習を行うにあたり教師信号のラベルを確実に秘匿することができるようにする。【解決手段】サポートベクトルマシン学習を行う分析実行装置は、サポートベクトルマシン学習の対象となる、特徴ベクトルおよび加法的準同型暗号方式により暗号化されたラベルを含む学習データの集合を記憶し、暗号化学習データに対して加法的準同型加算アルゴリズムを用いて勾配法による更新処理を行う。
2015155896.tif 000002
【特許請求の範囲】
【請求項１】
サポートベクトルマシン学習を行うシステムであって、
学習データ管理装置および学習装置を含んで構成され、
前記学習データ管理装置は、
前記サポートベクトルマシン学習の対象となる、ラベルおよび特徴ベクトルを含む学習データの集合を記憶する学習データ記憶部と、
前記学習データの前記ラベルを加法的準同型暗号方式により暗号化する暗号化処理部と、
前記暗号化された前記ラベルおよび前記特徴ベクトルを含む暗号化学習データを前記学習装置に送信する学習データ送信部と、
を備え、
前記学習装置は、
前記暗号化学習データを受信する学習データ受信部と、
前記暗号化学習データに対して加法的準同型加算アルゴリズムを用いて勾配法による更新処理を行う更新処理部と、
を備えることを特徴とするサポートベクトルマシン学習システム。
【請求項２】
請求項１に記載のサポートベクトルマシン学習システムであって、
前記学習データ管理装置は、前記学習データの集合にダミーデータを追加するダミーデータ追加処理部をさらに備え、
前記ダミーデータに含まれる前記ラベルの値は０であること、
を特徴とするサポートベクトルマシン学習システム。
【請求項３】
請求項１または２に記載のサポートベクトルマシン学習システムであって、
前記学習装置は、前記更新処理の対象となる係数（ａ１，ａ２，…，ａＮ）の初期値を生成する係数生成部をさらに備え、
前記更新処理部は、ｉ＝１，２，…，Ｎについて、前記特徴ベクトルをｘｉ、前記ラベルをｙｉ、前記加法的準同型暗号方式により暗号化された前記ラベルをＥ（ｙｉ）として、
2015155896.tif 000011
により算出した暗号文の集合｛Ｅ（ａｉｙｉ）｜ｉ＝１，２，…，Ｎ｝をサポートベクトルマシン学習の前記更新処理の処理結果として生成すること、
を特徴とするサポートベクトルマシン学習システム。
【請求項４】
請求項１または２に記載のサポートベクトルマシン学習システムであって、
前記学習装置は、前記更新処理の対象となる係数（ａ１，ａ２，…，ａＮ）の初期値を生成する係数生成部をさらに備え、
前記更新処理部は、ｉ＝１，２，…，Ｎについて、前記特徴ベクトルをｘｉ、前記ラベルをｙｉ、前記加法的準同型暗号方式により暗号化された前記ラベルをＥ（ｙｉ）、カーネル関数をＫとして、
2015155896.tif 000012
により算出した暗号文の集合｛Ｅ（ａｉｙｉ）｜ｉ＝１，２，…，Ｎ｝をサポートベクトルマシン学習の前記更新処理の処理結果として生成すること、
を特徴とするサポートベクトルマシン学習システム。
【請求項５】
請求項１ないし４のいずれか１項に記載のサポートベクトルマシン学習システムであって、
前記更新処理部は、前記更新処理の対象となる複数の係数組のそれぞれを用いて前記更新処理を行うこと、
を特徴とするサポートベクトルマシン学習システム。
【請求項６】
請求項５に記載のサポートベクトルマシン学習システムであって、
前記更新処理部は、前記複数の係数組のそれぞれについての前記更新処理の処理結果を合計し、当該合計値を前記処理結果とすること、
を特徴とするサポートベクトルマシン学習システム。
【請求項７】
サポートベクトルマシン学習を行うシステムであって、
前記サポートベクトルマシン学習の対象となる、特徴ベクトルおよび加法的準同型暗号方式により暗号化されたラベルを含む学習データの集合を記憶する学習データ記憶部と、
前記暗号化学習データに対して加法的準同型加算アルゴリズムを用いて勾配法による更新処理を行う更新処理部と、
を備えることを特徴とするサポートベクトルマシン学習システム。
【請求項８】
サポートベクトルマシン学習を行う方法であって、
前記サポートベクトルマシン学習の対象となる、ラベルおよび特徴ベクトルを含む学習データの集合を記憶する学習データ管理装置が、
前記学習データの前記ラベルを加法的準同型暗号方式により暗号化するステップと、
前記暗号化した前記ラベルおよび前記特徴ベクトルを含む暗号化学習データを学習装置に送信するステップとを実行し、
前記学習装置が、
前記暗号化学習データを受信するステップと、
前記暗号化学習データに対して加法的準同型加算アルゴリズムを用いて勾配法による更新処理を行うステップとを実行すること、
を特徴とするサポートベクトルマシン学習方法。
【請求項９】
請求項１に記載のサポートベクトルマシン学習方法であって、
前記学習データ管理装置はさらに前記学習データの集合にダミーデータを追加するステップを実行し、
前記ダミーデータに含まれる前記ラベルの値は０であること、
を特徴とするサポートベクトルマシン学習方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、サポートベクトルマシン学習システムおよびサポートベクトルマシン学習方法に関する。
【背景技術】
【０００２】
近年、大量のデータを収集し分析を行い、価値のある知識を抽出するビックデータビジネスが普及をみせている。大量データの分析を実行する際、大容量のストレージや高速なＣＰＵおよびこれらを分散統制するシステムを必要とするため、クラウドなどの外部リソースに分析を依頼する事が考えられる。しかし、データを外部にアウトソースする場合、プライバシー上の問題が発生する。そのため、暗号化やその他、プライバシー保護技術を施した後にデータをアウトソースし分析を行う秘匿分析技術が注目を集めている。例えば、非特許文献１では、サポートベクトルマシン学習を行う際に、分析依頼者が特徴ベクトルを１つのランダムな行列で線型変換して分析実行者に提供し、ｒｅｄｕｃｅｄ  ＳＶＭを用いて学習を行っている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Keng-Pei Lin、Ming-Syan Chen著、「Privacy-Preserving Outsourcing Support Vector Machines with Random Transformation」 、2010年7月25日、KDD2010 Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining、p.363-372
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、非特許文献１に記載の手法では、ラベルがポジティブであるかネガティブであるかは与えられるため、どのようなクラス分けが実現されているのかを分析実行者側で把握することができてしまう。また、特徴ベクトルの秘匿に線形変換を用いていることから、特徴ベクトル空間の次元数と同じだけ変換前後の特徴ベクトルの対応付けが可能となった場合には、線形変換後の特徴ベクトルから線形変換前の特徴ベクトルを特定することができてしまう。【０００５】
本発明は、このような背景を鑑みてなされたものであり、サポートベクトルマシン学習を行うにあたり教師信号のラベルを確実に秘匿することのできる、サポートベクトルマシン学習システムおよびサポートベクトルマシン学習方法を提供することを目的とする。
【課題を解決するための手段】
【０００６】
上記課題を解決するための本発明の主たる発明は、サポートベクトルマシン学習を行うシステムであって、学習データ管理装置および学習装置を含んで構成され、前記学習データ管理装置は、前記サポートベクトルマシン学習の対象となる、ラベルおよび特徴ベクトルを含む学習データの集合を記憶する学習データ記憶部と、前記学習データの前記ラベルを加法的準同型暗号方式により暗号化する暗号化処理部と、前記暗号化された前記ラベルおよび前記特徴ベクトルを含む暗号化学習データを前記学習装置に送信する学習データ送信部と、を備え、前記学習装置は、前記暗号化学習データを受信する学習データ受信部と、前記暗号化学習データに対して加法的準同型加算アルゴリズムを用いて勾配法による更新処理を行う更新処理部と、を備えることとする。【０００７】
その他本願が開示する課題やその解決方法については、発明の実施形態の欄及び図面により明らかにされる。
【発明の効果】
【０００８】
本発明によれば、サポートベクトルマシン学習を行うにあたり教師信号のラベルを確実に秘匿することができる。
【図面の簡単な説明】
【０００９】
【図１】サポートベクトルマシン学習の結果得られるマージンを最大化する超曲面を例示する図である。
【図２】第一の実施形態におけるデータ学習分析システムの構成例を示す図である。
【図３】第一の実施形態における分析依頼装置、分析実行装置のハードウェア構成例を示す図である。
【図４】第一の実施形態における分析依頼装置のソフトウェア構成例を示す図である。
【図５】第一の実施形態における分析実行装置のソフトウェア構成例を示す図である。
【図６】第一の実施形態における処理フローを示す図である。
【図７】第一の実施形態における学習用のデータ、つまり秘匿化特徴ベクトルの集合を説明する図である。
【図８】第一の実施形態における学習処理の処理フローを示す図である。
【図９】第一の実施形態における秘匿学習処理結果から得られる解を例示する図である。
【図１０】第一の実施形態における秘匿学習処理結果から得られる超曲面を例示する図である。
【図１１】第二の実施形態における学習処理の処理フローを示す図である。
【図１２】第二の実施形態における秘匿学習処理結果から得られる解を例示する図である。
【発明を実施するための形態】
【００１０】
以下、本発明の一実施形態に係るデータ学習分析システムを、図１から図６に基づいて詳細に説明する。本実施形態のデータ学習分析システムは、サポートベクトルマシン学習（以下、ＳＶＭ学習とも称する。）によりパターン識別器を生成するにあたり、（ａ）学習に用いるデータ（学習データ）を暗号化し、（ｂ）学習データの集合にダミーデータを加えることにより、確実にラベルを秘匿化し、セキュリティを高めようとするものである。
【００１１】
＝＝定義＝＝
まず、本実施形態で使用する暗号方式およびデータ分析の用語を定義する。本実施形態では、利用する加法的準同型暗号方式を１つ固定して実施するものとする。
【００１２】
（１）加法的準同型暗号方式（アルゴリズム）
本実施形態で用いる加法的準同型暗号方式は、準同型性を有する暗号方式（本実施形態では公開鍵暗号方式を想定している。）のうち加法性を有する暗号アルゴリズムである。例えば加法的準同型暗号方式は、通常の公開鍵暗号方式が有する暗号化鍵、復号化鍵に対する非対称性に加え、暗号文同士の加法性を有する。つまり、２つの暗号文に対して、平文がその２つの暗号文に対する平文の算術和（以下、加算、もしくは単に和と称し、当該算術和に用いる演算子も「＋」と表記する。）となる暗号文を公開情報のみを用いて（秘密鍵や平文を用いることなく）計算する事が可能である。したがって、平文ｍの暗号文をＥ（ｍ）とすると、Ｅ（ｍ１）＋Ｅ（ｍ２）＝Ｅ（ｍ１＋ｍ２）が成立する。以下の説明においても、Ｅ（ｍ）は平文ｍの暗号文を表すものとする。
【００１３】
（２）加法的準同型暗号秘密鍵／公開鍵生成アルゴリズム
上述した加法的準同型暗号アルゴリズムで規定されている秘密鍵／公開鍵生成アルゴリズムを指す。セキュリティパラメータと鍵シードをコマンド入力とし、特定のビット長の秘密鍵／公開鍵を出力とする。
【００１４】
（３）加法的準同型暗号暗号化アルゴリズム
上述した加法的準同型暗号アルゴリズムで規定されている暗号化アルゴリズムを指す。加法的準同型暗号暗号化アルゴリズムは、平文と公開鍵を入力とし暗号文を出力する。
【００１５】
（４）加法的準同型暗号復号化アルゴリズム
上述した加法的準同型暗号アルゴリズムで規定されている復号化アルゴリズムを指す。加法的準同型暗号復号化アルゴリズムは、暗号文と秘密鍵を入力とし、その暗号文に対応する平文を出力する。
【００１６】
（５）加法的準同型暗号加算アルゴリズム
上述した加法的準同型暗号アルゴリズムで規定されている暗号文同士の加算演算を実現するアルゴリズムを指す。複数の暗号文をコマンド入力とし、その複数の暗号文の平文の総和に対応する暗号文を出力する。例えば、１００に対応する暗号文Ｅ（１００）と２００に対応する暗号文Ｅ（２００）をコマンド入力とした際には、３００（１００＋２００）に対応する暗号文Ｅ（３００）を出力する。
【００１７】
（６）サポートベクトルマシン（以下、ＳＶＭとも称する）
教師あり学習を用いる識別手法の一つであり、以下のようなＳＶＭ学習の対象となる学習データ集合
Ｄ＝｛（ｘｉ，ｙｉ）｜ｘｉ∈Ｒｍ，ｙｉ∈｛-１，１｝ｉ＝１，２，…，ｎ｝
が与えられた際、Ｒｍ内でｙｉ＝１であるｘｉベクトルとｙｉ＝−１であるｘｉベクトルを分離する超平面もしくは超曲面の中で最もマージンの大きい超平面もしくは超曲面を算出する。ここで、超平面もしくは超曲面のマージンとはｙｉ＝１であるｘｉベクトルとｙｉ＝−１であるｘｉベクトルの中で最もその超平面もしくは超曲面に近いｘｉベクトルとの距離である。また、本実施形態では、各ｘｉベクトルを特徴ベクトルと呼ぶ。さらにｙｉ＝１である特徴ベクトルｘｉをポジティブラベル特徴ベクトル、ｙｉ＝−１である特徴ベクトルｘｉをネガティブラベル特徴ベクトルと呼ぶ。また、ｙｉは、パターン識別器によりデータをクラス分けするためのクラスであり（図１参照）、ラベルと呼ばれる。なお、本実施形態では、図３のような超平面もしくは超曲面で分離可能な学習データ集合（ハードマージン問題）を用いて説明を行うが、本発明はこれに限定されるものではなく、分離不可能な場合（ソフトマージン問題）についても同様の方法が適用できる。また以下では、超平面で分離可能な例を用いて説明を行うが、本発明はこれに限定されるものではなく、既存のカーネル法を用いて非線形な超曲面で分離可能な例に対しても適用できる。
【００１８】
（７）ＳＶＭ学習
上述の学習データ集合
Ｄ＝｛（ｘｉ，ｙｉ）｜ｘｉ∈Ｒｍ，ｙｉ∈｛−１，１｝ｉ＝１，２，…，ｎ｝
が与えられた際、Ｒｍ内でマージンを最大化する超平面を求めるアルゴリズムをＳＶＭ学習アルゴリズムと呼び、その超平面を求める問題をＳＶＭ問題と呼ぶ。より具体的に、この問題は、目的関数Ｌ（ａ１，ａ２，…，ａｎ）を最大化する実数係数（ａ１，ａ２，…，ａｍ）∈Ｒｍを探索する問題に帰着する。ここで目的関数Ｌは次式により表される。
【００１９】
2015155896.tif 000003
【００２０】
ただし、全てのａｉ≧０であり、
2015155896.tif 000004
という制約条件上を満たすものとする。
（８）勾配法
勾配法とは、最適化問題において関数の勾配に関する情報を基に解を探索するアルゴリズムである。上記ＳＶＭ問題について、上記目的関数Ｌを最大化する最適解（ａ１，ａ２，…，ａｎ）は勾配法により求める。
【００２１】
関数Ｌの勾配ベクトルの第ｉ成分Ｌ’ｉが、
2015155896.tif 000005
であるため、勾配法により係数（ａ１，ａ２，…，ａｎ）を、更新率γで再帰的に
2015155896.tif 000006
と更新することで最適解もしくはその近似解を得る事が可能である。
【００２２】
＝＝発明の概要＝＝
上述のとおり、本実施形態のデータ学習分析システムでは、ＳＶＭ学習にあたり（ａ）学習データを暗号化し、（ｂ）学習データにダミーデータを追加する。
【００２３】
（ａ）学習データの暗号化
本実施形態では、学習データのラベルｙｉを暗号化したうえでＳＶＭ学習を実行する分析実行装置２００に与える。これにより、分析実行装置２００側に対してラベルｙｉの内容（＋１であるか−１であるか）を隠蔽する。ラベルｙｉの内容が隠蔽されることにより、分析実行装置２００では学習データに有意な意味づけを行うことが困難となる。
【００２４】
暗号化のアルゴリズムには加法的準同型暗号化方式を用いる。上述したように、加法的準同型暗号方式により暗号化された暗号化データは、暗号化したまま（復号することなく）暗号文の加算が可能であり、加算された暗号文を復号した結果は、対応する平文が加算された結果に一致する。ＳＶＭ学習の最適解（または近似解）の算出に勾配法を用いる場合、上記更新式（４）を次式（５）のように変形することができる。
【００２５】
2015155896.tif 000007
【００２６】
ここで、（ａ１，ａ２，…，ａｎ）と（ｘ１，ｘ２，…，ｘｎ）とγが既知であれば、更新式（５）の右辺はｙｉに関してスカラー積の和である。したがって、ｙｉに代えて加法的準同型暗号での暗号文Ｅ（ｙｉ）を与え、平文ｙｉを与えなかったとしても、加法的準同型暗号の加法性を利用して更新式（５）の計算が可能である。すなわち、次式（６）を更新式として計算することができる。
【００２７】
2015155896.tif 000008
【００２８】
本実施形態のデータ学習分析システムでは、分析実行装置２００において上記式（６）を更新式としてＳＶＭ学習を行う。これにより、分析実行装置２００にはラベルｙｉについて平文を与えることなく暗号文Ｅ（ｙｉ）のままでＳＶＭ学習が可能となる。
【００２９】
なお、Ｐａｉｌｌｉｅｒ暗号方式のように加法的準同型暗号方式が乗法性を有していない場合には、更新式（６）を用いて２回以上再帰的に更新すると暗号文Ｅ（ｙ）の乗算が必要となる。そこで本実施形態では、更新処理は１回のみ行うものとする。
【００３０】
（ｂ）ダミーデータの追加
また、本実施形態では、学習データの集合にダミーデータを加える。これにより、学習データ集合の与えられた分析実行装置２００側では、例えば学習データの分布の偏りなどを用いて、学習データの有意な意味づけを推測することも困難となる。
【００３１】
学習データの集合に加えるダミーデータには、＋１でも−１でもない０のラベルｙｉを与える。ラベルとして０を与えることにより、更新式（５）の右辺においてはダミーデータのラベルｙｉに係る項は０となり更新式（５）に与える影響がない。これは加法性のある加法的準同型暗号方式を利用した更新式（６）においても同価値である。
【００３２】
その一方で、分析実行者側において、ラベルは暗号化されるため、学習データがダミーデータであるかどうかを判定することができないようにすることができる。また、学習データの集合が一様分布に近づくようにダミーデータを追加することにより学習データの意味づけをより困難とすることができる。
【００３３】
以下、詳細について説明する。
＝＝第一の実施形態＝＝
図２は、本発明の一実施の形態であるデータ学習分析システムの概略図である。図２に示すように、本実施形態のデータ学習分析システムは、分析依頼装置１００と分析実行装置２００とを含んで構成される。分析依頼装置１００は、学習データを管理するコンピュータである。分析実行装置２００はＳＶＭ学習に係る処理を行うコンピュータである。
【００３４】
分析依頼装置１００と分析実行装置２００とはネットワーク３００を介して相互に情報を送受信できるように設計されている。ネットワーク３００は、例えばインターネットやＬＡＮ（Local Area Network）であり、例えばイーサネット（登録商標）、光ファイバー、無線通信路、公衆電話回線網、専用電話回線網などにより構築される。
【００３５】
分析依頼装置１００はネットワーク３００を介して学習データの集合を分析実行装置２００に送信し、分析実行装置２００は分析依頼装置１００から受信した学習データに対してＳＶＭ学習を行い、ＳＶＭ学習の結果（以下、学習結果という。）をネットワーク３００を介して分析依頼装置１００に送信する。分析依頼装置１００は、学習結果を用いてパターン識別器を生成する。
【００３６】
＝＝ハードウェア構成＝＝
図３は、分析依頼装置１００のハードウェア概略図である。図３に示すように、分析依頼装置１００は、ＣＰＵ１０１と、補助記憶装置１０２と、メモリ１０３と、表示装置１０５と、入出力インターフェース１０６と、通信装置１０７と、が内部信号線１０４で連結し、構成される。また、補助記憶装置１０２には、プログラムコードが格納されている。プログラムコードは、メモリ１０３にロードされＣＰＵ１０１によって実行される。
【００３７】
また、分析実行装置２００も分析依頼装置１００と同様の図２に示すハードウェア構成を具備する。
【００３８】
＝＝分析依頼装置のソフトウェア構成＝＝
図４は、分析依頼装置１００のソフトウェア概略図である。分析依頼装置１００は、学習データ記憶部１２１、ダミーデータ記憶部１２２、ダミーデータ追加処理部１２３、暗号化処理部１２４、学習データ送信部１２５、学習結果受信部１２６、復号化処理部１２７およびパターン識別器生成部１２８を備える。
【００３９】
学習データ記憶部１２１およびダミーデータ記憶部１２２は分析依頼装置１００が備える補助記憶装置１０２よびメモリ１０３が提供する記憶領域の一部として実現され、ダミーデータ追加処理部１２３、暗号化処理部１２４、学習データ送信部１２５、学習結果受信部１２６、復号化処理部１２７およびパターン識別器生成部１２８は、分析依頼装置１００が備えるＣＰＵ１０１が補助記憶装置１０２に格納されているプログラムコードをメモリ１０３にロードして実行することにより実現される。
【００４０】
学習データ記憶部１２１は、学習データ集合Ｄを記憶する。なお、学習データ集合は上述のとおり
Ｄ＝｛（ｘｉ，ｙｉ）｜ｘｉ∈Ｒｍ，ｙｉ∈｛-１，１｝ｉ＝１，２，…，ｎ｝
と表される。
【００４１】
ダミーデータ追加処理部１２３は、学習データ集合Ｄにダミーデータを追加する。ダミーデータは、「０」のラベルｙを含むデータである。ダミーデータ追加処理部１２３は、学習データ集号Ｄに含まれる特徴ベクトルが特徴空間において一様な分布となるようにダミーデータを追加する。ダミーデータ追加処理部１２３は、ユーザから一様分布となるような特徴ベクトルの入力を受け付けるようにしてもよいし、例えば特徴空間を区画に区切り、カイ二乗検定などを用いて一様分布と判定されるようになるまで、区画内に存在する特徴ベクトルの数が少ない区画を選択し、選択した区画の１つまたは複数に入るように特徴ベクトルを生成するようにしてもよい。また、ダミーデータ追加処理部１２３は、学習データ（ラベル付特徴ベクトル）をランダムに並び替え（添え字ｉをランダムに置換）してもよい。ダミーデータ追加処理部１２３は、ダミーデータを示す情報（例えばダミーデータを示す添え字ｉ）をダミーデータ記憶部１２２に記憶する。
【００４２】
暗号化処理部１２４は、加法的準同型暗号暗号化アルゴリズムにより学習データのラベルｙを暗号化して暗号文Ｅ（ｙ）を生成し、ラベルｙに代えて暗号文Ｅ（ｙ）とした学習データ（以下、秘匿化学習データといい、Ｅ（Ｄ）で表す。）を生成する。秘匿化学習データＥ（Ｄ）は次のようになる。
【００４３】
Ｅ（Ｄ）＝｛（ｘｉ，Ｅ（ｙｉ））｜ｘｉ∈Ｒｍ，ｙｉ∈｛−１，１，０｝ｉ＝１，２，…，Ｎ｝
【００４４】
学習データ送信部１２５は、秘匿化学習データを分析実行装置２００に送信する。
【００４５】
学習結果受信部１２６は、分析実行装置２００から送信される、ＳＶＭ学習の処理結果を受信する。本実施形態では、後述するように分析実行装置２００からは、実数係数（ａ１，ａ２，…，ａｍ）∈Ｒｍを受信するのではなく、係数にラベルを乗じた値｛ａｉｙｉ｜ｉ＝１，２，…，Ｎ｝（以下、学習結果という。）の暗号文｛Ｅ（ａｉｙｉ）｜ｉ＝１，２，…，Ｎ｝（以下、秘匿化学習結果という。）を処理結果として受信する。
【００４６】
復号化処理部１２７は、秘匿化学習結果を復号して（ａ１ｙ１，ａ２ｙ２，…，ａＮｙＮ）を得る。また、復号化処理部１２７は、ダミーデータ記憶部１２２に記憶されている情報より復号した学習結果中のダミーデータを特定し、学習結果からダミーデータを除いて（ａ１，ａ２，…，ａｎ）を抽出する。また、復号化処理部１２７は、係数が負となる場合には、ベクトル（ａ１，ａ２，…，ａｎ）を（ｙ１，ｙ２，…，ｙｎ）の直交補空間に正射影した正射影ベクトルを学習結果としてもよい。
【００４７】
パターン識別器生成部１２８は、係数（ａ１，ａ２，…，ａｍ）∈Ｒｍを用いてパターン識別器を生成する。なお、パターン識別器の生成手法は、一般的なＳＶＭ学習を行う場合と同様のものを採用し、ここでは説明を省略する。
【００４８】
＝＝分析実行装置のソフトウェア構成＝＝
図５は、分析実行装置２００のソフトウェア概略図である。分析実行装置２００は、学習データ受信部２２１、係数生成部２２２、更新処理部２２３および学習結果送信部２２４を備える。なお、係数生成部２２２、更新処理部２２３および学習結果送信部２２４は、分析実行装置２００が備えるＣＰＵ１０１が補助記憶装置１０２に格納されているプログラムコードをメモリ１０３にロードして実行することにより実現される。
【００４９】
学習データ受信部２２１は、分析依頼装置１００から送信される秘匿化学習データ集合を受信する。
【００５０】
係数生成部２２２は、目的関数Ｌの係数（ａ１，ａ２，…，ａＮ）を生成する。本実施形態では、係数生成部２２２は、Ｎ回乱数を発生させて係数とするものとするが、たとえば所定の初期値（例えば全てのａｉを０とすることができる。）を設定するようにしてもよい。
【００５１】
更新処理部２２３は、上記更新式（６）により更新処理を行う。更新処理部２２３は、更新式（６）に係る演算子「＋」の演算には、加法的準同型暗号方式を用いた加算処理を用いる。また、本実施形態では、加法的準同型暗号方式として、例えばＰａｉｌｌｉｅｒ暗号方式など、乗法性を有しない加法的準同型暗号方式を用いることを想定しているため、更新処理部２２３は、ランダムに設定した係数と秘匿化学習データ集号とを更新式（６）に与えて算出した暗号文Ｅ（ａｉｙｉ）の集合をそのまま秘匿化学習結果として生成する。
【００５２】
学習結果送信部２２４は、秘匿化学習結果を分析依頼装置１００に送信する。
【００５３】
＝＝処理フロー＝＝
図６は、本実施形態のデータ学習分析システムにおいて実行される処理の流れを示す図である。
【００５４】
まず、分析依頼装置１００において、暗号化処理部１２４は加法的準同型暗号方式による秘密鍵／公開鍵生成アルゴリズムを用いて、以下で用いる秘密鍵／公開鍵を生成する（Ｓ１００）。次に、ダミーデータ追加処理部１２３は、学習データ記憶部１２１に記憶されている学習データ集合Ｄ＝｛（ｘｉ，ｙｉ）｜ｘｉ∈Ｒｍ，ｙｉ∈｛−１，１｝ｉ＝１，２，…，ｎ｝に対して、ラベルｙｉ＝０と、ダミーの特徴ベクトル｛（ｘｉ，０）ｉ＝ｎ＋１，…，Ｎ｝とを含むダミーデータを加えた新しい学習データ集合Ｄ＝｛（ｘｉ，ｙｉ）｜ｘｉ∈Ｒｍ，ｙｉ∈｛−１，１，０｝ｉ＝１，２，…，Ｎ｝を生成する（Ｓ１５０）。ここでダミーデータ追加処理部１２３は、学習データをランダムに並び替えてもよい。図７は、ラベル０を持つダミー特徴ベクトルの集合をポジティブ／ネガティブ特徴ベクトルの集合に加えた特徴空間を図示している。図７において、「○」に対応するベクトルがポジティブラベル特徴ベクトルであり、「×」に対応するベクトルがネガティブラベル特徴ベクトルであり、「△」に対応するベクトルがダミー特徴ベクトルである。図７に示すように、ダミーデータ追加処理部１２３は、特徴ベクトルが一様分布に近くなるようにダミーデータを追加する。
【００５５】
次に暗号化処理部１２４は、学習データ集合Ｄ＝｛（ｘｉ，ｙｉ）｜ｘｉ∈Ｒｍ，ｙｉ∈｛−１，１，０｝ｉ＝１，２，…，Ｎ｝に対して、ラベルｙｉを平文とし、（Ｓ１００）で生成した公開鍵で加法的準同型暗号暗号化アルゴリズムを用いて暗号文Ｅ（ｙｉ）を生成して、秘匿化学習データＥ（Ｄ）＝｛（ｘｉ，Ｅ（ｙｉ））｜ｘｉ∈Ｒｍ，ｙｉ∈｛−１，１，０｝ｉ＝１，２，…，Ｎ｝を生成する（Ｓ２００）。学習データ送信部１２５は、秘匿化学習データ（Ｄ１００）を分析実行装置２００に送信する。
【００５６】
秘匿化学習データ（Ｄ１００）を受信した分析実行者端末２００では、図８に示す学習処理が行われる（Ｓ３００）。学習結果送信部２２４は、学習結果｛Ｅ（ａｉｙｉ）｜ｉ＝１，２，…，Ｎ｝を秘匿化学習結果（Ｄ２００）として、分析依頼装置１００に返信する。
【００５７】
分析依頼装置１００では、学習結果受信部１２６が、分析実行装置２００から送信される秘匿化学習結果（Ｄ２００）を受信し、復号化処理部１２７が、（Ｓ１００）で生成された秘密鍵を用いて秘匿化学習結果（Ｄ２００）を復号し、学習結果（ａ１ｙ１，ａ２ｙ２，…，ａＮｙＮ）を得る（Ｓ４００）。復号化処理部１２７は、（ａ１ｙ１，ａ２ｙ２，…，ａＮｙＮ）からダミーデータに対応する結果をを除き、最終的な係数列（ａ１，ａ２，…，ａｎ）を生成する。復号化処理部１２７はａｉ＜０となる係数に関しては、ａｉ＝０とする。以上のようにして事後処理を終える（Ｓ５００）。ここで復号化処理部１２７は、必要であれば、
2015155896.tif 000009
となるように、ベクトル（ａ１，ａ２，…，ａｎ）を（ｙ１，ｙ２，…，ｙｎ）の直交補空間に正射影し、その正射影ベクトルを係数列（ａ１，ａ２，…，ａｎ）としてもよい。パターン識別器生成部１２８は、係数列（ａ１，ａ２，…，ａｎ）を用いてパターン識別器を生成する（Ｓ６００）。
【００５８】
図８は、図６の（Ｓ３００）における学習処理の処理フローを示す図である。
【００５９】
学習データ受信部２２１は、秘匿化学習データ（Ｄ１００）すなわち、Ｅ（Ｄ）＝｛（ｘｉ，Ｅ（ｙｉ））｜ｘｉ∈Ｒｍ，ｙｉ∈｛−１，１，０｝ｉ＝１，２，…，Ｎ｝を受信し（Ｓ３０１）、係数生成部２２２は、ランダムな係数（ａ１，ａ２，…，ａＮ）を生成して初期係数とするとともに、更新係数γ＞０を設定する（Ｓ３０２）。なお、本実施形態では係数生成部２２２は、所定の定数（γ＝０．００１）を用いるものとする。
【００６０】
次に更新処理部２２３は、初期係数（ａ１，ａ２，…，ａＮ）および秘匿化学習データ（Ｄ１００）について、上記更新式（６）を計算する（Ｓ３０３）。学習結果送信部２２４は、更新式（６）により算出された秘匿化学習処理結果｛Ｅ（ａｉｙｉ）｜ｉ＝１，２，…，Ｎ｝（Ｄ２００）を分析依頼装置１００に送信する（Ｓ３０４）。
【００６１】
以上のようにして、本実施形態のデータ学習分析システムでは、加法的準同型暗号方式を勾配法に適用することにより、ラベルを暗号化したまま（復号することなく）勾配法によるＳＶＭ学習を行うことができる。したがって、教師信号として特徴ベクトルに付したラベルを分析実行装置２００側に対して秘匿することができる。
【００６２】
また、本実施形態のデータ学習分析システムでは、ラベルは線形変換ではなく暗号化を行っている。例えば非特許文献１のような学習方法の場合には、全ての特徴ベクトルに対して同一の行列を用いて線型変換を行うため、例えば秘匿化後の特徴ベクトルと元の特徴ベクトルの組み合わせが特徴ベクトル空間の次元に一致する個数漏洩した場合などには、変換に用いた行列を特定し、これにより元の特徴ベクトルを特定することが可能となってしまう懸念があるところ、例えばＰａｉｌｌｉｅｒ暗号などの加法的準同型暗号方式は選択平文／暗号文攻撃に耐性を有しており、仮に特徴ベクトルの組が特徴ベクトル空間の次元以上漏洩した場合であっても、ラベルを推定することは困難である。よって、分析実行装置２００側に対してラベルを確実に秘匿することが可能となり、セキュリティの向上が期待される。
【００６３】
また、本実施形態のデータ学習分析システムでは、学習データ集合にダミーデータを加えたうえでラベルを暗号化しているため、特徴ベクトルの偏在などからラベルを推定することが困難となる。したがって、セキュリティを向上することができる。また、特徴ベクトルの分布に偏りがみられる場合には、その分布からラベルを推測することも考えられるものの、本実施形態のデータ学習分析システムでは、特徴ベクトルが一様分布に近づくようにダミーデータを追加しており、暗号化された特徴ベクトルの集合から元の特徴ベクトルに関する情報を推測することは困難である。したがって、分析実行装置２００側に対して確実にラベルを秘匿することができる。よって、さらにセキュリティを向上することができる。
【００６４】
また、本実施形態のデータ学習分析システムでは、ダミーデータのラベルを「０」としているので、勾配法の更新処理においてダミーデータを追加したことによる影響を排除することができる。その一方で、ダミーデータのラベルも暗号化されるため、影響が排除されているかどうかは暗号化データからは推定することができない。したがって、分析実行装置２００側に対して確実に学習データを秘匿することが可能となる。
【００６５】
＝＝第二の実施形態＝＝
次に第二の実施形態について説明する。
【００６６】
第一の実施形態中の学習処理（Ｓ３００）において、分析実行装置２００は初期係数に対して勾配法による更新を１度しか行っていない（Ｓ３０３）、一般に、勾配法において。更新を１度しか行わない場合、図７に示すように得られる解は最適解となるとは限らない。したがって、１度しか更新を行っていない秘匿化学習結果（Ｄ２００）から得られる超曲面は、図１０にあるように最適解から得られるマージンを最大化する超曲面と一致しない可能性があり、初期係数として選んだランダムな係数（ａ１，ａ２，…，ａＮ）の値に依存する。
【００６７】
そこで、第二の実施形態では、ｋ個の初期値（ａ１，ａ２，…，ａＮ）を準備して更新処理を行い、更新結果Ｅ（ａｉｙｉ）の和を取ることで、初期値への依存度を緩和する。
【００６８】
第一の実施形態との変更点は学習処理（Ｓ３００）のみであり、その他の処理フローは第一の実施形態と同一であるため、ここでは学習処理（Ｓ３００）についてのみ説明する。
【００６９】
図１１は第二の実施形態における学習処理（Ｓ３００）の処理フローである。
【００７０】
学習データ受信部２２１は、秘匿化学習データ（Ｄ１００）、すなわちＥ（Ｄ）＝｛（ｘｉ，Ｅ（ｙｉ））｜ｘｉ∈Ｒｍ，ｙｉ∈｛−１，１，０｝ｉ＝１，２，…，Ｎ｝を受信し（Ｓ６０１）、係数生成部２２２は、初期値の数ｋを決定し、内部変数ｔ＝０を設定する。ｋの値は、０より大きい任意の整数であればよく、ランダムな整数であってもよい。また、係数生成部２２２は、分析実行装置２００の計算リソースに合わせてなるべく大きな値となるように決定してもよい（Ｓ６０２）。係数生成部２２２は、ランダムな係数（ａ１，ａ２，…，ａＮ）を生成し初期係数とするとともに、更新係数γ＞０を生成し、ｉ＝１，２，…，Ｎについて秘匿化学習結果Ｅ（ａｉｙｉ）を０に初期化する（Ｓ６０３）。なお、本実施形態においても第一の実施形態と同様にγには定数（γ＝０．００１）を用いるものとする。
【００７１】
次に更新処理部２２３は、初期係数（ａ１，ａ２，…，ａＮ）と、秘匿化学習データ（Ｄ１００）と、秘匿化学習結果｛Ｅ（ａｉｙｉ）｜ｉ＝１，２，…，Ｎ｝とを更新式
2015155896.tif 000010
に与えて秘匿化学習結果Ｅ（ａｉｙｉ）を更新する（Ｓ６０４）。
【００７２】
更新処理部２２３は、内部変数ｔをインクリメントし、ｔ＜ｋの場合は、（Ｓ６０３）に処理を戻す。ｔ＝ｋの場合に、学習結果送信部２２４は、上記更新式（７）により算出された秘匿化学習結果｛Ｅ（ａｉｙｉ）｜ｉ＝１，２，…，Ｎ｝を分析依頼装置１００に送信する（Ｓ６０６）。
【００７３】
図１２は、第二の実施形態における学習処理（Ｓ３００）内での更新処理を説明する図である。図１２が示す通り、第一の実施形態は１つの初期係数の更新処理から秘匿化学習処理結果（Ｄ２００）を算出していたが、第二の実施形態では、複数の初期係数の加算として秘匿化学習処理結果（Ｄ２００）を算出している。したがって、第一の実施形態のように更新処理を１回しか行わない場合（図９参照）に比べ、より最適解に近い解を求めることができる。その一方で分析実行装置２００側では秘匿化学習データの復号を行わないようにすることができる。よって、分析実行装置２００側に対して学習データを秘匿しつつ、学習結果をより最適解に近づけることができる。
【００７４】
以上、本発明の実施形態について説明したが，上述の実施形態に限定されるものではなく、その要旨の範囲内で様々な変形が可能である。
【００７５】
例えば、本実施形態では、分析依頼装置１００および分析実行装置２００は１台のコンピュータであるものとしたが、これに限らず、例えば分析依頼装置１００および分析実行装置２００の少なくともいずれかを複数のコンピュータにより構成してもよい。
【００７６】
また、上述更新式（５）ないし（７）の右辺では、特徴ベクトルの内積値＜ｘｉ，ｘｊ＞のスカラー積の加算を計算しているが、必ずしも内積値である必要はなく、内積値を含む一般のカーネル関数Ｋ（ｘｉ，ｘｊ）を用いて、更新式（５）ないし（７）を計算してもよい。
【００７７】
また、上述の実施例では、更新係数γ＝０．０１としているが、必ずしもこの値とする必要は無く、既存の勾配法の更新係数決定アルゴリズムにより算出される値を用いてもよい。
【００７８】
また、第二の実施形態では、係数の初期値を準備する個数ｋを分析実行装置２００の係数生成部２２２が決定するものとしたが、分析依頼装置１００からｋの値を指定するようにしてもよい。この場合、学習データ送信部１２５は、例えばユーザからｋの値の入力を受け付けて秘匿化学習データとともに分析実行装置２００に送信すればよい。
【符号の説明】
【００７９】
１００  分析依頼装置
１０１  ＣＰＵ
１０２  補助記憶装置（記憶装置）
１０３  メモリ
１０４  内部信号線
１０５  表示装置
１０６  入出力インターフェース
１０７  通信装置
２００  分析実行装置
３００  ネットワーク
【図１】
2015155896.tif 000013
【図２】
2015155896.tif 000014
【図３】
2015155896.tif 000015
【図４】
2015155896.tif 000016
【図５】
2015155896.tif 000017
【図６】
2015155896.tif 000018
【図７】
2015155896.tif 000019
【図８】
2015155896.tif 000020
【図９】
2015155896.tif 000021
【図１０】
2015155896.tif 000022
【図１１】
2015155896.tif 000023
【図１２】
2015155896.tif 000024
【国際調査報告】
2015155896.tif 000025
2015155896.tif 000026
2015155896.tif 000027