线性SVM的训练复杂性 [英] Training complexity of Linear SVM
问题描述
SVM学习阶段的实际计算复杂度是多少(比如说，是在LibSVM中实现的)?
Which is the actual computational complexity of the learning phase of SVM (let's say, that implemented in LibSVM)?
谢谢
推荐答案
非线性的SVM的训练复杂度通常在O(n ^ 2)和O(n ^ 3)之间，其中n为训练实例.以下论文是很好的参考:
Training complexity of nonlinear SVM is generally between O(n^2) and O(n^3) with n the amount of training instances. The following papers are good references:
- 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)， SVM ^ perf .这些对于线性SVM具有很多更好的训练复杂性.训练速度可能比使用LIBSVM好几个数量级.
PS: If you want to use linear kernel, do not use LIBSVM. LIBSVM is a general purpose (nonlinear) SVM solver. It is not an ideal implementation for linear SVM. Instead, you should consider things like LIBLINEAR (by the same authors as LIBSVM), Pegasos or SVM^perf. These have much better training complexity for linear SVM. Training speed can be orders of magnitude better than using LIBSVM.
这篇关于线性SVM的训练复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
