GBDT和XGBOOST算法原理

GBDT

以多分类问题为例介绍GBDT的算法，针对多分类问题，每次迭代都需要更新K个函数（K为需分类的类别个数），每个函数记为F_{mk}(x)，其中m为迭代次数，k为分类类别。

针对一个训练样本(x_i,y_i)，经过m次迭代后的损失函数记为L(y_i, F_{m1}(x_i), ..., F_{mK}(x_i))=-\sum_{k=1}^{K}I({y_i}=k)\ln[p_{mk}(x_i)]=-\sum_{k=1}^{K}I({y_i}=k)\ln\left[\frac{e^{F_{mk}(x_i)}}{\sum_{l=1}^{K}e^{F_{ml}(x_i)}}\right]其中p_{mk}(x_i)表示经过m次迭代后x_i被分到类别k的概率，此时损失函数的梯度可以表示为g_{mki}=-\frac{\partial{L(y_i, F_{m1}(x_i), ..., F_{mK}(x_i))}}{\partial{F_{mk}(x_i)}}=I({y_i}=k)-p_{mk}(x_i)=I({y_i}=k)-\frac{e^{F_{mk}(x_i)}}{\sum_{l=1}^{K}e^{F_{ml}(x_i)}}

GBDT算法的流程如下所示：

• for k=1 to K: 初始化F_{0k}(x)=0
• for m=1 to M:
  • for k=1 to K:
    • 针对每个样本(x_i, y_i)计算梯度g_{m-1,ki}
    • 使用训练数据集(x_i, \space g_{m-1,ki})_{i=1\cdots N}构建CART决策树（回归问题）R_{mkj, \space j=1\cdots J_{mk}} (j表示叶子节点 )，具体过程可参考文章CART决策树和随机森林
    • 构建CART决策树（回归问题）之后，相对于直接使用每个叶子节点中的g_{m-1,ki}的均值作为叶子节点的权重，GBDT使用公式(1)计算叶子节点的权重w_{mkj, \space j=1\cdots J_{mk}}
    • 更新函数F_{mk}(x)=F_{m-1,k}(x)+\eta*\sum_{j=1}^{J_{mk}}w_{mkj}I({x}\in{R_{mkj}}), \eta表示学习率

上述计算过程可以直观地理解为使用一个决策树近似地估计损失函数的梯度，然后利用梯度下降算法优化损失函数。权重w_{mkj}的计算公式如下：\small \tag{1}\underset{\underset{k=1\cdots K, \space J=1\cdots J_{mk}}{\normalsize w_{kj}}}{\arg\min}\sum_{i=1}^N L\left(y_{i}, F_{m-1, 1}\left(x_{i}\right)+\sum_{j=1}^{J_{m1}} w_{1j} I(x_{i} \in R_{m1j}), \cdots, F_{m-1, K}\left(x_{i}\right)+\sum_{j=1}^{J_{mK}} w_{Kj} I(x_{i} \in R_{mKj})\right)利用Newton-Raphson公式求解（在这个问题中将初始值设为0，只进行一步迭代，并且Hessian矩阵H只取对角线上的值），记L_i=L\left(y_{i}, F_{m-1, 1}\left(x_{i}\right)+\sum_{j=1}^{J_{m1}} w_{1j} I(x_{i} \in R_{m1j}), \cdots, F_{m-1, K}\left(x_{i}\right)+\sum_{j=1}^{J_{mK}} w_{Kj} I(x_{i} \in R_{mKj})\right)有\begin{aligned}w_{mkj} &=0-\frac{\sum_{i=1}^N\partial{L_i}/\partial{w_{kj}}}{\sum_{i=1}^N\partial^2{L_i}/\partial{w_{kj}^2}}\bigg\vert_{\large w_{kj}\normalsize =0,\space k=1\cdots K,\space j=1\cdots J_{mk}} \\ &=\frac{\sum_{i=1}^{N}I({x_i}\in{R_{mkj}})[I({y_i}=k)-p_{m-1,k}(x_i)]}{\sum_{i=1}^{N}I^2({x_i}\in{R_{mkj}})p_{m-1,k}(x_i)[1-p_{m-1,k}(x_i)]}=\frac{\sum_{x_i\in{R_{mkj}}}g_{m-1,ki}}{\sum_{x_i\in{R_{mkj}}}\lvert{g_{m-1,ki}}\rvert(1-\lvert{g_{m-1,ki}}\rvert)}\end{aligned}文献[1]在上述w_{mkj}的前面乘以了系数\frac{K-1}{K}，可能原因是在分类器的建立过程中，可以把任意一个F_k(x)始终设为0，只计算剩余的F_k(x)，因此w_{mkj} \gets \frac{1}{K}*0+\frac{K-1}{K}w_{mkj}

