作者：韩信子@ShowMeAI
教程地址：www.showmeai.tech/tutorials/3…
本文地址：www.showmeai.tech/article-det…
声明：版权一切，转载请联络渠道与作者并注明出处

引言

XGBoost是eXtreme Gradient Boosting的缩写称呼，它是一个十分强壮的Boosting算法工具包，优秀的功能（效果与速度）让其在很长一段时刻内霸屏数据科学比赛解决计划榜首，现在很多大厂的机器学习计划依旧会首选这个模型。

XGBoost在并行核算功率、缺失值处理、操控过拟合、猜测泛化能力上都变现十分优秀。本文咱们给咱们详细打开介绍XGBoost，包含「算法原理」和「工程完成」两个方面。

关于XGBoost的工程运用实践，欢迎咱们参阅ShowMeAI的别的一篇实战文章 XGBoost工具库建模运用详解。

（本篇XGBoost部分内容涉及到机器学习根底常识、决策树/回归树/GBDT算法，没有先序常识储备的宝宝能够检查ShowMeAI的文章图解机器学习 | 机器学习根底常识、决策树模型详解、回归树模型详解）及图解机器学习 | GBDT模型详解）。

1.算法原理可视化解读

关于XGBoost的原理，其作者陈天奇本人有一个十分详尽的Slides做了系统性的介绍，咱们在这儿借助于这个资料给咱们做打开解说。

1）监督学习中的一些重要概念

在开始介绍Boosted Tree之前，咱们先来回忆一下机器学习中的一些重要的概念。

（1）监督学习中心要素

符号（Notations）： $xi∈Rdx_i \in R^d$ 表明练习集中的第 $i$ 个样本。

模型（Model）：关于已知的 $x_i$ 怎么猜测 $yi\hat{y}_i$ ？

线性模型（Linear Model） $yi=jwjxij\hat{y}_{i}=\Sigma_{j} w_{j} x_{ij}$ （包含线性回归和逻辑回归），猜测值 $yi\hat{y}_i$ 依据不同的使命有不同的解说：

线性回归（Linear Regression）： $yi\hat{y}_i$ 表明猜测的分数。
逻辑回归（Logistic Regression）： $1/(1+e−yi)1/(1+e^{-\hat{y}_i})$ 猜测了实例为正的概率。
其他：例如在排名使命中 $yi\hat{y}_i$ 可所以排名分数。

参数（Parameters）：需求从数据中学习的东西。

线性模型（Linear Model）： $={wj∣j=1,2,…,d}\Theta =\left \{w_j|j=1,2,\dots,d\right\}$ 。

方针函数（Objective function） $Obj()=L()+()Obj(\Theta )=L(\Theta )+\Omega (\Theta)$

$L()L(\Theta )$ 代表练习丢失函数（Training Loss），表明模型多好的拟合了练习数据。
$()\Omega (\Theta )$ 为正则化项（Regularization）衡量了模型的杂乱程度。

练习数据丢失函数（Training Loss） $L=i=1nl(yi,yi)L=\Sigma_{i=1}^{n}l(y_i,\hat{y}_i)$

平方丢失（Square Loss）： $l(yi,yi)=(yi−yi)2l(y_i,\hat{y}_i)=(y_i-\hat{y}_i)^2$
逻辑丢失（Logistic Loss）： $l(yi,yi)=yiln(1+e−yi)+(1−yi)ln(1+eyi)l(y_i,\hat{y}_i)=y_iln(1+e^{-\hat{y}_i})+(1-y_i)ln(1+e^{\hat{y}_i})$

正则化项（Regularization）：描述了模型的杂乱程度。

L1 Norm（lasso）： $(w)=∣∣w∣∣1\Omega (w)=\lambda||w||_1$
L2 Norm： $(w)=∣∣w∣∣2\Omega (w)=\lambda||w||^2$

（2）监督学习进阶常识

Ridge回归： $i=1n(yi−wTxi)2+∣∣w∣∣2\Sigma_{i=1}^{n}(y_i-w^Tx_i)^2+\lambda||w||^2$

Ridge是线性模型（Linear Model），用的是平方丢失（Square Loss），正则化项是L2 Norm。

Lasso： $i=1n(yi−wTxi)2+∣∣w∣∣1\Sigma_{i=1}^{n}(y_i-w^Tx_i)^2+\lambda||w||_1$

Lasso是线性模型（Linear Model），用的是平方丢失（Square Loss），正则化项是L1 Norm。

逻辑回归（Logistic Regression）： $i=1n(yiln(1+e−wTxi)+(1−yi)ln(1+ewTxi))+∣∣w∣∣2\Sigma_{i=1}^{n}(y_iln(1+e^{-w^Tx_i})+(1-y_i)ln(1+e^{w^Tx_i}))+\lambda||w||^2$

