AdaBoost Example

我终于想到自己应该滚过来更新了。实在是因为考完CFA以后，整个人生好像没有了明确的目标，导致自己什么都想做，结果什么都做不好。这段时间自己的状态一直保持低迷，原因肯定是对自己各种的放纵。前阵子，德约科维奇又拿下来澳网的冠军，我就顺便看了一本他的自传，印象最深的是极度的自律。在拿到某次冠军后（好像也是澳网），他说他想吃一块巧克力庆祝一下（因为平时绝对不会碰这种东西，怕影响状态），结果就吃了一小口。只有能做到这样的自律，才能取得不平凡的成绩。

说了一堆废话，还是言归正传。前段时间正好用到random forrest就想顺便把AdaBoost也看一下，李航《统计学习方法》里有一个例子，但是我怎么都没看懂（智商不够用，顺便吐槽一下这本书，虽然很多人推荐，但我一直没觉得这本书好在哪里），于是就到网上找例子，到油管上看视频，结果发现能把AdaBoost讲明白的例子几乎没有。后来不知道哪天突然开悟了，李航那本书上的例子竟然被我看明白了！

我就直接上例子了，AdaBoost具体的理论还请自行脑补。训练数据如下表：

序号	1	2	3	4	5	6	7	8	9	10
x	0	1	2	3	4	5	6	7	8	9
y	1	1	1	-1	-1	-1	1	1	1	-1

x是特征，y是label。显然根据特征x对y分类，分为2种类型1，-1。我一开始一直没搞明白评价分类结果依据什么？后来才理解了评价分类的依据是各训练数据的权值！我们知道Adaboost会将分类错误的训练数据的权值提高，这样，在下一次弱分类器的训练过程中就可以重点“关照”这些被分错的数据了。那么，也就有可能出现以下这种情况：某个弱分类器可能错误率很高但却被采纳了，因为它可能将权重更高的训练数据进行准确地分类。参见以下训练过程

m=1 (训练第一个弱分类器)

对于第一个弱分类器而言，每个训练数据的权值w都是一样的，即1/N（初始情况下的默认值），N表示训练数据量。就本例而言，N=10，每个训练数据的权值w为0.1，在此前提下可以训练出一个最优的弱分类器：

$G_1(x) = \\begin{cases} 1, & \text{x $<$ 2.5} \\\\ -1, & \text{x $>$ 2.5} \\\\ \\end{cases}$

切分点为x=2.5，因为误差率（分错权值加总）最低，注意这里需要强调的是选择弱分类器的依据是误差率最低的那个，而不是分对的数量最多的那个（当然，权值相同的时候分对数量最高则代表误差率最低），我一开始没看明白就是在这里犯糊涂了。那么有3个数据被错误分类了（x=6，7，8），由于w都为0.1，因此误差率$e_1$（分错权值加总）=0.3。这个误差率是当前权值（w）下最小的。

计算第一个弱分类器的系数（权重），套用公式了，$ \alpha_1 = \frac{1}{2}log\frac{1-e_1}{e_1} $ = 0.5*ln((1-0.3)/0.3) = 0.4236 ；直观的理解就是如果这个分类器的误差率越低，则在一系列弱分类器的组合里所占的权重越高。

更新训练数据的权值，也就是将分对的数据的权值调低，而将分错的数据的权值调高，计算权值的公式为：$w{m+1, i} = w{m, i}exp(-\alpha_m y_i G_m(x_i))$，计算结果如下：

序号	1	2	3	4	5	6	7	8	9	10
y	1	1	1	-1	-1	-1	1	1	1	-1
$w_1$	0.1	0.1	0.1	0.1	0.1	0.1	0.1	0.1	0.1	0.1
$G_1(x)$	1	1	1	-1	-1	-1	-1	-1	-1	-1
$ \alpha_1 $	0.4236
$w_2$ without normalized	0.06547	0.06547	0.06547	0.06547	0.06547	0.06547	0.15275	0.15275	0.15275	0.06547
Z	0.9165
$w_2$ normalized	0.07143	0.07143	0.07143	0.07143	0.07143	0.07143	0.16667	0.16667	0.16667	0.07143

