基于预备工作集的最小序列优化算法

为了提高支持向量机求解大规模问题的训练速度,提出了一种新的工作集选择策略--预备工作集策略:在SMO中,利用可行方向策略提取最大违反对的同时,从核缓存cache中提取违反KKT条件程度最大的一系列样本组成预备工作集,为此后历次SMO迭代优化提供工作集.该方法提高了核缓存的命中率,减少了工作集选择的代价.理论分析和实验结果表明,预备工作集策略能够很好地胜任待优化的工作集,加快了支持向量机求解大规模问题的训练速度.

SMO algorithm based on reserve working set strategy

In order to improve the training speed for large-scale problem, proposed a new strategy for the working set selection in SMO algorithm based on the tradeoff between the cost on working set selection and cache performance. This new strategy selected several maximal violating samples from cache as the reserve working set which would provide iterative working sets for the next several optimizing steps. The new strategy could improve the efficiency of the kernel cache and reduce the computational cost related to the working set selection. The results of theories and experiments demonstrate that the proposed method can reduce the training time, especially for large datasets.