关于人工智能:手撕系列AdaBoost

简介：

上次咱们介绍过 Adaboost 是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器(弱分类器)，而后把这些弱分类器集合起来，形成一个更强的最终分类器（强分类器）。

本次将通过一个简略示例，手撕拆解 Adaboost 的计算过程。本次是手撕模型系列第一篇，各位看官若有想理解的算法模型，欢送留言，后续会依据集体能力安顿！

一．初始化阶段

给定下列的训练样本，应用 AdaBoost 算法学习失去一个强分类器。

序号

-1

初始化训练数据的权值散布，令每个权值 W1i = 1/N = 0.1，其中，N = 10，i = 1,2, …, 10，而后别离对于 m = 1,2,3, … 等值进行迭代。

随机设定这 10 个数据的训练样本后，依据 X 和 Y 的对应关系，要把这 10 个数据分为两类，一类是“Y=1”，一类是“Y=-1”，依据数据的特点发现：“0 1 2”这 3 个数据对应的类是“1”，“3 4 5”这 3 个数据对应的类是“-1”，“6 7 8”这 3 个数据对应的类是“1”，9 是比拟独立的，对应类“-1”。抛开独立的 9 不讲，“0 1 2”、“3 4 5”、“6 7 8”这是 3 类不同的数据，别离对应的类是 1、-1、1，直观上揣测可知，能够找到对应的数据分界点，比方 2 - 3 之间 (2.5)、5- 6 之间(5.5)、8-9(8.5) 之间将那几类数据分成两类。上面理论计算下这个过程。

二．迭代计算

第一次迭代 m =1，在权值散布为 D1（10 个数据，每个数据的权值皆初始化为 0.1）的训练数据上。

序号

-1

0.1

通过计算下面样本可得：

a．阈值 v 取 2.5 时误差率为 0.3（x < 2.5 时取 1，x > 2.5 时取 -1，则 6 7 8 分错，误差率为 0.3）；

b．阈值 v 取 5.5 时误差率最低为 0.4（x < 5.5 时取 1，x > 5.5 时取 -1，则 3 4 5 6 7 8 皆分错，误差率 0.6 大于 0.5，不可取。故令 x > 5.5 时取 1，x < 5.5 时取 -1，则 0 1 2 9 分错，误差率为 0.4）；

c．阈值 v 取 8.5 时误差率为 0.3（x < 8.5 时取 1，x > 8.5 时取 -1，则 3 4 5 分错，误差率为 0.3）。

所以无论阈值 v 取 2.5，还是 8.5，总得分错 3 个样本，故可任取其中任意一个如 2.5，设定成第一个根本分类器为：

                                          image.png

下面说阈值 v 取 2.5 时则 6 7 8 分错，所以误差率为 0.3，更加具体的解释是：因为样本集中 X ={0,1,2}对应的类 Y =1，因它们自身都小于 2.5，所以被 G1(x)分在了相应的类“1”中，分对了。X={3,4,5}自身对应的类 Y =-1，因它们自身都大于 2.5，所以被 G1(x)分在了相应的类“-1”中，分对了。但 X ={6,7,8}自身对应类 Y =1，却因它们自身大于 2.5 而被 G1(x)分在了类 ”-1″ 中，所以这 3 个样本被分错了。X= 9 自身对应的类 Y =- 1 因它自身大于 2.5，所以被 G1(x)分在了相应的类“-1”中，分对了。

而后依据误差率 e1 计算 G1 的系数：

image.png

依据误差 e1=0.3 计算系数 α1=0.4236。这个 α1 代表 G1(x)在最终的分类函数中所占的权重为 0.4236。

接着更新训练数据的权值散布，用于下一轮迭代：

image.png

由权值更新的公式可知，每个样本的新权值是变大还是变小，取决于它是被分错还是被分正确。即如果某个样本被分错了，则 yi * Gm(xi)为负，负负等正，后果使得整个式子变大（样本权值变大），否则变小。

序号

-1

0.1

0.0715

0.1666

0.0715

