PAC-Bayes边界理论融合了贝叶斯定理和随机分类器的结构风险最小化原理，它作为一个理论框架，能有效评价机器学习算法的泛化性能。针对支持向量机（SVM）模型选择问题，通过分析PAC-Bayes边界理论框架及其在SVM上的应用，将PAC-Bayes边界理论与基于交叉验证的网格搜索法相结合，提出一种基于PAC-Bayes边界的SVM模型选择方法（PBB-GS），实现快速优选SVM的惩罚系数和核函数参数。UCI数据集的实验结果表明该方法优选出的参数能使SVM具有较高的泛化性能，并具有简便快速、参数选择准确的优点，能有效改善SVM模型选择问题。
汤莉,赵政,宫秀军:基于PAC- Bayes边界理论的SVM模型选择方法 2015,51(6) kL(Q(OP()=Eo In(@(c)P(c) (7) +n(m+ 该定理1表明,对于分布Q中的任意分类器c,它 KL(Q3(w,)Q(,)≤ 的分布经验误差与真实误差可以被它的先验分布与真 实分布来畀定即如果分类器的先验分布与真实分布足3基于PAC- Bayes边界的sVM模型选择方法 够接近的话,它的真实误差与经验误差分布也可以足够 随着计算学习理论和决策理论的发展, PAC-Bayes 接近。所以如果能够知道分类器的先验分布(如高斯分边界可作为模型选择有效的新方法。概率近似止确性 布),并且知道假设其真实分布与先验分布属丁同一类理论和贝叶斯决策理论能为 PAC-Bayes边界理论提供 型,定理1的后半部分不仅可以进步简化,并能够指导有效性和正确性的证明:同时,PAC- Baycs边界理论能 分类器模型的选择,使得分类边界(分类误差损失)更紧。为学习算法的评价提供深厚的理论基础将该理论运用 在经验误差固定的情况下,真实误差与KL相对熵于sVM分类器的模型选择,避免了计算量过大的问题 是单调增的,而经验误差和不等式后半部分对亍给定的3.SVM模型选择问题描述 学习算法和训练数据集都是固定的,因此该不等式给出 SVM模型选择主要包括两方面:SVM中核函数的 了平均真实误差的上界,而真实误差即是算法的泛化性选择及其参数的确定惩罚参数的选择。 能的绝对指标,故该定理对于学习算法效果的分析具有 SVM分类算法对线性不可分的训练样本做模型训 重大意义 练时,会引入核函数以及惩罚系数C。如何选择核函数 22SVM分类器上的PAC- Bayes边界计算 和惩罚系数是SVM模型选择研究的重点,也直接决定 传统的 PAC-Baves边界定理中给出了泛化错误率了SwM的分类性能。惩罚系数C的意义为将会被误分 概率近似正确的上限数学形式,但是在 PAC-Bayes边界类的点的费用系数,它同该点到决簧边缘的距离的乘积 定理中,要求计算出算法对概念的先验分布和后验分布即为分类的模型计算过程中的惩罚项,用来表示对该点 的杺对熵及概念后验分布的平均样本误差率,定理中各的惩剀。当该点距离边缘过远时,惩罚项会过大,而使 项式无法直接从实验结果测量得到解推导难度较大,得该点不能被准确预测。这种情况是不可避兔的,其目 因为要客观地分忻算法对概念的先验分布是难以实现的是为了使模型具有更强的泛化能力,能准确地预测大 的。同时除了 Bayes分类器,现有的大部分分类算法的多数点,而不是全部.以防止模型对数据的过分拟合 输出是一个分类函数,而不是概念的后验分布。这导致 对丁线性不可分的情况,SVM通过使用核函数,将 PAC- Bayes边界目前应用范围狹窄。若假定概念在特低维输入空间线性不可分的样本转化为高维特征空间 征权空间上的先验分布和后验分布都服从协方差矩阵使其线性可分,从而在高维特征空间中可采用线性算法 恒定的正态分布,则可将PAC- Bayes边界应用于SVM对样本的非线性特征进行线性分析。核函数降低了算 中,下面分析SVM分类器的PAC- Baves边界计算。 法的计算复杂度,常见的核函数有多项式核函数、RBF 假设先验分布与后验分布都是独立同分布的,且符合核函数以及 sigmoid核函数等,其中RBF核函数叫将原 权空间上的正态分布,设X=N(x,1E),Y=N(x,42E2),空间映射至无限维的高维。核函数中的参数,也是模型 则KL(ⅪY)的值可由下式表示: 选择中参数选择的一部分。SVM算法的模型选择可以 KCX)=(x1-42)2(1-2)+ 理解为对模型惩罚参数C、核函数种类以及核函数参数 的选取。本文中选定核眄数种类不变,采用RBF核函 221+otr(EI22-lai (8)数。RBF核函数屮的参数σ也是被评估选择的个参 这里再假设协方差矩阵Σ和∑2都是对角元为1的数,因此svM的模型选择决定于惩罚系数C和核函数 参数σ。不同的模型参数C和a经过对有限样本的训练 单位矩阵,则KL(QP)可由△/2来代替 后,会产生性能有差异的模型,这些模型对分类的有效 推论l(PAC- Bayes边界应用」sM)首先假设先 验分布和后验分布为具有单位方偏差的高斯分布,先验 高斯分布,先验和准确性是不同的。如何通过筛选不同的参数产生 最优分类模型,这就是模型选择要解决的问题。 分布P是以单位方差的原点作为中心的高斯分布,服从 目前关于核函数中参数选择问题主要有两种解决 MO.1)分布,后验分布Q(w,)具有单位矢量w和方向途的:1)交叉验证技术;(2)最小化学习算法错误率的 因子μ,即沿着w方向上与原点的距离是。给定任 界。采用交叉验证方法,需要在样本上进行训练建立 意的D分布,分类器给定w和>0,对于训练数据的样分类模型,进而测试数据在固定参数值上的分类错误 本,O、(w,A为训练数据错误率的随机度量,QDw,)率,并不断修正参数,使得测试错误率最小。使用该方 为分类器的真实误差。δ是置信度,不等式(5)可达到法评价模型,需要在不同数据集上进行大量预测。因此 1-6的概率 其缺陷在于大样本、多参数上的计算量过大。为了解决 30 2015,51(6) Computer Engineering and Applications计算机工程与应用 交叉验证技术的问题,很多学者提出了最小化误差边界核函数后,可以得到: 的方法",这些误差界包括ⅹi- Alpha bound,GACV、 wx=a, k(x,x), x'x=k(xx Span bound、Ⅴ C-bound、RM( Radius-margin) bound等, 其中较常用的是RM界,该方法减少了计算量,但存在 C.0:(x:;x 的缺陷在于,每一次迭代均需训练SⅴM和求解一个额 外的二次规划问题去得到特征空间中包含所有训练样 综上,可以将γ写成以下这样的形式 本的最小超球半径,造成了可观的计算开销 a k(x, x) 3.2基于PAC- Baves边界的SVM模型选择原理 (x,y) (16) 为了解决以上问题,同时考虑到 PAC-Bayes理论提 k(x,x)∑ak(x,x 供的风险边界可作为评价分类效果优劣的标准,本文 i,j=1.1 提出一种基于PAC- Bayes边界的SVM模型选择方法其中,RBF核函数k表示为 (PBB-(S),在基于交叉验证的网格搜索法选择初始参 k(xi,x)=exp(Ix, -x P/(20) 17 数的基础上,再基于PAC- Bayes边界最小化来选择SVM 最后讨论推论1中的参数u,对于边界来说p是非 最优参数和模型。 单调因子,即无法通过〃的趋势来预测边界的情况。但 首先阐述 PAC-Bayes边界应用于SvM分类器的基是通过SM对数据集学习分类,结果显示只有最佳的 本原理。假设先训练m个实例样本,经过训练m个样P能使边界最小化。从0.01到100之间取值,求出最 本会定义个线性分类器 小边界值和最佳u,将该最小边界值作为PAC- Baves边 c(x)=sign(w plr)) (10)界,以上讨论了全部参数。 其中w(x)即为核映射的表示,它叫将非线性的分类数据3.3算法实现 转换到某个数据线性可分的高錐特征空间。〃是确定 SVM模型选择山一对参数决定,即惩罚系数C和 分离超平面的权向量。对于任何个权向量v,使用如 RBF核的参数a,可写成参数组形式(C,o)。 PBB-GS 下方法选择随机分类 算法描述具体过程为:先采用基于交叉验证的网格搜索 首先选择一个具有单位协方差矩阵的球面高斯分 法( Grid Search)选择SVM参数(C,a),经过多次训练和 布Q,使得Q=Q(,p。其中形给定了中心点的方向,而 是从原点到中心的距离。其次,选择一个县有单位协 预测,生成不同的模型,再将PAC- Baves边界应川于SVM ,计算参数组(C,a)所对应的 PAC-Bayes边界,再基 方差矩阵的先验球面高斯分布P,该分布的中心在原点 服从这两个分布的分类就满足 PAC-Bayes边界,对于实于 PAC-Bayes边界理论,最后选取 PAC-Bayes边界值最 小的参数组作为SVM分类器的最优参数,从而实现模 例来说,就是公式(9)的形式。经验误差率Q表示为 型选择。 Q(w,us=E,[F(uy(x, y)) 算法1基于PAC- Bayes边界和网格搜索的SVM模 其中Em是对m个训练样本求均值,x,y)是SVM训练型选择方法(PBGS算法) 模型的标准化边缘,具体表示为: 输入训练数据文件,待预测文件 p》∵ d. k (12) 输出最优的(C,a) 步骤1初始化,读入训练数掂文件和待预测文件。 F(x)为计算标准正态分布某点的概率值的函数,表 步骤2采用网格搜索法初始化SVM参数C,) 示为 设C=C;,σ=0,其中C;∈{0,01.0.1,1,50,500} P(x) (13) 0.00001,0.001,0.1,100},选择一组(C,σ),基于5折交 F(x)=1-F(x (14)又验证方法,对训练数据使川SⅤM算法进行训练,产生 在SⅴM分类器中采用核函数,能使低维线性不可模型,再执行预测,计算预测的正确率和经验误差率 分的分类数据转化到高维线性可分的特征空间,这样就 步骤3调用PBB算法,将PAC- Baves边界应用于 能得到更容易计算和实现的形式。采用核函数后, SVM SVM算法,计算 PAC-Bayes边界。 分类器可写成下面的形式 步骤4转入步骤2,直到循环结東。 c(x)=sign(∑ak(x,x) 步骤5基于 PAC-Bayes边界最小化输出最优(C,a) (15 算法2PAC- Bayes边界的算法实现(PBB算法) 其屮a是SVM解决二次优化问题的·个参数,当训练 输入训练数据文件,待预测文件 完毕后,该参数的个数与攴持向量的数量相同。核函数 输出最优的PAC- Bayes边界,最优的m k表示为:k(x,x)=x)(x),x为支持向量。在采用 步骤1初始化,设 PAC-Bayes边界 PBbound=1,置 汤莉,赵政,宫秀军:基于PAC- Bayes边界理论的SVM模型选择方法 2015,51(6) 31 信度dela=0.1,精度cDs=0.001定义先验分布利后 表2封闭测试结果 验分布之间的距离为m,定义先验p和后验q的相对 数据集 (C,) PAC-Baycs边界确率 熵函数:KL(p,g)=px1n(p/q)+(1-p)xmn(1-p)(-q) (500,0.001)0.269229635 80.20 (50,0001)0.2866544980 步骤2读入训练数据文件和待预测文件,计算训练 (1,0.1) 0.2045190257 样本数量m和经验误差率Q。 500,0.001)0.3099295158 步骤3在区域[0.01,100以步长0.1搜索mu diabetes 0,0.001)0.3014707374 步骤4定义不等式(9)的右端为rght并进行计算 (50,0.1) 0.28724746l5 79.43 (1,0.1) 0.1122000319 right=(mu x mu/2 + In((m+ D)idelta))m ionosphere (50,0.1) 0.0493927860 99.72 步骤5采用二分法计算每个mu对应的 PRound, (50,0.1) 0.3665404556 75.65 且满足不等式(9),即k( QJPBbound)< right liver-disorde (500,0.1)0.3411816398 步骤6转入步骤3,直到循环结束。 (0.1,0.1) 0.0049652243 步骤7求得最优的m,能够使得 PRound最小 mushroon (0.01,0.1)0.0195273239 输出最优的m和最优的 Abound。 (1,0.001)00277636839 98.25 (1,0.1 0.0885341986 PBB算法实现 PAC-Bayes边界的计算,采用线性搜 sonar (500,0.001)0.2180657178 索参数mu,其算法复杂度为O(n)。而PBB-GS算法实 现基于网格搜索和PAC- Bayes边界的SVM模型选择 型,根据模型进行预测,求出预测的正确率和边界,部分 采网格搜索参数C,o,参数C有5种取值,参数有实验结果如表3。 4种取值,仅需5×4次简单迭代计算即可实现,其算法 表3开放测试结果 复杂度为OⅧmxn)。因此该算法具有参数选择准确简数据集C) PAC-Bayes边界正确率/% 便快速的优点。 500,0.001 germ (50,0.001)0.3423368220 81.00 (1,0.1) 0.4411321952 79.00 4实验结果及分析 (500,.0.001)0.406819304 4.1实验数据 50,0.001)0.3996415521 77.78 釆用UI数据集,进行模型选择实验。数据集的名 (50,0.1)0.3996415521 称,输入维度样本个数,如表1 (1,0.1) 0.3082057225 9143 ionosphere 0.2872380000 表1数据集信息 47047029 livcr-disorder 数据集类输入维度样本个数 (500,0.1)0.5486782496 71.01 erman 1000 (0.1,0.1) 0.0144429451 99.88 diabetes 768 mushroom (001,0.1)00672435743 ionosphere 34 (1,0.001)0.0472111038 97.91 livcr-disorder 2 (1,0.1) 0.4592228932 85.37 Sonar 112 8124 (500,0.001)0.5156195605 80.49 Sonar 2 208 在基于在折交又验证的网格搜索法的基础上,再基 4.2实验方法及结果分析 于PAC- Bayes边界值最小化,选择开放测试中PAC- Bayes 实验采用两种测试方法:封闭测试和开放测试。封边界值最小化的参数组作为SVM的模型参数,开放测 闭测试是对母个数据集的训练数据本身的测试,用亍体试中各数据集的最佳模型的边界及正确率见表4 现其训练的经验错误率。即取100%的数据进行训练, 長4最佳模型的边界及正确率 再以100%的数据进行测试。实验设为RBF核函数,采 数据集 (C. PAC- Baves边界正确率/o 用网格搜索法选择参数(C,σ,C∈{0.01,0.1,1,50,50), (50,0.001)0.342336822081.00 σ∈0.0001.0.01,0.1,100},共形成5×4个参数组,接 diabetes (50,0.001/0.1)0.3996415521 着在以下范围内做模型选择,部分实验结果如表2。 (50.0.1)0.28723800009286 开放测试是对测武集的测试,体现模型的泛化错误 (50.0.1) 0.47304702957826 率。采用五折交叉验证的网格搜索法选择参数,对于每 (0.1,0.1) 0.0144429451 9988 (1,0.1 0.4592228932 个训练子集,使用RBF核函数学习SVM分类器。从封 闭测试的20组C,a)屮选出任组参数,将之前分好的 从各数据集的实验结果可以得出,PAC- Bayes边界 个数据集的样本数据(80%)执行sSVM训练,产生模越低,对应的SVM模型分类的确率越高,即通过PAC 2015,51(6) Computer Engineering and Applications计算机工程与应用 Bayes边界最小化能找到最优的SⅤⅥ模型,因此基于 ample-compressed Gibbs classifiers[C]/Proc of the 22nd PAC- Bayes边界的SⅥM模型选择方法能够快速选择最 International Conference on Machine Learning. New York 优参数,进而得到更优的模型。该边界值叮作为SⅤM ACM Press,2005:481-488 模型选择的标准。从实验的结果中看到,有的参数组在9 Laviolette F, Marchand M.PAC-Bayes risk bounds for sto 封闭测试中有很高的正确率,但是开放测试中的正确率 chastic averages and majority votes of sample-compressed 却较低,相应的泛化误差边界也很高。这种情况产生的 classifiers [J] Journal of Machine Learning Research, 2007 原因考虑为惩罚系数C过大产生的过拟合情况,基本符 8:461-1487 合实验预计H标。综上,基于 PAC-Bayes边界的SvM10 Seldin y, Iishby N PAC-Bayesian generalization bound 模型选择方法(PBB-(S)是可行的,其优选出的参数能 for density estimation with application to co-clustering[C]// Proc of 1 2th International Conference on artificial intel 使SVM具有较高的泛化能力,并具有参数选择准确、简 igence and Statistics. Cambridge Mit Press, 2009: 472-479 便快速的优点,能有效改善SⅤM模型选择问题。 [11 Morvant E, Co s K, Ralaivola L PAC-Bayesian general ization bound on confusion matrix for multi-class clas 5结束语 ification[ CliProc of the 29th International Conference 本文研究了SVM的模型选择的相关内容,介绍了 on Machine Learning, 2012: 815-822 PAC-Bayes边界理论的内容和原理,分析了 PAC-Bayes[2] Amini m. laviolette f, Usunier n, transductive bound 边界在SⅤM上的可行性及其理论基础,将PAC- Bayes for the voted classifier with an application to semi-super 边界与基于交叉验证的网格搜索法相结合,进一步提 vised learning[c]iAdvances in Neural Information Pr 出了一种基丁PAC- Baves边界的SVM模型选择方法 cessing Systems 21.Cambridge: MIT Press, 2009: 65-72 (PBB-GS),最后实验证明该方法具有简便快速,准确选13] Parrado-Hernandez e, Armbruladze a. Shawe- Taylor j. 择参数的特点,能有效地改善SⅴM模型选择。使PAC PAC-Bayes bounds with data dependent priors[J] Journal Bayes边界在实际成用中发挥更大作用,是将来研究的 of Machine Learning Research, 2012, 13: 3507-3531 重要方向。 [14 Ralaivolia L, Szafranski M, Stempel G Chromatic PAC- Bayes bounds for non-Iid data: applications to ranking 参考文献: and stationary B-mixing processes[I]. Journal of Machine Learning Research, 2010, 11: 1927-1956. [1 Vapnik V.The nature of statistical learning theory [M]. Ber lin: Springer, 2000 [15]汪廷华支持向量机模型选择研究Φ]北京:北京交通大 [2] Valiant L A theory of the learnable[J]. Communications ol he ACM,1984,27(11):1134-1142 [16 Vapnik V, Chapelle O Bounds on crror expectation for [3 Mcallester D A.Some PAC-Bayesian theorems[]. Machine support vector machines[J]. Neural Computation, 2002,12 Learning,1999,37(3):355-363 9):2013-2036 14/ Langford J Tutorial on practical prediction theory for clas- [17] Chung K M, Kao W C,Sun T,et Radius margin silication.Journal of Machine Learning Research, 2005 bounds for support vector machines with the rBF ker- 6:273-306 nel[J]. Neural Computation, 2003, 15(11): 2463-2681 [5] Seeger MPAC-Bayesian generalisation error bounds for [18] Gold C, Sollich P Model selection for support vector Gaussian process classification []. Journal of Machine Learn machine classification [J] .Neurocomputing, 2003, 55: 221-249 ing Research,2003,3(2):233-269 119 Keerthi s SEfficient tuning of SVM hyperparameters 16 Herbrich R, Graepel TA PAC-Bayesian margin bound using radius/margin bound and iterative algorithms[J] for linear classifiers[J]. IEEE Transactions on Information IEEE Transactions on Neural Networks, 2002. 13(5) Theory2002,48(12):3140-3150 1225-1229 [7] Ambroladze A, Parrado-Hern E Shawe-Taylor I Tighter [20] Tang Li, Zhao Zheng, Gong Xiujun, et al. On the general- PAC-Bayes bounds[cli Advances in Neural Information ization of PAC-bayes bound for SvM linear classifier[C]/ Processing Systems 19. Cambridge: MIT Press, 2007: 9-16 Contemporary Research on E-business Technology and [81 Laviolette F, Marchand M. PAC-Bayes risk bounds for Strategy. Berlin: Springer, 2012: 176-186