集成学习之Boosting —— AdaBoost原理

  • 时间:
  • 浏览:3
  • 来源:大发快3官方网址—大发快3APP下载

由上图能不到看出,AdaBoost最后得到的强学习器是由一系列的弱学习器的线性组合,此即加法模型:

\[ f(x) = \sum_{m=1}^{M}\alpha_{m}G_{m}(x)\]

\[\begin{equation} \begin{aligned} E(e^{-yf_m(x)}|x) &= E(e^{-y(f_{m-1}(x) + G(x))}|x) \\ &=E(w \cdot e^{-yG(x)}|x) \\&=e^{-G(x)}P_w(y=1|x) + e^{G(x)}P_w(y=-1|x)\end{aligned} \end{equation}\]

\(G(x)\)求导: \(G(x) = \frac12log\frac{P_w(y=1|x)}{P_w(y=-1|x)}\)

式 (1.4) 对\(\alpha\) 求导并使导数为0: $-e^{-\alpha}\sum\limits_{y_{i}=G(x_{i})}w_{i}^{(m)} + e^{\alpha}\sum\limits_{y_i \neq G(x_i)}w_i^{(m)} = 0 $ ,

其中\(P_w(y=1|x)\)是权重为\(w\)下y=1的概率,注意这里的\(G(x)\)都会 基学习器,就让我基学习器的类别概率的一个多对数转换。由此Real AdaBoost的算法流程如下:

能不到看出,\(\epsilon_m​\)越小,最后得到的\(\alpha_m​\)就越大,表明在最后的线性组合中,准确率越高的基学习器会被赋予较大的系数。

一般\(\nu\)要和迭代次数M结合起来使用,较小的\(\nu\)因为 分析不到较大的M。ESL中提到的策略是先将\(\nu\)设得很小 (\(\nu\) < 0.1),再通过early stopping取舍 M,不过现实中也常用cross-validation进行取舍 。

这里一个多关键有哪些的现象:

weight trimming都会 正则化的最好的最好的办法,其主要目的是提高训练速率单位。在AdaBoost的每一轮基学习器训练过程中,不到小偏离 样本的权重较大,因而能产生较大的影响,而这种大偏离 权重小的样本则对训练影响甚微。Weight trimming的思想是每一轮迭代中删除有有哪些低权重的样本,只用高权重样本进行训练。具体是设定一个多阈值 (比如90%或99%),再将所有样本按权重排序,计算权重的偏离 和,偏离 和大于阈值的权重 (样本) 被舍弃,无需用于训练。注意每一轮训练完成后所有样本的权重依然会被重新计算,这因为 分析完后 被舍弃的样本在完后 的迭代中机会权重增加,机会会重新用于训练。

\(w_{i}^{(m+1)} = e^{-y_{i}f_{m}(x_{i})} = e^{-y_{i}(f_{m-1}(x_{i}) + \alpha G(x_{i}))} = e^{-y_if_{m-1}(x_i)}e^{-y_i\alpha_mG_m(x_i)} = w_i^{(m)}e^{-y_i\alpha_mG_m(x_i)}\)

(3) 各基学习器的系数 \(\alpha_m\)

其中\(G_{m}(x)\)为基学习器,\(\alpha_{m}\)为系数。

变为:

在了解了\(G_m(x)\)\(w_i^{(m+1)}\)\(\alpha_m\)的由来后,AdaBoost算法的整体流程也就呼之欲出了:

集成学习大致可分为两大类:Bagging和Boosting。Bagging一般使用强学习器,其个体学习器之间不位于强依赖关系,容易并行。Boosting则使用弱分类器,其个体学习器之间位于强依赖关系,是三种生活序列化最好的最好的办法。Bagging主要关注降低方差,而Boosting主要关注降低偏差。Boosting是一族算法,其主要目标为将弱学习器“提升”为强学习器,大偏离 Boosting算法都会 根据前一个多学习器的训练效果对样本分布进行调整,再根据新的样本分布训练下一个多学习器,这样 迭代M次,最后将一系列弱学习器组合成一个多强学习器。而有有哪些Boosting算法的不同点则主要体现在每轮样本分布的调整最好的最好的办法上。本系列文章先讨论Boosting的两大经典算法 —— AdaBoost和Gradient Boosting,再探讨近年来在各大数据科学比赛中大放异彩的XGBoost和LightGBM。

\[\frac{\partial E(e^{-yf(x)}|x)}{\partial f(x)} = -P(y=1|x) e^{-f(x)} + P(y=-1|x)e^{f(x)} = 0\quad ,\]

