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

Answer 2

这将在很大程度上取决于 svm 类型和内核。有一个相当技术性的讨论http://www.csie.ntu.edu.tw/~cjlin/papers/libsvm.pdf。为了快速回答，http ://www.csie.ntu.edu.tw/~cjlin/papers/libsvm.pdf说期望它是 n^2。