第 25 卷 第 6 期 2008 年 6 月 计 算 机 应 用 研 究 Application Research of Computers Vol. 25 No. 6 Jun. 2008 基 于 光 滑 R am p 损 失 函 数 的 健 壮 支 持 向 量 机 ( 1. 临 沂师范 学院 信 息学 院, 山 东 临沂 276005; 2. 电子 科技大 学 计算 机科 学与 工程 学院 , 成都 610054) 孙汪泉 1, 王 磊 2 摘 要: 提 出 一 种 新 型 的 基于 光 滑 Ramp 损 失 函 数 的 健 壮支 持 向 量 机 , 能 够 有效 抑 制 孤 立 点 对 泛 化 性 能 的 影 响, 并采 用 CCCP 将它 的非凸 优化 目标 函数 转换 成连 续、二次 可微 的凸 优化 。在 此 基 础上 , 给 出训 练 健 壮支 持 向 量机 的一 种 Newton 型算 法并 且分析 了算 法的 收敛 性 质 。实 验 结 果 表 明, 提出 的 健 壮 支 持 向 量 机对 孤 立 点 不 敏 感, 在各 种数 据集 上均 获得 了比 传统的 SVMlight 算法 和 Newton-Primal 算 法更 优的 泛化 能力 。 关键 词: 支 持向 量机 ; 光滑 Ramp 损 失函 数; 原 始空 间; 凹 凸过 程 中图 分类 号: TP18 文章 编号 : 1001- 3695( 2008) 06- 1676- 03 文献 标志码 : A Training robust support vector machine with smooth ramp loss SUN Wang-quan1, WANG Lei2 ( 1. School of Information, Linyi Normal University, Linyi Shandong 276005 , China; 2. School of Computer Science & Engineering, University of Science & Technology of China, Chengdu 610054, China) Abstract: This paper proposed a novel robust support vector machines based on the smooth Ramp loss function, which can suppress the influences of outliers on the generalization ability effectively. The concave-convex procedure was utilized to trans- form the associated non-convex optimization into a continuous, twice-differentiable and convex one. Then, a Newton-type algo- rithm was developed to solve optimization of robust support vector machines in the primal space and the convergence analysis was done. Experimental results showed that the proposed approach had superior robustness to outliers and yielded generaliza- tion improvements than the classical SVMlight and Newton-Primal algorithms in synthetic and real data sets. Key words: support vector machines( SVMs) ; smooth Ramp loss; primal space; concave-convex procedure( CCCP) 支持向量机是现代机器学习理论的最新研究进展之一, 具 有泛化能力强、维数不敏 感等特 点, 已 经在模 式识别 和回归 分 析等领域表现 出优 异 的性 能 [ 1] 。迄 今为 止, 理 论界 已经 针 对 SVMs 的对偶优化和 原 始优 化问 题 提出 了多 种 有效 的求 解 方 法, 如 SVMlight 算法 [ 2] 和 Newton-Primal 算法 [ 3] 等。然而, 软间 隔 SVMs 对训练样本中的孤立点非常敏感, 本质原因是采用 L1 损失函数时孤立点所产生的 间隔损 失最大, 从而 在确定 SVMs 的决策超平面位置时所起 到的作 用也最 大。因此, SVMs 的 泛 化性能 必 然 受 到 它 们 的 影 响 而 降 低。 近 年 来, 更 为 健 壮 的 Ramp 损失函数受到了广泛的 研究 [ 4, 5] 。该函 数明确 限制孤 立 点所能造成的最大损失, 直接抑 制它们 对决策 超平面 的影响。 但是, Ramp 损失函数同时也导致了优化目标的非凸性, 使得大 多数传统的凸优化方法不能直接用于求解 SVMs[ 6] 。 1 健壮支持向量机 考虑典型的二分类问题: 训练样本集为{ xi, yi } n i = 1, 且 xi ∈ d 和 yi∈{ + 1, - 1 } 。 SVMs 在 原始空 间中 优化 问题 通常 表 瓗 示为如下形式 [ 1] : J( w, b) = 1 /2 ‖w‖ 2 + C n  H1( yi f( xi) ) i =1 min w, b ( 1) 优化式 ( 1) 中 采 用 了 传 统 Hinge 损 失 函 数 ( 图 1) , 即 H1( z) = max( 0, 1 - z) 。但是从图 1 可看出, Hinge 损 失函数 对 孤立点( z< < 1) 所产 生的 损失 没有 任何 上界 限制, 导 致孤 立 点对 SVMs 的解的影响 最大并 且使 得决 策超 平面 的位 置更 靠 近实验结果。因此, SVMs 的泛化性能受到孤立点样本的严重 影响。 HR(z) huR H (z) 1 0.5 0 2 1 0 -1 hu1 H (z) H0(z) 1 0 -1 -2 z z 1 1 1.5 B2 0 B3 -0.5 -0.5 B2 0 (c) 分解 2 H1(z) 0 0.5 -0.5 z (b) 分解 员 hu0 H (z) B1 USV NSV B1 USV NSV B3 1.5 0.5 1.5 0.5 1 -0.5 -0.5 (a) 光滑 砸amp 损失函数 图 1 光滑砸amp 损失函数可以分解成两个 Huber 损失函数之和 相反, 图 1 ( a) 所 示 的 Ramp 损 失 函 数 具 有 更 好 的 健 壮 性 [ 4, 5] , 即 HR( z) = min( 1, H1 ( z) ) 。它明确限制 孤立点样本 所 能引起的 最大 损 失, 直 接 限制 它 们 对 SVMs 的 解 的影 响。 然 而, Ramp 损失函数既不具有二次可微性也不是凸函数, 传统的 Newton 下降等凸优化方法不能直 接对其 进行求 解。本节首 先 提出 一种新 的光滑 Ramp 损失 函数, 具有 二次可 微的性 质; 然 后利用 CCCP 过程解决了该函数带来的非凸性。 f( x) 是 SVMs 的 决 策 函 数, 即 f( x) = w ×Φ( x) + b。 Ω 中的 像, 并且 再生 核映 射 关 Ω 由 核函 数 k( xi , xj) = Φ( xi ) ×Φ( xj) 惟 在特征空间 瓗 瓗 →瓗 其中: Φ( x i) 是样本 x i d 系 Φ( ·) 一确定。 : 1. 1 光滑 Ramp 损失函数 从图 1 可 知, Ramp 函数 可以写 成两个 Hinge 损失 函数 之 和, 即 HR( z) = H1( z) + H- 0 ( z) 。借鉴文 献[ 3] 中的方 法, 本 文 采 用两个连续可微的 Huber 损失函数分别对 Hinge 函数 H1( z) 收 稿日期 : 2007- 03- 05; 修 回日期 : 2007- 06- 12 作 者简介 : 孙汪泉 ( 1976- ) , 男, 山东 诸城人 , 讲师, 主要 研 究 方向 为 数 据 挖掘 、网 络 数据 库 等 ( cigarl@ 21cn. com) ; 王 磊( 1978- ) , 男, 河 南信 阳 人, 博士, 主要 研究 方向为 模式 识别、人工 智能 等. 

