Using Analytic QP and Sparseness to Speed Training of Support Vector Machines
Using Analytic QP and Sparseness to Speed Training of Support Vector Machines
复制标题
DOI：
--
复制
发表时间：
1998-12
期刊：
影响因子：
--
通讯作者：
John C. Platt
中科院分区：
文献类型：
--
作者：
John C. Platt
训练支持向量机 (SVM) 需要解决非常大的二次规划 (QP) 问题。本文提出了一种训练 SVM 的算法：顺序最小优化 (SMO)。 SMO 将大型 QP 问题分解为一系列可分析解决的最小可能 QP 问题。因此，SMO 不需要数值 QP 库。 SMO 的计算时间主要由内核的评估决定，因此内核优化大大加快了 SMO 的速度。对于MNIST数据库，SMO的速度是PCG分块的1.7倍；而对于UCI Adult数据库和线性SVM，SMO可以比PCG分块算法快1500倍。
Training a Support Vector Machine (SVM) requires the solution of a very large quadratic programming (QP) problem. This paper proposes an algorithm for training SVMs: Sequential Minimal Optimization, or SMO. SMO breaks the large QP problem into a series of smallest possible QP problems which are analytically solvable. Thus, SMO does not require a numerical QP library. SMO's computation time is dominated by evaluation of the kernel, hence kernel optimizations substantially quicken SMO. For the MNIST database, SMO is 1.7 times as fast as PCG chunking; while for the UCI Adult database and linear SVMs, SMO can be 1500 times faster than the PCG chunking algorithm.