AdaBoost

总结一下 AdaBoost

参考文献：西瓜书，南瓜书，"ADDITIVE LOGISTIC REGRESSION: A STATISTICAL VIEW OF BOOSTING"

集成学习（ensemble learning）通过构建多个个体学习器，并将它们结合在一起构成集成学习器来完成学习任务。

集成学习的两个关键要素就是个体学习器（基学习器）和结合策略。

• 假设个体学习器错误率相互独立的前提下，可以证明随着集成数量的增加，集成错误率将以指数级下降并趋于 0.

根据结合策略的不同，目前集成学习的方法可大体分为 Boosting 和 Bagging 两大类。

Boosting

Boosting（提升学习）是一族将弱学习器提升为强学习器的算法，个体学习器之间存在强依赖关系，必须串行生成。

通常的工作机制是：先训练出一个基学习器，根据基学习器的表现对训练样本的分布进行调整，使先前分类错误的样本在后续得到更多关注，然后基于调整后的分布进行训练下一个基学习器。最后将基学习器进行结合。

AdaBoost

AdaBoost 是 Boosting 算法里著名的代表，标准的 AdaBoost 只适用于二分类任务。

假设训练集为 D={(x1,y1),...,(xm,ym)}，其中 xi∈Rn，yi∈{−1,+1} 为样本的类标记。假设训练集 D 里的样本服从某个分布 D，即 x∼D。

第 t 轮训练的基分类器记为 ht(x)，基分类器的加权和记为 H(x)，最终的集成分类器记为 F(x)

AdaBoost

• AdaBoost 算法需要详细解释的地方有两处：①基分类器 ht 的权重为何采用第 6 行的公式来计算②样本分布为何采用第 7 行的公式来更新

AdaBoost 的损失函数 —— 指数损失

根据西瓜书的推导方法，AdaBoost 采用的损失函数为指数损失函数：

lexp(H|D)=Ex∼D[e−yH(x)]

其中 H(x) 是基分类器的加权和，y 是样本的类标记。

H(x)=∑t=1Tαtht(x)

贝叶斯最优错误率

• 最小化指数损失将使最终的集成分类器 F(x) 满足贝叶斯最优错误率：

F(x)=arg⁡maxyP(f(x)=y|x)

当指数损失得到最小化时，对应的条件期望 Ex∼D[e−yH(x)|x] 也一定得到最小化。

Ex∼D[e−yH(x)|x]=e−H(x)P(y=1|x)+eH(x)P(y=−1|x)

此时条件期望对 H(x) 的偏导数为 0：

∂Ex∼D[e−yH(x)|x]∂H(x)=−e−H(x)P(y=1|x)+eH(x)P(y=−1|x)=0

H(x)=12lnP(y=1|x)P(y=−1|x)

F(x)=sign(H(x))=sign(lnP(y=1|x)P(y=−1|x))={1,P(y=1|x)>P(y=−1|x)−1,P(y=1|x)<P(y=−1|x)=arg⁡maxyP(f(x)=y|x)

基分类器权重公式

• 权重 αt 应最小化带权基分类器 αtht 在 t 上的指数损失

αt=arg⁡minαlexp(αht|Dt)

注意到 yht(x)∈{−1,+1}

lexp(αtht|Dt)=Ex∼Dt[e−yαtht(x)]

指数损失 lexp(αtht|Dt) 最小化时，lexp(αtht|Dt) 对基分类器的权重 αt 的偏导数为 0：

∂lexp(αtht|Dt)∂αt=−e−αt(1−ϵt)+eαtϵt=0

αt=12ln(1−ϵtϵt)

从这里还可以看出，当 ϵt>0.5 时有 αt<0。

这说明如果某一个基分类器比随机猜测的效果还差的时候，这个基分类器的权重应当取负数。与其留下效果不好的基分类器，倒不如直接舍弃，所以算法第 5 行要求基分类器的错误率要小于 0.5 才继续训练。

样本分布更新公式

• 下一轮训练的基分类器 ht 应最小化基分类器加权和 Ht−1+αtht 在原始数据分布 D 上的指数损失 lexp(Ht−1+αtht|D)

ht(x)=arg⁡minhlexp(Ht−1+αth|D)

lexp(Ht−1+αtht|D) 展开可以写成： lexp(Ht−1+αtht|D)=Ex∼D[e−yHt−1(x)(e−yht−1(x))αt]

根据算法第 5 行，0<ϵt≤0.5，所以 αt≥0。最小化 lexp(Ht−1+αtht|D) 等价于最小化 lexp(Ht−1+ht|D)

lexp(Ht−1+ht|D)=Ex∼D[e−y(Ht−1(x)+ht(x))]=Ex∼D[e−yHt−1(x)e−yht(x)]

将 e−yht(x) 用泰勒公式展开到二阶近似代替，并注意到 y2=ht(x)2=1

lexp(Ht−1+ht|D)≈Ex∼D[e−yHt−1(x)(1−yht(x)+y2ht(x)22)]=Ex∼D[e−yHt−1(x)(1−yht(x)+12)]

ht(x)=arg⁡minhEx∼DEx∼D[e−yHt−1(x)(1−yh(x)+12)]=arg⁡maxhEx∼D[e−yHt−1(x)yh(x)]

配上一个归一化用的常数因子

1Zt=1Ex∼D[e−yHt−1(x)]

原式可以改写成

ht(x)=arg⁡maxhEx∼D[e−yHt−1(x)Ex∼D[e−yHt−1(x)]yh(x)]

Dt(x)=D(x)e−yHt−1(x)Ex∼D[e−yHt−1(x)]

不难证明 Dt 表示一个新的分布，考虑 Dt+1 和 Dt 的关系

Dt+1(x)=D(x)e−yHt(x)Ex∼D[e−yHt(x)]=D(x)e−yHt−1(x)e−yαtht(x)Ex∼D[e−yHt(x)]=Dt(x)e−yαtht(x)·Ex∼D[e−yHt−1(x)]Ex∼D[e−yHt(x)]

这就得到了算法第 7 行的样本分布更新公式。

在新的分布下最小化分类误差

原式又可以改写成

ht(x)=arg⁡maxhEx∼Dt[yh(x)]

这表明理想的 ht 是在新的分布 Dt 下最小化指数损失。由 y,h(x)∈{−1,+1}，有

yh(x)=1−2I(y≠h(x))

于是原式等价于

ht(x)=arg⁡minhEx∼DtI(y≠h(x))=arg⁡minhP(y≠h(x))

这说明 ht 不仅在分布 Dt 下最小化指数损失，同时也在最小化分类误差