Boosting是集成学习中一种重要的方法，通过集成弱分类器，可以获得比单一学习器性能都好的一个模型。XGBoosting是在Gradient Boosting基础上，进行了一些改动设计，使得算法效率显著提高，并可以并行化。
XGBoosting的亮点主要在以下方面：
- 提出了一个新的针对稀疏数据的稀疏感知型算法
- 提出了一个带权分位数计算的高效算法，用于树的近似学习过程中
- 和传统的GBDT相比，它添加了正则项，显式地防止过拟合
- 从随机森林算法中借鉴了特征子采样(column/feature subsampling)技术
- 通过数据分块来支持并行
算法概略
正则化的目标函数
对于给定的含有 $n$ 个样本，$m$ 个特征的数据集 $\mathcal{D}=\{(\mathbf{x}_i,y_i)\}$，XGBoost和GBDT一样，也是由一棵棵树逐渐构建起整个模型：
$$\hat{y}_i=\phi(\mathbf{x}_i)=\sum_{k=1}^K f_k(\mathbf{x}_i),\quad f_k\in\mathcal{F}\tag{1}$$
其中 $\mathcal{F}=\{f(\mathbf{x}=w_{q(\mathbf{x})})\}(q:\mathbb{R}^m\to T,w\in\mathbb{R}^T)$ 表示所有回归树(CART)的空间。
$q$ 表示一个将样本映射到树的叶结点索引的函数，每一个不同的树结构对应一个不同的函数 $q$。
每一个 $f_k$ 对应一个树结构 $q$ 和叶节点得分 $w$。
以下图为例，这是总模型中的一个基学习器（回归树）$f_k$。设三个叶节点从左到右编号为1，2，3，则 $q(\mathbf{x}_1)=3$，$q(\mathbf{x}_4)=1$。对于回归树，每个叶结点有一个取值连续的得分，如图中红色字体所示，我们用 $w_i$ 来表示（下面也称权重）。
与传统GBDT不同，XGBoost优化的目标函数是带有正则项的，即最小化
$$\mathcal{L}(\phi)=\sum_i l(\hat{y}_i,y_i)+\sum_k\Omega(f_k)\tag{2}$$
其中，第一项是误差项，$\hat{y}_i$是预测出来的目标值，$y_i$是给定的目标值，$l$ 是一个可微的凸的损失函数。而第二项代表了对模型复杂度的度量，用来防止过拟合，其中
$$\Omega(f)=\gamma T+\frac{1}{2}\lambda||w||^2\tag{3}$$
当正则化参数设为0时，这个目标函数即和传统的GBDT没有区别。
梯度提升树
和GBDT一样，XGBoost也是通过递加(Additive)的形式进行训练的，即
$$\begin{array}{c,l}
\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) \\
&\cdots& \\
\hat{y}_i^{(t)}&=&\sum_{k=1}^t f_t(x_i)=\hat{y}_i^{(t-1)}+f_t(x_i) \\
\end{array}$$
则第 $t$ 次迭代中我们要最小化的目标是
$$\mathcal{L}^{(t)}=\sum_{i=1}^n l(y_i,\hat{y}_i^{(t-1)}+f_t(\mathbf{x}_i))+\Omega(f_t)$$这意味着我们每次贪心地添加一个最能改善模型性能地树 $f_t$。为了在一般情况下快速地优化这个目标函数，我们用二阶泰勒展开来近似
回顾泰勒展开
$f(x+\Delta x)\simeq f(x)+f’(x)\Delta x+\frac{1}{2}f’’(x)\Delta x^2$
取 $x=\hat{y}_i^{(t-1)}, \Delta x=f_t(\mathbf{x}_i)$
$$\mathcal{L}^{(t)}\simeq\sum_{i=1}^n [l(y_i,\hat{y}_i^{(t-1)})+g_i f_t(\mathbf{x}_i)+\frac{1}{2}h_i f_t^2(\mathbf{x}_i)]+\Omega(f_t)\tag{4}$$其中 $g_i=\partial_{\hat{y}^{(t-1)}}l(y_i,\hat{y}_i^{(t-1)})$，$h_i=\partial^2_{\hat{y}^{(t-1)}}l(y_i,\hat{y}_i^{(t-1)})$ 分别是损失函数的一阶和二阶导数。由于常数项不影响最优点的位置，去掉常数项，得到
$$\tilde{\mathcal{L}}^{(t)}=\sum_{i=1}^n [g_i f_t(\mathbf{x}_i)+\frac{1}{2}h_i f_t^2(\mathbf{x}_i)]+\Omega(f_t)\tag{5}$$
定义 $I_j=\{i|q(\mathbf{x}_i)=j\}$ 表示叶节点 $j$ 所包含的样本的集合，并代入(3)式，则有
$$\begin{array}{r,l}
\tilde{\mathcal{L}}^{(t)}&=&\sum\limits_{i=1}^n [g_i f_t(\mathbf{x}_i)+\cfrac{1}{2}h_i f_t^2(\mathbf{x}_i)]+\gamma T+\cfrac{1}{2}\lambda\sum\limits_{j=1}^T w_j^2 \\
&=& \sum\limits_{j=1}^T[(\sum\limits_{i\in I_j}g_i)w_j+\cfrac{1}{2}(\sum\limits_{i\in I_j}h_i+\lambda)w_j^2]+\gamma T
\end{array}\tag{5}$$
上式的变化相当于重新排列了以下求和次序，从按样本序号求和变成了按每个叶节点求和。给定一个固定的树结构 $q(\mathbf{x})$，由上式我们可以得到，对叶节点 $j$，最优的权重 $w^{*}_j$ 为
$$w^{*}_j=-\cfrac{\sum_{i\in I_j}g_i}{\sum_{i\in I_j}h_i+\lambda}\tag{6}$$
则对应最优的目标函数值为
$$\tilde{\mathcal{L}}^{(t)}(q)=-\cfrac{1}{2}\sum\limits_{j=1}^T\cfrac{(\sum_{i\in I_j}g_i)^2}{\sum_{i\in I_j}h_i+\lambda}+\gamma T\tag{7}$$