·468. 智能系统学报 第3卷 的缘故. 代方式逐步排除非支持向量.块算法将矩阵的规模 类似用于模式分类的SVM,回归SVM(support 从训练样本数的平方减少到具有非零Lagrange乘 vector regression,SVR)的基本思想是，通过非线性 子的样本数的平方，从而降低了训练过程对存储容 变换中(·)，将输人空间映射到一个高维特征空 量的要求 间，并在这个特征空间用线性函数f(x)= Osuna等人提出的分解算法(decomposition al- w中(x)+b拟合样本数据，同时保证能得到较好的 gorithm)21,是目前有效解决大规模问题的主要方 泛化能力.设x:∈R,y:∈R,i=1,…,l,l为观测样 法.分解算法将二次规划问题分解成一系列规模较 本，R"代表输人空间，SVR问题可以表示为线性约 小的二次规划子问题，进行迭代求解.在每次迭代 束二次规划的优化问题： 中，选取拉格朗日乘子分量的一个子集做为工作集， m吃11+号容+g1, 利用传统优化算法求解一个二次规划的子问题. Joachims在上述分解算法的基础上做了几点重要改 r（(w·)+b)-y≤6+6， (1) 进.第一，采用类似Zoutendijk可行方向法的策略确 8.t.{y:-(w·)+b)≤e+g, 定工作集B,即求解一个线性规划问题，得到可行 5,5≥0. 下降方向，把该方向中的非零分量作为本次迭代的 其中C>0是函数复杂度和损失误差之间的一个平 工作集，该线性规划存在高效算法，其核心是一个排 衡量.由优化问题(1)的Lagrange函数相对于变量 序问题.第二，提出shrinking方法，估计出有界支持 、b5、5:的偏导数为0，可得优化问题(1)的对偶 向量和非支持向量，有效地减小QP问题的规模.最 问题： 后，利用KernelCache来减少矩阵中元素的计算次 数.Joachims利用这些方法实现的SVMlight,.是目前 min 设计SVM分类器的重要软件， 且x(a-a Lin7]和Takahashi9等人分析并证明了分解 (a +ai) (2) 算法的收敛性.Lino]对-SVM和多类SVM的停 机准则进行了分析，并针对多类SVM证明了分解算 8.t. a,-)=0, 法的渐进收敛性.Hu得到了鲁棒SVM的KKT条 0≤a,a≤l,i=1,…,1. 件和分解算法，利用预选取技术提高分解算法的收 这个约束最优化问题的解是核函数的线性组合，具 敛速度.Dong2]引进并行优化算法来快速剔除非支 有如下的形式： 持向量，用对角块矩阵逼近原核矩阵，从而原始问题 分解为易于求解的子问题.Qiao131提出一种工作集 )=召(a,-a)K)+b (3) 选择规则，使分解算法具有多项式收敛的性质。 这个用作函数回归的学习机器就是支持向量 块算法的目标是找出所有的支持向量，因而最 机，支持向量就是使表达式(3)中系数(a:-a:)不 终需要存储相应的核函数矩阵，对于支持向量数很 为零的训练样本，在使用SVM解决实际问题时，首 大的问题，块算法十分复杂，与块算法不同，分解算 先需要把它转化为一个可以用SVM求解的数学模 法的目的不是找出所有的支持向量，而是每次只针 型，这一工作称为模型选择，它包括训练集的选择、 对很小的训练子集来求解，即使支持向量的个数超 SVM类型的选择、核函数的选择、SVM中自由参数 过工作集的大小，也不改变工作集的规模.各种分解 的选择等.对已经进行了模型选择的最优化问题 算法的区别在于工作集的大小和工作集生成原则的 (1)或(2)，其求解方法就是SVM的训练算法. 不同.工作集的选择对于分解算法的收敛与否和收 敛速度至关重要，因此开发新的工作集选择算法是 2支持向量机的基本算法 提高分解算法性能的重要途径， 2.1块算法与分解算法 除了分解算法，还有Huber近似算法[4、多拉 块算法(chunking algorithm)[21最早是由Boser 格朗日乘子协同优化算法1s]、剪枝算法「16等SVM 等人提出来的.它的出发点是，删除矩阵中对应于 的求解方法. Lagrange乘子为零的行和列不会对最终结果产生影 2.2序贯最小优化算法 响.对于给定的样本，块算法的目标就是通过某种迭 由Platt提出的序列最小优化(sequential mini-