Linear SVM的訓練複雜度

Question

SVM的學習階段的實際計算複雜度是什麼（比方說，在LibSVM中實現）？

謝謝

Answer 1

這將嚴重依賴於svm類型和內核。有一個相當技術性的討論http://www.csie.ntu.edu.tw/~cjlin/papers/libsvm.pdf。 爲了快速回答，http://www.csie.ntu.edu.tw/~cjlin/papers/libsvm.pdf，表示期望它是n^2。

Answer 2

訓練複雜度爲非線性支持向量機一般在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好幾個數量級。