Boosting算法简介.pdf-资料库

cc5zhenhua-10568655-16359647560318388830.pdf-第1页.png

第1页 / 共18页

cc5zhenhua-10568655-16359647560318388830.pdf-第2页.png

第2页 / 共18页

cc5zhenhua-10568655-16359647560318388830.pdf-第3页.png

第3页 / 共18页

cc5zhenhua-10568655-16359647560318388830.pdf-第4页.png

第4页 / 共18页

cc5zhenhua-10568655-16359647560318388830.pdf-第5页.png

第5页 / 共18页

cc5zhenhua-10568655-16359647560318388830.pdf-第6页.png

第6页 / 共18页

cc5zhenhua-10568655-16359647560318388830.pdf-第7页.png

第7页 / 共18页

cc5zhenhua-10568655-16359647560318388830.pdf-第8页.png

第8页 / 共18页

集成学习需要解决两个问题：  如何调整输入训练数据的概率分布及权值；  如何训练与组合基分类器。 Bagging 与 Boosting。 Bagging（Bootstrap Aggregating）对训练数据擦用自助采样（boostrap sampling），即有放回地采样数据；每一次的采样数据集训练出一个基分类器，经过 MM 次采样得到 MM 个基分类器，然后根据最大表决（majority vote）原则组合基分类器的分类结果。分类问题很常见： 1) 博客男女 2) OCR 3) 情感分类 4) 查询意图识别 5) 排序学习 6) 等等文本分类算法： 1) Nave Bayes 2) Decision Tree 3) KNN 4) ANN 5) SVM 6) ME 7) ... PAC：因为我们不能指望学习能够零错误，并且也不能要求对任意数据的预测能够成功，但是我们需要将错误率和预测失败率控制在一定范围内，也就是近似正确，而不是以 1 为指标的。

Boosting 是一种提高任意给定学习算法准确度的方法。它的思想起源于 Valiant 提出的 PAC ( Probably Approximately Correct)学习模型。 Valiant 和 Kearns 提出了弱学习和强学习的概念 ,识别错误率小于 1/2, 也即准确率仅比随机猜测略高的学习算法称为弱学习算法; 识别准确率很高并能在多项式时间内完成的学习算法称为强学习算法。同时 ,Valiant 和 Kearns 首次提出了 PAC 学习模型中弱学习算法和强学习算法的等价性问题, 即任意给定仅比随机猜测略好的弱学习算法 ,是否可以将其提升为强学习算法 ? 如果二者等价 ,那么只需找到一个比随机猜测略好的弱学习算法就可以将其提升为强学习算法 , 而不必寻找很难获得的强学习算法。 1990 年, Schapire 最先构造出一种多项式级的算法 ,对该问题做了肯定的证明 ,这就是最初的 Boosting 算法。一年后 ,Freund 提出了一种效率更高的 Boosting 算法。但是,这两种算法存在共同的实践上的缺陷 ,那就是都要求事先知道弱学习算法学习正确的下限。 1995 年 , Freund 和 schap ire 改进了 Boosting 算法 ,提出了 AdaBoost (Adap tive Boosting)算法[ 5 ],该算法效率和 Freund 于 1991 年提出的 Boosting 算法几乎相同 , 但不需要任何关于弱学习器的先验知识 ,因而更容易应用到实际问题当中。之后 , Freund 和 schapire 进一步提出了改变 Boosting 投票权重的 AdaBoost . M1,AdaBoost . M2 等算法 ,在机器学习领域受到了极大的关注。 Boosting 方法是一种用来提高弱分类算法准确度的方法, 这种方法通过构造一个预测函数系列,然后以一定的方式将他们组合成一个预测函数。他是一种框架算法,主要是通过对样本集的操作获得样本子集, 然后用弱分类算法在样本子集上训练生成一系列的基分类器。他可以用来提高其他弱分类算法的识别率, 也就是将其他的弱分类算法作为基分类算法放于 Boosting 框架中,“ 通过 Boosting 框架对训练样本集的操作,得到不同的训练样本子集,用该样本子集去训练生成基分类器; 每得到一个样本集就用该基分类算法在该样本集上产生一个基分类器, 这样在给定训练轮数 n 后,就可产生 n 个基分类器,然后 Boosting 框架算法将这 n 个基分类器进行加权融合,产生一个最后的结果分类器,在这 n 个基分类器中, 每个单个的分类器的识别率不一定很高 ,但他们联合后的结果有很高的识别率 ,这样便提高了该弱分类算法的识别率。在产生单个的基分类器时可用相同的分类算法,也可用不同的分类算法,这些算法一般是不稳定的弱分类算法,如神经网络(BP) ,决策树(C4.5)等。由于 Boosting 算法在解决实际问题时有一个重大的缺陷,即他们都要求事先知道弱分类算法

