集成学习之Boosting —— Gradient Boosting原理

  • 时间:
  • 浏览:0
  • 来源:大发欢乐生肖APP下载_大发欢乐生肖APP官网

(a) 计算负梯度: \(\tilde{y}_i = -\frac{\partial L(y_i,f_{m-1}(x_i))}{\partial f_{m-1}(x_i)}, \qquad i = 1,2 \cdots N\)

上一篇介绍了AdaBoost算法,AdaBoost每一轮基学习器训练并且都不 更新样本权重,再训练下2个 多学习器,最后将所有的基学习器加权组合。AdaBoost使用的是指数损失,否则 损失函数的缺点是对于异常点非常敏感,(关于各种损失函数可见并且的文章: 常见回归和分类损失函数比较),因而通常在噪音比较多的数据集上表现不佳。Gradient Boosting在这方面进行了改进,使得都可不能不能 使用任何损失函数 (假如损失函数是连续可导的),从前否则 比较robust的损失函数就能得以应用,使模型抗噪音能力更强。

借用bootstrap的思想,每一轮训练时只使用一偏离 样本,不同点是这里的采样是无放回抽样,否则 最好的法子 被称为Stochastic Gradient Boosting。对于单棵树来说,只使用一偏离 样本拟合会增加单棵树的偏差和方差,然而subsampling会使树与树之间的相关性减少,从而降低模型的整体方差,越来太满之都不 提高准确性。

输出\(f_M(x)\)

决策树是非参数模型,这从不原因分析分析其越来越参数,只是在训练并且参数数量是不选者的,否则 完整篇 生长的决策树有着较大的自由度,能最大化地拟合训练数据。然而单颗决策树是不稳定的,样本数相同的训练集产生微小变动就能原因分析分析最终模型的较大差异,即模型的方差大,泛化性能不好。集成学习的另一代表Bagging是对付否则 哪些地方的疑问的一大利器 (详见前一篇文章Bagging与方差) 。而Bagging的拓展算法 —— 随机森林,通过在树内部人员结点的分裂过程中,随机选者固定数量的内部人员纳入分裂的候选项,从前就进一步降低了单模型之间的相关性,总体模型的方差也比Bagging更低。

初始化: \(f_0(x) = \mathop{\arg\min}\limits_\gamma \sum\limits_{i=1}^N L(y_i, \gamma)\)

对比式 (1.2)和 (1.3),都可不能不能 发现若将\(h_m(x) \approx -\frac{\partial L(y,f_{m-1}(x))}{\partial f_{m-1}(x)}\),即用基学习器\(h_m(x)\)拟合前一轮模型损失函数的负梯度,只是通过梯度下降法最小化\(L(f)\) 。肯能\(f(x)\)实际为函数,越来太满该最好的法子 被认为是函数空间的梯度下降。

负梯度也被称为“响应 (response)”或“伪残差 (pseudo residual)”,从名字都可不能不能 看出是2个 多与残差接近的概念。直觉上来看,残差\(r = y-f(x)\)越大,表明前一轮学习器\(f(x)\)的结果与真实值\(y\)相差较大,越来越下一轮学习器通过拟合残差或负梯度,就能纠正并且的学习器犯错较大的地方。

即先求出树划分出的区域,而相应的\(b_{jm} = \mathop{mean} \limits_{x \in R_{jm}} \tilde{y}_{im}\)为该区域的平均值。

输出\(f_M(x)\)

(a) 计算负梯度: \(\tilde{y}_i = -\frac{\partial L(y_i,f_{m-1}(x_i))}{\partial f_{m-1}(x_i)}, \qquad i = 1,2 \cdots N\)

因而在第m步朋友 的目标是最小化损失函数 \(L(f) = \sum\limits_{i=1}^NL(y_i,f_m(x_i))\),进而求得相应的基学习器。若将\(f(x)\)当成参数,则同样都可不能不能 使用梯度下降法:

\[f_m(x) = f_{m-1}(x) - \rho_m \cdot \frac{\partial}{\partial f_{m-1}(x)}L(y,f_{m-1}(x)) \tag{1.3}\]

(d) \(f_m(x) = f_{m-1}(x) + \rho_m h_m(x\,;\,w_m)\)

对于单棵树T,用下式来衡量每个内部人员\(X_l\)的重要性:\[\mathcal{I}_{l}^2(T) = \sum\limits_{t=1}^{J-1}\hat{i}_t^2I(v(t) = l)\]

肯能是分类哪些地方的疑问,最后输出\(f_M(x)\)前会进行概率估计:设 \(P = P(y=1|x)\)\[f(x) = \frac12 log\frac{P(y=1|x)}{P(y=-1|x)} = \frac12log \frac{P}{1-P} \quad \color{Blue}{\Longrightarrow}\quad P = P(y=1|x) = \frac{1}{1+e^{-2f(x)}} \;\in \left\{0,1 \right\}\]