逻辑回归是线性模型（Linear Model），用的是逻辑丢失（Logistic Loss），正则化项是L2 Norm。

（3）方针函数及偏差方差权衡

回忆一下方针函数 $Obj()=L()+()Obj(\Theta )=L(\Theta )+\Omega (\Theta )$ ，为什么方针函数需求两部分组成呢？

优化练习丢失函数（Training Loss）有助于建立猜测模型，很好地拟合练习数据至少能让你更挨近潜在的练习数据的散布。
优化正则化项（Regularization）有助于建立简略的模型：模型越简略，未来猜测的方差越小，猜测越安稳。

2）回归树（Regression Tree）和集成（Ensemble）

（1）回归树（Regression Tree）

回归树，也便是分类回归树（Classification and Regression Tree）（详情请检查ShowMeAI文章回归树模型详解）

决策规矩和决策树相同
每个叶子结点有一个值

（2）回归树集成（Regression Tree Ensemble）

从上图的左图能够看出，共有5个练习样本。

从上图的中图能够看出，每个叶子节点都有猜测值：第一个叶子结点的猜测值是2，第二个叶子结点的猜测值是0.1，第三个叶子结点的猜测值是-1。

小男孩被分到第一个叶子结点中，所以小男孩的猜测值是2；
小女儿被分到第二个叶子结点，她的猜测值是0.1；
剩下的三个人（样本）被分到第三个叶子结点中，他们的值都是-1。

终究的猜测值便是样本在每颗树中所在的叶子结点的猜测值的和。

（3）树集成办法

树集成的办法运用十分广泛，像GBM、随机森林等（详见ShowMeAI文章图解机器学习 | GBDT模型详解和图解机器学习 | 随机森林分类模型详解）。多达对折的数据发掘比赛经过运用各式各样的树集成办法而取胜。

不受输入量纲的影响，因而不需求对特性进行详尽的标准化。
学习特征之间的高阶交互（高阶交叉特征）。
能够扩展，用于不同的职业。

（4）Boosted Tree的模型和参数

模型：假定咱们有K棵树： $yi=k=1Kfk(xi),fk∈F\hat{y}_i=\Sigma_{k=1}^Kf_k(x_i), f_k\in F$ 。其间，F为包含一切回归树的函数空间。

回归树是一个将属性映射到分数的函数。

参数：包含每棵树的结构和叶子结点中的分数。或者运用函数当作参数： $={f1,f2,…,fK}\Theta =\left\{f_1,f_2,…,f_K\right\}$ 。

这儿咱们不学习 $R^d$ 的权重，咱们在Boosted Tree中学习函数（树）。

（5）在单变量上学习Boosted Tree

单变量也便是单个特征，经过了解怎么在单变量上学习Boosted Tree，咱们能够对Boosted Tree的学习方式有个简略的概念。

举例：假定回归树只要一个输入变量t（时刻），期望猜测小哥在t时刻有多喜爱浪漫音乐。

从上左图能够看到，这位小哥在独身的时分，对浪漫音乐的喜爱程度很低；可是当他遇到了女朋友，随着体内荷尔蒙的散布添加，他对浪漫音乐的喜爱程度添加了；可是有一天分手了，他对浪漫音乐的喜爱程度又变低了。当然，咱们也能够发现，上右图的回归树很容易能表达上左图。

为了构建上右图的树，咱们需求学习两个东西：

1、割裂的点；
2、每个分段上的高。

单变量回归树的方针（阶跃函数）

练习丢失：函数怎么拟合点?
正则化：怎么界说函数的杂乱度?（割裂点的个数和每段高度的L2 Norm？）

图（1）是小哥在每个时刻上对浪漫音乐的喜爱程度的散点图；
图（2）能够看到有太多的分割，模型的杂乱度很高，所以模型的 $(f){\color{DarkGreen} \Omega (f)}$ 很高；
图（3）能够看到模型的拟合程度很差，所以 $L(f){\color{DarkGreen} L (f)}$ 很高；
图（4）是最好的，无论是拟合程度和杂乱程度都十分适宜；

（6）一般情形的Boosted Tree

首先回忆上面咱们对Boosted Tree的界说：

模型：假定咱们有K棵树： $yi=k=1Kfk(xi),fk∈F\hat{y}_i = \Sigma_{k=1}^{K} f_k(x_i), f_k\in F$

方针函数： $Obj=i=1nl(yi,yi)+k=1K(fk)Obj=\Sigma_{i=1}^nl(y_i,\hat{y}_i)+\Sigma_{k=1}^K\Omega (f_k)$

