machine-learning - SVM 分類器の予測計算量

Question

線形 SVM の予測の複雑さは? 分離面は単なる超平面であるため、予測時間はトレーニング データに依存するべきではないようです。同時に、複雑さはサポート ベクターの数に比例することを読みました。これらすべてのサポート ベクターをトレーニング済みの分類器に保持する意味は何ですか?

Answer 1

線形 SVM の場合、分離超平面は実際に明示的に計算され、モデルとして保存されます。つまり、線形 SVM モデルを使用した予測では、入力空間に超平面が厳密に必要です。多くの特殊な線形パッケージはまさにこれを行います(LIBLINEAR、SVMPERF、PEGASOS など)。線形 SVM で予測するためにサポート ベクターの知識は必要ありませんが、サポート ベクターを知っていれば、さまざまな用途に使用できます。

非線形カーネルを使用して SVM で予測する場合、分離超平面が無限次元になる可能性があるため (たとえば、RBF カーネルを使用する場合)、話はまったく異なります。超平面自体を特徴空間で計算することは不可能かもしれませんが、超平面と特徴空間のテスト ポイントの間の内積は、サポート ベクターとテスト ポイントの間のカーネル評価を介して計算できます。これがいわゆるカーネルトリックです。

線形カーネルと非線形カーネルの両方をサポートするほとんどの一般的なパッケージは、すべてのモデルを同じ方法で保存する傾向があります (LIBSVM など)。これは、線形モデルが格納され、非線形モデルと同様に、テスト ポイントとサポート ベクター間の内積に関して評価されることを意味します。明らかに、これは線形 SVM の場合よりも複雑です。大多数の人は、線形 SVM をトレーニングする場合でも、特殊な線形パッケージではなく、SVM の一般的なパッケージを使用します。これがおそらく、線形 SVM による予測が常にサポート ベクターに依存していると多くの人が誤って想定している理由です。

Answer 2

そうです、予測時間は線形 SVM のデータに依存しません。これは、予測子がテスト ベクトルと学習済みの重みベクトルの間の内積であるためです。

サポートベクターを維持しても意味がありません。そうでないと言う人は混乱します:)。何らかの理由でサポート ベクターが後で知りたい場合は、トレーニング データで分類子を評価することで簡単に見つけることができます。予測に失敗するか、絶対値で 1 未満の SVM からの出力値を持つすべてのトレーニング データ サンプルがサポート ベクターです。