《选择性集成【特制材料】》由会员分享,可在线阅读,更多相关《选择性集成【特制材料】(27页珍藏版)》请在金锄头文库上搜索。
1、选择性集成选择性集成(Selective Ensemble)周志华周志华http:/ 南京大学计算机软件新技术国家重点实验室泛化:generalization泛化能力越强,处理新数据的能力越好泛化能力是机器学习关注的基本问题之一提高泛化能力是永远的追求泛化能力集成学习(Ensemble Learning)是一种机器学习范式,它使用多个(通常是同质的)学习器来解决同一个问题集成学习 问题 . . 问题集成学习中使用的多个学习器称为个体学习器当个体学习器均为决策树时,称为“决策树集成”当个体学习器均为神经网络时,称为“神经网络集成” 由于集成学习技术可以有效地提高学习系统的泛化能力,因此它成为国际
2、机器学习界的研究热点,并被国际权威 T.G. Dietterich 称为当前机器学习四大研究方向之首T.G. Dietterich, AIMag97集成学习的重要性问题:对20维超立方体空间中的区域分类左图中纵轴为错误率从上到下的四条线分别表示:平均神经网络错误率最好神经网络错误率两种神经网络集成的错误率令人惊奇的是,集成的错误率比最好的个体还低 L.K. Hansen & P. Salamon, TPAMI90集成学习的用处集成学习技术已经在行星探测、地震波分析、Web信息过滤、生物特征识别、计算机辅助医疗诊断等众多领域得到了广泛的应用只要能用到机器学习的地方,就能用到集成学习期望结果个体1
3、 (精度33.3%)个体2 (精度33.3%)个体3 (精度33.3%)集成(精度33.3%)投票个体必须有差异期望结果个体1 (精度33.3%)个体2 (精度33.3%)个体3 (精度33.3%)集成 (精度0%)投票个体精度不能太低个体学习器越精确、差异越大,集成越好A. Krogh & J. Vedelsby, NIPS94如何构建好的集成既然多个个体的集成比单个个体更好,那么是不是个体越多越好?更多的个体意味着: 在预测时需要更大的计算开销,因为要计算更多的个体预测 更大的存储开销,因为有更多的个体需要保存个体的增加将使得个体间的差异越来越难以获得个体越多越好吗?Many Could
4、be Better Than All:在有一组个体学习器可用时,从中选择一部分进行集成,可能比用所有个体学习器进行集成更好Z.-H. Zhou et al., AIJ02从一组个体学习器中排除出去的个体(k)应满足:分类选择性集成回归遗憾的是,上述公式在解决实际问题时难以直接使用 .w1w2 . wn利用遗传算法进化 .遗传算法选择随机生成若干权向量,权向量的每个分量对应了一个个体学习器,这些权向量被遗传算法进化,得到一个最优权向量,它表示了各个体学习器在构成集成时的“重要性”,据此进行个体的选择假设 w2 1/n 分类:有排除的投票 回归:有排除的平均为了证明选择性集成学习的可操作性,我们提
5、出了GASEN算法w11w12 . w1nw21w22 . w2nwm1wm2 . wmn随机生成一个权向量群体 . . . .Z.-H. Zhou et al., AIJ02GASEN(基于遗传算法的选择性集成学习算法)(基于遗传算法的选择性集成学习算法)与著名的集成学习算法Bagging和Boosting相比,GASEN 获得了更高的(或相当的) 精度,而且使用的个体学习器少得多 (回归:19% (3.71/20);分类:36% (7.10/20.0) Z.-H. Zhou et al., AIJ02实验结果给定学习目标和训练集规模, bias 度量了学习算法的平均估计结果与目标的接近程度
6、variance 度量了在同样规模的不同训练集上,学习算法的估计结果的扰动程度以往研究表明,Bagging主要减小variance,而Boosting主要减小bias E. Bauer & R. Kohavi, MLJ99; L. Breiman, TechRep96我们采用的分解机制为 R. Kohavi & W.H. Wolpert, ICML96Bias-Variance分解在回归任务中,GASEN在减小bias和variance方面都优于Bagging和Boosting在分类任务中,GASEN在减小bias方面优于Bagging,在减小variance方面优于Boosting GASE
7、N的成功在于其既可以有效地减小bias,又可以有效地减小varianceZ.-H. Zhou et al., AIJ02回归分类biasvariance分解结果生物特征识别:选择性集成的一个应用Bill Gates: 以人类生物特征进行身份验证的生物识别技术,在今后数年内将成为IT产业最为重要的技术革命人脸 脸部热量图 指纹 手形 手部血管分布 虹膜 视网膜 签名 语音 人脸识别人脸识别因识别方式友好、可隐蔽而备受学术界和工业界关注(但人脸识别不是万能的)自动人脸识别系统所谓自动人脸识别系统,是指不需要人为干预,能够自动获取人脸图像并且辨别出其身份的系统 一个自动人脸识别系统至少要包含三个部分
8、,即数据采集子系统、人脸检测子系统和人脸识别子系统 “人脸识别”有时是指整个自动人脸识别系统所做的工作,有时是指人脸识别子系统所做的工作数据采集子系统人脸识别子系统人脸检测子系统自动人脸识别系统识别结果:He is !本征脸(eigenfaceeigenface)方法是人脸识别的基准技术,并已成为事实上的工业标准该方法基于主成分分析(PCA)PCA是将分散在一组变量上的信息集中到某几个综合指标(主成分)上的数学方法,实际上起着数据降维的作用,并保证降维过程最大化保留原数据的差异这对最大化类间差异(即不同人之间的差异)并最小化类内差异(即同一人的不同图像间的差异)很有效用PCA将2维数据降到1维
9、的例子,绿色点表示二维数据,PCA的目标就是找到这样一条直线,使得所有点在这条直线上的投影点之间的平均距离最大。也就是最大化地保留了原数据的差异性本征脸方法u高N1,宽N2的图像P 可以转化为N1N2维的向量xu线性变换: ,其中y的维数m 远远小于x的维数nu寻找W 使得y 最大程度地保持x原有的差异(variance)uW 的求法:1) 样本集的总体散布矩阵: 2) 求出C 的本征向量和对应的本征值; 3) 将本征值排序为 ,它们对应的本征向量分别为4) 取最前面的m个本征向量 组成变换矩阵W 本征脸方法u直接计算C 的本征值和本征向量是困难的,可以通过对矩阵 做奇异值分解间接求出um值的
10、选择:如果将本征向量恢复成图像,这些图像很像人脸,因此称为“本征脸” M. Turk & A. Pentland, JCN91本征特征(eigenfeatureeigenfeature)方法利用PCA分析眼、鼻、嘴等局部特征,即本征特征方法 R. Brunelli & T. Poggio, TPAMI93 A. Pentland et al., CVPR94这实际上相当于:为若干重要的特征建立本征空间,然后将多个本征空间集成起来本征脸 vs. 本征特征本征脸利用全局特征,本征特征利用局部特征,二者各有优势待识别图像本征脸识别结果本征特征识别结果 A. Pentland et al., CVPR
11、94本征脸 vs. 本征特征(2)(1)(3)(4)难题能否自动确定:该用哪些特征?(眼睛?鼻子?嘴?)特征的确切位置在哪儿?(从哪儿到哪儿算眼睛?)将二者结合,可以得到更好的识别效果同样,这实际上相当于:为若干重要的特征建立本征空间,然后将多个本征空间集成起来由于嘴部受表情影响很严重,因此未考虑嘴部特征考虑 ,选择的原则应该是:将人脸图像中所有的矩形区域都看做一个可能的特征,这样,在每一个矩形区域都建立一个本征空间,最后将重要的本征空间集成起来图像中包含的矩形区域的数量是非常巨大的(例如一幅3431的图像包含的矩形区域就多达295,120个),不可能使用所有的本征空间组成集成,但可以运用选择
12、性集成思想,从中选择出部分本征空间组成集成 本征空间本身的误差较小 本征空间之间的差异较大(即互补性较大)SEME(选择性多本征空间集成算法)(选择性多本征空间集成算法)l给定k个人脸图像样本(每人两张图像,一张为gallery图像,另一张为probe图像),算法将从所有N个矩形(R1, R2, , RN.)中选择出m个lFor i = 1, 2, , N:1以gallery图像为训练集,在Ri 上训练出一个本征空间2利用该本征空间识别所有的probe图像,记下识别率ril将Ri按照相应的ri从大到小排序lS = R1,A = R2, , Rn,这里 m n NlFor t = 1, 2, ,
13、 m-1:1对A中的每一个矩形Ri,计算Ri 能够识别正确,而S中至少有一个矩形识别错误的probe图像的数目,记为ci2找到具有最大纠正误识数目ct的矩形Rt3将Rt从A中删除并添加到S中l集成与S中m个矩形相对应的本征空间用于人脸识别选择误差小的矩形特征选择差异大的矩形特征SEME(选择性多本征空间集成算法)(选择性多本征空间集成算法) X. Geng & Z.-H. Zhou, unpub04实验结果 X. Geng & Z.-H. Zhou, unpub04FERET人脸数据库上的结果(3)(2)(1)(4)(2)(1)(3)(4)待识别图像出现在算法返回的前Rank个图像中SEME选择的特征本征脸+本征特征所用的特征SEME的可扩展性SEME的训练(计算)开销很大,但只需训练一次 X. Geng & Z.-H. Zhou, unpub04将FERET人脸数据库上选择出的本征空间集成直接用于ORL(左)和BioID(右)这两个人脸数据库的结果总结:选择性集成选择性集成的思想:利用多个个体,并通过对个体进行选择,可以获得更好的结果 问题 . .个体解个体解个体解选择性集成的思想可以用到更多的领域中去选择的基本原则:个体的效用高、差异大谢谢!