【xgboost】理论推导+代码demo_xgboost demo

目录

1.泰勒公式

2.梯度下降法（Gradient Descend Method）

3.牛顿法

4.GBDT原理分析

5.XGBoost原理

目标函数

6.xgb增益计算方法的演进：

 

1.泰勒公式

1. 定义：是一个用函数在某点的信息，描述其附近取值的公式。

2. 基本形式：

   

    

   其中一阶泰勒展开式就是求一阶导，二阶展开式即求二阶导。x0为已知，公式表示f(x)在x0附近的展开。

3. GDBT或是xgb都是一个参数迭代的过程，因此这里表示一个迭代形式的泰勒函数：

   假设

   

   将f(x^t) 在x^(t-1)处进行展开：

   

2.梯度下降法（Gradient Descend Method）

机器学习中需要最小化损失函数L(θ),这个θ就是要求解的模型参数。GDM常用于求解无约束最优化问题，是一种迭代方法。初始话θ为θ^0，不断迭代来更新θ的值，进行损失函数的极小化。

• 迭代公式 θ^t = θ^(t-1)+△θ
  进行一阶泰勒展开：

   

  

   

  要使得L(θ^t) < L(θ^(t-1)),则可取：

   

  

• 其中解释一下为何△θ要取值为上式：首先明确，a的值为正，为了保证△θ恒为负数，则需要乘上L’(θ^t-1)先保证其为整数，再加上负号即可。
• 其实a就是我们常用的学习速率
• a如何选取？
  对于这个问题其实有很多方法可以使用，如果考虑使用full gradient较为笨但是精确的方法是line search，但是其复杂度过高，因此通常我们选取一个很小的值即可例如0.01-0.1之间。

3.牛顿法

牛顿法就是求取二阶泰勒展开：

假设我们要求的参数θ是一维，则记一阶导数为g，二阶导数为h，那么上式可表示为：

此时若求取L(θ^t) 的极小值，则令g△θ+h△θ^2/2极小，求取其一阶导数为0时的△θ即可：

 

如果参数θ是向量形式，那么可以向高维空间推广，此时的h为H（海森矩阵）。

---

以上介绍的梯度下降和牛顿法均为参数空间的优化算法
如何从参数空间推广到函数空间呢？即从Gradient descend到Gradient boosting；从Newton's method到Newton Boosting
下面介绍GBDT和xgb中使用的函数空间的优化算法，其基本原理还是梯度下降和牛顿法。
关系是这样的：
GBDT泛指一切梯度提升树，包括XGB。为了区分二者，可以利用其梯度下降的原理进行区分：

• GBDT在函数空间中利用梯度下降进行优化
• XGB在函数空间利用牛顿法进行优化

---

1. 梯度下降从参数空间到函数空间

其中对于函数空间，仅仅是将参数的拟合换为函数的拟合，每次仍然迭代的是一个负梯度，只是其最终得到的是增量函数的累加而不是增量参数累加。
GBDT里，迭代项ft(x)就是我们的决策树，最终将每棵决策树的预测值（函数）加起来。

2. 牛顿法从参数空间到函数空间

对于牛顿法的函数空间优化，其方法类似于梯度下降的函数空间优化

3. boosting算法小结
无论是梯度下降还是牛顿法，其函数空间上的boosting优化模型都看作是一类加法模型，相加的对象可以是一系列弱分类器或是回归树。

4. 牛顿法小结
牛顿法是梯度下降的进一步优化，梯度下降利用目标函数的一阶偏导信息，以负梯度方向作为搜索方向，只考虑目标函数在迭代点的局部性质；而牛顿法不仅使用目标函数的一阶偏导数，还进一步利用了目标函数的二阶偏导，这样就考虑了梯度变化的趋势，因而能更全面地确定合适的搜索方向以加快收敛。

---

4.GBDT原理分析

GBDT最早由Friedman提出，其核心是拟合前面迭代所留下来的残差，使其达到最小。

• 模型F定义为一个加法模型：

  

其中x为输入样本，h为分类回归树，w是分类回归树的参数，a是每棵树的权重。

• 通过最小化损失函数求解最优模型：

 

• GBDT原是论文的算法伪代码：

• 

算法的输入(xi,yi)分别是样本和lable，T为样本个数，L为损失函数

• GBDT的学习过程是使得前面拟合的残差达到最小，那么首先计算残差，即算法中的2.1步，也称为响应。
• 接着学习第t棵树时就是寻找最新的残差的最小值。可以看到lable yi变成了前t-1棵树的残差值。
  然后寻找合适的步长（通常情况，不使用line search，而是手动给一个很小的值）
  最后将第t棵树与前t-1棵树加起来，更新模型即可。

5.XGBoost原理

• 模型的函数形式

  

xgb同样是一个加性模型，同样是在学习多棵树的结果并将其累加。f(x)就是每一棵树。其中q(x)表示将样本x分到了某个叶子节点上，w是叶子节点的分数，所以wq(x)就表示回归树对样本的预测值。

• 回归树的预测输出是一个实数的分数，因此可以用于回归和分类，以及排序等任务。

目标函数

• 首先回忆一下参数空间的目标函数：

  

   

  实际上就是一个误差函数+正则化项

其中误差函数可以是平方误差或是对数误差等；正则化项可以是L1或L2

• 正则化项

 

wepon大神说道，正则化项的理解可以从贝叶斯先验角度去理解。也就是说，如果引入L2，那么就是假设模型参数服从正态分布（相当于对参数加上了分布约束），这样一来就将参数的取值进行一定的限制，同时可以知道，正态分布取0附近的概率最大，因此又将参数空间可能的范围进一步缩小，模型最终学习出来的参数取值都在0附近。