参考文献

[1] Friedman, J. H., 2001, Greedy function approximation: A gradient boosting machine. Ann. Statist., 29(5), 1189-1232.

---

XGBOOST

仍以多分类问题介绍XGBOOST算法，相对于GBDT的一阶导数，XGBOOST还引入了二阶导数，并且加入了正则项。区别于上文中g_{mki}的定义，记g_{mki}=\frac{\partial{L(y_i, F_{m1}(x_i), ..., F_{mK}(x_i))}}{\partial{F_{mk}(x_i)}}=p_{mk}(x_i)-I({y_i}=k)=\frac{e^{F_{mk}(x_i)}}{\sum_{l=1}^{K}e^{F_{ml}(x_i)}}-I({y_i}=k)以及h_{mki}=\frac{\partial^2{L(y_i, F_{m1}(x_i), ..., F_{mK}(x_i))}}{\partial{F_{mk}(x_i)}^2}=p_{mk}(x_i)[1-p_{mk}(x_i)]区别于GBDT中决策树的构建过程，XGBOOST将决策树结构R_{mkj,\space j=1\cdots J_{mk}}以及叶子节点权重w_{mkj}的求解转化为问题\underset{\underset{k=1\cdots K,\space j=1\cdots J_k}{R_{kj}, \normalsize w_{kj}}}{\arg\min}\sum_{i=1}^N L\left(y_{i}, F_{m-1, 1}\left(x_{i}\right)+\sum_{j=1}^{J_{1}} w_{1j} I(x_{i} \in R_{1j}), \cdots, F_{m-1, K}\left(x_{i}\right)+\sum_{j=1}^{J_{K}} w_{Kj} I(x_{i} \in R_{Kj})\right)利用二阶泰勒展开，上述公式可转化为\tag{2} \underset{\underset{k=1\cdots K, \space J=1\cdots J_{k}}{R_{kj}, \normalsize w_{kj}}}{\arg\min}\sum_{i=1}^N \left[L\left(y_{i}, F_{m-1, 1}(x_i),\cdots,F_{m-1, K}(x_i)\right)+\sum_{k=1}^K\left(g_{m-1,ki}f_{k}(x_i)+\frac{1}{2}h_{m-1,ki}f^2_{k}(x_i)\right)\right]其中函数f_{k}(x)=\sum_{j=1}^{J_{k}}w_{kj}I({x}\in{R_{kj}})，容易看出公式(2)等价于\tag{3} \underset{\underset{k=1\cdots K, \space J=1\cdots J_{k}}{R_{kj}, \normalsize w_{kj}}}{\arg\min}\sum_{i=1}^N\sum_{k=1}^K \left(g_{m-1,ki}f_{k}(x_i)+\frac{1}{2}h_{m-1,ki}f^2_{k}(x_i)\right)XGBOOST在公式(3)的基础上还加入了一个正则项用来惩罚过多的叶子节点以及过大的叶子节点权重：\Omega(f_{k})=\gamma J_{k}+\frac \lambda {2}\sum_{j=1}^{J_{k}}w_{kj}^2此时公式(3)变为\tag{4} \underset{\underset{k=1\cdots K, \space J=1\cdots J_{k}}{R_{kj}, \normalsize w_{kj}}}{\arg\min}\sum_{k=1}^K\left[\sum_{i=1}^N\left(g_{m-1,ki}f_{k}(x_i)+\frac{1}{2}h_{m-1,ki}f^2_{k}(x_i)\right)+\Omega(f_{k})\right]经过简单地变换容易看出公式(4)可以写成\tag{5} \underset{\underset{k=1\cdots K, \space J=1\cdots J_{k}}{R_{kj}, \normalsize w_{kj}}}{\arg\min} \sum_{k=1}^K\left[\gamma J_k+\sum_{j=1}^{J_k}\left(G_{kj}w_{kj}+\frac{1}{2}(\lambda+H_{kj})w_{kj}^2\right)\right]其中G_{kj}=\sum_{x_i \in R_{kj}}g_{m-1,ki}以及H_{kj}=\sum_{x_i \in R_{kj}}h_{m-1,ki}

