线性支持向量机的训练复杂度

Question

支持向量机的学习阶段的实际计算复杂度是多少（比如在LibSVM中实现的）？

谢谢。

- user1923631

Answer 1

非线性支持向量机的训练复杂度通常介于 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 快几个数量级。

- Marc Claesen

---

链接2已失效，而链接1的文档似乎已被删除。 - Carlos Pinzón

liblinear svm 的复杂度是多少？ - Michael D

Answer 2

这将严重依赖于支持向量机类型和核函数。有一个相当技术的讨论http://www.csie.ntu.edu.tw/~cjlin/papers/libsvm.pdf。 简单回答，http://www.csie.ntu.edu.tw/~cjlin/papers/libsvm.pdf，预计它将是n^2。

- Bull