ML算法(三)——Adaboost算法

用户7506105

发布于 2021-08-06 15:24:32

5970

发布于 2021-08-06 15:24:32

文章被收录于专栏：碎片学习录

集成学习在机器学习领域占有非常重要的比重，它在一定条件下可以使得模型泛化效果和神经网络平分秋色，但在可解释性上就更有优势了，此外，它包含的有些比如xgboost、lightgbm、GBDT算法等也是数据竞赛kaggle、天池等的top解决方案中最常用的算法，所以深入研究下数学原理是很有必要的。

集成学习，顾名思义就是会有多个学习器通过某种手段集成到一起的综合算法，在现实生活中，对于一个复杂任务或方案，有多个专家进行评估，而将多个专家的评估结果进行适当的综合所得出的判断，要比其中任何一个专家单独的判断好，毕竟单个个体的评判结果会对噪声误差敏感，所以简单理解集成学习就是集众家之长，这还有另外几层含义就是每个个体都必须具有一定的准确性(比如分类器正确率大于0.5的)和差异性(避免每个学习器都相同)，表现为君子和而不同！只有这样集成下来的学习器才会优于每一个个体。

一般来讲，集成学习分为两种典型的，他们区别是个体学习器间是否存在强依赖关系，如果存在强依赖关系就表明需要按照拓扑结构串行生成，如果不存在则说明可以同时并行训练。前者的代表是Boosting，后者的代表是Bagging和随机森林，本文先解释Boosting中最有代表性的AdaBoost算法。

预备知识

假设一个二分类的场景，即因变量y只有1和-1两个值，对于每个学习器

h_i(\vec{x})

，对于每一个

\vec{x}

,真实因变量值为

y_0

,则定义其预测错误的误差率为

\epsilon = P(h_i(\vec{x}) \neq y_0)

假设集成方法是投票方法(还有其他结合方法，比如加权平均等)，以此结合了T个基学习器，则此时集成学习器为

H(\vec{x}) = sign(\sum_{i=1}^T h_i(x))

这里先假设每个个体学习器

h_i(x)

对应的误差

\epsilon

相互独立，则由二项分布概率公式可知集成学习器的误差为

P(H(\vec{x}) \neq y_0) = \sum_{k=0}^T C_T^k (1-\epsilon)^k \epsilon^{T-k}

以上的组合数公式由一些文献上的不等式证明可以得到

P(H(\vec{x}) \neq y_0) <= exp(-\frac{T(1-2\epsilon)^2}{2})

这里只是用来说明在集成学习中随着个体学习器的总数T增大，集成学习的错误率会呈现指数级下降，并且这里对每个学习器的误差做了独立性假设这在Boosting这种算法中是有些牵强的，但即使不独立随着后面的学习器误差越来越小也可以说明更优的学习器越多那集成后的学习器也会越好

sign为符号函数，以下用

取代

\vec{x}

思想

需要注意的是生成过程中的每个学习器都是强依赖的，且算法是有监督学习

它的思想简单来说就是先从训练数据整体训练一个基学习器(比如

y=sign(h(\vec{x}))

)，再根据这个预测值和实际值的误差对样本分布进行调整(调整样本的权重，使得预测失误的样本权重更大)，然后基于调整后的样本继续训练下一个学习器，循环下去，直到达到给定的学习器数目T或总体误差率小于阈值即可，然后再分别将这些生成的学习器进行集成(线性加权求和,即

sign(\sum_{t=1}^T \alpha_t h_t(x))

，其中权值和每个学习器的误差有关)，最终得到的就是集成后的学习器

还有另一种角度解释，即认为AdaBoost算法是模型为加法模型、损失函数为指数函数、学习算法为前向分步算法时的二类分类学习方法，具体可参考李航老师的《统计学习方法》，比较赞

推导

一些约定

样本数为M，在第t次生成的基分类器为

sign(h_t(x))

，每次的基分类器的权重为

\alpha_t

,每次的误差率为

\epsilon_t

,因为是有监督模型，最后训练好的Adaboost模型为

H(x)

所以假设真实隐射函数为

y=f(x)

(

y\in \{+1, -1\}

), 尤其重要的是这里的损失函数为指数损失函数，即

L(h_t(x)|D_t) = E_{x\in D_t} (exp(-f(x)h_t(x)))

D_t

为自变量在t次生成的分布，之所以用指数损失函数可能是因为求导容易，且如果

H(x)

预测错误，则

f(x)H(x)

一定是-1为负数，所以

L(H|D)

反而会越大

过程

首先初始化每个样本的权值为

\frac{1}{M}

, 毫无疑问是需要使得每次的损失函数最小，这里

f(x)

为已知函数，只有

h_t(x)

是变化的，故对

h_t(x)

函数求导并令其为0，因为

L(h_t(x)|D_t)

为期望，即