$i=1nl(yi,yi)\Sigma_{i=1}^nl(y_i,\hat{y}_i)$ 是成本函数
$k=1K(fk)\Sigma_{k=1}^K\Omega (f_k)$ 是正则化项，代表树的杂乱程度，树越杂乱正则化项的值越高（正则化项怎么界说咱们会在后边详细说）。

当咱们评论树的时分，通常是启发式的：

经过信息增益来做割裂
修剪树木
最大深度
平滑叶值

大多数启发式算法都能很好地映射到方针函数，选用方式（方针）视图让咱们知道咱们正在学习什么：

信息增益 → 练习丢失
修剪 → 对节点的正则化
最大深度 – 函数空间上的约束
平滑叶片值 – L2正则化对叶片的权重

回归树集成界说了怎么得到猜测值，它不仅仅能够做回归，同样还能够做分类和排序。详细做什么使命依赖于「方针函数」的界说：

运用平方误差：能够得到用于回归问题的gradient boosted machine。
运用对数丢失：能够得到LogitBoost用于分类。

3）Gradient Boosting（怎么学习）

在这一节中咱们将正式学习Gradient Boosting。这儿，xgboost的处理咱们能够比照GBDT模型（可参阅ShowMeAI文章图解机器学习 | GBDT模型详解）来了解中心差异。

（1）解决计划

方针函数： $Obj=i=1nl(yi,yi)+k=1K(fk)Obj=\Sigma_{i=1}^nl(y_i,\hat{y}_i)+\Sigma_{k=1}^K\Omega (f_k)$

在做GBDT的时分，咱们没有办法运用SGD，因为它们是树，而非数值向量——也便是说从原来咱们熟悉的参数空间变成了函数空间。

参数空间：学习模型中的权重。
函数空间：学习函数 $f$ ，包含函数的结构和其间的权重。

解决计划：初始化一个猜测值，每次迭代添加一个新函数（ $f$ ）：

yi(0)=0yi(1)=f1(xi)=yi(0)+f1(xi)yi(2)=f1(xi)+f2(xi)=yi(1)+f2(xi)…yi(t)=k=1tfk(xi)=yi(t−1)+ft(xi)\begin{aligned} \hat{y}_i^{(0)} & = 0 \\ \hat{y}_i^{(1)} & = f_1(x_i)=\hat{y}_i^{(0)}+f_1(x_i) \\ \hat{y}_i^{(2)} & = f_1(x_i)+f_2(x_i)=\hat{y}_i^{(1)}+f_2(x_i) \\ \dots \\ \hat{y}_i^{(t)} & = \Sigma_{k=1}^tf_k(x_i)=\hat{y}_i^{(t-1)}+f_t(x_i) \\ \end{aligned}

$yi(t)\hat{y}_i^{(t)}$ 是第 $t$ 次迭代的猜测值。
$yi(t−1)\hat{y}_i^{(t-1)}$ 是 $t - 1$ 次迭代的猜测值。
$f_t(x_i)$ 是第 $t$ 颗树，也便是咱们第 $t$ 次迭代需求得到的树。

（2）方针函数改换

第一步：依据上面的公式，方针函数能够做如下变形

Obj(t)=i=1nl(yi,yi(t))+k=1t(fk)=i=1nl(yi,yi(t−1)+ft(xi))+(ft)+constant\begin{aligned} Obj^{(t)} & =\Sigma_{i=1}^nl(y_i,\hat{y}_i^{(t)})+\Sigma_{k=1}^t\Omega (f_k)\\ & =\Sigma_{i=1}^nl(y_i,\hat{y}_i^{(t-1)}+f_t(x_i))+\Omega (f_t)+constant \end{aligned}

这儿咱们考虑平方丢失，此刻方针函数又能够变形为：

Obj(t)=i=1n(2(yi−yi(t−1))ft(xi)+ft(xi)2)+(ft)+constantObj^{(t)}=\Sigma_{i=1}^n(2(y_i-\hat{y}_i^{(t-1)})f_t(x_i)+f_t(x_i)^2)+\Omega (f_t)+constant

第二步：所以咱们的意图便是找到 $f_t$ 使得方针函数最低。可是，经过上面初度变形的方针函数依然很杂乱，方针函数会产生二次项。

在这儿咱们引进泰勒打开公式：

f(x+x)≃f(x)+f(x)x+1/2f(x)x2f(x+\Delta x)\simeq f(x)+f(x)\Delta x+1/2f(x)\Delta x^2

令 $f(x)=i=1nl(yi,yi(t))f(x)=\Sigma_{i=1}^nl(y_i,\hat{y}_i^{(t)})$
令 $x=ft\Delta x=f_t$

方针函数运用泰勒打开式就能够变成：

