XGBoost

https://www.hrwhisper.me/machine-learning-xgboost/
https://mp.weixin.qq.com/s/_NCKAon-megJbxzV6w3aYg

image.png

CART Tree Ensemble：

image.png

$f'(x)=0$ 与 $f(x)=0$ 最优化问题的解法：

1. 梯度下降法：

$L(w^{t+1})=L(w^t)+L'(w^t)(w^{t+1}-w^t)+R$ ， $R$ 为残差项

我的理解：视 $w^{t+1}$ 为 $x$ ， $w^t$ 为 $x_0$

令 $v$ 为单位向量， $\eta$ 为学习率，当 $w^{t+1}-w^t$ 很小的时候， $R$ 约等于0

$v=-\frac{L'(w)}{||L'(w^t)||}$

$w^{t+1}=w^t-\eta\frac{L'(w^t)}{||L'(w^t)||}$

将 $||L'(w^t)||$ 并入 $\eta$ 中化简为最终表达式：

$w^{t+1}=w^t-\eta L'(w^t)$

2. 牛顿法

泰勒公式在 $w_t$ 处二阶展：
$L(w^{t+1}) \approx L(w^{t}) + L'(w^{t})(w^{t+1} – w^t) + \frac{L”(w^{t})}{2}(w^{t+1} – w^t) ^2$

因为最优点一阶导数为0，求关于 $w^{t+1}$ 的偏导：

$\frac{\partial L(w^{t+1})}{\partial w^{t+1}} = L'(w^{t})+ (w^{t+1} – w^t)L”(w^{t})$

