GB、GBDT、XGBoost之间紧密相关,GBDT是以决策树CART为基学习器的GB算法,XGBoost扩展和改进了GDBT.

Gradient boosting(GB)

机器学习的学习算法的目标就是优化或者最小化loss function,Gradient boosting的思想是迭代多个(M个)弱的模型,然后将每个弱模型相加,后面的模型$F_{m+1}$(x)基于前面学习模型的$F_m(x)$的效果生成的,关系如下：

$F_{m+1}=F_m(x)+h(x)$

Q:如何生成h(x)?
如果目标函数是回归问题的均方误差,则h(x)需要的是拟合y-$F_m(x)$,这就是基于残差的学习.残差学习在回归中很好理解.但是为了更加一般性(分类、排序问题),实际中往往是基于loss function在函数空间的负梯度学习,对于回归问题$\frac{1}{2}(y-F(x))^2$残差和负梯度也是相同的.L(y,F)中的F不要理解为传统意义上的函数,而是一个函数向量$f(x_1),f(x_2),…,f(x_n)$,向量中的元素个数与训练样本的元素个数相同,因此基于loss function 函数空间的负梯度的学习也称为”伪残差”.
GB流程:

初始化模型为常数值:
$F_0(x)=argmin_{\gamma}\sum_{i=1}^nL(y_i,\gamma)$
迭代生成M个基学习器

计算伪残差(用负梯度来近似残差,负梯度一般认为是loss下降最快的方向) $r_{im}=-[\frac{\partial L(y_i,F(x_i))}{\partial F(x_i)}]_ {F(x)=F_{m-1}(x)}$
基于$\{(x_i,r_{im})\}_{i=1}^n$生成基学习器$h_m(x)$
计算最优的$\gamma_m$ $\gamma_m=argmin_{\gamma}\sum_{i=1}^nL(y_i,F_{m-1}(x_i)+\gamma h_m(x_i))$
更新模型 $F_{m}(x)=F_{m-1}(x)+\gamma_m h_m(x)$

Gradient boosting Decision Tree

GB算法中最典型的基学习器是决策树,尤其是CART.GBDT中的决策树是个弱模型,深度较小一般不会超过5.

回顾CART

CART是二叉树,其既可以用于分类也可以用于回归.分类输出的是样本类别,回归输出的是一个实数.

CART算法有两步:

决策树的生成:分类树用Gini指数最小化准则,回归树用平方误差最小化准则

回归树生成：目标函数是平方误差$\sum_{x_i∈R_m}(y_i-f(x_i))^2$来表示回归树对于训练数据的预测误差.
上述f(x_i)的形式如下:
$f(x)=\sum_{m=1}^Mc_mI(x∈R_m)$
我们注意到,这里有存在符号$R_m和c_m$,$c_m$很简单就是表示在$R_m$中的点贡献的值.并且$R_m$中的最优$\hat{c}_m$是$R_m$上的所有输入实例$x_i$对应的输出$y_i$的均值,即
$\hat{c}_m=ave(y_i|x_i∈R_m)$
$R_m$表示将输入空间进行划分后的一块区域.
$R_1(j,s)=\{x|x^{(j)}≤s\} \ \ \ \ \ \ R_2(j,s)=\{x|x^{(j)}>s\}$
其中j是表示x中的第j个变量$x^{(j)}$,s表示最优切分点.
Q:如何求最优变量j和最优切分点s?
$min_{j,s}[min_{c_1}\sum_{x_i∈R_1(j,s)}(y_i-c_1)^2+min_{c_2}\sum_{x_i∈R_2(j,s)}(y_i-c_2)^2]$
用启发式的方法求上式.
Algorithm:
输入:训练数据集D
输出:回归树f(x)
在训练数据集所在的输入空间中递归地将每个区域划分成两个子区域并决定每个子区域地输出值,构建二叉决策树
(1)选择最优切分变量j与切分点s,求解
$min_{j,s}[min_{c_1}\sum_{x_i∈R_1(j,s)}(y_i-c_1)^2+min_{c_2}\sum_{x_i∈R_2(j,s)}(y_i-c_2)^2]$
(2)用选定地对(j,s)划分区域并决定相应地输出值
$R_1(j,s)=\{x|x^{(j)}≤s\} \ \ \ \ \ \ \ R_2(j,s)={x|x^{(j)}＞s}$ $\hat{c}_m=\frac{1}{N_m}\sum_{x_i∈R_m(j,s)}y_i \ \ \ \ \ x∈R_m,m=1,2$
(3)继续对两个子区域调用(1)(2),直到满足停止条件
(4)将输入空间划分为M个区域$R_1,R_2,…,R_M$,生成决策树:
$f(x)=\sum_{m=1}^M\hat{c}_mI(x∈R_m)$
分类树的生成
用基尼(Gini)指数来选择最优特征,同时也要确定最优二值切分点.然后递归地执行上述步骤.
$Gini(D)=1-\sum_{i=1}^n(\frac{|C_i|}{|D|})^2$
CART每一次迭代中选择基尼指数最小的特征及其对应的切分点进行分类.
与ID3、C4.5不同的是CART是一个二叉树,只采用二元分割法,每一步将数据按特征A的取值切分成两份,分别进入左右子树.特征A的Gini指数定义为:
$Gini(D|A)=\sum_{i=1}^n\frac{|D_i|}{|D|}Gini(D_i)$
Gini值越小越好

