xgboost推导

目标函数

$$\begin{aligned} L^{(t)} & = \sum_{i=1}^n l(y_i, \bar{y}_i^t ) + \Omega(f_t) \\ & = \sum_{i=1}^n l(y_i, \bar{y}_i^{t-1} + f_t(x_i)) + \gamma T + \frac{1}{2}\lambda\sum_{j=1}^Tw_j^2 \end{aligned}$$

其中L(t)表示第t轮迭代的目标函数，由损失函数和正则项两部分组成：

• $l(y_i, \bar{y}_i^{t})$ 表示损失函数，当损失函数是平方误差时，即同最小二乘cart回归树原理。其中n表示样本个数，$y_i$表示样本i的真实值，$\bar{y}_{i}^{t}$表示第t轮样本i的预测值，$\bar{y}_{i}^{t-1}$表示第t-1轮样本i的预测值，$f_t(x_i)$表示第t轮的决策树对样本i的预测值。故有：$\bar{y}_i^{t}=\bar{y}_i^{t-1}+f_t(x_i)$ 。即第t轮预测值=第t-1轮预测值+第t轮决策树预测值
  • $\Omega(f_t)$表示正则项，n表示样本个数，T表示叶子节点个数。$\gamma和\lambda$都是常数参数，控制正则项。$w_j$表示第t轮的决策树第j个叶子节点预测值.

目标函数二阶泰勒展开

二阶泰勒展开通式

$$f(x+\Delta x) \simeq f(x)+f'(x)\Delta x+\frac{1}{2}f''(x)\Delta x^2$$

按照上述通式将$l(y_i, \bar{y}_i^{t-1} + f_t(x_i))$二阶展开，通式中的x对比$\bar{y}_i^{t-1}$，通式中的$\Delta x$对比$f_t(x_i))$，则有：

$$l(y_i, \bar{y}_i^{t-1} + f_t(x_i))=l(y_i, \bar{y}_i^{t-1})+l'(y_i, \bar{y}_i^{t-1})f_t({x_i})+\frac{1}{2}l''(y_i, \bar{y}_i^{t-1})f_t^2(x_i)$$

其中，$l(y_i, \bar{y}_i^{t-1})$为样本i第t-1轮的损失，它对于第t轮的样本i来说无论样本i落在哪个叶子节点都一样，可视作常数项丢掉，丢掉常数项有：

$$l(y_i, \bar{y}_i^{t-1} + f_t(x_i))=l'(y_i, \bar{y}_i^{t-1})f_t({x_i})+\frac{1}{2}l''(y_i, \bar{y}_i^{t-1})f_t^2(x_i)$$

$l’(y_i, \bar{y}_i^{t-1})$是对$\bar{y}_i^{t-1}$求一阶导，$l’’(y_i, \bar{y}_i^{t-1})$是对$\bar{y}_i^{t-1}$求二阶导。令：

$$g_i=l'(y_i, \bar{y}_i^{t-1}),h_i=l''(y_i, \bar{y}_i^{t-1})$$

则有：

$$l(y_i, \bar{y}_i^{t-1} + f_t(x_i))=g_if_t({x_i})+\frac{1}{2}h_if_t^2(x_i)$$

带入(1)式有：

$$\begin{aligned} L^{(t)} &= \sum_{i=1}^n l(y_i, \bar{y}_i^{t-1} + f_t(x_i)) + \gamma T + \frac{1}{2}\lambda\sum_{j=1}^Tw_j^2 \\ &=\sum_{i=1}^n [g_if_t({x_i})+\frac{1}{2}h_if_t^2(x_i)] + \gamma T + \frac{1}{2}\lambda\sum_{j=1}^Tw_j^2 \end{aligned}$$

先做下转换，$f_t(x_i)=w_j , 其中 i\in I_j$，表示样本i落在$w_j$这个叶子节点。故有：

$$\begin{aligned} L^{(t)} &=\sum_{j=1}^T [ (\sum_{i\in I_j}g_i)w_j+\frac{1}{2}(\sum_{i\in I_j}h_i)w_j^2] + \gamma T + \frac{1}{2}\lambda\sum_{j=1}^Tw_j^2 \\ &=\sum_{j=1}^T [ (\sum_{i\in I_j}g_i)w_j+\frac{1}{2}(\sum_{i\in I_j}h_i+\lambda)w_j^2] + \gamma T \end{aligned}$$

这是一个初中就学过的一元二次方程了，直接用顶点公式可以得出：

