machine learning / 机器学习

Adaboost

AdaBoost

1.前言:

最近在学习Adaboost,看了不少大神的博文,也有算法执行的演练,但比较偏应用,有些地方没有解释就直接蹦出个公式套用,所以自己硬着头皮重新推导一遍。希望大神帮忙指出错误。

AdaBoost(Adaptive Boosting),中文叫做“自适应增强”,是boost集成学习的一种实现方式。

AdaBoost 是一种迭代算法,在每一轮中加入一个新的弱分类器,直到达到某个预定的足够小的错误率。每一个训练样本都被赋予一个权重,表明它被某个分 类器选入训练集的概率。如果某个样本点已经被准确地分类,那么在构造下一个训练集中,它被选中的概率就被降低;相反,如果某个样本点没有被准确地分类,那 么它的权重就得到提高。

在具体实现上,最初令每个样本的权重都相等,对于第k次迭代操作,我们就根据这些权重来选取样本点,进而训练分类 器。然后就根据这个分类器,来提高被它分 错的的样本的权重,并降低被正确分类的样本权重。然后,权重更新过的样本集被用于训练下一个分类器。整个训练过程如此迭代地进行下去。

.

2.算法:

给定训练集

  • 初始化训练集权值分布,每个训练样本的初始权重皆为 ,即: 这里wi(1)表示权重,D1表示权重的集合(第一次迭代的权重集合)。因为每次迭代后,权重集合都会发生变化,因此假设共有n次迭代,那么有权重集合wm(n)m表示第m个样本,n表示第n次迭代。
  • 通过对Dn的学习,得到弱分类器 ,这里暂不考虑选择的什么函数,比如通过CART决策树求得fn(x),这也说明了为什么这个算法叫Boosting
  • 将所有弱分类器进行组合,生成增强分类器
  • 每个弱分类器会产生一个输出,设为h(xi),同时在每次迭代中对弱分类器添加系数αn,求第n次迭代的训练误差En的总和的最小化值。即:。其中Fn-1(x)是上一个迭代中生成的增强分类器(上面第三步的分类器);E[]是代价函数; 是当前迭代中产生的弱分类器。

.

3.推导:

给定数据集 ;

给定弱分类器 ,即1中的fn(x)

经过n-1次迭代后增强分类器将是一个弱分类器的线性组合形式:

n次迭代后的增强分类器可以表示为:

我们选择指数误差(exponential loss)来计算Cn的总误差En

(根节点只有一个类别所以权重是1 ,当n>1时有:

可得

如果弱分类器kn分类正确则有 ,如果分类错误则有 ,那么继续推导

由于在 表示第n层的总权重。而 表示误差的权重,显然该值越小误差越小,所以误差最小化问题就成了 最小化问题(如果 意味着样本全部分类正确,此时 )。又因为 中,yikn-1(xi)都是已知项,因此问题就变成了与αn有关。

由于αn未知,为了确认αn,通过指数函数求导公式E求导并使结果等于0(最小化E,不明白的去看下凸优化),有:

,这里就是错误样本权重在总权重中的比例。

因此有

,这里可以发现ε越小,αn越大,此时错误样本权重也越小。因此通过公式 可以发现,正确分类概率越高的弱分类器给予的α越高,这时α可以理解成弱分类器k的权重,显然这样可以更好的进行拟合。

同时可以发现 中,如果分类错误会导致w变成正数,使w在此次迭代中的值变大。这就会产生这样一个现象: 对于分类正确的样本,降低其权重,从而提高分类错误的样本权重,这样分错的样本就被突显出来,从而得到一个新的样本分布如果把w的分布点画出来,显然这种规律更容易进行分类。

最后通过最小化 ,求得相应的αn,进一步不断进行递归可求得增强分类器 。再次强调kn(x)通常选用CART决策树。

.

.

2016.11.6 完成第一版内容

2016.11.8 完善内容

2016.11.10 调整样式

原创内容,转载请注明出处

Leave a Reply

Your email address will not be published. Required fields are marked *