一种SVM分类器自动模型选择方法

D0I:10.13374/j.issnl001053x.2006.01.021 第28卷第1期 北京科技大学学报 Vol.28 No.1 2006年1月 Journal of University of Science and Technology Beijing Jan.2006 一种SVM分类器自动模型选择方法 封筠1,2)颉斌1)郝卫东1)杨 扬1) 1)北京科技大学信息工程学院，北京1000832)石家庄铁道学院计算机系，石家庄050043 摘要提出了一种基于粗网格与模式搜素相结合的支持向量机分类器模型参数优化方法，采用 Jaakkola--Haussler误差上界作为模型选择的评价标准.以黎曼几何为理论依据，提出了一种新的 保角变换，对核函数进行数据依赖性改进，进一步提高分类器泛化能力.在研究人工非线性分类间 题的基础上，将该方法应用于手写相似汉字识别，实验结果表明分类精度得到了明显提高. 关键词支持向量机；模型选择；黎曼几何；保角变换；汉字识别 分类号TP391.43 支持向量机(SVM)是由Vapnik等人]于 两方面的问题，即选择标准和所采用的搜索方法， 1995年在统计学习理论基础上提出的一种实现 本文提出了一种基于Jaakkola-Haussler误差上界 结构风险最小化准则的机器学习方法，模型选 评价标准及粗网格与模式搜索相结合的模型参数 择[2]是SVM从理论走向实际应用时所必须解决 优化策略， 的一个关键问题，它将直接显著地影响分类器泛 因为在研究模型参数优化时所采用的核函数 化性能的好坏，但目前对于该问题的研究还很不 类型是确定的，所以并未充分考虑实际数据的影 深入.SVM分类器的模型选择问题可被描述为： 响.然而为了进一步提高分类的精度，有必要从 对于某-一给定的问题，如何寻找到最适合的核函 数据的角度重新定义核函数.本文完成核参数优 数，其中包括核函数类型的确定、核参数的优化以 化后，以黎曼几何[4)为理论依据，对核函数进行 及针对具体给定数据的核函数的修正等方面，在 数据依赖性改进，进而提高分类器泛化能力. 核函数类型的确定上，如何根据实际问题来选择 1模型选择评价标准 最优的核函数至今仍未有明确的答案，从理论上 来说，所有满足Mercer条件的核函数都可作为支 这里重，点讨论常用的L2范数非线性软间隔 持向量核使用.研究表明，高斯核函数SVM具有 SVM分类器.根据已知训练集T={(x1,y1), 很强的学习能力，因此它是一种应用最多的核 …,(xn,yn)川∈(X×Y)",其中x:∈X=Rm,y 函数，本文将重点讨论高斯核函数，其表示形式 ∈Y=1,-1{,i=1,…,n,建立L2范数非线性 如下式所示： 软间隔SVM的优化问题对偶形式如下： 1 K(,)=exp2aIx-） (1) 1 mini y04,K(x,x,）+ 除了核函数中的自由参数（比如高斯核函数 (2) 中的宽度参数σ)外，对于软间隔分类情况，在 ]房 SVM设计时需要引入常量参数C作为误差惩罚 s.t.a,≥0，i=1,2,…,n (3) 因子，通过变换核函数可将问题转变为硬间隔 其中， SVM3],从而将C看作是核函数中的一个自由参 数.在研究模型参数优化选择方法时，需要考虑 0=0,tj 1,i=j (4) 求解该最优化问题，得到最优解α‘=(ai, 收稿日期：2004-1101修回日期：2004-12-28 基金项目：河北省科学技术研究与发展指导计划项目(No, …,a)T,其中a≠0的训练样本为支持向量 02213560) 所构造的齐次决策函数为 作者简介：封筠(1971一)，女，副教授，博士研究生 (x)) (5)

第 卷 2第8 1期 年2 0 0 6月 l 北 京 科 技 大 学 学 报 u J o a r n l o U i f n e份 v i y t fo Sc i e e e a n nd e e T h n o l o y 价幼g i n g V o l . 2 8 N o . l J a n . 2 0 0 6 一种 SMv 分类器 自动模型选择方法 封 药 ` , 2 ) 领 斌 ` ) 郝 卫 东 ` ) 杨 扬 ` ) 1 ) 北京科技大学信息工程学院 , 北京 1 0 0 0 83 2) 石 家庄铁道学院计算机系 , 石家庄 0 5 0 043 摘 要 提出了一种基于 粗 网格与模式搜索相结合的支持 向量机分类器模型 参数优化方 法 , 采用 aJ a k kol a 一 H au s le r 误差上界作 为模型选择 的评 价标准 . 以黎 曼几何为理论 依据 , 提 出 了一种新 的 保角变换 , 对核函 数进 行数据依赖性改进 , 进一步提高分类器泛 化能力 . 在研究人工非线性分类间 题 的基础上 , 将该方法应用于 手写相似汉 字识别 , 实验结果表明分类精度得到 了明显提高 . 关祖词 支持 向量机 ; 模型 选择 ; 黎曼几何 ; 保角变换 ; 汉字识别 分类号 T P 3 9 1 . 4 3 支持 向量 机 ( s v M ) 是 由 v a p n ik 等人 川 于 1 9 9 5 年在统计 学 习理 论 基 础 上提 出的 一 种 实 现 结 构 风 险最 小 化 准 则 的机 器 学 习方 法 . 模型 选 择 2[] 是 s v M 从理 论走向实际应 用 时所 必须解决 的一个关键问题 , 它将直接显 著地 影 响分类器泛 化性 能的好 坏 , 但 目前对 于 该 问题 的研究还 很 不 深入 . S V M 分 类器 的模 型选择 问题 可被 描述 为 : 对于某一给定的问题 , 如 何寻找到最 适 合的核 函 数 , 其 中包括 核 函数类 型的确 定 、 核参数的优化 以 及针对具体给定数据的核函数的修正 等方 面 . 在 核函数类型 的确定上 , 如何 根 据 实际 间 题来选 择 最优 的核函 数 至今仍未 有 明确的 答案 . 从理 论上 来说 , 所有满足 M er ce r 条 件的核 函数都可作 为支 持向量核使 用 . 研 究表明 , 高斯核 函数 S v M 具 有 很强 的学 习能 力〔` 〕 , 因此 它是 一种应 用 最多 的核 函数 . 本文将重 点讨论 高斯核 函数 , 其表示形 式 如下式所 示 : 兀 ( 二 . 二 、 ) 一 e x D卜 共 JJ 二 一 二 J} 2 { ( 1 ) 二 ` 、 丹 , ` 忿 j ` 几 F ( , 2 “ ` 丹 之 1 厂 、 孟 / 乙 J 除 了核 函数 中 的 自由参 数 ( 比如 高 斯 核 函 数 中的宽 度参数 6 ) 外 , 对 于 软 间 隔 分 类 情况 , 在 S V M 设计时需要 引人常量 参 数 C 作为误 差惩罚 因子 . 通 过 变换 核 函 数 可将 问题 转 变为硬 间 隔 s v M 〔’ } , 从 而将 c 看作是核 函数 中的一个 自由参 数 . 在 研 究模型参数 优化选择方 法 时 , 需要 考虑 收稿 B 期 : 2 0 0 4 一 11 一 0 2 修回 日期 : 2 0 0 4 一 22 一 2 5 墓金项 目 : 河 北 省科 学 技 术研 究与 发 展 指导 计 划 项 目 ( N 仓 0 2 2 13 5 6 0 ) 作者简介 : 封摘 ( 19 7 1一 ) , 女 , 副教授 , 博士研究生 两 方面 的问题 , 即选 择标准 和所采 用的搜索方 法 . 本 文提 出了一种基 于 Ja k k ol a 一 H au s le r 误差 上界 评价 标准及粗 网格与模 式搜索相 结合 的模型参数 优化策略 . 因为在研 究模型 参数优化 时所采用 的核 函数 类型是确 定的 , 所 以并 未 充分考虑 实 际数 据 的影 响 . 然而 为 了进 一 步提 高 分类 的精 度 , 有 必要 从 数据 的角度重新 定义核 函数 . 本文 完成 核参数优 化后 , 以 黎 曼几 何4[] 为 理 论 依据 , 对 核 函数 进行 数 据依赖性 改进 , 进 而提高分类器泛 化能力 . 1 模型选择评价标准 这里重 点讨论常用 的 L Z 范数非 线性 软 间隔 s v M 分 类器 . 根 据 已 知 划11练 集 T = { ( x l , y l ) , … , ( x 。 , y 。 ) }任 ( x x y ) ” , 其 中 x 、 任 x = R m , y , 任 Y = { 1 , 一 1 } , i 二 1 , … , n , 建立 L Z 范数 非线性 软 间隔 S V M 的优化 问题 对偶形 式如下 : 一i2 n . im 。 、了1 、 、 , 尹少 ù, 3 万硬、了、 艺 名 y 了 = I J = 1 粼 1 、 ] 砂 红 」 - . a , ) 0 , =i 1 , 2 , … , n 其中 , 、 一 {左属 ( 4) 求解该最 优 化 问题 , 得到 最 优解 a ` = ( a 广 , … , 。 厂) T , 其 中 。 广共 。 的训 练样 本 为支 持 向 量 . 所构 造的齐 次决策 函数为 , ( · ,一 g · (客 · 厂, ! K (一 ) ! ( 5 , DOI: 10. 13374 /j . issn1001 -053x. 2006. 01. 021

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 在 特 征 空 间 中 , 黎 曼 度规 与核 函 数 之 间满 足如下关 系式 :

·90· 北京科技大学学报 2006年第1期 g,(x)=22K(,儿，： (10) 为-1的支持向量数目，xm表示属于负类的支持 向量样本的特征均值.所以，x:表示支持向量样 在黎曼空间中，体积微元可被定义为： 本x:与其所属类的支持向量特征中心矢量xm间 dV=√g(x)dx1dx2dxa (11) 的Euclidean距离.显然，从式(l4)可知映射 其中g(x=detg)(x)川，放大因子√g(x)表示在 D(x)与样本到支持向量的距离呈指数递减. 映射”下输入空间I的局部区域如何在特征空 定理2采用式(14)所示保角变换D(x)的 间F中被放大. 修正核函数K(x,x')满足Mercer定理的条件. 3.2 Amari的核函数修正思想 证明设A为R的紧子集，对于任意的 根据在输入空间所锈导的黎曼几何结构的基 h(x)∈L2(A),有h2(x)dx<∞. 础上，日本学者Amari等人提出了通过修正核函 数来提高SVM分类性能的方法[4，门.该方法的 由式(12)，易见K(x,x)具有连续性和对称 基本思想是通过改变不同区域的体积元来增大 性.下面证明K(x,x)的半正定性.由式(14)可 SVM分界面处的空间分解力，即增大f(x)=0 得到D(x)>0,因此必存在一个正数B,使得 分离边界曲面附近区域的黎曼度规g(x),而同 D(x)≥>0，从而有： 时减小其他区域的g(x).基于在实际应用中分 离边界曲面是未知的这一事实，Amari则通过增 AR,h(xh()dr= 加支持向量邻域的黎曼度规矩阵来解决这个问 D(x)D(x)K(x,x)h(x)h(x)dxdx 题，提出了如下定义的修正核函数的准保角映射 定义1对于一个正的标量函数D(x),定 (()dxdx0. 义： 定理得证 K(x,x')=D(x)D(x)K(x,x')(12) 在所提出的保角变换D(x)基础上，给出了 称之为核函数通过因子D(x)的保角变换，则 数据依赖型修正核函数的支持向量机训练算法， 衣(x,x)成为支持向量机的修正核函数.同时， 该算法可描述为： 非线性映射p被修正为p(x)=D(x)p(x). Step1根据具体问题初步确定所选核函数 对于高斯核函数，在其经过D(x)的保角变 类型； 换后，黎曼度规g(x)将变为： Step2利用本文提出的核参数优化算法， g(x)=D(x)D,(x+D2(x)g(x)(13) 求得优化核参数，进而确定初始的核函数K； 其中，D,(x)=D(x Step3使用核函数K训练SVM,获取支持 Oxi 向量的信息，并计算x和xm,然后按式(12)， 由式(13)知，所选择的D(x)应该在支持向 量处取值大而在其他点取值小 (14)和(15)修正它，得到修正核函数K; 3.3保角变换 Step4使用修正核函数K训练SVM; 本文提出了一种新的保角变换D(x),如下 Step5重复执行Step3与Step4,直到获得 式： 最好的分类性能 D(x)=∑exp(-‖x-x:‖2/x)(14) 4实验结果与分析 其中，t=‖xm-x:I2,xm的取值可由下式给出： 4.1人工非线性分类问题 xm,=+1 为了测评本文所提出的模型选择方法性能， xm= (15) xm,y:=-1 首先研究了它在人工非线性分类问题上的应用. 这里选用在区域[-0.5,0.5]×[-0.5,0.5]内随 在式(15)中，x=1 x,nt是类标签为+1 机均匀分布的数据点，两类数据由非线性分界线 y=0.5sin(2πx)所决定，如图2所示.在仿真实 的支持向量数目，x表示属于正类的支持向量 验中，每类随机选取100个样本构成训练集，每类 样本的特征均值；x。=1∑ ,nsv是类标签 再另选1000个样本构成测试集， nsv 由核参数优化算法所得到的误差惩罚因子C

北 京 科 技 大 学 学 报 2 0 06 年第 1 期 a a _ _ , igj ( ` ’ 一 石寻 ( ` , ` ” X 一 二 ( ` 0 ’ 在黎 曼空 间中 , 体积微元 可被定 义为 : d y 一 甲百石) d x l d x Z … d x 、 ( r r ) 其中 g ( 二 = de t } g 。 ( 二 )1 , 放 大因子 了奋石万表示在 映 射 切 下输入 空 间 I 的 局 部 区域 如 何在 特征空 间 F 中被放大 . 3 . 2 A m ar i 的核函数修正 思想 根据在输入 空间所诱导 的黎 曼几何结 构的基 础上 , 日本 学者 A m ar i 等人提 出了通 过修正 核函 数来提 高 s v M 分类 性 能 的方 法 ’[, 7〕 . 该 方 法 的 基本 思想 是 通 过 改变 不 同 区域 的体积 元 来 增 大 S v M 分界 面处 的空 间分 解 力 , 即 增 大 f ( x ) = 0 分离边界 曲面附近 区域的黎 曼 度规 igj ( x) , 而 同 时减小其 他区 域的 igj ( x ) . 基于在实 际应 用 中分 离边界 曲 面是 未 知 的这 一 事实 , A m ar i 则 通过 增 加支持 向量 邻域 的黎 曼 度 规 矩 阵 来 解决 这 个 问 题 , 提出 了如下定义 的修正核 函数的准保角映射 . 定义 1 对 于 一 个 正 的 标 量 函 数 D ( x ) , 定 义 : K ( x , x ` ) = D ( x ) D ( x ’ ) K ( x , x ` ) ( 12 ) 称之为 核 函 数 通 过 因 子 D ( x ) 的 保 角变 换 , 则 天( x , x ` )成 为支 持 向量 机 的修正 核 函数 . 同 时 , 非线性映 射 甲 被修正为 毋( x) = D ( x) 杯 x) . 对于高斯核 函 数 , 在其经过 D ( x )的保角 变 换 后 , 黎 曼度规 igj ( x) 将变为 : 云ij ( x ) = D 、 ( x ) jD ( x + D Z ( x ) g 。 ( x ) ( 1 3 ) 甘 。 n , _ 八 _ 旦旦工主 2 其 甲 . D 、 ( x ) = - . / 、 月 , 一 , 、 一 ` a x 、 由式 ( 1 3) 知 , 所选 择的 D ( x ) 应 该在支 持 向 量处取 值大而在 其他点取 值小 . 3 . 3 保角变换 本文提出 了一 种新的保角变换 D ( x ) , 如 下 为 一 1 的支持向量数 目 , x 孟表示属 于 负类的支持 向量样本 的特征 均值 . 所 以 , : 、 表 示 支持 向量 样 本 x : 与其 所属类的支持向量特征 中心 矢量 x m 间 的 E u e li d e a n 距 离 . 显 然 , 从 式 ( 14 ) 可 知 映 射 D ( x) 与样本到 支持 向量 的距离呈 指数递减 . 定理 2 采用式 ( 14) 所 示保 角变换 D ( x ) 的 修正 核函数 元( x , x ` )满足 M er ce r 定理 的条件 . 证明 设 A 为 R N 的 紧 子 集 , 对 于 任 意 的 、 ( 二 ) 。 : ’ ( , , , 有 { ` ’ ( ! , d 工 < 一 由式 ( 1 2 ) , 易见 K ( x , x ’ )具 有连 续性和 对称 性 . 下面证 明 K ( x , x ’ )的半正定性 . 由式 ( 1 4) 可 得到 D ( x ) > 0 , 因 此 必 存 在 一 个 正 数 月 , 使 得 D ( x ) ) 月> 0 , 从 而有 : 汗 元( 二 . 二 · ) 、 ( 二 ) 。 ( 二 · ) d 二 d x 一 J J A 火 A 仟 n ( 二 ) n ( 二 · )、 ( 二 . 二 )。 ( 二 )、 ` 二 · ) d x d x · 要 。 , 厅 兀 ( x . x / ) 、 ( x ) 、 ( x · ) d x d x ·妻 0 . J J A X A 定理得证 . 在所提出 的保角 变换 D ( x ) 基础 上 , 给 出 了 数据依赖型修正核 函 数 的支持 向量机 训 练算 法 . 该 算法可 描述 为 : st eP I 根据具 体问题 初 步确 定所 选 核 函 数 类型 ; st eP Z 利 用 本 文 提 出 的 核参数 优 化 算法 , 求得 优化核参数 , 进而 确定初 始的核 函数 K ; s t e p 3 使用核 函数 兀 训 练 S v M , 获取支持 向量 的信息 , 并 计 算 x 盆和 x 爪 , 然 后 按 式 ( 12) , ( 14 ) 和 ( 15) 修正它 , 得 到修正核 函数 元; s t e p 4 使用修正核 函数 K 划11练 s v M ; s t e p s 重 复执行 s t e p 3 与 s t e p 4 , 直 到获得 最 好的分 类性 能 D ( x ) 一 艺 e x p ( 一 ll x 一 x 、 11 2 / : 子) ( 一4 ) 其中 , : 卜 } X m 一 X 乞 工 m = }1 2 , x m 的取值可 由下式给出 : X m , y i = + 1 = 一 1 ( 1 5 ) 工 m , y ￡ n X 类是类 标签为 + 1 n 脚, 艺浏 土 , 在式 ( 1 5) 中 vsn , x 孟= 的支持 向量数 目 , x 盖表示 属 于 正 类 的 支持 向量 样本 的特征均 值 ; · 、 一 亡郭 , · 、 是类标 签 4 实验结果与分析 4 . 1 人工 非线性分 类问题 为 了测 评本文 所提 出的模型 选 择方 法 性 能 , 首先研 究 了它在 人工 非线性 分 类 问题 上的 应用 . 这里选 用在 区域〔 一 0 . 5 , 0 . 5」x 〔 一 0 . 5 , 0 . 5] 内随 机均匀分布 的数据 点 . 两类 数据 由非 线性 分界 线 y = 0 . s is n ( 2二 x ) 所 决 定 , 如 图 2 所示 . 在仿 真 实 验 中 , 每类随机选取 10 0 个样本构成训 练集 , 每类 再 另选 1 0 0 个 样本构成 测试集 . 由核参 数优化算法所得到 的误差 惩罚 因子 C

Vol.28 No.1 封筠等：一种SVM分类器自动模型选择方法 91· 0.5 量，形成最终输入分类器的特征向量.图4以某 0.4000。。。 0 0.3 8 个汉字样本为例说明了本文所采用的特征提取方 08 法，另外，实验中发现弹性网格数N×N选为 0.200 8g0 0 8×8时分类效果最好 0.1 0 0 8080 016 029.8 0 -0.3 0.4- (1) (2) (3) ◆ 0,5405-6.2u00.10203040.5 图4特征提取示例.(1)规范化汉字：(2)LL子图：(3)弹性网 格化的LL子图 图2人工数据集（两类分别用和'“'表示） Fig.4 Illustration of feature extraction:(1)normalized char- Fig.2 Artificial data set.the two classes are denoted by acter;(2)LL sub-image:(3)meshed LI.sub-image and 'respectively 以相似字组“己巳"为例来研究本文所提出的 为2048，宽度参数。为2.在此优化值的基础上， 模型选择方法在手写相似字识别中的应用，在实 利用本文所提出的保角变换对核函数进行送代修 验中，每个汉字选用900套不同的书写样本，其中 正计算，其结果如图3所示.可见，在第1步迭代 400套用作训练，剩余500套用于测试.由核参数 时SVM分类器就达到了最好的性能0.033，与没 优化算法所得到的误差惩罚因子C为16，宽度参 有修正前的0.09相比较，测试误差要降低 数：为8.对核函数进行迭代修正计算的结果如 63.3%,性能得到了大大改善 图5所示.在第1步送代时GE达到了0.033并 0.99 且此时支持向量占总的训练样本比例为17.0%， 与没有修正前的GE为0.06及支持向量比例为 0.07 54.9%相比较，GE要降低45%，支持向量比例要 降低69%，由此可见SVM分类器性能得到了较 06 大程度地改善.另外，对比图3可以发现两者的 0.05 核函数修正迭代曲线变化趋势很相似，都是在第 0.04 1步迭代时SVM分类器就达到了最好的性能，并 在后面的迭代中泛化误差GE趋于基本不变 0.030 6 送代步 0.0609 留3人工非线性分类问题的核函数修正结果 0.055 Fig.3 Simulated result for modified kernel on the artificial 0.050 non-linear classification problem 4.2手写相似汉字识别问题 0.045 相似字的识别是脱机手写汉字识别技术需要 0.040 解决的一个关键问题.尝试应用本文所提出的模 0.035 型选择方法来解决相似字识别这一难题.首先采 用弹性网格与小波变换相结合的方法提取汉字的 0.0300 4 5 迭代步 特征，具体做法是：先将规范化后的二维手写体汉 图5相似字组“己已”识别的核函数修正结果 字图像(64<64)按行、列分别进行一级小波变换， Fig.3 Simulated result for modified kernel on the similar set 对得到的低频分其【L子图（保持了汉字基本信 '己已'recognition problem 息)按汉字图像在水平和垂直两个方向上的直方 图投影的均匀划分构造一组弹性网格(N×N 5 结论 格)，再计算每个网格内的像素概率分布，进而得 到一个V维的特征向量.然后，利用部分空间 本文提出了一种SVM分类器自动模型选择 法选择那些能表明相似字间主要差别的特征分 的新方法，有效地解决了SVM从理论走向实际

V o l . 2 8 N o . l 封药等 : 一种 s v M 分类器自动模型选择方法 令 。 今卜+., 闷 。户今. 翔沪泌 . 卜 气 令 0 0 0 0 今吞母令 仑 o O 压 户 o U 、 O O o O 饭于 量 , 形 成最 终 输入 分类 器 的特 征 向量 . 图 4 以 某 个汉字样 本为例说 明 了本 文所采用 的特 征提取方 法 . 另 外 , 实 验 中 发 现 弹性 网 格 数 N 又 N 选 为 8 x s 时分类 效果最 好 . 0 0 0 + 、 + 已 已 。 ( l ) ( 2 ) ( 3 ) 一í么 。 一 0 . 至执卜 户 一 0 2 一 一住 3 漆 一 0 . 4 一 尹 。 。傀 魏犷 一 住s只 廿 黑共 一又j 〕 一气) 拜 一LJ ` 乍 0 . 2 一 0 . 1 0 0 . 1 0 2 0 一 3 0 . 4 0 . 5 X 图 2 人 工数据集 {两类分别用 ` 。 ’ 和 ` 关 ’ 表示 ) F ig . 2 a n d ` 关 人r t in e i a 搜 d a t a s e t . t he t附 e l a s s e s a er d e n o tde b y 图 4 特征提取示例 . ( l) 规范化汉字 ; 〔2 ) L L 子图 ; ( 3 )弹性网 格化的 L L 子图 F i g . 4 I及一此 t r a t盖。 n o f afe t 吐代 ex t ar e t i叨 : ( 1 ) n o r 秘li z de c h ar · a e t e r : ( 2 ) L L s u b · i m a g e ; ( 3 ) 砒 s h de L L s u b 一盖咖ge r e s P e e t i 、 e l》 为 2 0 4 8 , 宽度参数 。 为 2 . 在此优 化值的基础上 , 利用本 文所提 出的保角变换 对核 函数 进行迭代修 正 计 算 , 其结 果如图 3 所示 . 可见 , 在第 1 步迭代 时 S V M 分类器 就达 到 了最 好的性 能 0 . 0 3 , 与没 有 修 正 前 的 0 . ()9 相 比 较 , 测 试 误 差 要 降 低 6 3 . 3 % , 性能 得到了大大 改善 . 应0 1 2—3 4 5 6 以 相似字组 “ 己 巳 ” 为 例来研究本 文所提 出的 模型选 择方法 在手 写相似 字识 别中 的应用 . 在 实 验 中 , 每个汉 字选用 9 0 0 套不 同的书写样本 , 其中 4 0 0 套 用作训练 , 剩 余 50 0 套用 于测试 . 由核 参数 优 化算法所得 到的误差惩 罚 因子 C 为 16 , 宽度参 数 。 为 8 . 对核 函数进 行迭 代修正计算的结果 如 图 5 所示 . 在 第 1 步 迭代 时 G E 达 到 了 0 . 0 3 并 且此时支持 向量 占总的训 练样 本 比例为 17 . 0 % , 与没有 修正 前 的 G E 为 0 . 06 及支 持 向量 比 例为 5 4 . 9 % 相 比较 , G E 要 降低 4 5 % , 支持 向量 比 例要 降低 69 % , 由此 可 见 S V M 分 类 器性 能 得 到 了较 大程度 地 改善 . 另外 , 对 比 图 3 可 以 发现 两 者的 核函 数修正迭 代 曲 线变 化趋 势 很相 似 , 都 是 在第 1 步 迭代时 S V M 分类器 就达到 了最 好的性 能 , 并 在后面 的迭代中泛 化误差 G E 趋 于基本不变 . 勺QOC “朽气 通络,、 日口0日n 日自曰Unù n曰门 绷线 迭代步 图 3 人工非线性分类问题的核函 数修正结果 0 . 06 0 0 . 0 5 5 F i g . 3 Sim ” . a t ed r es u l t f o r n l o d if ied ke r 俄 1 o n t he a r t ifj e i a l n o n 一 l i n e a r e l a s s 云6 e a t i o n P m b l e n l 0 乃50 4 . 2 手写相似 汉字识别问题 相似字 的识别 是脱机手 写汉字识 别技术需要 解决 的 一 个关 键问题 . 尝试应 用本 文所提 出的模 型选 择 方法来 解决相似 字识别这一 难题 . 首先 采 用弹性 网格 与小波变换 相结合的方法提取 汉字的 特征 , 具体 做法是 : 先将规范化 后的二维手 写体汉 字 图像( 64 只 6 4) 按行 、 列分别进 行一级 小波变换 , 对得到 的低频 分 量 几L 子 图 ( 保 持 了汉 字 基本 信 息 ) 按汉字 图像 在水 平和 垂 直两 个方 向上 的 直方 图投影 的均 匀 划 分 构 造 一组 弹 性 网 格 ( N 又 N 格 ) , 再 计算每个网 格 内的像 素概率分 布 , 进 而得 到一 个 N 二 维 的特征 向量 . 然 后 , 利 用 部 分 空 间 法选择 那些 能 表 明 相 似 字 间 主要 差 别 的 特 征分 劣 。刀4 5 兮二 0 0 4 0 0 . 0 3 5… 1 0刀3 0 6 图 5 1 2 3 4 5 6 迭代步 相似字组 “ 己巳 ” 识 别的核函数修正结果 F i g . 3 Si m u l a tde 代 s u 砚t fo r m峨心 iif de k e能 1 o n t h e s 应m il a r s e t ` 己已 ’ er 魄 n it i o n p r o b一e m 5 结论 本 文提 出了一种 S V M 分 类器 自动模型 选 择 的新 方 法 , 有效 地解 决 了 S V M 从 理论 走 向实 际

·92· 北京科技大学学报 2006年第1期 应用时所面临的模型选择这一“瓶颈”问题.首先 Ed.New York:Springer,2000 针对高斯核函数以Jaakkola--Haussler误差上界为 [2]Gold C,Sollichb P.Model selection for support vector ma 模型选择性能评价标准，应用粗网格与模式搜索 chine classifcation.Neurocomputing,2003,55:221 [3]Cortes C,Vapnik V.Support vector networks.Mach Learn. 相结合的优化算法寻找优化的模型参数.该优化 1995,20:273 算法充分利用了粗网格全局搜索及模式搜索的高 [4]Amari S,Wu S.Improving support vector machine classifiers 效率优点，特别适合于计算导数困难的低维优化 by modifying kernel functions.Neural Networks,1999,12: 问题.然后基于黎曼几何理论提出了一个新的保 783 角变换，对核函数进行数据依赖性的进一步改进， [5]Chapeile O,Vapnik V N.Choosing multiple parameters for 并证明了对应的修正核函数满足Mercer条件. support vector machines.Mach Learn,2002,46:131 16]Burges CJC.Geometry and invariance in kernel based meth 最后，在人工非线性分类问题实验研究的基础上， ods//Scholkopf B.Burges C JC.Smola A J.Advances in 将该方法应用于手写体相似汉字识别，实验结果 Kernel Methods-Support Vector Learning.Cambridge:MIT 表明SVM分类器性能得到了明显地改善. Press,1999 [7]Wu S,Amari S.Conformal transformation of kemel fune. 参考文献 tions:a data-dependent way to improve support vector machine classifiers.Neural Process Lett,2002,15:59 [1]Vapnik V N.The nature of statistical learning theory.2nd Automatic model selection method for support vector machines classifiers FENG Jun2),XIE Bin),HAO Weidong1),YANG Yang1) 1)Information Engineering School,University of Science and Technology Beijing,Beijing 100083,China 2)Department of Computer Science,Shijiazhuang Institute of Railway,Shijiazhuang 050043,China ABSTRACT An optimal approach was presented for model parameters of a support vector machine classifi- er based on coarse grid search combined with pattern search,in which the Jaakkola-Haussler error bound was considered as the evaluation criterion of model selection.Based on the Riemannian geometry theory,a novel conformal transformation was proposed and the kernel function was modified by the transformation in a data-dependent way.Simulated results for the artificial data set showed that the approach for automatic model selection was very effective.An application of the approach in handwritten similar Chinese characters recognition was further investigated.The experimental result showed remarkable improvement of the per- formance of the classifier. KEY WORDS support vector machines;model selection;Riemannian geometry;conformal transforma- tion;Chinese character recognition

北 京 科 技 大 学 学 报 2 0 0` 年第 1 期 应用时 所面临 的模 型选择 这一 “ 瓶颈 ” 问题 . 首先 针对高斯核函数 以 Ja k ko af 一 H au s el r 误差上界 为 模型选择性 能评 价标准 , 应 用粗 网格与模式 搜索 相结合的优化 算法寻 找优化 的模型参数 . 该 优 化 算法充分利用 了粗 网格全局搜索及模式 搜索 的高 效率 优点 , 特别 适 合于 计算导 数困难的低 维 优化 问题 . 然后基 于黎 曼几何理论 提 出 了一 个新的保 角变换 , 对核 函数进行数据依赖性的进一步 改进 , 并证 明 了对 应 的修正 核 函 数 满足 M er ce r 条 件 . 最后 , 在人工非线性分类问题 实验研 究的基础 上 , 将该方法应用 于 手 写体相似 汉 字识 别 , 实验 结果 表 明 S V M 分类 器性 能得到 了明显地改善 . 参 考 文 献 川 Va p n i k V N . T h e n a t u r e o f s t a t i s t i e a l l e am i叱 t h eo r y . Z n d E d , N e w Y or k : S p ir n 郎 r , 2 0 0 0 〔2 ] G o ld e , 50 1一i e h b P . M od e l s e l e e t io n f o r s u p卯rt ve c t o r m a - e h i n e e l as if e a t i o n . N e o r o c 帅)I . t i gn , 2 0 0 3 , 5 5 : 2 2 1 t 3 ] oC rt es C , v 叩 n ik V . S u p卯rt v e e t or n e t ow rks M a e h L e的 · 1 9 9 5 , 2 0 : 2 7 3 〔4 〕 A n l ar i s , w u 5 . xm p r vo i明 s叩即rt v e ct o r m a e h i n e e l a s if i e r s b y n 、浏if y ign k e rne l f u n c t ~ . N e u ar l N e tw or kS , 19 99 , 1 2 : 78 3 汇5 〕 Ch a p e ll e O , v a p n ik v N , C h o s i n g m u l t i p l e p amr et e r s f o r s u P p o r l v e e ot r m a e h i n e s . M a e h eL aur , 2 00 2 , 4 6 : 1 3 1 〔6 〕 B u 啥es C J e . G eO m e t r y an d i n va ir an c e i n k e r n e l bas e d m e t h - od s / cS h6I k o p f B , B u 啥es C J C , S m o l a A J . A d va n e e s i n K e rn e l M e t h od s 一 S 叩op rt V ce t o r L ~ i雌 . C a m b r i d g e : M IT P r e s , 1 9 9 9 [ 7 了 W u S , A m a r i 5 . oC n fo rm a l t r an s fo rm a t i o n o f k e rn e l f u n e - t i o n s : a d a t a 一 d e 伴n d e n t w a y t o im p ro v e s u p po r t ve e t o r m a e h i n e e l a s if i e rs . N e u r a l P r oc 积” L e t t , 2 0 0 2 , 1 5 : 5 9 A u t o m a t i e m o d e l s e l e e t i o n m e t h o d f o r s u p p o r t v e e t o r m a e h i n e s e l a s s i fi e r s 咫N G J u n l , 2 ) , x 班 B i n l ) , 月A o we 艺己o n g l ) , 以N G 介 n g l ) 1 ) I n fo 二 a t i o n E n g i n e e ir n g cS h o l , U n i v e r s i t y o f cS i e n e e a n d T e e h nol 吃y eB ij i眼 , B e ij i n g 1 0 00 8 3 , C h i n a 2 ) D e p art m en t of o 〕 n l p u t e r cS i e n e e , S h ij iaz h u a n g I n s t i t u t e o f R a Uw a y , s h ij iaz h u a n g 0 5 0 04 3 , e h i n a A BS T R A C T A n o p t i m a l a p p or a e h w a s p r e s e n t e d f o r m o d e l p a r a m e t e r s o f a s u p p o r t v e e t o r m a e h i n e e l a s s i fi - e r b a s e d o n e o a r s e g r id s e a r e h e o m b i n e d w i t h P a t t e r n s e a r e h , i n w h i e h t h e J a a k k o l a 一 H a u s s l e r e r or r bo u n d w a s e o n s i d e r e d a s t h e e v a l u a t i o n e r i t e r i o n o f m o d e l s e l e e t i o n . B a s e d o n t h e R i e m a n n i a n g e o m e t r y t h e o r y , a n o v e l e o n fo r m a l t r a n s fo r m a t i o n w a s p or po s e d a n d t h e k e r n e l f u n e t i o n w a s mo d if i e d b y t h e t r a n s fo r m a t i o n i n a d a t a 一 d e p e n d e n t w a y . S im u l a t e d r e s u l t s fo r t h e a r t i fi e i a l d a t a s e t s h o w e d t h a t t h e a p P or a e h fo r a u t o m a t i e m o d e l s e l e e t i o n w a s v e r y e f f e e t i v e . A n a P p li e a t i o n o f t h e a p p or a e h i n h a n d w ir t t e n s i m i l a r C h i n e s e e h a r a e t e r s r e e o g n i t i o n w a s f u r t h e r i n v e s t i g a t e d . T h e e x p e r im e n t a l r e s u l t s ho w e d r e m a r k a b l e im p or v e m e n t o f t h e P e r - fo mr a n e e o f t h e e l a s s i fi e r . K E Y W O R D S s u p 卯 r t v e e ot r m a e h i n e s ; mo d e l s e l e e t i o n ; Ri em an n i a n g eom e t r y ; e o n fo mr a l t r a n s f o mr a - t ion ; C h i n e s e e h a r a e t e r r e e o g n i t i o n