Vol.28 No.1 封筠等：一种SVM分类器自动摸型选择方法 89* 模型选择的评价标准提供了问题解决的原 心，利用所定义的模式确定搜索的方向.对于R2 则，通常可用泛化误差(GE)表示分类器推广能 核参数空间，所采用的模式如图1所示，对应的模 力.能够作为评价准则的数量指标主要分为两大 式矩阵为： 类：一类来自实际数据的实验验证结果；一类来自 「1 10-1-1-101 01 理论分析所给出的界，实验验证准则的获得完全 Px= 1110-1-1-10J 依赖于经验数据，该类方法将所得训练样本的部 (8) 分作为验证数据用来评估泛化性能，主要包括K- (0.1) 折交叉验证(K-fold cross-validation)误差估计、 (-1.1)● 4模式中心0.0)●(1.) 留一(Leaveone--oul,简称LOO)误差估计.理论 分析的目的就是要寻求与期望GE最紧的界，因 (-1.0)● ●1.0) 45 为I()()误差估计被认为是对(GE的近似无偏估 计，所以也经常采用通过理论分析所获得的LOO (1.-1) ●(1，-1) (0.-1) 误差上界作为模型选择的评价标准。 图1R2核参数空间对应的模式 由于实验验证准则的计算代价很高，所以本 Fig.1 Pattern for an R2 kernel parameter space 文采用了种经过理论推导获得的LOO误差上 界估计，即Jaakkola-Haussler误差上界s).针对 模式矩阵的每一列确定了以模式中心为起点的下 L2范数非线性软间隔SVM分类器，其LO)误 一个搜索计算参数点的位置，通过模式搜索步长 差满足下式： △P取值的不同，可以实现以模式中心为圆心的 Rio(T).I1 360°范围搜索.参数变化量可由下式计算得到： n sgn(-yif(x;)+a;K(x,,x)) S=APPK (9) (6) 上式的右边项被称为Jaakkola-Haussler误差上 对于R2核参数空间，其中△” 界.对高斯核函数.式(6)可写成 模式搜索算法描述如下： Rw(r)≤1 n sgn(-y,f(x,)+a)(7) Step1确定初始的模式中心为粗网格搜索 显然，在计算Jaakkola-Haussler误差上界时只需 所得到的优化参数点，给定对数参数搜索步长AP 要利用所有训练样本做一次分类器训练，获得分 及足够小的允许步长ε； 类决策函数f(x),因此与经验验证方法相比较， Step2根据式(9)计算对数参数的变化量 计算Jaakkola-Haussler误差上界所花费的代价要 s,然后依次求得当前模式中心的各邻域参数点 小很多 的Jaakkola-Haussler误差上界，并将其中使得该 评价准则最小的参数点置为新的模式中心； 2搜索策略 Step3若模式中心不变，则减小搜索步长 在确定了模型选择的准则后，需要设计一种 AP并转到Step2重新寻找新的模式中心； 能寻找到使得该准则全局最优的模型参数点的搜 Step4重复执行Step2与Step3,直到AP 索方法.本文提出了一种粗网格与模式搜索相结 小于允许步长ε为止，最终确定的模式中心即为 合的优化策略，该算法先执行粗网格搜索寻找全 最优参数点 局优化区域，再利用模式搜索寻找在该优化区域 3基于黎曼几何的核函数修正 的最优点 2.1粗网格搜索 3.1核函数的几何特性 该搜索算法首先在参数空间定义统一的网 Burges在文献[6]中讨论了基于核函数的非 格.研究发现在优化核参数时采用对数坐标是比 线性支持向量机的几何问题，认为非线性映射P 较合理的2.然后计算所有网格点的Jaakkola- 是一个曲子流形，它定义了从输入空间I到特征 Haussler误差上.界，寻找全局最小区域，网格的粒 空间F(再生核Hilbert空间)的一个嵌入， 度决定了解的质量与搜索效率 定理1在特征空间中，黎曼度规与核函数 2.2模式搜索 之间满足如下关系式： 该搜索算法将当前优化参数点置为模式中V o l . 2 8 N ` ) . 1 封鸽等 : 一种 s v M 分类器 自动模型选择方法 模 型选 择 的评 价 标 准提 供 了 问题 解 决 的原 则 , 通常可 用泛 化误 差 ( G E )表 示分 类 器推 广能 力 . 能够作 为评 价准则 的数 量 指标 主要分 为两大 类 : 一类来 自实际数据的 实验 验证结果 ; 一类来 自 理论 分析所给 出的界 实验 验证 准则 的获 得完 全 依赖于 经验 数据 , 该 类方 法 将所 得训 练样 本 的部 分作 为验证数据用 来 评估泛 化性 能 , 主要 包括 K - 折交 叉 验 证 ( K 一 f o ld C or s S 一 v a lid a t i o n ) 误 差估 计 、 留一 ( L e a v e 一。 n 〔 、 一 。 ut , 简称 L O( ) 误 差估计 . 理论 分析 的 目的就 是要 寻 求与期望 G E 最 紧的 界 . 因 为 L ( )O 误差 估计 被 认为 是 对 G E 的 近似 无 偏估 计 , 所 以 也经常 采用通过理 论分 析所 获得 的 L O O 误差 上 界作 为模型选 择 的评 价标准 . 由于实验验 证 准 则的 计算代 价 很 高 , 所 以 本 文采用 J ’ 一 种经过 理 论推 导获 得 的 L O O 误 差 上 界估 计 , 即 , J a a k k o z a 一 日a u s s l e : 误 差上 界 [ 5 〕 . 针 对 L “ 范数 非 线性 软 间 隔 S v M 分 类 器 , 其 (L )( ) 误 差 满足 一 厂式 : 心 , 利用 所定义 的模式 确 定搜 索的方 向 . 对 于 R Z 核参数 空间 , 所采 用的模式如 图 1 所 示 , 对应的模 式矩 阵为 : 厂1 1 0 一 1 一 1 一 1 P K = i 匕U 1 1 1 0 一 1 0 1 0 - 一 1 一 1 0 _ ( 8 ) ( 一 1 . 1) ( 0 , l ) ( 一 1 . 0 ) ( 一 l 一 l ) 图 1 R Z 核参数空间对应的模式 r i g . i P a t t e rn ro r an R Z k e r n e 一p a r a毗t er s ( l , l) ( l , 0 ) ( l ,一 l ) Pa C e R l一` T ,搜 一 告客 5 9 一 (一、 ( 一 ,二 : K ( · , , · , ) ) ( 6 ) 上式 的右 边 项 被 称 为 J a a k k o l a 一 H a u s s l e r 误 差 上 界 对 于高斯核 函 数 , 式 ( 6) 可 写成 R , 一 阳 (I · ) ; : 1 艺 s g n ( 一 : J ( x : ) + 。 广) ( 7 ) 显然 , 在计算 J a : , k k o i a 一 H a u s s l e : 误 差上 界 时 只需 要利用所有训 练 样本 做一次 分类 器训 练 , 获得 分 类决策 函数 _ f( x ) , 因此 与经 验验 证方 法 相 比较 , 计算 J a ak k ol a 一 H a us s1( , : 误差上 界所花 费的代价要 小很 多 . 2 搜索策略 在确定 厂模型选 择的 准则 后 , 需 要设 计 一 种 能寻 找到使 得 该准则 全局 最优的模 型 参数点 的搜 索方 法 . 本 文提 出 了一 种粗 网格与模式搜索相 结 合的优化策略 , 该 算法 先执 行 粗 网格搜 索 寻 找全 局优 化 区域 , 再 利 用 模式搜 索 寻 找在该 优化 区 域 的最优 点 . 2 . 1 粗 网格搜索 该搜索 算法 首 先 在 参 数 空 间 定 义统 一 的 网 格 . 研究发现 在优化核参数 时采 用对 数坐标 是 比 较合理 的〔2 . 然后 计算所 有 网 格 点 的 J a ak ko l a - H au s l e : 误差 上界 , 寻找 全局 最小 区域 . 网格的粒 度决 定 了解的 质量 与搜索效 率 . 2 . 2 模式搜索 该搜 索 算法 将 当前 优 化 参数 点 置 为模 式 中 模式 矩 阵的每一列确 定了以 模式 中心为起 点的下 一 个搜索计算参数点 的位置 . 通过 模式搜索步 长 △ P 取值 的不 同 , 可 以 实现 以 模 式 中 心为 圆心 的 3 6 0 。 范 围搜 索 . 参数变化量 可 由下 式计 算得到 : s 二 压P P K ( 9 ) 厂△耳] T 对于 R “ 核参 数空间 , 其 中 乙” = } 二 ’ } . 匕△号J 模式 搜索算法描 述如下 : s et p l 确定初 始 的模 式 中心 为粗网格搜索 所得到 的优化参数 点 , 给定对 数参数搜索 步长 j P 及足够 小的允许步 长 引 st 印 2 根 据 式 ( 9 ) 计算 对 数 参数 的 变化量 、 , 然后 依 次 求得 当前模式 中心 的各邻 域 参数点 的 J a a k k o l a 一 H a u s s l e r 误差 上 界 , 并 将 其 中使 得该 评 价准则最 小的参数 点置 为新 的模 式 中心 ; st eP 3 若 模 式 中心 不 变 , 则 减 小搜 索 步 长 压P 并转 到 st 即 2 重新 寻找新 的模式 中心 ; s t e p 4 重复 执行 s t e p Z 与 s t e p 3 , 直 到 乙” 小于允许步 长 : 为止 , 最终 确定 的模 式 中心 即为 最优参数 点 . 3 基于 黎曼几何 的核函数修正 3 . 1 核函数的几 何特性 B ur ge S 在文献 「6」中讨论 了基于 核 函数 的非 线性 支持向量 机 的几何问题 , 认为非线性 映射 , 是一个 曲子流形 , 它 定义 了从输 入 空 间 I 到特征 空 间 F ( 再 生核 iH lb er t 空 间 ) 的一个嵌入 . 定理 1 在 特 征 空 间 中 , 黎 曼 度规 与核 函 数 之 间满 足如下关 系式 :