XgBoost算法

  XgBoost算法(eXtreme Gradient Boosting)属于Boosting系列算法，更多的是基于GBDT算法的一个进阶算法。本文假设XgBoost算法使用的弱学习器为决策树。

XgBoost算法学习目标

1. XgBoost算法目标函数
2. XgBoost算法正则化项
3. XgBoost算法最小化目标函数
4. XgBoost算法优缺点

XgBoost算法详解

XgBoost算法参数

  假设我们获取了XgBoost的模型和它的目标函数，现在我们的任务就是最小化目标函数$J(\theta)$找到最佳的$\theta$，但是这个参数是什么呢？XgBoost由一堆CART树组成，因此这个参数很明显存在于每颗CART树中。但是CART树的参数又是什么呢？CART树如果被确定之后，子节点是可以丢掉的，剩下的只有每一个叶子节点以及每一个叶子节点上的分数，这就是CART树的参数即XgBoost的参数，还是不清楚继续往下看。

XgBoost算法目标函数

  通过真实值和预测值以及xboost模型我们能得到一个目标函数，该目标函数假设存在一个$L$代价函数和一个正则项$\sum_{i=1}^t\Omega(fk)$(类似于线性回归的L1、L2正则化，之后会详细解释，此处是t棵树的正则化项加和，现在假设我们有t棵树，n个训练样本，既得一个目标函数
$$
J(\theta)=\sum{i=1}^nL(y_i^t,\hat{y}i^{(t)}))+\sum{i=1}^t\Omega(fi)
$$
  如果我们假设$C$是t-1棵树的正则化项加和，并且代入XgBoost的模型，得
$$
J(\theta)=\sum{i=1}^nL(y_i^t,\hat{y}_i^{(t-1)}+f_t(x_i))+\Omega(f_t)+C
$$
泰勒展开式公式为：
$$
f(x+\Delta{x})\approx{f(x)}+f'(x)\Delta{x}+{\frac{1}{2}}f”(x)\Delta{x^2}
$$
假设
$$
\begin{align}
& f(x)=\hat{y}_i^{(t-1)} \
& \Delta=f_t(xi) \
& gi=\partial{\hat{y}_i^{(t-1)}}L(y_i^t,\hat{y}i^{(t-1)}) \
& hi=\partial{\hat{y}_i^{(t-1)}}^2L(y_i^t,\hat{y}i^{(t-1)})
\end{align}
$$
  在这些假设的基础上，我们假设存在一个代价函数$L$，我们可以把$J(\theta)$泰勒二阶展开：
$$
\begin{align}
J(\theta) & = \sum{i=1}^nL(y_i^t,\hat{y}i^{(t)}))+\sum{i=1}^t\Omega(fi) \
& = \sum{i=1}^nL(y_i^t,\hat{y}_i^{(t-1)}+f_t(x_i))+\Omega(ft)+C \
& = \sum{i=1}^n[L(y_i^t,\hat{y}_i^{(t-1)})+g_if_t(x_i)+{\frac{1}{2}}h_if_t^2(x_i)]+\Omega(f_t)+C
\end{align}
$$
其中$y_i^t$和$\hat{y}_i^{(t-1)}$已知，即$L(y_i^t,\hat{y}i^{(t-1)})$是一个常数项(因为我们假设了这个代价函数$L$是已知的一个代价函数，可以是MSE，可以是MSA，可以是任何一个已知的代价函数)；$C$是前t-1棵树的正则化项加和，也是一个常数，这两个常数项对目标函数求最小值无意义，因此我们可以去掉，既得
$$
J(\theta)=\sum{i=1}^n[g_if_t(x_i)+{\frac{1}{2}}h_if_t^2(x_i)]+\Omega(ft)
$$
  现在如果我们假设损失函数$L$使用的是MSE，那么上述式子会变成
$$
\begin{align}
J(\theta) & = \sum{i=1}^n(y_i^t-(\hat{y}_i^{(t-1)}+f_t(x_i)))^2+\Omega(ft)+C \
& = \sum{i=1}^n((y_i^t-\hat{y}_i^{(t-1)})-f_t(x_i))^2+\Omega(ft)+C \
& =\sum{i=1}^n[(y_i^t-\hat{y}_i^{(t-1)})^2-2(y_i^t-\hat{y}_i^{(t-1)})f_t(x_i)+f_t(x_i)^2]+\Omega(ft)+C
\end{align}
$$
去掉常数项可以得到
$$
J(\theta)=\sum{i=1}^n[-2(y_i^t-\hat{y}_i^{(t-1)})f_t(x_i)+f_t(x_i)^2]+\Omega(f_t)
$$
  如果你代入验证很明显可以发现我们使用泰勒展开式得到的式子是没有问题的

  其实走到这里我们的XgBoost已经算是结束了，是不是忘了我们在做什么，哈哈！我们在做的是通过前t-1棵的预测值加和我们是否能算出第t棵树的最优预测值。

XgBoost算法正则化项

  如线性回归的正则化项一样，你可以使用L1正则化，你也可以使用L2正则化。这里我就讲讲我对XgBoost使用的正则化项。

  正则化前我们先对CART树做处理：假设一棵树有T个叶子节点，这T个叶子节点组成了一个T维向量$w$，而$q(x)$是一个映射，用来将样本映射成1到T的某个值，即$q(x)$表示了CART树的结构，$w_q(x)$表示了这棵树对样本x的预测值
$$
ft(x)=w{q(x)},w\in{R^T},a:R^d\rightarrow{1,2,\cdots,T}
$$
  由此我们可以假设XgBoost的正则化项