分类函数 f1(x)= α1*G1(x) = 0.4236G1(x)。此时，失去的第一个根本分类器 sign(f1(x))在训练数据集上有 3 个误分类点（即 6 7 8）。从上述第一轮的整个迭代过程能够看出：被误分类样本的权值之和影响误差率，误差率影响根本分类器在最终分类器中所占的权重。

第二次迭代 m =2，权值散布为 D2

通过计算下面样本可得：

a．阈值 v 取 2.5 时误差率为 0.16663（x < 2.5 时取 1，x > 2.5 时取 -1，则 6 7 8 分错，误差率为 0.16663）；

b．阈值 v 取 5.5 时误差率最低为 0.07154（x > 5.5 时取 1，x < 5.5 时取 -1，则 0 1 2 9 分错，误差率为 0.07153 + 0.0715）；

c．阈值 v 取 8.5 时误差率为 0.07153（x < 8.5 时取 1，x > 8.5 时取 -1，则 3 4 5 分错，误差率为 0.07153）。

所以，阈值 v 取 8.5 时误差率最低，故第二个根本分类器为：

image.png

很显著，G2(x)把样本“3 4 5”分错了，依据 D2 可知它们的权值为 0.0715，所以 G2(x)在训练数据集上的误差率 e2=P(G2(xi)≠yi)=0.0715*3=0.2143。

依据误差 e2=0.2143 计算系数 α2=0.6496。这个 α2 代表 G2(x)在最终的分类函数中所占的权重为 0.6496。

更新训练数据的权值散布：

序号

-1

0.1

0.0715

0.1666

0.0715

0.0455

0.1667

0.1060

0.0455

f2(x)=0.4236G1(x) + 0.6496G2(x)

此时，失去的第二个根本分类器 sign(f2(x))在训练数据集上有 3 个误分类点（即 3 4 5）。

第三次迭代 m =3，权值散布为 D3

通过计算下面样本可得：

a．阈值 v 取 2.5 时误差率为 0.10603（x < 2.5 时取 1，x > 2.5 时取 -1，则 6 7 8 分错，误差率为 0.10603）；

b．阈值 v 取 5.5 时误差率最低为 0.04554（x > 5.5 时取 1，x < 5.5 时取 -1，则 0 1 2 9 分错，误差率为 0.04553 + 0.0715）；

c．阈值 v 取 8.5 时误差率为 0.16673（x < 8.5 时取 1，x > 8.5 时取 -1，则 3 4 5 分错，误差率为 0.16673）。

所以，阈值 v 取 5.5 时误差率最低，故第三个根本分类器为：

image.png

此时，G3 误分类的样本是：0 1 2 9，这 4 个样本所对应的权值皆为 0.0455，所以 G3(x)在训练数据集上的误差率 e3= P(G3(xi)≠yi) = 0.0455*4 = 0.1820。

依据误差 e2=0.1820 计算系数 α2=0.7514。这个 α3 代表 G2(x)在最终的分类函数中所占的权重为 0.7514。

序号

-1

0.1

0.0715

0.1666

0.0715

0.0455

0.1667

0.1060

0.0455

0.1250

0.1020

0.0650

0.1250

f3(x)=0.4236G1(x) + 0.6496G2(x)+0.7514G3(x)

此时，失去的第三个根本分类器 sign(f3(x))在训练数据集上有 0 个误分类点。至此，整个训练过程完结。

G(x)=sign[f3(x)]=sign[α1G1(x)+α2G2(x)+α3*G3(x)]，将下面计算失去的 α1、α2、α3 各值代入 G(x)中，失去最终的分类器为：G(x)=sign[f3(x)]=sign[0.4236G1(x)+0.6496G2(x)+0.7514G3(x)]。

总结：

以上就是一个简略的计算示例，Aadboost 算法具备较高的检测效率，且不容易呈现过拟合景象。然而该算法在实现过程中为获得更高的检测精度则须要较大的训练样本集，在每次迭代过程中，训练一个弱分类器则对应该样本集中的每一个样本，每个样本具备很多特色，因而从宏大的特色中训练失去最优弱分类器的计算量增大。