Obj(t)≃i=1n(l(yi,yi(t−1))+gift(xi)+1/2hift(xi)2)+(ft)+constantObj^{(t)}\simeq \Sigma_{i=1}^n(l(y_i,\hat{y}_i^{(t-1)})+g_if_t(x_i)+1/2h_if_t(x_i)^2)+\Omega (f_t)+constant

$gi=∂y(t−1)l(yi,y(t−1))g_i = \partial _{\hat{y}^{(t-1)}}l(y_i,\hat{y}^{(t-1)})$
$hi=∂y(t−1)2l(yi,y(t−1))h_i = \partial _{\hat{y}^{(t-1)}}^2l(y_i,\hat{y}^{(t-1)})$

第三部：把常数项提出来，方针函数能够简化为

Obj(t)≃i=1n[gift(xi)+1/2hift(xi)2]+(ft)+constantObj^{(t)}\simeq \Sigma_{i=1}^n[g_if_t(x_i)+1/2h_if_t(x_i)^2]+\Omega (f_t)+constant

思考：为什么要做这么多变化而不直接生成树？

理论好处：知道咱们在学习什么，收敛。
工程好处：回忆监督学习的要素。
- $g_i, h_i$ 都来自丢失函数的界说。
- 函数的学习只经过 $g_i, h_i$ 依赖于方针函数。
- 当被要求为平方丢失和逻辑丢失完成Bootsted Tree时，能够考虑怎么别离代码模块。

（3）从头界说树

在前面，咱们运用 $f_t(x)$ 代表一颗树，在本末节，咱们从头界说一下树：咱们经过叶子结点中的分数向量和将实例映射到叶子结点的索引映射函数来界说树：（有点儿抽象，详细请看下图）

ft(x)=wq(x),w∈RT,q:Rd→{1,2,3,…,T}f_t(x)=w_q(x), w\in R^T, q:R^d\rightarrow \left\{1,2,3,…,T\right\}

$w$ 代表树中叶子结点的权重
$q$ 代表的是树的结构

从上图能够看出，共有3个叶子结点，第一个叶子结点的权重为+1，第二个叶子结点的权重为0.1，第三个叶子结点的权重为-1；其间，小男孩属于第1个叶子结点，老奶奶属于第3个叶子结点。

（4）界说树的杂乱程度

经过下面的式子界说树的杂乱程度（界说并不是唯一的）

(ft)=T+12j=1Twj2\Omega (f_t)=\gamma T+\frac{1}{2}\lambda\Sigma_{j=1}^Tw_j^2

$T\gamma T$ 代表了叶子结点的个树
$12j=1Twj2\frac{1}{2}\lambda\Sigma_{j=1}^Tw_j^2$ 叶子结点分数的L2 Norm

（5）从头审视方针函数

界说在叶子结点 $j$ 中的实例的集合为：

Ij={i∣q(xi)=j}I_j=\left\{i|q(x_i)=j \right\}

依据每棵叶子从头界说方针函数：

Obj(t)≃i=1n[gift(xi)+12hift(xi)2]+(ft)+constant=i=1n[giwq(xi)+12hiwq(xi)2]+T+12j=1Twj2+constant=j=1T[(iIjgi)wj+12(iIjhi+)wj2]+T+constant\begin{aligned} Obj^{(t)}& \simeq \Sigma_{i=1}^n[g_if_t(x_i)+\frac{1}{2}h_if_t(x_i)^2]+\Omega (f_t)+constant \\ & = \Sigma_{i=1}^n[g_iw_q(x_i)+\frac{1}{2}h_iw_q(x_i)^2]+\gamma T+\frac{1}{2}\lambda\Sigma_{j=1}^Tw_j^2+constant \\ & = \Sigma_{j=1}^T[(\Sigma_{i\epsilon I_j} g_i)w_j+\frac{1}{2}(\Sigma_{i\epsilon I_j} h_i+\lambda)w_j^2]+\gamma T+constant \end{aligned}

上式是T个独立二次函数的和

（6）核算叶子结点的值

一些常识需求先了解。关于一元二次函数： $Gx+12Hx2Gx+\frac{1}{2}Hx^2$ ，咱们很容易得到这个函数的最小值和最小值对应的 $x$ 。

最小值对应的 $x$ 相当于求 $Gx+12Hx2Gx+\frac{1}{2}Hx^2$ 的导数，使导数等于0时的值，即 $G x + H x = 0$ ，所以 $x = - G / H$ 。
当 $x = - G / H$ ，对应的 $Gx+12Hx2Gx+\frac{1}{2}Hx^2$ 的值为： $−12∗G2/H-\frac{1}{2}*G^2/H$

也便是：

argminxGx+12Hx2=−GH,H>0minxGx+12Hx2=−12G2H\begin{aligned} argmin_x Gx+\frac{1}{2}Hx^2 & =-\frac{G}{H}, H>0 \\ min_x Gx+\frac{1}{2}Hx^2 & =-\frac{1}{2}\frac{G^2}{H} \end{aligned}

