中国建设管理信息网站网络服务提供者接到权利人

当前位置： 首页 > news >正文

中国建设管理信息网站,网络服务提供者接到权利人,网页设计作业动态,wordpress page 模板机器学习笔记之集成学习——Gradient Boosting引言回顾#xff1a;Boosting\text{Boosting}Boosting算法思想与AdaBoost\text{AdaBoost}AdaBoostGradient Boosting\text{Gradient Boosting}Gradient Boosting算法介绍场景构建算法过程迭代过程与梯度下降法之间的关联关系引言 … 机器学习笔记之集成学习——Gradient Boosting引言回顾Boosting\text{Boosting}Boosting算法思想与AdaBoost\text{AdaBoost}AdaBoostGradient Boosting\text{Gradient Boosting}Gradient Boosting算法介绍场景构建算法过程迭代过程与梯度下降法之间的关联关系引言 上一节介绍了Boosting\text{Boosting}Boosting算法思想。并以加性模型的AdaBoost\text{AdaBoost}AdaBoost为例介绍了理论推导过程。本节将继续介绍Boosting\text{Boosting}Boosting算法系列的另一个样例——Gradient Boosting\text{Gradient Boosting}Gradient Boosting。 回顾Boosting\text{Boosting}Boosting算法思想与AdaBoost\text{AdaBoost}AdaBoost 关于Boosting\text{Boosting}Boosting算法思想可表示为在迭代过程中通过不断学习出新的基学习器ht(x)(t1,2,⋯,T)ht(x)(t1,2,\cdots,\mathcal T)ht​(x)(t1,2,⋯,T)使得它们能够更关注之前迭代过程中的基学习器预测误差较大的样本最终使得基学习器融合的强学习器 能够覆盖更多的样本并使得这些样本的预测偏差较小。 基于加性模型的AdaBoost\text{AdaBoost}AdaBoost算法描述表示如下 这里仅描述的是‘二分类任务’关于样本标签y(i)(i1,2,⋯,N)∈{−1,1}y^{(i)}(i1,2,\cdots,N) \in {-1,1}y(i)(i1,2,⋯,N)∈{−1,1}. 输入(Input)(\text{Input})(Input)训练集D{x(i),y(i)}i1N\mathcal D {x^{(i)},y^{(i)}}{i1}^ND{x(i),y(i)}i1N​基学习算法K\mathcal KK迭代次数T\mathcal TT初始化(Initialization\text{Initialization}Initialization)Dinit1N\begin{aligned} \mathcal D_{init} \frac{1}{N}\end{aligned}Dinit​N1​​算法过程(Algorithmic Process\text{Algorithmic Process}Algorithmic Process)1.1.1. for t1,2,⋯,Tt1,2,\cdots,\mathcal Tt1,2,⋯,T do2.2.2.   htK(D,Dt);h_t \mathcal K(\mathcal D,\mathcal D_t);ht​K(D,Dt​); 3.3.3.   ϵtPx∼Dt[ht(x)≠f(x)]\epsilont \mathcal P{x \sim \mathcal D_t} \left[h_t(x) \neq f(x)\right]ϵt​Px∼Dt​​[ht​(x)f(x)]4.4.4.   if ϵt0.5:\epsilon_t 0.5:ϵt​0.5:5.5.5.      break6.6.6.   else7.7.7.      αt12ln⁡(1−ϵtϵt)\alpha_t \frac{1}{2} \ln \left(\frac{1 - \epsilon_t}{\epsilont}\right)αt​21​ln(ϵt​1−ϵt​​)8.8.8.      Dt11Zt⋅Dt⋅exp⁡{−f(x)⋅αtht}\mathcal D{t1} \frac{1}{\mathcal Z_t} \cdot \mathcal D_t \cdot \exp{-f(x) \cdot \alpha_tht}Dt1​Zt​1​⋅Dt​⋅exp{−f(x)⋅αt​ht​}9.9.9. end for输出(Output\text{Output}Output)H(x)Sign(∑t1Tαtht)\mathcal H(x) \text{Sign}(\sum{t1}^{\mathcal T} \alpha_th_t)H(x)Sign(∑t1T​αt​ht​) 观察上述算法对于学习出的基学习器htK(D,Dt)h_t \mathcal K(\mathcal D,\mathcal D_t)ht​K(D,Dt​)其中Dt\mathcal DtDt​表示样本的采样权重。也可以理解为样本被关注的程度。 以555个样本组成的数据集为例初始状态下它们各自的权重信息是相等状态 Dinit⇒[15,15,15,15,15]\mathcal D{init} \Rightarrow \left[\frac{1}{5},\frac{1}{5},\frac{1}{5},\frac{1}{5},\frac{1}{5}\right]Dinit​⇒[51​,51​,51​,51​,51​] 经过ttt次迭代后得到的权重结果可能是这个样子 Dt⇒[110,110,25,15,15]\mathcal D_t \Rightarrow \left[\frac{1}{10},\frac{1}{10},\frac{2}{5},\frac{1}{5},\frac{1}{5}\right]Dt​⇒[101​,101​,52​,51​,51​] 比较这两组权重可以发现对于样本的关注度转移了。可以想象 对于x(1),x(2)x^{(1)},x^{(2)}x(1),x(2)两个样本ttt次迭代之前学习的基学习器h1,⋯,ht−1h1,\cdots,h{t-1}h1​,⋯,ht−1​相比之下能够较容易地将这两个样本预测正确相反被分配权重较高的样本如样本x(3)x^{(3)}x(3)它就需要当前迭代的基学习器hth_tht​进行学习。如果依然有f(x(3))≠ht(x(3))f(x^{(3)})\neq ht(x^{(3)})f(x(3))ht​(x(3))只能再次分配权重让t1t1t1次迭代的基学习器ht1h{t1}ht1​去学习x(3)x^{(3)}x(3)以此类推。 通过上面的算法流程可以发现关于权重分布Dt\mathcal D_tDt​它并不是我们想要关注的对象。我们真正关注的对象只有αt\alpha_tαt​和hththt​。它的更新顺序表示为 Dinit⇒h1,α1⇒D1⇒⋯⇒DT−1⇒hT,αT⇒DT\mathcal D{init} \Rightarrow h_1,\alpha_1 \Rightarrow \mathcal D1 \Rightarrow \cdots \Rightarrow \mathcal D{\mathcal T-1} \Rightarrow h{\mathcal T},\alpha{\mathcal T} \Rightarrow \mathcal D_{\mathcal T}Dinit​⇒h1​,α1​⇒D1​⇒⋯⇒DT−1​⇒hT​,αT​⇒DT​ 关于加性模型的AdaBoost\text{AdaBoost}AdaBoost在每次迭代学习新的基学习器 过程中我们只是对训练集D\mathcal DD进行重新赋权(Re-Weighting\text{Re-Weighting}Re-Weighting)操作。那么对于不接受带权样本的基学习算法K′\mathcal KK′可以使用重采样(Re-Sampling\text{Re-Sampling}Re-Sampling)实现。 机器学习(周志华著)P177. 不同于重新赋权操作ttt次迭代过程中重采样操作产生的Dt\mathcal D_tDt​不再是权重分布而是真真正正的以t−1t-1t−1次迭代过程中未被学习正确的样本为主体的样本集合。 一般情况下无论是重新赋权还是重采样两种方法没有优劣区别。但重新赋权方法中需要判别ϵtPx∼Dt[ht(x)≠f(x)]\epsilont \mathcal P{x \sim \mathcal D_t} \left[ht(x) \neq f(x)\right]ϵt​Px∼Dt​​[ht​(x)f(x)]的结果是否满足条件如果不满足条件会提前停止迭代。 相反如果是重采样方法相当于每一次迭代均重新设置训练集只要训练集内有样本就不会出现停止迭代的情况。因而可以持续到预设的T\mathcal TT轮迭代完成。 由于概率密度积分的约束因而权重之和必然是1 - 不会出现采不到样本的情况。
Gradient Boosting\text{Gradient Boosting}Gradient Boosting算法介绍 场景构建 依然假设数据集合D{(x(i),y(i))}i1N\mathcal D {(x^{(i)},y^{(i)})}{i1}^ND{(x(i),y(i))}i1N​并且定义一个初始状态下预测模型Hinit(x)\mathcal H{init}(x)Hinit​(x)并初始化它的模型结果 Hinit(x(i))0i1,2,⋯,N\mathcal H{init}(x^{(i)}) 0 \quad i1,2,\cdots,NHinit​(x(i))0i1,2,⋯,N 算法过程 这里以第ttt次迭代为例并且假设我们基于数据集D\mathcal DD处理一个回归任务 在t−1t-1t−1次迭代后我们得到的数据集合Dt−1\mathcal D{t-1}Dt−1​表示如下 Dt−1{(x(i),y(i)−Ht−1(x(i)))}i1N\mathcal D{t-1} {(x^{(i)},y^{(i)} - \mathcal H{t-1}(x^{(i)}))}{i1}^NDt−1​{(x(i),y(i)−Ht−1​(x(i)))}i1N​ 其中样本特征x(i)(i1,2,⋯,N)x^{(i)}(i1,2,\cdots,N)x(i)(i1,2,⋯,N)未发生变化而对应标签表示为真实标签y(i)y^{(i)}y(i)与t−1t-1t−1时刻预测模型Ht−1(x)\mathcal H{t-1}(x)Ht−1​(x)关于对应样本x(i)x^{(i)}x(i)的预测结果Ht−1(x(i))\mathcal H{t-1}(x^{(i)})Ht−1​(x(i))之间的残差信息(Residuals\text{Residuals}Residuals) 当t1t1t1时,H0(x(i))Hinit(x(i))0\mathcal H0(x^{(i)}) \mathcal H{init}(x^{(i)}) 0H0​(x(i))Hinit​(x(i))0。这意味着‘初始时刻’就在原始的数据集合D\mathcal DD上进行训练。 y(i)−Ht−1(x(i))y^{(i)} - \mathcal H{t-1}(x^{(i)})y(i)−Ht−1​(x(i)) 以Dt−1\mathcal D{t-1}Dt−1​作为第ttt次迭代步骤的数据集并通过学习算法K\mathcal KK从该数据集训练出一个新的基学习器(Base Learner\text{Base Learner}Base Learner)hth_tht​ htK(Dt−1)ht \mathcal K(\mathcal D{t-1})ht​K(Dt−1​) 这意味着hththt​作为学习的并不是关于真实标签的信息而是t−1t-1t−1时刻的预测模型Ht−1(x)\mathcal H{t-1}(x)Ht−1​(x)对于真实标签拟合不足的部分。也就是说Ht−1(x)\mathcal H_{t-1}(x)Ht−1​(x)对于真实标签没有拟合的部分由新训练的基学习器hththt​去拟合。 按照上述逻辑我们需要将t−1t-1t−1时刻预测模型Ht−1(x)\mathcal H{t-1}(x)Ht−1​(x)与ttt时刻的基学习器hth_tht​做融合得到ttt时刻的预测模型Ht(x)\mathcal Ht(x)Ht​(x) Ht(x)Ht−1(x)η⋅ht\mathcal H{t}(x) \mathcal H_{t-1}(x) \eta \cdot h_tHt​(x)Ht−1​(x)η⋅ht​ 观察上式可以发现多了一个学习率(Learning Rate\text{Learning Rate}Learning Rate)η\etaη。它本质上式一个正则项也被称作基学习器hth_tht​的收缩(Shrinkage\text{Shrinkage}Shrinkage)。从常规逻辑的角度既然hththt​能够对残差训练集Dt−1\mathcal D{t-1}Dt−1​进行拟合那么应该将hththt​与Ht−1(x)\mathcal H{t-1}(x)Ht−1​(x)直接融合即可。即η1\eta 1η1。 但真实情况是这种做法可能会导致过拟合(Overfitting)(\text{Overfitting})(Overfitting)。因为不断拟合残差的过程最终可能导致除去初始的若干次迭代之外剩余的迭代中基学习器拟合的信息绝大多数是数据的噪声信息。因而使用学习率来约束基学习器hth_tht​的拟合信息。
迭代过程与梯度下降法之间的关联关系 关于Ht(x)\mathcal Ht(x)Ht​(x)的迭代过程类似于梯度下降法(Gradient Descent,GD\text{Gradient Descent,GD}Gradient Descent,GD)不同于梯度下降法的点在于直接对预测模型自身求解梯度而不是对模型参数。针对回归任务的目标函数我们选择均方误差(Mean-Square Error,MSE\text{Mean-Square Error,MSE}Mean-Square Error,MSE) L1N∑i1N(y(i)−ypred(i))2\mathcal L \frac{1}{N} \sum{i1}^N \left(y^{(i)} - y{pred}^{(i)}\right)^2LN1​i1∑N​(y(i)−ypred(i)​)2 由于样本之间独立同分布(Independent Identically Distribution,IID\text{Independent Identically Distribution,IID}Independent Identically Distribution,IID)这里仅观察某一个样本标签y(i)y^{(i)}y(i)的目标函数信息 L(i)1N(y(i)−ypred(i))2\mathcal L^{(i)} \frac{1}{N}\left(y^{(i)} - y{pred}^{(i)}\right)^2L(i)N1​(y(i)−ypred(i)​)2假设迭代到ttt时刻停止那么此时的预测模型就是Ht(x)\mathcal Ht(x)Ht​(x)。因而关于样本标签y(i)y^{(i)}y(i)的预测结果ypred(i)y{pred}^{(i)}ypred(i)​为 ypred(i)Ht(x(i))y_{pred}^{(i)} \mathcal H_t(x^{(i)})ypred(i)​Ht​(x(i))根据定义我们希望基学习器hththt​能够拟合Ht−1(x)\mathcal H{t-1}(x)Ht−1​(x)拟合不足的部分。关于样本(x(i),y(i))(x^{(i)},y^{(i)})(x(i),y(i))有 ht(x(i))y(i)−Ht−1(x(i))ht(x^{(i)}) y^{(i)} - \mathcal H{t-1}(x^{(i)})ht​(x(i))y(i)−Ht−1​(x(i))至此基于上述逻辑关系我们要求解样本(x(i),y(i))(x^{(i)},y^{(i)})(x(i),y(i))对应的目标函数L(i)\mathcal L^{(i)}L(i)对t−1t-1t−1时刻的预测模型Ht−1(x(i))\mathcal H{t-1}(x^{(i)})Ht−1​(x(i))的梯度 ∂L(i)∂Ht−1(x(i))\frac{\partial \mathcal L^{(i)}}{\partial \mathcal H{t-1}(x^{(i)})}∂Ht−1​(x(i))∂L(i)​ 根据链式求导法则可以将其拆成两项 后续梯度∂L(i)∂Ht−1(x(i))\begin{aligned}\frac{\partial \mathcal L^{(i)}}{\partial \mathcal H{t-1}(x^{(i)})}\end{aligned}∂Ht−1​(x(i))∂L(i)​​使用符号I\mathcal II替代。 I∂L(i)∂Ht(x(i))⋅∂Ht(x(i))∂Ht−1(x(i))\mathcal I \frac{\partial \mathcal L^{(i)}}{\partial \mathcal H{t}(x^{(i)})} \cdot \frac{\partial \mathcal Ht(x^{(i)})}{\partial \mathcal H{t-1}(x^{(i)})}I∂Ht​(x(i))∂L(i)​⋅∂Ht−1​(x(i))∂Ht​(x(i))​ 观察第一项将L(i)\mathcal L^{(i)}L(i)代入有 也将ypred(i)Ht(x(i))y_{pred}^{(i)} \mathcal Ht(x^{(i)})ypred(i)​Ht​(x(i))代入公式。 ∂L(i)∂Ht(x(i))1N⋅2×(y(i)−ypred(i))⋅[0−1]−2N[y(i)−Ht(x(i))]\begin{aligned} \frac{\partial \mathcal L^{(i)}}{\partial \mathcal H{t}(x^{(i)})} \frac{1}{N} \cdot 2 \times(y^{(i)} - y{pred}^{(i)}) \cdot [0 - 1] \ - \frac{2}{N} \left[y^{(i)} - \mathcal H{t}(x^{(i)})\right] \end{aligned}∂Ht​(x(i))∂L(i)​​N1​⋅2×(y(i)−ypred(i)​)⋅[0−1]−N2​[y(i)−Ht​(x(i))]​ 观察第二项它的结果为 这里η⋅ht(x(i))\eta \cdot ht(x^{(i)})η⋅ht​(x(i))与Ht−1(x(i))\mathcal H{t-1}(x^{(i)})Ht−1​(x(i))之间无关视作常数导数结果为000. ∂Ht(x(i))∂Ht−1(x(i))∂∂Ht−1(x(i))[Ht−1(x(i))η⋅ht(x(i))]101\begin{aligned}\frac{\partial \mathcal Ht(x^{(i)})}{\partial \mathcal H{t-1}(x^{(i)})} \frac{\partial}{\partial \mathcal H{t-1}(x^{(i)})} \left[\mathcal H{t-1}(x^{(i)}) \eta \cdot h_t(x^{(i)})\right] \ 1 0 \ 1 \end{aligned}∂Ht−1​(x(i))∂Ht​(x(i))​​∂Ht−1​(x(i))∂​[Ht−1​(x(i))η⋅ht​(x(i))]101​ 至此梯度结果I\mathcal II表示如下 将ht(x(i))y(i)−Ht−1(x(i))ht(x^{(i)}) y^{(i)} - \mathcal H{t-1}(x^{(i)})ht​(x(i))y(i)−Ht−1​(x(i))代入到公式中。 I−2N[y(i)−Ht(x(i))]×1−2N[y(i)−Ht−1(x(i))−η⋅ht(x(i))]−2N(1−η)⋅ht(x(i))\begin{aligned} \mathcal I -\frac{2}{N} \left[y^{(i)} - \mathcal Ht(x^{(i)})\right] \times 1 \ -\frac{2}{N} \left[y^{(i)} - \mathcal H{t-1}(x^{(i)}) - \eta \cdot h_t(x^{(i)})\right] \ -\frac{2}{N} (1 - \eta) \cdot ht(x^{(i)}) \end{aligned}I​−N2​[y(i)−Ht​(x(i))]×1−N2​[y(i)−Ht−1​(x(i))−η⋅ht​(x(i))]−N2​(1−η)⋅ht​(x(i))​此时梯度中2N(1−η)\begin{aligned}\frac{2}{N}(1 - \eta)\end{aligned}N2​(1−η)​仅是一个描述梯度大小的系数和方向无关。因而可以继续化简为如下形式 I∂L(i)∂Ht−1(x(i))∝−ht(x(i))\mathcal I \frac{\partial \mathcal L^{(i)}}{\partial \mathcal H{t-1}(x^{(i)})} \propto - h_t(x^{(i)})I∂Ht−1​(x(i))∂L(i)​∝−ht​(x(i)) 此时再回顾预测模型的迭代公式可以将其转化为 Ht(x(i))Ht−1(x(i))η⋅ht(x(i))⇒Ht(x(i))Ht−1(x(i))−η⋅∂L(i)∂Ht−1(x(i))\begin{aligned} \quad \mathcal Ht(x^{(i)}) \mathcal H{t-1}(x^{(i)}) \eta \cdot ht(x^{(i)}) \ \Rightarrow \mathcal H{t}(x^{(i)}) \mathcal H{t-1}(x^{(i)}) - \eta \cdot \frac{\partial \mathcal L^{(i)}}{\partial \mathcal H{t-1}(x^{(i)})} \end{aligned}​Ht​(x(i))Ht−1​(x(i))η⋅ht​(x(i))⇒Ht​(x(i))Ht−1​(x(i))−η⋅∂Ht−1​(x(i))∂L(i)​​ 可以看出这就是一个梯度下降的标准公式。这说明基学习器hth_tht​它的方向与梯度优化的方向相反。 这里是针对视频中The residuals equal to −∂L∂Hif using MSE as the loss.\begin{aligned}\text{The residuals equal to }-\frac{\partial \mathcal L}{\partial \mathcal H} \text{ if using MSE as the loss.}\end{aligned}The residuals equal to −∂H∂L​ if using MSE as the loss.​的一个推导解释。 需要注意的是一些其他的Boosting\text{Boosting}Boosting函数也可以套用到Gradient Boosting\text{Gradient Boosting}Gradient Boosting这个框架下面。这里仅以回归任务(均方误差)示例描述。 下一节将针对基学习器方向与梯度方向相反的性质介绍梯度提升树(Gradient Boosting Decision Tree,GBDT\text{Gradient Boosting Decision Tree,GBDT}Gradient Boosting Decision Tree,GBDT) 相关参考 5.3 Boosting【斯坦福21秋季实用机器学习中文版】 机器学习(周志华著)