time-complexity - 线性 SVM 的训练复杂度

Question

哪个是 SVM 学习阶段的实际计算复杂度(比如说，在 LibSVM 中实现的)？

谢谢

Answer 1

非线性 SVM 的训练复杂度通常在 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 好几个数量级。