flash网站设计概述,网站列表页是啥,cctv5体育现场直播,wordpress 电商 插件下载机器学习 第8章-集成学习
8.1 个体与集成
集成学习(ensemble learning)通过构建并结合多个学习器来完成学习任务#xff0c;有时也被称为多分类器系统(multi-classifersystem)、基于委员会的学习(committee-based learning)等。
图8.1显示出集成学习的一般结构:先产生一组“…机器学习 第8章-集成学习
8.1 个体与集成
集成学习(ensemble learning)通过构建并结合多个学习器来完成学习任务有时也被称为多分类器系统(multi-classifersystem)、基于委员会的学习(committee-based learning)等。
图8.1显示出集成学习的一般结构:先产生一组“个体学习器”(individual learner)再用某种策略将它们结合起来。个体学习器通常由一个现有的学习算法从训练数据产生例如C4.5决策树算法、BP神经网络算法等此时集成中只包含同种类型的个体学习器例如“决策树集成中全是决策树“神经网络集成”中全是神经网络这样的集成是“同质的(homogeneous)。同质集成中的个体学习器亦称“基学习器”(base learner)相应的学习算法称为“基学习算法”(base learning algorithm)。集成也可包含不同类型的个体学习器例如同时包含决策树和神经网络这样的集成是“异质”的(heterogenous)。异质集成中的个体学习器由不同的学习算法生成这时就不再有基学习算法相应的个体学习器一般不称为基学习器常称为“组件学习器”(component learner)或直接称为个体学习器 集成学习通过将多个学习器进行结合常可获得比单一学习器显著优越的泛化性能。这对“弱学习器”(weak learner)尤为明显因此集成学习的很多理论研究都是针对弱学习器进行的而基学习器有时也被直接称为弱学习器。但需注意的是虽然从理论上来说使用弱学习器集成足以获得好的性能但在实践中出于种种考虑例如希望使用较少的个体学习器或是重用关于常见学习器的一些经验等人们往往会使用比较强的学习器。
8.2 Boosting
Boosting是一族可将弱学习器提升为强学习器的算法。这族算法的工作机制类似:先从初始训练集训练出一个基学习器再根据基学习器的表现对训练样本分布进行调整使得先前基学习器做错的训练样本在后续受到更多关注然后基于调整后的样本分布来训练下一个基学习器如此重复进行直至基学习器数目达到事先指定的值T最终将这T个基学习器进行加权结合
Boosting族算法最著名的代表是AdaBoost其描述如图 8.3 所示其中 y i ∈ − 1 , 1 y_i∈{-1,1} yi∈−1,1f是真实函数。
AdaBoost算法有多种推导方式比较容易理解的是基于“加性模型”(additive model)即基学习器的线性组合 H ( x ) ∑ t 1 T α t h t ( x ) H(x)∑^T_{t1}\alpha _t h_t (x) H(x)t1∑Tαtht(x) 来最小化指数损失函数 l e x p ( H ∣ D ) E x ∼ D [ e − f ( x ) H ( x ) ] l_{exp}(H|D)E_{x\sim D}[e^{-f(x)H(x)}] lexp(H∣D)Ex∼D[e−f(x)H(x)] 若 H ( x ) H(x) H(x)能令指数损失函数最小化则考虑对 H ( x ) H(x) H(x)的偏导 ∂ l e x p ( H ∣ D ) ∂ H ( x ) − e − H ( x ) P ( f ( x ) 1 ∣ x ) e H ( x ) P ( f ( x ) − 1 ∣ x ) {\partial l_{exp}(H|D)\over \partial H(x)}-e^{-H(x)}P(f(x)1|x)e^{H(x)}P(f(x)-1|x) ∂H(x)∂lexp(H∣D)−e−H(x)P(f(x)1∣x)eH(x)P(f(x)−1∣x) 令其为0可得 H ( x ) 1 2 l n P ( f ( x ) 1 ∣ x ) P ( f ( x ) − 1 ∣ x ) H(x){1\over 2}ln{P(f(x)1|x)\over P(f(x)-1|x)} H(x)21lnP(f(x)−1∣x)P(f(x)1∣x) 则有 s i g n ( H ( x ) ) a r g m a x y ∈ { − 1 , 1 } P ( f ( x ) y ∣ x ) sign(H(x))arg max_{y∈\{-1,1\}}\quad P(f(x)y|x) sign(H(x))argmaxy∈{−1,1}P(f(x)y∣x) 这意味着 sign(H())达到了贝叶斯最优错误率。换言之若指数损失函数最小化则分类错误率也将最小化这说明指数损失函数是分类任务原本0/1损失函数的一致的(consistent)替代损失函数。理想的基学习器为 h t ( x ) a r g m i n h E x ∼ D t [ I ( f ( x ) ≠ h ( x ) ) ] h_t(x)\underset{h}{arg\: min}E_{x\sim D_t}[\mathbb{I}(f(x)\neq h(x))] ht(x)hargminEx∼Dt[I(f(x)h(x))] 理想的基学习器将在分布 D t D_t Dt下最小化分类误差。
Boosting算法要求基学习器能对特定的数据分布进行学习这可通过“重赋权法”(re-weighting)实施即在训练过程的每一轮中根据样本分布为每个训练样本重新赋予一个权重对无法接受带权样本的基学习算法则可通过“重采样法”(re-sampling)来处理即在每一轮学习中根据样本分布对训练集重新进行采样再用重采样而得的样本集对基学习器进行训练。一般而言这两种做法没有显著的优劣差别。
8.3 Bagging与随机森林
8.3.1 Bagging
Bagging[Breiman,1996a]是并行式集成学习方法最著名的代表。从名字即可看出它直接基于自助采样法(bootstrap sampling)给定包含m个样本的数据集我们先随机取出一个样本放入采样集中再把该样本放回初始数据集使得下次采样时该样本仍有可能被选中这样经过m次随机采样操作我们得到含m个样本的采样集初始训练集中有的样本在采样集里多次出现有的则从未出现。
照这样我们可采样出T个含m个训练样本的采样集然后基于每个采样集训练出一个基学习器再将这些基学习器进行结合。这就是Bagging的基本流程。在对预测输出进行结合时Bagging 通常对分类任务使用简单投票法对回归任务使用简单平均法。若分类预测时出现两个类收到同样票数的情形则最简单的做法是随机选择一个也可进一步考察学习器投票的置信度来确定最终胜者。Bagging 的算法描述如图8.5所示 从偏差-方差分解的角度看Bagging 主要关注降低方差因此它在不剪枝决策树、神经网络等易受样本扰动的学习器上效用更为明显。
8.3.2 随机森林
随机森林(Random Forest,简称RF)是Bagging 的一个扩展变体。RF在以决策树为基学习器构建Bagging集成的基础上进一步在决策树的训练过程中引入了随机属性选择。具体来说传统决策树在选择划分属性时是在当前结点的属性集合(假定有d个属性)中选择一个最优属性而在RF中对基决策树的每个结点先从该结点的属性集合中随机选择一个包含k个属性的子集然后再从这个子集中选择一个最优属性用于划分。这里的参数k控制了随机性的引入程度:若令 k d kd kd则基决策树的构建与传统决策树相同若令 k 1 k1 k1则是随机选择一个属性用于划分一般情况下推荐值 k l o g 2 d klog_2d klog2d
随机森林简单、容易实现、计算开销小令人惊奇的是它在很多现实任务中展现出强大的性能被誉为“代表集成学习技术水平的方法”。可以看出随机森林对 Bagging 只做了小改动但是与 Bagging 中基学习器的“多样性”仅通过样本扰动(通过对初始训练集采样)而来不同随机森林中基学习器的多样性不仅来自样本扰动还来自属性扰动这就使得最终集成的泛化性能可通过个体学习器之间差异度的增加而进一步提升。
随机森林的收敛性与 Bagging相似。但随机森林的训练效率常优于Bagging因为在个体决策树的构建过程中Bagging使用的是“确定型”决策树在选择划分属性时要对结点的所有属性进行考察而随机森林使用的“随机型”决策树则只需考察一个属性子集
8.4 组合策略
学习器结合可能会从三个方面带来好处:
首先从统计的方面来看由于学习任务的假设空间往往很大可能有多个假设在训练集上达到同等性能此时若使用单学习器可能因误选而导致泛化性能不佳结合多个学习器则会减小这一风险
第二从计算的方面来看学习算法往往会陷入局部极小有的局部极小点所对应的泛化性能可能很糟糕而通过多次运行之后进行结合可降低陷入糟糕局部极小点的风险
第三从表示的方面来看某些学习任务的真实假设可能不在当前学习算法所考虑的假设空间中此时若使用单学习器则肯定无效而通过结合多个学习器由于相应的假设空间有所扩大有可能学得更好的近似。图8.8给出了一个直观示意图 假定集成包含 T T T个基学习器 h 1 , h 2 , . . . , h T {h_1,h_2,...,h_T} h1,h2,...,hT其中 h i h_i hi在示例 x x x上的输出为 h i ( x ) h_i(x) hi(x)。本节介绍几种对 h i h_i hi进行结合的常见策略
8.4.1 平均法
对数值型输出 h(æ)€R最常见的结合策略是使用平均法(averaging)
其中 简单平均法 H ( x ) 1 T ∑ i 1 T h i ( x ) H(x){1\over T}∑^T_{i1}h_i(x) H(x)T1i1∑Thi(x) 加权平均法 H ( x ) ∑ i 1 T w i h i ( x ) H(x)∑^T_{i1}w_ih_i(x) H(x)i1∑Twihi(x) 其中 w i w_i wi是个体学习器 h i h_i hi的权重通常要求 w i ≥ 0 ∑ i 1 T w i 1 w_i≥0∑^T_{i1}wi1 wi≥0∑i1Twi1
8.4.2 投票法
对分类任务来说学习器 h i h_i hi将从类别标记集合 { c 1 , c 2 , . . . , c N } \{c_1,c_2,...,c_N\} {c1,c2,...,cN}中预测出1个标记最常见的结合策略是使用投票法(voting)
为便于讨论我们将 h i h_i hi在样本 x x x上的预测输出表示为一个 N N N维向量 ( h i 1 ( x ) h i 2 ( x ) 。。。 h i N ( x ) ) (h^1_i(x)h^2_i(x)。。。h^N_i(x)) (hi1(x)hi2(x)。。。hiN(x))其中 h i j ( x ) h^j_i(x) hij(x)是 h i h_i hi在类别标记 c j c_j cj上的输出。
绝对多数投票法 H ( x ) { c j i f ∑ i 1 T h i j ( x ) 0.5 ∑ k 1 N ∑ i 1 T h i k ( x ) r e j e c t o t h e r w i s e H(x)\begin{cases} c_j if \quad ∑^T_{i1}h^j_i(x)0.5∑^N_{k1}∑^T_{i1}h^k_i(x)\\ reject otherwise \end{cases} H(x){cjrejectif∑i1Thij(x)0.5∑k1N∑i1Thik(x)otherwise 即若某标记得票过半数则预测为该标记:否则拒绝预测
相对多数投票法 H ( x ) c a r g m a x j ∑ i 1 T h i j ( x ) H(x)c_{argmax_j∑^T_{i1}h^j_i(x)} H(x)cargmaxj∑i1Thij(x) 即预测为得票最多的标记若同时有多个标记获最高票则从中随机选取一个
加权投票法 H ( x ) c a r g m a x j ∑ i 1 T w i h i j ( x ) H(x)c_{argmax_j∑^T_{i1}w_ih^j_i(x)} H(x)cargmaxj∑i1Twihij(x)
与加权平均法类似 w i w_i wi是 h i h_i hi的权重通常 w i ≥ 0 w_i≥0 wi≥0 ∑ i 1 T w i 1 ∑^T_{i1}w_i1 ∑i1Twi1
8.4.3 学习法
当训练数据很多时一种更为强大的结合策略是使用“学习法”即通过另一个学习器来进行结合。Stacking是学习法的典型代表。这里我们把个体学习器称为初级学习器用于结合的学习器称为次级学习器或元学习器(meta-learner)
Stacking 先从初始数据集训练出初级学习器然后“生成”一个新数据集用于训练次级学习器。在这个新数据集中初级学习器的输出被当作样例输入特征而初始样本的标记仍被当作样例标记。Stacking的算法描述如图8.9所示这里我们假定初级学习器使用不同学习算法产生即初级集成是异质的。 次级学习器的输入属性表示和次级学习算法对Stacking集成的泛化性能有很大影响。
贝叶斯模型平均(Bayes Model Averaging,简称 BMA)基于后验概率来为不同模型赋予权重可视为加权平均法的一种特殊实现。对Stacking和BMA 进行了比较理论上来说若数据生成模型恰在当前考虑的模型中且数据噪声很少则 BMA 不差于 Stacking然而在现实应用中无法确保数据生成模型一定在当前考虑的模型中甚至可能难以用当前考虑的模型来进行近似因此Stacking通常优于 BMA因为其鲁棒性比 BMA 更好而且BMA 对模型近似误差非常敏感。
8.5 多样性
8.5.1 误差-分歧分解
对示例 x x x定义学习器 h i h_i hi 的分歧 (arnbiguity)为 A ( h i ∣ x ) ( h i ( x ) − H ( x ) ) 2 A(h_i|x)(h_i(x)-H(x))^2 A(hi∣x)(hi(x)−H(x))2 则集成的分歧是 A ˉ ( h ∣ x ) ∑ i 1 T w i A ( h i ∣ x ) ∑ i 1 T w i ( h i ( x ) − H ( x ) ) 2 \bar{A}(h|x)\sum _{i1}^{T}w_iA(h_i|x)\sum_{i1}^{T}w_i(h_i(x)-H(x))^2 Aˉ(h∣x)i1∑TwiA(hi∣x)i1∑Twi(hi(x)−H(x))2 这里的“分歧”项表征了个体学习器在样本。上的不一致性即在定程度上反映了个体学习器的多样性。
8.5.2 多样性度量
多样性度量(diversity measure)是用于度量集成中个体分类器的多样性即估算个体学习器的多样化程度典型做法是考虑个体分类器的两两相似/不相似性。
给定数据集 D { ( x 1 , y 1 ) ( x 2 , y 2 ) 。。。 ( x m , y m ) } D \{(x_1,y_1)(x_2,y_2)。。。(x_m,y_m)\} D{(x1,y1)(x2,y2)。。。(xm,ym)}对二分类任务 y i ∈ − 1 , 1 y_i ∈{-1,1} yi∈−1,1分类器 hi与h的预测结果列联表(contingency table)为 其中a表示 h i h_i hi与 h j h_j hj均预测为正类的样本数目b、c、d含义由此类推: a b c d m abcdm abcdm。基于这个列联表下面给出一些常见的多样性度量
不合度量 d i s i j b c m dis_{ij}\frac{bc}{m} disijmbc d i s i j dis_{ij} disij的值域为[0,1]。值越大则多样性越大
相关系数 ρ i j a d − b c ( a b ) ( a c ) ( c d ) ( b d ) \rho _{ij}\frac{ad-bc}{\sqrt{(ab)(ac)(cd)(bd)}} ρij(ab)(ac)(cd)(bd) ad−bc pij的值域为[-1,1]。若h与h无关则值为0若h与h正相关则值为正否则为负
Q-统计量 Q i j a d − b c a d b c Q_{ij}\frac{ad-bc}{adbc} Qijadbcad−bc
k-统计量 κ p 1 − p 2 1 − p 2 \kappa \frac{p_1-p_2}{1-p_2} κ1−p2p1−p2。
8.5.3 多样性增强
在集成学习中需有效地生成多样性大的个体学习器。与简单地直接用初始数据训练出个体学习器相比如何增强多样性呢一般思路是在学习过程中弓入随机性常见做法主要是对数据样本、输入属性、输出表示、算法参数进行扰动。
数据样本扰动
给定初始数据集可从中产生出不同的数据子集再利用不同的数据子集训练出不同的个体学习器。数据样本扰动通常是基于采样法例如在Bagging中使用自助采样在AdaBoost中使用序列采样。此类做法简单高效使用最广。对很多常见的基学习器例如决策树、神经网络等训练样本稍加变化就会导致学习器有显著变动数据样本扰动法对这样的“不稳定基学习器”很有效然而有一些基学习器对数据样本的扰动不敏感例如线性学习器、支持向量机、朴素贝叶斯、k近邻学习器等这样的基学习器称为稳定基学习器(stablebase learner)对此类基学习器进行集成往往需使用输入属性扰动等其他机制
输入属性扰功 训练样本通常由一组属性描述不同的“子空间”(subspace,即属性子集)提供了观察数据的不同视角。显然从不同子空间训练出的个体学习器必然有所不同。著名的随机子空间(random subspace)算法|Ho1998]就依赖于输)属性扰动该算法从初始属性集中抽取出若干个属性子集再基于每个属性子集训练一个基学习器算法描述如图8.11所示。对包含大量冗余属性的数据在子空间中训练个体学习器不仅能产生多样性大的个体还会因属性数的减少而大幅节省时间开销同时由于冗余属性多减少一些属性后训练出的个体学习器也不至于太差。若数据只包含少量属性或者冗余属性很少则不宜使用输入属性扰动法。 输出表示扰动 此类做法的基本思路是对输出表示进行操纵以增强多样性。可对训练样本的类标记稍作变动如“翻转法”(Flipping Output)随机改变一些训练样本的标记也可对输出表示进行转化如“输出调制法”(OutputSmearing)[Breiman2000|将分类输出转化为回归输出后构建个体学习器还可将原任务拆解为多个可同时求解的子任务如ECOC法利用纠错输出码将多分类任务拆解为一系列二分类任务来训练基学习器
算法参数扰动 基学习算法一般都有参数需进行设置例如神经网络的隐层神经元数、初始连接权值等通过随机设置不同的参数往往可产生差别较大的个体学习器
例如“负相关法”(Negative Correlation)显式地通过正则化项来强制个体神经网络使用不同的参数。对参数较少的算法可通过将其学习过程中某些环节用其他类似方式代替从而达到扰动的目的例如可将决策树使用的属性选择机制替换成其他的属性选择机制。值得指出的是使用单一学习器时通常需使用交叉验证等方法来确定参数值这事实上已使用了不同参数训练出多个学习器只不过最终仅选择其中一个学习器进行使用而集成学习则相当于把这些学习器都利用起来:由此也可看出集成学习技术的实际计算开销并不比使用单一学习器大很多。
不同的多样性增强机制可同时使用例如8.3.2节介绍的随机森林中同时使用了数据样本扰动和输入属性扰动有些方法甚至同时使用了更多机制。