分类正确率的下限,这在实际问题中很难做到。后来 Freund 和 Schapire 提出了 AdaBoost 算法,该算法的效率与 Freund 方法的效率几乎一样,却可以非常容易地应用到实际问题中。 AdaBoost 是 Boosting 算法家族中代表算法,AdaBoost 主要是在整个训练集上维护一个分布权值向量 Dt( x) ,用赋予权重的训练集通过弱分类算法产生分类假设 Ht ( x) ,即基分类器,然后计算他的错误率,用得到的错误率去更新分布权值向量 Dt( x) ,对错误分类的样本分配更大的权值,正确分类的样本赋予更小的权值。每次更新后用相同的弱分类算法产生新的分类假设,这些分类假设的序列构成多分类器。对这些多分类器用加权的方法进行联合,最后得到决策结果。这种方法不要求产生的单个分类器有高的识别率,即不要求寻找识别率很高的基分类算法,只要产生的基分类器的识别率大于 0.5 ,就可作为该多分类器序列中的一员。寻找多个识别率不是很高的弱分类算法比寻找一个识别率很高的强分类算法要容易得多,AdaBoost 算法的任务就是完成将容易找到的识别率不高的弱分类算法提升为识别率很高的强分类算法,这也是 AdaBoost 算法的核心指导思想所在, 如果算法完成了这个任务,那么在分类时,只要找到一个比随机猜测略好的弱分类算法,就可以将其提升为强分类算法,而不必直接去找通常情况下很难获得的强分类算法。通过产生多分类器最后联合的方法提升弱分类算法,让他变为强的分类算法,也就是给定一个弱的学习算法和训练集,在训练集的不同子集上,多次调用弱学习算法,最终按加权方式联合多次弱学习算法的预测结果得到最终学习结果。包含以下 2 点: 样本的权重 AdaBoost 通过对样本集的操作来训练产生不同的分类器,他是通过更新分布权值向量来改变样本权重的,也就是提高分错样本的权重,重点对分错样本进行训练。 (1) 没有先验知识的情况下,初始的分布应为等概分布,也就是训练集如果有 n 个样本,每个样本的分布概率为 1/ n。 (2)每次循环后提高错误样本的分布概率,分错的样本在训练集中所占权重增大,使得下一次循环的基分类器能够集中力量对这些错误样本进行判断。弱分类器的权重最后的强分类器是通过多个基分类器联合得到的, 因此在最后联合时各个基分类器所起的作用对联合结果有很大的影响,因为不同基分类器的识别率不同,他的作用就应该不同,这里通过权值体现他的作用,因此识别率越高的基分类器权重越高,识别率越低的基分类器权重越低。权值计算如下: 基分类器的错误率: e = ∑( ht ( x i) ≠yi) Di (1) 基分类器的权重:W t = F( e) ,由基分类器的错误率计算他的权重。算法流程及伪码描述算法流程描述算法流程可用结构图 1 描述, 如图 1 所示 AdaBoost 重复调用弱学习算法(多轮调用产生多个分类器) , 首轮调用弱学习算法时,按均匀分布从样本集中选取子集作为该次训练集,以后每轮对前一轮训练失败的样本,赋予较大的分布权值( Di 为第 i 轮各个样本在样本集中参与训练的概率) ,