$$
\Omega(ft)=\gamma{T}+{\frac{1}{2}}\lambda\sum{j=1}^T{w_j^2}
$$
其中$\gamma$和$\lambda$是我们自定义的一个数(类似线性回归的学习率)，如果$\gamma$越大，表示希望获得结构简单的树，因为$\gamma$越大对叶子节点多的树惩罚更大；$\lambda$越大也是如此。

XgBoost算法最小化目标函数

  这个时候我们有了泰勒二阶展开的目标函数，有了自定义的正则化项，我们可以把自定义的正则项代入目标函数中
$$
J(\theta)=\sum_{i=1}^n[g_if_t(x_i)+{\frac{1}{2}}h_if_t^2(xi)]+\gamma{T}+{\frac{1}{2}}\lambda\sum{j=1}^T{w_j^2}
$$
代入$ft(x)=w{q(x)}$，得
$$
J(\theta)=\sum_{i=1}^n[giw{q(x_i)}+{\frac{1}{2}}hi{w{q(xi)}^2}]+\gamma{T}+{\frac{1}{2}}\lambda\sum{j=1}^T{w_j^2}
$$
  这个时候我们需要考虑，如果一个叶子节点上难道只会对应一个样本吗？很明显如果样本很多，一个叶子可能会对应多个样本。因此我们用$Ij$表示一个叶子节点上的所有样本，即$\sum{i\in{Ij}}$对应一个叶子节点上所有样本的对应值的加和，我们需要计算的就是T个叶子节点上的样本预测值的加和，这也是为什么用$\sum{j=1}^T$开头的原因
$$
\begin{align}
J(\theta) & =\sum{j=1}^T{[(\sum{i\in{I_j}}g_i)wj+{\frac{1}{2}}(\sum{i\in{I_j}}hi)wj^2]+\gamma{T}+{\frac{1}{2}}\lambda\sum{j=1}^T{wj^2}} \
& = \sum{j=1}^T{[(\sum_{i\in{I_j}}g_i)wj+{\frac{1}{2}}(\sum{i\in{I_j}}hi+\lambda)w_j^2]+\gamma{T}}
\end{align}
$$
假设$Gj=\sum{i\in{I_j}}g_i,Hj=\sum{i\in{I_j}}hi$
$$
J(\theta)=\sum{j=1}^T[G_jw_j+{\frac{1}{2}}(H_j+\lambda)w_j^2]+\gamma{T}
$$
  通过上式我们可以对目标函数对$w$求偏导找到最优$w^{}$为
$$
{\frac{\partial{J(f_t)}}{\partial{w_J}}}=G_j+(H_j+\lambda)w_j==0\Rightarrow{w_j^}=-{\frac{G_j}{Hj+\lambda}}
$$
回代最优$w^{}$得
$$
J(\theta)^=-{\frac{1}{2}}\sum{j=1}^T{\frac{G_j^2}{H_j+\lambda}}+\gamma{T}
$$
  因为$J(\theta)^$的推导过程中只和$G_j$和$H_j$和有关，而它们又只和树的结构$q(x)$有关，这表示$J(\theta)^$代表了这颗树的结构有多好，值越小，代表这样的结构越好。

  其实聪明的同学已经发现了我们的$\theta$这个参数完全可以看成$f_t$，它表示的是第t颗树的结构，也就可以看成我们的$\theta$呀？不是吗？嘻嘻，你仔细思考下。当然$f_t$也是我们自己定义的。

XgBoost算法举例

  现在我们假设我们有一家五口的数据，见下表

  儿子+妈妈
$$
G_L=g_1+g_2
$$
  爸爸+奶奶+爷爷
$$
G_R=g_3+g_4+g5
$$
$$
J(\theta)^*=-{\frac{1}{2}}\sum{j=1}^T{\frac{G_j^2}{H_j+\lambda}}+\gamma{T}
$$
  如果我们不对这5个样本分开，把数据代入$J(\theta)$，他们的目标值是
$$
{\frac{1}{2}}{\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}}
$$
  如果我们把他们五个人按照年龄排列并从空格列分开，即该决策树会有两个叶子，一个叶子会有儿子+妈妈的分数；另一个叶子会有爸爸+奶奶+爷爷的分数

把数据代入$J(\theta)$目标值是
$$
{\frac{1}{2}}[{\frac{G_L^2}{H_L+\lambda}}+{\frac{G_R^2}{H_R+\lambda}}]
$$
  由此可以计算Gain值
$$
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
$$
  总结：该Gain值是单节点的目标值减去切分后的所有节点的目标值，Gain值如果是正的，并且Gain值越大，就越值得切分，然后不断重复上述过程；如果Gain值是负的，表明切分后目标值变大了。而$\gamma$在这里控制目标值的下降幅度。Gain值类似于信息增益，并且相比较传统的GBDT，XgBoost使用了二阶泰勒展开，可以更快的在训练集上收敛，虽然XgBoost需要计算每个样本的g和h值，但是XgBoost使用了并行/多核运算，这都不是问题。

XgBoost算法优缺点

优点

1. 可以使用正则化项等策略防止过拟合
2. 目标函数优化利用了损失函数关于待求函数的二阶导数，相比较GBDT，迭代速度更快
3. 支持并行化，训练速度快
4. 添加了对稀疏数据的处理
5. 支持设置样本权重，该权重体现在一阶导数g和二阶导数h，通过调整权重可以去更加关注一些样本

缺点

1. 数据量大时，由于选择划分点需要对特征做预排序，计算开销过大

小结

  XgBoost算法是GBDT算法的一个提升，他们两者之间的主要区别在于目标函数形式不同。并且XgBoost使用了二阶泰勒展开，使得XgBoost算法收敛速度更快。