以计算第一个$w_2$为例，原来的$w_2=0.1, \alpha=0.4236, y=1, G_1(x_1)=1$，也就是分类正确，那么可得: 0.1 exp(-0.4236 1 * 1) = 0.06547
，标准化后为0.07143（$w_2$ 需要标准化，也就是$w_2$的sum为1，表中的Z为所有w的加总，那么normalized w = w without normalized / Z），因此权重降低了！。而对$x_7, x_8, x_9$来说，由于分错了，因此权重升高了。至此第一个弱分类器训练完成，可得：

$f_1(x) = 0.4236G_1(x)$

m=2 (训练第二个弱分类器)

通过训练可得x=8.5最为最佳切分点，因为误差率最小，即：

$G_2(x) = \\begin{cases} 1, & \text{x $<$ 8.5} \\\\ -1, & \text{x $>$ 8.5} \\end{cases}$

$G_2(x)$的误差率为$e_2 = 0.2143$。因为当以8.5为切分点的时候，4，5，6被错误分类了，而他们对应的权重$w_2$ 分别为：0.07143，0.07143，0.07143，即 0.07143 * 3 = 0.2143。如果选择8.5以外的切分点，误差率都比0.2143高。

同样的计算$\alpha_2 = 0.5*LN((1-0.2143)/0.2143) = 0.6496$

其余数据参见下表：

序号	1	2	3	4	5	6	7	8	9	10
y	1	1	1	-1	-1	-1	1	1	1	-1
$w_2$	0.07143	0.07143	0.07143	0.07143	0.07143	0.07143	0.16667	0.16667	0.16667	0.07143
$G_2(x)$	1	1	1	1	1	1	1	1	-1	-1
$ \alpha_2 $	0.6496
$w_3$ without normalized	0.0373	0.0373	0.0373	0.1368	0.1368	0.1368	0.0870	0.0870	0.0870	0.0373
Z	0.8207
$w_3$ normalized	0.0455	0.0455	0.0455	0.1667	0.1667	0.1667	0.1061	0.1061	0.1061	0.0455

至此第二个弱分类器训练完成，可得：

$f_2(x) = 0.4236G_1(x) + 0.6496G_2(x)$

如果，此时将数据喂给$f_2(x)$，可得以下结果：

序号	1	2	3	4	5	6	7	8	9	10
x	0	1	2	3	4	5	6	7	8	9
y	1	1	1	-1	-1	-1	1	1	1	-1
$f_2(x)$	1.0732	1.0732	1.0732	0.226	0.226	0.226	0.226	0.226	0.226	-1.0732
$sign(f_2(x))$	1	1	1	1	1	1	1	1	1	-1

由y同$sign(f_2(x))$比较可知，一共有3个误分类点：4，5，6。

m=3 (训练第三个弱分类器)

通过训练可得x=5.5最为最佳切分点，因为误差率最小，即：

$G_3(x) = \\begin{cases} 1, & \text{x $>$ 5.5} \\\\ -1, & \text{x $<$ 5.5} \\end{cases}$

$G_3(x)$的误差率为$e_3 = 0.1818$。因为当以5.5为切分点的时候1, 2, 3, 10被错误分类了，而他们对应的权重$w_3$ 分别为：0.0455, 0.0455, 0.0455, 0.0455，即 0.0455 * 4 = 0.1818。

同样的计算$\alpha_3 = 0.5*LN((1-0.1818)/0.0.1818) = 0.7520$

至此第三个弱分类器训练完成，可得：

$f_3(x) = 0.4236G_1(x) + 0.6496G_2(x) + 0.7520G_3(x)$

如果，此时将数据喂给$f_3(x)$，可得以下结果：

序号	1	2	3	4	5	6	7	8	9	10
x	0	1	2	3	4	5	6	7	8	9
y	1	1	1	-1	-1	-1	1	1	1	-1
$f_3(x)$	0.3212	0.3212	0.3212	-0.526	-0.526	-0.526	0.978	0.978	0.978	-0.3212
$sign(f_3(x))$	1	1	1	-1	-1	-1	1	1	1	-1

由y同$sign(f_3(x))$比较可知已经无错误分类点！因此，可以认为达到了精度要求，无需再进一步训练。