线性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 快几个数量级。

这将严重依赖于 svm 类型和内核。有一个相当技术性的讨论

Answer 2

。 要快速回答，

http://www.csie.ntu.edu.tw/~cjlin/papers/libsvm.pdf，表示期望它是 n^2。