改进工作集选择策略的序贯最小优化算法

针对标准序贯最小优化(sequential minimal optimization, SMO)算法采用可行方向工作集选择策略所带来的缓存命中率低下问题,给出了SMO类型算法每次迭代所带来的目标函数下降量的二阶表达式,并据此提出了一种改进的工作集选择策略.新策略综合考虑算法收敛所需的迭代次数及缓存效率,从总体上减少了核函数计算次数,因此极大提高了训练效率,并且,它在理论上具有严格的收敛保障.实验结果表明,核函数越复杂,样本维度越高,缓存容量相对训练样本的规模越小,改进工作集选择策略的SMO算法相较于标准SMO算法的性能提高就越显著.

An Improved Working Set Selection Strategy for Sequential Minimal Optimization Algorithm

Working set selection is an important step in the sequential minimal optimization (SMO) type methods for training support vector machine (SVM). However, the feasible direction strategy for selecting working set may degrade the performance of the kernel cache maintained in standard SMO. In this paper, an improved strategy for selecting working set applied in SMO is presented to handle such difficulties based on the decrease of objective function corresponding to second order information. The new strategy takes into consideration both iteration times and kernel cache performance related to the selection of working set in order to improve the efficiency of the kernel cache, which leads to reduction of the number of kernel evaluation of the algorithm as a whole. As a result, the training efficiency of the new method upgrades greatly compared with the older version. On the other hand, the SMO with the new strategy of working set selection is guaranteed to converge to an optimal solution in theory. It is shown in the experiments on the well-known data sets that the proposed method is remarkably faster than the standard SMO. The more complex the kernel is, the higher the dimensional spaces are, and the relatively smaller the cache is, the greater the improvement is.