决策树的剪枝

回到GBDT

GBDT实际地核心问题是怎么基于$\{(x_i,r_{im})\}_{i=1}^n$使用CART回归树生成$h_m(x)$
$r_{im}$是GB里提到的伪残差

终于到了XGBoost

XGBoost是GB算法的高效实现,XGBoost中的基学习器除了可以是CART(GBtree)也可以是线性分类器(GBlinear).

XGBoost在目标函数中显式地加上了正则化项,基学习为CART时,正则化项与树的叶子节点的数量T和叶子节点的值有关. $L(\phi)=\sum_il(\hat{y}_i,y_i)+\sum_k\Omega(f_k)$ $其中\Omega(f)=\gamma T+\frac{1}{2} \lambda ||w||^2$
GB中使用Loss Function对f(x)的一阶导数计算出伪残差用于学习生成$f_m$(x),XGBoost不仅使用了一阶导数,还是用了二阶导数,第t次的loss
$L^{(t)}=\sum_{i=1}^nl(y_i,\hat{y}_i^{(t-1)}+f_t(x_i))+\Omega(f_t)$
对上式做二阶泰勒展开:g为一阶导数,h为二阶导数
$L^{(t)}≈\sum_{i=1}^n[l(y_i,\hat{y}^{(t-1)})+g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)]+\Omega(f_t)$ $其中g_i=\partial_{\hat{y}^{t-1}}l(y_i,\hat{y}^{(t-1)}) \ \ \ \ and \ \ h_i=\partial^2_{\hat{y}^{t-1}}l(y_i,\hat{y}^{(t-1)})$
考虑$f_t(x)=w_{q(x)}$,w∈$R^T$,q:$R^d\rightarrow {1,2,..,T}$,其中T表示叶子的数目
对上式再进行展开,这里是为了将目标函数按叶子结点规约分组.一定要始终注意我们的变量是$f_t(x)$.
$L≈\sum_{i=1}^n[g_iw_{q(x_i)}+\frac{1}{2}h_iw^2_{q(x_i)}]+\gamma T+\frac{1}{2}\lambda ||w||^2$
交换求和符号,并将$w_{q(x_i)}$表示成每个叶结点求和的形式
$L≈\sum_{t=1}^T[(\sum_{i∈I_t}g_i)w_t+\frac{1}{2}(\sum_{i∈I_t}h_i)w^2_{t}]]+\frac{1}{2}\lambda\sum_{t=1}^Tw_t^2+\gamma T$
将$\sum_{i∈I_t}g_i$用$G_t$表示,将$\sum_{i∈I_t}h_i$用$H_t$表示
$L≈\sum_{t=1}^T[G_tw_t+\frac{1}{2}(H_t+\lambda)w_t^2]+\gamma T$
将上式想象成一个二次函数,则w的最优取值为$\frac{-b}{2a}$(韦达定理),即
$w^* =\frac{-G_t}{H_t+\lambda}$
最优值为：
$L^* =-\frac{1}{2}\sum_{j=1}^T\frac{G_j^2}{H_j+\lambda}+\gamma T$
其中$\frac{G_j^2}{H_j+\lambda}$测量了该结构的好坏.
$\frac{G_j^2}{H_j+\lambda}$该值越大,$L^* $就越小,说明结构越好.因此我们就可以用$\frac{G_j^2}{H_j+\lambda}$来确定每个结点的分割点.
采用的是树的贪婪学习：
从深度为0开始
对于树的每个左结点,尝试去添加一个分割点.我们希望分割点能使下面的函数越大越好 $Gain=\frac{1}{2}[\frac{G_L^2}{H_L+\lambda}+\frac{G_R^2}{H_R+\lambda}-\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}]-\gamma$ 第一项是左子树的分数,第二项是右子树的分数,第三项是如果我们不分割得到的分数
这里需要找到一个分割点能使增益最大化,一般的方法有精确法和近似法
精确法
遍历所有特征及其候选分裂点,找出使其增益最大的最佳特征与最佳分割点.具体地,将样本按照当前特征上地取值排序,遍历样本同时改变$G_L,G_R,H_L,H_R$的值
近似法
对于每个特征,只考虑分位点,减少计算复杂度.近似法可以有两种做法:1.在训练整棵树前,提前为每个特征选择分位点,其二是在每个结点的分裂时,重新提出每个特征的候选切分点.

