time-complexity - 線形 SVM のトレーニングの複雑さ

Question

SVM の学習フェーズの実際の計算上の複雑さはどれですか (たとえば、LibSVM に実装されているとしましょう)?

ありがとうございました

Answer 1

非線形SVMのトレーニングの複雑さは、一般に O(n^2) から O(n^3) の間であり、トレーニング インスタンスの量は n です。以下の論文が参考になります。

• Bottou と Lin によるベクター マシン ソルバーのサポート
• List と Simon による SVM 最適化と最急降下線検索

PS: リニア カーネルを使用する場合は、LIBSVM を使用しないでください。LIBSVM は、汎用 (非線形) SVM ソルバーです。これは、線形 SVM の理想的な実装ではありません。代わりに、LIBLINEAR (LIBSVM と同じ作成者による)、Pegasos、SVM^perfなどを検討する必要があります。これらは、線形 SVM のトレーニングの複雑さがはるかに優れています。トレーニング速度は、LIBSVM を使用するよりも桁違いに優れています。