令偏导为0，可得： $w^{t+1} = w^{t} -\frac{L'(w^{t})}{L”(w^{t})}$

$w^{t+1} = w^{t} – H^{-1}g\hspace{5ex} H为海森矩阵，g=L'(w^t)$

3. 在数值分析中的做法：

上面的做法是在最优化问题中的，求的是一阶导为0，即 $f′(x)=0$

而在数值分析中，想要求的是方程式的根，即 $f(x)=0$ ，我们只需要进行一阶展开，并令其为0

$f(x^{t + 1}) =f(x^{t}) + f'(x^{t})(x^{t+1} – x^t) = 0$

得到迭代的公式： $x^{t + 1} = x^t -\frac{f(x^t)}{f'(x^t)}$

XGBoost：

这里定义目标函数如下，损失函数 $l$ ，并带了关于分类器 $f$ 的正则项 $\Omega$ ：

$Obj(\Theta) = \sum_{i=1}^N l(y_i,\hat y_i) +\sum_{j=1}^t \Omega(f_j)， \ \ f_j \in\mathcal{F}$

我们不能用诸如梯度下降的方法，因为 $f$ 是树，而非数值型的向量。所以我们需要用前向分步算法，即贪心法找局部最优解：

基于前向算法的目标函数：

因为 $\hat y_i^{(t)} = \sum_{j=1}^tf_j(x_i)=\hat y_i^{(t-1)} + f_t(x_i)（可引入步长\eta抗过拟合）$
$Obj^{(t)}=\sum_{i=1}^{N}l(y_i,\hat{y_i}^{(t)})+\sum_{j=1}^{t}\Omega(f_j)=\sum_{i=1}^{N}l(y_i,\hat{y_i}^{(t-1)}+f_t(x_i))+\sum_{j=1}^{t}\Omega(f_j)$

目标函数处在第t轮，等于每个样本的损失+t轮每棵树的正则项。而在第t轮，前面的t-1轮的正则项都相当于常数，可以不做考虑。

把 $\hat{y_i}^{t-1}$ 视为x， $f_t(x_i)$ 视为 $\Delta x$ ，故可泰勒展开为：
$Obj^{(t)}=\sum_{i=1}^{N}[l(y_i,\hat{y_i}^{t-1})+g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)]+\sum_{j=1}^{t}\Omega(f_j)$

其中损失函数一阶导为 $g_i$ ，二阶导为 $h_i$ ，注意是对 $\hat{y_i}^{t-1}$ 求导

以平方损失函数为例：

$\sum_{i=1}^{N}(y_i-(\hat{y_i}^{t-1}+f_t(x_i)))^2$

则：（我估计 $f_t(x) \approx 0$ 就在下面忽略了）

$g_i=\frac{\partial(y_i-(\hat{y_i}^{t-1}+f_t(x_i)))^2}{\partial \hat{y}^{t-1}}=2(\hat{y}^{t-1}-y_i)$

$h_i=\frac{\partial^2(\hat{y}^{t-1}-y_i)^2}{\hat{y}^{t-1}} = 2$

由于 $\hat{y}^{t-1}$ 已知，所以 $l(y_i,\hat{y_i}^{t-1})$ 是一个常数，对其函数优化不会产生影响，目标函数可以写成：

$Obj^{(t)} \approx \sum_{i=1}^{N} [g_if_t(x_i)+\frac{1}{2}h_if^2_t(x_i)]+\sum_{i=1}^{t} \Omega(f_i)$

Xgboost 的基模型不仅支持决策树，还支持线性模型

目标函数的正则项：

$\Omega(f_t)=\gamma T+\frac{1}{2} \lambda \sum_{j=1}^{T}w_j^2$

模型复杂度由叶子节点数量T决定，此外叶节点的值 $w_j$ 也不应该太高。

完整的目标函数与化简：

$Obj^{\ (t)} = \underbrace{\sum_{i=1}^N \left(g_if_t({\bf x_i}) + \frac{1}{2} h_if_t^2({\bf x_i})\right)}_{对样本累加} +\gamma T +\frac{1}{2}\lambda \underbrace{\sum_{j=1}^{T} w_j^2}_{对叶结点累加}$

定义 $q$ 函数将x映射到某个叶节点j上，则 $f_t(x)=w_{q(x)}$ ，令 $I_j=\{i|q(x_i)=j\}$

$Obj^{t}=\sum_{i=1}^{N}(g_if_t(x_i)+\frac{1}{2}h_iw^2_{q(x_i)})+\gamma T +\frac{1}{2} \lambda\sum_{j=1}^{T} w_j^2$
$=\sum_{i=1}^{N}(g_iw_{q(x_i)}+\frac{1}{2}h_iw^2_{q(x_i)})+\gamma T +\frac{1}{2}\lambda\sum_{j=1}^{T} w_j^2$
$=\sum_{j=1}^{T}(\sum_{i \in I_j}g_iw_j+\frac{1}{2}\sum_{i \in I_j}h_iw^2_j)+\gamma T +\frac{1}{2}\lambda\sum_{j=1}^{T} w_j^2$
$=\sum_{j=1}^{T}(\sum_{i \in I_j}g_iw_j+\frac{1}{2}(\sum_{i \in I_j}h_i+\lambda)w^2_j)+\gamma T$
$=\sum_{j=1}^{T}(\sum_{i \in I_j}g_iw_j+\frac{1}{2}(H_j+\lambda)w^2_j)+\gamma T$
$G_j=\sum_{i \in I_j}g_i，H_j=\sum_{i \in I_j}h_i$

鉴于
$g_i=\frac{\partial(y_i-(\hat{y_i}^{t-1}+f_t(x_i)))^2}{\partial \hat{y}^{t-1}}=2(\hat{y}^{t-1}-y_i)$
$h_i=\frac{\partial^2(\hat{y}^{t-1}-y_i)^2}{\hat{y}^{t-1}} = 2$
可知 $g_i,h_i$ 是前面 $t-1$ 轮得到的结果，其值已知可视为常数，对 $w_j$ 这个变量求导等于0可进一步简化：
$w^*_j=-\frac{G_j}{H_j+\lambda}$

$Obj=-\frac{1}{2}\frac{G_j}{H_j+\lambda}+\gamma T$

image.png

举个例子：求每个节点每个样本的一阶导数 $g_i$ 与二阶导数 $h_i$ ，然后对所含样本求和得到 $G_j,H_j$ ，最后得到目标函数。目标函数越小则越优。

$\lambda,\gamma$ 都是调参的参数，预先已经设计好了

最优切分点划分算法：

贪心算法
1）从深度0开始对每个叶节点枚举所有的可用特征
2）对某一类特征的所有特征值进行升序排序，通过线性扫描的方式决定最佳分裂点，记录分裂收益
3）选择分裂收益最大的点作为分裂位置，分裂出左右两个最新的叶节点，并关联对应的样本集
4）重复以上步骤

所以怎么算分裂收益？

$Obj_{before} = - \frac{1}{2}[\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}] +\gamma$