与传统GBDT相比,XGBoost有何不同

基函数不同:GBDT只用CART树,而XGBoost除了CART也支持线性函数
目标不同:具体体现在结点分裂策略与正则化.GBDT和XGBoost都是根据目标增益分割结点,GBDT根据均方误差(回归)或基尼指数(分类),XGBoost则进一步引入正则项
正则化不同.XGboost定义正则化,包含了对叶子结点数的约束以及叶子输出权值的L2范数,有利于防止过拟合
利用导数阶数不同,XGBoost用到了一阶和二阶导数
最佳特征选择策略不同:GBDT遍历所有特征,而XGBoost有引入类似于RandomForest的列(特征)子采样,有利于防止过拟合与加速运算。
候选分裂点选取策略不同:GBDT遍历特征所有值,XGBoost有两种做法,其一是遍历,其二是根据二阶导数选择样本分位点作为候补,类似于直方图算法
XGBoost为什么那么快
预排序实现特征粒度的并行
近似法避免遍历分裂所有点,只尝试分位点
XGBoost如何防止过拟合的？
控制模型复杂度:正则化和最大深度
该模型增加随机性:行列采样、学习率shrinkage

XGBoost怎么处理类别不均?

若只关注预测的排序表现,可以用AUC作metric,然后用scale_pos_weight调整正负样本权重
若关注预测概率的准确性,最好改变权重,可以改变max_delta_step(调成正数)来加速收敛.

XGBoost构建树的时候是level-wise还是leaf-wise?
贪心法默认是level-wise，逐层分裂.若选用直方图算法,可以通过grow_policy选择depthwise或者lossguid,前者有限分裂距离根最近的叶结点,实际上近似于level-wise,后者优先分裂loss减少量最多的结点

XGBoost如何实现多分类?
对于K分类,每一轮迭代训练K棵树,用softmax代入各树的输出以表示样本属于各类的概率

XGBoost怎么处理ID类特征?
XGBoost并不直接支持ID类,如果输入ID类是数值型,会直接被当成具有大小关系的数值特征处理

总结

XGBoost算法的步骤和GB基本相同,都是首先初始化一个常数,GB是根据一阶导数$r_i$,XGBoost是根据一阶导数$g_i$和二阶导数$h_i$,迭代生成基学习器,相加更新学习器.(同时还引入了正则化项)
XGBoost还做了许多优化：

最寻找最优分割点时,传统的枚举方法效率太低,XGBoost实现了一种近似的算法.大致思想是根据百分位数列举可能成为分割点的候选者,然后从候选者中根据上面求分割点的公式计算处最佳分割点
XGBoost考虑了训练数据为稀疏值得情况,可以为缺失值或者指定得值指定分支得默认方向,这能大大提升算法得效率
特征排序后以块得形式存储在内存中,在迭代中重复使用;虽然boosting算法迭代必须串行,但是再处理每个特征列时可以做到并行.
XGBoost还考虑了当数据量比较大,内存不够时怎么有效得使用磁盘,主要结合多线程、数据压缩、分片得方法,尽可能的提高算法的效率.

GBDT与深度学习

XGBoost和深度学习的关系,陈天奇在Quora上解答如下:
不同的机器学习模型使用不同类型的任务.深度神经网络通过对时空位置建模,能够很好的捕获图像、语言、文本等高维数据.而基于树模型的XGBoost则能很好地处理表格数据,同时还拥有一些深度神经网络没有的特性(如模型的可解释性、输入数据的不变性、更易于调参).
两类模型都很重要,并广泛用于数据竞赛和工业界.

大杀器XGBoost