(57)【特許請求の範囲】
【請求項１】
複数のデータサンプルから複数のトレーニングサンプルを決定するためのコンピュータ実装される方法であって、前記複数のデータサンプルの各々は１つまたは複数の特徴値とそのデータサンプルを分類するラベルとを備え、前記方法は、
前記複数のデータサンプルのサブセットをランダムに選択し、前記トレーニングサンプルの特徴の前記特徴値が前記データサンプルのその特徴の前記特徴値の組み合わせとなるように、前記サブセットの前記データサンプルの各々の前記ラベルに基づいて、前記サブセットの前記データサンプルの前記特徴値を組み合わせることによって、前記複数のトレーニングサンプルの各々を決定することを備える方法。
【請求項２】
前記複数のデータサンプルの前記サブセットをランダムに選択することは、前記複数のデータサンプルの各々に、そのデータサンプルを選択するためにゼロに等しくないランダム選択値を、またはそのデータサンプルを選択解除するためにゼロに等しいランダム選択値を乗算することを備える、請求項１に記載の方法。
【請求項３】
前記データサンプルの前記特徴値を組み合わせることは、前記トレーニングサンプルの特徴の前記特徴値が前記データサンプルのその特徴の前記特徴値の和となるように、前記データサンプルの前記特徴値の和を決定することを備える、請求項１または２に記載の方法。
【請求項４】
前記和を決定することは、前記データサンプルの各々の前記ラベルに基づいて重み付けされる加重和を決定することを備える、請求項３に記載の方法。
【請求項５】
前記和を決定することは、前記複数のデータサンプルの前記サブセット中のデータサンプルの数に基づいて重み付けされる加重和を決定することを備える、請求項３または４に記載の方法。
【請求項６】
前記加重和は、前記複数のデータサンプルの前記サブセットをランダムに選択することが前記特徴値を組み合わせることと同時に実施されるように、乱数に基づいて重み付けされる、請求項４または５に記載の方法。
【請求項７】
複数のデータサンプルのサブセットをランダムに選択することが、非一様分布に基づいて複数のデータサンプルのサブセットをランダムに選択することを備える、請求項１〜６のいずれか一項に記載の方法。
【請求項８】
前記データサンプルは符号付きの実数値を特徴値として有し、
前記ラベルは「−１」および「＋１」のいずれかである、請求項１〜７のいずれか一項に記載の方法。
【請求項９】
前記複数のトレーニングサンプルの各々を決定することは、前記複数のトレーニングサンプルの各々が少なくとも所定数のデータサンプルに基づくように、前記複数のトレーニングサンプルの各々を決定することを備える、請求項１〜８のいずれか一項に記載の方法。
【請求項１０】
前記複数のデータサンプルのサブセットをランダムに選択することは、少なくとも所定数のデータサンプルを備える前記複数のデータサンプルのサブセットをランダムに選択することを備える、請求項９に記載の方法。
【請求項１１】
複数のトレーニングサンプルを決定するためのコンピュータ実装される方法であって、  請求項１に従ってトレーニングサンプルを受信することと、
修正されたトレーニングサンプルを決定するために、前記トレーニングサンプルの各特徴値ごとにランダム値を決定し、その特徴値に前記ランダム値を加えることとを備える方法。
【請求項１２】
コンピュータにインストールされると、請求項１〜１１のいずれか一項に記載の方法を前記コンピュータに実施させるソフトウェア。
【請求項１３】
複数のデータサンプルから複数のトレーニングサンプルを決定するためのコンピュータシステムであって、
前記複数のデータサンプルを受信する入力ポートと、前記複数のデータサンプルの各々は、１つまたは複数の特徴値およびそのデータサンプルを分類するラベルを備え、
前記複数のデータサンプルのサブセットをランダムに選択し、前記トレーニングサンプルの特徴の前記特徴値が前記データサンプルのその特徴の前記特徴値の組み合わせとなるように、前記サブセットの前記データサンプルの各々の前記ラベルに基づいて、前記サブセットの前記データサンプルの前記特徴値を組み合わせることによって、前記複数のトレーニングサンプルの各々を決定するプロセッサとを備えるコンピュータシステム。
【請求項１４】
特徴インデックスに関係付けられる分類器係数を決定するためのコンピュータ実装される方法であって、
前記特徴インデックスに関係付けられる複数のトレーニング値を受信することと、ここにおいて、
前記複数のトレーニング値は複数のデータ値から決定され、
前記複数のデータ値の各々は、データラベルと関連し、
各トレーニング値は、各々のデータ値に関連した前記データラベルに基づいた前記複数のデータ値のサブセットの組合せに基づいており、
相関値が複数のデータ値の各々とそのデータ値に関係付けられる前記データラベルとの間の相関を示すように、前記複数のトレーニング値に基づいて前記相関値を決定することと、
前記相関値に基づいて前記分類器係数を決定することとを備える方法。
【請求項１５】
前記複数のトレーニング値の各々に対して、そのトレーニング値に関係付けられるトレーニング値重みを決定すること、ここにおいて、前記相関値を決定することは、前記複数のトレーニング値の各々に関係付けられる前記トレーニング値重みに基づく、をさらに備える、請求項１４に記載の方法。
【請求項１６】
前記相関値を決定することは、前記複数のトレーニング値の各々に関係付けられる前記トレーニング値重みによって重み付けされたトレーニング値の和を決定することを備える、請求項１５に記載の方法。
【請求項１７】
前記相関値を決定することは、
最大トレーニング値を決定することと、
前記和を前記最大トレーニング値で除算することとを備える、請求項１６に記載の方法。
【請求項１８】
前記トレーニング値の各々に関係付けられる前記トレーニング値重みを決定することは、前記相関値に基づいて、前記複数のトレーニング値の各々に関係付けられる前記トレーニング値重みを決定することを備える、請求項１５〜１７のいずれか一項に記載の方法。
【請求項１９】
前記複数のトレーニング値のうちの１つに関係付けられる各トレーニング値重みを決定することは、
最大トレーニング値を決定することと、
前記最大トレーニング値に対する前記複数のトレーニング値のうちの１つの割合に基づいて、前記トレーニング値重みを決定することとを備える、請求項１８に記載の方法。
【請求項２０】
複数の分類器係数を決定するために前記方法の複数の繰り返しを実施すること、ここにおいて、各分類器係数は複数の特徴インデックスのうちの１つに関係付けられる、をさらに備える、請求項１４〜１９のいずれか一項に記載の方法。
【請求項２１】
前記複数のトレーニング値の各々に対して、そのトレーニング値に関係付けられるトレーニング値重みを決定すること、ここにおいて、前記相関値を決定することは、前記複数のトレーニング値の各々に関係付けられる前記トレーニング値重みに基づく、をさらに備え、
前記トレーニング値重みを決定することは、現在の繰り返しの正則化関数の第１の値と、以前の繰り返しの前記正則化関数の第２の値との差に基づいて、前記トレーニング値重みを決定することを備える、請求項２０に記載の方法。
【請求項２２】
前記正則化関数は、前記対応する繰り返しに関係付けられる前記複数の分類器係数に依存する、請求項２１に記載の方法。
【請求項２３】
前記トレーニング値重みを決定することは、指数を有する指数関数に基づいて、前記差を前記指数に加えることによって、前記トレーニング値重みを決定することを備える、請求項２１または２２に記載の方法。
【請求項２４】
前記正則化関数は、
リッジ関数、
ラッソ関数、
Ｌ∞正則化、および
ＳＬＯＰＥ正則化のうちの１つまたは複数を備える、請求項２１〜２３のいずれか一項に記載の方法。
【請求項２５】
複数の特徴インデックスの順序付けに基づいて前記特徴インデックスを選択すること、ここにおいて、前記順序付けは前記差に基づく、をさらに備える、請求項２１〜２４のいずれか一項に記載の方法。
【請求項２６】
前記方法を繰り返すことは、前記複数のデータ値のコスト関数を最適化するために前記方法を繰り返すことを備える、請求項２０〜２５のいずれか一項に記載の方法。
【請求項２７】
テスト値を受信することと、
前記分類器係数に基づいて前記テスト値の分類を決定することとをさらに備える、請求項１４〜２６のいずれか一項に記載の方法。
【請求項２８】
コンピュータにインストールされると、請求項１４〜２７のいずれか一項に記載の方法を前記コンピュータに実施させるソフトウェア。
【請求項２９】
特徴インデックスに関係付けられる分類器重みを決定するためのコンピュータシステムであって、
前記特徴インデックスに関係付けられる複数のトレーニング値を受信する入力ポートと、ここにおいて、
前記複数のトレーニング値は複数のデータ値から決定され、
前記複数のデータ値の各々は、データラベルと関連し、
各トレーニング値は、各々のデータ値に関連した前記データラベルに基づいた前記複数のデータ値のサブセットの組合せに基づいており、
相関値が前記複数のデータ値の各々とそのデータ値に関係付けられる前記データラベルとの間の相関を示すように、前記複数のトレーニング値に基づいて前記相関値を決定し、前記相関値に基づいて前記分類器重みを決定するプロセッサとを備えるシステム。
【請求項３０】
機械学習システムをトレーニングするためのコンピュータ実装される方法であって、凸損失関数を最適化することを備え、前記凸損失関数は、請求項１に記載の方法に従って決定されたトレーニングサンプルに基づく、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照
本願は、２０１４年１０月２４日に出願されたオーストラリア国仮特許出願第２０１４９０４２６１号の優先権を主張するものであり、そのすべての内容が参照によって本願に援用される。本願はまた、２０１５年２月２日に出願されたオーストラリア国仮特許出願第２０１５９００３０８号の優先権を主張するものであり、そのすべての内容が参照によって本願に援用される。
【０００２】
本開示は、変換されたデータを用いた学習に関する。
【背景技術】
【０００３】
インターネットを介してサービスまたは製品を提供する企業は多くの場合、顧客から広範なデータを収集し、クライアントの行動に関する集約された洞察を得るためにこのデータを処理する。
【０００４】
図１は、スマートフォン１０８、１１０、１１２などの３つのそれぞれのインターネット対応通信デバイスを動作させる３名の参加する顧客またはユーザ１０２、１０４、１０６を伴う、従来技術の企業中心型コンピュータネットワーク１００を示す。ユーザ１０２、１０４、１０６は、ソーシャルメディアプロバイダ１１４に登録されており、自身の好みの指示を与えること、コメントを投稿すること、または写真をアップロードおよびタグ付けすることによって、互いにインタラクトする。本質的に、これらのアクティビティは、ソーシャルメディアプロバイダ１１４によって操作されるデータベース１１６に３名のユーザ１０２、１０４、１０６に関係する個人データを記憶することを伴う。
【０００５】
サーバ１１８がデータベース１１６に接続されており、このサーバ１１８は、集約された情報を導出するために、データベース１１６に記憶されたユーザデータを分析する。次いで、その結果は、広告会社１２０などのサードパーティに販売され得る。しかしながら、ユーザ１０２、１０４、および１０６は、プライベートなまたは機密の情報を共有することに消極的である。したがって、ユーザ１０２、１０４、および１０６に関連するプライベートなまたは極秘のデータに基づいて集約的な洞察を導き出すことは困難である。
【０００６】
本明細書に含められている文書、行為、材料、デバイス、物品などの議論は、これらの事項のいずれかまたはすべてが先行技術の基礎の一部を形成するか、または、本願の各請求項の優先日の前に存在していたものとして、本開示に関連する分野における共通の一般知識であることを認めるものとはみなされない。
【０００７】
本明細書の全体を通じて、「備える（ｃｏｍｐｒｉｓｅ）」という単語、または「備える（ｃｏｍｐｒｉｓｅｓ）」または「備えている（ｃｏｍｐｒｉｓｉｎｇ）」などの変化形は、記載された要素、整数もしくはステップ、または要素、整数もしくはステップのグループを含むことを意味するが、他の要素、整数、もしくはステップ、または要素、整数、もしくはステップのグループを除外することを意味しないと理解されよう。
【発明の概要】
【０００８】
複数のデータサンプルから、複数のトレーニングサンプルを決定するためのコンピュータ実装される方法であって、複数のデータサンプルの各々が１つまたは複数の特徴値とそのデータサンプルを分類するラベルとを備える方法が提供される。その方法は、
複数のデータサンプルのサブセットをランダムに選択し、そのサブセットのデータサンプルの各々のラベルに基づいて、サブセットのデータサンプルの特徴値を組み合わせることによって、複数のトレーニングサンプルの各々を決定することを備える。
【０００９】
トレーニングサンプルは、ランダムに選定されたデータサンプルの組合せであるため、トレーニングサンプルは、実際のトレーニングデータを開示することなく、サードパーティに提供され得る。このことは、たとえば、データが極秘であり、したがって分類器の学習器と共有されるべきでない場合に、既存の方法と比べて有利である。
【００１０】
この方法は、複数のトレーニングサンプルを記憶することを備え得る。この方法は、それらを記憶してまたはそれらを記憶することなく、コンピュータシステムに複数のトレーニングサンプルを送ることを備え得る。２つの組合せは共通のデータサンプルを有し得る。
【００１１】
複数のデータサンプルのサブセットをランダムに選択することは、複数のデータサンプルの各々に、そのデータサンプルを選択するためにゼロに等しくないランダム選択値を、またはそのデータサンプルを選択解除するためにゼロに等しいランダム選択値を乗算することを備え得る。
【００１２】
ゼロに等しくないランダム選択値は「１」であってもよい。
【００１３】
データサンプルの特徴値を組み合わせることは、トレーニングサンプルの特徴の特徴値がデータサンプルのその特徴の特徴値の和となるように、データサンプルの特徴値の和を決定することを備え得る。
【００１４】
和を決定することは、データサンプルの各々のラベルに基づいて重み付けされる加重和を決定することを備え得る。
【００１５】
和を決定することは、複数のデータサンプルのサブセット中のデータサンプルの数に基づいて重み付けされる加重和を決定することを備え得る。
【００１６】
ラベル依存重みの結果として、同一のデータサンプルではあるが異なるラベルを有するデータサンプルは、加重和の結果に対する影響を低減させる。したがって、和の結果は、この特徴が種々のラベルへの分類にいかに関係するかを示す。
【００１７】
加重和は、複数のデータサンプルのサブセットをランダムに選択することが特徴値を組み合わせることと同時に実施されるように、乱数に基づいて重み付けされ得る。
【００１８】
複数のデータサンプルのサブセットをランダムに選択することは、非一様分布に基づいて複数のデータサンプルのサブセットをランダムに選択することを備え得る。
【００１９】
データセット全体にわたるトレーニングサンプルの非一様分布が、一様分布の場合と比較してデータセットの再構築をより困難にすることが有利である。
【００２０】
データサンプルは、符号付きの実数値を特徴値として有し得、ラベルは「−１」および「＋１」のいずれかであり得る。
【００２１】
複数のトレーニングサンプルの各々を決定することは、複数のトレーニングサンプルの各々が少なくとも所定数のデータサンプルに基づくように、複数のトレーニングサンプルの各々を決定することを備え得る。
【００２２】
複数のデータサンプルのサブセットをランダムに選択することは、少なくとも所定数のデータサンプルを備える複数のデータサンプルのサブセットをランダムに選択することを備え得る。
【００２３】
複数のトレーニングサンプルを決定するためのコンピュータ実装される方法は、
上記の方法に従ってトレーニングサンプルを受信することと、
修正されたトレーニングサンプルを決定するために、トレーニングサンプルの各特徴値ごとにランダム値を決定し、その特徴値にランダム値を加えることとを備える。
【００２４】
ランダム値の追加は低い複雑性を有するが、それと同時に、トレーニングサンプルに付加的な差分プライバシーをもたらすことが有利である。データに直接ノイズを加える他の技法は、重要な保護層がデータを破壊するのに必要とされるノイズのレベルを、学習した分類器が低い品質を有する程度にする。対照的に、提案する方法は、複数のデータサンプルをすでに組み合わせているトレーニングサンプルにノイズを加えるものである。その結果、データに対するノイズの破壊的影響はより少なく、要求されるプライバシー保護を考慮すれば、分類の結果はより良好となる。
【００２５】
修正されたトレーニングサンプルを決定することは、トレーニングサンプルを決定することとは異なるコンピュータシステムによって実施され得る。
【００２６】
コンピュータにインストールされると、上記の方法をコンピュータに実施させるソフトウェア。
【００２７】
複数のデータサンプルから複数のトレーニングサンプルを決定するためのコンピュータシステムが提供される。そのコンピュータシステムは、
複数のデータサンプルを受信する入力ポートと、複数のデータサンプルの各々は、１つまたは複数の特徴値と、そのデータサンプルを分類するラベルとを備え、
複数のデータサンプルのサブセットをランダムに選択し、サブセットのデータサンプルの各々のラベルに基づいて、サブセットのデータサンプルの特徴値を組み合わせることによって、複数のトレーニングサンプルの各々を決定するプロセッサとを備える。
【００２８】
特徴インデックスに関係付けられる分類器係数を決定するためのコンピュータ実装される方法が提供される。その方法は、
特徴インデックスに関係付けられる複数のトレーニング値を受信することと、各トレーニング値は、複数のデータラベルに基づいた複数のデータ値のサブセットの組合せに基づき、複数のデータラベルの各々は複数のデータ値のうちの１つと関係付けられる、
相関値が複数のデータ値の各々とそのデータ値に関係付けられるデータラベルとの間の相関を示すように、複数のトレーニング値に基づいて相関値を決定することと、
相関値に基づいて分類器係数を決定することとを備える。
【００２９】
相関値はトレーニング値に対して決定され、データ値に対して決定されるものではないので、実際のデータ値を知ることなく分類器をトレーニングすることが可能である。このことは、データが極秘であり、したがって分類器の学習器と共有されるべきでない場合に、既存のブースティングアルゴリズムと比べて有利である。分類器係数を決定することは、分類器係数の以前の値に基づいて分類器を更新することを備え得る。
【００３０】
本方法は、複数のトレーニング値の各々に対して、そのトレーニング値に関係付けられるトレーニング値重みを決定すること、ここにおいて、相関値を決定することは、複数のトレーニング値の各々に関係付けられるトレーニング値重みに基づき得る、をさらに備え得る。
【００３１】
相関値を決定することは、複数のトレーニング値の各々に関係付けられるトレーニング値重みによって重み付けされたトレーニング値の和を決定することを備え得る。
【００３２】
相関値を決定することは、
最大トレーニング値を決定することと、
和を最大トレーニング値で除算することとを備え得る。
【００３３】
トレーニング値の各々に関係付けられるトレーニング値重みを決定することは、相関値に基づいて、複数のトレーニング値の各々に関係付けられるトレーニング値重みを決定することを備え得る。
【００３４】
トレーニング値重みを決定することは、トレーニング値重みの以前の値に基づいて、トレーニング値重みを更新することを備え得る。
【００３５】
複数のトレーニング値のうちの１つに関係付けられる各トレーニング値重みを決定することは、
最大トレーニング値を決定することと、
最大トレーニング値に対する複数のトレーニング値のうちの１つの割合に基づいて、トレーニング値重みを決定することとを備え得る。
【００３６】
本方法は、複数の分類器係数を決定するために方法の複数の繰り返しを実施すること、各分類器係数は複数の特徴インデックスのうちの１つに関係付けられる、をさらに備え得る。
【００３７】
第１の特徴インデックスに関係付けられる第１の分類器重みは第１の繰り返しで決定され得、第２の特徴インデックスに関係付けられる第２の分類器重みは第２の繰り返しで決定され得る。第１の特徴インデックスは、第２の特徴インデックスと等しくても異なっていてもよい。
【００３８】
トレーニング値重みを決定することは、現在の繰り返しの正則化関数の第１の値と、以前の繰り返しの正則化関数の第２の値との差に基づいて、トレーニング値重みを決定することを備え得る。
【００３９】
正則化関数は、対応する繰り返しに関係付けられる複数の分類器係数に依存し得る。
【００４０】
トレーニング値重みを決定することは、指数を有する指数関数に基づいて、差を指数に加えることによって、トレーニング値重みを決定することを備え得る。
【００４１】
正則化関数は、
リッジ関数、
ラッソ関数、
Ｌ∞正則化、および
ＳＬＯＰＥ正則化のうちの１つまたは複数を備え得る。
【００４２】
本方法は、複数の特徴インデックスの順序付けに基づいて特徴インデックスを選択すること、ここにおいて、順序付けは差に基づく、をさらに備え得る。
【００４３】
方法を繰り返すことは、複数のデータ値のコスト関数を最適化するために方法を繰り返すことを備え得る。
【００４４】
本方法は、
テスト値を受信することと、
分類器係数に基づいてテスト値の分類を決定することとをさらに備え得る。
【００４５】
コンピュータにインストールされると、特徴インデックスに関係付けられる分類器係数を決定するための上記の方法をコンピュータに実施させるソフトウェア。
【００４６】
特徴インデックスに関係付けられる分類器重みを決定するためのコンピュータシステムが提供される。そのコンピュータシステムは、
特徴インデックスに関係付けられる複数のトレーニング値を受信する入力ポートと、各トレーニング値は、複数のデータラベルに基づいた複数のデータ値のサブセットの組合せに基づき、複数のデータラベルの各々は複数のデータ値のうちの１つと関係付けられる、
プロセッサと、そのプロセッサは、
相関値が複数のデータ値の各々とそのデータ値に関係付けられるデータラベルとの間の相関を示すように、複数のトレーニング値に基づいて相関値を決定し、
相関値に基づいて分類器係数を決定する、を備える。
【００４７】
機械学習システムをトレーニングするためのコンピュータ実装される方法であって、凸損失関数を最適化すること、凸損失関数は、複数のデータサンプルから複数のトレーニングサンプルを決定するための上記の方法に従って決定されたトレーニングサンプルに基づく方法が提供される。
【００４８】
方法、コンピュータ可読媒体またはコンピュータシステムの任意の態様の任意選択の特徴が、必要に応じて、同様に本明細書で説明した他の態様に同様に当てはまる。
【図面の簡単な説明】
【００４９】
【図１】ソーシャルメディアプロバイダを有する従来技術の企業中心型コンピュータネットワークを示す図。
【図２】３つのサービスプロバイダを有するユーザ中心型コンピュータネットワークを示す図。
【図３ａ】薬物の投薬量を計算するためのモバイルアプリケーションのスクリーンショットを示す図。
【図３ｂ】薬物の投薬量を計算するためのモバイルアプリケーションのスクリーンショットを示す図。
【図４】変換されたデータを用いて学習するためのコンピュータシステムを示す図。
【図５】複数のデータサンプルから複数のトレーニングサンプルを決定するための方法を示す図。
【図６】変換されたデータを用いて学習するためのコンピュータネットワークを示す図。
【図７】特徴インデックスに関係する分類器係数を決定するための方法を示す図。
【図８ａ】異なる特徴インデックスが各反復において選択される、図７の方法の様々な反復を示す図。
【図８ｂ】異なる特徴インデックスが各反復において選択される、図７の方法の様々な反復を示す図。
【図９】図７の方法をより詳細に示す図。
【図１０】変換されたデータを用いて学習するための例示的な設定を示す図。
【図１１】変換されたデータを用いて学習するための例示的な設定を示す図。
【図１２】変換されたデータを用いて学習するための例示的な設定を示す図。
【図１３】トレーニングサンプルの特徴的な差分プライバシー準拠解放のためのアルゴリズムを示す図。
【図１４】等価な例示的ラド損失を示す図。
【図１５】
【図１６】
【図１７】
【発明を実施するための形態】
【００５０】
図２は、スマートフォンまたはタブレットコンピュータ２０４などの通信デバイスを操作するユーザ２０２を備える人中心型コンピュータネットワーク２００を示す。ユーザ２０２は、プロバイダ２０６、２０８および２１０から製品またはサービスを受信する。サービスプロバイダ２０６、２０８および２１０は、そのユーザ２０２に関するデータを収集し、通信デバイス２０４に格納されるようにそのデータを再びユーザ２０２に提供する。結果として、通信デバイス２０４は、ユーザ２０２に関する個人データの豊富なコレクションを保持する。言うまでもなく、このデータは、たとえば、ユーザ２０２がプリファレンスを提供すること、写真を撮ること、質問に答えること、またはコメントを提供することなどにより、ユーザ２０２によって生成されるデータを備え得る。
【００５１】
ユーザデバイス２０４と複数のさらなるユーザデバイス（図示せず）が、集約システム２１４に接続される（２１２）。ユーザデバイス２０４と集約システム２１４との間の通信である接続２１２は、集約システム２１４が、集約されたデータを決定または学習し得るが、ユーザデバイス２０４に記憶された使用済みデータは、集約システム２１４と共有されないようなものである。
【００５２】
その結果、個人２０２は、契約しているすべての企業２０６、２０８、および２１０からデータを収集および集約して、すべての契約からの深い洞察を可能にし、結果として個人のニーズ、欲求および行動のより個人的な理解を可能にする。
【００５３】
このアーキテクチャ２００は、多くの意義を有している。最も重要なことには、個人が自身のデータを所有するようになっている。第１に、このことは、プライバシーがローカルな人中心の問題であり、企業または組織がデータをどのようにデータを共有するかという問題ではないことを意味する。これは、プライバシーに関する議論を完全に覆すものである。第２に、個人の行動に関する非常に豊富なデータが、単一のロケーションにおいて利用可能になる。そのような豊富なデータは、組織自体がこの深い情報を共有しないかまたは多くの場合、共有し得ないため、個人によって集約され得る。そのような豊富なデータにより、個人の行動に関するより深い洞察が可能となり、新たな個人化された分析パラダイム、「Ｎ＝１に関する分析」が推進される。
【００５４】
この技術に関する１つの重要な用途は、個人的健康の管理である。個人は自身の個人的健康情報を所有し得、また個人は、考えられる最良の健康予測および管理のソリューションを提供するために、自身のデバイス上にこの情報をローカルに集約し得る。
【００５５】
健康情報は、個人（差異）ゲノム配列、個人の表現型、医師または病院への訪問中に採取された情報、およびデバイス自体から収集された、またはＦｕｅｌＢａｎｄなどの現在普及している活動測定デバイスから採取された個人の（食および活動の）ライフスタイル情報を含み得る。
【００５６】
健康関連の用途には、医師への訪問とその結果としての特定の薬剤の処方、集団全体にわたってコホート研究を実施しようと試みる医学研究者、および、世界最高の医師から供給される、自身の個人的なニーズに合わせた最良のアドバイスを受けたい個人という、３つのユースケースがある。
【００５７】
図３ａおよび３ｂは、ワルファリン投与スマートフォンアプリケーションからの２つのスクリーンショットを示す。図３ａは個人のゲノムおよび表現型情報を示し、図３ｂは、ワルファリン投与量の安全な計算の結果を示す。
【００５８】
このシナリオでは、個人のゲノムおよび表現型は、モバイルフォン上に安全に内密に保持される。医師は、ワルファリン（その最適な投与量が遺伝情報と表現型情報の両方に依存する血液希釈剤）の適切な投与量を決定することを望む。投薬量が計算され、医師に返される。正しい投薬量を計算するために内密の個人データが使用されている間、この情報は個人によって安全に保たれ、医師にも製薬会社にも提供されない。
【００５９】
もう１つの健康に関するシナリオは、がん研究者が個々に保持しているゲノム情報を照会するためのツールを提供することである。集団遺伝学は、がんの理解およびがん治療の発展に対して大きな影響を及ぼす可能性を有しており、全ゲノム配列決定のコストが１，０００ドル以下に下がるとますます重要になる。しかしながら、ゲノムデータベースへのアクセスは、種々の機関が種々のデータにアクセスするため、また倫理的および制度的制約がこのデータが共有されることを妨げるため、非常に困難であることが判明している。このことが、がん研究の大きな障害となっている。
【００６０】
１つのシナリオでは、すべての個人が、パーソナルデバイス上でまたはパーソナルクラウド上で維持される自身の遺伝情報を所有する。個人は次いで、計算が安全に保たれること、および、データが機密に、結果が匿名に保たれることを確信しながら、デバイスに参加することを志願する。
【００６１】
健康関連のアプリケーションでは、どのぐらいの人がＳＮＰのこの組合せを有するか、これらの体重の間にあるか、過去６カ月間にこの薬を服用したか、そして週に３回以上運動するかなどの質問を研究者が行うことが可能である。より豊かでより多くの個人情報を研究者に提供すると同時に、倫理およびデータプライバシーの問題に対する解決策が提供される。
【００６２】
健康において多く存在するプライバシー、セキュリティ、データの豊富さの問題の多くは、銀行業務および個人金融のアプリケーションにおいても同様に重要である。消費と投資、リスクと保険、短期対長期行動に関する決定は、個人と、関係する金融機関の双方にとって重要である。Ｎ＝１のアナリティクスである個々の顧客に適用される分析を用いて豊富な新しい機能を可能にする一方で、データ集約とデータプライバシーの両方の問題に対してソリューションが提供される。
【００６３】
第１の例では、個人がデータを集約し、金融機関は、金融商品およびアドバイスをより良好に目標とし、予測し、個人化することを望む。第２の例では、ビジネスおよびビジネス部門も、各個人のデータベースのセキュリティおよびプライバシーを保証しながら、分析を引き受けるか、または多数の種々のデータベースにわたって情報を共有することを望む。
【００６４】
個人は、自身の個人的な財務情報へのアクセスだけでなく、生活様式、家庭環境、社会的行動、第三者との出資および投資のプロファイルへの直接的なアクセスをも有する。提案されるソリューションは、単一のロケーションに豊富な情報源を作成するために、この個人データの集約を可能にする。さらに、金融機関は、さらに方向性を持った金融アドバイスおよび個人的な製品の方向性を提供するために、この情報を用い得る。これにより、方向性を持った個人向けの個人化された分析を可能にしながら、個人に関する情報のプライバシーおよびセキュリティが保証される。
【００６５】
サードパーティの組織（メディア、マーケティング、販売など）により深い個人の洞察を販売することによって個人が自身のデータを収益化することを可能にする、幅広い潜在的な商用アプリケーションを予想することも可能である。
【００６６】
図４は、変換されたデータを用いて学習するためのコンピュータシステム４００を示す。一例では、コンピュータシステム４００は、複数のデータサンプルから複数のトレーニングサンプルを決定するために使用される。別の例では、コンピュータシステム４００は、分類器係数を決定するために使用される。
【００６７】
コンピュータシステム４００は、モバイルフォンであってもよく、プログラムメモリ４０４、データメモリ４０６、通信ポート４０８、およびユーザポート４１０に接続されたプロセッサ４０２を備える。プログラムメモリ４０４は、ハードドライブ、ソリッドステートディスクまたはＣＤ−ＲＯＭなど、非一時的コンピュータ可読媒体である。ソフトウェア、すなわちプログラムメモリ４０４上に記憶された実行可能なプログラムは、プロセッサ４０２に図５の方法を実行させ、すなわち、プロセッサ４０２は、複数のデータサンプルのサブセットをランダムに選択し、その選択したデータサンプルの特徴値を組み合わせることによって、複数のトレーニングサンプルの各々を決定する。
【００６８】
本開示は、コンピュータシステム４００と同様の要素を有する複数のコンピュータシステムについて説明しているので、コンピュータシステム４００は一度しか説明および図示されない。スマートフォンまたはサーバなどの特定のデバイスが特定のステップを実行すると以下の説明で述べられている場合、このステップはその特定のスマートフォンまたはサーバのプロセッサ４０２によって実行されることを理解されたい。
【００６９】
プロセッサ４０２は、ＲＡＭまたはプロセッサレジスタなどのデータストア４０６に、決定されたトレーニングサンプルまたは分類器係数を記憶し得る。プロセッサ４０２はまた、通信ポート４０８を介して別のモバイルフォンなどの別のコンピュータシステムに、決定されたトレーニングサンプルまたは分類器係数を送り得る。
【００７０】
プロセッサ４０２は、データメモリ４０６からだけでなく、データセットまたはデータセットの特徴付けの視覚的表現４１４をユーザ４１６に示すディスプレイ４１２に接続された通信ポート４０８およびユーザポート４１０からも、データサンプルまたはトレーニングサンプルのデータなどのデータを受信し得る。一例では、プロセッサ４０２は、ＩＥＥＥ８０２．１１に準拠したＷｉ−Ｆｉネットワークを使用することなどによって、通信ポート４０８を介してストレージデバイスからデータを受信する。Ｗｉ−Ｆｉネットワークは、ルータなどの専用の管理インフラストラクチャが必要とされないか、または、ネットワークを管理するルータまたはアクセスポイントを備えた集中型ネットワークが必要とされないような、分散型のアドホックネットワークであり得る。
【００７１】
一例では、プロセッサ４０２は、リアルタイムでデータセットを受信および処理する。これは、プロセッサ４０２が、新たなデータサンプルが受信されるたびにトレーニングサンプルを決定し、次のデータ更新が提供される前にこの計算を完了することを意味する。
【００７２】
通信ポート４０８およびユーザポート４１０は別個のエンティティとして示されているが、ネットワーク接続、メモリインターフェース、プロセッサ４０２のチップパッケージのピンなど、またはＩＰソケットもしくはプログラムメモリ４０４に記憶されプロセッサ４０２によって実行される機能のパラメータなどの論理ポートなど、任意の種類のデータポートがデータを受信するために使用され得ることを理解されたい。これらのパラメータは、データメモリ４０６に記憶されてもよく、また、ソースコード内で、値によって、または参照によって、すなわちポインタとして扱われてもよい。
【００７３】
プロセッサ４０２は、キャッシュもしくはＲＡＭなどの揮発性メモリ、または、光ディスクドライブ、ハードディスクドライブ、ストレージサーバもしくはクラウドストレージなどの不揮発性メモリのメモリアクセスを含む、すべてのこれらのインターフェースを介してデータを受信し得る。コンピュータシステム４００はさらに、動的な台数の仮想マシンをホストする相互接続サーバの管理グループなどのクラウドコンピューティング環境内に実装されてもよい。
【００７４】
任意の受信ステップが、後に受信されるデータを決定または計算するプロセッサ４０２によって先行され得ることを理解されたい。たとえば、プロセッサ４０２は、トレーニングサンプルまたは分類器係数を決定し、それらをＲＡＭまたはプロセッサレジスタなどのデータメモリ４０６に記憶する。プロセッサ４０２は次いで、メモリアドレスとともに読み取り信号を供給することなどによって、データメモリ４０６にデータを要求する。データメモリ４０６は、データを物理的ビットライン上の電圧信号として供給し、プロセッサ４０２は、メモリインターフェースを介してトレーニングサンプルまたは分類子係数を受信する。
【００７５】
図５は、複数のデータサンプルから複数のトレーニングサンプルを決定するための、プロセッサ４０２によって実施される方法５００を示す。複数のデータサンプルの各々は、１つ以上の特徴値と、そのデータサンプルを分類するラベルとを備える。
【００７６】
図６は、複数のコンピュータシステムを備えるコンピュータネットワーク６００を示す。具体的に言えば、図６は、第１のコンピュータシステム６０２、第２のコンピュータシステム６０４、第３のコンピュータシステム６０６および収集サーバ６０８を示す。３つのコンピュータシステム６０２、６０４、６０６および収集サーバ６０８の各々は、図４を参照して説明した要素を備える。
【００７７】
一例では、その目的は、レギュライザを用いたロジスティック回帰分析などの予測モデルを学習することである。これは、目的関数を最小にするパラメータベクトルθ*を発見することを伴う。
【００７８】
【数１】
0006789934.tif 000002
【００７９】
ここで、Ｎはデータプロバイダの数であり、Ｎiはデータプロバイダｉによって保持されている、見本とも呼ばれるデータサンプルの数であり、ｘijはデータプロバイダｉによって保持されているｊ番目の特徴ベクトルであり、ｙijは特徴ベクトルｘijに対応するバイナリラベルであり、λは正則化パラメータである。この目的は、トレーニング見本（ｘij、ｙij）のプライバシーを維持しながら、θ*または近くのパラメータベクトルを発見することである。
【００８０】
最適なパラメータベクトルを発見するための１つの手順は、初期推定値θ1を反復的に改善するデータ処理サーバにデータサンプルを送ることを伴う。しかしながら、データサンプルを送ることは、処理サーバにデータサンプルを公開することになる。したがって、このタイプの手順は、プライバシーを保護するものではない。
【００８１】
図６の例では、収集サーバ６０８は、デバイス６０２、６０４および６０６からデータを収集する。しかしながら、収集サーバ６０８は、データサンプルを開示しないが、デバイス６０２、６０４および６０６から受信されたデータサンプルを学習サーバ６２０に開示することなく、分類器のトレーニングを可能にするトレーニングサンプルを学習サーバ６２０に供給する。
【００８２】
この例では、タスクは、単純なアンケートに基づいてロジスティック回帰分類器を決定することである。アンケートは３つの質問を備える。２つの質問は機能に関するものであるが、第３の質問はラベルに関するものである。第１の質問は、ある人が喫煙者であるかどうかであり、第２の質問は、その人が完全菜食主義者であるかどうかである。第３の質問は、その人ががん患者であるかどうかであり、すなわち、各サンプルのラベルは、その人が「がん患者」であるかどうかである。
【００８３】
タスクは、喫煙者であるか完全菜食主義者であるかに基づいてある人ががん患者であるかどうかを予測し得る分類器を構築することである。しかし、がん患者であることは、ほとんどのユーザが公然と共有することを望まない情報であり、アンケートではプライバシーが保護されることが重要であるが、これは、特定のユーザががん患者であるかどうかの情報が、信頼された収集サーバ６０８以外のいかなる関係者にもデバイスにも開示されないことを意味する。
【００８４】
この例では、３つのコンピュータシステム６０２、６０４および６０６はスマートフォンであり、アンケートの質問はそれぞれの画面に表示される。陰影は、アクティブ化または選択されたユーザコントロール要素を示す。第１のスマートフォン６０２のユーザは、喫煙者であることに対して「はい」、完全菜食主義者であることに対して「いいえ」、がん患者であることに対して「はい」と回答している。回答は、第１のコンピュータシステム６０２のデータメモリ（図４に４０６と称される）に記憶される第１のデータサブセット６１０として記憶される。第１の行は、「喫煙者」である特徴「１」に関連し、第２の行は、「完全菜食主義者」である特徴「２」に関連し、第３の行は、「がん」であるラベル「Ｌ」に関連する。この例では、２番目の列は、それぞれの特徴の特徴値を記憶するものであり、「１」は「はい」の回答を表し、「−１」は「いいえ」の回答を表す。
【００８５】
第１のスマートフォン６０２に提供された結果に基づくと、喫煙することと完全菜食主義者でないことはがん患者であることにつながるように見える。しかし、この結論は単一のサンプルに基づくものであり、したがって統計的に有意ではない。より多くの参加者を組み込むことは、結果をより有意にすることになる。
【００８６】
同様に、第２のスマートフォン６０４のユーザは、彼が喫煙者ではなく、完全菜食主義者ではなく、がん患者でないことを示しており、このことは、第２のコンピュータシステム６０４に第２のデータサブセット６１２として記憶される。第３のスマートフォン６０６のユーザは、彼女が喫煙者であり、完全菜食主義者であり、がん患者であることを示しており、このことは、第３のコンピュータシステム６０６に第３のデータサブセット６１４として記憶される。
【００８７】
他の例では、データサブセット６１０、６１２、および６１４は、顔画像またはゲノムおよび特定の疾病など、他のタイプのデータを記憶してもよい。たとえば、データサブセット６１０、６１２および６１４は、多数の一塩基多型（ＳＮＰ）の各々について１つの特徴を含み得、そのため、サブセットは、その人のＤＮＡがそのＳＮＰを示す場合は「１」、そうでない場合は「−１」を記憶するようになる。ラベルはここでも、糖尿病などの特定の疾病であってよい。
【００８８】
別の例では、データサブセット６１０、６１２、および６１４は、年齢、性別、住所、国籍、民族性などのユーザデータに関連する特徴を備える。このユーザデータは、他の当事者に開示されるべきではなく、または他の当事者と共有されるべきではない。
【００８９】
ラベルは、購入した品目、視聴した動画、読んだ書籍、または、「いいね（ｌｉｋｅ）」もしくは「好き（ｌｏｖｅ  ｉｔ）」のリンクを選択することなどによってユーザが自身の好みとして指示したコメント、ウェブサイトキーワードもしくは写真の個々の単語など、それぞれのユーザの履歴行動データを表し得る。
【００９０】
ネットワーク６００は次いでレコメンダシステムとして機能し、ここで、データセットを特徴付けすることは、ユーザの履歴行動、好みとユーザデータとの間の関係を学習することを意味し得る。その結果、追加の品目、動画、書籍、コメント、ウェブサイトの写真などが、ユーザデータまたは好みに応じてユーザに推薦され得る。
【００９１】
各例では、データサブセット６１０、６１２、および６１４の各々が厳密に１つのデータサンプルを含み、デバイス６０２、６０４および６０６は、データテーブル６１６にデータサンプルを記憶する収集サーバ６０８に、それらのデータサンプルを送る。
【００９２】
データテーブル６１６は３つの列を有し、ここで、最初の２つの列は特徴値を保持するものであり、第３の列は各データサンプルのラベルを保持するものである。テーブルヘッダを除いて、データテーブル６１６は３つのデータサンプルを備える。ここで、この例における方法５００は収集サーバ６０８によって実施されることに留意されたい。しかしながら、他の例では、スマートフォン６０２、６０４および６０６の各々は、複数のデータサンプルを保持してもよく、またそれらのデータサンプルから複数のトレーニングサンプルを決定してもよい。
【００９３】
一例では、収集サーバ６０８は、データサンプル６１６のプライバシーを保証する法的義務を負う収集当事者によって操作される。学習サーバ６２０は、顧客の年齢に応じた特定の製品の人気など、マーケティング関連の結論を導出するために、データセット６１６を取得することを望む第三者によって動作される。収集当事者は、第三者にデータサンプル６１６を提供することが許可されていないが、データセット６１６のプライバシーを維持するトレーニングサンプルを決定し、学習サーバ６２０にそのトレーニングサンプルを提供し得る。
【００９４】
ここで説明は、トレーニングサンプルを決定するための、図５の方法５００に戻る。収集サーバ６０８のプロセッサ４０２は、複数の訓練サンプルを決定するために方法５００の複数回の繰り返しを実施する。各トレーニングサンプルについて、プロセッサ４０２は最初に、複数のデータサンプルのサブセットをランダムに選択する（５０２）。一例では、これは、複数のデータサンプルの各々に、そのデータサンプルを選択するためにゼロに等しくないランダム選択値を、またはそのデータサンプルを選択解除するためにゼロに等しいランダム選択値を乗算することによって達成される。
【００９５】
図６は、ランダム選択変数の第１のベクトル６２２およびランダム選択変数の第２のベクトル６２４を示す。プロセッサ４０２は、乱数生成方法を実施することまたはランド疑似デバイスを読み取ることによってこれらのベクトル６２２および６２４を生成し、また第１のトレーニングサンプル６２６を決定するために第１のベクトル６２２を使用し、第２のトレーニングサンプル６２８を決定するために第２のベクトル６２４を使用する。第１のベクトル６２２の場合、第１および第３のエントリは「１」であり、第２のエントリは「０」であることが分かる。その結果、第１および第３のデータサンプルが選択される。第２のベクトル６２４の場合、第１および第２のデータサンプルが選択される。
【００９６】
プロセッサ４０２は次いで、サブセットのデータサンプルの各々のラベルに基づいて、選択されたデータサンプルの特徴値を結合する。たとえば、プロセッサ４０２は、両方の特徴値をラベルで乗算し、各特徴の値を決定するためにその結果を加算する。図６の例では、第１のトレーニングサンプル６２６の第１の値は、表６１６の第１の列の第１および第３の行の値の合計に「１」を乗算したもの、すなわち１＋１＝２である。同様に、プロセッサ４０２は、第１のトレーニングサンプル６２６の第２の特徴値および第２のトレーニングサンプル６２８の特徴を決定する。
【００９７】
注意深く見ると、第１のベクトル６２２は、正のトレーニング特徴値「２」によって表される、「喫煙者」の特徴と「がん」ラベルとの間の正の相関を表すサンプルを選択することが分かる。対照的に、選択されたサンプルは、「０」の特徴値によって表される「完全菜食主義者」の特徴に関連して決定的ではない。他方では、第２のトレーニングサンプル６２８のために選択されたサンプルは、「−２」の大きな負値によって表される、「完全菜食主義者」の特徴と「がん」のラベルとの間の強い負相関を表し、このことは、選択された完全菜食主義者ががん患者でないかまたは選択された非完全菜食主義者ががん患者であることを意味する。
【００９８】
上記の説明は、データサンプルの情報がどのように保持されるかを示しているが、ランダム選択ベクトル６２２および６２４を知らずにトレーニングサンプルに対する個人の寄与を決定することは困難である。
【００９９】
一例では、トレーニングサンプルはＲＡＤｅｍａｃｈｅｒ  ＯｐｅｒａｔｏｒＳの略称として、ラドスと呼ばれる。
【０１００】
以下の説明は、Ｒａｄｅｍａｃｈｅｒ演算子の集合Ｕを定義するための例を提供するものである。
【０１０１】
本発明者らは［ｎ］＝｛１，２，．．．，ｎ｝とする。例は、Ｘ×｛−１，１｝にわたる未知の、ただし不変の分布Ｄに従う、想定サンプリングされたｉ．ｉ．ｄ．であり、ここで
【０１０２】
【数２】
0006789934.tif 000003
【０１０３】
である。
【０１０４】
【数３】
0006789934.tif 000004
【０１０５】
を学習サンプルとし、
【０１０６】
【数４】
0006789934.tif 000005
【０１０７】
とする。ｙは、
【０１０８】
【数５】
0006789934.tif 000006
【０１０９】
となるようなσ∈Σmを表す。プロセッサ４０２は以下を決定する。
・非中央Ｒａｄｅｍａｃｈｅｒ演算子
【０１１０】
【数６】
0006789934.tif 000007
【０１１１】
・中央ラドス（以下ではラドスと呼ばれる）
【０１１２】
【数７】
0006789934.tif 000008
【０１１３】
すべての量において、学習サンプルＳへの言及は暗黙的である。
【０１１４】
【数８】
0006789934.tif 000009
【０１１５】
では、σはマスキング変数のように働き、σi≠ｙiであるとき、見本ｉの寄与ｙiｘiはラドから除去される。要約すると、
【０１１６】
【数９】
0006789934.tif 000010
【０１１７】
【数１０】
0006789934.tif 000011
【０１１８】
が得られる。
【０１１９】
それらの名前は、σiｓに対するｉ．ｉ．ｄの均一なピッキングを示唆するが、プロセッサ４０２はまた、データ依存の選択肢を提供するために、より洗練された手順を構築し得る。また、Ｕの最大基数は２mであり、可能な限り大きなＵを構成することは、計算上は困難であるが、たとえば｜Ｕ｜＝２mはＳ内におけるｙi・ｘiｓの容易な再構成を意味するので望ましくない。データについて、より多くの知識がない限り、クラスを観測から切り離すことは困難となるが、クラス、Ｒａｄｅｍａｃｈｅｒ変数および観測の特徴値の符号を反転してもＳ*は変化しない。最後に、Ｓ*は、クラスに関する別々の情報を統合していないので、Ｓよりも１つ少ない列を有しており、このことは、トレーニングサンプル６２６および６２８の列（２つの列）をデータテーブル６１６の列（３つの列）と比較することによって図６で分かる。
【０１２０】
上記の式（２）は、データサンプルのサブセットをランダムに選択し、データサンプルの各々のラベルに基づいてデータサンプルを組み合わせることによって、プロセッサ４０２がトレーニングサンプルの各々をどのように決定するかを数学的に示す。具体的に言えば、プロセッサ４０２は、トレーニングサンプルの特徴の特徴値がデータサンプルの特徴の特徴値の合計となるように、データサンプルの特徴値の合計を決定するために式（２）を計算する。さらに、式（２）における和の決定は、データサンプルの各々のラベルに基づいて重み付けされた加重和である。
【０１２１】
図６の例でも分かるように、加重和は乱数に基づいて重み付けされ、複数のデータサンプルのサブセットをランダムに選択することは、特徴値を組み合わせることと同時に実施され、すなわち、両方の操作は同じ式を計算することによって実施される。
【０１２２】
一例では、ランダムな選択は非一様分布に基づく。さらに、一例では、データサンプルは、符号付きの実数を特徴値として有し、ラベルは「−１」または「＋１」である。
【０１２３】
別の例では、プロセッサ４０２は、各ラドの座標をデータサンプルの数で除算する。データサンプルに対するこれらの非負の重みは、学習の結果を著しく向上させる。
【０１２４】
上述したように、収集サーバ６０８は、学習サーバ６２０に決定されたトレーニングサンプル６２６および６２８を送り得る。学習サーバ６２０は、図４を参照して説明したコンポーネントを有する。具体的に言えば、学習サーバは、プロセッサ４０２に図７の方法を実施させるソフトウェアを記憶したプログラムメモリ４０４を有する。サーバ６２０は、トレーニングサンプルおよび決定された分類器係数を記憶するデータメモリ４０６をさらに有する。上述のように、サーバ６２０のプロセッサ４０２は、ＬＡＮもしくはＷｉ−Ｆｉネットワークアダプタおよび／またはＮＡＳもしくはＳＡＮストレージインターフェースであり得る通信ポート４０８を介して、トレーニングサンプルを受信する。
【０１２５】
図７は、特徴インデックスｋに関係する分類器係数θを決定するための方法７００を示す。本開示の全体を通じて、特に明記しない限り、「トレーニング」サンプル／値と「データ」サンプル／値との間になされた重要な区別があることを再び強調しておく。「トレーニング」サンプルは、学習サーバ６２０に開示されるが、「データ」サンプルのプライバシーを保護する。それにもかかわらず、学習サーバ６２０は、「データ」サンプルからの「トレーニング」サンプルの特別な構成のために、「トレーニング」サンプルのみに基づいて「データ」サンプルの分類器を学習することが可能である。
【０１２６】
通信ポート４０８を通じて、プロセッサ４０２は、方法５００に従って決定された特徴インデックスに関係する複数のトレーニング値を受信する（７０２）。上記で説明したように、各トレーニング値は、複数のデータラベルに基づく複数のデータ値のサブセットの組合せに基づくものである。複数のデータラベルの各々は、複数のデータ値のうちの１つに関係付けられる。
【０１２７】
図８ａおよび図８ｂは、２つのトレーニングサンプル６２６および６２８の簡略化された例を継続し、方法７００の種々の繰り返しを示すものであり、ここで、異なる特徴インデックスが各繰り返しで選択される。方法７００は、プロセッサ４０２が１つの特徴に対する分類器係数をどのように決定するかを説明するものである。したがって、方法７００の説明のため、各トレーニングサンプルが複数の特徴を備えるという事実は、明確さのために無視される。結果として、サンプルは簡単に値を参照される。図８ａの例では、第１の特徴が選択され、すなわち、選択された特徴インデックスはι（ｔ）＝１である。トレーニング値は、第１の列の各行値、すなわち「２」および「２」である。
【０１２８】
図９は、より詳細にアルゴリズム９００の形態で方法７００を示す。図９における各ステップの参照符号は、該当する場合、図７における方法７００の各ステップに対応する。
【０１２９】
プロセッサ４０２は、相関値ｒが複数のデータ値の各々とそのデータ値に関係するデータラベルとの間の相関を示すように、複数のトレーニング値に基づいて相関値ｒを決定する（７０４）。ここでもまた、相関値ｒは、データサンプルの特性を示すが、プロセッサ４０２は、トレーニング値に基づいて、そしてデータサンプルに基づかずにその特性を決定する。
【０１３０】
この例では、各トレーニング値は１つのトレーニング値重みｗに関係付けられ、相関値ｒはトレーニング値重みに基づくものである。重みは、トレーニング値の数の逆数で初期化され、以下に説明するアルゴリズム９００の各繰り返しにおいて決定され、すなわち更新され得る。
【０１３１】
プロセッサは次いで、相関値に基づいて分類器係数を決定する（７０６）。図９で分かるように、プロセッサ４０２は、複数のトレーニング値の各々に関係付けられるトレーニング値重みｗによって重み付けされたトレーニング値
【０１３２】
【数１１】
0006789934.tif 000012
【０１３３】
の和を計算することによって相関値を決定する。プロセッサ４０２は次いで、π*ι(t)で示される最大トレーニング値を決定し、その合計を最大トレーニング値π*ι(t)で除算する。
【０１３４】
図７の例では、第１の特徴インデックスを考慮し、各トレーニング値について０．５の初期重みを仮定すると、ｒに対する結果は「１」であり、したがって係数に対する結果は∞である。「喫煙者」に「はい」と答えたすべてのユーザが、がんに「はい」と回答し、逆も同様であるため、この結果は驚くべきことではない。その結果、アルゴリズム９００のステップ７０４に従って相関値を計算することにより、複数のデータ値の各々、すなわち「喫煙者」に対する回答と、そのデータ値に関係付けられるデータラベル「がん」との間の相関を示す相関値が得られる。しかしながら、その相関は、データ値自体に基づくものではなく、方法５００によって決定されたトレーニング値に基づくものである。
【０１３５】
重みｗは、分布の要素として選定され得るものであり、これはｒの値が区間［−１，１］にあることを意味することに留意されたい。
【０１３６】
同様に、第２の特徴値について、プロセッサ４０２は再び方法７００を実施し、ｒに対する結果は、第２の特徴に対する係数に対して−０．５および−０．５４である。このことは、「完全菜食主義者」のデータ値とそのデータ値に関係付けられるラベル「がん」との間に弱い負相関があることを示唆する。
【０１３７】
プロセッサ４０２は、相関値ｒに基づいて、更新ステップ９０２に従ってトレーニング値重みｗを更新する。さらに、プロセッサ４０２は、最大トレーニング値π*ι(t)を決定し、最大トレーニング値π*ι(t)に対する複数のトレーニング値πjι(t)のうちの１つの割合に基づいて、トレーニング値重みｗを決定し得る。言い換えれば、最大トレーニング値π*ι(t)に対する個々のトレーニング値πjι(t)の割合は、どの程度に各特徴がラドｊに統合されたデータサンプルのラベルと相関しているかを示す。説明した更新方法の結果として、弱い相関を有するトレーニング値、すなわち、
【０１３８】
【数１２】
0006789934.tif 000013
【０１３９】
は、増加した重みｗを招き、その一方で、強い相関を有するトレーニング値、すなわち
【０１４０】
【数１３】
0006789934.tif 000014
【０１４１】
は減少した重みｗを招く。このように、不正確に分類された特徴が優先される。
【０１４２】
上述したように、プロセッサ４０２は、複数の特徴インデックスに対して複数の分類子係数を決定するために、この方法を繰り返し得る。各繰り返しにおいて、プロセッサ４０２は、弱い特徴予測インデックスとしてインデックスを決定し得る。一例では、プロセッサ４０２は、以下の方法によってインデックスを決定する。
ステップ１：ｉｎｉｔｉａｌｉｓｅ  ｊｍａｘ＝−１，ｒｍａｘ＝０
ステップ２：ｆｏｒ  ｊ＝１  ｔｏ  ｄ
ステップ２．１：ｉｆ（（ｊ＝１）ｏｒ（｜ｒｊ｜＞ｒｍａｘ））  ｔｈｅｎ  ｊｍａｘ＜−ｊ
出力：ｊｍａｘ
ここで、ｒjは、（ｔ）をｊで置き換えた以下の式（３０）である。したがって、プロセッサ４０２は、重みの現在のセット上のすべての特徴について、（３０）のようにｒtを計算する。プロセッサ４０２は次いで、ｒtがデータストア４０６に記憶されている絶対値において最大となるインデックスを保持する。
【０１４３】
方法７００を２回、繰り返すことで、異なる特徴インデックスまたは同じ特徴インデックスに対する分類器係数および重みを複数回、計算し得ることに留意されたい。
【０１４４】
たとえば、プロセッサ４０２が方法７００を１０回繰り返し、特徴「１」を７回、特徴「２」を３回、選択する場合、式（２２）の和は、特徴「１」に対する７つの要素と、特徴「２」に対する３つの要素を有することになる。たとえば、特徴「２」が、３回、５回、６回の繰り返しで選択された場合、式（２２）の和はθ10,2＝α3＋α5＋α7に展開されることになる。第１の繰り返しで決定された更新済みの重みｗは次いで、特徴の選択にかかわらず第２の繰り返しで使用されることにさらに留意されたい。
【０１４５】
この意味において、プロセッサ４０２は、トレーニング値に基づいて、変更されたブースティングアルゴリズムを実施し、また、この方法を繰り返すことによってプロセッサ４０２は、実際のデータ値を使用せず、トレーニング値のみを使用して複数のデータ値のコスト関数を最適化する。繰り返しが１０００回などの最大反復数など、終了基準に到達すると、結果として得られる分類器係数は、分類器係数に基づいて試験値の分類を決定するための試験値を受信するように適用され得る。
【０１４６】
以下の説明は、上記で定義したＲａｄｅｍａｃｈｅｒ演算子（ラドス）に基づく方法５００および７００のより詳細で数学的な説明を提供するものである。
【０１４７】
ディプティク（損失、トレーニングサンプル）、（Ｆ（．，θ），Ｓ）は、別のもの、（Ｆ*（．，θ），Ｓ*）によって置き換えられ得るが、ここで、Ｓ*は、理想的にはＳを「曝露」しないサンプルの変換であり、Ｆ*は、最小化するＦ（Ｓ，θ）が最適化するＦ*（Ｓ*，θ）と「等価」となることを主な目的としてＳ*に対して定義される凹または凸関数である。たとえば、後者の最適化を実現する分類器は、前者の最適化を実現する分類器に「近い」ものであるべきである。「新しいサンプル」であるＳ*，
【０１４８】
【数１４】
0006789934.tif 000015
【０１４９】
は、ＳおよびセットＵに依存し、セットＵは、この新しいサンプルを構築するために使用されたパラメータの（おそらくは無作為化された）セットである。
【０１５０】
両方の損失の引数における分類子が同じであり得ること、すなわち、いくつかは特徴をさらに「隠す」ように考案され得るが、本発明者らは分類器の変換を仮定していないことに留意されたい。設定に関して本発明者らが設けた主な特性または仮定は以下の通りである。
・θが線形である。少なくともいくつかの結果については、分類器のカーネル化が可能となり得る。
・変換
【０１５１】
【数１５】
0006789934.tif 000016
【０１５２】
は、｜Ｓ｜において線形であり、すなわち、時間および空間の複雑さを低減して実施され得る。さらに、大きなデータセットに対する計算をスケールアップするために、異なるプロセッサもしくはコンピュータまたはコンピューティングクラスタにわたって並列化され得る。
・データが「ワンショット」で伝達される、すなわち、Ｓ*が学習者に伝達され、他には何も伝達されない。したがって、
・ＵがＦ*を最適化するために知られる必要がなく、また通信される必要もない。
【０１５３】
本発明者らのタスクが関連する１つの設定が図１０に提示されている。データベースＤは、Ｕを、次いでＳからＳ*を計算し、次いで学習器ＬにＳ*を伝達する。学習器は、Ｓ*を介して分類器θを学習し、Ｄにその分類子を送り返す。
【０１５４】
たとえば、Ｓ*またはデータ（またはパラメータＵ）を共有し得るか、学習器がデータのサブセットを同様に有し得る場合など、Ｓ*を共有する（そしてそれらのデータは共有しない）いくつかのデータベースが存在するとき、より多数の設定が本発明者らのタスクに関連し得る。図１１は別の例を示す。
【０１５５】
この設定は、Ｄｕｃｈｉら「Ｐｒｉｖａｃｙ  Ａｗａｒｅ  Ｌｅａｒｎｉｎｇ」、Ｊｏｕｒｎａｌ  ｏｆ  ＡＣＭ、２０１４に記載されているプライバシー認識学習に関連する。この場合、図１２に示すように、データベースと学習器との間に、繰り返される通信が存在する。学習器はデータベース（ここでは分類子θ）にパラメータを送り、データベースは、学習器によって最適化された損失関数を知っており、難読化された勾配を再び通信する。これは、雑音で畳み込まれた勾配の形態を取り得る。
損失Ｆ*の定義
表記を多くしないために、表記においてＳとＵのみを維持してＳ*への参照を回避することにする。原理は以下の通りである。損失Ｆ（Ｓ，θ）が与えられると、プロセッサ４０２は、
【０１５６】
【数１６】
0006789934.tif 000017
【０１５７】
となるような機能Ｆ*（．，．，．）を発見し、ｇは狭義に単調である。次いで、プロセッサ４０２は、少なくとも最適なθの観点から、Ｆ*（Ｓ，θ，Ｕ）がＦ*（Ｓ、θ、Σm）の良好な近似となるという目的で、あるＵ⊂ΣmについてＦ*（Ｓ，θ，Ｕ）を最適化する。Ｆ*の最小化に関する１つの重要な点は、これがＳ*のみに依存することである。
【０１５８】
そのため、分類器θは、以下の定量的知識なしに推定される。
・観測ｘi（ｉ＝１，２，．．．，ｍ）
・クラスｙi（ｉ＝１，２，．．．，ｍ）
・パラメータセットＵ
・見本の数ｍ
これは、ｍ・ｄ＋ｍ＋ｍ・｜Ｕ｜＋１＝（｜Ｕ｜＋ｄ＋１）・ｍ＋１個の未知数を表す。
ロジスティック損失の場合
本発明者らはロジスティック損失を以下のように考える。
【０１５９】
【数１７】
0006789934.tif 000018
【０１６０】
以下の補助定理は、Ｆ*が指数損失となり、ｇ（ｚ）＝ｌｏｇ（２）＋（１／ｍ）・ｌｏｇｚとなり得ることを示す。ｃａｒｄ（Ｕ）＝ｎである任意のＵ⊆Σmに対して、
【０１６１】
【数１８】
0006789934.tif 000019
【０１６２】
を平均指数ラド損失とする。その場合は、以下のようになる。
【０１６３】
【数１９】
0006789934.tif 000020
【０１６４】
ロジスティック損失を最小限にすることは、指数関数的なラド損失を、ただしΣm全体にわたって最小限に抑えることと同等である。本発明者らは、Ｕ⊂Σmによってその最小化を近似している。
【０１６５】
提案するアルゴリズムは、ラドスを用いてモデルを学習し得る唯一の手順ではない。ラド損失の式（たとえば、式（８））が与えられると、凸関数を最小化するための任意のアルゴリズムがトレーニングのために実行され得る。結果として、機械学習システムのプロセッサは、機械学習システムをトレーニングするための方法を実施し得、その方法は、式（８）などの凸損失関数を最適化することを備え、凸損失関数は、図５における方法５００に従って決定されるトレーニングサンプルに基づくものである。
２乗損失の場合
本発明者らは２乗損失を以下のように考える。
【０１６６】
【数２０】
0006789934.tif 000021
【０１６７】
以下の補助定理は、Ｆ*が平均分散基準となり、ｇ（ｚ）＝１−（２／ｍ）・ｚとなり得ることを示す。本発明者らは、Ｆsql（Ｓ，θ）＝１−（２／ｍ）・Ｊ（Ｓ，θ，Σm）としており、ここで、任意のＵ⊆Σmに対して、
【０１６８】
【数２１】
0006789934.tif 000022
【０１６９】
であり、分布は一様である。
ラドベースの勾配を通じた最適化
本発明者らは、上記となり得る設定で、手近の損失の勾配の通信を研究している。Ｕlogを、サポートＵを伴った、以下のような離散分布であるとする。
【０１７０】
【数２２】
0006789934.tif 000023
【０１７１】
Ｕsqlを、サポートＵを伴った、以下のような重みのセットであるとする。
【０１７２】
【数２３】
0006789934.tif 000024
【０１７３】
ティルド記号は、重みの和が１であるが、一部は負であり得ることを示す。本発明者らは、ティルド記号を期待値に拡張して、そのような種類の重み分布への参照を示している。θΤπσがＵにわたってゼロの期待値を有する［−１，１］に属していることを確実にした場合、
【０１７４】
【数２４】
0006789934.tif 000025
【０１７５】
は分布となることに注意されたい。また、πσを
【０１７６】
【数２５】
0006789934.tif 000026
【０１７７】
で置き換えた場合も、どちらの分布も変化しないことに注意されたい。本発明者らは以下を得た。
【０１７８】
【数２６】
0006789934.tif 000027
【０１７９】
【数２７】
0006789934.tif 000028
【０１８０】
指数ラド損失によるラドブースト
プロセッサ４０２が、その要素
【０１８１】
【数２８】
0006789934.tif 000029
【０１８２】
が略して
【０１８３】
【数２９】
0006789934.tif 000030
【０１８４】
と新たに名付けられる中央ラドスＳ*のセットをトレーニング値として与えられるとすると、πnの座標ｎ（対応分類子θt）はπnj（対応θtj）と表される。
【０１８５】
【数３０】
0006789934.tif 000031
【０１８６】
は絶対値で最大ラド特徴値を表すものとする。ｗｆｉは、これは、中央ラドスのセットおよびラドスにわたる離散分布（１Tｗt＝１、ｗtj≧０、∀ｊ∈［ｎ］）である重みベクトルｗtを入力として与えられる、弱い特徴指数オラクルを表すものとする。ｗｆｉは、レバレッジ係数が更新される特徴のインデックスを出力する。
［ｔ］Ｒａｄｅｍａｃｈｅｒ演算子ブースト（ＲａｄｏＢｏｏｓｔ）
ｃａｒｄ（Ｓ*）＝ｎ、反復回数を
【０１８７】
【数３１】
0006789934.tif 000032
【０１８８】
として中央ラドスＳ*のセットを入力する。ステップ１：θ0←０、Ｗ0←（１／ｎ）１：／／初期分類器および重み  ステップ２：ｆｏｒ  ｔ＝１，２，．．．，Ｔ  ステップ２．１：［ｄ］∋（ｔ）←ｗｆｉ（Ｓ*，ｗt）；／／弱い特徴予測子インデックス（ｔ）を得る  ステップ２．２：
【０１８９】
【数３２】
0006789934.tif 000033
【０１９０】
【数３３】
0006789934.tif 000034
【０１９１】
ステップ２．３：ｆｏｒ  ｊ＝１，２，．．．，ｎ
【０１９２】
【数３４】
0006789934.tif 000035
【０１９３】
次式で定義されるθTを返す。
【０１９４】
【数３５】
0006789934.tif 000036
【０１９５】
アルゴリズム９００を実施すると、ＲａｄｏＢｏｏｓｔプロセッサ４０２は、ラドセットＳ*および反復回数Ｔから線形分類器を学習し記憶する。ＲａｄｏＢｏｏｓｔ９００は、学習するために見本の数ｍを知る必要はない。本発明者らは、弱い学習仮定（ＷＬＡ：Weak Learning Assumption）の観点からＲａｄｏＢｏｏｓｔを以下のように分析している。
・ｗｆｉによって返される特徴は次式を満たす。
【０１９６】
【数３６】
0006789934.tif 000037
【０１９７】
（ＷＬＡ）が成立するとする。その場合、Ｔ回のブースティングの後、指数関数的なθTのラド損失に対して以下の上限が成立する。
【０１９８】
【数３７】
0006789934.tif 000038
【０１９９】
そして、Ｓ*、すなわちθTの近似ロジスティック損失に対して以下の上限が成立する。
【０２００】
【数３８】
0006789934.tif 000039
【０２０１】
ラドブースティングのために行う弱い学習仮定と、Ｓに対して行われるようなブースティングのための弱い学習仮定とが「等価」であるかどうかに関する質問が問われ得る。本発明者らはここで、本質的にある定数になるまでそれらが実際に等価であり、そのため、ラドブースティングが弱い学習仮定を人為的に「伸ばす」ことはないことを示している。
【０２０２】
本発明者らの結果を述べるために、次の定義が必要である。
【０２０３】
【数３９】
0006789934.tif 000040
【０２０４】
となるようなσj∈Σmを略して表す。重みｗ，（Ｓ*｜ｗ）に対するＳ*の平均加重ラベル類似度は、以下のように定義される。
【０２０５】
【数４０】
0006789934.tif 000041
【０２０６】
ここでＨ（．，．）はハミング距離である。Ｓにわたってブースティングする状況における弱い学習仮定を定義するために、本発明者らは、
【０２０７】
【数４１】
0006789934.tif 000042
【０２０８】
としており、ここでｗは、見本
【０２０９】
【数４２】
0006789934.tif 000043
【０２１０】
にわたる重みベクトルを表し、ｊ∈［ｄ］は特徴インデックスである。式（３８）は、ブースティングで実行される弱い学習仮定において（３４）でｒtに取って代わるものであり、したがって、Ｓにわたる任意の重みベクトルｗに対して、｜μ（Ｓ｜ｗ；ｋ）｜≧γ’となるような特徴ｋが存在するようなγ’＞０が存在することになる。
【０２１１】
（ＷＬＡ）が特徴
【０２１２】
【数４３】
0006789934.tif 000044
【０２１３】
に対して成立するとする。その場合、以下のような重みベクトルｗがＳにわたって存在する。
【０２１４】
【数４４】
0006789934.tif 000045
【０２１５】
特徴はセンタリングされ得、すなわち、
【０２１６】
【数４５】
0006789934.tif 000046
【０２１７】
となる。予測する実数値クラスを有するドメインは、クラスが平均よりも大きいかどうか、すなわちセンタリング後にプロセッサ４０２がその符号でクラスを置き換え得るかどうかを予測することによって、バイナリ分類問題に変換され得る。
【０２１８】
プロセッサ４０２は、固定された｜Ｓ*｜＝ｍｉｎ｛１０００，トレーンサイズ／２｝で総数Ｔ＝１０００回の反復にわたってブースティングアルゴリズム９００を実行して、ラドスの数がトレーニングセットのサイズの半分を超えないことを保証し得る。
差分プライバシーの結果
本発明者らは、すべてのｄ記述変数が符号付きバイナリ値（ｘik∈｛−１，１｝）であるデータセットを考える。｜Ｓ｜＝ｍとし、一般性を失うことなく、以下を仮定する。
【０２１９】
【数４６】
0006789934.tif 000047
【０２２０】
式（４２）は、その特徴が学習の観点から自明ではないことを等価に述べている。さもなければ、｜｛ｉ：ｙiｘik＞０｝｜＝ｍの場合に、そしてその場合に限りｓｉｇｎ（α）＝＋１、｜｛ｉ：ｙiｘik＞０｝｜＝０の場合に、そして場合に限りｓｉｇｎ（α）＝−１とした（式（４２）に違反するｋに対する）形式θ＝αｘkは、ゼロの経験的リスクを有することになる。アルゴリズムＤＰ−Ｆｅａｔは、表記
【０２２１】
【数４７】
0006789934.tif 000048
【０２２２】
を使用する。
【０２２３】
ラドスの差分プライバシー準拠のリリースの鍵は、Σmの厳密なサブセット上におけるσｓの一様な分布、すなわちそれらの一様なｉ．ｉ．ｄ生成のクランピングであると思われる。また、ラドスからの一定の肯定的な学習結果のためには、平均的なオペレータへの期待を保つ分布に従うラドスの生成が（たとえば、ブースティングのために）重要であると思われる。
【０２２４】
これは、次の定義を導く。
【０２２５】
【数４８】
0006789934.tif 000049
【０２２６】
がサポート⊂Σmの分布を表すとする。
【０２２７】
【数４９】
0006789934.tif 000050
【０２２８】
は、
【０２２９】
【数５０】
0006789934.tif 000051
【０２３０】
の場合に、そしてその場合に限り、平均演算子に準拠するものであるとする。
【０２３１】
【数５１】
0006789934.tif 000052
【０２３２】
がラド
【０２３３】
【数５２】
0006789934.tif 000053
【０２３４】
のｋ番目の座標を表すとする。最初に、ラドスの特徴的な差分プライバシーを調べる。この設定では、ユーザは、１つの選択された「重要な」特徴ｋ∈［ｄ］の差分プライバシーをターゲットにする。
【０２３５】
図１３は、式（２）のΣm,βが空でないこと、すなわち、アルゴリズム１３００が式（２）によるラドスの生成に対するアドオンであることをステップ２が保証する別のアルゴリズム１３００を示す。基本的に、αは１より大きい定数で除算される。
【０２３６】
ステップ４ではΣmにサンプリングσｓを用いるため、同様に、Σm,βはΣm,βにわたる一様分布を示すものとする。ステップ４は、Σmにおけるσｓの簡単なＲａｄｅｍａｃｈｅｒ  ｉ．ｉ．ｄ拒否サンプリングによって実装され得る。このスキームを略してＲａｄｅｍａｃｈｅｒ拒否サンプリングと呼ぶことにする。
【０２３７】
任意のδ＞０に対し、以下を定義する。
【０２３８】
【数５３】
0006789934.tif 000054
【０２３９】
ｎ個のＲａｄｅｍａｃｈｅｒ演算子のセットが得られる前に、Ｒａｄｅｍａｃｈｅｒ拒否サンプリングにおけるランダムに生成されたσsの総数をＴRrsとする。ＴRrsが、最低の取り得る値ｎに可能な限り近くなることが望まれる。
【０２４０】
次の３つの特性がアルゴリズムＤＰ−Ｆｅａｔに対して成立する。
１．アルゴリズムＤＰ−Ｆｅａｔは特徴ｋ上のε−差分プライバシーを与える。
２．アルゴリズムＤＰ−Ｆｅａｔは平均演算子に準拠する。
３．δ＞０とする。確率≧１−δ、
【０２４１】
【数５４】
0006789934.tif 000055
【０２４２】
、ここで、
【０２４３】
【数５５】
0006789934.tif 000056
【０２４４】
したがって、Ｒａｄｅｍａｃｈｅｒ拒否サンプリングは単純であり、εが０に近すぎない場合は非常に効率的となり得る。これは、特徴ごとに差分プライバシーを扱うものである。
計算上の複雑さの結果
・スパース近似Ｉ（ＳＡ−Ｉ）
・Ｐ＝｛π1、π2，．．．，πn｝、中央ラドのセット、整数ｍ∈Ｎ*、最大誤差
【０２４５】
【数５６】
0006789934.tif 000057
【０２４６】
、最大ノルムｌ、ｐノルム｜｜．｜｜p、ここでｐ＝∞
・次式のような、ｍ個のスパース見本｛（ｘj，ｙj），ｊ∈［ｍ］｝のセットおよびｎ個のＲａｄｅｍａｃｈｅｒ割当てσ1，σ2，．．．，σn∈｛−１，１｝mのセットが存在するか。
【０２４７】
【数５７】
0006789934.tif 000058
【０２４８】
【数５８】
0006789934.tif 000059
【０２４９】
ＳＡ−ＩはＮＰ−Ｃｏｍｐｌｅｔｅである。
備考：
・ＳＡ−１の硬度は、Ｒａｄｅｍａｃｈｅｒ変数をピッキングする組合せ硬度には依存しないが、サイズが制限されている（見本の数と見本のノルム）見本のセットをフィットさせることに依存する。
・フィーチャサインリークがある場合、すなわち、各特徴を取る得る可能性のある兆候を開示する場合、問題は依然としてＮＰ完全である。
・プライバシーリークチェックＩ（ＰＬＣ−Ｉ）。
・Ｓ見本のセット、Ｐ＝｛π1、π2，．．．，πn｝、中央ラドのセット、整数ｍ∈Ｎ*、最大誤差
【０２５０】
【数５９】
0006789934.tif 000060
【０２５１】
、ｐノルム｜｜．｜｜p、ここでｐ＝∞
・観測されたラドスに近似的につながるＳのｍ個の見本のサブセットが存在するか。より正確に言えば、次式のような、｛（ｘj，ｙj），ｊ∈［ｍ］｝⊆Ｓおよびｎ個のＲａｄｅｍａｃｈｅｒ割当てσ1，σ2，．．．，σn∈｛−１，１｝mのセットが存在するか。
【０２５２】
【数６０】
0006789934.tif 000061
【０２５３】
ＰＬＣ−ＩはＮＰ−Ｃｏｍｐｌｅｔｅである。
備考：
・ＰＬＣ−Ｉの硬度は、Ｒａｄｅｍａｃｈｅｒ変数をピッキングする組合せ硬度には依存しないが、観測されたラドスにつながり得るデータセットの限定されたサブセットを発見することに依存する。
・フィーチャサインリークがある場合、すなわち、各特徴を取る得る可能性のある兆候を開示する場合、問題は依然としてＮＰ完全である。
・この問題は、ドメインに関するすべてのデータを所有する第三者（エージェント、ビジネス）が、そのデータの一部をデータセットエンティティが所有し得るかどうかをチェックすることを望む状況で関心を引くものとなる。
【０２５４】
上記の例ではトレーニングサンプルはＲＡＤｅｍａｃｈｅｒ  ＯｐｅｒａｔｏｒＳの略称としてラドスと呼ばれているが、他の例では、ラドという用語はＲＡＤｅｍａｃｈｅｒ  ＯｂｓｅｒｖａｔｉｏｎＳを表す。式（２）に代わるものとして、Ｒａｄｅｍａｃｈｅｒ  Ｏｂｓｅｒｖａｔｉｏｎはまた、πσ＝（１／２）・Σi（σi＋ｙi）ｘiと定義され得、これによって表記が単純化され得る。
【０２５５】
上記のいくつかの例では、データサンプルは、ＤＮＡサンプル、調査の回答、財務データなど、測定値から受信されたクリーンなオリジナルデータであると仮定され得る。しかしながら、いくつかの例ではプライバシー要件が存在し、その結果、クリーンデータは利用可能ではなく、実際のデータを秘密に保つためにランダムノイズの影響を受けるデータのみが利用可能となる。そのようなノイズの多いデータの一例が、差分プライバシー（ＤＰ）準拠のデータである。
【０２５６】
データに加えられるランダムノイズが球形などのように対称である場合、それらのランダムノイズは「打ち消される」ため、多数のサンプルに対する平均は依然として正確となる。しかしながら、ラドスは、これらのノイズの多いサンプルのサブセット上で生成され、生成されたラドスのいくつかは、少数のノイズの多いサンプルのみに基づくことが可能である。図７、８ａ、８ｂおよび９に関連して説明したＲａｄｏＢｏｏｓｔ方法は、ノイズの量が一定のしきい値を超える場合に、低下した性能を示し得る。これは、この方法がより緩徐に収束し、したがって同等の精度に対してより多くのサンプルが必要とされることを意味する。
【０２５７】
一例では、プロセッサ４０２は、クリーンデータを使用して達成される収束速度をほぼ維持するように、ＤＰ準拠の見本からラドを生成する。より正確に言えば、本発明者らは、エッジベクトルがＤＰ準拠であることを仮定している。ＤＰフレームワークのデータを保護するための判断基準は、データをノイズと畳み込むことである。１つの一般的なメカニズムは、その標準偏差
【０２５８】
【数６１】
0006789934.tif 000062
【０２５９】
がＤＰ要件（ε、δ）に依存する独立したガウス雑音変数
【０２６０】
【数６２】
0006789934.tif 000063
【０２６１】
でデータを畳み込むガウスメカニズムである。
【０２６２】
厳しい構造仮定が成立しない限り、すぐれた特性がノイズで急速に低下し得るという意味で、強力なＤＰレジームは、多くの効率的な学習アルゴリズムに対して扱うことが困難である。たとえば、ノイズの多い電力法のＤＰノイズ下における特異ベクトルの近似係数ρは、Δ＝Ｏ（ｄ）が２つの特異値の間の差である場合、おおよそ、
【０２６３】
【数６３】
0006789934.tif 000064
【０２６４】
として振る舞う。
【０２６５】
【数６４】
0006789934.tif 000065
【０２６６】
が小さいとき、これは非常に良好な境界となる。しかしながら、ＤＰ要件が発生するとき、この境界はあまり適切ではない。
【０２６７】
特徴ベクトルを有するラベルの積は、「エッジベクトル」と呼ばれ、すなわち、各ラドは見本にわたってエッジベクトルのサブセットを合計する（１エッジ＝１観測時間掛けるラベル）。本発明者らは、ＩおよびＩ’を１つのエッジベクトルだけ異なるｍ個のベクトルエッジの２つのセットとして、不等式
【０２６８】
【数６５】
0006789934.tif 000066
【０２６９】
を考え、Ｏは、ガウスメカニズムを通じて生成されるｍ個のエッジベクトルのノイズ付加されたセットである。
【０２７０】
ここで次の重要な結果を示すが、プロセッサ４０２が別の特定のΣrを設計する場合、非ノイズラドス上で測定されたＲａｄｏＢｏｏｓｔの収束速度は、ｍが十分大きい限り、（その振幅に関係なく）ガウスメカニズムを通じたエッジベクトルへのノイズ注入に本質的に耐える。プロセッサ４０２は、多数のエッジベクトルを合計するラドスのみをピッキングするため（これはΣrの設計である）、ｉ．ｉ．ｄ．ノイズ成分は、雑音のない設定とほぼ同じくらい迅速にアルゴリズムが学習することが可能となるよう十分に集中する。
【０２７１】
言うまでもなくＲａｄｏＢｏｏｓｔが認識しない非ノイズのラドスにわたって収束速度が測定されるという重要な事実を、本発明者らは強調している。その結果は、図９における｜ｒt｜（１９）が上限を定められる特徴をピッキングする、プルーデンシャルと呼ばれる特定の弱い学習器を使用するので、ブースティングフレームワークにおいて、独立に関心を引くものである。
【０２７２】
プロセッサ４０２は、入力として与えられたパラメータκ≧１によって、ＲａｄｏＢｏｏｓｔのレバレッジ係数αt（図９の式（２０））を最初に再正規化するので、ここでステップ２．２におけるαt←（１／（κπ*ι(t)））ｌｏｇ（（１＋ｒt）／（１−ｒt））が得られる。現在の収束速度は、（ＷＬＡ）を適用する前に、次のようになる。
【０２７３】
【数６６】
0006789934.tif 000067
【０２７４】
ＷＦＩは、｜ｒt｜≦pとなるような特徴が反復ごとに選択される場合に、そしてその場合に限り、λp＞０に対してλpプルーデンシャルである。ベクトルエッジは、（ｉ∈［ｍ］に対して）
【０２７５】
【数６７】
0006789934.tif 000068
【０２７６】
として
【０２７７】
【数６８】
0006789934.tif 000069
【０２７８】
を計算することによって、ＤＰ保護されている。ある
【０２７９】
【数６９】
0006789934.tif 000070
【０２８０】
に対して、
【０２８１】
【数７０】
0006789934.tif 000071
【０２８２】
とし、ｍσ＝｜｛ｉ：σi＝ｙi｝｜がラドのサポートを表すとする。
【０２８３】
これらの例では、各ラドのサポートは所定のしきい値よりも大きく、これは、複数のトレーニングサンプルの各々が少なくとも所定数のデータサンプルに基づくことを意味する。
【０２８４】
このしきい値は、データサンプルのランダム選択に統合されてもよく、このことは、少なくとも所定のしきい値数のデータサンプルを備える複数のデータサンプルのサブセットをプロセッサ４０２がランダムに選択することを意味する。一例では、このしきい値はデータサンプルの数の半分である。
【０２８５】
以下のＤＰ定理では、「
【０２８６】
【数７１】
0006789934.tif 000072
【０２８７】
」におけるティルダは、式のパラメータ以外の項における依存関係を隠す。
【０２８８】
ＤＰ定理：∀ｔ＞０、で
【０２８９】
【数７２】
0006789934.tif 000073
【０２９０】
である場合、λpプルーデンシャルの弱い学習器の出力θTを使用して、確率≧１−τで
【０２９１】
【数７３】
0006789934.tif 000074
【０２９２】
を満たすλp＞０が存在する。
【０２９３】
この証明は、ステートメントに隠されたパラメータと依存関係を詳述するものである。｜ｒt｜が１に近いときは、αtが膨張するので、プルーデンシャルな弱い学習器の使用は、ノイズの多い状況においてはいくぶんか直感的となる。
【０２９４】
ＤＰ定理は本質的に、ラドスに対する十分に大きなサポートが、ＲａｄｏＢｏｏｓｔの収束速度をノイズフリーレジーム内に高確率で維持するのに十分となることをもたらす。もちろん、弱い学習器はプルーデンシャルであり、これは、有界の｜ｒt｜＜１を意味し、さらに、レバレッジ係数αtは正則化され、これはより小さいマージンを意味する。それでもやはり、ＤＰ定理は、ＤＰ準拠のエッジベクトルから学習するときにラドスを利用するためのすぐれた議論である。
【０２９５】
一般的なロジスティック損失を伴う教師あり学習は、クラス：Ｒａｄｅｍａｃｈｅｒ  ｏｂｓｅｒｖａｔｉｏｎｓ（ｒａｄｏｓ）に関する十分な統計を用いて指数損失を最適化することと等価になり得ることに留意されたい。本開示は、４つのラド損失で例示される、等価となるべき損失に対する条件を提示する。その等価物に含められる損失は、指数（ブースティング）、平均分散（ファイナンス）、リニアヒンジ（オンライン学習）、ＲｅＬＵ（深層学習）、および不安定（統計）損失を含む。
【０２９６】
４つのラド損失に対して成立する十分な条件が提供され、その条件下では、見本に対する損失を正規化することは、等価なラド損失においてラドスを正則化することと等価であり、すなわち、ミンコフスキー和でデータを正規化することは、分類器のマージンにペナルティを課すことに等しい。これは、スパース制御正則化の状況下で当てはまり得るものであり、また、正式なブーストアルゴリズムは、一般的なリッジおよびラッソの選定を含めた正則化のために、正則化された指数ラド損失に対して提案される。差別的にプライベートなメカニズムは、代理正則化の一形態としてラドスの見本を保護するために適用され得、保護されたラドスを用いた学習は、保護された見本を用いた学習よりも著しくすぐれたものとなり得る。
【０２９７】
１つの例は、凸損失の２人プレイゼロサムゲーム表現を使用するものであり、これは、１つの主要な違いを用いたブースティングアルゴリズムを分析するのに有用となり得、ペイオフは非線形凸であり、最終的には区別不能である。これらはまた、エントロピーの双対損失に似ているが、提案する方法はシンプレックスに対して共役を強制しないという違いがある。
【０２９８】
例示的なゲームでは、学習器の敵は、学習する分類器のワーストピクチャをもたらす重みに適合する。学習者の戦略は次いで、このワーストケースの分布を仮定する分類器に適合することであり、これは次いで、データから分類器を学習するために使用され得る損失を生じさせる。ゲームの条件は、合計の重みがラドスに対して１でなければならないため、見本とラドスとでわずかに異なる。
【０２９９】
見本に対する結果的な損失とラドスが等価となるための必要十分条件が与えられる。非公式には、ゲームの凸関数が対称関係を満たし、重みが線形連立方程式を満たす場合に、またその場合に限り等価性が生じる。
【０３００】
含まれる損失は、指数、ロジスティック、２乗、平均分散、ＲｅＬＵ、リニアヒンジ、および不安定損失（およびその他多数）を含む。
【０３０１】
さらに、例示的な損失を正則化することが、ラド損失におけるラドスを正則化すること、すなわち、その要素が分類器に比例するシングルトンでラドセットのミンコフスキー和を作ることと等価となる等価性のための十分条件が提供される。この特性は、レギュラライザとは無関係である。たとえば、見本に対するリッジ回帰は、ラド損失のマージンに、等価的にペナルティを課す。等価性の４つのすべての例がこの十分条件を満たすことが分かる。
【０３０２】
さらに、指数正規化ラド損失を使用して、リッジ（の一般化）および／またはラッソ正則化、ならびにＬ∞正則化を使用して、ラドスからの分類器に適合する効率的なブースティングアルゴリズムが提供される。正規化のこの最後のケースは、通常はスパース性の低減を促進するので、一般的ではない。
【０３０３】
本発明者らの実験は、実際に、一般的なケースで単に節減を増すのではなく、モデルの節減を制御することが望ましいことを示している。理論的な観点から、これらの正則化のいずれについても、アルゴリズムは、通常の弱い学習仮定の下で、指数正規化ラド損失の指数関数的な迅速な収束を伴うブースティングアルゴリズムであることを、本発明者らは示している。したがって、正則化されたフレームワークにおける非常に速い収束のために、付加的な特定の仮定は必要ではない。ブースティングの鍵は、正則化されていない学習ケースと比較して、弱い学習者を修正することに依存していることを、この理論的な分析は明らかにしている。
【０３０４】
さらに、ε差分プライバシーへの直接的な適用が提供され、ここで、この方法は見本を直接的に保護し、すべての後続のステージが同様に差分的にプライベートであることを認める。見本を保護する１つのメカニズムは、たとえば、ラプラス分布からサンプリングされたｉ．ｉ．ｄ．ランダムノイズベクトルを追加することにある。
【０３０５】
ラドスにおけるこの保護メカニズムは、クリーンサンプルの損失の正則化の代理形式を意味し、さらに、ラドスに入れるノイズの量は、見本自体を保護するためにピッキングするものに釣り合い得ることを、本発明者らは理論的に示している。言い換えれば、ラドスのノルムは見本のノルムよりも大きくなり得るので（大きなドメインではさらに）、保護されたラドスから学習するときに、ノイズははるかに与えるダメージの小さいものとなり得、したがって、正確さをほとんど犠牲にすることなく、プライバシーの予算を小さく（たとえば、ε＜１０-4）することが可能となり得る。実験により、これが実際に起こることが示される。
ゲームおよび等価な見本／ラド損失
まず、本発明者らの一般的な２人プレイゲーム設定を定義および分析することから始める。表記の負担を避けるために、学習器がデータ（見本またはラドス）と分類器との両方に依存する一般的なベクトル
【０３０６】
【数７４】
0006789934.tif 000075
【０３０７】
に適合する瞬間を考慮して、学習設定を直ちにプレイにはしないものとする。ｍ＞０に対して、［ｍ］｛１，２，．．．，ｍ｝およびΣm｛−１，１｝mとする。
【０３０８】
【数７５】
0006789934.tif 000076
【０３０９】
および
【０３１０】
【数７６】
0006789934.tif 000077
【０３１１】
を２つの凸および下半連続ジェネレータとする。関数
【０３１２】
【数７７】
0006789934.tif 000078
【０３１３】
および
【０３１４】
【数７８】
0006789934.tif 000079
【０３１５】
を定義する。
【０３１６】
【数７９】
0006789934.tif 000080
【０３１７】
【数８０】
0006789934.tif 000081
【０３１８】
ここで、ｅ，ｒ＞０はｚに依存しない。表記を有意味にするために、ｑにおける座標は、２[m]による全単射にあると仮定される（ｗｌｏｇ）。それぞれのジェネレータにおける両方の問題の依存性は暗黙的であり、文脈から明らかとなるはずである。敵の目標は、以下にフィットすることであり、
【０３１９】
【数８１】
0006789934.tif 000082
【０３２０】
【数８２】
0006789934.tif 000083
【０３２１】
ただし、
【０３２２】
【数８３】
0006789934.tif 000084
【０３２３】
であり、そのため、
【０３２４】
【数８４】
0006789934.tif 000085
【０３２５】
【数８５】
0006789934.tif 000086
【０３２６】
が得られ、
【０３２７】
【数８６】
0006789934.tif 000087
【０３２８】
および
【０３２９】
【数８７】
0006789934.tif 000088
【０３３０】
はそれらの劣微分を表すとする。本発明者らは、学習器のタスクを、式（６７）（見本による）もしくは（６８）（ラドスによる）における対応する問題を最大化するか、または、本発明者らが損失関数と呼ぶ対応する問題を負に等価に最小化する問題と考えている。これらの２つの問題が学習器の立場からいつ等価になるかという問題は、以下の定義を動機付けるものである。
【０３３１】
定義１：２つのジェネレータ
【０３３２】
【数８８】
0006789934.tif 000089
【０３３３】
は、任意のｍ＞０に対して、
【０３３４】
【数８９】
0006789934.tif 000090
【０３３５】
となるようなｅ，ｒが存在する場合に、そしてその場合にのみ比例と呼び、ここで、ｂはｚに依存しない。いかなる
【０３３６】
【数９０】
0006789934.tif 000091
【０３３７】
に対しても、行列
【０３３８】
【数９１】
0006789934.tif 000092
【０３３９】
は、ｍ＞１の場合、
【０３４０】
【数９２】
0006789934.tif 000093
【０３４１】
のように定義し、その他の場合はＧ1［０  １］である（ｚdは
【０３４２】
【数９３】
0006789934.tif 000094
【０３４３】
におけるベクトルを表す）。Ｇmの各列は、ラドにおいて考慮されるエッジベクトルのためのバイナリインジケータベクトルであり、本発明者らは、一般性を失うことなく、これらが２[m]とｑ(*)（ｚ）の座標との間の全単射に対応すると仮定している。
【０３４４】
定理２：
【０３４５】
【数９４】
0006789934.tif 000095
【０３４６】
は、式（６５）および（６６）に対する最適解ｐ*（ｚ）およびｑ*（ｚ）が、次式を満たす場合に、そしてその場合に限り、比例する。
【０３４７】
【数９５】
0006789934.tif 000096
【０３４８】
【数９６】
0006789934.tif 000097
【０３４９】
【数９７】
0006789934.tif 000098
【０３５０】
が微分可能である場合、それらは、ｐ*（ｚ）＝Ｇmｑ*（ｚ）を満たす場合に、そしてその場合に限り、比例する。
【０３５１】
定理２は、２つのジェネレータが比例するための必要十分条件を与える。これは、一方から他方をどのように構築するかを述べるものではない。ここで、探索空間をプルーニングし、
【０３５２】
【数９８】
0006789934.tif 000099
【０３５３】
が、ある
【０３５４】
【数９９】
0006789934.tif 000100
【０３５５】
に比例する場合、これは、以下の定義によれば、
【０３５６】
【数１００】
0006789934.tif 000101
【０３５７】
の「対称化」バージョンでなければならない。
【０３５８】
定義３：
【０３５９】
【数１０１】
0006789934.tif 000102
【０３６０】
を
【０３６１】
【数１０２】
0006789934.tif 000103
【０３６２】
となるものであるとする。
【０３６３】
【数１０３】
0006789934.tif 000104
【０３６４】
を
【０３６５】
【数１０４】
0006789934.tif 000105
【０３６６】
の対称化と呼ぶ。
【０３６７】
補助定理４：
【０３６８】
【数１０５】
0006789934.tif 000106
【０３６９】
および
【０３７０】
【数１０６】
0006789934.tif 000107
【０３７１】
が比例する場合、
【０３７２】
【数１０７】
0006789934.tif 000108
【０３７３】
であり、ここでｂは式（６９）に現れるものである。
【０３７４】
要約すると、
【０３７５】
【数１０８】
0006789934.tif 000109
【０３７６】
と
【０３７７】
【数１０９】
0006789934.tif 000110
【０３７８】
は、（ｉ）
【０３７９】
【数１１０】
0006789934.tif 000111
【０３８０】
が（定理２に従って）
【０３８１】
【数１１１】
0006789934.tif 000112
【０３８２】
の対称化バージョンである（に比例する）という構造的特性を満たす場合、（ｉｉ）問題（６３）および（６４）に対する最適解ｐ*（ｚ）およびｑ*（ｚ）が定理２の条件を満たす場合に、そしてその場合にのみ比例する。方向に応じて、本発明者らは、比例ジェネレータを作成する２つのケースを有する。第１に、
【０３８３】
【数１１２】
0006789934.tif 000113
【０３８４】
を有する場合、必然的に
【０３８５】
【数１１３】
0006789934.tif 000114
【０３８６】
であり、したがって、単純に定理２をチェックするだけでよい。第２に、
【０３８７】
【数１１４】
0006789934.tif 000115
【０３８８】
を有する場合、これは定義２に適合する。代替的に、
【０３８９】
【数１１５】
0006789934.tif 000116
【０３９０】
が許可される。この場合、
【０３９１】
【数１１６】
0006789934.tif 000117
【０３９２】
を発見せねばならず、ここで、ｇ（ｚ）＝−ｇ（１−ｚ）および
【０３９３】
【数１１７】
0006789934.tif 000118
【０３９４】
である。
【０３９５】
ここで、定義２で定義した
【０３９６】
【数１１８】
0006789934.tif 000119
【０３９７】
、
【０３９８】
【数１１９】
0006789934.tif 000120
【０３９９】
に戻り、見本とラド損失とを結びつける。次の定義では、ｅ−ｌｏｓｓ  ｌe（ｚ）はｚの座標に対して定義される関数であり、ｒ−ｌｏｓｓ  ｌr（ｚ）は、座標の和のサブセットに対して定義される関数である。関数は他のパラメータにも同様に依存し得る。
定義５：ｅ−ｌｏｓｓ  ｌe（ｚ）およびｒ−ｌｏｓｓ  ｌr（ｚ）が、（ｉ）  ともに真に増加する
【０４００】
【数１２０】
0006789934.tif 000121
【０４０１】
と
【０４０２】
【数１２１】
0006789934.tif 000122
【０４０３】
が存在するような、そして、
【０４０４】
【数１２２】
0006789934.tif 000123
に対して
【０４０５】
【数１２３】
0006789934.tif 000124
【０４０６】
【数１２４】
0006789934.tif 000125
【０４０７】
となるようなものであると仮定する。
【０４０８】
その場合、対（ｌe，ｌr）は等価な見本−ラド損失の対と呼ばれる。
【０４０９】
以後、
【０４１０】
【数１２５】
0006789934.tif 000126
【０４１１】
の代わりに、単に
【０４１２】
【数１２６】
0006789934.tif 000127
【０４１３】
と書く。
【０４１４】
補助定理６：μe＝μrである限りは、
【０４１５】
【数１２７】
0006789934.tif 000128
【０４１６】
は
【０４１７】
【数１２８】
0006789934.tif 000129
【０４１８】
に比例する。
【０４１９】
系７：次の見本およびラド損失は、いかなる＞０に対しても等価である。
【０４２０】
【数１２９】
0006789934.tif 000130
【０４２１】
【数１３０】
0006789934.tif 000131
【０４２２】
補助定理８：μe＝μr／２m-1である限りは、
【０４２３】
【数１３１】
0006789934.tif 000132
【０４２４】
は
【０４２５】
【数１３２】
0006789934.tif 000133
【０４２６】
に比例する。
【０４２７】
系９：次の見本およびラド損失は、いかなる＞０に対しても等価である。
【０４２８】
【数１３３】
0006789934.tif 000134
【０４２９】
【数１３４】
0006789934.tif 000135
【０４３０】
ここで、
【０４３１】
【数１３５】
0006789934.tif 000136
【０４３２】
および
【０４３３】
【数１３６】
0006789934.tif 000137
【０４３４】
は、Ｉ⊆［ｍ］に対する一様な重みに関するＸの期待値および分散を表す。
【０４３５】
ここで、微分不可能な比例ジェネレータの場合を調べるが、その第１は、自己比例
【０４３６】
【数１３７】
0006789934.tif 000138
【０４３７】
である。ΧA（ｚ）はインジケータ関数を表すものとする。
【０４３８】
【数１３８】
0006789934.tif 000139
【０４３９】
Ａ＝［０，１］は凸であるので、上式も凸である。
【０４４０】
補助定理１０：
【０４４１】
【数１３９】
0006789934.tif 000140
【０４４２】
は自己比例する∀μe，μrである。
【０４４３】
系１１：次の見本およびラド損失は、いかなるμe，μrに対しても等価である。
【０４４４】
【数１４０】
0006789934.tif 000141
【０４４５】
【数１４１】
0006789934.tif 000142
【０４４６】
補助定理１２：
【０４４７】
【数１４２】
0006789934.tif 000143
【０４４８】
は、いかなるμe，μrに対しても、
【０４４９】
【数１４３】
0006789934.tif 000144
【０４５０】
に比例する。
【０４５１】
系１３：次の見本およびラド損失は、いかなるμe，μrに対しても等価である。
【０４５２】
【数１４４】
0006789934.tif 000145
【０４５３】
【数１４５】
0006789934.tif 000146
【０４５４】
図１４は、等価なラド損失の見本を有するテーブル１４００を示す。ラド損失ｌr（ｚ，μr）の名前は、それぞれ、指数（Ｉ）、平均分散（ＩＩ）、ＲｅＬＵ（ＩＩＩ）および不安定（ＩＶ）ラド損失である。本発明者らは略記
【０４５５】
【数１４６】
0006789934.tif 000147
【０４５６】
および
【０４５７】
【数１４７】
0006789934.tif 000148
【０４５８】
を使用している。パラメータａeが式（８５）に現れる。列「μeおよびμr」は等価性が成立するための制約条件を与える。
（ラド）正則化損失を用いた学習
ここで学習設定について述べる。学習器は、見本Ｓ＝｛（ｘi，ｙi），ｉ＝１，２，．．．，ｍ｝のセットを与えられ、ここで、
【０４５９】
【数１４８】
0006789934.tif 000149
【０４６０】
、ｙi∈Σ1（ｉ＝１，２，．．．，ｍに対し）である。これは所定のセットＨから分類器
【０４６１】
【数１４９】
0006789934.tif 000150
【０４６２】
を返す。
【０４６３】
【数１５０】
0006789934.tif 000151
【０４６４】
とし、ｚ（ｈ）を
【０４６５】
【数１５１】
0006789934.tif 000152
【０４６６】
における対応するベクトルとして定義し、これを、対応する見本およびラド損失を得るためにテーブル１４００の損失において利用する。損失は、ある
【０４６７】
【数１５２】
0006789934.tif 000153
【０４６８】
に対して、Ｈが線形分類器、
【０４６９】
【数１５３】
0006789934.tif 000154
【０４７０】
からなるとき、好都合にも簡潔化する。この場合、見本損失は、ｚi＝θT（ｙi・ｘi）であるため、エッジベクトル
【０４７１】
【数１５４】
0006789934.tif 000155
【０４７２】
を用いて記述され得、ラド損失は、ｉ∈Ｉ（および他の場合−ｙi）であり、
【０４７３】
【数１５５】
0006789934.tif 000156
【０４７４】
である場合に、そしてその場合に限り、σi＝ｙiに対してΣi∈I  ｚi＝θTπσであるので、Ｒａｄｅｍａｃｈｅｒ観測［？］を用いて記述され得る。
【０４７５】
【数１５６】
0006789934.tif 000157
【０４７６】
をすべてのＲａｄｅｍａｃｈｅｒ観測のセットと定義することにする。等価性が成立するように前もって修正されると仮定して、パラメータμeおよびμrを省略して、等価な見本およびラド損失の任意のカップルをそれぞれｌe（Ｓe，θ）および
【０４７７】
【数１５７】
0006789934.tif 000158
【０４７８】
として書き直す（テーブル１４００を参照）。表記上の過度な負担を防ぐために、（ポイントワイズ）損失と（サンプルワイズ）リスクの概念を単に「損失」として混合する。
【０４７９】
見本損失を正則化し、それによって、学習器の目標が、
【０４８０】
【数１５８】
0006789934.tif 000159
【０４８１】
を最小化することであり、ここで
【０４８２】
【数１５９】
0006789934.tif 000160
【０４８３】
はＳeに依存しない正則化関数である。
【０４８４】
見本はリッジ（
【０４８５】
【数１６０】
0006789934.tif 000161
【０４８６】
）およびラッソ（Ω∝｜｜．｜｜1）正則化を含む。
【０４８７】
次の定理は、式（７３）におけるｆeが線形であるとき、Ωの任意の選択に対し、この正則化された見本損失に等価なラド損失が存在することを示す。
【０４８８】
定理１４：Ｈが線形分類器を含むとする。
【０４８９】
【数１６１】
0006789934.tif 000162
【０４９０】
を等価な見本ラド損失の任意のカップルであるとすると、式（７３）におけるｆeは、ある
【０４９１】
【数１６２】
0006789934.tif 000163
【０４９２】
に対して、
【０４９３】
【数１６３】
0006789934.tif 000164
【０４９４】
のように線形となる。その場合、任意のレギュラライザΩ（．）に対し、正則化見本損失ｌe（Ｓe，θ，Ω）は、正則化されたラドス
【０４９５】
【数１６４】
0006789934.tif 000165
【０４９６】
にわたって計算されたラド損失
【０４９７】
【数１６５】
0006789934.tif 000166
【０４９８】
と等価となる。ここで、
【０４９９】
【数１６６】
0006789934.tif 000167
【０５００】
は、ミンコフスキー和であり、θ≠０（およびその他の場合は０）の場合、
【０５０１】
【数１６７】
0006789934.tif 000168
【０５０２】
ある。
【０５０３】
定理１４はテーブル１４００におけるすべてのラド損失（Ｉ〜ＩＶ）に当てはまる。ラドスに対する正則化の効果は、マージンの観点からは直感的であり、「すぐれた」分類器θは、あるマージンしきい値τに対して下限付きの内積θTｚ≧τを保証するものである。次いで、正則化されたラドスに対するすぐれた分類器は実際には、正則化されていないラドスに対して、
【０５０４】
【数１６８】
0006789934.tif 000169
【０５０５】
を満たし、したがって、正則化によってマージンしきい値τを「叩く」。１つの重要な問題は、ラドスをサブサンプリングし、ある
【０５０６】
【数１６９】
0006789934.tif 000170
【０５０７】
からθを学習するときに、正則化ラド損失の最小化が正則化見本損失の最小化に影響を及ぼす様式である。
【０５０８】
本発明者らは、ログ損失に対する回答をテーブル１４００の行Ｉに示し、この目的で、｜Ｓr｜＝ｎとし、＞０のユーザを固定して、Ｓrに対して計算されたΩ正則化指数見本ラド損失を定義する。
【０５０９】
【数１７０】
0006789934.tif 000171
【０５１０】
これはθ≠０のときに常に成立する（その他の場合、公式中のωに応じて因子を棄却する）。Ωはノルムであると仮定し、
【０５１１】
【数１７１】
0006789934.tif 000172
【０５１２】
は非正則化損失（式（８８）でω＝０）を表すとし、
【０５１３】
【数１７２】
0006789934.tif 000173
【０５１４】
はΩ正則化ログ損失を表すとする。
【０５１５】
損失を正則化していることに留意されたい。オープンボール
【０５１６】
【数１７３】
0006789934.tif 000174
【０５１７】
および
【０５１８】
【数１７４】
0006789934.tif 000175
【０５１９】
を定義し、ここでΩ*はΩの双対ノルムである。
【０５２０】
定理１５：あるｒθ＞０に対し、Θ⊆Ｂ（０，ｒΘ）を仮定する。次式が成立するとする。
【０５２１】
【数１７５】
0006789934.tif 000176
【０５２２】
すると、ｍが十分に大きく、∀＞０、である場合、ある定数ｕ＞０に対して≧ｕｍである限り、任意のθ∈Θが
【０５２３】
【数１７６】
0006789934.tif 000177
【０５２４】
を満たす、Ｓrのサンプリングにわたって≧１の確率が存在する。
（ラド）正則化損失を用いたブースティング
図１５は、式（８８）における損失
【０５２５】
【数１７７】
0006789934.tif 000178
【０５２６】
を最小化するためにペナルティΩで正則化されたラドスで学習するための、プログラムメモリ４０４に記憶され、プロセッサ４０２によって実行されるプログラムコードに実装されるアルゴリズム１５００を示している。このステートメントでは、パラメータのセットが、Ωに依存する弱い学習器に通信される。
【０５２７】
分類器θは以下のように定義される。
【０５２８】
【数１７８】
0006789934.tif 000179
【０５２９】
ここで、１kはｋ番目の標準基底ベクトルである。フレームボックスはブースト［？］との違いを強調する。式（９０）においてαtを計算するために使用される予想エッジｒtは、次の基本割当てに基づく。
【０５３０】
【数１７９】
0006789934.tif 000180
【０５３１】
図１６は、弱い学習器によるｒtの計算を微調整するための、プログラムメモリ４０４に記憶され、プロセッサ４０２によって実行されるプログラムコードに実装されるアルゴリズム１６００を示している。許可されたものから選定された正則化Ωに関係なく、アルゴリズム１５００および１６００のペアは、同じ基本的特性を維持し、アルゴリズム１５００のステップ２．１においてアルゴリズム１６００がどのようにｌ（ｔ）をピッキングするかに関する標準的な弱い学習仮定の下で、図９のアルゴリズム９００にほぼ匹敵する（指数における定数以下）アルゴリズム１５００の正則化指数ラド損失の収束制限を得ることが可能であり、それによって、アルゴリズム１５００が正則化のすべての選定に対して（高速な）ラドブースティングアルゴリズムであることが示される。
【０５３２】
アルゴリズム１６００におけるステップ１に関して、方向は示されておらず、これは、ブースティング理論における弱い学習器の定義と一致するものであり、弱い学習器に要求することは、弱い学習しきい値＞０以上である
【０５３３】
【数１８０】
0006789934.tif 000181
【０５３４】
がすべてである。
【０５３５】
しかしながら、弱い形式でも述べる、弱い学習器のためのオプションのステップが提供されており、これは、ある特徴が別の特徴よりも好まれる簡単なテストを提供するものであり、たとえば、弱い学習器が、同じｒ≧を有する特徴のセットにおいて、その特徴を選定しなければならない場合、この順序は不確定性を解決するのに役立ち得る。
【０５３６】
定義１６：任意の定数γWL∈（０，１）を固定する。アルゴリズム１６００は、反復ｔにおいてピッキングする特徴ι（ｔ）が任意のｔ＝１，２，．．．，Ｔに対して｜ｒι(t)｜≧γWLを満たす場合に、そしてその場合に限り、γWLの弱い学習器であると言われる。
【０５３７】
この弱い学習の定義は、ブースティングフレームワークで実行されるものと本質的に等価である。
【０５３８】
ここで、ある固定された対称行列
【０５３９】
【数１８１】
0006789934.tif 000182
【０５４０】
に対し、
【０５４１】
【数１８２】
0006789934.tif 000183
【０５４２】
で開始して、アルゴリズム１６００におけるΩのすべてのインスタンシエイションに対するアルゴリズム１５００の収束性の証明を提供する。
【０５４３】
【数１８３】
0006789934.tif 000184
【０５４４】
とする。任意の０＜ａ＜１／５を固定し、Γおよび反復数Ｔは、次のように選定されたものであると仮定する。
【０５４５】
【数１８４】
0006789934.tif 000185
【０５４６】
ここで、λΓ＞０はΓの最大固有値である。
【０５４７】
すると、任意の固定された０＜γWL＜γに対し、アルゴリズム１６００がγWL−Ｗｅａｋ  Ｌｅａｒｎｅｒである場合に、Ｔブースティング反復の最後に、次式
【０５４８】
【数１８５】
0006789934.tif 000186
【０５４９】
を満たす分類器θTを返すようなγ＞０（ａに依存し、アルゴリズム１６００に与えられる）が存在する。
【０５５０】
さらに、ａ＝１／７に固定すると、γ＝０．９８に固定し得、またａ＝１／１０を考慮する場合、γ＝０．９９９に固定し得る。
【０５５１】
２つの所見を順に述べる。第１に、ａ＝１／７，１／１０の場合は、アルゴリズム１６００が依然として式（９６）で大きな強みを持ち得るため、「強固な」弱い学習器であっても、その強みを負わせることなく、アルゴリズム１６００に適合し得る。
【０５５２】
第２に、不等式（９７）の右辺は、
【０５５３】
【数１８６】
0006789934.tif 000187
【０５５４】
がｍ2に比例し得ることを考慮する場合、非常に大きくなり得る。そのため、ωに対する制約は実際には非常に緩いものであり、またωは定理１５の制約条件を容易に満たし得る。
【０５５５】
ここで、Ω（．）∈｛｜｜｜｜1，｜｜．｜｜∞｝に対するアルゴリズム１５００の収束性を証明する。
【０５５６】
定理１８：Ω（．）∈｛｜｜．｜｜1，｜｜．｜｜∞｝とする。任意のγWL＞０を考え、アルゴリズム１６００がγWLーＷｅａｋ  Ｌｅａｒｎｅｒであると仮定する。任意のａ＜３／１１を固定し、次のようにωが選定されたと仮定する。
【０５５７】
【数１８７】
0006789934.tif 000188
【０５５８】
すると、アルゴリズム１５００は、Ｔブースティング反復の最後に、次式を満たす分類器θTを返す。
【０５５９】
【数１８８】
0006789934.tif 000189
【０５６０】
ここで、
【０５６１】
【数１８９】
0006789934.tif 000190
【０５６２】
であり、Ｔ*は反復数であり、ここで、Ｌ∞ノルムを計算する特徴が更新された。いくつかの特徴がこの基準に適合する場合、対応するＴ*のうちの最小のものが選定される。
【０５６３】
ここで、定理１５で示したように、見本に対するθTの正則化された対数損失を検討することができ、また、見本によって出力され、見本に対して計算される正則化対数損失θTは、ｍ→∞のときτ（ｍ）→０として、高確率
【０５６４】
【数１９０】
0006789934.tif 000191
【０５６５】
を満たし、κはＴに依存しないことから、正則化のいかなる適用可能な選定に対しても、高い確率でＴに伴う単調減少が保証されていることを示す。
正則化された損失および差分プライバシー
上記の説明は、一例では、単一の機密特徴の差別的プライベート（DP）保護を調べるものである。ここで、見本の完全な保護について調べる。
【０５６６】
【数１９１】
0006789934.tif 000192
【０５６７】
はラプラス分布の確率密度関数を表すものとする。
【０５６８】
図１７は、その座標がＬａｐ（ｚ｜．）に従う固定ベクトルｚを各ラドに加えることによって、ラドスにおける見本を保護するための簡潔な様式を与える、アルゴリズム１７００を示す。２つのトレーニングサンプルＳeおよびＳ’eを、それらがある見本と異なる場合に、そしてその場合に限り、Ｓe≒Ｓ’eとして記されるネイバーとして定義することにする。本発明者らは、どのようにしてアルゴリズム１７００のラプラスメカニズムが低ノイズでε差分プライバシー（Ｓrのラドスはランダムに一様にサンプリングされる）を与え得るか、さらに、保護されたラドスに対するラド損失の最小化が、クリーンな見本に対する等価な見本の正則化への楽観的制約の最小化に似ていることを示している。
【０５６９】
任意の２つのエッジベクトル、ｅ，ｅ’が｜｜ｅ−ｅ’｜｜1≦ｒeを満たすことを仮定しており、これは、たとえば、すべての見本が直径ｒeのＬ1ボールに属する場合に保証される。
【０５７０】
定理１９：アルゴリズム１７００はε差分プライバシーをもたらす。さらに、双対ノルムの任意のカップル（Ω，Ω’）を選び、
【０５７１】
【数１９２】
0006789934.tif 000193
【０５７２】
を仮定する。すると、∀θ、
【０５７３】
【数１９３】
0006789934.tif 000194
【０５７４】
およびｚσがラドπσに関してステップ２．２でサンプリングされる。
【０５７５】
一例では、アルゴリズム１６００は、その順序における最上位の特徴を回収するために示唆された順序を使用する。したがって、弱い学習器は、｜ｒl｜−δlを最大にする特徴を返す。
【０５７６】
【数１９４】
0006789934.tif 000195
【０５７７】
に対して弱い学習器をクランプしなくてもよい。
【０５７８】
提案するアルゴリズムは、合計Ｔ＝１０００回の反復にわたって実行され得、この反復の最後に、実験的損失を最小化するシーケンスの分類器が保持される。したがって、ラドベースの分類器は、ラドスを計算するトレーニングセット上で評価されることに留意されたい（等価的に、学習器は分類器のシーケンスをデータハンドラに送り、データハンドラは次いでそのトレーニングサンプルに従って最良のものを選択する）。
【０５７９】
一例では、ラドスの数はｎ＝１００に固定される。プロセッサ４０２は、フルトレーニングフォールドからランダムに、トレーニングされたｎ＝１００の見本のサブセットをサンプリングし得る。これによって単にサンプルが小さすぎるがためにアルゴリズムを損なわれないことを確かにするために、プロセッサ４０２は、非常に大きな値のε（したがって、ほとんどノイズは存在しない）ごとにテストエラーをベースラインとして計算する。
【０５８０】
指数正則化ラド損失を最小化するブースティングアルゴリズムが提供され、正則化は、構築されたモデルのスパース性のよりタイトな制御を介して結果をさらに改善するのに有益である。また、クリーン見本に対する等価な見本損失を正則化することに関連する、ラドスにおける見本の差分的にプライベートな保護のためのメカニズムが提供される。ラドスにおけるこの保護は、大きなドメインにおける正確性を危うくしない小さなプライバシー予算をピッキングすることを可能にし、このことは、保護された見本に対して学習するときには生じないものである。
【０５８１】
一例では、上記のレギュラライザ機能はＳＬＯＰＥ正則化に基づいている。ＳＬＯＰＥは、Ｂｏｇｄａｎ、Ｍ、ｖａｎ  ｄｅｎ  Ｂｅｒｇ、Ｅ．、Ｓａｂａｔｔｉ、Ｃ．、Ｓｕ、Ｗ．、およびＣａｎｄｅｓｅｓ、Ｅ．−Ｊ．などの「Ｓｏｒｔｅｄ  Ｌ−Ｏｎｅ  Ｐｅｎａｌｉｚｅｄ  Ｅｓｔｉｍａｔｉｏｎ」の略である。ＳＬＯＰＥとは、参照によって本明細書に組み込まれる、凸最適化による適応的変数選択、Ａｎｎａｌｓ  ｏｆ  Ａｐｐｌｉｅｄ  Ｓｔａｔｉｓｔｉｃｓ，２０１５である。プロセッサ４０２は、θ、｜｜θ｜｜ΦのＳＬＯＰＥノルムを次のように計算する。
【０５８２】
・最初に、θ1≧θ2≧θ3≧・・・≧θdとなるようにθの座標を順序付ける。
【０５８３】
・次いで以下を計算する。
【０５８４】
【数１９５】
0006789934.tif 000196
【０５８５】
ここで
【０５８６】
【数１９６】
0006789934.tif 000197
【０５８７】
である。
【０５８８】
ここでΦ-1は、分位点としても知られる、標準正規分布の逆累積分布関数であり、すなわち、Φ-1（α）＝ｚ⇔ＰｒX〜N(0,1)［Ｘ≦ｚ］＝αである。ｑは推測統計学における標準ｑ値である。
【０５８９】
したがって、θの最大座標は、最小の座標よりも大きなペナルティを課される。ＳＬＯＰＥの正則化は、誤検出率、すなわち、モデルに含まれる無関係な変数の割合を（すべての無関係な変数から）制御するのに役立ち得る。
【０５９０】
ここで、Ω＝｜｜．｜｜Φに対するアルゴリズム１５００の収束性を証明する。
定理２０：（ＳＬＯＰＥを用いたブースティング）Ω（．）＝｜｜．｜｜Φとする。｜θTk｜≧｜θT(k+1)｜、∀ｋとし、ω＝１を固定する。次のようにする。
【０５９１】
【数１９７】
0006789934.tif 000198
【０５９２】
（ｉ）はある＞０に対するＷｅａｋ  Ｌｅａｒｎｅｒであり、（ｉｉ）ｑ値は次式を満たすように選定されるとする。
【０５９３】
【数１９８】
0006789934.tif 000199
【０５９４】
すると、Ｔブースティング反復の最後に返された分類器θTは次式を満たす。
【０５９５】
【数１９９】
0006789934.tif 000200
【０５９６】
当業者であれば、特許請求の範囲で規定された範囲から逸脱することなく、多くの変形および／または修正が特定の実施形態になされ得ることが理解されよう。
【０５９７】
本開示の技術は様々な技術を使用して実装され得ることを理解されたい。たとえば、本明細書に記載された方法は、適切なコンピュータ可読媒体上に存在する一連のコンピュータ実行可能命令によって実施され得る。適切なコンピュータ可読媒体には、揮発性（たとえば、ＲＡＭ）および／または不揮発性（たとえば、ＲＯＭ、ディスク）メモリ、搬送波および伝送媒体が含まれ得る。例示的な搬送波は、ローカルネットワークまたはインターネットなどの公開アクセス可能なネットワークを通じてデジタルデータストリームを搬送する電気、電磁気または光信号の形態を取り得る。
【０５９８】
また、別段の明確な定めがない限り、以下の議論から明らかなように、説明の全体を通じて、「推定する」または「処理する」または「計算する」または「算出する」または「最適化する」または「決定する」または「表示する」または「最大化する」などの用語を利用する議論は、コンピュータシステムのレジスタおよびメモリ内で物理（電子的）量として表現されるデータを、コンピュータシステムのメモリもしくはレジスタ、または他のそのような情報記憶、送信もしくは表示デバイス内で物理量として同様に表現される他のデータへと処理および変換する、コンピュータシステムまたは類似の電子計算デバイスの動作および処理を指していることを理解されたい。
【０５９９】
本実施形態は、したがって、すべての点で例示的であり、限定的ではないとみなされるべきである。  以下に、本願出願の当初の特許請求の範囲に記載された発明を付記する。
［１］
複数のデータサンプルから複数のトレーニングサンプルを決定するためのコンピュータ実装される方法であって、前記複数のデータサンプルの各々は１つまたは複数の特徴値とそのデータサンプルを分類するラベルとを備え、前記方法は、
前記複数のデータサンプルのサブセットをランダムに選択し、前記サブセットの前記データサンプルの各々の前記ラベルに基づいて、前記サブセットの前記データサンプルの前記特徴値を組み合わせることによって、前記複数のトレーニングサンプルの各々を決定することを備える方法。
［２］  前記複数のデータサンプルの前記サブセットをランダムに選択することは、前記複数のデータサンプルの各々に、そのデータサンプルを選択するためにゼロに等しくないランダム選択値を、またはそのデータサンプルを選択解除するためにゼロに等しいランダム選択値を乗算することを備える、［１］に記載の方法。
［３］  前記データサンプルの前記特徴値を組み合わせることは、前記トレーニングサンプルの特徴の前記特徴値が前記データサンプルのその特徴の前記特徴値の和となるように、前記データサンプルの前記特徴値の和を決定することを備える、［１］または［２］に記載の方法。
［４］  前記和を決定することは、前記データサンプルの各々の前記ラベルに基づいて重み付けされる加重和を決定することを備える、［３］に記載の方法。
［５］  前記和を決定することは、前記複数のデータサンプルの前記サブセット中のデータサンプルの数に基づいて重み付けされる加重和を決定することを備える、［３］または［４］に記載の方法。
［６］  前記加重和は、前記複数のデータサンプルの前記サブセットをランダムに選択することが前記特徴値を組み合わせることと同時に実施されるように、乱数に基づいて重み付けされる、［４］または［５］に記載の方法。
［７］  複数のデータサンプルのサブセットをランダムに選択することが、非一様分布に基づいて複数のデータサンプルのサブセットをランダムに選択することを備える、［１］〜［６］のいずれか一項に記載の方法。
［８］  前記データサンプルは符号付きの実数値を特徴値として有し、
前記ラベルは「−１」および「＋１」のいずれかである、［１］〜［７］のいずれか一項に記載の方法。
［９］  前記複数のトレーニングサンプルの各々を決定することは、前記複数のトレーニングサンプルの各々が少なくとも所定数のデータサンプルに基づくように、前記複数のトレーニングサンプルの各々を決定することを備える、［１］〜［８］のいずれか一項に記載の方法。
［１０］  前記複数のデータサンプルのサブセットをランダムに選択することは、少なくとも所定数のデータサンプルを備える前記複数のデータサンプルのサブセットをランダムに選択することを備える、［９］に記載の方法。
［１１］  複数のトレーニングサンプルを決定するためのコンピュータ実装される方法であって、  ［１］に従ってトレーニングサンプルを受信することと、
修正されたトレーニングサンプルを決定するために、前記トレーニングサンプルの各特徴値ごとにランダム値を決定し、その特徴値に前記ランダム値を加えることとを備える方法。
［１２］  コンピュータにインストールされると、［１］〜［１１］のいずれか一項に記載の方法を前記コンピュータに実施させるソフトウェア。
［１３］  複数のデータサンプルから複数のトレーニングサンプルを決定するためのコンピュータシステムであって、
前記複数のデータサンプルを受信する入力ポートと、前記複数のデータサンプルの各々は、１つまたは複数の特徴値およびそのデータサンプルを分類するラベルを備え、
前記複数のデータサンプルのサブセットをランダムに選択し、前記サブセットの前記データサンプルの各々の前記ラベルに基づいて、前記サブセットの前記データサンプルの前記特徴値を組み合わせることによって、前記複数のトレーニングサンプルの各々を決定するプロセッサとを備えるコンピュータシステム。
［１４］  特徴インデックスに関係付けられる分類器係数を決定するためのコンピュータ実装される方法であって、
前記特徴インデックスに関係付けられる複数のトレーニング値を受信することと、各トレーニング値は、複数のデータラベルに基づいた複数のデータ値のサブセットの組合せに基づき、前記複数のデータラベルの各々は前記複数のデータ値のうちの１つと関係付けられ、
相関値が複数のデータ値の各々とそのデータ値に関係付けられる前記データラベルとの間の相関を示すように、前記複数のトレーニング値に基づいて前記相関値を決定することと、
前記相関値に基づいて前記分類器係数を決定することとを備える方法。
［１５］  前記複数のトレーニング値の各々に対して、そのトレーニング値に関係付けられるトレーニング値重みを決定すること、ここにおいて、前記相関値を決定することは、前記複数のトレーニング値の各々に関係付けられる前記トレーニング値重みに基づく、をさらに備える、［１４］に記載の方法。
［１６］  前記相関値を決定することは、前記複数のトレーニング値の各々に関係付けられる前記トレーニング値重みによって重み付けされたトレーニング値の和を決定することを備える、［１５］に記載の方法。
［１７］  前記相関値を決定することは、
最大トレーニング値を決定することと、
前記和を前記最大トレーニング値で除算することとを備える、［１６］に記載の方法。
［１８］  前記トレーニング値の各々に関係付けられる前記トレーニング値重みを決定することは、前記相関値に基づいて、前記複数のトレーニング値の各々に関係付けられる前記トレーニング値重みを決定することを備える、［１５］〜［１７］のいずれか一項に記載の方法。
［１９］  前記複数のトレーニング値のうちの１つに関係付けられる各トレーニング値重みを決定することは、
最大トレーニング値を決定することと、
前記最大トレーニング値に対する前記複数のトレーニング値のうちの前記１つの割合に基づいて、前記トレーニング値重みを決定することとを備える、［１８］に記載の方法。
［２０］  複数の分類器係数を決定するために前記方法の複数の繰り返しを実施すること、ここにおいて、各分類器係数は複数の特徴インデックスのうちの１つに関係付けられる、をさらに備える、［１４］〜［１９］のいずれか一項に記載の方法。
［２１］  前記トレーニング値重みを決定することは、現在の繰り返しの正則化関数の第１の値と、以前の繰り返しの前記正則化関数の第２の値との差に基づいて、前記トレーニング値重みを決定することを備える、［２０］に記載の方法。
［２２］  前記正則化関数は、前記対応する繰り返しに関係付けられる前記複数の分類器係数に依存する、［２１］に記載の方法。
［２３］  前記トレーニング値重みを決定することは、指数を有する指数関数に基づいて、前記差を前記指数に加えることによって、前記トレーニング値重みを決定することを備える、［２１］または［２２］に記載の方法。
［２４］  前記正則化関数は、
リッジ関数、
ラッソ関数、
Ｌ∞正則化、および
ＳＬＯＰＥ正則化のうちの１つまたは複数を備える、［２１］〜［２３］のいずれか一項に記載の方法。
［２５］  複数の特徴インデックスの順序付けに基づいて前記特徴インデックスを選択すること、ここにおいて、前記順序付けは前記差に基づく、をさらに備える、［２１］〜［２４］のいずれか一項に記載の方法。
［２６］  前記方法を繰り返すことは、前記複数のデータ値のコスト関数を最適化するために前記方法を繰り返すことを備える、［２０］〜［２５］のいずれか一項に記載の方法。
［２７］  テスト値を受信することと、
前記分類器係数に基づいて前記テスト値の分類を決定することとをさらに備える、［１４］〜［２６］のいずれか一項に記載の方法。
［２８］  コンピュータにインストールされると、［１４］〜［２７］のいずれか一項に記載の方法を前記コンピュータに実施させるソフトウェア。
［２９］  特徴インデックスに関係付けられる分類器重みを決定するためのコンピュータシステムであって、
前記特徴インデックスに関係付けられる複数のトレーニング値を受信する入力ポートと、各トレーニング値は、複数のデータラベルに基づいた複数のデータ値のサブセットの組合せに基づき、前記複数のデータラベルの各々は前記複数のデータ値のうちの１つと関係付けられ、
前記相関値が前記複数のデータ値の各々とそのデータ値に関係付けられる前記データラベルとの間の相関を示すように、前記複数のトレーニング値に基づいて相関値を決定し、  前記相関値に基づいて前記分類器係数を決定するプロセッサとを備えるシステム。
［３０］  機械学習システムをトレーニングするためのコンピュータ実装される方法であって、凸損失関数を最適化することを備え、前記凸損失関数は、［１］に記載の方法に従って決定されたトレーニングサンプルに基づく、方法。
【図１】
0006789934.tif 000201
【図２】
0006789934.tif 000202
【図３ａ】
0006789934.tif 000203
【図３ｂ】
0006789934.tif 000204
【図４】
0006789934.tif 000205
【図５】
0006789934.tif 000206
【図６】
0006789934.tif 000207
【図７】
0006789934.tif 000208
【図８（Ａ）】
0006789934.tif 000209
【図８（Ｂ）】
0006789934.tif 000210
【図９】
0006789934.tif 000211
【図１０】
0006789934.tif 000212
【図１１】
0006789934.tif 000213
【図１２】
0006789934.tif 000214
【図１３】
0006789934.tif 000215
【図１４】
0006789934.tif 000216
【図１５】
0006789934.tif 000217
【図１６】
0006789934.tif 000218
【図１７】
0006789934.tif 000219