怎么求叶子结点最优的值？接着持续变化方针函数：

界说 $Gj=iIjgiG_j= \Sigma_{i\epsilon I_j}g_i$
界说 $Hj=iIjhiH_j = \Sigma_{i\epsilon I_j}h_i$

Obj(t)=j=1T[(iIjgi)wj+12(iIjhi+)wj2]+T+constant=j=1T[Gjwj+12(Hj+)wj2]+T+constant\begin{aligned} Obj^{(t)}&= \Sigma_{j=1}^T[(\Sigma_{i\epsilon I_j} g_i)w_j+\frac{1}{2}(\Sigma_{i\epsilon I_j} h_i+\lambda)w_j^2]+\gamma T+constant\\ & = \Sigma_{j=1}^T[G_jw_j+\frac{1}{2}(H_j+\lambda)w_j^2]+\gamma T+constant \end{aligned}

假定树的结构 $q (x)$ 是固定的，那么每一个叶子结点的权重的最优值为

wj∗=−Gj/(Hj+)w_j^*=-G_j/(H_j+\lambda)

方针函数的最优值为

Obj=−12j=1TGj2Hj++TObj=-\frac{1}{2}\Sigma_{j=1}^T\frac{G_j^2}{H_j+\lambda}+\gamma T

下图是前面公式解说对应的一个实际例子。

这儿再次总结一下，咱们现已把方针函数变成了仅与 $G、H、、、TG、H、\gamma、\lambda、T$ 这五项已知参数有关的函数，把之前的变量 $f_{t}$ 消灭掉了，也就不需求对每一个叶子进行打分了！那么现在问题来，方才咱们提到，以上这些是假定树结构确认的状况下得到的结果。可是树的结构有好多种，咱们应该怎么确认呢？

（7）贪婪算法生成树

上一部分中咱们假定树的结构是固定的。可是，树的结构其实是有无限种可能的，本末节咱们运用贪婪算法生成树：

首先生成一个深度为0的树（只要一个根结点，也叫叶子结点）
关于每棵树的每个叶子结点，测验去做割裂（生成两个新的叶子结点，原来的叶子结点不再是叶子结点）。在添加了割裂后的方针函数前后变化为（咱们期望添加了树之后的方针函数小于之前的方针函数，所以用之前的方针函数减去之后的方针函数）：

Gain=12(GL2HL++GR2HR+−(GL+GR)2HL+HR+)−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

$GL2HL+\frac{G_L^2}{H_L+\lambda}$ 是左边叶子结点的值
$GR2HR+\frac{G_R^2}{H_R+\lambda}$ 是右面叶子结点的值
$(GL+GR)2HL+HR+\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}$ 是未割裂前的值
$\gamma$ 是引进了多一个的叶子结点添加的杂乱度

接下来要考虑的是怎么寻找最佳割裂点。

例如，假如 $x_j$ 是年龄，当割裂点是 $a$ 的时分的增益gain是多少？

咱们需求做的仅仅只是核算每一边的 $g$ 和 $h$ ，然后核算

Gain=12(GL2HL++GR2HR+−(GL+GR)2HL+HR+)−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

对排序后的实例进行从左到右的线性扫描就足以决议特征的最佳割裂点。

所以，割裂一个结点的办法是：

关于每个节点，枚举一切特性
关于每个特性，按特性值对实例排序
运用线性扫描来决议该特征的最佳割裂点
选用一切特征中最好的割裂计划

时刻杂乱度：

关于一个有d个特征，深度为K的树，核算的时刻杂乱度为：O(dKnlog n)。其间每一层需求花费O(nlog n)的时刻做排序。
能够进一步优化（例如运用近似或缓存排序的特性）。
能够扩展到十分大的数据集。

（8）怎么处理分类型变量

一些树学习算法别离处理分类变量和接连变量，咱们能够很容易地运用咱们推导出的根据分类变量的评分公式。但事实上，咱们没有必要单独处理分类变量：

咱们能够运用one-hot方式处理分类变量：