使其在这一轮训练出现的概率增加, 即在后面的训练学习中集中对比较难训练的样本进行学习,从而得到 T 个弱的基分类器, h1 , h2 , …, ht ,其中 ht 有相应的权值 w t ,并且其权值大小根据该分类器的效果而定。最后的分类器由生成的多个分类器加权联合产生。算法伪码描述输入: S = { ( x1 , y1 ) , …( x i , y i) …, ( x n , y n) } , x i ∈X yi ∈Y ;训练轮数为 T; 初始化分发权值向量: 公式 (2) for t = 1 , …, T : (1) 使用分发权值向量 Dt 训练基分类器 ht = R( x , y ,Dt) ; R 为一弱的分类算法; (2) 计算错误率:e = ∑( ht ( x i) ≠y i) Di (3) (3) if e≥ 0.5 ,break ; (4) 计算基分类器的权值 ht :wt ∈w; (5) 更新权值:Dt ( i+1) = Dt ( i) ×F( e) (4) 其中 F( x)为更新函数,他以该次得到的基分类器的分类错误率 e 为自变量; (6) 将多个基分类器进行联合,输出最后的分类器。在上面的算法中: x i ∈X , yi ∈Y , x i 表示样本属性组成的向量, yi 表示该样本的类别标签; ②Dt 为样本的分发权值向量: 没有先验知识的情况下, 初始的分布应为等概率分布,也就是训练集如果有 n 个样本,每个样本的分布概率为 1/ n; 每次循环后提高错误样本的分布概率, 分错的样本在训练集中所占权重增大,使得下一次循环的弱学习算法能够集中对这些错误样本进行判断; Dt 总和应该为 1 ; wt 为分类器的权值: 准确率越高的分类器权重 w 越大。二、Boosting 原理

1. Boosting 由来 Kearns & Valiant (1984) PAC 学习模型提出问题： 1) 强学习算法：存在一个多项式时间的学习算法以识别一组概念，且识别的正确率很高。 2) 弱学习算法：识别一组概念的正确率仅比随机猜测略好。 3) 弱学习器与强学习器的等价问题。如果两者等价，只需找到一个比随机猜测略好的学习算法，就可以将其提升为强学习算法。 Kearns & Valiant (1989) 证明了弱学习器和强学习器的等价问题。 Schapire (1989) 第一个提出了一个可证明的多项式时间的 Boosting 算法。 Schapire, etc. (1993) 第一次把 Boosting 算法思想用于实际应用：OCR。 Freund & Schapire (1995) AdaBoost 算法。 2. Boosting 思想基本思想： 1) 先赋予每个训练样本相同的概率。 2) 然后进行 T 次迭代，每次迭代后，对分类错误的样本加大权重(重采样)，使得在下一次的迭代中更加关注这些样本。示例：

3. AdaBoost 算法及分析 1) Base Setting 二元分类问题训练数据: (x1, y1), …, (xm, ym) where xi∈X, yi∈Y={-1, +1} Dt(i): 样本 xi 在第 t 次迭代的权重 D1(i)=1/m ht(X)：弱学习器 Ct 训练得到的判别函数 ht:X->{-1, +1} εt：ht(X)的错误率 2) 基本思路 a) 训练一系列弱学习器 h1, h2, …, hT。 b) 在训练过程中，注重那些分类错误的样本。 c) 把训练出来的一系列弱学习器组合起来，每个弱学习器 ht(X)都有一个相应的权重 α t: 3）AdaBoost 算法

弱学习器 Ct 的权重 αt 由第 t 次迭代决定训练样本的分布权重 Dt (i)在每一次迭代都会更新弱学习器 Ct 的选择：如果某次迭代的训练误差大于 1/2，则抛弃，算法停止算法在每次迭代都会更新样本的分布权重，在下一次迭代前会进行一次训练样本的重采样。如何进行重采样？可根据概率分布 Dt(i)来采样。“轮盘赌”算法是其中一种比较简单、高效的方法。 “轮盘赌”算法使用一个[0~1]随机数生成器举例：如果随机数生成器生成 0.525，则恭喜你，获得“康师傅冰红茶”一瓶；若生成 0.91，则能获得宝马一部。 4) AdaBoost 特性分析特性 1：训练误差的上界，随着迭代次数的增加，会逐渐下降。

特性 2： AdaBoost 算法即使训练次数很多，也不会出现过度拟合(over fitting)的问题。三、应用 1. 文本分类给定某篇文档，判别其所属类别文档可能是某些网页，也可能是短文本(query，微博等) 应用很广 AdaBoost (weak learner: NB, C4.5 等) 2. 排序学习 1) 排序问题 2) 排序模型

资料库

Boosting算法简介.pdf

相关推荐

人工智能

热门标签

最新资料