$Obj_{after} = - \frac{1}{2}[\frac{(G_L)^2}{H_L+\lambda}+\frac{(G_R)^2}{H_R+\lambda}] +2\gamma$

$obj_{final}= Obj_{before}-Obj_{after} = \frac{1}{2}[\underbrace{\frac{G_L^2}{H_L+\lambda}}_{左子树分数} + \underbrace{\frac{G_R^2}{H_R+\lambda}}_{右子树分数} – \underbrace{\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}}_{分裂前分数}] – \underbrace{\gamma}_{新叶节点复杂度}$

当数据量太大时则无法读入内存进行计算，近似算法主要针对贪婪算法这一缺点给出了近似最优解。

image.png

近似算法(Exact Greedy Algorithm)

举个例子：

image.png

关于分界点的选择，XGBoost有两种策略，全局策略（Global）和局部策略(Local)

Global：学习每棵树前，提出候选切分点
Local：每次分裂前，重新提出候选切分点

直观上来看，Local 策略需要更多的计算步骤，而 Global 策略因为节点没有划分所以需要更多的候选点。

准确度.png

我们可以看到 Global 策略在候选点数多时（eps 小）可以和 Local 策略在候选点少时（eps 大）具有相似的精度。此外我们还发现，在 eps 取值合理的情况下，分位数策略可以获得与贪婪算法相同的精度。局部切分点个数不需要那么多，因为每一次分裂都重新进行了选择。

那么，直接等分得到候选点么？

不是，使用分位数：是使用二阶梯度 $h_i$

$r_k(z) = \frac{1}{\sum_{(x,h) \in D_k} h_i} \sum_{(x,h_i) \in D_k, x<z}h_i$

候选点要求 $|r_k(s_{k,j})-r_k(s_{k,j+1})|<\varepsilon$ ，即让相邻两个候选分裂点相差不超过某个值 $\varepsilon$ ，所以最后会得到 $1/\varepsilon$ 个分割点。

image.png

为什么要用二阶梯度加权？

下面是我们泰勒二阶展开后的目标函数：

$\sum_{i=1}^N\left(g_if_t({\bf x_i}) + \frac{1}{2}h_if_t^2({\bf x_i})\right) + \Omega(f_t)$
$=\sum_{i=1}^N\frac{1}{2}h_i\left(2\frac{g_i}{h_i}f_t({\bf x_i}) + f_t^2({\bf x_i})\right) + \Omega(f_t)$
$=\sum_{i=1}^N \frac{1}{2}h_i\left(\frac{g_i^2}{h_i^2} +2\frac{g_i}{h_i}f_t({\bf x_i}) + f_t^2({\bf x_i})\right) + \Omega(f_t)$
（因为加入的 $g_i,h_i$ 是上一轮 $f_{t-1}(x)$ 的，所以是常数）
$=\sum_{i=1}^N \frac{1}{2}{h_i}\left( f_t({x_i}) – ({- \frac{g_i}{h_i}})\right)^2 + \Omega(f_t)$

长得很像是标签为 $-\frac{gi}{hi}$ ，权重为 $h_i$ 的平方损失，因此用 $h_i$ 加权

稀疏值处理：

在真实世界中，我们的特征往往是稀疏的，可能的原因有：

1）数据缺失值
2）大量的0值（比如统计出现的）
3）进行了One-hot 编码（又称为一位有效编码，主要是采用N位状态寄存器来对N个状态进行编码，每个状态都由他独立的寄存器位，并且在任意时候只有一位有效）

决策树模型不推荐对离散特征进行one-hot编码：

会产生样本不平衡问题，本来特征是：红的白的绿的，现在变为是否红的、是否白的、是否绿的。。只有少量样本为 1，大量样本为 0。这种特征的危害是，本来节点的划分增益还可以，但是拆分后的特征，占总样本的比例小的特征，所以无论增益多大，乘以该比例之后会很小，占比例大的特征其增益也几乎为 0，影响模型学习；决策树依赖的是数据的统计信息，one-hot 会把数据切分到零散的小空间上，在这些零散的小空间上，统计信息是不准确的，学习效果变差。

稀疏感知算法：