第 6 期 孙汪 泉, 等: 基于 光滑 Ramp 损 失函 数的 健壮 支持向 量机 ·7761· 和 H- 0 ( z) 进行逼近, 如下: Hhu 1 ( z) = { 0 ( 1 + h - z) 2 /( 4 h) 1 - z 0 - ( h - z) 2 /( 4h) z { if |1 - z|≤h if z > 1 + h if z < 1 - h if z > h if |z|≤h if z < - h Hhu 0 ( z) = ( 2) ( 3) 其中: h 是 可 选 参 数, 取 值 为 h ∈ [ 0. 01, 0. 5] 。 显 然, 当 h→0 时, Huber 损失函数 与 Hinge 损 失完 全 一致, 但 前者 具 有 二次可微的性质。 这样, 定 义 光 滑 Ramp 损 失 函 数 为 Hhu 1 ( z) + Hhu 0 ( z) , 它同样具有连续和 二次可 微的性 质( 如图 1( a) ) 。将 Hhu R ( z) 代替优 化问 题式 ( 1) 中 的 Hinge 损失, 得 到 SVMs 在 原 始空间中的新优化目标函数 JR( w, b) , 称为健壮支持向量机。 R ( z) = Hhu JR( w, b) = 1 /2‖ w‖ 2 + C min w, b n  i =1 Hhu 1 ( y i f( xi ) ) + n  C i =1 1. 2 CCCP 解决非凸优化 Hhu 0 ( yi f( x i) ) ( 4) n  由式( 4) 中的目标函数中存在非凸项, 即 JR c av( w, b) = C i =1 Hhu 0 ( yi f( xi) ) , 直 接 采 用 凸 优 化方 法 对 其 求 解 存 在 困难。 因 此, 采用 CCCP 将式 ( 4) 中 的 非凸 优化 转 换成 凸优 化 问题 [ 7] 。 简单起见, 此后的推导过程中暂时不考虑偏置 b 的影 响。 根据 CCCP 求解非凸优化的基本准则, 健壮 支持向 量机的 最优解 可 以依据如下规则迭代的更新优化变量 w 得到, 即 c av ( wt) ×w) vex ( w) + JR′ wt +1 = arg min ( JR ( 5) w 其中: JR vex( w) 是优 化 式( 4) 的凸 项, 即 JR 1 ( y i f( x i) ) ; JR′ vex( w) = ‖ W‖ 2 /2 + cav( wt) 是非凸项 对于 优化 变量 w 的一 阶 Hhu n C 6 i =1 导数, 如下: JR cav ′( wt) = JR cav ( wt) / w = n  i =1 [ JR cav ( wt) / f( xi ) ] ×[ f( x i) / w] = cav( wt ) / f( x i) ] ×Φ( xi ) ( 6) 这里, wt 是前一次迭代获得的 w 的最优解。令 n  [ JR i= 1 { ηt i =yi [ JR c av ( wt ) / f( xi ) ] = C yi f t( xi) < - h C( h - yi f t( xi) ) /( 2h) |yi f t( xi ) |≤h 0 yi f t ( xi) > h f t ( xi) = wt ×Φ( xi) 则结合式( 5) 和( 6) 容易 推知, 在 CCCP 的每 个迭 代步中 只 需 要最小化如下的优化问题: JR C( w) = JR vex( w) + ( n  i =1 ηt i yiΦ( x i) ) w = JR vex ( w) + n  i =1 ηt iy if( x i) ( 7) n  vex( w) 和 其中: JR 析, 式( 7) 是连续且二次可微的凸优化。 ηt i =1 iy if( xi) 都是 凸 函数。因 此 根据 前面 的 分 2 原始空间中训练健壮支持向量机 接下来定义原始空间中的支 持向量。令 ft ( x) 表 示 CCCP 的第 t 个迭代获得的健壮 SVMs 的决策函数。根据 z = yi ft ( x i) 的值将训练样本分成如下五类: 定义满足 式 |z - 1 |≤ h 的样 本 为非边界支持向量 ( USV) 且令 它们 的数 目为 nu; 定 义满 足 式 z < 1 - h的样本为边界支持向量( BSV) , 并根据不等式 h < z < 1 - h, |z|≤h 和 z < - h 将它们进一 步分成 B1、B2 和 B3 三个子 类, 数目分别为 nb1, nb2 和 nb3 ; 最后, 定义 剩余 的 满足 z > 1 - h 的样本为非支持向量( NSV) , 数目为 nn。 为了方便分析, 将 五类 样 本按 照 USV、B1、B2、B3 和 NSV 的 顺序重新组织, 并调整相应的核矩阵 K 和类标记向量 Y。然 后, 令 I 0, I 1 , I 2和 I 3 均是规模为 n ×n 的对角矩阵。其中: I 0 的 前 nu 个对角元素为 1 且剩 余元素 为 0; I 1( I 2 和 I 3) 仅 有中 间 的 nb1 ( nb2和 nb3) 个对角元素为 1, 分别对应着 B1( B2 和 B3) 区 域中的样本。这样, 计算优化问题式( 8) 的梯度为  t = K β+ C( KI 0 ( Kβ- ( 1 + h) Y) /2h - K ( I 1 + I 2 + I 3) Y ) + CK( I 3 + A t) Y ( 9 ) 其中: A t 是规模为 n ×n 的对角 矩阵, 它的 前 nu + nb1 个对角 元 素为 0, 接着 的 nb2 个元 素对 应 于 B2 区域 中 的样 本 且取 值 为 ( h - yi ft ( Xi ) ) /2h, 最后剩余对角元素为 0。 同样, 可以求解优化式( 8) 的 Hessian 矩阵为 H t = K + CKI 0 K /2h。可以验证对于 任意 向量 β∈瓗 n 不 等式 BTH t β> 0 成 立, 即 JR c ( β) 是正定二次函数。因此, 若给定 K, Y 和 A t, 式( 8) 的最优解 βt +1 可以通过 Newton 下降法一次性求解得到 βt +1 = βt - ( H t) - 1 ( I + CI 0K / ( 2 h) ) - 1( C( 1 + h) /( 2h) t =  I 0 + C( I1 + I2 - A t) ) Y =     ( 2h/CI u + K u, u) - 1( ( 1 + h) Yu - b2) Yb2) ) C( Ku, b1Yb1 + Ku, b2( Ib2 - At C ×Yb1 C ×( Ib2 - A t 0 0 b2) Yb2     βt + 1 u βt + 1 b1 βt + 1 b2 0 0 =         ( 10 ) 其中: 下标 u, b1 和 b2 分 别表 示相 应的 子矩 阵或 者向 量 分量。 例如, Ku, b1是 K 的规模为 nu ×nb1 的子 矩阵并 且包含 了 K 中 的 行和列分别对应于 USV 和 B1 区域( 图 1) 的所 有元素。再如, Y b2 是向量 Y 的分量, 由所有位于 B2 区域的训练样本的类标记 组成。 当确定最优解 βt +1后, 可以 得到 健壮 SVMs 在 第 t 个迭 代 步时的决策函数, 如下: n  i =1 βt +1 i ft( x) = wt +1 ×Φ( x) = k( x i, x) 由式( 10) 知, 由于最 优解 βt +1 的分量 βt +1 n 均为 0 向量, 位于 B3 和 USV 区域的样 本对式 ( 8) 的 决策函 数没有 任 何影响。因此, 鉴于 大 多数 孤立 点 样本 都 存在 于 B3 区域, 健 壮 SVMs 在求解过程中保持了对孤立点 的不敏感性, 从而可 以 获得更优的泛化能力。 b3 和 βt+ 1 ( 11 ) 由著名的 representer 定 理 [ 8] , 优化 式 ( 7) 的 最 优 解 w* 在 再生核映射函 数空 间( RKHS) 中可 以由 训练样 本的 像的 线 性 组合表示。因此, 采用与文献[ 3] 中类似的做法, 将优化式 ( 7) 依据 CCCP 求解健壮支持向量机优化问题的特 点, 每个 迭 代步只需要重复地按式( 10) 求解 βt + 1, 直到它收敛。 综上分析, 本文设计了如下的训练算法用于求解健壮支持 n  的解表示为 w = βi ×Φ( xi) 。其中系数 βi 是 RKHS 函数空间 中基向量的权重。将 w 的 表达 式带 入式 ( 7) 并结 合核 再生 性 质, 得到如下的以 β为变量的新优化问题。 i = 1  C( β) = 1 /2βTK β+ C JR n i =1 min β Hhu 1 ( yiKT i β) + n  i =1 i yiKT ηt i β ( 8) 其中: K 是元素为 Ki, j = k( xi, x j) = Φ( xi ) Φ( xj ) 的 核矩 阵; Ki 是核矩阵的第 i 列。 向量机。 算法 1 N-RSVM 输 入: 训练 样本 集 S = { 0。 x i, yi} n i = 1, 核矩阵 K 和 任意 小的正 实数 ν> a) 初 始化: 令 t = 0。 利用 SVMlight算法 在 S 的一个 子集 上训练 初始 的 SVMs 分 类器 f 0 ( x) , 并依 据 yi f 0 ( xi) 的值 将训 练样本 分成 五类。 b) 令 t = t + 1。重 新按 USV、B1、B2、B3、NSV 的顺 序 组织 五 类训 练 样 本, 并且 相应地 调整 核矩阵 K 和 类标 记 向 量 Y 。 重新 计 算 对 角矩 阵 

·8761· At 的值。 c) 依 据式( 10) 计 算 βt +1, 并由 式( 11) 得到 决策函 数。 d) 按式 ( 9) 求解梯度  若其满足‖  t‖ ≤ ν则 算 法停 止 ; 否 则, t, 依据 y ift ( xi) 的 值将样 本重新 分割 成五类 , 然后返 回到步 骤 b) 。 由于该算法在形式上与 Newton 下降法的过程一致, 将它称为 N-RSVM 算法。最后, 将讨论 N-RSVM 算法的收敛性质。 vex( β) 和 JR 设 JR( β) 是以变量 β表示的 健壮支 持向 量机 的优 化目 标 函数, JR cav( β) 分 别是 它 的 凸项 和 非 凸项。 此时, 若 βt + 1是 N-RSVM 算法的第七次迭 代时 式( 8) 的 最优 解, 则依 据 最优解的性质和非凸函数的性质, 容易验证下面的两个不等式 成立。 n i yi KT ηt  vex ( βt +1) + JR i = 1 c av( βt ) ≤ JR′ cav ( βt +1 - JR JR  i βt +1 - i yiKT ηt n i =1 n  i =1 iy iKT ηt i βt n  i βt + 1≤JR vex ( βt) + iyi KT ηt cav( βt ) ×( βt+ 1 - βt ) = i =1 i βt ( 12) ( 13) 合并上述两式可以得到 JR( βt +1) ≤JR( βt ) , 即 N-RSVM 算 法能够单调地 降低健 壮支持 向量机 的优化 目标值。根据 文献 [ 7] 中的定理 2, CCCP 通常是收敛到优 化目标的某个局 部最小 值。然而, 上述算法步骤 a) 中采用 SVMlight 算法低开销地获得 了一个靠近全局最优的解作为 N-RSVM 算法的初始解, 使得它 常常能够收敛健壮支持向量机的全局最小值。下面的实验结果 也说明了 N-RSVM 算法能够获得优异的泛化性能。 3 实验与分析 本章在多个数据集上对提 出的健 壮支持 向量机 方法的 性 能进行评价, 并与用于 训练 传统 支持 向量 机的 SVMlight算 法 [ 2] 以及 Newton-Primal 算法 [ 3] 的实验结果进行比较。 3. 1 基于合成数据集的实验 采用两个二元高斯分布合成 Gauss 数据集( 每类样本 对应 一个高斯分布) , 中心和协方差矩阵分 别为 μ= ( - 4, 0) , ∑ = ( 9 4 4 9 和 - μ, ∑。训练集包含 50 个样 本, 并 在每类 中随机 改 ( 变三个样本的类 标记 以便 模拟 孤立 点( 图 2 中的 圆圈 标志 ) 。 测试集包含 200 个样本, 每类各 100 个。 首先在 Gauss 数据集上 分别 采用上 述算 法训 练线 性分 类 器( 核函数为 k( xi, xj) = x T i ×xj) 。图 2 比较了它们训练产生的 决策超 平面的 位置。 显然, Newton-Primal 算 法和 SVMlight算 法 对孤立点比较敏感, 产生 的决策 超平面 明显地 更加靠 近它们。 相反, N-RSVM 算法 对孤立 点保持 了良好 的健壮 性, 得到的 测 试精度达到 94. 5% ( 相比于前两种算法的 89. 5% 和 91. 0% ) 。 接着考察了非线性核函数的情况( 采用 RBF 核) 。训练参 数采用 5-fold 交叉验 证方法 选取, 即 C = 50 和 σ= 6. 0。实 验 重复 20 次, 每次均由高斯分布产生规模为 50 和 200 的训 练集 和测 试 集。实 验 结 果 得 到 Newton-Primal、SVMlight 和 N-RSVM 算法的平均测试精度分别为 93. 7% 、94. 1% 和 95. 8% 。 可见, 基于合成数据集 的实验 结果表 明, 本 文提出 的健 壮 支持 向 量 机 方 法 对 孤 立 点 样 本 不 敏 感, 获 得 了 显 著 优 于 SVMlight和 Newton-Primal 的泛化性能。 3. 2 基于 UCI数据集的实验 本文在 10 个 UCI 数据集上进一步验证健壮支持向量机的 性能。这些数据集的共同特征是存在明显的类别重叠, 使得固 有的 Bayes 误差率较高。对于 每个数据集, 采用 bootstrap 技 术 生成 10 个训练集, 并由 5-fold 交叉验证方法选取 参数 C 和 σ。 表 1 比较了上述三种算法在这些数据集上的平均测试精度。 计 算 机 应 用 研 究 第 25 卷 实验结果( 图 2) 表明, 绝大多数情况下 ( mushroom 除外 ) , N-RSVM 算法均获得了 最低的 泛化 误差 率且 产生 的支 持向 量 数目最少。其中在 sonar 和 tic 数据集上, SVMlight训练算法获得 的平均分类误差率分别 为 18. 17% 和 14. 75% , 而 本文 算法 显 著地将它们降低到 14. 74% 和 12. 46% 。 N-RSVM SVMlight Newton-Primal 10 5 0 -5 -10 10 -10 图圆 训练后的决策超平面的位置 0 表员 晕-RSVM,Newton-Primal (NP)和SVMlight 算法的性能比较 测试误差渊伊100%) Datasets N-RSVM NP SVMlight sonar 14.74 18.10 18.177.64 glass 7.6521.82 7.78 pima 22.68 22.43 ticgerman 12.46 15.41 14.75 23.10 24.07 23.495.355.940.009.72 sickwaveform 5.215.840.359.0714.95 5.396.030.58 mushroom splice 10.14 adult20 15.12 15.13 注院adult20 为随机选取了约 圆园豫的 adult 数据集的原始训练样本遥 -5 5 渊Gauss 数据集袁C=50) 实际上, 上述 UCI 数据集中由于普遍存在类别 重叠, 因 而 固有地包含一些误分类样本( 图 1 中的 z≤1 的样本) , 任何 分 类算法都不能将它们完全 正确地 分类。鉴于 许多误 分类样 本 存在于图 1 中的 B3 区域, 它们 对决策 超平面 具有同 孤立点 类 似的负面 影 响。 这 样, 由 于 Hinge 损 失 对 孤 立 点 敏 感, 使 得 Newton-Primal 和 SVMlight算 法的 泛化 误差 率较 高。 相反, 本 文 提出的健壮支持向量 机方 法采 用了 不敏 感的 光滑 Ramp 损 失 函数, 能够抑制孤立点对决 策超平 面的影 响, 因而获 得了更 低 的泛化误差率。 4 结束语 本文提出一种光 滑 Ramp 损失 函数, 并 将其 应 用到 SVMs 的原始优化问题, 得到了新型的对孤立点样本的不敏感的健壮 支持向量机; 通过 CCCP 过 程 [ 7] 克 服新优 化目 标的 非凸 性, 获 得它的连续、二次可微的凸优化形式; 给出一种 Newton 型算 法 对其进行求解并且分析了 算法的 收敛性 质。 基于多 个数据 集 的实验结果表明, 提出的健壮支持向量机方法对孤立点样本不 敏感并且获得了更优的泛化性能。 参考文献: [ 1] APNIK V N. 统 计学习 理论 的本质 [ M] . 张学 工, 译. 北京: 清 华 [ 2 ] 大学出 版社 , 2000 . JOACHIMS T. Making large-scale SVM learning practical [ C ] / / SCHOLKOPF B, BURGES C, SMOLA A. Advances in Kernel Methods: Support Vector Learning. Cambridge: MIT Press, 1999: 169-184. [ 3] CHAPELLE A. Training a support vector machine in the primal, TR- 147[ R] . [ S. l. ] : Max Planck Institute, 2006. [ 4 ] KRAUSE N, SINGER Y. Leveraging the margin more carefully [ C] / / Proc of the 21st International Conference on Machine Lear- ning. New York: ACM Press, 2004. [ 5] MASON L, BARTLETT P L, BAXTER J. Improved generalization through explicit optimization of margins [ J] . Ma chine Learning , 2000, 38 ( 3) : 243- 255 . [ 6] XU L, CRAMMER K, SCHUURMANS D. Robust support vector ma- chine training via convex outlier ablation[ C] / / Proc of the 21st Na- tional Conference on Artificial Intelligence. Boston: [ s. n. ] , 2006. YUILLE A L, RANGARAJAN A. The concave-convex procedure ( CCCP) [ J] . Neural Comput ation , 2003, 1 5( 4) : 915- 936. [ 7 ] [ 8] KIMELDORF G S, WAHBA A. A correspondence between Bayesian estimation on stochastic processes and smoothing by splines[ J] . An- nals of Mathem atical S tatistics, 1970, 4 1( 5 ) : 495- 502.