《机器学习技法》AdaBoost算法

1 AdaBoost的推导

首先&＃xff0c;直接给出AdaBoost算法的核心思想是&＃xff1a;在原数据集上经过取样&＃xff0c;来生成不同的弱分类器&＃xff0c;最终再把这些弱分类器聚合起来。

关键问题有如下几个&＃xff1a;

&＃xff08;1&＃xff09;取样怎样用数学方式表达出来&＃xff1b;

&＃xff08;2&＃xff09;每次取样依据什么准则&＃xff1b;

&＃xff08;3&＃xff09;最后怎么聚合这些弱分类器。

 

首先我们看第一个问题&＃xff0c;如何表示取样&＃xff1f;答案使用原数据集上的加权error。

假设我们对数据集D做的取样如下&＃xff1a;

那么我们在新数据集上的01error可以等效为在原数据集上的加权error&＃xff1a;

 

即我们取样相当于确定一组权重μ&＃xff0c;对这个加权的error作最小化就能得到一个弱分类器g。

特别的&＃xff0c;对于svm和逻辑回归&＃xff0c;如果我们已知权重μ&＃xff0c;我们可以用下面的方式解&＃xff1a;

 

然后是第二个问题&＃xff0c;依据什么原则来取样&＃xff1f;或者说&＃xff0c;怎样选择权重μ。

答案是多样性。即保证生成的每个弱分类器的差别越大&＃xff0c;最后的聚合出来的强分类器就会越好。

如何来保证这一点呢&＃xff1f;假设我的第t次取样生成了gt&＃xff0c;第t&＃43;1次取样生成了g(t&＃43;1)&＃xff0c;取样的规则分别是μt和μt&＃43;1。即&＃xff1a;

那么&＃xff0c;要保证gt&＃43;1和gt有很大不同&＃xff0c;有一个办法&＃xff0c;就是使gt用在gt&＃43;1的数据集上时&＃xff0c;效果很差。效果很差就是错误率是0.5&＃xff0c;跟扔硬币一样&＃xff1a;

 即&＃xff1a;

所以&＃xff0c;更新这个权重的方法是&＃xff0c;对于t轮上分类错误的点&＃xff0c;它的u应该更新为乘以总的分类正确率&＃xff0c;对于分类正确的点&＃xff0c;它的u应该更新为乘以总的分类错误率&＃xff0c;注意这里的分类错误率是加权后的分类错误率&＃xff08;或者说在采样后的分类错误率&＃xff09;&＃xff1a;

这里我们使用另一种与上面等效的方法&＃xff1a;

它有一定的物理意义&＃xff1a;由于上一轮错误率总是小于0.5&＃xff0c;因此方块t是大于1的。因此对于上一次分类正确的权重&＃xff0c;除以方块t&＃xff0c;减小了权重&＃xff1b;对于上一次分类错误的权重&＃xff0c;乘以方块t&＃xff0c;放大了权重。

类似于水果课堂中老师教学生的例子。

 

第三个问题&＃xff0c;得到了这些弱分类器&＃xff0c;如何把他们聚合起来&＃xff1f;AdaBoost使用的是Linear Blending的方式&＃xff0c;其中的权重应该与方块t成正比&＃xff0c;即这个弱分类器表现越好&＃xff0c;权重应该越大&＃xff1a;

 

另外&＃xff0c;初始的u我们定为均匀的。

这样&＃xff0c;AdaBoost算法如下&＃xff1a;

 

2 AdaBoost的理论保证