Successive overrelaxation for support vector machines
Successive overrelaxation for support vector machines
复制标题
DOI：
10.1109/72.788643
复制
发表时间：
1999-09-01
影响因子：
--
通讯作者：
Musicant, DR
中科院分区：
文献类型：
--
作者：
Mangasarian, OL;Musicant, DR
用对称线性互补问题和二次规划的逐次超松弛算法训练支持向量机，用于区分两个海量数据集的元素，每个数据集有数百万个点。由于SOR在一个Lime中处理一个点，类似于Platt的一次处理两个约束的顺序最小优化(SMO)算法和Joachims的SVMlight一次处理少量的点，因此SOB可以处理不需要驻留在内存中的非常大的数据集，该算法线性收敛到一个解。在多达10 000 000个点的数据集上给出了令人鼓舞的数值结果。这种大规模的判别问题不能用传统的线性或二次规划方法处理，而且据我们所知，其他方法也没有解决过。在较小的问题上，SOB比SVMlight快，与SMO相当或更快。
Successive overrelaxation (SOR) for symmetric linear complementarity problems and quadratic programs is used to train a support vector machine (SVM) for discriminating between the elements of two massive datasets, each with millions of points. Because SOR handles one point at a Lime, similar to Platt's sequential minimal optimization (SMO) algorithm which handles two constraints at a time and Joachims' SVMlight which handles a small number of points at a time, SOB can process very large datasets that need not reside in memory, The algorithm converges linearly to a solution. Encouraging numerical results are presented on datasets with up to 10 000 000 points. Such massive discrimination problems cannot be processed by conventional linear or quadratic programming methods, and to our knowledge have not been solved by other methods. On smaller problems, SOB was faster than SVMlight and comparable or faster than SMO.