zj={1ifxisincategoryj0otherwisez_{j}=\left\{\begin{array}{ll} 1 & \text { if } x \text { is in category } j \\ 0 & \text { otherwise } \end{array}\right.

假如有太多的分类的话，矩阵会十分稀少，算法会优先处理稀少数据。

（9）修剪和正则化

回忆之前的增益，当练习丢失削减的值小于正则化带来的杂乱度时，增益有可能会是负数：

Gain=12(GL2HL++GR2HR+−(GL+GR)2HL+HR+)−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

此刻便是模型的简略性和可猜测性之间的权衡。

前停止（Pre-stopping）：当最佳割裂是负数时，停止割裂；可是一个割裂可能会对未来的割裂有利；
后剪枝（Post-Pruning）：把一颗树生长到最大深度，递归修剪一切割裂为负增益的叶子。

2.XGBoost中心原理概括解析

1）方针函数与泰勒打开

XGBoost也是一个Boosting加法模型，每一步迭代只优化当时步中的子模型。第 $m$ 步咱们有：

F_m(x_i) = F_{m-1}(x_i) + f_m(x_i)

$f_m(x_i)$ 为当时步的子模型。
$F_{m-1}(x_i)$ 为前 $m - 1$ 个完成练习且固定了的子模型。

方针函数规划为「经历危险」+「结构危险」（正则项）：

Obj=∑i=1NL[Fm(xi),yi]+∑j=1m(fj)=∑i=1NL[Fm−1(xi)+fm(xi),yi]+∑j=1m(fj)\begin{aligned} O b j &=\sum_{i=1}^{N} L\left[F_{m}\left(x_{i}\right), y_{i}\right]+\sum_{j=1}^{m} \Omega\left(f_{j}\right) \\ &=\sum_{i=1}^{N} L\left[F_{m-1}\left(x_{i}\right)+f_{m}\left(x_{i}\right), y_{i}\right]+\sum_{j=1}^{m} \Omega\left(f_{j}\right) \end{aligned}

正则项 $(f)\Omega (f)$ 表明子模型 $f$ 的杂乱度，用于操控过拟合。

在数学中，咱们能够用泰勒公式近似 $f (x)$ ，详细如下式。XGBoost对丢失函数运用二阶打开来近似。

f(x0+x)≈f(x0)+f′(x0)x+f′′(x0)2(x)2f(x_0+\Delta x) \approx f(x_0)+f^{‘}(x_0) \Delta x + \frac{f^{”}(x_0)}{2} (\Delta x)^2

（更多数学常识推荐阅读ShowMeAI的AI数学根底系列教程图解AI数学根底：从入门到通晓系列教程）。

对应XGBoost的丢失函数，咱们在上式里将 $F_{m-1}(x_i)$ 视作 $x_0$ ， $f_{m}(x_i)$ 视作 $x\Delta x$ ， $L(yi,yi)L(\hat{y_i},y_i)$ 视作关于 $yi\hat{y_i}$ 的函数，得到：

\sum_{i=1}^N \Big[ L[F_{m-1}(x_i),y_i] + \frac{\partial L}{\partial F_{m-1}(x_i)} f_m(x_i) + \frac{1}{2} \frac{\partial^2 L}{\partial^2 F_{m-1}(x_i)} f_m^2(x_i) \Big] +\sum_{j=1}^m \Omega (f_j)

又因前 $m - 1$ 个子模型现已确认了，故上式中除了关于 $f_{m} (x)$ 的部分都是常数，不影响对 $f_{m} (x)$ 的优化求解。方针函数可转化为：

j=\sum_{i=1}^{N}\left[g_{i} f_{m}\left(x_{i}\right)+\frac{1}{2} h_{i} f_{m}^{2}\left(x_{i}\right)\right]+\Omega\left(f_{m}\right)

$gi=∂L∂Fm−1(xi)g_i = \frac{\partial L}{\partial F_{m-1}(x_i)}$
$h_i = \frac{\partial^2 L}{\partial^2 F_{m-1}(x_i)} \\$
这儿的 $L$ 代表丢失函数，衡量一次猜测的好坏程度
在 $F_{m-1}(x)$ 确认了的状况下，对每个样本点 $i$ 都能够容易核算出一个 $g_i$ 和 $h_i$

2）XGBoost的正则化

实际上，XGBoost的基分类器对决策树和线性模型都支撑，这儿咱们只评论更常见的「根据树」的状况。为避免过拟合，XGBoost设置了根据树的杂乱度作为正则项：

(f)=T+12∣∣w∣∣2\Omega(f) = \gamma T + \frac{1}{2} \lambda ||w||^2

$T$ 为树 $f$ 的叶节点个数
$w$ 为一切叶节点输出回归值构成的向量， $w||^2$ 为该向量L2范数（模长）的平方
$\gamma$ 、 $\lambda$ 为超参数

作为回归树，叶子节点越多、输出的回归值越大，树的杂乱度越高。

终究方针函数如下：

\sum_{i=1}^N \Big[g_i f_m(x_i)+\frac{1}{2} h_i f_m^2(x_i)\Big]+\gamma T + \frac{1}{2} \lambda \sum_{j=1}^T w_j^2

下面是一个数学转换处理，为了使正则项和经历危险项合并到一起。咱们把在样本层面上求和的经历危险项，转换为叶节点层面上的求和。

界说节点 $j$ 上的样本集为 $I(j)=\{x_i|q(x_i)=j\}$ ，其间 $q(x_i)$ 为将样本映射到叶节点上的索引函数，叶节点 $j$ 上的回归值为 $wj=fm(xi),i∈I(j)w_j=f_m(x_i),i \in I(j)$ 。

\sum_{j=1}^{T} \Big[ (\sum_{i\in I(j)} g_i) w_j + \frac{1}{2}(\sum_{i\in I(j)} h_i + \lambda) w_j^2 \Big] + \gamma T

进一步简化表达，令 $∑i∈I(j)gi=Gj\sum_{i\in I(j)} g_i=G_j$ ， $∑i∈I(j)hi=Hj\sum_{i\in I(j)} h_i=H_j$ 留意这儿G和H都是关于 $j$ 的函数：

\sum_{j=1}^{T} \Big[ G_j w_j + \frac{1}{2}(H_j + \lambda) w_j^2 \Big] + \gamma T

转化到这个方式后，咱们能够看出，若一棵树的结构现已确认，则各个节点内的样本 $x_i,y_i,g_i,h_i)$ 也是确认的，即 $G_j$ ， $H_j$ 、 $T$ 被确认，每个叶节点输出的回归值应该使得上式最小，由二次函数极值点：

wj∗=−GjHj+w_j^*=-\frac{G_j}{H_j+\lambda}

按此规矩输出回归值后，方针函数值也便是树的评分如下公式，其值越小代表树的结构越好。观察下式，树的评分也能够了解成一切叶节点的评分之和：

Obj∗=∑j=1T(−12Gj2Hj++)Obj^* = \sum_{j=1}^T \Big( -\frac{1}{2}\frac{G_j^2}{H_j + \lambda} + \gamma \Big)

3）节点割裂原则

咱们之前文章【决策树模型详解】里给咱们讲到了决策树模型是递归生长形成的，而XGBoost的子模型树也相同，需求要依赖节点递归割裂的贪心原则来完成树的生成。

咱们之前文章决策树模型详解里给咱们讲到了决策树模型是递归生长形成的，而XGBoost的子模型树也相同，需求要依赖节点递归割裂的贪心原则来完成树的生成。

（1）贪心原则

XGBoost子树的根本处理思路和CART相同，会对特征值排序后遍历区分点，将其间最优的割裂收益作为该特征的割裂收益，选取具有最优割裂收益的特征作为当时节点的区分特征，按其最优区分点进行二叉区分，得到左右子树。

上图是一次节点割裂过程，很自然地，割裂收益是树A的评分减去树B的评分。虚线框外的叶节点，即非割裂节点的评分均被抵消，只留下割裂后的LR节点和割裂前的S节点进行比较，因而割裂收益的表达式为：

\frac{1}{2} \Big[ \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}\Big]-\gamma

