第6期 王书舟，等：支持向量机的训练算法综述 471· 与样本数呈线性关系.SVMPerf以精度e在时间 因为一次泰勒逼近是逼近函数的下界，则 O(md/(A&2))内求得解.这个界被Shwartz提出 Rp（w）≥max,<a,w>, 的Pegasos方法改进为以精度e,以置信度1-6，在 定义Rp和J的下界为 时间O(1/(A8e)内得到解.Pegasos实质上是执行 R.(w)max a,w>+b, 随机次梯度下降，把解返回并投影到以1/√入半径的 J(w):=A2(w)+R(w). L,球面上 且对所有t≤t构造R,≤R,≤Rmp,J,≤J,≤J,通过 Smola6]针对正则风险最小化问题，提出了一 定义： 种统一框架的全局收敛方法，可以应用于任何导致 w=argmin/(w）,w,=argmin,（w), 凸优化问题的正则风险最小化问题.其基本思想是： Y=J(,）-J(w,）,t=mi(w,）-J(w,) 在正则化函数中，正则项不变，用经验风险的下界， 则可得到如下结论，对所有≤t有如下关系成立： 即经验风险的一次泰勒逼近，代替经验风险，进行最 J(w）≤J,(w:)≤J(w）≤J(w,)=J+(w) 优化求解.Smola指出SVMPerf是这种方法的一个 进而，6，是单调减的且 特例，并给出了更紧的收敛界，即对ε精度，对一般 E:-6+1≥J+1(w41）-J,(w,)≥0. 的凸优化问题在0(1/ε)步内收敛，对连续可微问 另外ε，为到最优点距离的上界： 题在0(1lg(1/ε))步内收敛.这个方法的另一个重 要特点是，它可以自动利用优化问题的光滑性，它的 Y.≥E:≥minsJ(w,）-J(w) 在主空间支持向量机的线性算法可简单描述如 一个改进是无需求解二次规划问题而拥有同样的收 下： 敛速度。 这种方法一个关键技术点是次梯度.次梯度是 初始化：t=0,州o=0,a6=0,b=0,J(w)=入2(w) 凸函数梯度的一个推广，其中凸函数可以是非光滑 While s,≤e 的.假设"是凸函数F的一个函数值有限点，那么 取得最小值w,:=argmin J,(w) 次梯度是在w点F的任何正切支撑超平面的标准 计算次梯度a,+1和偏移量b+1 法向量.确切地被称为F在点的次梯度，当且 t←t+1 仅当 End Yw',F(w')>F(w)+<w'-w,u>, 此外，Smola]还给出了在对偶空间SVM的线 F在一点w的所有次梯度的集合称为F在这点的 性算法，并由经验数据得出结论：在对偶空间执行精 次微分，表示为8F(w).若这个集合非空，那么称F 确的线性搜索，则在主空间的目标函数有更快的收 在”点次可微.若这个集合只有一个元素，称F在 敛速度， w点可微.用x∈X,y∈Y分别表示训练样本的输人 3支持向量机的扩展算法 模式和输出标签，l(x,y,w)是凸损失函数且w∈W, W是再生核希尔伯特空间.对给定的一组观测样本 随着对SVM研究的深入，人们提出了一些SVM x:∈R",y:∈R,i=1,…,l,正则风险最小化函数可表 的扩展算法.这些扩展算法主要是通过增加函数项、 示为 变量或系数等方法使公式变形，产生出有某一方面 优势，或者有一定应用范围的算法，如-SVM646s]】 J(w）=Rp(w)+入2(w), 广义SVM(generalized SVM,CSVM)[s6,最小二乘 R(w):=12105,,m). SVM(least-square SVM,LS-SVM)[63-691.-SVM ma 法中用参数)取代C,v是间隔错误样本的个数所占 2(w)是光滑的凸正则项，入>0是正则系数，：=表 总样本点数的份额的上界，也是支持向量的个数所 示按定义等于， 占总样本点数的份额的下界.参数v对于各种噪声 令"：∈W表示在每次迭代中w的取值，并且令 具有较好的鲁棒性，易于选择，并且可用以控制支持 a,∈W,b.∈R,w0=0,a0=0,bo=0,则Rp[w.]的 向量的数目和误差，广义SVM直接以优化系数和核 泰勒展开系数为 矩阵构造出一个不等式约束的非线性优化问题，其 a+l=anRm（w:）, 对偶形式与标准SVM对偶形式等价.但广义SVM bit Ramp(w:)-<at+l,W:> 并不是直接求解此优化问题或其对偶形式，而是构