1組のデータベースのための差分プライバシー集合分類器を求めるための方法であって、該1組のデータベース内の各データベースは分類器及び雑音値に関連付けられ、該分類器及び該雑音値は、該分類器及び該雑音値の組み合わせが前記データベースの差分データプライバシーを保証するように、前記データベース毎にローカルに求められ、前記差分プライバシー集合分類器は各前記データベースの前記差分データプライバシーを保護し、該方法は、前記分類器を組み合わせて集合分類器を求めるステップと、前記1組のデータベース内の最も小さなデータベースに対応する雑音値を用いて前記集合分類器を変更して前記差分プライバシー集合分類器を生成するステップとを含み、該方法の該ステップはプロセッサによって実行される、方法。前記最も小さなデータベースは最も少ない数のエントリを有し、前記エントリのデータ構造は全てのデータベースについて同一である、請求項1に記載の方法。前記データベースのインデックスの置換から生じる前記最も小さなデータベースの不明瞭化インデックスを求めるステップと、全ての雑音値の加法的持分から、前記不明瞭化インデックスに基づいて、前記最も小さなデータベースに関連付けられた雑音値の第1の加法的持分をオブリビアスに選択するステップであって、第2の加法的持分が1つ又は複数のデータベース内に格納されるものと、各前記分類器、前記雑音値の前記第1の加法的持分及び前記第2の加法的持分をオブリビアスに組み合わせることによって前記差分プライバシー集合分類器を求めるステップとをさらに含む、請求項1に記載の方法。前記雑音値はラプラス分布に従って分布する、請求項1に記載の方法。前記データベース毎の前記雑音値は前記データベースのサイズに基づいて求められる、請求項1に記載の方法。前記分類器は2値ロジスティック回帰分類器である、請求項1に記載の方法。前記分類器は、2値ロジスティック回帰分類器の組み合わせから構成されるマルチクラス分類器である、請求項6に記載の方法。前記差分プライバシー分類器を求めることは、暗号プロトコルによって実行される、請求項3に記載の方法。前記差分プライバシー分類器を求めることは、秘密共有プロトコルによって実行される、請求項3に記載の方法。1組のデータベースのための差分プライバシー集合分類器を求めるためのシステムであって、該1組のデータベース内の各データベースは分類器及び雑音値に関連付けられ、該分類器及び該雑音値は、該分類器及び該雑音値の組み合わせが該データベースの差分データプライバシーを保証するように、前記データベース毎にローカルに求められ、前記差分プライバシー集合分類器は各前記データベースの前記差分データプライバシーを保護し、該システムは、前記分類器を組み合わせて集合分類器を求める手段と、前記1組のデータベース内の最も小さなデータベースに対応する雑音値を用いて前記集合分類器を変更して、前記差分プライバシー集合分類器を生成する手段とを備える、システム。前記最も小さなデータベースは最も少ない数のエントリを有し、前記エントリのデータ構造は全てのデータベースについて同一である、請求項10に記載のシステム。前記データベースのインデックスの置換から生じる前記最も小さなデータベースの不明瞭化インデックスを求める手段と、全ての雑音値の加法的持分から、前記不明瞭化インデックスに基づいて、前記最も小さなデータベースに関連付けられた雑音値の第1の加法的持分をオブリビアスに選択する手段であって、第2の加法的持分が1つ又は複数のデータベース内に格納されるものと、各前記分類器、前記雑音値の前記第1の加法的持分及び前記第2の加法的持分をオブリビアスに組み合わせることによって前記差分プライバシー集合分類器を求める手段とをさらに備える、請求項10に記載のシステム。前記雑音値はラプラス分布に従って分布する、請求項10に記載のシステム。前記データベース毎の前記雑音値は前記データベースのサイズに基づいて求められる、請求項10に記載のシステム。1組のデータベースのための差分プライバシー集合分類器を格納するコンピューター読み取り可能な記憶媒体であって、該1組のデータベース内の各データベースは分類器及び雑音値に関連付けられ、該分類器及び該雑音値は、該分類器及び該雑音値の組み合わせが前記データベースの差分データプライバシーを保証するように、前記データベース毎にローカルに求められ、前記差分プライバシー集合分類器は、前記1組のデータベース内の最も小さなデータベースに対応する雑音値を用いて変更された、該1組のデータベースの前記分類器の組み合わせである、コンピューター読み取り可能な記憶媒体。差分プライバシーが、分類器の出力が個々のデータインスタンスについての情報を含まないという統計的保証を提供する。しかしながら、マルチパーティーの応用例では、分類器を求めるためのデータがいくつかのデータベースにわたって分散され、従来の差分プライバシー法は、複数の寄与しているパーティーのための差分データプライバシーを保護しない。これは、従来の方法が本来、分類器がデータベースの全データへのアクセスに基づいて求められ、データに関して計算された雑音値によって分類器を変更して、そのデータに専用の差分プライバシー分類器を生成するように設計されるためである。しかしながら、マルチパーティーの応用例では、セキュリティ制約に起因して、多くの場合に、異なるデータベースのデータにアクセスすることはできない。この発明の実施の形態は、1組のデータベースについて、データベースのデータへのアクセスを許可することなく、1組のデータベース内の個々のデータベースの分類器及び雑音値から、各データベースの差分データプライバシーを保護する差分プライバシー集合分類器を求めることができるという認識に基づいている。しかしながら、マルチパーティーの応用例では、分類器に雑音値を付加することはもはや簡単ではない。これは、雑音を付加した結果として各データベースの差分データプライバシーが達成されるという保証がないためである。たとえば、全ての分類器及び雑音値の集合は、論理的手法と見なされることになり、組み合わせられたデータに対する差分プライバシーを満たさない。この発明の実施の形態は、1組のデータベース内の最も小さなデータベースに対応する雑音値によって変更される各データベースの分類器の集合として、差分プライバシー集合分類器を求めることができるという別の認識に基づいている。最も小さなデータベースは、最も少ないエントリ数を有し、各エントリのデータ構造は全てのデータベースにわたって同じである。この認識が正しいことの裏付けは、付録において提供される。したがって、この発明の1つの実施の形態は、1組のデータベースのための差分プライバシー集合分類器を求めるための方法であって、該1組のデータベース内の各データベースは分類器及び雑音値に関連付けられ、該分類器及び該雑音値は、該分類器及び該雑音値の組み合わせが前記データベースの差分データプライバシーを保証するように、前記データベース毎にローカルに求められ、前記差分プライバシー集合分類器は各前記データベースの前記差分データプライバシーを保護し、該方法は、各前記データベースの前記分類器を組み合わせて集合分類器を求めるステップと、前記1組のデータベース内の最も小さなデータベースに対応する雑音値を用いて前記集合分類器を変更するステップとを含み、前記最も小さなデータベースは最も少ないエントリ数を有し、各エントリのデータ構造は全てのデータベースについて同じである、方法を開示する。さらに、この発明の種々の実施の形態は、暗号プロトコルを用いてセキュアに差分プライバシー集合分類器を求める。それらの実施の形態は、各データベースのデータがいかなる他のパーティーとも共有されないこと、及び差分プライバシー集合分類器をリバースエンジニアリングによって解析していかなるデータベースのいかなる個々のデータも突き止めることができないことを保証する。別の実施の形態は、1組のデータベースのための差分プライバシー集合分類器を求めるためのシステムであって、該1組のデータベース内の各データベースは分類器及び雑音値に関連付けられ、該分類器及び該雑音値は、該分類器及び該雑音値の組み合わせが該データベースの差分データプライバシーを保証するように、前記データベース毎にローカルに求められ、前記差分プライバシー集合分類器は各前記データベースの前記差分データプライバシーを保護し、該システムは、前記分類器を組み合わせて集合分類器を求める手段と、前記1組のデータベース内の最も小さなデータベースに対応する雑音値を用いて前記集合分類器を変更して、前記差分プライバシー集合分類器を生成する手段とを備える、システムを開示する。さらに別の実施の形態は、1組のデータベースのための差分プライバシー集合分類器を格納するコンピューター読み取り可能な記憶媒体であって、該1組のデータベース内の各データベースは分類器及び雑音値に関連付けられ、該分類器及び該雑音値は、該分類器及び該雑音値の組み合わせが前記データベースの差分データプライバシーを保証するように、前記データベース毎にローカルに求められ、前記差分プライバシー集合分類器は、前記1組のデータベース内の最も小さなデータベースに対応する雑音値を用いて変更された、該1組のデータベースの前記分類器の組み合わせである、コンピューター読み取り可能な記憶媒体を開示する。この発明の実施の形態は、差分プライバシー集合分類器を求め、複数データベースの差分プライバシーを保証する。この発明は、マルチパーティー差分プライバシーを達成するのに、最も小さなデータベースのサイズに基づいて確率的成分を選択すれば十分であるという認識に基づいている。いくつかの実施の形態は、この認識のために、SMC法を介して雑音値の選択をセキュアに実行することができることをさらに認めている。しかしながら、従来の方法とは異なり、それらの実施の形態は分類器を構成するのにSMCを使用しない。それゆえ、この発明の実施の形態は、組み合わせられたデータにおいて分類器を計算する任意のSMC法よりもはるかに簡単である。定義この発明の実施の形態を説明する際に、全体を通して以下の定義が適用可能である。コンピューターは、構造化された入力を受け取り、構造化された入力を所定の規則に従って処理し、処理結果を出力として生成することができる任意の装置を指している。コンピューターの例には、コンピューター;汎用コンピューター;スーパーコンピューター;メインフレーム;スーパーミニコンピューター;ミニコンピューター;ワークステーション;マイクロコンピューター;サーバー;双方向テレビ;コンピューター及び双方向テレビの種々の組み合わせ;並びにコンピューター及び/又はソフトウエアをエミュレートする専用ハードウエアが含まれる。コンピューターは単一のプロセッサ又は複数のプロセッサを有することができ、それらのプロセッサは並列に、かつ/又は非並列に動作することができる。また、コンピューターは、コンピューター間で情報を送信又は受信するためのネットワークを介して共に接続される2つ以上のコンピューターも指している。そのようなコンピューターの例には、ネットワークによってリンクされるコンピューターを介して情報を処理するための分散コンピューターシステムが含まれる。中央演算装置又はプロセッサは、ソフトウエア命令を読み出し、実行するコンピューター、又はコンピューターの構成要素を指している。メモリ又はコンピューター可読媒体は、コンピューターによってアクセス可能なデータを格納するための任意の記憶装置を指している。その例には、磁気ハードディスク;フロッピィディスク;CD-ROM又はDVDのような光ディスク;磁気テープ;メモリチップ;電子メールを送受信する際に、又はネットワークにアクセスする際に用いられるような、コンピューター可読電子データを搬送するために用いられる搬送波、並びにコンピューターメモリ、たとえば、ランダムアクセスメモリが含まれる。ソフトウエアは、コンピューターを動作させるための所定の規則を指している。ソフトウエアの例には、ソフトウエア;コードセグメント;命令;コンピュータープログラム;及びプログラムされたロジックが含まれる。インテリジェントシステムのソフトウエアは、自己学習できる場合もある。モジュール又はユニットは、タスク又はタスクの一部を実行するコンピューター内の基本構成要素を指している。それはソフトウエア又はハードウエアのいずれかによって実装することができる。図1に示されるように、この発明の実施の形態は、1組のデータベース110のための差分プライバシー集合分類器170であって、該1組のデータベース内の各データベースの差分データプライバシーを保護するような差分プライバシー集合分類器170を求めるためのシステム及び方法100を開示する。この発明の実施の形態は、当該技術分野において既知であるように、メモリ及び入力/出力インターフェースを含むプロセッサ101によって実施することができる。1組のデータベース110内の各データベース120~130は、分類器、たとえば、分類器121及び131、並びに雑音値、たとえば、雑音値122及び132に関連付けられる。たとえば、データベースはD1、...、DKと表される。ただし、Di=|jは1組のエントリxと、対応する2値ラベルyとを含む。分類器及び雑音値の組み合わせがデータベースの差分データプライバシー125又は135を保証するように、分類器及び雑音値はデータベース毎にローカルに求められる。ローカルに求められるは、分類器及び雑音値が、方法100の実行前に、又は実行と同時にデータベースの各所有者によって独立して求められることを意味する。通常、差分プライバシーを保証するために、雑音値はデータベースのサイズ123又は133に依拠してデータベースの全データエントリにわたって求められる。本明細書において用いられるときに、データベースのサイズは、エントリの数に基づいている。エントリは任意のデータ構造を有することができる。しかしながら、各エントリのデータ構造は全てのデータベースにわたって同じである。エントリの例は、フィールド、表内の行、表自体、ファイル、又は別のデータベースである。この発明の実施の形態は、データベースの和集合D1∪D2...∪DKからの差分プライバシー集合分類器を、1組のデータベース内の最も小さなデータベースに対応する雑音値によって変更される各データベースの分類器の集合として求めることができるという認識に基づいている。最も小さなデータベースは最も少ないエントリ数を有し、各エントリのデータ構造は全てのデータベースについて同じである。この認識が正しいことの裏付けは、付録Aにおいて提供される。したがって、一実施の形態は、各データベースの分類器を組み合わせて、集合分類器145を求める。さらに、それらの実施の形態は、最も小さなデータベースに対応する雑音値155を求める。次に、雑音値155を用いて集合分類器145を変更し、差分プライバシー集合分類器170を生成する。差分プライバシー集合分類器は公開され、たとえば、メモリ175に格納されるか、又はインターネット上で配布される。差分プライバシー差分プライバシーモデルの定義によれば、1つの要素だけ異なる任意の2つのデータベースD及びD’、すなわち、隣接するデータベースが与えられたとすると、関数MがデータベースDにおいて応答Sを生成する確率が、関数MがデータベースD’において同じ応答Sを生成する確率と同様である場合には、ランダム化クエリ関数Mによって定義される分類器は差分プライバシーを有する。個々のエントリの存在又は不在時に、クエリ出力が高い確率で概ね同じであるので、出力からいかなる個々のエントリについてもほとんど何も突き止めることはできない。全ての隣接するデータベースD及びD’の場合に、かつ任意のS∈rangeの場合に、以下の式が成り立つ場合には、明確な確率密度Pを有するランダム化関数Mは、ε差分プライバシーを満たす。したがって、差分プライバシー分類器は、アプリオリの背景知識以外に、学習アルゴリズムの出力から確信を持って個々のエントリについてのさらに詳しい事柄を得ることができないことを保証する。差分プライバシーは、特定の1組の攻撃及び敵対的挙動に対してその場限りの保証を与える大部分の他のモデルとは対照的に、全てに通じる保証を与える。多数のエントリにわたって差分プライバシー分類器を評価しても、敵対者は、そのデータの厳密な形を突き止めることはできない。図2A~図2Cは、横軸に沿って雑音値を、縦軸においてそのような雑音値に関連付けられた確率を示す。したがって、高い確率を有する雑音値が、選択される可能性が高い。それらの分布は全て、絶対値が大きくなると、所与の雑音値の確率が小さくなるという有益な特徴を共有する。過度に高い雑音値の確率が起こる可能性は小さいので、この特徴によれば、雑音を含む出力を有用にすることができる。図2Aは、雑音値の指数分布210を示す。図2Bは、雑音値の正規分布220を示す。図2Cは、雑音値の混成分布230を示す。図2Cの混成分布は、最も確からしい雑音値を含む分布の部分、すなわち、より高い確率を有する部分を正規分布が定義し、最も確からしくない雑音値を含む分布の部分、すなわち、より大きな絶対雑音値に対応する低い確率を有する部分を指数分布が定義するような、正規分布及び指数分布である。図2A~図2Cにおいて各分布を計算する際に、差分直径240及びプライバシーパラメーターεを用いることができる。大きな差分直径値は分布を広くし、より高い雑音値が用いられる確率を高める。逆に、小さな差分直径は、大きな雑音値が選択される可能性を小さくする。プライバシーパラメーターが分布関数の分母にあるとき、小さい値のプライバシーパラメーターεが強いプライバシーに対応し、その逆も成り立つ。上記の例示的な式は満足できるものであり、それを用いて無限の様々な分布を構成することができ、それらの分布は差分直径測定値及びプライバシーパラメーターを利用して、満足できる雑音分布を作り出すのに成功する。たとえば、図2A~図2Cにおいて示される分布に対して無数の小さな変更を加えることができる。通常、それらの分類器は、分類器の重みに雑音値を加算することによって、差分プライバシーを有するように設計される。ただし、雑音値は上記の分布から選択される。さらに、分布のパラメーターは、イプシロンεによって表される所望のプライバシー度に依存し、それは通常、データベースのサイズに、かつ分類器の関数のタイプ、たとえば、平均関数、最大関数又は対数関数に依存する。一実施の形態では、雑音値はラプラス分布を有する。個々のデータベースにおいて分類器をローカルに求める各データベース所有者Pjが、そのデータベース|jを用いて、重みwjを有する分類器を求める。ただし、jはデータベースのインデックスである。一実施の形態は、分類器のために、正則化ロジスティック回帰関数l2を用いる。たとえば、分類器wjは、以下の目的関数を最小にすることによって求めることができる。ただし、λ>0は正則化パラメーターであり、Tは転置演算子である。しかしながら、それらの分類器は個々のデータベース毎にローカルに求められ、データ又は情報は共有されない。差分プライバシー集合分類器の例この発明の一実施の形態は、以下の式に従って、差分プライバシー集合分類器wS170を定義する。ただし、Kは1組のデータベース内のデータベースの数であり、jはデータベースのインデックスであり、ηはパラメーター2/ελを用いてスケーリングされるラプラス分布からサンプリングされるd次元確率変数であり、nは最も小さなデータベースに対応する雑音値、すなわち、n=minjnjであり、λはラプラス分布のパラメーターであり、εは差分プライバシーパラメーターである。差分プライバシー集合分類器wSは、パーティーがそのプライバシーを保持できるようにしながら、全てのデータの和集合において分類器を直にトレーニングすることによって、十分に制限された過剰リスクのみを受ける。雑音値ηは、分類器wSが差分プライバシーを満たすことを、すなわち、分類器から個々のデータインスタンスを判別できないことを保証する。上記の雑音値ηの定義は直観的ではなく、この発明によれば、ローカルにトレーニングされた分類器を集めることによって構成された差分プライバシー集合分類器が、最も少ない数のエントリを有する個々の分類器の性能によって制限されることが証明された。ローカルにトレーニングされた分類器を集めても、差分プライバシーを保証する正しい雑音値を与えないので、この発明のいくつかの実施の形態は、データベースPjの所有者は、単にそのような分類器wjを取り込み、雑音ベクトルを用いてそれらの分類器を摂動させて、摂動した分類器を公開することはできないという認識に基づいている。また、個々のデータベース所有者は、他の全ての分類器に対して差分プライバシーを課すために、それらの分類器に単に雑音を加算することはできないので、個々の分類器、又は各データベース内のエントリの数が暴かれないように、実際の平均化演算を実行しなければならない。したがって、いくつかの実施の形態は、プロセッサとインタラクトして平均化を実行するために、セキュアマルチパーティー計算法を用いる。その方法の結果として、データベース所有者のそれぞれが所望の差分プライバシー分類器wSの加法的持分を得るようになり、差分プライバシー集合分類器を得るために、これら持分を加算しなければならないようになっている。セキュアマルチパーティー計算法それらの実施の形態は、非対称鍵加法的準同型暗号化を用いる。そのような暗号化の所望の特性は、暗号文要素において実行される演算が同じ平文要素における既知の演算に写像することである。加法的準同型暗号化関数の場合、ξは、任意のa及びbに対して、ξξ=ξ、ξb=ξであることを意味する。加法的準同型暗号化は強秘匿性であり、すなわち、同じ平文を繰返し暗号化しても、結果として、異なる暗号文が生成される。SMC法の場合、暗号鍵は、公開されていると考えられ、解読鍵は、指定されたデータベース所有者によって非公開で所有される。図3は、SMC法を用いて、差分プライバシー集合分類器170を求めるための方法300のブロック図を示す。その方法はプロセッサ301によって実行することができる。最も小さなデータベースの不明瞭化インデックスを求めるプロセッサは、データベースのインデックスの置換から生じる置換済みインデックス320に基づいて最も小さなデータベースの不明瞭化インデックス315を求める。たとえば、各データベース所有者、すなわち、パーティーPjが、nj=ajbjを計算する。ただし、aj及びbjはデータベース長njの加法的持分を表す整数であり、j=1、2、...、Kである。加法的持分のK長ベクトルはそれぞれa及びbと定義される。パーティーPjは、インデックスベクトルに関する置換π1に互いに合意する。この置換はプロセッサには未知である。その後、各パーティーPjは、その持分ajを代表するパーティーに送信し、置換に従ってインデックスが変更されている自身の持分bjをプロセッサに送信する。したがって、そのステップの後に、そのパーティーは、π1によって与えられる置換済み加法的持分を有し、一方、プロセッサは、置換済み加法的持分π1を有する。パーティーPjは鍵対を生成する。ただし、pkは準同型暗号化のための公開鍵であり、skはパーティーにのみ知られており、プロセッサには知られていない秘密解読鍵である。aの要素単位の暗号化はξと定義される。パーティーは、プロセッサに、ξ=π1を送信する。プロセッサは、ランダムベクトルr=を生成する。ただし、要素riは無作為に均等に選択される整数であり、同程度に正又は負である可能性がある。その後、プロセッサは、ξξ=ξrjを計算する。ベクトル表記では、プロセッサはξrを計算する。同様に、受信された加法的持分と同じ順序において同じ乱数整数を減算することによって、プロセッサはπ1-rを得て、無作為に置換π2を選択し、信号及び信号π2-rを得る。プロセッサは信号ξrを個々のパーティーに順に、たとえば、第1のパーティーP1に第1の要素を、第2のパーティーP2に第2の要素を、第KのパーティーPKに第Kの要素を送信する。各パーティーは、プロセッサから受信された信号を解読する。すなわち、パーティーP1、P2、...、PKはそれぞれ、ベクトルπ2rの要素を有し、一方、プロセッサはベクトルπ2-rを有する。π1はプロセッサには未知であり、π2はパーティーには未知であるので、両方のベクトル内のインデックスは不明瞭化される。かつである場合には、以下の式が成り立つ。対毎に、セキュアな億万長者プロトコルを実施することによって、これらの比較を解くことができる。全ての比較が行われたとき、プロセッサは、が成り立つようなインデックス325を求める。しかしながら、最も小さなデータセットに対応する真のインデックスは不明瞭化される。最も小さなデータベースの雑音値の第1の加法的持分をオブリビアスに選択する不明瞭化インデックス315に基づいて、プロセッサは、全ての雑音値の加法的持分340から、最も小さなデータベースに関連付けられた雑音値の第1の加法的持分335をオブリビアスに選択する。最も小さなデータベースに関連付けられた雑音値の第2の加法的持分360が1つ又は複数のデータベースによって格納される。たとえば、プロセッサは、であり、かつ他の全ての要素が0であるような、長さKのインジケーターベクトルuを構成する。その後、プロセッサは、インジケーターベクトルを置換して、置換済みベクトルπ2-1を生成する。ただし、π2-1はπ2を反転する。次に、プロセッサは、加法的準同型関数ζのための鍵対を生成し、パーティーPjにζ=π2-1を送信する。ただし、暗号鍵pk’だけが、パーティーPjが利用できるように公開される。パーティーは、置換済みベクトルπ1-1=ζを互いに入手する。ただし、π1-1は、パーティーPjによって当初に適用された置換π1を反転し、vは基底ベクトルである。ここで両方の置換が除去されたので、インジケーターベクトルv内の0以外の要素のインデックスは、最も小さなデータベースの真のインデックスに対応する。しかしながら、パーティーPjはζを解読することができないので、パーティーはこのインデックスを見つけ出すことはできない。j=1、...、Kについて、パーティーPjは雑音値ηjを選択する。一実施の形態では、雑音値は、パラメーター2/を有するラプラス分布からサンプリングされるd次元雑音ベクトルである。別の実施の形態では、異なる分布から雑音ベクトルが選択される。さらに別の実施の形態では、雑音ベクトルは予め決定される。その後、パーティーはd次元ベクトルΨjを入手する。ただし、i=1、...、dについて、以下の式が成り立つ。全てのパーティーPjが、i=1、...、dについて、以下の式が成り立つようなd次元雑音ベクトルΨを計算する。構成によって、上記の式は、他の全てのデータベースのための雑音値を拒否しながら、最も小さなデータベースのための雑音値のみを選択する。これは、vが最も小さなデータベースに対応するインデックスにおいて値1を有する要素を有し、他の全ての場所において0を有するためである。パーティーのうちの1つ、たとえば、P1が、d次元乱数整数雑音ベクトルSを生成し、それにより、全てのi=1、...、dについて第1の加法的持分335ψζを生成し、第1の加法的持分をプロセッサに送信する。また、パーティーP1は、たとえば、w1-Ksを計算することによって、雑音値の第2の加法的持分360を格納する。ただし、w1はそのパーティーの分類器である。付加的に又は代替的に、第2の加法的持分は複数のデータベースによって格納される。プロセッサは、i=1、...、dについて、ψξを解読して、ηsを入手する。したがって、プロセッサは、最も小さなデータベースに関連付けられた雑音値の第1の加法的持分をKとして格納し、選択されたパーティーP1が雑音値の第2の加法的持分及び分類器をw1-Ksとして格納し、他の全てのパーティーPjが分類器wjを格納する。分類器、第1の加法的持分及び第2の加法的持分をオブリビアスに組み合わせる種々の実施の形態において、プロセッサ、及びデータベースを所有するK個のパーティーは、K1人の関係者のそれぞれが差分プライバシー集合分類器KwSの加法的持分を入手するように、セキュアな関数評価プロトコルを実行する。いくつかの実施の形態では、加法的持分は、計算上セキュアなプロトコルを用いて生成される。他の実施の形態では、加法的持分は、無条件にセキュアなプロトコルを用いて生成される。結果として生成されるK1個の持分は、差分プライバシー集合分類器を形成し、公開され、たとえば、メモリ175に格納される。付録Aマルチパーティー環境における差分プライバシーのための理論的証明最も小さなデータベースのサイズに基づいて確率的成分を選択すれば十分である。以下において、これが事実であるという理論的証明が与えられる。差分プライバシーの証明この発明における摂動集合分類器は差分プライバシーを満たすことを示す。正則化回帰分類器の感度に関する以下の限界を用いる。定理1半径1の球体内に存在するn個のデータインスタンスの集合を与えるとき、正則化ロジスティック回帰関数の感度は高くても2/である。w1及びw2が正則化パラメーターλを用いてサイズnの隣接するデータベースにおいてトレーニングされた関数であるとすると、以下の式が成り立つ。この限界は、KamalikaChaudhuri及びClaireMonteleoniPrivacypreservinglogisticregressionによって証明されており、その文献は参照により本明細書に援用される。この発明における摂動関数又は分類器が差分プライバシーを満たすことを示すために、以下のように進める。定理2分類器wSはε差分プライバシーを保護する。任意の2つの隣接するデータベースD及びD’について、以下の式が成り立つ。証明トレーニングデータベースDの1つのインスタンスが変更され、結果として隣接するデータベースD’が生成される場合について考える。これは、1つのパーティーのトレーニングデータベース内の1つの要素の変更、それにより、対応する学習されたベクトルwSj内の変更を意味するであろう。その変更がパーティーPjのデータベース内にあると仮定すると、学習されたベクトルの変更はwj内に入るだけである。新たな分類器をwj’によって表すものとする。定理1において、wjの感度を||wj-wj’||1≦2/と制限する。トレーニングデータベースD及びD’のいずれかを用いて同じベクトルwSを学習することを考えるとき、関数感度の定義によって、以下の式が得られる。同様に、expによって、その比の下限を設定することができる。過剰誤差の解析予想されるように、摂動雑音項を付加することによって、関数評価において誤差が導入される。分類器として用いられる関数の場合、この誤差は過剰誤差又は過剰リスクと呼ばれる。それは、差分プライバシーに対して支払われる対価である。差分プライバシー分類器が有用であるためには、過剰リスクは小さいことが望ましい。言い換えると、雑音を付加することによって、分類性能をあまりにも劣化させないことが望ましい。上記の検討において、トレーニングデータ全体においてトレーニングされた非プライバシー非摂動分類器wに対して、この発明における摂動集合分類器wSを用いるときに、どの程度の誤差が導入されるかを考える。また、非摂動集合分類器wに対して、どの程度の誤差が導入されるかも考える。最初に、集合分類器wと、トレーニングデータ全体にわたってトレーニングされた分類器wとの間の差のl2ノルムに関する限界を確立する。その限界を証明するために、以下の補助定理を適用する。補助定理1G及びgをwの2つの区別可能な凸関数とする。とすると、||w1-w2||≦g1/G2である。ただし、任意の単位ベクトルv∈Rdについて、g1=maxw||∇g||及びG2=minvminwvT∇2Gvである。補助定理1は、KamalikaChaudhuri及びClaireMonteleoniPrivacypreservinglogisticregressionから得られたものであり、その文献は参照により本明細書に援用される。最初に、非プライバシー非摂動集合分類器wと、データベース全体において調整された非プライバシー分類器wとの間の過剰リスクを制限する以下の定理を考える。定理3集合分類器w、トレーニングデータ全体にわたってトレーニングされた分類器wが与えられ、nが最も小さなトレーニングデータベースのサイズであるとすると、以下の式が成り立つ。証明:2つの区別可能な凸関数g及びGを最小にすることに関して、個々の分類器wj及びトレーニングデータ全体にわたってトレーニングされた分類器wを推定するという問題を定式化する。補助定理6.2におけるg1及びG2に関する限界を代入すると、以下の式が成り立つ。三角不等式を適用すると、以下の式が成り立つ。ただし、n=minjnjである。その限界は、最も小さなデータベース内のインスタンスの数に反比例する。これは、データベースが異なるサイズからなるとき、wはwとは大きくことなることを示す。nが取り得る最も大きな値はn/Kであり、その場合、全てのパーティーが等しい量のトレーニングデータを有し、wはwに最も近くなるであろう。K=1の場合の1つのパーティーの事例では、その限界は、差のノルムの上限が0に設定されることを示し、それは、集合分類器wがwと同じであるときに有効なサニティーチェックである。この結果を用いて、以下の定理において、非摂動分類器wの経験的リスクを上回る摂動集合分類器wS=wηの経験的リスクに関する限界を確立する。定理4全てのデータインスタンスxiが、少なくとも1-δの確率で単位球内に存在する場合には、トレーニングデータ全体にわたってトレーニングされた分類器wを上回る摂動集合分類器wSの経験的正則化過剰リスクは以下の通りである。証明:或るについて、関数Jのテイラー級数展開を用いて、以下の式が得られる。定義により、∇J=0である。両辺のl2ノルムを取り、コーシー-シュワルツ不等式を適用すると、以下の式が得られる。ロジスティック回帰のための正則化損失関数の第二勾配は以下の通りである。ロジスティック関数項は常に1未満であり、かつ全てのxiが単位球内に存在するので、||∇2J||≦λ1である。これを式8に代入し、の場合に、J≦Jであるという事実を用いるとき、以下の式が成り立つ。分類器wSは、雑音項η:Lapελを有する摂動集合分類器であり、すなわち、wS=wηである。少なくとも1-δの確率で||η||を制限するために、KamalikaChaudhuri及びClaireMonteleoniPrivacypreservinglogisticregressionからの以下の補助定理を適用し、その文献は参照により本明細書に援用される。補助定理2少なくとも1-δの確率を有するd次元の確率変数η:Lap、すなわち、が与えられたとすると、その確率変数のl2ノルムは以下のように制限される。これを式9に代入すると、以下の式が得られる。最後の項においてコーシー-シュワルツ不等式を用いると、以下の式が得られる。その限界は、2つの要因:集合及び摂動による誤差を示唆する。εの値が小さいほど、同じ意味で、差分プライバシーの定義が厳しいほど、その限界は増大し、プライバシーと有用性との間に明らかなトレードオフがあることを示す。また、その限界はn2に反比例し、それは、パーティーが異なるサイズのトレーニングデータベースを有するときに、過剰リスクが増加することを意味する。極端な事例ε→∞では、無限小の分散のラプラシアン分布からサンプリングされる摂動項ηを加算しており、結果として、その摂動分類器は、差分プライバシーのあまり厳密でない定義を満たす非摂動集合分類器wを用いるのと概ね同じである。そのようなε値の場合、この発明の限界は以下のようになる。定理3の解析と同じように、集合分類器を用いる際の過剰誤差は最も小さなデータベースnのサイズに反比例し、1パーティーの事例K=1では、集合分類器wがwと同じであるので、その限界は0になる。上記の定理は所与のトレーニングデータベースを上回る経験的過剰リスクに関する限界を与えるが、wを上回るwSの真の過剰リスクに関する限界について考えることが重要である。分類器wSの真のリスクをによって表し、同様に、分類器wの真のリスクをによって表すことにする。定理5全てのトレーニングデータインスタンスxiが、少なくとも1-δの確率で単位球内に存在する場合には、トレーニングデータ全体にわたってトレーニングされた分類器wを上回る摂動集合分類器wSの真の過剰リスクは以下の通りである。証明:wrを真のリスクを最小にする分類器とする。項を並べ替えることによって、以下の式が得られる。さらに進むために、最初に、分類器のための正則化経験的リスクに関する限界の表現としての任意の分類器の真の過剰リスクと、正則化経験的リスクを最小にする分類器の真の過剰リスクとの間の限界を必要とする。少なくとも1-δの確率で、以下の式が成り立つ。定理4からの限界を代入すると、以下の式が得られる。この限界を式10に代入することによって、分類器wを上回る分類器wSの真の過剰リスクに関する限界が与えられる。