单棵决策树的可解释性很强,GBDT则继承了否则 优点。

其中\(J\)表示叶结点 (leaf node) 数量,\(J-1\)表示内部人员结点 (internal node) 数量,\(X_{v(t)}\)是与内部人员结点t相关联的分裂内部人员。对于每个内部人员结点t,用内部人员\(X_{v(t)}\)来模拟划分内部人员空间,得到2个 多分裂后的平方误差减几滴 ,即\(\hat{i}^2_t\),最后将所有内部人员节点上的误差减几滴 加起来,只是内部人员\(X_l\)的重要性。总误差减少地太满,该内部人员就越重要。

区别在于指数损失容易受异常点的影响,严重不足robust,且非要用于二分类哪些地方的疑问。越来太满像scikit-learn中GradientBoostingClassifier的默认损失函数只是deviance。

变为:

\[f_m(x) = f_{m-1}(x) + \nu \rho_m h_m(x\,;\,w_m)\]

subsampling的从前好处是肯能只使用一偏离 样本进行训练,越来太满能显著降低计算开销。

/

Gradient Boosting算法理论上都可不能不能 选者多种不同的学习算法作为基学习器,但实际使用地最多的无疑是决策树,这从不偶然。决策树有越来太满优良的内部人员,比如能灵活解决各种类型的数据,包括连续值和离散值;对缺失值不敏感;不需用做内部人员标准化/归一化;可解释性好等等,但其致命缺点是不稳定,原因分析分析容易过拟合,因而越来太满并且准确率不如否则 算法。

(b) 通过最小化平方误差,用基学习器\(h_m(x)\)拟合\(\tilde{y_i}\)\(w_m = \mathop{\arg\min}\limits_w \sum\limits_{i=1}^{N} \left[\tilde{y}_i - h_m(x_i\,;\,w) \right]^2\)

不加限制完整篇 生成的树同样肯能会学的越快原因分析分析过拟合,因而通常对其进行预剪枝。常用的最好的法子 是限制树的强度(scikit-learn中的max_depth)等。

这里首先回顾一下梯度下降 (Gradient Descend)。机器学习的一大主要步骤是通过优化最好的法子 最小化损失函数\(L(\theta)\),进而求出对应的参数\(\theta\)。梯度下降是经典的数值优化最好的法子 ,其参数更新公式:

否则 单棵决策树可表示为 \(h(x\,;\,\left \{R_j,b_j \right \}_1^J) = \sum \limits_{j=1}^J b_j I(x \in R_j)\),其中\(\left \{R_j \right \}_1^J\)为划分出来的独立区域 (即各个叶结点),\(\left \{ b_j \right \}_1^J\)为各区域上的输出值。为了求出否则 个 多参数,于是上方Gradient Boosting中的2.b步变为:

\[\left \{ R_{jm} \right\}_1^J = \mathop{\arg\min}\limits_{\left \{ R_{jm} \right\}_1^J}\sum\limits_{i=1}^N \left [\tilde{y}_i - h_m(x_i\,;\,\left \{R_{jm},b_{jm} \right\}_1^J) \right]^2\]

决策树都可不能不能 看作是2个 多分段函数,将内部人员空间划分为多个独立区域,在每个区域预测2个 多常数,如下图所示:

for m=1 to M:

对于每个区域\(R_j\)的最优值为:\(\gamma_j = \mathop{\arg\min}\limits_\gamma \sum\limits_{x \in R_j} L(y,f_{m-1}(x)+\gamma) = \mathop{\arg\min}\limits_\gamma \sum \limits_{x \in R_j} log(1+e^{-2y(f_{m-1}(x)+\gamma)})\)

常用的损失函数为平方损失 (squared loss),绝对值损失 (absolute loss),Huber损失 (huber loss),下面给出每各人的负梯度 (来自ESL 350页):

都可不能不能 都看这与指数损失的目标函数一样,都不 对数几率,见下图 (来自MLAPP 566页):

与回归提升树的流程类事,求logistic loss的负梯度为:\(\tilde{y} = -\frac{\partial \, log(1+e^{-2yf(x)})}{\partial f(x)} = -\frac{-2y e^{-2yf(x)}}{1+e^{-2yf(x)}} = \frac{2y}{1+e^{2yf(x)}}\)

(b) \(\left \{ R_{jm} \right\}_1^J = \mathop{\arg\min}\limits_{\left \{ R_{jm} \right\}_1^J}\sum\limits_{i=1}^N \left [\tilde{y}_i - h_m(x_i\,;\,\left \{R_{jm},b_{jm} \right\}_1^J) \right]^2\)

