训练一个SVM分类器需要多长时间？

Question

我写了以下代码并在小数据上进行了测试：

classif = OneVsRestClassifier(svm.SVC(kernel='rbf'))
classif.fit(X, y)

在这里，X, y（X - 30000x784矩阵，y - 30000x1）是NumPy数组。在小数据上，算法表现良好并给出了正确的结果。

但是我大约10小时前启动了我的程序...而且它仍在进行中。

我想知道还需要多长时间，或者它是否卡住了？ （笔记本电脑规格：4 GB内存，Core i5-480M处理器）

- Il'ya Zhenin

---

嗯...30000个维度和30000 X 784个点...我并没有太长时间的机器学习经验，但这是一个相当大且高维的特征向量...我认为它花费那么长时间并不令人惊讶...你可以尝试减少维度以加快速度... - Roy

@Roy 对于核方法来说，减少训练实例的数量比降低维度要有效得多。 - Marc Claesen

@MarcClaesen 我只能相信你的话，因为我自己也只是一个新手。 - Roy

Answer 1

SVM的训练时间可以任意长，这取决于几十个参数：

- C参数 - 错误分类惩罚越大，过程越慢 - 核函数 - 核函数越复杂，过程越慢（rbf是预定义核函数中最复杂的） - 数据大小/维度 - 同样的规则也适用于这个

一般来说，基本的SMO算法的时间复杂度是O(n^3)，所以在有30,000个数据点的情况下，它需要运行的操作次数与2,700,000,000,000成正比，这是一个非常庞大的数字。

你有哪些选择呢？

- 将核函数改为线性核函数，784个特征已经相当多了，rbf可能是多余的 - 降低特征的维度（使用PCA等方法） - 降低C参数的值 - 在部分数据上训练模型以找到好的参数，然后在某个集群/超级计算机上对整个数据集进行训练。

- lejlot

---

当涉及到真正大的问题时，内核计算时间通常不是一个问题。径向基函数（RBF）和多项式等不同内核的差异是无关紧要的。内核复杂度的唯一方面是线性与其他方面之间的区别。此外，训练复杂度范围从 O(n^2)（小 C）到 O(n^3)（大 C）。第三，输入维度对总体复杂度影响不大（总体复杂度是训练实例数的函数，而不是维度）。 - Marc Claesen

谢谢。参数C会使算法变慢，我没有考虑到这一点。我也不知道rbf是最复杂的核函数 - 但事实是，当我将核函数改为'poly'时，它在2小时内给出了结果。 - Il'ya Zhenin

@Marc - 感谢您的评论。径向基函数和多项式之间存在巨大差异，不是因为核函数本身很复杂，而是诱导的RHKS很复杂，这就是优化发生的地方。其次，O（n ^ 3）是上限，显然对于小的C来说速度更快。第三，维数很重要，因为它在每个核计算的成本中起作用（不太重要），并且因为它参与诱导的RHKS的复杂性的复杂性（更重要）。 - lejlot