博客

复杂度高的原因：

1. SVM参数优化方法是先转为对偶问题再使用SMO算法，最坏情况下要计算n*n次，并不适合在大规模数据集上做分类。
2. svm使用核技巧时，如RBF，特征会升高至无限维，计算量也很大。

补充：

LR较为简单，可以适用于大规模线性分类。SVM可以有效解决

高维特征的分类和回归问题

。

训练SVM的最小时间复杂度为



O

(

n

2

)

O(n^2)






O


(



n










2









)





，SVM对小样本的寻优能力是非常好的，无可置疑。SVM的优化目标是结构化风险最小，有优秀的泛化能力，所以在小样本高维特征上表现很好。对大样本可能不太适合，一是上面提到的复杂，二是样本足够多时，支持向量基本固定了，许多不重要样本的增加不能提高性能了。

对SVM来说，求得解析解的时间复杂度最坏可以达到



O

(

N

s

v

3

)

O(Nsv3)






O


(


N


s


v


3


)





，其中



N

s

v

Nsv






N


s


v





是支持向量的个数，而虽然没有固定的比例，但支持向量的个数多少也和训练集的大小有关

如何解决复杂度高的问题呢？

1. 分布式，对不同样本对做核距离计算，可以分开放在不同机器。有人提到PEGASOS就是一种分布式的SVM的训练方法，待学习。
2. 
   svm-light
   
   和
   
   libsvm
   
   
   但实际中这些效果并不太好