（2）近似算法

根据功能的考量，XGBoost还对贪心原则做了一个近似版本，简略说，处理方式是「将特征分位数作为区分候选点」。这样将区分候选点集合由全样本间的遍历减缩到了几个分位数之间的遍历。

打开来看，特征分位数的选取还有global和local两种可选战略：

global在全体样本上的特征值中选取，在根节点割裂之行进行一次即可；
local则是在待割裂节点包含的样本特征值上选取，每个节点割裂前都要进行。

这两种状况里，由于global只能区分一次，其区分粒度需求更细。

XGB原始paper中对Higgs Boson数据集进行了试验，比较了精确贪心原则、global近似和local近似三类装备的测试集AUC，用eps代表取分位点的粒度，如 $e p s = 0.25$ 代表将数据集区分为1/0.25=4个buckets，发现global（eps=0.05）和local（eps=0.3）均能达到和精确贪心原则几乎相同的功能。

XGBoost工具包支撑上述提到的3类装备。

（3）加权分位数

检查方针函数 $Obj=∑i=1N[gifm(xi)+12hifm2(xi)]+(fm)Obj=\sum_{i=1}^{N}\left[g_{i} f_{m}\left(x_{i}\right)+\frac{1}{2} h_{i} f_{m}^{2}\left(x_{i}\right)\right]+\Omega\left(f_{m}\right)$ ，令偏导为0易得 $fm∗(xi)=−gihif_m^*(x_i)=-\frac{g_i}{h_i}$ ，此方针函数可了解为以 $h_i$ 为权重， $−gihi-\frac{g_i}{h_i}$ 为标签的二次丢失函数：

Obj=∑i=1N[gifm(xi)+12hifm2(xi)]+(fm)=∑i=1N12hi[fm(xi)−(−gihi)]2+(fm)+C\begin{aligned} Obj &= \sum_{i=1}^N \Big[g_i f_m(x_i)+\frac{1}{2} h_i f_m^2(x_i)\Big]+\Omega (f_m) \\ & = \sum_{i=1}^N \frac{1}{2} h_i\Big[ f_m(x_i)-(-\frac{g_i}{h_i}) \Big]^2+\Omega (f_m) + C \end{aligned}

