リニアSVMのトレーニングの複雑さ

Question

SVMの学習段階の実際の計算の複雑さはどれですか（LibSVMで実装されているとします）？

これはSVMの種類やカーネルに大きく依存することになるだろうあなた

Answer 1

ありがとうございます。むしろ技術的な話があるhttp://www.csie.ntu.edu.tw/~cjlin/papers/libsvm.pdfです。 クイックアンサーでは、http://www.csie.ntu.edu.tw/~cjlin/papers/libsvm.pdfは、それがn^2であると期待しています。

Answer 2

トレーニングの複雑さ非線形 SVMは一般にO（n^2）とO（n^3）の間にあり、nはトレーニングインスタンスの量です。以下の論文は良いリファレンスです：

• Support Vector Machine Solvers by Bottou and Lin
• SVM-optimization and steepest-descent line search by List and Simon

PS：あなたは線形カーネルを使用する場合は、LIBSVMを使用しないでください。 LIBSVMは汎用（非線形）SVMソルバです。リニアSVMの理想的な実装ではありません。代わりに、LIBLINEAR（LIBSVMと同じ著者）、PegasosまたはSVM^perfなどを考慮する必要があります。これらは、多くのリニアSVMのトレーニングの複雑さがあります。トレーニングのスピードは、LIBSVMを使用するよりもはるかに優れています。