Gradient Boosting 采用和AdaBoost同样的加法模型,在第m次迭代中,前m-2个 多基学习器都不 固定的,即\[f_m(x) = f_{m-1}(x) + \rho_m h_m(x) \tag{1.2}\]

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

\[f_m(x) = f_{m-1}(x) + \rho_m h_m(x\,;\,w_m)\]

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

对于M棵树的集成而言,内部人员重要性只是各棵树相应值的平均:\[\mathcal{I}_{l}^2 = \frac1M\sum\limits_{m=1}^M\mathcal{I}_l^2(T_m)\]

\[ \theta = \theta - \alpha \cdot \frac{\partial}{\partial \theta}L(\theta) \tag{1.1}\]

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

(c) 使用line search选者步长\(\rho_m\),以使\(L\)最小,\(\rho_m = \mathop{\arg\min}\limits_{\rho} \sum\limits_{i=1}^{N} L(y_i,f_{m-1}(x_i) + \rho h_m(x_i\,;\,w_m))\)

for m=1 to M:

初始化: \(f_0(x) = \mathop{\arg\min}\limits_\gamma \sum\limits_{i=1}^N L(y_i, \gamma)\)

将GBDT由回归拓展到分类,关键是损失函数的选者。肯能选者了指数损失 (exponential loss),则退化为AdaBoost算法。另这名常用的分类损失函数为logistic loss,形式为\(L(y,f(x)) = log(1+e^{-2yf(x)})\)

要将其最小化,则对于\(f(x)​\)求导并令其为0:\[\frac{\partial\,log(1+e^{-2yf(x)})}{\partial f(x)} = P(y=1|x) \frac{-2e^{-2f(x)}}{1+e^{-2f(x)}} + P(y=-1|x) \frac{2e^{2f(x)}}{1+e^{2f(x)}} = 0 \quad \Longrightarrow \quad f(x) = \frac12 log\frac{P(y=1|x)}{P(y=-1|x)}\]

上式难以直接求出,否则 常用近似值代替: \(\gamma_j = \frac{\sum\limits_{x \in R_j}\tilde{y}}{\sum\limits_{x \in R_j}|\tilde{y}|(2-|\tilde{y}|)}\)

(d) \(f_m(x) = f_{m-1}(x) + \sum\limits_{j=1}^J \gamma_{jm}I(x \in R_{jm})\)

当事人面,决策树和Gradient Boosting结合诞生了GBDT,GBDT继承了决策树的诸多优点,一块儿也改进了其缺点。肯能GBDT采用的树都不 多样化度低的树,越来太满方差很小,通过梯度提升的最好的法子 集成多个决策树,最终有有助于很好的解决过拟合的哪些地方的疑问。然而Boosting共有的缺点为训练是按顺序的,难以并行,从前在大规模数据上肯能原因分析分析强度过慢,所幸近年来XGBoost和LightGBM的再次出显都极大缓解了否则 哪些地方的疑问,后文详述。

(c) \(\gamma_{jm} = \mathop{\arg\min}\limits_\gamma \sum\limits_{x_i \in R_{jm}}L(y_i,f_{m-1}(x_i)+\gamma)\)

Boosting的基本思想是通过这名最好的法子 使得每一轮基学习器在训练过程中更加关注上一轮学习错误的样本,区别在于是采用何种最好的法子 ?AdaBoost采用的是增去掉 一轮学习错误样本的权重的策略,而在Gradient Boosting中则将负梯度作为上一轮基学习器犯错的衡量指标,在下一轮学习中通过拟合负梯度来纠正上一轮犯的错误。这里的关键哪些地方的疑问是:为哪些地方通过拟合负梯度就能纠正上一轮的错误了?Gradient Boosting的发明权者给出的答案是:函数空间的梯度下降。

接下来注意到2.c步中求出的\(\rho_m\)对于整棵树中所有区域都不 一样的,从前肯能从不让使损失最小,否则 Friedman提出都可不能不能 对每个区域\(R_j\)分别求2个 多最优的值\(\gamma_{jm} = \rho_m b_{jm}\),则2.c步变为:

\[\gamma_{jm} = \mathop{\arg\min}\limits_\gamma \sum\limits_{x_i \in R_{jm}}L(y_i,f_{m-1}(x_i)+\gamma)\]

在Gradient Boosting框架中,最常用的基学习器是决策树 (一般是CART),二者结合就成了著名的梯度提升树 (Gradient Boosting Decision Tree, GBDT)算法。下面先叙述回归哪些地方的疑问,再叙述分类哪些地方的疑问。注意GBDT不论是用于回取消是分类,其基学习器 (即单颗决策树) 都不 回归树,即使是分类哪些地方的疑问也是将最后的预测值映射为概率。