针对公式(5)的求解，首先假设已知了决策树的结构，即R_{mkj,\space j=1\cdots J_{mk}}，则权重w_{mkj,\space j=1\cdots J_{mk}}的求解就转换为了求一个二次函数的最小值问题：\underset{\underset{j=1\cdots J_{mk}}{\normalsize w_{kj}}}{\arg\min}\left[\gamma J_{mk}+\sum_{j=1}^{J_{mk}}\left(G_{kj}w_{kj}+\frac{1}{2}(\lambda+H_{kj})w_{kj}^2\right)\right]容易得到当\large w_{mkj}=-\frac{\large G_{kj}}{\large H_{kj}+\lambda}时上式取得最小值，最小值为\tag{6} \large \gamma J_{mk}-\frac{\large 1}{\large 2}\sum_{j=1}^{J_{mk}}\frac{\large G_{kj}^2}{\large H_{kj}+\lambda}

接下来确定决策树的结构：从一个节点开始不断进行分裂，假设待分裂的节点为I，分裂后的两个节点分别为I_L和I_R，容易计算出分裂前的节点I上的-\frac{\normalsize 1}{\normalsize 2}\frac{\normalsize G^2_I}{\normalsize H_I+\lambda}，分裂目标是使得分裂后的-\frac{\normalsize 1}{\normalsize 2}\left(\frac{\normalsize G^2_{I_L}}{\normalsize H_{I_L}+\lambda}+\frac{\normalsize G^2_{I_R}}{\normalsize H_{I_R}+\lambda}\right)达到最小，因此分裂增益可表示为：-\frac{\normalsize 1}{\normalsize 2}\frac{\normalsize (\sum_{x_i \in I}g_{m-1,ki})^2}{\normalsize \lambda+\sum_{x_i \in I}h_{m-1,ki}}+\frac{\normalsize 1}{\normalsize 2}\left[\frac{\normalsize (\sum_{x_i \in I_L}g_{m-1,ki})^2}{\normalsize \lambda+\sum_{x_i \in I_L}h_{m-1,ki}}+\frac{\normalsize (\sum_{x_i \in I_R}g_{m-1,ki})^2}{\normalsize \lambda+\sum_{x_i \in I_R}h_{m-1,ki}}\right]分裂规则是挑选使分裂增益最大的特征和分裂点进行分裂，直到达到预先设定的某个停止条件为止。需要注意的是因为分裂后的叶子节点数量多了1个，所以最大分裂增益至少应为\gamma才能保证分裂后计算的公式(6)的值是减小的，否则应停止对该节点进行分裂

XGBOOST的计算流程如下：

• for k=1 to K: 初始化F_{0k}(x)=0
• for m=1 to M:
  • for k=1 to K:
    • 针对每个样本(x_i, y_i)计算g_{m-1,ki}以及h_{m-1,ki}
    • 按照前述方法得到函数f_{mk}(x)=\sum_{j=1}^{J_{mk}}w_{mkj}I({x}\in{R_{mkj}})
    • 更新函数F_{mk}(x)=F_{m-1,k}(x)+\eta*f_{mk}(x), \eta表示学习率

XGBOOST的Python包中的重要参数：

• eta(alias:learning_rate): learning rate or shrinkage，同上文的\eta，常用值0.01-0.2
• gamma(alias: min_split_loss): min loss reduction to create new tree split，同上文的\gamma
• lambda(alias: reg_lambda): L2 regularization on leaf weights，同上文的\lambda
• alpha(alias: reg_alpha): L1 regularization on leaf weights
• max_depth: max depth per tree，常用值3-10
• min_child_weight: minimum sum of instance weight(hessian) of all observations required in a child，即在分裂后的一个子节点中H_{\text{child}}=\sum_{x_i \in \text{child}}h_{m-1,ki}需达到的最小值，否则停止分裂
• subsample: percentage of samples used per tree，常用值0.5-1
• colsample_bytree: percentage of features used per tree，常用值0.5-1
• 针对样本类别不均衡问题，若是二分类问题，可以设置参数scale_pos_weight，通常设为负样本个数/正样本个数；若是多分类问题，可以通过xgboost.DMatrix(...,weight,...)或者Scikit-Learn API中的fit(...,sample_weight,...)进行设置
• 特征重要性可以通过该特征被选中作为节点分裂特征的次数来度量
• 算法应用示例可参见文章XGBOOST应用及调参示例