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

  • 时间:
  • 浏览:0
  • 来源:uu快3计划师_uu快3app苹果_全天计划

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

因此单棵决策树可表示为 \(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\)为各区域上的输出值。为了求出这1个 参数,于是里边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\]

Gradient Boosting算法理论上可不也能确定多种不同的学习算法作为基学习器,但实际使用地最多的无疑是决策树,这固然偶然。决策树有其他其他优良的特性,比如能灵活除理各种类型的数据,包括连续值和离散值;对缺失值不敏感;不时要做特性标准化/归一化;可解释性好等等,但其致命缺点是不稳定,因为容易过拟合,因而其他其他也不准确率不如其他算法。

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

(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\)

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

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

不加限制全版生成的树同样因为分析会学的越快因为过拟合,因而通常对其进行预剪枝。常用的最好的方式是限制树的角度(scikit-learn中的max_depth)等。

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

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

输出\(f_M(x)\)

输出\(f_M(x)\)

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

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

将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)}\]

接下来注意到2.c步中求出的\(\rho_m\)对于整棵树中所有区域也不一样的,原来因为分析固然会使损失最小,因此Friedman提出可不也能对每个区域\(R_j\)分别求1个 最优的值\(\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)\]

(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\)

因为分析是分类那此的问题,最后输出\(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\}\]

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

(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))\)

对比式 (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)”,从名字可不也能看出是1个 与残差接近的概念。直觉上来看,残差\(r = y-f(x)\)越大,表明前一轮学习器\(f(x)\)的结果与真实值\(y\)相差较大,没办法 下一轮学习器通过拟合残差或负梯度,就能纠正也不的学习器犯错较大的地方。

对于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}\]

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

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

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

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

与回归提升树的流程这类,求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)}}\)

/

subsampling的原来好处是因为分析只使用一偏离 样本进行训练,其他其他能显著降低计算开销。

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

变为:

\[f_m(x) = f_{m-1}(x) + \nu \rho_m h_m(x\,;\,w_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)})\)

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

\[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}\]

区别在于指数损失容易受异常点的影响,过低robust,且不到用于二分类那此的问题。其他其他像scikit-learn中GradientBoostingClassifier的默认损失函数其他其他我deviance。

(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\)

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

(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每一轮基学习器训练也不也不更新样本权重,再训练下1个 学习器,最后将所有的基学习器加权组合。AdaBoost使用的是指数损失,你其他损失函数的缺点是对于异常点非常敏感,(关于各种损失函数可见也不的文章: 常见回归和分类损失函数比较),因而通常在噪音比较多的数据集上表现不佳。Gradient Boosting在这方面进行了改进,使得可不也能使用任何损失函数 (因此我损失函数是连续可导的),原来其他比较robust的损失函数就能得以应用,使模型抗噪音能力更强。

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

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

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

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

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

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

买车人面,决策树和Gradient Boosting结合诞生了GBDT,GBDT继承了决策树的诸多优点,共同也改进了其缺点。因为分析GBDT采用的树也不错综复杂度低的树,其他其他方差很小,通过梯度提升的最好的方式集成多个决策树,最终也能很好的除理过拟合的那此的问题。然而Boosting共有的缺点为训练是按顺序的,难以并行,原来在大规模数据上因为分析因为角度过慢,所幸近年来XGBoost和LightGBM的经常出现都极大缓解了你其他那此的问题,后文详述。

决策树可不也能看作是1个 分段函数,将特性空间划分为多个独立区域,在每个区域预测1个 常数,如下图所示:

for m=1 to M:

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

for m=1 to M: