回顾一下boosting tree的基础知识，主要是gbdt、lambdamart、xgboost、lightgbm等，温习一下主要的实现原理,keypoint，这里对公式啥的就简单的表示一下。之前的文章中提到了决策树，决策树的目标是又多种定义方式，比如信息增益、信息增益率或者gini系数，决策树是单颗树，而boosting是用多个弱分类器来拟合最后的得分，即F(x) = f1(x)+f2(x)+…+fn(x)，fi(x)即弱分类器，实现上用tree来实现，所以现在的问题就是给你一个训练集，Train=[1…N][x1..n]，如何来训练这么多tree，叶子节点的value代表最后的分数,区别于random forest的bagging，即tree之间的训练没有明显区别，这里是boosting，即提升。既然是tree，如何控制分裂？分裂的最大收益是什么？

gbdt

gbdt分裂的标准是”统一、均匀”，拟合label的任务由loss的一阶导数来做，即tree分裂后，落到一起的样本”loss的一阶导数”的均方差最小，则为最佳分裂点。叶子节点上的值也是loss对F(x)i-1的求导(注意这里不是对fi(x)的求导，每次完事后需要更新). Fi(x) = F(x)i-1 + shrink$\cdot$fi(x)，当然叶子节点的值没有shrink，loss使用最简单的最小二乘法loss=(yi-Fi-1(x))2，可见这个loss是可导的，这个非常重要，对 F(x) 求导得 gradient=-2$\cdot$(-1)(yi-Fi-1(x)), gradient的就是所求的fi(x)很简单(拟合残差，最后加一起可不就是label了么)，可以通过参数设置树的深度、叶子节点最大个数、均方差满足提前收敛等。缺点是没有设置模型复杂度目标不是么？应该是可以做的， Obj = EM(gi-$\overline{g}$)2+W2(W是分裂点的叶子权重f(x)) + lambda$\cdot$T(T为页节点个数) [这应该就是防止无限分裂以及某些点上出现极值的情况发生], 每次遍历所有的feature的所有value split，得到 min(Obj)，即使最佳分裂点，当然不能比没分离的还挫。

lambdamart

肯定会有问题，这个gbdt是否只是point-wise，如果扩展到 pair-wise和list-wise，好像有困难，pair-wise和list-wise的一些标准计算再算loss貌似不可导，如果引入group的概念来解决组内的一些规则的计算呢，比如搜索场景下一个query对应多条结果，算MAP, ERR, NDCG等，把这些搜索指标融入到树的分裂目标？
这里就提到了lambda mart，之前先介绍rank-net，引入了pair对比信息，定义了
$$
Sij=
\begin{cases}
0 & x_i负例，x_j正例 \\
1 & x_j负例，x_i正例
\end{cases}
$$
于是定义了目标
$$
C=\frac{1}{2}(1-Sij)\delta(s_i-s_j)+log(1+e^{-\delta(s_i-s_j)})
$$
这样，目标里就简单的将两个文档的比较融入到目标中，比如上面的Sij目标中，xi是正例，xj是负例，那么拉大si和sj的差距成为目标, C对w的求导可以转化为C对si和sj的求导！而！！容易得到
$$
\frac{\partial C}{\partial s_i} = - \frac{\partial C}{\partial s_j}
$$
这样第i步的迭代即f(xi)的计算可以转化为组内和其不同label的样本的计算，比xi差的为其贡献正梯度，比xi好的为其贡献负梯度，这就是 $\lambda_{ij}$
当然这远远不够，这仅仅是rank-net，这里大家看到的好像就是两个pair之间的定制关系，如何引入复杂的目标呢？ 比如NDCG, 很简单，$\lambda_{ij}$*($\Delta$NDCG)，$\Delta$NDCG 这个怎么算？交换i和j后整个NDCG得分的bias。好了，lambda-mart诞生了，rank-net提供了复杂应用目标的梯度计算方式，mart即多个弱分类器(tree)提供了整体的框架，那就结合吧。最后叶子节点值的结算可以参考论文里的，直接带进去算就可以了，当然要记住，分裂的基础仍然是拿这个f(x)做均方差分裂, 将均匀的样本分到一起。
Lambda-mart-gbdt 的实现分裂方式不变，仍然采用均方差最小的方式(暂不提正则)，而叶子节点的计算不再是简单的loss的负梯度，而是转为lambda rank的计算方式，通过group里lambda的方式获得，这里又不仅限于lambda，而是进一步优化，采用牛顿法的思想，一阶梯度不行了，要对Ft-1(x)做二阶导，$F(x)=F(x)-F’(x)/F’’(x)，f(x) = F’(x)/F’’(x)$, 二阶导数有利于更快的收敛，这也是优化点之一。

