(57)【要約】【課題】  膨大な数の正則化パラメータλについて正則化最小二乗（RLS）の問題でのLOO（leave-one-out）誤差を膨大な数の正則化パラメータλについて求めるためのアルゴリズムを実施する手法を開示する。【解決手段】  前記手法で実施されるアルゴリズムは、１つの正則化最小二乗分類器／回帰アルゴリズムをトレーニングするときと略同じ時間と空間を用いる。前記手法は、非正則化カーネル行列の固有値分解に基づいて、中規模のデータセットに好適な分類／回帰処理を含む。この処理は、多数の基準データセット（benchmark datasets）に適用して、実験的に、帯域幅パラメータσよりも若干大きい値を有するガウスカーネルを用いることで正確な分類／回帰が可能となる。さらに、このような大きいσを用いる手法を用いて、LOO値の演算をλの範囲全体で行うような、大規模なデータセットに適した線形時間アルゴリズムを求める方法も示す。  【選択図】  図２
2009510633.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータに実装されるRLS分類／回帰に関する方法であって、
前記方法は、
データのトレーニングセットを受信し、
前記トレーニングセットを用いて行列分解を演算し、
複数の正則化パラメータを受信し、
前記行列分解を用いて前記正則化パラメータの各々について係数を演算し、
前記正則化パラメータの各々についてLOO誤差を演算し、
前記LOO誤差の最小値を有する前記正則化パラメータを選択する
ことを含むことを特徴とするRLS分類／回帰に関する方法。
【請求項２】
前記選択した正則化パラメータに対応する係数cまたは超平面関数wの少なくとも１つに基づいて将来のデータ点を予測することをさらに含むことを特徴とする請求項１に記載のRLS分類／回帰に関する方法。
【請求項３】
前記トレーニングセットを用いた行列分解の演算には、前記トレーニングセットを用いてSVDを演算することが含まれ、
この場合の前記SVDは前記行列分解である
ことを特徴とする請求項１に記載のRLS分類／回帰に関する方法。
【請求項４】
前記トレーニングセットを用いた行列分解の演算には、
入力したトレーニングセットを用いてカーネル行列を生成し、
前記カーネル行列の固有値分解を演算することが含まれ、
この場合の固有値分解は前記行列分解である
ことを特徴とする請求項１に記載のRLS分類／回帰に関する方法。
【請求項５】
前記カーネル行列を陽関数表示で表現し、
前記カーネル行列を記憶することをさらに含む
ことを特徴とする請求項４に記載のRLS分類／回帰に関する方法。
【請求項６】
前記カーネル行列を陽関数表示で表現し、
O(n3+n2d)時間とO(n2)空間でのすべての正則化パラメータについて前記LOO誤差を演算することをさらに含み、
この場合のnは前記トレーニングセットのd次元におけるデータ点の数である
ことを特徴とする請求項４に記載のRLS分類／回帰に関する方法。
【請求項７】
2009510633.tif 000035
【請求項８】
１つ以上のプロセッサにより実行されるときに、
前記プロセッサにRLS分類／回帰の処理を実行させるような指令が符号化されたマシン読み取り可能な媒体であって、
前記処理は、
データのトレーニングセットを受信し、
前記トレーニングセットを用いて行列分解を演算し、
複数の正則化パラメータを受信し、
前記行列分解を用いて前記正則化パラメータの各々について係数を演算し、
前記正則化パラメータの各々についてLOO誤差を演算し、
前記LOO誤差の最小値を有する前記正則化パラメータを選択する
ことを含むことを特徴とするマシン読み取り可能な媒体。
【請求項９】
前記選択した正則化パラメータに対応する係数cまたは超平面関数wの少なくとも１つに基づいて将来のデータ点を予測することをさらに含む
ことを特徴とする請求項８に記載のマシン読み取り可能な媒体。
【請求項１０】
前記トレーニングセットを用いた行列分解の演算には、前記トレーニングセットを用いてSVDを演算することが含まれ、
この場合の前記SVDは前記行列分解である
ことを特徴とする請求項８に記載のマシン読み取り可能な媒体。
【請求項１１】
前記トレーニングセットを用いた行列分解の演算には、
入力したトレーニングセットを用いてカーネル行列を生成し、
前記カーネル行列の固有値分解を演算することが含まれ、
この場合の固有値分解は前記行列分解である
ことを特徴とする請求項８に記載のマシン読み取り可能な媒体。
【請求項１２】
前記カーネル行列を陽関数表示で表現し、
前記処理は前記カーネル行列を記憶することをさらに含む
ことを特徴とする請求項１１に記載のマシン読み取り可能な媒体。
【請求項１３】
前記カーネル行列を陽関数表示で表現し、
前記処理はO(n3+n2d)時間とO(n2)空間でのすべての正則化パラメータについて前記LOO誤差を演算することをさらに含み、
この場合のnは前記トレーニングセットのd次元におけるデータ点の数である
ことを特徴とする請求項１１に記載のマシン読み取り可能な媒体。
【請求項１４】
2009510633.tif 000036
【請求項１５】
データのトレーニングセットを受信する入力モジュールと、
前記トレーニングセットを用いた行列分解を演算する行列分解モジュールと、
複数の正則化パラメータを受信し、前記行列分解を用いて前記正則化パラメータの各々について係数を演算する係数演算モジュールと、
前記複数の正則化パラメータを受信し、前記正則化パラメータの各々についてLOO誤差を演算するLOO誤差演算モジュールと、
前記LOO誤差の最小値を有する前記正則化パラメータを選択する正則化パラメータ選択モジュールと
を備えることを特徴とするRLS分類／回帰システム。
【請求項１６】
前記選択した正則化パラメータに対応する係数cまたは超平面関数wの少なくとも１つに基づいて将来のデータ点を予測する予測モジュールをさらに備えることを特徴とする請求項１５に記載のRLS分類／回帰システム。
【請求項１７】
前記行列分解モジュールは、前記トレーニングセットを用いてSVDを演算し
この場合の前記SVDは前記行列分解であること
を特徴とする請求項１５に記載のRLS分類／回帰システム。
【請求項１８】
入力したトレーニングセットを用いてカーネル行列を生成するカーネル行列生成器をさらに備え、
この場合の前記トレーニングセットを用いて行列分解を演算する前記行列分解モジュールは、前記カーネル行列の固有値分解を演算し、この固有値分解は行列分解である
ことを特徴とする請求項１５に記載のRLS分類／回帰システム。
【請求項１９】
前記カーネル行列は陽関数表示で表現され、
前記カーネル行列を記憶するメモリをさらに備える
ことを特徴とする請求項１８に記載のRLS分類／回帰システム。
【請求項２０】
前記カーネル行列を陽関数表示で表現し、
O(n3+n2d)時間とO(n2)空間でのすべての正則化パラメータについて前記LOO誤差を演算し、
この場合のnは前記トレーニングセットのd次元におけるデータ点の数であることを特徴とする請求項１８に記載のRLS分類／回帰システム。
【請求項２１】
2009510633.tif 000037
【発明の詳細な説明】
【技術分野】
【０００１】
本願は、米国特許仮出願第６０／７２１７５３号（出願日：２００５年９月２８日）発明の名称：「Making Regularized Least Squares Practical」および米国特許出願第１１／５３５９２１号  発明の名称：「Regularized Least Squares Classification/Regression」の優先権を主張するものであり、これら出願のすべての記載をここに引用するものである。
【０００２】
本発明は、マシン学習（Machine Learning）に関し、具体的には、正則化最小二乗法の分類／回帰に関する。
【背景技術】
【０００３】
2009510633.tif 000003
【０００４】
【数１】
2009510633.tif 000004
【０００５】
2009510633.tif 000005
【０００６】
二乗損失を含む幅広い損失関数では、いわゆるRepresenter定理は、Tikhonovの最小化問題の解では下の式２を用いることが証明されている（Scholkopfら、２００１年；Wahba、１９９０年）。
【０００７】
【数２】
2009510633.tif 000006
【０００８】
2009510633.tif 000007
【０００９】
RLSアルゴリズムには、いくつかのすばらしい特性がある。概念がシンプルであり、数行のMATLABコードを用いて効率的な実施が可能である。回帰も分類もまったく同じフレームワークに置くことができる（つまり、同じコードで回帰と分類の問題を解くことができる）。直感的には、二乗損失関数は、回帰の問題には好適である一方で、ヒンジ損失と比較すると、分類の問題には適した選択とは言い難い。
2009510633.tif 000008
【発明の開示】
【発明が解決しようとする課題】
【００１０】
その一方で、大規模なデータベースや非線形カーネルでは、RLSは、より一般的なSVMと比較すると、重大な問題を抱える。詳細には、RLSを解く直接的な手法では、カーネル行列全体を扱うため、O(n3) 時間と、（さらに悪いことに）O(n2) 空間が必要になる。このような問題は、行列・ベクトル積のみが必要となる共役勾配などの反復法を用いることで緩和できる。しかし、dが大きい場合、反復ごとにカーネル行列を再計算するには、O(n2d) 仕事が必要となるため、dが大きい場合には禁止される恐れがある。一方、SVMは演算上極めて魅力的であるのは、正しく分類された点の平坦な損失関数は、正しく分類された点がすべてゼロの係数ciを有する疎の解を導出するためである。トレーニング動作中常に正しく分類される１対のトレーニング点同士のカーネル積を最新のSVMアルゴリズムで演算することはない。とりわけ、SVMアルゴリズムはカーネル行列の小さい分数のみを生成するため、SVMの方がRLSよりもはるかに非線形問題に適することになる。
【００１１】
2009510633.tif 000009
SVMのほうが幾分速いが大差はない。というのは、最新のSVMアルゴリズムは座標上昇アルゴリズム（Coordinate Ascent Algorithms）であって、このアルゴリズムは、実施可能領域の境界部に働き、残りの係数を固定したままでいくつかの係数を最適化するため、カーネル行列Kの明示的エントリ（Explicit Entries）が必要となるからだ。行列・ベクトル積で表現可能であり、これにより線形カーネルがもたらす強みのすべてを利用できる内点SVMにおいていくつかの試みを行った。しかしながら、このようなアプローチは、最新の線形SVMと同じ性能を達成するまでには至っておらず、正則化の線形分類器をトレーニングする方法としては、依然としてRLS分類が最速の方法である。
【００１２】
したがって、正則化最小二乗をより実践的に用いるような技術が求められている。
【課題を解決するための手段】
【００１３】
本発明の一実施形態では、コンピュータに実装する正則化最小二乗（RLS）分類／回帰に関する方法を提供する。本方法は、データのトレーニングセットを受信し、このトレーニングセットを用いて行列分解（例えば、固有値分解やSVD）を演算することを含む。本方法は、複数の正則化パラメータを受信し、前記行列分解を用いて正則化パラメータの各々について係数を演算することをさらに含む。本方法は、前記に続いて、前記正則化パラメータの各々についてLOO（leave-one-out）誤差も演算することを含む。本方法は、前記選択した正則化パラメータに対応する係数cまたは超平面関数wの少なくとも１つに基づいて未来のデータ点を予測することをさらに含む。特定の場合には、トレーニングセットを用いた行列分解の演算には、トレーニングセットを用いて特異値分解（以下、「SVD」ともいう）を演算することが含まれ、この場合のSVDは行列分解である。別の特定の場合には、トレーニングセットを用いた行列分解の演算には、入力したトレーニングセットを用いてカーネル行列を生成し、このカーネル行列の固有値分解を演算することが含まれ、この場合の固有値分解は行列分解である。このような場合の一例では、前記カーネル行列を明示的に表現し、本方法は前記カーネル行列を記憶することを含む。このような場合の別の例では、前記カーネル行列を明示的に表現し、本方法は、O(n3+n2d)時間とO(n2)空間でのすべての正則化パラメータについて前記LOO誤差を演算することをさらに含み、この場合のnは前記トレーニングセットのd次元におけるデータ点の数である。
2009510633.tif 000010
【００１４】
本発明の別の実施形態では、１つ以上のプロセッサによって実行されるときに、このプロセッサに正則化最小二乗（RLS）分類／回帰の処理を実行させるような指令が符号化された（例えば、１つ以上のコンパクトディスク、フレキシブルディスク、サーバ、メモリスティック、ハードドライブなどの）マシン読み取り可能な媒体を提供する。この処理は、例えば、前記の方法の類似例や変形例であってもよい。
【００１５】
本発明の別の実施形態では、正則化最小二乗（RLS）分類／回帰システムを提供する。システムの機能性（例えば、前記の方法やその変形例など）は、多数の手段、例えば、ソフトウェア（１つ以上のコンピュータ読み取り可能記憶媒体に符号化された実行可能な指令など）、ハードウェア（ゲートレベル論理や１つ以上のASICなど）、ファームウェア（Ｉ／Ｏ能力を有する１つ以上のマイクロコントローラおよびここに記載する機能を実行するための搭載ルーチン）、あるいはこれらを組み合わせものに実装可能である。特定の場合では、本システムを、実行可能なRLS分類モジュール、あるいはこれらのモジュールを記憶するモージュールセットを備えた、デスクトップやラップトップコンピュータなどの演算環境に実装する。
【００１６】
ここに記載する特徴や利点は必ずしも包括的なものではなく、特に、さらに多くの追加的な特徴や利点があることは、本願の図面や記載に照らすならば当業者には明らかでる。さらに、本明細書中に用いられる表現は、主に、読みやすさや例示の目的から選んだものであって、これによって本発明の主題の範囲が限定されるものではない。
【発明を実施するための最良の形態】
【００１７】
正則化最小二乗法をより実践的に用いる技術を開示し、より具体的には、従来技術に係わる演算上の制約を低減する技術を開示する。
【００１８】
＜概  要＞
本発明の一実施形態では、正則化最小二乗分類器（RLSC）を提供する。周知の通り、分類器は（対象物の特性や状況の特徴に関する値など）入力値を受けると、これら入力値に関するラベルを個別に出力するようにプログラムされている、あるいはそのように構成されている。顔認識、対象物追跡、室内ナビゲーション、医療画像解析、音声認識などは分類法が適用された応用例である。このような分類器を、固定型分類器あるいは学習用分類器として実装可能である。さらに、ここに記載する技術は、本開示に照らせば明らかなように、RLS回帰の問題にも適用可能である。
【００１９】
2009510633.tif 000011
SVMの解法の開発者によっては、LOOの算出や（Rifkin、２００２年）、境界付け（Joachims、１９９０年）を可能にした者もいるが、正確に演算を行おうとすれば演算の費用がかさみ、境界付けには重大な誤差が付随的に発生する恐れもある。ここで述べるように、中規模から小規模のデータセットについては、交差検定（cross-validation）の「黄金基準（gold standard）」としてLOOを効果的に用いることができる。この基準はほとんど偏りがなく、10-fold cross-validationなどの手順に関連するばらつきは極めて高く、データセットの分割を変えることで実質的に異なる結果がもたらされる。大規模なデータセットについては、LOOの重要度は低くなるが、ここで述べるように、同じく利用には適している。
【００２０】
従って、本発明の一実施形態では、RLSに関連するいくつかのタスクについて、極めて安価な演算費用で正則化パラメータλを広範囲な値全体ついて変化させる方法を示すとともに、分類器を構築し、同時にトレーニングセットを用いてこれらの分類器でLOO値を演算することで、RLSをより実践的なものにする。正則化の手法ではλの選択は重要であり、選択が悪いと分類器の精度が損なわれることになる。RLS（およびSVM）を頻繁に「モデル選択」のフレームワークに用いるため、膨大な数のλ値を検証する能力は、すなわち演算上の強みを意味する。RLSを特徴選択の問題（例えば、顔・対象認識など）の構成要素として用いるときや、カーネルのハイパーパラメータの選択が必要なときに、この違いが特に重要になる。ここに記載する方法論の１つは、（O(n2)カーネル行列を記憶・操作可能な）中規模の問題について、１つのλについて「直接的に」解く場合と比較すると小さい定数係数（おおよそ３）でスローダウンはあるものの、膨大な数のλ値について「解」cとLOO値の両方を求めることから始まる。次に、本方法論では、多数の基準データセットにおいてσとλを広範囲に変化させる大規模な実験を行って、大きいσ値を用いることで正確な分類がしばしば得られることが実験観察から明らかである。加えて、σを大きくして大規模な問題を解く能力を利用する方法と、多数の演算例についても説明する。
【００２１】
＜システム構造＞
【００２２】
図１は、本発明のある実施形態に係わる構成の演算環境１０を示すブロック図である。
【００２３】
この事例から分かるように、演算環境１０には、バス１１９を介してメモリ１０７に動作可能に接続されるプロセッサ１０１と、ＲＬＳ分類器／回帰モジュール１０５（および、オペレーティングシステムおよびアプリケーションなどのこの他の実行可能な符号）を記憶する記憶装置１０３と、キーボード１１３と、グラフィックアダプター１０９と、ポインティング装置１１７と、ネットワークアダプター１１５とを備える。ディスプレイ１１１は、グラフィックアダプター１０９に動作可能に接続される。
【００２４】
プロセッサ１０１はいずれのプロセッサであってもよく、各種のオペレーティングシステム（UNIX（登録商標）など）や演算環境１０のアプリケーション／ドライバ（MATLAB（登録商標）など）を実行可能なプロセッサのセットであってもよい。多数の最適なプロセッサ（例えば、Intel Pentium（登録商標）、MAC（登録商標）のG4またはG5のプロセッサ、AMD（商標）のKプロセッサ、いずれのコプロセッサ、オンボードキャッシュなどのこの他の代表的な演算最適化）を使用可能であることは、本開示に照らせば明らかである。メモリ１０７は、例えば、ファームウェアＲＯＭ、ＲＡＭおよびまたはフラッシュメモリであってもよく、（例えば、５１２Ｍバイト以上の）プロセッサ１０１が用いる指令やデータを記憶する。一実施形態では、記憶装置１０３は（例えば、１０ギガバイト以上の）ハードディスクドライブであるが、データを持続的に記憶でるものであれば、メモリスティックや固体メモリ装置などのいずれの装置であってもよい。記憶装置１０３は、一般に行われるように、実行可能な符号およびまたはデータを含む複数のファイルを記憶可能である。演算環境１０は実行可能なファイルをメモリ１０７にロードして、プロセッサ１０１でこれを実行する。図示する実施形態では、ＲＬＳ分類器モジュール１０５は記憶装置１０３に実行可能な符号として記憶され、メモリ１０７にロードされて、１つ以上の処理を行うためにプロセッサ１０１で実行される。
【００２５】
記憶装置１０３に記憶されるファイルは、例えば、MATLAB形式（Mファイルとも呼ばれる）であってもよい。記憶装置１０３には、他のファイル形式も記憶できるため、例えば、EXEファイル、DLLファイル、INIファイル、あるいは演算環境を適切に動作させるために必要なファイル種別であればいずれであってもよい。このようなファイルは、Microsoft社のオペレーティングシステムを組み込んだ演算環境において代表的なものである。この他のファイル形式としては、Apple社のMacintosh（登録商標）およびUNIXベースのコンピュータで利用されるものであることは、本開示に照らせば明らかであろう。
【００２６】
ポインティング装置１１７は、マウス、トラックボール、あるいはこの他のユーザによる入力装置などがあり、一般に行われているように、キーボード１１３と組み合わせて用いることでユーザが演算環境１０とのやり取り（入力データおよびプロンプトへの応答など）が可能となる。グラフィックアダプター１０９は、画像やこの他の情報をディスプレイ１１１に表示する。ネットワークアダプター１１５は、所望であれば、一般に行われるように、（例えば、従来の有線・無線技術などを用いた）インターネットやLANあるいはこれらを組み合わせたような外部ネットワークを介して通信可能に演算環境１０に接続する。
【００２７】
演算環境１０は、コンピュータプログラムモジュールを実行して、ここに記載するようなＲＬＳ分類器モジュール１０５の機能を含むＲＬＳ機能をもたらす。ＲＬＳ分類器モジュール１０５の構造と機能については、図２から図５を参照しつつ詳細に説明する。本開示に照らせば明らかなように、演算環境１０は、汎用のデスクトップ型またはノート型のコンピュータなどの処理システム、あるいは、ここに記載するＲＬＳ分類（またはＲＬＳ回帰）を実行するように構成された専用の処理システムを介して実現してもよい。場合によっては、演算環境１０は、１．７ＧＨｚのPentium-Mプロセッサおよび２ギガバイトのRAMを搭載したIBM社製Ｔ４２ラップトップによって実現される。この他の集中的な演算処理は、標準的なユーザのデスクトップ環境でも実行可能であるが、ここに記載するＲＬＳ処理を実行するために処理能力を反転させる必要性に応じて限定することもできる。
【００２８】
＜分類器／回帰モジュール＞
図２は、本発明のある実施形態に係わるＲＬＳに分類器／回帰モジュール１０５内のモジュールを図示するブロック図である。
【００２９】
図示するように、モジュール１０５には、入力モジュール２１０と、カーネル行列生成器２０３と、固有値分解／SVDモジュール２０５と、係数（c）演算モジュール２０７と、LOO（leave-one-out）誤差演算モジュール２０９と、正則化パラメータ（λ）選択モジュール２１１と、予測モジュール２１３と出力モジュール２１５とを備える。一実施形態では、これらモジュールの各々は、所定の機能性を提供するための実行可能なソフトウェア（例えば、Ｃ、Ｃ＋＋、この他の最適な指令セットなど）によって実現される。ただし、このようなモジュールは、ハードウェア（例えば、ゲート論理など）、ファームウェア（各モジュールの機能性を実行するルーチンを搭載したマイクロコントローラ）あるいはこれらの組み合わせによっても実施可能である。本開示に照らせば、ここに例示されるモジュールは本発明の一実施形態を示したものであることは理解できるであろう。したがって、この他の実施形態には、追加的な、あるいは異なるモジュールや機能性を含んでいてもよい。同様に、他の実施形態では、ここに記載するいくつかのモジュールを欠いたり、モジュール間で前記RLSの機能性を異なる形態によって分散させるようにしてもよい。
【００３０】
2009510633.tif 000012
カーネル行列生成器２０３は、カーネル行列（K）がO(n2)のサイズであるような対距離のカーネル行列（K）を生成するようにプログラミングされている、もしくはそのように設計されている。なお、以下に順次説明するのだが、本発明の一実施形態によれば、カーネル行列生成器２０３は、特異値分解の処理を用いることができる線形カーネルの場合には適用しない。
【００３１】
本発明のある実施形態に係わるRLSCアルゴリズムでは、下の式３を用いればLOO（leave-one-out）誤差値が陽関数表現で与えられる。
【００３２】
【数３】
2009510633.tif 000013
【００３３】
2009510633.tif 000014
【００３４】
係数c演算モジュール２０７は、正則化パラメータ（λ）の集合を受信し、固有値分解／SVDモジュール２０５が算出した行列分解を用いて、各λについて係数cを算出するようにプログラムされている、もしくはそのように設計されている。
2009510633.tif 000015
【００３５】
【数４】
2009510633.tif 000016
【００３６】
2009510633.tif 000017
【００３７】
固有値分解／SVDモジュール２０５は、カーネル行列Kの固有値分解を算出するようにプログラムされている、もしくはそのように設計されている。かつまたは、（線形カーネルの場合についても）固有値分解／ＳＶＤモジュール２０５は、データ行列（トレーニングセットのデータ）の特異値分解（SVD）を算出することができる。
【００３８】
2009510633.tif 000018
【００３９】
【数５】
2009510633.tif 000019
【００４０】
ここで、超平面wはXtcとして定義する。新規のデータ点を分類するときには、n個のカーネル積（通常O(nd)時間かかる）の加重和を算出せずに、wを用いてO(d)時間にて分類することができる。n×dデータの行列Xは、行列Xのランクが列数と同じ（full column rank）であり、経済的な規模の特異値分解X=USVt を有するものとする。
2009510633.tif 000020
【００４１】
【数６】
2009510633.tif 000021
【００４２】
SVDの算出に、O(nd2)時間とO(nd)メモリが必要になる。
【００４３】
Uを算出すると、λの所定値について、cとdiag(G−１)をO(nd)時間で求めることができる。n>>dのとき、O(nd3)時間ではなくO(nd2)時間で良好なλを求められる点で、大幅な節約と言える。高次元の大規模データセットでは、メモリ上でのデータセットの調整が困難な場合がある。さらに、基本的にSVDはout-of-coreで算出したり、コンピュータ群により平行的に演算することは可能であるが、このような作業ツールは容易に手に入るものではない。
2009510633.tif 000022
【００４４】
【数７】
2009510633.tif 000023
【００４５】
VとS2をd×d XtXの固有値分解から求めることができる。さらに、U=XVS−１であるため、Uを含む表現であればXVS−１として記述することができる。この式の利点は、XtXやXtyを生成する並列プログラムやout-of-coreプログラムはプログラミングの作業がそれほど困難でない点である。この手法で最も時間がかかるのは、共分散行列XtXを生成する段階であり、O(nd2)時間がかかり、さらに後の固有値分解にO(d3)時間がかかる。この手法では、XtXとXtYを生成するための環境整備の労力は必要だが、d×d行列を処理する能力さえ与えれば演算により実施可能である。実際には、n >> dであり、ここに記載するような共分散法を用いる場合の線形関数の処理ではw(λ)のみを求めて、cとdiag(G−１)の演算に必要なU=XVS1−１を求めるよりもテストセット（holdout set）で動作確認を行うほうが好ましい。SVDおよび共分散に基づく手法には、同じような（漸近的な）演算上の複雑さがある。しかし、SVD手法は数値的に安定していると言える。
【００４６】
2009510633.tif 000024
【００４７】
予測モジュール２１３は、最も優れたλに対応するRLS関数に基づいて（例えば、膨張係数cまたは超平面関数wに基づいて）データ点をさらに予測する。出力モジュール２１５は、入力されたデータセットに基づいてRLSの予測を出力するようにプログラムされている、もしくはそのように設計されている。さらに、出力モジュール２１５は、出力された予測データのフォーマット化と構築を（必要ならば）適宜行って、このデータをディスプレイ、あるいは報告できるように準備をする。
【００４８】
本実施形態により実現される時間短縮について、最良の事例を示す。より詳細には、表１を参照しつつ、４１９２点ある１４次元のGalaxy Dimデータセットを検討する。データセット全体と、このデータセットの半分のランダムなサブセットについて、従来の直接法と本発明のある実施形態に係わる固有値分解法とをそれぞれに用いてLOO誤差値を算出し、そのタイミングを比較した。表１に報告したタイミング結果は概算値（例えば、±５％）であるため、近似するタイミングの順番は変わる場合もある。報告した時間はすべて、５回のテストの平均値であり；分散値は平均値と比べて小さかった。時間はすべて経過時間で表した；ディスクの交換は行なわず、システム時間は合計時間では問題にならない程度であった。
【００４９】
【表１】
2009510633.tif 000025
【００５０】
表１：直接線形代数を用いてGalaxy DimデータセットのLOO値を算出するのにかかった時間（秒）
【００５１】
上記から分かるように、この規模の問題（例えば、２０４８点から４０９２点まで）で、３以上のλを検討するときには、本発明のある実施形態に係わる固有値分解法によるLOO誤差算定のほうが有利であり、λの数が増えるほどより有利になる。λあたりの費用はO(n3)ではなくO(n2)であるため、問題の規模が大きくなるほど、（十分な数のλがある場合には）固有値分解の利点も相対的に大きくなる。この程度のnの範囲では、直接法と固有値分解法はいずれもO(n3)であるが、問題の規模が２倍になれば、約８倍（２０４８点では８．１倍、４０９２点では８．５倍）の時間がかかることになる。異なる２５個のλについてLOO値を算出するのにかかった合計時間は、２０４８点で３８．１秒であり、データセット全体の４１９２点では３１１．１秒であった。ここで説明するアルゴリズムはO(n2)空間を用いるため、中規模のデータセットに好適である。大規模なデータセットに好適な手法については後述する。
【００５２】
＜σおよびλの変化＞
効果を例示する目的から、RLS分類器／回帰モジュール１０５の実施形態を本明細書に記載するように実現し、これを用いて大規模な実験を行った。その中で、所定のデータセットについて、値の範囲全体で帯域幅パラメータσを変化させて、多数の正則化パラメータλの各σ値についてLOO値を算出する。
図３ａ、図３ｂ、図４ａ、図４ｂは、４つのデータセットについての実験結果をそれぞれ示したものである。なお、この他のデータセットも利用可能であり、UCI machine learning repository（UCI = University of California at Irvine；例えば http://www.ics.uci.edu/~mlearn/MLRepository.htmlを参照のこと）なども類似する結果を有するため利用可能である。図３ａ、図３ｂ、図４ａ、図４ｂのラベル付けされた縦線のmはカーネル行列の最小成分を表す。
【００５３】
図３ａ、図３ｂ、図４ａ、図４ｂからは多数の興味深い観察事項が読み取れる。例えば、λの選択が適切であれば、最高レベルの精度に等しいか、それに近似するレベルの精度が得られるようなσ値の範囲が幅広いことが分かる。さらに、非常に大きいσで正確な分類／回帰を得ることができる。特に、カーネル行列のすべての成分が限りなく１に近似する（例えば、０．９９９９以上）ようにσを選択することができる。同時に、大きいσを用いて好適に分類を行うためには、λをできる限り小さくする必要がある。ここで、数式の限界を理解することが重要になる。
【００５４】
2009510633.tif 000026
【００５５】
通常、RLSC（およびSVM）は、テストのデータ点を中規模数の近似点によって分類するような重み付け局所法として働くものだ、という直感的事実に基づけば、このように大きいσで好適な分類が行える能力が得られることは予想できない。大きいσを用いる手法では、最も遠い点は、最も近いものとほぼ同じインパクトを有する。以下では、本発明の各種実施形態に係わる、大きいσを利用した大規模な正則化最小二乗分類器（および回帰）の問題を迅速かつ正確に解く方法について説明する。
【００５６】
＜大規模問題と大きいσ＞
2009510633.tif 000027
【００５７】
【数８】
2009510633.tif 000028
【００５８】
処理がrステップ分だけ実行されるとき、得られるQは、連続するベクトルx0,Kx0, K2x0,…  Kr−１x0のGram-Schmidtの直交化法（Gram-Schmidt orthonormalization）によって与えられる直交基底、つまり、Kyrlovの部分空間（Kyrlov subspace）である。
【００５９】
2009510633.tif 000029
【００６０】
2009510633.tif 000030
【００６１】
【数９】
2009510633.tif 000031
【００６２】
2009510633.tif 000032
【００６３】
丸め誤差は、qiにおける直交性の損失を引き起こす傾向がある。したがって、式１から式４を直接的に用いると不安定を招く恐れがある。そこで、ARPACK（LehoucqおよびSorensen、１９９６年； Lehoucqら、１９９７年）ライブラリによって、数的に安定したバージョンである、Lanczos原理（Lanczos process：アーノルディ原理（Arnoldi process）を安定的に実装したものであり、アーノルディ原理の特殊事例である）が提供されており；ここに記載する実験にこのライブラリを用いる。
【００６４】
ここに記載する数学はσに関係なく適用する。しかし、できる限り大きい σ を用いることが有用である理由は少なくとも２つあり、いずれの理由もKの構造に関係する。ガウスカーネル（Gaussian kernel）と、一般の位置（general position）における点を用いて、正確な計算においては、Kはいずれの σ についてもフルランク（full rank）となる。しかし、σ が大きくなるほどKの崩壊スペクトルが速くなって、下位ランクの行列を有するKの概算が容易になり、O(n2) 未満時間で正確な行列・ベクトル積Kxを生成することが容易になる。非線形のRLS分類を迅速に行うための前記作業の大半は、このような概算法に着目したものであるが、大きいσを用いた概算法により取り扱いが容易になることには結びついてはいなかった。大きなσを用いることで、同時に多数の利点が得られる。例えば、正則化最小二乗分類に必要な行列・ベクトル積が少なくてすむのは、Kの固有構造の崩壊が迅速であり、行列・ベクトル積Kxの概算が容易であるからだ。
【００６５】
＜改良型高速ガウス変換（Improved Fast Gauss Transform (IFGT)）＞
本発明の一実施形態によれば、改良型の高速ガウス変換（IFGT）を用いて行列・ベクトル積Kxを生成することができる。また、ニストロム法（Nystrom method）など、この他の手法も用いてもよい。IFGTにより中心のセットを取り出し、これら中心付近の截端（丸め）エルミート展開（truncated Hermite expansions）を合計したものを用いて行列・ベクトル積Kxを算出する。本明細書の目的から、IFGTをブラックボックスとして取り扱う；つまり、行列A、ベクトルx、パラメータpが与えられるならば、IFGTは、Axに対する「第p次数」の概算値を算出する。第p次数を１つ処理するために、IFGTは、O(ndp) 時間とO(ndp) 空間を要し； CGの反復が一定数であるとすれば、得られるアルゴリズムは、時間と空間のいずれもO(ndp)になる。dp << nであるときには、このやり方は非常に効果的である。
【００６６】
Yangらは、σが小さい固定値の場合には、IFGTは最終的にはゆっくりと多項式次数pへ収束することを証明する実験を行っている。さらにYangは、小さいp (p = 1, 2)についてのIFGTの動作時間が非常に魅力的であることも証明している。しかし、Yangは、σやλを変化させることは考慮していない。むしろ、Yangは、各データセット（.5d）に１つのσ値を用いているが、λの指定はしていない。Yangのデータセットと同じものをここで検討するのだが、最適なσを求めて適切なλを選択するため、より良好で均一な動作性のを達成することができる。
2009510633.tif 000033
【００６７】
＜実  験＞
ここで再びGalaxy Dimデータセットを考慮する。特に、Galaxy Dimはこの規模（４１９２点）の事例に適しており；このサブセットは、漸近解析を良好に理解するには十分な大きさの規模であり、カーネル行列K全体を必要とする方法と必要としない方法を比較するには十分な小ささの規模である。表１を再び参照して、２０４８点のデータのサブセットでは、異なる２５個のλについてLOO値を算出するのにかかった合計時間は３８．１秒であり、４１９２点のデータセット全体では３１１．１秒であった。ここに記載する方法を用いて、第３次数のIFGTとσ = 100を用いて実施される行列・ベクトルの積算を行うと、同じ演算を２０４８点について行った場合の時間は１９．３秒であり、４１９２点全体では３８．３秒であった。本発明の一実施形態によれば、λ >= 1e−11について結果はすべて必然的に同じであり、フルの固有値分解とIFGTベース法を用いて、２点以下のデータ点を個別に分類した。必然的にタイミングは線形であり、データセットの規模ではIFGTは線形であるが、データセットの規模が大きくなれば、収束までの演算の反復回数が若干増える。低次数のIFGTでは、IFGTの１反復にかかる時間は実質的に短くなるものの、精度が落ちる可能性もある。
【００６８】
ここで、カーネル行列全体を直接処理することは一般的に実用的ではないが、「マッシュルーム」という８１２４点、２２次元のデータセットについて検討する。ここに記載のIFGT法によるRLSを用いて、σ = 100、２６０秒で、λの範囲（例えば、10-16から10+16まで）において、このデータセットのLOO値を算出する。1e−11となるように最適なλを演算し、LOO値の演算精度が８８．８％になるようにした。４０６２点のデータのサブセットには１３７秒の作業が必要であった；ここで再び、IFGTアルゴリズムのRLSは必然的に線形時間であることを確認されたし。
【００６９】
＜方法論＞
図６は、本発明のある実施形態に係わるRLS分類／回帰の方法を示すものである。この方法は、例えば、図１および図２を参照しつつ説明したRLS分類／回帰モジュール１０５を用いて実行される。
【００７０】
この方法はトレーニングセットのデータを受信することを含む（Ｓ５０１）。線形カーネルの場合にはステップＳ５０３を飛ばして、ステップＳ５０５に進む。あるいは、入力したトレーニングセットを用いて対距離てのカーネル行列を生成する（Ｓ５０３）。なお、本方法では、ここに記載するRLS分類器／回帰モジュールのトレーニングが完了すると、実際のデータセットを受信することをさらに含む。
【００７１】
次に、前記の通りのカーネル行列の固有値分解を演算する、あるいは（線形カーネルの場合には）データ行列のSVDを演算する（Ｓ５０５）。本発明の実施形態によっては、固有値分解とSVDの両方を演算するように構成する。本方法は、正則化パラメータ（λ）の集合を受信することをさらに含む（Ｓ５０７）。このλの集合の範囲と分解能は、手動（ユーザ入力など）により、あるいは（ユーザ入力で指定した目標の範囲と分解に基づいて、あらかじめ記憶されたりハードコード化されたものから読み出したり、ダイナミックに演算するなどして）自動的に求めることができ、分類器の所望の精度とロバスト性などの要因に依存する。実施形態によっては、λの集合は10-16から10+16までの範囲であり、互いに均等な空間を置いた２００から４００までの中間的なλ値の分解能を含む。このような広範囲性は、（例えば、小さすぎる範囲から大きすぎる範囲で）収束が可能となり、このような収束を達成するために過度の演算を必要とせずに十分な分解能が得られる。
【００７２】
2009510633.tif 000034
【００７３】
次に、LOO誤差が最小値のλを選択する（Ｓ５１３）。前記に説明した通り、適切なλを選択することは、分類器の精度を確保するために重要である。さらに、最適なλに関するRLS関数（例えば、最適なλの係数cまたは超平面関数w）に基づいて将来のデータ点を予測する（Ｓ５１５）。分類の実用化（つまり、顔や対象、音声など、予測するもの）あるいは回帰の実用化（つまり、寿命やサラリーなど、予測する数量の大きさ）については、本開示に照らすならば、変更可能であることは明らかである。
【００７４】
本発明の２つの実施形態に係わるLOO・RLSの高速処理の２つの手法はλの範囲全体に用いることが可能であることを再び確認されたし：つまり、中規模データセットではO(n3+ n2d)時間、小さいO(n2d)メモリの手法と、大きいσを用いる大規模データセットではO(ndp)時間、O(ndp)メモリ（この場合のpは用いるIFGTの次数）の手法である。
【００７５】
本発明の実施形態は、例示的な説明の目的から前記の通りの説明を行った。これは包括的なものではなく、本発明を開示された形態に厳密に限定することを意図したものではない。したがって、本開示に照らすならば各種の修正や変形が可能である。例えば、係数cのみを正確に求め、diag(G−１)を求める必要がない場合には、ここに記載するLanczos原理での許容範囲を大きくしたり、あるいはもっと小さいσを用いることも可能である。しかしながら、大きいσの方が、Kのスペクトル崩壊が速く、IFGTも正確であるために好ましい；しかし、大きいσはすなわち小さいλを意味するため、本明細書のLanczos原理では許容範囲は小さくなる。従って、条件の選択を適切かつ慎重に行う必要がある。さらに、（ここに記載する）ガウスカーネルを有するRLS分類器の考え方は、おおまかな局所学習の手法としては、小さいあるいは中程度のσに依存し；大きいσについては、最も遠い点は最も近い点とほぼ同じインパクトを有する。さらに、RLS分類器の漸近解析を検討する場合は、σ → ∞ および λ → 0ならば、RLS分類器は、σ/λ → 0のレートに依存するような次数を有する特定の多項式分類λの手法に収束する。同じく、ここに記載するσを用いた手法は、RLS分類の問題とRLS回帰の問題の両方に等しく適用することができる。本発明の範囲は、本明細書に記載された詳細によってではなく、むしろ付属の請求項によって限定されるべきである。
【図面の簡単な説明】
【００７６】
【図１】本発明のある実施形態に係わる構成の演算環境を示すブロック図である。
【図２】本発明のある実施形態に係わる構成の正則化二乗（ＲＬＳ）分類器／回帰モジュール１０５を示すブロック図である。
【図３】ａおよびｄは、本発明のある実施形態に係わる、σとλの範囲でのRLS分類器／回帰についての精度を示したものである。
【図４】ａおよびｄは、本発明のある実施形態に係わる、σとλの範囲でのRLS分類器／回帰についての精度を示したものである。
【図５】本発明の実施形態に係わる、事例データセットの ||K-FGT(K)||/||K|| を示したものであり、この場合のPは多項式展開の次数を表す。
【図６】本発明のある実施形態に係わるRLS分類／回帰の方法を示したものである。
【符号の説明】
【００７７】
１０    演算環境
１０１  プロセッサ
１０３  記憶装置
１０５  ＲＬＳ分類器／回帰モジュール
１０７  メモリ
１０９  グラフィックアダプタ
１１１  ディスプレイ
１１３  キーボード
１１５  ネットワークアダプタ
１１７  ポインティング装置
１１９  バス
２０１  入力モジュール
２０３  カーネル行列生成器
２０５  固有値分解／ＳＶＤモジュール
２０７  係数（ｃ）演算モジュール
２０９  ＬＯＯ誤差演算モジュール
２１１  正則化パラメータ（λ）選択モジュール
２１３  予測モジュール
２１５  出力モジュール
【図１】
2009510633.tif 000038
【図２】
2009510633.tif 000039
【図３】
2009510633.tif 000040
【図４】
2009510633.tif 000041
【図５】
2009510633.tif 000042
【図６】
2009510633.tif 000043
2009510633.tif 000044
2009510633.tif 000045
2009510633.tif 000046