xgboost:算法数学原理

xgboost算法数学原理

1、求预测值
$${\hat{y}}_i=\varphi \left({\mathbf{x}}_i\right)=\sum _{k=1}^K{f}_k\left({\mathbf{x}}_i\right),f_k\in \mathcal{F},\text{\hspace{1em}(1)}$$
$\mathcal{F}=\left\{f(\mathbf{x})=w_{q(\mathbf{x})}\right\}\left(q:{\mathbb{R}}^m\to T,w\in {\mathbb{R}}^T\right)$：递归树的的空间；

$q$：每棵树的结构，映射一个样本到一个叶子节点index；

$T:$叶子的数目；$f_k$对于一个独立的树结构$q$和叶子权重$w$。

$w_i$：在$i-th$叶子节点的分数；（与决策树不同，递归树在每个叶子节点上包含一个连续分数）。

示例图：（注：图中的人指的是一个个样本）

结合上面的公式理解就是对于样本$i$的预测值等于$K$棵递归树样本落在的叶子节点对应的分数的和；

2、计算带正则项的损失
$$\begin{array}{rl}& \mathcal{L}(\varphi )=\sum _{i}l\left({\hat{y}}_i,y_i\right)+\sum _k\Omega \left(f_k\right)\\ & \text{ where }\Omega (f)=\gamma T+\frac{1}{2}\lambda \Vert w{\Vert }^2\end{array}\text{\hspace{1em}(2)}$$
$l$：衡量预测值$\widehat{y_i}$和目标值$y_i$差别的可微的凸函数；

$\Omega$：模型复杂度的惩罚项；用于平滑最终的学习权重避免过拟合。正则化的目标函数倾向于选择一个更简单、可预测的函数（递归树模型）；传统的梯度提升树没有用正则化项，RGF用到。

3、梯度树集成（Gradient Tree Boosting）

从对全部递归树的损失，利用贪心和近似，推导到一棵树的损失

为什么用(3)式作为目标函数而不是(2)式？

将(1)和(2)合并：
$$\begin{array}{rl}& \mathcal{L}(\varphi )=\sum _{i}l\left(\sum _{k=1}^K{f}_k\left({\mathbf{x}}_i\right),y_i\right)+\sum _k\Omega \left(f_k\right)\\ & \text{ where }\Omega (f)=\gamma T+\frac{1}{2}\lambda \Vert w{\Vert }^2\end{array}\text{\hspace{1em}(2)}$$

可以看到(2)式不能进行优化，不能优化的原因是$K$棵树的话，就有$K$个$f(x)$，在优化理论中，相当于多变量优化，是一个极其难以优化的问题。所以使用(3)式这种贪婪的方式，每一次只优化一棵树。
$${\mathcal{L}}^{(t)}=\sum _{i=1}^{n}l\left(y_i,{\hat{y}}_i^{(t-1)}+f_t\left({\mathbf{x}}_i\right)\right)+\Omega \left(f_t\right)\text{\hspace{1em}(3)}$$
${\widehat{y_i}}^t$：第$i$个样本实例在第$t$次迭代的预测值；

注：二阶泰勒公式：
$$f(x+\Delta x)\approx f(x)+f^{\prime }(x)\cdot \Delta x+\frac{1}{2}{f}^{\prime \prime }(x)\cdot \Delta x^2$$

但是(3)式还是不容易优化，需要进行二阶近似：
$${\mathcal{L}}^{(t)}\simeq \sum _{i=1}^n\left[l\left(y_i,{\hat{y}}^{(t-1)}\right)+g_i{f}_t\left({\mathbf{x}}_i\right)+\frac{1}{2}{h}_i{f}_t^2\left({\mathbf{x}}_i\right)\right]+\Omega \left(f_t\right)\text{\hspace{1em}(4)}$$
$g_i$：$g_i={\partial }_{{\hat{y}}^{(t-1)}}l\left(y_i,{\hat{y}}^{(t-1)}\right)$

$h_i$：$h_i={\partial }_{{\hat{y}}^{(t-1)}}^{2}l\left(y_i,{\hat{y}}^{(t-1)}\right)$

进一步去掉常数项，得到损失函数：（常数项不影响损失函数，因为常数项不影响最小化损失函数问题，只会影响损失函数的结果的量级）
$${\tilde{\mathcal{L}}}^{(t)}=\sum _{i=1}^n\left[g_i{f}_t\left({\mathbf{x}}_i\right)+\frac{1}{2}{h}_i{f}_t^2\left({\mathbf{x}}_i\right)\right]+\Omega \left(f_t\right)\text{\hspace{1em}(5)}$$
按照叶子节点进行样本的集合划分：
$$\begin{array}{rl}{\tilde{\mathcal{L}}}^{(t)}& =\sum _{i=1}^n\left[g_i{f}_t\left({\mathbf{x}}_i\right)+\frac{1}{2}{h}_i{f}_t^2\left({\mathbf{x}}_i\right)\right]+\gamma T+\frac{1}{2}\lambda \sum _{j=1}^T{w}_j^2\\ & =\sum _{j=1}^T\left[\left(\sum _{i\in I_j}{g}_i\right)w_j+\frac{1}{2}\left(\sum _{i\in I_j}{h}_i+\lambda \right)w_j^2\right]+\gamma T\end{array}\text{\hspace{1em}(6)}$$
Ij={i∣q(xi)=j}I_j=\{i|q(\mathbf{x}_i)=j\}Ij​={i∣q(xi​)=j}：叶子节点$j$的样本集合；

然后对$w$求导数，令其==0，得到：
$$w_j^{\ast }=-\frac{{\sum }_{i\in I_j}{g}_i}{{\sum }_{i\in I_j}{h}_i+\lambda },\text{\hspace{1em}(7)}$$
计算对应的优化值：
$${\tilde{\mathcal{L}}}^{(t)}(q)=-\frac{1}{2}\sum _{j=1}^T\frac{{\left({\sum }_{i\in I_j}{g}_i\right)}^2}{{\sum }_{i\in I_j}{h}_i+\lambda }+\gamma T.\text{\hspace{1em}(8)}$$
式(8)可以作为像决策树里面的纯度、信息熵一样的划分函数，得到树的划分分数。如图

通常应该计算单个叶子节点和添加左右节点的贪婪算法来评估是不是增加分支，而不能直接计算(8)，如下：
$${\mathcal{L}}_{split}=\frac{1}{2}\left[\frac{({\sum }_{i\in I_L}{g}_i{)}^2}{{\sum }_{i\in I_L}{h}_i+\lambda }+\frac{({\sum }_{i\in I_R}{g}_i{)}^2}{{\sum }_{i\in I_R}{h}_i+\lambda }-\frac{({\sum }_{i\in I}{g}_i{)}^2}{{\sum }_{i\in I}{h}_i+\lambda }\right]-\gamma \text{\hspace{1em}(9)}$$
R}h_i+\lambda}-\dfrac{(\sum_{i\in I}g_i)^2}{\sum_{i\in I}h_i+\lambda}\right]-\gamma\tag{9}
$$