$$w_j = - \frac{\sum_{i \in I_j} g_i}{\sum_{i \in I_j} h_i + \lambda}=- \frac{G_i}{H_i+\lambda}$$ $$min(L^{(t)}) = - \frac{1}{2} \sum_{j=1}^T \frac{(\sum_{i \in I_j} g_i)^2}{\sum_{i \in I_j} h_i + \lambda} + \gamma T = -\frac{1}{2} \sum_{j=1}^T \frac{G_i^2}{H_i+\lambda} +\gamma T$$

举个例子

当损失函数取平方误差时，$l(y_i, \bar{y}_i^{t})= \frac{1}{2}( y_i - \bar{y}_i^{t} )^2$，则：

$$\begin{aligned} & g_i =l'(y_i, \bar{y}_i^{t-1})=-(y_i - \bar{y}_i^{t-1} ) \\ \\ & h_i=l''(y_i, \bar{y}_i^{t-1})=1 \end{aligned}$$

代入$w_j$有：

$$w_j = \frac{\sum_{i \in I_j} (y_i - \bar{y}_i^{t-1} )}{\sum_{i \in I_j} 1 + \lambda}$$

当$\lambda=0$时，即没有正则项时，第j个叶子节点的预测值为所有落在第j个叶子节点的样本残差的均值。

总结

相比于GBDT的优点：
1.算法层面：

• 显示的在目标函数中加入了正则项，防止过拟合。【正则项是叶子节点个数，和叶子节点预测值的l2正则】
• 对目标函数进行泰勒展开到二阶，统一了形式，方便自定义损失函数，并且使用了二阶导的信息，能更快的逼近最优解。

2.工程层面：

• 传统GBDT以CART作为基分类器，xgboost还支持线性分类器
• 支持对缺失值的处理，对稀疏格式数据的处理。
• 在寻找最优切分点时：
  xgboost的单机版本是采用遍历每个特征的每个取值【Basic Exact Greedy Algorithm】的方式去寻找最优切分点，为了更加高效的计算损失，采用预排序【pre-sorted】的方法按照每个特征对数据进行排序方便累加梯度信息；
  xgboost分布式版本采用近似直方图算法选择最优切分点，【直方图存储了两类信息，分别是每个bin中样本的梯度之和，还有就是每个bin中样本数量】

另外，从最优化的角度来看:
GBDT采用的是数值优化的思维, 在参数空间中利用梯度下降法进行优化，朝着负梯度方向，使得叶子节点的预测值不断逼近真实值，使得损失函数最优
XGboost用的解析的思维, 在函数空间中用牛顿法进行优化，对目标函数展开到二阶近似, 求得叶子节点预测值的解析解, 进而使得损失函数最优.

lightgbm相较于xgboost的优点：

• histogram 算法的好处：1.对于一个特征，pre-sorted 需要对每一个不同特征值都计算一次分割增益，而histogram只需要计算#bin(histogram 的横轴的数量) 次；2.在数据并行的时候，用 histgoram 可以大幅降低通信代价。用 pre-sorted 算法的话，通信代价是非常大的（几乎是没办法用的）。所以 xgoobst 在并行的时候也使用 histogram 进行通信； 3.一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到。

• 在 histogram 算法之上，LightGBM 进行进一步的优化。首先它抛弃了大多数 GBDT 工具使用的按层生长(level-wise) 的决策树生长策略，而使用了带有深度限制的按叶子生长 (leaf-wise) 算法。 level-wise 过一次数据可以同时分裂同一层的叶子，容易进行多线程优化，不容易过拟合。但实际上level-wise是一种低效的算法，因为它不加区分的对待同一层的叶子，带来了很多没必要的开销。因为实际上很多叶子的分裂增益较低，没必要进行搜索和分裂。leaf-wise则是一种更为高效的策略，每次从当前所有叶子中，找到分裂增益最大(一般也是数据量最大)的一个叶子，然后分裂，如此循环。因此同 level-wise 相比，在分裂次数相同的情况下，leaf-wise 可以降低更多的误差，得到更好的精度。leaf-wise 的缺点是可能会长出比较深的决策树，产生过拟合。因此 LightGBM 在leaf-wise 之上增加了一个最大深度的限制，在保证高效率的同时防止过拟合。

直方图存储了两类信息，分别是每个bin中样本的梯度之和，还有就是每个bin中样本数量，故可以一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到。

ref:

LightGBM 直方图优化算法
如何看待微软新开源的LightGBM?
https://blog.csdn.net/sb19931201/article/details/52557382

test mathjax

$$\begin{eqnarray} \nabla\cdot\vec{E} &=& \frac{\rho}{\epsilon_0} \\ \nabla\cdot\vec{B} &=& 0 \\ \nabla\times\vec{E} &=& -\frac{\partial B}{\partial t} \\ \nabla\times\vec{B} &=& \mu_0\left(\vec{J}+\epsilon_0\frac{\partial E}{\partial t} \right) \end{eqnarray}$$