Adaboost的思想

主要是两个部分:

1. 对错误的分类样本更多的关心
2. 对分类正确率高的基本分类器更大的权值
   步骤:
   由初始样本, 有权重D1, 我们训练一个基本分类器G1, 然后可以得到分类错误率e1, 得到e1的同时, 我们可以计算出基本分类器的权重α1. 然后继续计算得到D2, 就可以进行下去了. 大概的示意如下:

# 一共训练 M 轮, 算法的大体过程如下:
D1 -> G1 -> e1 -> α1 -> D2.... -> Dm -> Gm -> em -> αm -> Dm+1 -> ... -> αM -> end

# 最终我们训练所得的目标分类器:
G(x) = sign(f(x))
# 其中f(x)为M轮训练的基本分类器的加权和
f(x) = α1*G1 + α2*G2 + ... + αm*Gm + ... + αM*GM

下面详细说明:
符号说明:

• Dm表示样本集的权重(w_m1, w_m2, ... ,w_{m, i}, ... , w_{m, N}), 下标m表示第几轮, i表示第i个样本, 共有N个样本.(AdaBoost思想的第一部分通过该参数体现)
• Gm表示第m轮我们训练出来的基本分类器
• em表示第m轮的分类器的错误率
• αm表示第m轮我们训练出来的分类器的权重(AdaBoost思想的第二部分通过该参数体现)
• f(x)m表示第m轮的分类器

正式开始:

第一步, 初始化样本的权重, 我们并未开始分类, 所以一视同仁定义为:

初始化样本权重

初始条件已经有了, 对于下面的训练过程都一样的, 就是从第一轮循环然后循环至M了.

然后一般的, 对于第m次训练过程, 我们有样本权重D_m, 然后通过样本训练一个基本分类器Gm, 然后这里的基本分类器是什么, 我们并不关心(但是这个基本分类器必须比随机猜想要好, 要不就没有意义了). 为了简单起见, 不妨设我们要解决的是一个二分类问题.
然后这个我们就得到了一个基本分类器:

基本分类器

第二步, 计算Gm(x)在训练数据集上的分类错误率.
I(x)函数的意思是: 1 if x == true else 0
也就是说, 我们的分类错误率定义为错误样本的权重之和.

分类错误率

第三步, 计算Gm的系数αm:

αm

关于这个函数, 我简单花了一个图:

αm和em的关系

可以明显的看出来:

• 当em小于0.5, 接近于0的时候, 权值为很接近于正无穷
• 当em大于0.5, 接近于1的时候, 权值为很接近于负无穷

这样定义权值符合我们的认知.

此时, 计算得了αm, 我们可以得到训练到第m步的分类器:
G(x) = sign(f(x))
其中:
f(x) = α1G1 + α2G2 + ... + αm*Gm
在这里我们就可以看到训练器在第m步的时候的分类正确率了.

同时也可以计算下一次(m+1次)训练样本的权重了:

m+1次训练所需的样本的权值计算

这里的Zm是规范化因子, 保证所有的样本的权重之和等于1(错误率是错误样本的权重和, 所以错误率也绝对不会超过1).

Zm

观察 exp( -yi * α * Gm),

• 当分类正确的时候, α权值大, 然后yi * Gm为正, 所以整体的值是变小的.
• 当分类错误的时候, α权值小, 然后yi * Gm为负, 所以整体的值是变大的.

然后该式子再乘以之前的权值, 表示这是一个变化的过程.
从中我们可以体会, 要是之前分错的样本, 现在还分错, 那么权重会变得更大,
要是之前分对的样本, 现在还是分对, 那么权重将会变得更小,
要是之前分错的样本, 现在分对了, 那么权重将会衰减变小, 但是也不会变得太小.

最后训练至M步停止, 我们的分类器诞生了:

最终的分类器

其中, f(x)为基本分类器的线性组合:

基本分类器的线性组合

.....