• 现在来看函数空间的目标函数

   

  

其中正则化项是对每一棵树的复杂度进行惩罚。
相比于GBDT，xgb目标函数就是多了一个正则化项。这样的做法使得模型不易过拟合。
既然是对复杂度做惩罚，那么树的什么特性可以反映复杂度？

• 树的深度、内部节点个数、叶子节点个数，叶节点分数
  xgb中选用了叶子节点个数(T)，叶节点分数(w)来反映树的复杂度，其复杂度定义如下：

  

看完正则化项后再来关心一下目标函数中的误差函数

 

• 首先模型第t次迭代后将ft(x)与前t次的迭代结果进行相加，并代入目标函数，即式2，然后将误差项在yt-1处进行二阶展开，然后去掉常数项得到：

   

  

   

  上面这个形式跟牛顿法的形式几乎一样，由于f在函数空间中是一个树的形式，则将f写为树的结构：

  

  代入目标函数中得到：

  

   

  虽然现在loss函数可以求最小值了，但是公式的两项并不统一，即：

  

  如何将两项进行统一以方便求导呢？因为样本都会落在每一个节点上面，因此可以定义如下：

  

  
  对每一个样本都相应有一个gi和hi。从最终的公式可以看到，由于是按照叶子节点进行累加，所以相当于每一个叶子节点均有一个误差函数，都要进行相应的误差计算。
  根据转换后的损失函数，就可以求极小值了，前提是树结构确定：

  

  相当于每一棵树的最小损失都可以计算了。

既然前提是需要树结构确定，那么如何确定树的结构？即如何确定树节点的分裂方法？

1. 可以暴力枚举全部的树结构然后选择损失最小的结构即可。明显是一个NP问题。不现实！

2. 贪心法：每次尝试分裂一个叶节点，计算前后增益，选择增益最大的保留。

    

   那么增益如何计算？

   

6.xgb增益计算方法的演进：

1. 初始版本：

   

    

   补充：gain的计算

这样的方法相当于去遍历所有可能分割的分割点，然后计算增益，最后选取最大的增益的分列方式去分割，明显负责度太高！！

1. 近似算法：
   对于每一个特征，只考虑分位点，以减少复杂度，分位点的选取粒度有两种：全局global和局部local。全局速度快但是经度降低。
   解释一下：先将某特征的特征值从小到大排序，再选取分位点进行计算增益即可。

   

   
   3. xgb中采用的树节点分裂方法（增益计算）

   

   如何看权重分位点的选取呢？上图中前六个特征值的权重之和为0.6，7-8的权重和为0.6，最后一个为0.6，就这选取权重之和相同的点来进行分位点的选取，然后再计算增益。

纸上得来终觉浅，绝知此事要躬行，于是乎，抄写了一遍加深印象，对手写，能联想到当时的理解，光看还是不行~~，大家也可动手写写划拉划拉。

学习笔记：

代码demo

# coding:utf-8
import xgboost as xgb
 
# 计算分类正确率
from sklearn.metrics import accuracy_score
 
# read in data，数据在xgboost安装的路径下的demo目录,现在我们将其copy到当前代码下的data目录
my_workpath = './data/'
dtrain = xgb.DMatrix(my_workpath + 'agaricus.txt.train')
dtest = xgb.DMatrix(my_workpath + 'agaricus.txt.test')
 
dtrain.num_col()
 
dtrain.num_row()
 
dtest.num_row()
 
# specify parameters via map
param = {'max_depth':2, 'eta':1, 'silent':0, 'objective':'binary:logistic' }
print(param)
 
# 设置boosting迭代计算次数
num_round = 2
 
import time
 
starttime = time.clock()
 
bst = xgb.train(param, dtrain, num_round)  # dtrain是训练数据集
 
endtime = time.clock()
print (endtime - starttime)
 
train_preds = bst.predict(dtrain)    #
print ("train_preds",train_preds)
 
train_predictions = [round(value) for value in train_preds]
print ("train_predictions",train_predictions)
 
y_train = dtrain.get_label()
print ("y_train",y_train)
 
train_accuracy = accuracy_score(y_train, train_predictions)
print ("Train Accuary: %.2f%%" % (train_accuracy * 100.0))
 
# make prediction
preds = bst.predict(dtest)
predictions = [round(value) for value in preds]
 
y_test = dtest.get_label()
 
test_accuracy = accuracy_score(y_test, predictions)
print("Test Accuracy: %.2f%%" % (test_accuracy * 100.0))
 
import graphviz
 
xgb.plot_tree(bst, num_trees=0, rankdir='LR')
pyplot.show()
 
# xgb.plot_tree(bst,num_trees=1, rankdir= 'LR' )
# pyplot.show()
# xgb.to_graphviz(bst,num_trees=0)
 

 

参考链接：
1.公式推导：https://www.jianshu.com/p/6075922a8bc3

2.原理和公式介绍：https://cloud.tencent.com/developer/article/1415137

3.雪伦大神的blog：https://blog.csdn.net/a819825294/article/details/51206410

4.DART的介绍：https://blog.csdn.net/Yongchun_Zhu/article/details/78745529

5.xgboost官方文档：https://xgboost.readthedocs.io/en/latest/tutorials/dart.html

6.xgb中的直方图以及加权分位数：https://blog.csdn.net/m0_37870649/article/details/104561431