第3卷第6期 智能系统学报 Vol.3 No.6 2008年12月 CAAI Transactions on Intelligent Systems Dec.2008 支持向量机的训练算法综述 王书舟，伞冶 (哈尔滨工业大学控制与仿真中心，黑龙江哈尔滨150001) 摘要：支持向量机(SVM)是在统计学习理论基础上发展起来的新方法，其训练算法本质上是一个二次规划的求解 问题.首先简要概述了SVM的基本原理，然后对SVM训练算法的国内外研究现状进行综述，重点分析SVM的缩减 算法和具有线性收敛性质的算法，对这些算法的性能进行比较，并且对SVM的扩展算法也进行简单介绍.最后对该 领域存在的问题和发展趋势进行了展望， 关键词：统计学习理论；支持向量机；训练算法 中图分类号：TP391.9文献标识码：A文章编号：1673-4785(2008)06046709 A survey on training algorithms for support vector machine WANG Shu-zhou,SAN Ye (Control Simulation Centre,Harbin Institute of Technology,Harbin 150001,China) Abstract:Support vector machines (SVMs)use new methods that originated in statistical learning theory.Training of an SVM can be formulated as a quadratic programming problem.The principles of SVM have been summarized briefly in this paper.The latest developments in SVM training algorithms in domestic and overseas research were re- viewed,especially reduction algorithms and algorithms with linear convergence properties.The performance of these algorithms was then compared,and a brief introduction to a proposed extension of them was given.Finally some problems and potential directions for future research are discussed. Keywords:statistical learning theory;support vector machine;training algorithms 支持向量机(support vector machine,.SVM)是近对SVM本身的特点提出了许多算法，本文对这些算 年发展起来的一种通用机器学习新方法.它不但具 法进行综述，包括块算法、分解算法、序贯最小优化 有坚实的理论基础、简洁的数学形式、直观的几何解 算法、增量与在线训练算法、缩减算法、具有线性收 释，而且能够较好地解决小样本、非线性、维数灾和 敛性质的算法，以及SVM的扩展算法. 局部极小等问题12，因此在模式分类[34)、回归问 题56等很多领域得到了广泛的应用。 1支持向量机 训练SVM的算法归结为求解一个受约束的凸 SVM最初是在模式分类中提出的，其基本思想 二次优化问题.对于小规模的二次优化问题，利用牛 是：通过非线性变换中(·)将输入空间映射到一个 顿法、内点法等成熟的经典最优化算法就可以很好 高维特征空间，在这个特征空间中求取最大间隔分 地求解.但这些算法通常需要利用整个Hessian矩 类超平面f(x)=w中(x)+b,其中w、b分别是这个 阵，内存占用过多，从而导致训练时间过长.当训练 超平面的权值和阈值.特征空间的维数可能是非常 集很大，特别是支持向量数目也很大时，求解二次优 高的，通常导致计算非常复杂.SVM算法通过核函 化问题的经典方法不再可行.因此设计适用于大量 数K(x,y)巧妙地解决了这个问题.SVM不直接计算 样本的训练算法成为SVM研究的重要内容.目前针 复杂的非线性变换中(·)，而是计算非线性变换 收稿日期：2008-06-30. 中(·)的内积K(r,y),即核函数K(x,y)=中(x)· 基金项目：国家自然科学基金资助项目(60474069) 中(y）,从而大大简化了计算.核函数K(x,y)的利用 通信作者：王书舟.E-mail:seek2000@163.com, 是由于在原空间和高维特征空间只用到了内积运算