xgboost

xgboost 呢，对目标做了详细规划
$$
OBJ=L+\Omega \\
L = L(yi, Fx-1(x)+fi(x)) \\
\Omega = T + \frac{1}{2} * \lambda * W^{2}
$$
这里 对L做了泰勒二阶展开(万物皆可泰勒)
$$
f(x+\Delta x) = f(x) + f’(x) * \Delta x+\frac{1}{2} * f’’(x)+(\Delta x)^2
$$
算出gi, 和 hi, 即Fi-i(x)的一阶导和二阶导，$\Delta x$ 是叶子节点的权重即fi(x)即w。通过归并，将训练集归并到T个叶子节点上，通过求最大值，可以得出最小值，这个最小值则是split的参考, gi和hi可以很容易的通过同group里不同label的s算得到。这里的split和上面的不一样了，这里的split是让L最小的split，即遍历各个split value，根据泰勒展开后满足条件的$\Delta x$，带入求得最小的min$\Sigma$L。由于是二阶泰勒展开，所以也是和牛顿法有相同收敛速度的算法。
参考陈天奇的 “Introduction to Boosted Trees” slide

Light GBM

https://www.hrwhisper.me/machine-learning-lightgbm/ 不错的介绍

特点

  1. 直方图:Float feature => bin 分桶里，len(bin) <<< len(feature)，split点的计算量不再随sample的增加而增加
  2. Presort改为pre cal，将每个sample的g,h 计算出来，落到分桶里；计算best split时，可以根据直方图，直接计算，计算量减半，right = all - left，且直方图可以通过简单的减法，在分裂时直接继承
  3. Leaf wise: 不再限定死宽度，允许深度分裂，较灵活
  4. GOSS: 单边采样，相对于列采样，效果更好？ada的思想，对拟合不好的样本加大其对应梯度的权重
  5. EFB: exclusive feature bundling，互斥的特征捆绑，降低特征维度，（不采用PCA的原因是PCA是有损的。。。）， EFB可以比较精细的控制，如果完全互斥，则肯定对精度无损，如何获取互斥特征，采用图着色法，相同颜色的节点(特征)则可以绑定

gbdt里的目标逼近

$F(m)=F(m-1)+f(x)$，如何通过优化$f(x)$来让$F(m)$逼近真实的目标y？
首先定义损失函数，最简单的就是$loss=|y-F(m-1)|$，由于绝对值不好求导，所以一般转为最小二乘法的形式，即$loss=(y-F(m-1))^2$，通过改变自变量$F(m-1)$来获得目标loss的极值，肯定是要对自变量求导，用负梯度作为方向来更新自变量，所以
$$f(x)=\vartheta_{F(m-1)}loss$$
这里有个问题，最小二乘法可以用牛顿求解么？可以先看一个例子 $y=x^2$，初始x=2，求y极值对应x的变化，$loss=0-x^2$，$g1=-2x$，如果按照这个更新，step2中，$x=2+2(-2)=-2$，可以看到一阶的倒数可能方向是ok的，但是步子容易迈得太大，需要learning rate的控制，如果进一步使用牛顿法呢？
$$x=x-\frac{g1}{g2}$$
$$g2=\vartheta_{x}g1=-2$$
这样$x=2-(-22)/(-2)=0$，似乎更好一些？我是认为牛顿法适用于所有类型的loss，而并非简单地就不好使。好了，下面开始说二分类的目标，要复杂一些。
先直接贴结论:
$$f(x)=-g1=\frac{2y}{1+e^{-2yF(m-1)}}$$ 而叶子节点的值为
$$\gamma_{jm}=-\frac{g1}{g2}=\frac{\sum_{x_i\in{Rjm}}f(x_i)}{\sum_{x_i\in{Rjm}f(x_i)(2-f(x_i))}}$$