XGBoost 在构建树的节点过程中只考虑非缺失值的数据遍历，而为每个节点增加了一个缺省方向，当样本相应的特征值缺失时，可以被归类到缺省方向上，最优的缺省方向可以从数据中学到。至于如何学到缺省值的分支，其实很简单，分别枚举特征缺省的样本归为左右分支后的增益，选择增益最大的枚举项即为最优缺省方向。

先计算不含缺失值的样本得到分类的score，然后：
1）让特征k的所有缺失值（整体）的都到右子树，然后和之前的一样，枚举划分点，计算最大的gain
2）让特征k的所有缺失值的都到左子树，然后和之前的一样，枚举划分点，计算最大的gain

使用了该方法，相当于比传统方法多遍历了一次，但是它只在非缺失值的样本上进行迭代，因此其复杂度与非缺失值的样本成线性关系。在Allstate-10k数据集上，比传统方法快了50倍:

image.png

XGBOOST的加速

分块并行：

1）Block中的数据以稀疏格式CSC进行存储（增加一些"元信息"来描述矩阵中的非零元素存储的位置(基于列)，然后结合非零元素的值来表示矩阵。这样在一些场景下可以减少矩阵存储的空间）
2）Block中的特征进行排序（不对缺失值排序）
3）Block 中特征还需存储指向样本的索引，这样才能根据特征的值来取梯度。
4）一个Block中存储一个或多个特征的值

image.png

只需在建树前排序一次，后面节点分裂时可以直接根据索引得到梯度信息。缺点是空间消耗大了一倍。

缓存优化

使用Block结构的一个缺点是取梯度的时候，是通过索引来获取的，而这些梯度的获取顺序是按照特征的大小顺序的。这将导致非连续的内存访问，可能使得CPU cache缓存命中率低，从而影响算法效率。

CPU的Cache理论：

程序局部性原理，包括时间局部性和空间局部性。即最近被CPU访问的数据，短期内CPU 还要访问（时间）；被 CPU 访问的数据附近的数据，CPU 短期内还要访问（空间）。因此如果将刚刚访问过的数据缓存在Cache中，那下次访问时，可以直接从Cache中取，其速度可以得到数量级的提高。

因此，对于exact greedy算法中, 使用缓存预取。具体来说，对每个线程分配一个连续的buffer，读取梯度信息并存入Buffer中（这样就实现了非连续到连续的转化），然后再统计梯度信息。该方式在训练样本数大的时候特别有用。

image.png

Block大小设置：

在approximate 算法中，对Block的大小进行了合理的设置。定义Block的大小为Block中最多的样本数。设置合适的大小是很重要的，设置过大则容易导致命中率低，过小则容易导致并行化效率不高。经过实验，发现 $2^{16}$ 比较好。

image.png

Blocks for Out-of-core Computation

当数据量太大不能全部放入主内存的时候，为了使得out-of-core计算称为可能，将数据划分为多个Block并存放在磁盘上。

计算的时候，使用独立的线程预先将Block放入主内存，因此可以在计算的同时读取磁盘
Block压缩，貌似采用的是近些年性能出色的LZ4 压缩算法，按列进行压缩，读取的时候用另外的线程解压。对于行索引，只保存第一个索引值，然后用16位的整数保存与该block第一个索引的差值。
Block Sharding，将数据划分到不同硬盘上，提高磁盘吞吐率

XGBoost为什么快

当数据集大的时候使用近似算法
Block与并行
CPU cache 命中优化
Block预取、Block压缩、Block Sharding等

XGBoost与传统GBDT的不同

传统GBDT以CART作为基分类器，XGBoost还支持线性分类器，这个时候XGBoost相当于带L1和L2正则化项的Logistic回归（分类问题）或者线性回归（回归问题）。
传统的GBDT只用了一阶导数信息（使用牛顿法的除外），而XGBoost对损失函数做了二阶泰勒展开。并且XGBoost支持自定义损失函数，只要损失函数一阶、二阶可导。
XGBoost的目标函数多了正则项，相当于预剪枝，使得学习出来的模型更加不容易过拟合。
XGBoost还有列抽样，进一步防止过拟合。
对缺失值的处理。对于特征的值有缺失的样本，XGBoost可以自动学习出它的分裂方向。
XGBoost工具支持并行。当然这个并行是在特征的粒度上，而非tree粒度，因为本质还是boosting算法。

