XGBoost，一种可计算提升树机器学习系统，主要做出了如下贡献：
1、设计并提供一种可以高效计算的端到端提升树系统；
2、提出一种可用于高效地命题计算的理论合理的加权分位数略图；
3、提出一种适用于并行树计算的稀疏感知算法；
4、提出一种高效的缓存感知块结构用于核外树学习（也就是有大量数据存在硬盘而不是内存）
给定一个数据集$D$，包含$n$个样本，每个样本有$m$个特征，也即
\[D=\{(X_i,y_i)\}(|D|=n,X_i\in R^m,y_i\in R)\]集成树模型用$K$个函数的相加结果来预测输出
\[\hat{y_i}=\Phi(X_i)=\sum_{k=1}^{K}f_k(x_i),f_k\in F\]其中，$F={f(X)=w_{q(X)}}(q:R^m\rightarrow T,w\in R^t)$是回归树（这里专指CART）的空间。这里的$q$代表每棵树的结构（也就是样本到对应的叶子结点的索引的映射）；$T$是这课树的叶子结点个数。每个$f_k$对应一个单独的树的结构$q$及其叶子结点们的权重$w$。每个叶子结点都有一个对应值，$w_i$代表第$i$个叶子结点上的值。
要优化的带正则化项的优化目标为：
\[L(\Phi)=\sum_i l(\hat{y_i},y_i)+\sum_k \Omega(f_k)\]其中，
\[\Omega(f)=\gamma T+\frac{1}{2}\lambda \| w \|^2\]这里的$l$是一个可微的凸损失函数，衡量预测$\hat{y_i}$和目标$y_i$之间的差距，$\Omega$用来惩罚模型复杂度（也就是惩罚这些回归树的函数），额外的正则化项可以平滑最终的学习权重避免过拟合。
上面带正则项的优化目标不是用欧氏空间上传统的优化算法来优化的，而是通过一种相加的方式进行训练。令$\hat{y_i}^{(t)}$表示第$i$个样本在第$t$次迭代时的预测结果（也就是第$t$棵树的预测结果），在第$t$次迭代时，我们是加上$f_t$来最小化下面的目标：
\[L^{(t)}=\sum_{i=1}^n l(y_i,\hat{y_i}^{(t-1)}+f_t(X_i))+\Omega(f_t)\]也就是说，我们每次迭代时采用贪心算法加上当前最能提升我们模型的$f_t$。二阶近似在一般情况下可以快速优化目标
\[L^{(t)}\simeq \sum_{i=1}^n[l(y_i,\hat{y}^{(t-1)})+g_if_t(X_i)+\frac{1}{2}h_if_t^2(X_i)]+\Omega(f_t)\]其中，$g_i=\partial_{\hat{y}^{(t-1)}}l(y_i,\hat{y}^{(t-1)})$，$h_i=\partial_{\hat{y}^{(t-1)}}^2 l(y_i,\hat{y}^{(t-1)})$分别为是损失函数的一阶和二阶导数。对第$t$次迭代来说，$l(y_i,\hat{y}^{(t-1)})$是一个常数，可以从优化目标中移除不影响，那么
\[\tilde{L}^{(t)}=\sum_{i=1}^n[g_if_t(X_i)+\frac{1}{2}h_if_t^2(X_i)]+\Omega(f_t)\]定义
\[I_j=\{i|q(X_i)=j\}\]代表叶子结点$j$的样本集合，将$\Omega$展开，
\[\tilde{L}^{(t)}=\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\\ =\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\]对于一个固定的结构$q(X)$，我们可以通过下面的式子计算叶子结点$j$的最优权重$w_j^*$
\[w_j^*=-\frac{\sum_{i\in I_j}g_i}{\sum_{i\in I_j}h_i+\lambda}\]那么对应的最优值就是
\[\tilde{L}^{(t)}(q)=-\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\]上面这个式子可以作为评分函数来衡量树结构$q$的质量（类似于决策树中的不纯度函数，只不过XGBoost用的评分函数由更广泛的目标函数推导而来）。
枚举所有树结构$q$是不现实的，实际使用的是一种贪心方法，一开始将所有样本放在一个结点中，然后迭代地向树中加入分支。假设$I_L$和$I_R$是分割后左右节点的样本集合，$I=I_L+I_R$，分裂结点后的损失下降为
\[L_{split}=\frac{1}{2}[\frac{(\sum_{i\in I_L}g_i)^2}{\sum_{i\in I_L}h_i+\lambda}+\frac{(\sum_{i\in I_R}g_i)^2}{\sum_{i\in I_R}h_i+\lambda}-\frac{(\sum_{i\in I}g_i)^2}{\sum_{i\in I}h_i+\lambda}]-\gamma\]上面的公式实践中常用来评估划分候选。
除了正则化项，XGBoost还用到了两种防止过拟合的技术。Shrinkage是指每一次迭代后，将新的树的叶子结点权重乘以一个系数$\mu$再相加。减少了每棵树的影响，为未来的树留出了空间。
第二个技术是column（也就是特征feature）的子采样，列（也就是特征）的子采样实际中比行（也即是样本）的子采样更有效，而且列子采样还加快了并行算法的速度。
枚举所有可能的划分，要实现这种，必须实现按照特征对样本进行排序，然后按照排序访问样本累计梯度。
当数据无法全部装入内存以及需要分布式训练的时候，朴素贪心算法就不适用了，需要一种算法来近似。
根据数据的百分比提出候选分割点，然后将数据放入由分割点分割出来的桶中，根据汇总后的数据和分割点分割出来的桶寻找最优分割。