矩优化Boosting算法

第28卷第12期模式识别与人工智能Vol.28 No. 122015年12月PR&AIDec. 2015矩优化Boosting算法刘川廖士中(天津大学计算机科学与技术学院天津 300072)摘要间隔分布是Boosting算法的关键,现有的间隔分布泛化误差界难以计算,限制Boosting算法的发展.基于此问题,文中提出直接优化间隔分布的矩优化Boosting算法( MOBoost).首先,推导基于间隔分布一阶矩和二阶矩的Boosting泛化误差界( Boosting的矩泛化界) ,直接刻画间隔分布对Boosting 的影响.然后,依据Boosting 的矩泛化界,给出Boosting的矩准则，在最大化间隔分布的一阶矩同时最小化间隔分布的二阶矩.最后,给出求解Boosting的矩准则凸二次优化问题的原始形式和对偶形式,为Boosting 矩准则提供有效的计算方法.理论分析与实验表明,MOBoost有效可靠.关键词Boosing, 间隔分布,矩,泛化误差,模型选择中图法分类号TP 181DOI 10. 16451/j. enki. ssn1003 6059.201512002Moment-Optimized Boosting AlgorithmLIU Chuan, LIAO Shi Zhong( School of Computer Science and Technology , Tianjin University , Tianjin 300072)ABSTRACTMargin distribution is critical to Boosting. However, the existing margin-based generalization errorbounds are too complicated to be used for the design of new Boosting algorithms. In this paper, amoment-optimized Boosting ( MOBoost ) algorithm is proposed with direct optimization of the margindistribution. Firstly, a generalization error bound for Boosting based on first and secondary moments ofthe margin distribution is derived to reveal the close relationship between margin distribution andgeneralization error. Then, a moment criterion for Boosting model selection is presented based on themoment generalization bound. The criterion maximizes the first moment and minimizes the second momentof the margin distribution simultaneously. Consequently, the primary and dual forms are formulated forsolving the convex quadratic program of the moment criterion for Boosting. Thus , an efcient computingmethod for the moment criterion is proposed. Theoretical analysis and experimental results show thatMOBoost is effective and reliable.Key Words Booting, Margin Distribution, Moment, Generalizaion Error, Model Selection*国家自然科学基金项目( No.61 170019)资助中国煤化工收稿日期:2015-05-12;修回日期:2015-07-09CNMH G作者简介刘川，男 ,1990年生，硕士研究生,主要研究方向为Boosting算法.居士+(旭以F有)，另,104年生,博士,教授,主要研究方向为人工智能应用基础、理论计算机科学. E-mail :szliao@ tju. edu. cn.1068模式识别与人工智能28卷1引言并不直观. Shen等[16] 证明Booting最大化非规范间隔期望的同时,最小化间隔分布的方差,但该证明Boosting算法是当前较成功的分类算法之一.建立在Boosting生成的弱分类器是相互独立这-该算法通过- - 系列弱分类器的线性组合产生强分类假设上.此外,Shivaswamy等17-8]受经验伯恩斯坦器,其中,弱分类器由弱学习算法产生,仅要求分类界的启发,提出方差正则化的Boosting 算法,但该性能强于随机猜测. Freund 等[' -2] 提出的AdaBoost算法依赖的泛化误差界忽略强分类器f与训练集s是一种实用的Boosting 算法，至今仍是常用的之间的关系,与实际情况并不相符.Boosting算法之- -.本文在Gao等(41工作的基础上，推导Boosting学者在如何解释Boosting算法的工作原理时关于经验间隔分布一阶矩和二阶矩的泛化误差界,依然存有争议,两种最有影响力的解释分别为统计并以经验间隔分布的二阶矩作为正则化因子,最大解释和间隔理论解释. Breiman[3] 和Friedman等[4化经验间隔分布的一- 阶矩,设计矩优化的Boosting将Boosting算法解释为函数空间中梯度下降的优算法(Moment-Optimized Boosting Algorithm,化,据此Mason等[5]提出AnyBoost Boosting 框架,MOBoost).同Gao等[14]基于期望方差的泛化误差界将Boosting扩展到回归问题，甚至非监督学习.统计相比,本文应用经验间隔分布的二阶矩而不是它的观点虽然对Boosting的发展做出巨大贡献,却无法替代统计量推导理论界,给出的理论界更能反映间解释Boosting对于过拟合的抵抗性.Schapire等[6]隔分布的特征.实验表明MOBoost有效可靠.提出的间隔理论是另一种通用解释.该理论首次给出关于间隔分布的泛化误差界,从而将Boosting算2基础知识法的成功归因于间隔分布的提高.Breiman[(3推导基于最小间隔的泛化误差界,比Schapire基于间隔令训练集分布的界更紧.由此, Breiman认为最小间隔比间隔S= {x;,y;}"分布更重要.优化最小间隔是凸优化问题,易计算，独立取自未知分布D(X x Y) ,其中,X为特征空间,这使得最大化最小间隔的策略受到广泛关注,如Y={- 1,1}. dt为给定的假设空间,Vh∈H是将Xarg-gv[3] 和LP-AdaBoost!7]等.映射到Y的弱分类器本文中,假设dH中分类器的个然而，大量实验表明，上述策略并未提高数有限,即Boosting的泛化性,甚至会降低泛化性,因此,间隔|#|=NJ <+∞.理论遭到严重质疑.尽管软间隔最大化Boosting算令C(H)为J4凸闭包的完备,即法表现出较佳性能[8-9] ,却无益于缓解间隔理论的争论.之后,Koltchinskii等[0-11利用拉德马赫及高.C(#)= {|s= Eath,a.≥0,Za.=1}.斯复杂度证实可提高Schapire 的间隔分布界,但并定义预测矩阵H∈QMxNn ,其中,Hq=h,(x)是不能证明这些新的泛化界比Breiman的最小间隔弱分类器h,(.)对训练样例x;的预测结果.为方便界更紧. Reyzin等[12复制Breiman的实验,不同的起见,记H;为H的第i行.是,他们采用决策树桩作为弱学习器.与决策树相Boosting 通过迭代T步建立-一个加法模型:比,决策树桩能控制模型复杂性,实验表明间隔分布比最小间隔更重要.f,(x)= 2 a,h,(x),近期, Wang等[13]提出均衡间隔界( Emargin),其中,h,(x)为第t步选出的“最佳”弱分类器,a,为比Breiman的最小间隔界更紧,为间隔解释提供新相应的权,的理论支撑,但考虑因素与Schapire及Breiman 不同. Gao等[14)利用改进的经验伯恩斯坦界[5),假设a.≥0,Za,=1.在Breiman等相同的工作条件下,证明关于间隔分由前面定义可知，模型f,(x)可等价表示为J4 中所布更紧的泛化界,应对Breiman 的质疑,再次肯定有分类器线性组合的形式: .间隔分布的核心作用.并且,Gao等[4]还推导关于中国煤化工间隔分布期望及方差的泛化误差界,为设计新的Boosting 算法指明方向.然而,尽管文献[14]的期MYHCNMHG_对样例(xy)，问隔YJr(%;)反映正确分类与望方差界中出现- -项自然反映间隔方差,但方差项误分类的弱分类器的权值差异,即12期川等:矩优化 Bosting算法1069y.f(x})=. 2 β,-_ 2 β。3Boosting的矩泛化界对训练集S,Prs(xf+(x) <θ)可看作θ∈[-1,1]上的一个分布,即间隔分布.在Gao等(41工作的基础上,本文进- -步给出基于经验间隔分布,Cao等[4)] 给出如下泛Boosting关于经验间隔分布一阶矩和二阶矩的泛化化界.误差界,称为Boosting的矩泛化界.定理1若训练集引理对任意正整数k,示性函数S= {(x,y)}"抓x)0,投票分类器f以至少1-8的证明分情况讨论概率满足1)当xf(x) < θ时，(1 +θ-xrf(x))*≥1*=1 =Mv) θ时,由-1≤yf(x)≤1,0 <θ≤1,亚十了亚。聚[(3)<0]|.得3M1 +θ-xf(x)≥0,其中μ= gIn M In(2N#) + ln-QH2Ng(1 +θ-x(x))*≥0=gu0<在相同假设下，定理1给出的泛化界比综上所述,对任意正整数k,m) 0,投票分类器f至少以1-8的满足M≥5,对Vδ > 0,投票分类器f以至少1-8的Pr[xf(x) <0]≤Pr[x(x) <0]≤而+_ inf. |Pr([x(x) <0] +两+. inf.θe(0,1] '(n+/籍的+亚招座),μ= fIn M ln(2Ny) + ln2N#”8证明由引理可得μ=1441n M ln(2Nn)+In(2%).Pr[xf(x) < 0]02(0)=PLu(>) <0]P[x(x) >号].ly1x) 0,Pr[xf(x)中国煤化工)=M，(1)因此，定理2表明，最大化Es[x(x)]且最小化Pr[yf(xMHCNMH Gi(.)可提高Boosting的泛化性.≤(1 +0)2-2(1 +0)Es[x(x)] + Es[(x(x))门]1070模式识别与人工智能28卷(2)s.t.2 uyh.(x)≤s.(7)将式(1)和式(2)分别代人定理1右端的Pr[xf(x) < ]可见，Boosting的矩准则的求解问题是-个凸中,即得证定理.二次优化问题.与定理2给出的泛化界相比,定理3给出的泛化界不含Boosting的矩优化算法Pr[xf(x) < 0]项,形式简洁且只相关于经验间隔的一阶矩和二阶本节根据Boosting的矩准则，设计Boosting 的矩.因而,定理3给出的泛化误差界更易计算,并且矩优化算法.可直接反映间隔分布对泛化性的影响.当弱分类器较少时，可按式(5)"直接求解Boosting的矩准则;当弱分类器较多时，可应用对4 Boosting的矩准则偶式(7)并采用列生成算法求解Boosting 的矩准则.依据Boosting矩泛化界给出Boosting算法的值得注意的是,式(7)也可看作是一种正则化优化准则,称为Boosting 的矩准则.因子下的软间隔LPBoostf8. 不同的是u不再是一由定理3可知,增加经验间隔的-阶矩或减少个分布由拉格朗日对偶性,为使原问题收敛更快，经验间隔的二阶矩,可提高Boosting的泛化性.据仅需寻找违背式(7)约束不等式最严重的弱分类此可得到如下准则:器,即max(E[)f(x)] - ηE{[(x(x)])，(3)arg max 2 uy.h(x,).(8)其中,η >0,用于给出Es[x(x)]与E([(x(x)]此时选择的弱分类器h与Boosting -致.的权衡.式(3)等价于综上所述,可设计MOBoost,具体步骤如下.max(ZyH,a -点(y,H,a)算法MOBoost输入训练集S= {(x;,y,) },迭代次数T,正则s.t. 2a;=1,a;≥0,i=1,2,,M.化参数η > 0输出F;(x)= sgn[f,(x)] ,其中ρ=[ρ,r,",pm]'∈[- 1,1]",p:=yHa,f(x)= E a,h,(x)并令1,为以y: ,y.,.. ,Yu为对角线元素的对角阵,有step 1初始化训练集的权值分布ρ =I,Ha.则式(4)可改写为u;=一, i= 1,2,.. ,M.minηp'p - 1'p,(5)step2生成 T个弱分类器s.t. a≥0, 1'a=1,ρ =I,Ha.whilet= 1: T上式显然是一个凸二次优化问题引人变量r,s,u,可得式(5)的拉格朗日函数:由式(8)生成弱分类器h;L(a,ρ,r,s,u)=ηρρ-1p-r"a+s(1'a-1) +增加h,到原问题式(5),由其对u'(ρ - I,Ha),应的对偶式(6)更新u.其中r≥0,可得式(5)的对偶形式:max | -s(u- 1)"(u-1)step3根据对偶性得 到原问题式(5)的解a,4η~(6)算法结束s.t. H'I,u ≤s1.MOBoq中国媒化工均值较大且二展开(u-1)"(u- 1),式(6)可进-步改写为阶矩较小,H.CNMHG大的间隔,可给min|s-2-1'u+一u"u,出直觉上“好的问隔分仰.在求解原始/对偶问题的二次优化过程中,对.12期刘川等:矩优化 Boosting 算法1071应的矩阵通常是半正定的而不是正定的,故需在矩0.03 ,0.05 ,0.08 ,0.10,0.12,0.13 ,0.15.阵的对角线加上δ > 0的扰动.表2给出3种Boosting算法的误差,最好的结果标注为黑体.由表2可见,在大部分数据集上,6实验及结果分析MOBoost有更好的预测性能.表1实验数据集本节通过实验验证MOBoost的有效性和可Table 1 Experimental datasets靠性.数据集类别属性个数样本数实验环境如下: Intel Core2 Quad Q8200Ionosphere342.33 CHz CPU,内存4.0 GB;软件R3. 0.0;标准数768据集选自UCI等数据库.Banknote1371为控制分类器的复杂性,均采用决策树桩作为569弱分类器,即仅包含--个节点的决策树对比算法包German201000括AdaBoost和LPBoost.实验采用13个标准数据Diabetes68Heart-c303集(见表1) ,按照4: 3: 3的比例随机抽取数据作为Heart-h94训练集、验证集和测试集,测试迭代数为100和200Heart-statlog270时3种Boosting算法的性能每次实验均重复10次Hepatitis55并取平均值.均衡参数Labor657Wpbe .99LPBoost的参数取值为0. 001 ,0. 005 ,0.01 ,0.02 ,Colic表2 AdaBoost、LPBoost和MOBoost的测试误差Table 2 Testing errors of AdaBoost , LPBoost and MOBoostT= 100T= 200AdaBoostLPBoostMOBoost9.62土2.05 9.43 +1.33 7.55 +1.49 9.43 +1.89 10.57 +2.70 13.04 +2. 58Pima26.32 +2.30 31.34 +1.58 23.73 +1.2028.09 +0.79 30.00 +1.7727.22 +2. 560.63 +0.44 0.63 +0.53 0.24 +0. 171.12 +0.68 1.02 +0.90 0.58 +0.49Wdbc5.38 +1.72 5.61 +2.13 5.38 +0.765.50 +1.06 5.96 +0.494.09 +0.92 .26.27 +1.40 26.80 +3.48 26.00 +0.94 27.07 +2.88 29.33 +3.47 26.93 +1.1625.97 +4.26 27.72 2.86 25.37 +2.38 27.53 +3.07 29. 16 +4.6625.31 +2.4722.20 +5.68 21.32 +5.69 20.88 +3.01 21.76 +2.51 22.42 +5.0120.44士+4. 7019.55 +4.53 18.88 +3.59 21.57 +3.68 20.00 +3.84 21.80 +4.3220.00 +2.5721.48 +1.87 20.99 +6.42 19.51 +3.94 19.75 +5.01 18.99 +4.86 15.67 +3.4620.00 +7.15 21.70 +4.61 19.15 +3.36 20.43 +4.41 16.60 +1.7813.19 +4.6125.56 +6.33 27.56 +9.72 24.44 +8.43 19.24 +6.80 23.33 +7.3122.56 +7.52Wpbe23.00 +3.80 25.67 +1.49 24.33 +2.79 26.33 +4.62 24.67 +5.45 26.00 +3.21Colice18.20 +3.45 17.66 +1.87 16.58 +1.37 21.80 +3.90 20.36 +2.07 16.76 +3.35图1给出均衡参数η对测试误差的影响.当η图2给出迭代数T =100时AdaBoost与MOBoost取值过小或过大时,算法倾向于只考虑经验间隔分在Wdbe、German与Diabetes这3个数据集上的累布的一阶矩或二阶矩,都不全面,测试误差较大.当计间隔分布对比，其他数据集上有相似结果.η=30 ,,.,30MOBoost的间隔分布曲线通常位于AdaBoost右下时,同时兼顾经验间隔分布的-阶矩和二阶矩，给出方,这表明MOBoost比AdaBoost具有更好的间隔较好的经验间隔分布,此时的测试误差较小且较分布,与之中国煤化工稳定.上述实YH |c N M H c效性和可靠性..1072模式识别与人工智能28卷.0.250.380.140.36-0.34-删0.10糊0.32↑0.15-e 0.08路0.30-冕0.06冕0.28-0.26 t0.05 L0.24-268-log,nlog,7(a) lonosphere(b) Pima(c) Banknote0.090.36r0.36*0.08g 0.070.32[删0.32-s 0.06↑g 0.30-当0.30-冕0.050.280.040.260.032δ246.802.468log.7(d) Wdbc(e)Germnan(f) Diabetes图1 η对泛化误差的影响Fig. 1 Effeet of η on generalization errors1.1.0p0.8至0.6-0.6-否0.6-于0.4本0.4-0.2-MOBoost0.. MOBoost一MOBoost |AdaBoost-- AdaBoost-0.2 0 0.2 0.4 0.6 0.81.0-0.2 0 0.2 0.4 0.6 0.8 1.0间隔(a) Wdbe(b)German(c) Diabetes图2 MOBoost 与AdaBoost累计间隔分布的对比Fig. 2 Comparison of cumulative margin distibution between MOBoost and AdaBoost7,结束语一阶矩和二阶矩的Boosting 的矩泛化界,给出最大化经验间隔分布期望同时最小化经验间隔分布二阶间隔在监督学习和非监督学习中都起着重要作矩的Boosting的矩准则,设计基于Boosting的矩优化用.直接应用间隔最大化的算法，如支持向量机的MOBoost算法,实验验证MOBoost比AdaBoost和(SVM)和谱聚类,可得到较好的泛化性.间隔分布LPBoost更有效.该项工作给出一个完整的Boosting的好坏也影响算法性能,因此,基于间隔分布的算法算法设计的经验间隔分布优化理论与方法,也为进受到广泛关注(19-21].然而,关于间隔分布至今尚未-步研究其他学习算法的间隔分布优化理论与方法有适用于学习算法设计的理论、准则和方法.提供有价值的参考.矩是随机变量的重要统计特征.本文提出经验下一步中国煤化工定性,给出基于间隔分布矩优化Boosting算法,推导基于经验间隔经验间隔分MHC N M H G的泛化误差界..12期刘川等:矩优化 Boosting算法1073参考文献Annals of Stistis, 2002, 30(1): 1-50[11] Koltchinskii V, Panchenko D. Complexities of Convex Combina-[1] Freund Y, Schapire R E. Experiments with a New Boosting Algo-tions and Bounding the Generalization Error in Classfication. Therithm // Proc of the 13th Intemational Conference on MachineAnnals of Stistis, 2005 , 33(4): 1455 -1496Leaming. Bari, ltaly, 1996: 148-156[12] Reyzin L, Schapire R E. How Boosing the Margin Can Also Boost[2] Freund Y, Schapire R E A Decision -Theoretic Gencrlizaion of On-Cassifer Complexity /1 Proe of the 23rd Inemational Conferenceline Ieaming and an Application to Boosting. Jourmal of Computeron Machine Leaming. Pttsburgh, USA, 2006: 753-760and System Sciences, 1997, 5s(1): 119-139[13] WangL W, Sugjyama M, JingZ X, et al. A Refined Margin Ana-[3] Breiman L. Prediction Games and Arcing Algorithms. Neural Com-lysis for Boosting Algorithms via Equilibrium Margin. Joumal ofputation, 1999, 11(7): 1493-1517Machine Leaning Research, 2011, 12: 1835-1863[4] Friedman J H, Hastie T, Tibshirani R. Additive Logstic Regres- [14] Gao w, ZhouZ H. On the Doubt about Margin Explanation ofsion: A Statistical View of Boosting. The Annals of Statistics, 2000Bosting. Aricial Ieligence, 2013, 203: 1-1828(2): 337-407[15] Maurer A, Pontil M. Empincal Bernstein Bounds and Sample Va-[5] Mason L, Baxter J, Bartett P, et al. Boosing.Algorithns as Gra-riance Penalzation[ EB/OL]. [ 2015 -04 - 30]. htp://www.dient Descent // SollaS A, Leen T K, Muller K, eds. Advances inandreas -maurer. eu/svp-final. pdiNeural Inomation Processing Systems 12. Cambridge, USA: MIT[16] Shen C H, Li H X. Boosting through Optimization of Margin Disti-Press, 199: 512-518butions. IEEE Trans on Neural Networks, 2010, 21(4): 659-666[6] Schapire R E, Freund Y, BarlettP, et al. Boosting the Margin: A [17] Shivaswamy P K, Jecbara T. Empirical Bemstein Boosting // ProcNew Explanation for the Efectiveness of Voting Methods. Thof the 13th Intemational Conference on Artificial Inelligence andAnnals of Stisics, 1998, 26(5): 1651-1686Statistics. Sardinia, ltaly, 2010, IX: 733-740[7] Crove A J, Schuurmans D. Boosting in the Limit: Maximizing the [18] Shivaswamy P K, Jebara T. Variance Penalizing Adaboost //Margin of Learmed Ensembles /1 Proe of the 15th National Confe-Shawe-TaylorJ, Zemel RS, Bartlett P L, et al. eds. Adrancesrence on Arificial Ielligence. Madison, USA, 1998: 692 -699in Neural Informnation Processing Systens 24. Cambridge, USA:[8] Demiriz A, Bennett K P, Shawe-Taylor 」. Linear ProgranmingMIT Press, 2011: 1908-1916Boosting via Colunn Generation. Machine Leamning. 2002, 46(1): .[19] Garg A. Roth D. Margjin Distribution and Leaming Algorithms //225-254Proc of the 20th Intemational Conference on Machine Leaming.[9] FangY K, Fu Y, ZhouJL, et al. Selective Boosting Algorihm forWashington, USA, 2003: 210-217Maximizing the Soft Margin. Joumal of Software, 2012, 23(5):[20] Liu C, Liao s z. Boosting via Appraching Optimal Margin Distrbu-1132-1147 (in Chinese).tion /1 Proc of the 19th Pacific-Asia Coference on Knowledge Dis-(方育柯,傅彦,周俊临,等基于选择性集成的最大化软间隔算covery and Data Mining. Ho Chi Minh, Vietnam, 2015: 684-695法.软件学报, 2012, 23(5): 1132-1147)[21 ] Zhang T, Zhou z H. Large Margin Distribution Machine // Proc of[10] Koltchinski V, Panchenko D. Empincal Margin Distrbutions andthe 20th ACM SIGKDD Conference on Knowledge Discovery andBounding the Generalization Error of Combined Casfers. TheData Mining. New York, USA, 2014: 313-322中国煤化工MHCNMH G