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好几个数量级。