\frac{dL(h_t(x)|D_t)}{dh_t(x)} = -exp(h_t(x))P(f(x)=1) + exp(h_t(x))P(f(x)=-1) = 0

推得

h_t(x) = \frac{1}{2} ln \frac{P(f(x)=1)}{P(f(x)=-1)},x\in D_t

所以此时的基分类器为(对数真数大于1则值大于0，反之小于0)

sign(h_t(x)) = \begin{cases} 1, P(f(x)=1) >P(f(x)=-1) \\ -1, P(f(x)=1) < P(f(x)=-1) \end{cases}

= arg\max \limits_{y\in\{-1,+1\}} P(f(x)=y | x), x \in D_t

可以看出如果指数损失函数最小，则分类错误率也会越小，

假设此时的

h_t(x)

的权重为

\alpha_t

，则此时的指数损失函数为

L(\alpha_t h_t(x)|D_t) = E_{x\in D_t} (exp(-f(x)\alpha_th_t(x)))

分离常量后，可以转化成

exp(-\alpha_t)P_{x \in D_t}(f(x)=h_t(x)) + exp(\alpha_t)P_{x \in D_t}(f(x)\neq h_t(x))

由前文误差率

\epsilon_t

的定义，则得到

exp(-\alpha_t)(1-\epsilon_t) + exp(\alpha_t)\epsilon_t

一样的，对权重变量

\alpha_t

求导后并为0后得到

-exp(-\alpha_t)(1-\epsilon_t) + exp(\alpha_t)\epsilon_t = 0

则解得此时的权重为

\alpha_t = \frac{1}{2} ln\frac{1-\epsilon_t}{\epsilon_t}

这个权重除了是学习器的加权系数外，也是样本

D_t

调整的因素

假设此时已经进行到第k次生成了，即此时的分类器函数为

H_{k-1}(x) = \sum_{t=1}^{k-1}\alpha_t h_t(x)

则如果要生成

h_k(x)

则理想情况肯定是

h_k(x)

这个学习器能纠正

H_{k-1}

这个的全部错误，即最小化此时的指数损失函数，即

h_k(x) = arg \min\limits_{h(x)} L(H_{k-1}(x) + h(x) | D_{k-1})

= arg \min\limits_{h(x)} E_{x\in D_{k-1}}[-f(x)h(x) exp(-f(x)H_{k-1}(x))]

因为k-1及以前的都已经算完了，所以一定有

E_{x \in D_{k-1}} [exp(-f(x)H_{k-1}(x))]

为常数，故即转化成

arg \max\limits_{h(x)} [f(x)h(x) \frac{exp(-f(x)H_{k-1}(x))}{E_{x \in D_{k-1}} [exp(-f(x)H_{k-1}(x))]}]

这样做的好处是可以转化成

arg \max\limits_{h(x)} E_{x \in D_{k}} f(x)h(x)

因为此时要求的f(x)h(x)越大则表明之前的指数损失越小，即正确分类的越多，是满足h(x)为理想函数的条件的，所以这里就有了样本权重分布更新函数了，即

D_k = \frac{D_{k-1}(x) exp(-f(x)H_{k-1}(x))}{E_{x \in D_{k-1}} [exp(-f(x)H_{k-1}(x))]}]

更新样本权值的目的是让错误分类样本获得更高的权值，以此数据分布训练的学习器会在这些样本上得到一定程度上的修正。

最后在达到个数T或分类误差小于阈值后停止增加学习器，然后通过计算每个基分类器的误差从而求出权值，最后加权求和，得到最后的模型为

H(x) = sign(\sum_{t=1}^T \alpha_t h_t(x))

每一轮都会检测生成的基学习器是否比随机猜想好，即误差率是否小于0.5，一旦不满足，则抛弃该学习器，然后进行按照当前数据分布进行重新采样来避免只有很少弱学习器的方法，此外对于一些不能接受带权样本作为输入的基学习器也需要按照当前数据分布重采样处理，这样就能让权重越高的数据越多

总结

在推导过程中可知，Adaboost算法会使训练误差不断减小，因为不断修正误分类样本的权重，能基于泛化性相当弱的学习器做出较好的集成，此外如果需要用adaboost算法来做回归问题，也可以参照推导过程，将每次的概率等价为与每次最大误差之间的相对误差，然后以此更新权重系数

\alpha_t

、样本分布

D_t

即可

回归的话，需要注意的此时权重系数是

\alpha_t = \frac{\epsilon_t}{1-\epsilon_t}

，且最后的回归函数为

H(x) = \sum_{t=1}^T (ln \frac{1}{\alpha_t} )h_t(x)

参考资料

《机器学习西瓜书》

《统计学习方法》

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-08-04，如有侵权请联系 cloudcommunity@tencent.com 删除

机器学习

本文分享自碎片学习录微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度