在近似算法取分位数时，实际上XGBoost会取以二阶导 $h_i$ 为权重的分位数（Weighted Quantile Sketch），如下图表明的三分位。

4）列采样与学习率

XGBoost为了进一步优化效果，在以下2个方面进行了进一步规划：

列采样
- 和随机森林做法一致，每次节点割裂并不是用全部特征作为候选集，而是一个子集。
- 这么做能更好地操控过拟合，还能削减核算开支。
学习率
- 也叫步长、shrinkage，详细的操作是在每个子模型前（即每个叶节点的回归值上）乘上该系数，不让单颗树太激进地拟合，留有必定空间，使迭代更安稳。XGBoost默许设定为0.3。

5）特征缺失与稀少性

XGBoost也能对缺失值处理，也对特征稀少问题（特征中出现很多的0或one-hot encoding结果）做了一些优化。XGBoost用「稀少感知」战略来一起处理这两个问题：

简略说，它的做法是将缺失值和稀少0值同等视作缺失值，将其「绑定」在一起，割裂节点的遍历会越过缺失值的全体。这样大大进步了运算功率。 0值在XGB中被处理为数值意义上的0还是NA，需求结合详细渠道的设置，预处理区分开作为数值的0（不应该被处理为NA）和作为稀少值的0（应该被处理为NA）。

依然经过遍历得到割裂节点，NA的方向有两种状况，在此根底上对非缺失值进行切分遍历。

如上图所示，若某个特征值取值为1，2，5和很多的NA，XGBoost会遍历以上6种状况（3个非缺失值的切分点缺失值的两个方向），最大的割裂收益便是本特征上的割裂收益，一起，NA将被分到右节点。

3.XGBoost工程优化

1）并行列块规划

XGBoost将每一列特征提早进行排序，以块（Block）的方式储存在缓存中，并以索引将特征值和梯度统计量对应起来，每次节点割裂时会重复调用排好序的块。并且不同特征会散布在独立的块中，因而能够进行散布式或多线程的核算。

2）缓存拜访优化

特征值排序后经过索引来取梯度 $g_i，h_i$ 会导致拜访的内存空间不一致，进而降低缓存的命中率，影响算法功率。为解决这个问题，XGBoost为每个线程分配一个单独的接连缓存区，用来寄存梯度信息。

3）核外块核算

数据量十分大的情形下，无法一起全部载入内存。XGBoost将数据分为多个blocks储存在硬盘中，运用一个独立的线程专门从磁盘中读取数据到内存中，完成核算和读取数据的一起进行。为了进一步进步磁盘读取数据功能，XGBoost还运用了两种办法：

① 压缩block，用解压缩的开支换取磁盘读取的开支。
② 将block分散储存在多个磁盘中，进步磁盘吞吐量。

4.XGBoost vs GBDT

咱们对之前解说过的GBDT（参阅ShowMeAI文章【GBDT算法详解】）和这儿的XGBoost做一个比照总结：

GBDT是机器学习算法，XGBoost在算法根底上还有一些工程完成方面的优化。
GBDT运用的是丢失函数一阶导数，相当于函数空间中的梯度下降；XGBoost还运用了丢失函数二阶导数，相当于函数空间中的牛顿法。
正则化：XGBoost显式地加入了正则项来操控模型的杂乱度，能有用避免过拟合。
列采样：XGBoost选用了随机森林中的做法，每次节点割裂行进行列随机采样。
缺失值：XGBoost运用稀少感知战略处理缺失值，GBDT无缺失值处理战略。
并行高效：XGBoost的列块规划能有用支撑并行运算，功率更优。

更多监督学习的算法模型总结能够检查ShowMeAI的文章 AI常识技术速查 | 机器学习-监督学习。

ShowMeAI相关文章推荐

1.机器学习根底常识
2.模型评价办法与原则
3.KNN算法及其运用
4.逻辑回归算法详解
5.朴素贝叶斯算法详解
6.决策树模型详解
7.随机森林分类模型详解
8.回归树模型详解
9.GBDT模型详解
10.XGBoost模型最全解析
11.LightGBM模型详解
12.支撑向量机模型详解
13.聚类算法详解
14.PCA降维算法详解

ShowMeAI系列教程推荐

图解Python编程：从入门到通晓系列教程
图解数据分析：从入门到通晓系列教程
图解AI数学根底：从入门到通晓系列教程
图解大数据技术：从入门到通晓系列教程
图解机器学习算法：从入门到通晓系列教程

图解机器学习 | XGBoost模型详解

引言