\[f(x) = \frac12 log\frac{P(y=1|x)}{P(y=-1|x)},或写为 P(y=1|x) = \frac{1}{1+e^{-2f(x)}}\]

\[f_m(x) = f_{m-1}(x) + \alpha_m G_m(x)\]

输入: 训练数据集 \(T = \left \{(x_1,y_1), (x_2,y_2), \cdots (x_N,y_N)\right \}\)\(y\in\left\{-1,+1 \right\}\),基学习器\(G_m(x)\),训练轮数M

这因为 分析\(sign(f(x))\)达到了贝叶斯最优错误率,即对于每个样本\(x\)都取舍 后验概率最大的类别。若指数损失最小化,则分类错误率也将最小化。这说明指数损失函数是分类任务从前 0-1损失函数的一致性替代函数。机会你这种 替代函数是单调连续可微函数,否则用它代替0-1损失函数作为优化目标。

推导与Discrete AdaBoost这类 ,仍最小化指数损失:

AdaBoost的具体流程为先对每个样本赋予相同的初始权重,每一轮学习器训练完后 都会根据其表现对每个样本的权重进行调整,增加分错样本的权重,从前 先前做错的样本在后续就能得到更多关注,按从前 的过程重复训练出M个学习器,最后进行加权组合,如下图所示。

\[f_m(x) = f_{m-1}(x) + \nu \cdot \alpha_m G_m(x)\]

结合上文,亲戚亲戚大伙儿现在的目标是在指数函数最小的具体情况下求得\(\alpha_{m}\)\(G_{m}(x)\)

\[(\alpha_{m},G_{m}(x)) = \mathop{\arg\min}\limits_{(\alpha,G)}\sum\limits_{i=1}^{N}e^{-y_{i}f_{m}(x_{i})} = \mathop{\arg\min}\limits_{(\alpha,G)}\sum\limits_{i=1}^{N}e^{-y_{i}(f_{m-1}(x_{i}) + \alpha G(x_{i}))} \qquad (1.3)\]

根据 [Friedman et al., 30000] 中的描述,weighting trimming能不到提高计算速率单位,且无需牺牲准确率,下一篇中将通过实现来验证。

(2) 下一轮样本权值\(w_i^{(m+1)}\)

这种个多多有哪些的现象可由加法模型和指数损失函数推导出来。

其中 \((x_{1},y_{1}),(x_{2},y_{2}),\cdots(x_{N},y_{N})\)为训练数据集。

for m=1 to M:

能不到看一遍对于\(\alpha_m>0\),若\(y_i = G_m(x_i)\),则\(w_i^{(m+1)} = w_i^{(m)}e^{-\alpha_m}\),表明前一轮被正确分类样本的权值会减小; 若\(y_i \neq G_m(x_i)\),则\(w_i^{(m+1)} = w_i^{(m)}e^{\alpha_m}\),表明前一轮误分类样本的权值会增大。

对每个基学习器乘以一个多系数\(\nu\) (0 < \(\nu\) <1),使其对最终模型的贡献减小,从而处里学的太快产生过拟合。\(\nu\)又称学习率,即scikit-learn中的 learning rate。于是上文的加法模型就从:

\(G_m(x)\)在训练集上的带权误差率为 \(\epsilon_m = \frac{\sum\limits_{i=1}^Nw_i^{(m)}\mathbb{I}(y_i \neq G_m(x_i))}{\sum\limits_{i=1}^Nw_i^{(m)}}\)

在第m步,亲戚亲戚大伙儿的目标是最小化一个多指定的损失函数\(L(y,f(x))\),即 :

\[\min\limits_{(\alpha_{m}\,,\,G_{m})}\sum\limits_{i=1}^{N}L(y_{i}, \,\sum\limits_{m=1}^{M}\alpha_{m}G_{m}(x_{i})) \qquad (1.1)\]

机会是最小化指数损失,则将上式求导并令其为0:

这是个繁复的全局优化有哪些的现象,通常亲戚亲戚大伙儿使用其繁复版,即假设在第m次迭代中,前m-1次的系数\(\alpha\)和基学习器\(G(x)\)都会 固定的,则\(f_{m}(x) = f_{m-1}(x) + \alpha_{m}G_{m}(x)\),从前 在第m步亲戚亲戚大伙儿只需就当前的\(\alpha_{m}\)\(G_{m}(x)\)最小化损失函数。

