大規模データセットのカーネルメソッド

Question

カーネルベースの分類器は、通常、2つのインスタンス間の内積計算のためにO（n^3）のトレーニング時間を必要とします。トレーニングをスピードアップするために、内積値を事前計算して2次元アレイに格納することができます。しかし、インスタンスの数が非常に多く、たとえば100,000を超えると、そうするための十分なメモリがないことになります。

だからこれについてもっと良いアイデアですか？

Answer 1

関連性ベクトルマシンは、カーネルマトリックス全体をメモリに保持する必要がないシーケンシャルトレーニングモードを備えています。基本的には、一度に1つの列を計算し、関連するかどうかを判断し、そうでない場合はそれを放棄することができます。私は自分自身にそれほど運がなかったし、RVMにはいくつかの問題がある。 Gaussian Processsの分野では、より良い解決策が考えられます。私は実際にはあまり座っていないが、私はそれのためのオンラインアルゴリズムの言及を見てきた。

Answer 2

私は数値アナリストではありませんが、普通の最小二乗線形回帰O（n^3）を行う必要がありますQR decompositionですか？

とにかく、あなたが使っているアルゴリズムのオンライン学習やアクティブ学習のバージョンでは、文章を検索したいと思うかもしれません（これはかなり新しいものです）。一般的な考え方は、意思決定の境界から離れたデータを破棄するか、最初にそれらを含めないことです。危険なのは、あなたが悪いローカル最大値にロックされ、あなたのオンライン/アクティブなアルゴリズムがあなたが出るのを助けるデータを無視するということです。

Answer 3

サポートベクターマシンの最新の実装では、トレーニングアルゴリズムのスケーリングは、使用しているトレーニングデータとカーネルの性質など、多くの要因に依存します。 O（n^3）のスケーリング係数は分析結果であり、実際の状況でSVMトレーニングがどのようにスケーリングされるかを予測するのに特に有用ではありません。例えば、SVMLightによって使用されるトレーニングアルゴリズムの経験的推定は、トレーニングセットサイズに対するスケーリングをapproximately O(n^2)とした。

kernel machines forumでこの質問をすることをお勧めします。スタックオーバーフローよりも優れた答えを得る可能性が高いと思います。スタックオーバーフローは、汎用プログラミングサイトのほうが多くです。