(57)【特許請求の範囲】
【請求項１】
局所的学習のためのトレーニング点のセットから、或るクエリポイントの近くのトレーニング点のサブセットを選択するための方法であって、
トレーニング点のセットΧ、クエリポイントｘｑを与えるステップと、
以下の式に従って、トレーニング点のセットΧから、前記クエリポイントｘｑの近くのトレーニング点のサブセットＸＮを求めるステップとを含み、
【数１】
0005398682.tif 000014
ただし、関数ａｒｇｍａｘは関数Ｇを最大にするＸの値を返し、ｐ＝１，２の場合の
【数２】
0005398682.tif 000015
は前記クエリポイントから前記トレーニング点のサブセットＸｎへの累積類似度であり、ｅ−Ｈ（Ｘ）はＸによって誘導される分布の逆範囲を求め、λは０より大きな制御パラメータであり、Ｈはシャノンエントロピーであり、
前記与えるステップ及び前記求めるステップはプロセッサにおいて実行される、選択するための方法。
【請求項２】
以下の式
【数３】
0005398682.tif 000016
に従って、前記シャノンエントロピーを推定するステップをさらに含み、ただし、μは前記サブセットＸＮ内の前記トレーニング点の平均であり、Σは前記サブセットＸＮ内の前記トレーニング点の共分散であり、Ｃは前記トレーニング点の前記セットの次元数である、請求項１に記載の方法。
【請求項３】
前記トレーニング点の前記サブセットＸＮを用いて分類法をトレーニングするステップをさらに含む、請求項１に記載の方法。
【請求項４】
前記トレーニング点の前記サブセットＸＮを用いて回帰法をトレーニングするステップをさらに含む、請求項１に記載の方法。
【請求項５】
前記回帰法として異分散サポートベクトル回帰を用いるステップをさらに含む、請求項４に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は包括的には局所的な教師あり学習に関し、より詳細には、単一のクエリポイントに基づいて、トレーニングデータセットからトレーニング点のサブセットを選択することに関する。
【背景技術】
【０００２】
教師あり学習では、クエリポイントから成る入力ベクトルに基づいて未知の出力を予測する関数を推定するために、トレーニングデータが用いられる。局所的学習法では、所与のクエリポイントに対して、そのクエリポイントの「近くにある」トレーニング点によって関数が求められる。近さは、或る距離メトリックによって判断することができる。
【０００３】
局所的学習法の例は、最近傍回帰及び分類、並びに局所重み付け回帰を含む。２つの応用例として、過去の値に基づいて、或る時系列の未来の値を予測すること、及びピクセル値に基づいて、或る画像内に或る特定の物体が存在するか否かを検出することが挙げられる。
【０００４】
そのような問題において、トレーニングデータセットＤは複数のペアから成るセットであり、
【０００５】
【数１】
0005398682.tif 000002
【０００６】
である。ただし、Ｘは入力パターンを表し、たとえば、Χ＝Ｒｄである。各ペアは入力ベクトルｘｉ及び出力ｙｉを含む。関数
【０００７】
【数２】
0005398682.tif 000003
【０００８】
は対応する入力ベクトルから出力を推定し、その関数はトレーニングデータセットから学習される。
【０００９】
局所的学習法において、クエリポイントＸｑ毎に、入力クエリポイントＸｑの近くにある、トレーニングセット内のトレーニングデータ点だけに基づいて、局所関数Ｆ(ｘ)が学習される。クエリポイントの近くにあるトレーニング点は通常、距離メトリックに従って、トレーニングデータセット内のｋ個の最も近い点から選択される。代替的には、選択されるトレーニング点は、クエリポイントからの或る距離しきい値ｄ未満である。
【００１０】
局所的学習法の背景にある概念は、データは入力空間の異なる部分において異なる特性を有することができること、及びクエリポイントの近くにあるデータは、所与の入力から所望の出力を予測する関数を学習するのに最も有用なはずであるということである。
【００１１】
１つの応用例において、毎日の電力需要を予測することが望まれる。１年のうちの異なる時点では、異なる要因が需要負荷に影響を及ぼす可能性がある。クエリポイントが夏日に対応する場合には、トレーニングデータセット内の夏日だけに基づいて、関数Ｆ()を学習することが好都合である可能性がある。
【００１２】
しかしながら、ｋ個の最近傍点、又は或る距離ｄ内にある全ての近傍点を用いることが、必ずしも最良の性能を与えるとは限らない。
【発明の概要】
【発明が解決しようとする課題】
【００１３】
いずれのトレーニング点が近傍に属するかを求めるための方法と共に、局所近傍の新たな概念を提供することが望まれる。
【課題を解決するための手段】
【００１４】
方法は、累積類似度を最大にすることによって、トレーニング点のセットから、１つのクエリポイントに近いトレーニング点のサブセットを選択し、その累積類似度は、クエリポイントとサブセット内の各点との類似度、及びサブセット内の点の互いの類似度を評価する。
【図面の簡単な説明】
【００１５】
【図１Ａ】トレーニングデータ、及びこの発明の実施の形態による方法によって選択されるトレーニングデータのサブセットのプロット図である。
【図１Ｂ】トレーニングデータ、及び従来技術の方法によって選択されるトレーニングデータのサブセットのプロット図である。
【図２Ａ】トレーニングデータ、及びこの発明の実施の形態による方法によって選択されるトレーニングデータのサブセットのプロット図である。
【図２Ｂ】トレーニングデータ、及び従来技術の方法によって選択されるトレーニングデータのサブセットのプロット図である。
【図３】この発明の実施の形態による、トレーニングデータを選択するための方法のフローチャートである。
【発明を実施するための形態】
【００１６】
図３に示されるように、この発明の実施の形態は、単一の入力クエリポイントｘｑ３０５の近くにある、複数の点から成る局所近傍ＸＮ３０２を選択するための方法を提供する。近傍点の全てがコンパクトであることが望ましい。この明細書において定義されるように、複数の点が或る距離メトリックに従って互いに相対的に近い場合には、そのセットはコンパクトである。この方法のステップは、当該技術分野において既知のように、メモリ及び入力／出力インターフェースを備えるプロセッサにおいて実行することができる。
【００１７】
従来の最近傍法は、結果として得られる近傍がコンパクトであるか否かを考慮することなく、クエリポイントの近くにある近傍点を選択する。
【００１８】
この発明の実施の形態による方法は、入力トレーニングデータ(３０１参照)が入力空間内で不均一に分布するときに性能を改善するために、コンパクトであることの判定基準を含む。
【００１９】
この発明による局所近傍点のサブセットＸＮ３０２は(３１０参照)以下の通りである。
【００２０】
【数３】
0005398682.tif 000004
【００２１】
ただし、関数ａｒｇｍａｘ３１０は関数Ｇを最大にするパラメータＸの値を返し、ｐ＝１，２の場合に、
【００２２】
【数４】
0005398682.tif 000005
【００２３】
はクエリポイント３０５からトレーニングサブセット
【００２４】
【数５】
0005398682.tif 000006
【００２５】
への累積類似度であり、ｅ−Ｈ(Ｘ)はＸによって誘導される分布の逆範囲(inverse range)を求め、λは制御パラメータである。分布の「範囲」によって、この発明では、サンプル空間が離散的である場合には、サンプル空間内の点の数を意味し、サンプル空間が指数関数的なエントロピーの特性に従う実線である場合には、確率密度関数が０でない区間の長さを意味する。Ｈはシャノンエントロピーである。シャノンエントロピーは、確率変数の値が未知であるときに失う平均情報量の指標である。
【００２６】
この発明では、以下のようにガウス分布を仮定してシャノンエントロピーを推定する。
【００２７】
【数６】
0005398682.tif 000007
【００２８】
ただし、μはサブセット内の点の平均であり、Σはその共分散である。Ｃは入力トレーニング点３０１の次元数である。
【００２９】
式(１)の目的は、或るクエリポイントの近くの最も大きなクラスタへの累積類似度を最大にすることである。この発明の目的は、トレーニングデータパターンの基本的な構造に適応できるような方法で、トレーニングデータのサブセット３０２を見つけることである。
【００３０】
この問題の組み合わせ最適化特性は、従来の最近傍法において用いられる貪欲法との重要な相違点である。この発明において最大にする、式(１)において定義される目的関数は、優モジュラ性として知られている数学的特性を有する。全てのｘ，ｙ∈Ｒｋに対して、
【００３１】
【数７】
0005398682.tif 000008
【００３２】
である場合には、関数
【００３３】
ｆ：Ｒｋ→Ｒ
【００３４】
は優モジュラ性である。ただし、
【００３５】
【数８】
0005398682.tif 000009
【００３６】
はｘ及びｙの成分毎の最大値を表し、
【００３７】
【数９】
0005398682.tif 000010
【００３８】
は成分毎の最小値を表す。
【００３９】
優モジュラ関数を最大にすることは、劣モジュラ関数を最小にすることと同じである。それゆえ、この発明では、この関数を最適化するために、劣モジュラ性最適化の従来の手段を適用することができる。
【００４０】
上記の手順を用いて、複数の点から成る最適なサブセットが求められた後に、任意の分類又は回帰法をトレーニングするために(３２０)、その点のサブセットを用いることができる。
【００４１】
図１Ａ，１Ｂ，２Ａ，２Ｂを用いて、２つの単純な例を説明し、ｋ＝１５の場合の、この発明の劣モジュラモデル選択法と、従来のｋ最近傍点選択法とを比較する。それらの図は、単一のクエリポイント１０１と、サブセット１０２とを示す。これらの図において、時間間隔［−８，８］内に１００個の合成入力データ点ｘｉが均一な間隔で配置されており、対象となる出力データ点ｙｉ＝２ｓｉｎ(２πｘ)が、ｘ＝０における０．５からｘ＝１における１．５まで線形に増加する標準偏差を有するガウス雑音で汚染される。
【００４２】
これらの図は、この発明の方法が従来の方法よりも優れていることを明示する。劣モジュラ法では、近傍点が適応的に選択され、ここで図１Ａ及び図１Ｂにおいて示されるように分布の先端では点の数が少なく、図２Ａ及び図２Ｂにおいて示されるように、末端に近いほど数が多くなり、それは、この発明の例においてガウス雑音の汚染が増加することに一致する。
【００４３】
異分散サポートベクトル回帰
上記のように選択される近傍トレーニングデータを用いて、任意の回帰又は分類法をトレーニングすることができる。ここで、異分散サポートベクトル回帰のための１つのそのような技法を説明する。異分散サポートベクトル回帰は、サポートベクトル回帰を拡張したものであり、局所近傍を用いて局所回帰関数を見つける。統計学において、一連の確率変数が異なる分散を有するときに、それらの確率変数は異分散である。
【００４４】
異分散サポートベクトル回帰は、形式
【００４５】
Ｆ(ｘ)＝ｗＴｘ＋ｂ
【００４６】
の関数Ｆ(ｘ)を推定する。ただし、ｗＴは転置演算子Ｔを伴うベクトルであり、ｂはスカラーである。
【００４７】
その関数は、以下の最適化問題を解くことによって求められる。
【００４８】
【数１０】
0005398682.tif 000011
【００４９】
ただし、ＩはＮ×Ｎ恒等行列であり、Ｎは入力ベクトルの次元数であり、ξｉ及びξ＊ｉはスラック変数であり、εは誤差許容範囲であり、ｐ∈{１，２}はペナルティタイプを決定し、そして
【００５０】
【数１１】
0005398682.tif 000012
【００５１】
はｘｉの近傍内のトレーニング点のための実験的な共分散である。ただし、Ｘｉは近傍点のサブセットであり、ｋｉはＸｉ内の点の数であり、
【００５２】
【数１２】
0005398682.tif 000013
【００５３】
はこれらの近傍点の平均である。複数の点から成るこの近傍は、上記の劣モジュラ性最適化技法を用いて選択することができる。
【００５４】
この発明を、好ましい実施の形態の例として説明してきたが、この発明の精神及び範囲内で他のさまざまな適合及び変更を行えることが理解されるべきである。したがって、この発明の真の精神及び範囲内に入るすべての変形及び変更を包含することが、添付の特許請求の範囲の目的である。
【図１Ａ】
0005398682.tif 000017
【図１Ｂ】
0005398682.tif 000018
【図２Ａ】
0005398682.tif 000019
【図２Ｂ】
0005398682.tif 000020
【図３】
0005398682.tif 000021