\[\sum\limits_{i=1}^{N}w_{i}^{(m)}e^{-y_i\alpha G(x_i)} = e^{-\alpha}\sum\limits_{y_{i}=G(x_{i})}w_{i}^{(m)} + e^{\alpha}\sum\limits_{y_i \neq G(x_i)}w_i^{(m)} \qquad\qquad (1.4)\]

求令式 (1.5) 最小的\(G_m(x)\)等价于令 \(\sum\limits_{i=1}^Nw_i^{(m)}\mathbb{I}(y_i \neq G(x_i))\) 最小化的\(G_m(x)\),否则可认为每一轮基学习器都会 通过最小化带权重误差得到。

AdaBoost是一个多具有里程碑意义的算法,机会其是第一个多具有适应性的算法,即能适应弱学习器该人 的训练误差率,这也是其名称的由来(Ada为Adaptive的简写)。

由中间几只式子能不到得到AdaBoost算法的几只关键点:

输出最终模型: \(G(x) = sign\left[\sum\limits_{m=1}^M\alpha_mG_m(x) \right]\)

若将指数损失表示为期望值的形式:

仔细看,这不就让我logistic regression吗?二者只差系数\(\frac12\),否则每一轮最小化指数损失人太好就让我在训练一个多logistic regression模型,以逼近对数几率 (log odds)。

将数据集划分为训练集和测试集,在训练过程中不断检查在测试集上的表现,机会测试集上的准确率下降到一定阈值之下,则停止训练,取舍 当前的迭代次数M,这同样是处里过拟合的手段。

两边同乘以\(e^\alpha\),得 \(e^{2\alpha} = \frac{\sum\limits_{y_{i}=G(x_{i})}w_{i}^{(m)}}{\sum\limits_{y_{i} \neq G(x_{i})}w_{i}^{(m)}} = \frac{1-\epsilon_m}{\epsilon_m}\) \(\quad {\color{Red}{\Longrightarrow}} \quad\) \(\alpha_m = \frac{1}{2}ln\frac{1-\epsilon_m}{\epsilon_m}\)

/

AdaBoost的原始论文 [Freund & Schapire, 1997] 无须使用了上文中的推导最好的最好的办法,就让我基于PAC学习框架下进行解释的。上文的将AdaBoost视为 “加法模型 + 指数损失” 的观点,由斯坦福的几位统计系大牛 [Friedman et al., 30000] 提出,因而你这种 派也被称为“统计视角”。沿着你这种 路子,若将指数损失替换为这种损失函数并依此不断训练新学习器,则诞生了Gradient Boosting算法,是为下一篇的主题。

AdaBoost采用的损失函数为指数损失,形式如下:

\[L(y,\,f(x)) = e^{-yf(x)} \qquad (1.2)\]

下图显示通过将简单学习器加权组合就能生成具有繁复边界的强学习器。

上文推导出的AdaBoost算法被称为"Discrete AdaBoost",机会其各个基学习器\(G_m(x)\)的输出为{-1,1} 。机会将基学习器的输出改为一个多类别概率,则产生了Real AdaBoost。Real AdaBoost通常在更少的轮数达到更高的精度,像scikit-learn中的AdaBoostClassifier就让我默认优先使用Real AdaBoost (SAMME.R),不过Real AdaBoost中的基学习器不到支持概率估计。

\[E(e^{-yf(x)}|x) = P(y=1|x)e^{-f(x)} + P(y=-1|x)e^{f(x)}\]

于是,

\[= (e^{\alpha} - e^{-\alpha})\sum\limits_{i=1}^Nw_i^{(m)}\mathbb{I}(y_i \neq G(x_i)) + e^{-\alpha}\sum\limits_{i=1}^Nw_i^{(m)} \qquad\qquad\quad (1.5)\]

\[\begin{equation} \begin{aligned} sign(f(x)) &= sign(\frac12 log\frac{P(y=1|x)}{P(y=-1|x)}) \\ & =\left\{\begin{matrix} 1 & \;\; P(y=1|x) > p(y=-1|x)\\ -1 & \;\; P(y=1|x) < P(y=-1|x) \end{matrix}\right. \\&=\mathop{\arg\max} \limits_{y \in\{-1,1\}}P(y|x) \end{aligned} \end{equation}\]

\(w_{i}^{(m)} = e^{-y_{i}f_{m-1}(x_{i})}\),机会\(w_i^{(m)}\)不依赖于\(\alpha\)\(G(x)\),这种这种可认为其是第m步训练完后 赋予每个样本的权重。然而\(w_i^{(m)}\)依赖于\(f_{m-1}(x_i)\),这种这种每一轮迭代会改变。

于是式 (1.3) 变为:

(1) 基学习器\(G_m(x)\) :