XGBOOST与RF（随机森林）的区别

数据敏感性：RF对异常值不敏感，而GBDT对异常值比较敏感
最终结果：RF最终是多棵树进行多数表决（回归问题是取平均），而GBDT是加权融合

比较LR和GBDT，说说什么情景下GBDT不如LR

LR是线性模型，可解释性强，很容易并行化，但学习能力有限，需要大量的人工特征工程
GBDT是非线性模型，具有天然的特征组合优势，特征表达能力强，但是树与树之间无法并行训练，而且树模型很容易过拟合；

当在高维稀疏特征的场景下，LR的效果一般会比GBDT好。原因如下：

一个二分类问题，label为0和1，特征有100维，如果有1w个样本，
但其中只有10个正样本1，而这些样本的特征 f1的值为全为1，
而其余9990条样本的f1特征都为0(在高维稀疏的情况下这种情况很常见)。

我们都知道在这种情况下，树模型很容易优化出一个使用f1特征作为重要
分裂节点的树，因为这个结点直接能够将训练数据划分的很好，
但是当测试的时候，却会发现效果很差，因为这个特征f1只是刚好偶然间
跟y拟合到了这个规律，这也是我们常说的过拟合。

那么这种情况下，如果采用LR的话，应该也会出现类似过拟合的情况呀：y = W1f1 + Wifi+….，其中 W1特别大以拟合这10个样本。为什么此时树模型就过拟合的更严重呢？

因为现在的模型普遍都会带着正则项，而 LR 等线性模型的正则项是对权重的惩罚，也就是 W1一旦过大，惩罚就会很大，进一步压缩 W1的值，使他不至于过大。但是，树模型则不一样，树模型的惩罚项通常为叶子节点数和深度等，而我们都知道，对于上面这种 case，树只需要一个节点就可以完美分割9990和10个样本，一个结点，最终产生的惩罚项极其之小，相当于没有正则化项也就没有过拟合的保护。

这也就是为什么在高维稀疏特征的时候，线性模型会比非线性模型好的原因了：带正则化的线性模型比较不容易对稀疏特征过拟合

防止过拟合的措施：

1）目标函数的正则项，叶子节点数+叶子节点数输出分数的平方和 $\Omega(f_t) =\gamma T +\frac{1}{2}\lambda\sum_{j=1}^{T} w_j^2$
2）行抽样和列抽样：训练的时候只用一部分样本和一部分特征
可以设置树的最大深度
3）η: 可以叫学习率、步长或者shrinkage
4）Early stopping：使用的模型不一定是最终的ensemble，可以根据测试集的测试情况，选择使用前若干棵树

叶节点的权值是什么？

利用当前叶子上所有样本的一阶梯度和二阶梯度计算出来的

图片.png

其中 $w_j$ 是第j个叶节点， $g_i$ 是第j个叶节点的第i个样本的一阶导， $h_i$ 则是二阶导， $\lambda$ 是正则化系数

最后编辑于：2022.03.02 21:52:39

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 218,546评论 6赞 507
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 93,224评论 3赞 395
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 164,911评论 0赞 354
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,737评论 1赞 294
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,753评论 6赞 392
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,598评论 1赞 305
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,338评论 3赞 418
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 39,249评论 0赞 276
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,696评论 1赞 314
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,888评论 3赞 336
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 40,013评论 1赞 348
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,731评论 5赞 346
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,348评论 3赞 330
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,929评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 33,048评论 1赞 270
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 48,203评论 3赞 370
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,960评论 2赞 355

XGBoost

CART Tree Ensemble：

与最优化问题的解法：

1. 梯度下降法：

2. 牛顿法

3. 在数值分析中的做法：

XGBoost：

最优切分点划分算法：

稀疏值处理：

XGBOOST的加速

Blocks for Out-of-core Computation

XGBoost为什么快

XGBoost与传统GBDT的不同

XGBOOST与RF（随机森林）的区别

比较LR和GBDT，说说什么情景下GBDT不如LR

防止过拟合的措施：

叶节点的权值是什么？

推荐阅读更多精彩内容

$f'(x)=0$ 与 $f(x)=0$ 最优化问题的解法：