machine-learning - SVM顺序最小优化的收敛问题

Question

我已经研究支持向量机大约两个月了。我自己编写了SVM，对于SVM的优化问题，我使用了John Platt博士的顺序最小优化(SMO)。

现在我正处于通过网格搜索来为我的数据集找到最佳 C 值的阶段。 (请在此处查找我的项目应用程序和数据集详细信息 SVM Classification - minimum number of input sets for each class )

我已成功检查了自定义实现的 SVM 对 C 值范围从 2^0 到 2^6 的准确性。但现在我遇到了一些关于 C> 128 的 SMO 收敛的问题。 就像我试图找到 C=128 的 alpha 值一样，它需要很长时间才能真正收敛并成功给出 alpha 值。

对于 C=100，SMO 收敛所需的时间约为 5 小时。我认为这个巨大(因为 SMO 应该很快。)尽管我得到了很好的准确性？ 我被搞砸了，不是因为我无法测试较高 C 值的准确性。

我实际上显示了 SMO 每次传递中更改的 alpha 数量，并得到 10、13、8...alpha 不断变化。 KKT 条件确保收敛，那么这里发生了什么奇怪的事情呢？

请注意，尽管执行时间很长，但我的实现对于 C<=100 运行良好，并且具有良好的准确性。

请就这个问题向我提供意见。

谢谢你，干杯。

Answer 1

对于大多数 SVM 实现，训练时间会随着 C 值的增大而急剧增加。要了解 SMO 相当好的实现中的训练时间如何随 C 缩放，请查看 libSVM 的对数刻度线如下图所示。

SVM 训练时间与 C - 来自 Sentelle 等人的 A Fast Revised Simplex Method for SVM Training .

alt text http://dmcer.net/StackOverflowImages/svm_scaling.png

您可能有两种简单的方法和一种不太简单的方法来加快速度。

让我们从简单的事情开始。首先，您可以尝试放宽收敛标准。像 epsilon = 0.001 这样的严格标准将需要更长的时间来训练，而通常产生的模型并不比 epsilon = 0.01 这样的宽松标准更好。其次，您应该尝试分析您的代码以查看是否存在任何明显的瓶颈。

不太容易的修复方法是切换到不同的优化算法(例如，来自 Sentelle 等人上述论文的 SVM-RSQP)。但是，如果您有 SMO 的有效实现，那么您可能只应该将其作为最后的手段。