XGBoost
Extreme Gradient Boosting(XGBoost)是由华盛顿大学（University of Washington）的陈天奇作为 Distributed (Deep) Machine Learning Community (DMLC) 组员所开发的一个研究项目。在陈天奇与队友一起赢得了Higgs Machine Learning Challenge后，许多的数据科学竞赛队伍使用XGBoost并获得了冠军，促进了该工具在数据科学应用中的广泛使用。
目标函数
在有监督学习中，我们的目标函数可以分解为训练损失和正则化项：
如果对每个样本，训练损失函数为，则
对树模型而言，，其中
是第
个叶子结点上的socre，每个样本点
会落在某一个叶子节点
上，
是叶子数。在XGBoost中，树的复杂度描述为：
当然还可以加上其他正则项，如L1正则（对应正则化系数）等。
Boosting
Boosting的过程，是拟合一个加性模型。假设我们已经训练了步，对应的模型为
第步，我们的目标是找到
，以最小化目标函数：
将样本损失函数在处做二阶泰勒展开,
对应地，将每个样本代入可得：
其中
而是与
无关的，因此，我们的目标函数可以简化为：
第棵树的目标函数是理论目标函数最优值与前
棵树预测的目标函数值的残差，即以目标函数的负梯度来作为第
棵树的学习目标。
树的分裂准则
我们可以将目标函数重写为
其中。因此，
因此后者可以用来衡量树结构的好坏，用来决定树的分裂。这里我们定义结点分裂的增益为
特性
- 支持线性分类器、DART（Dropouts meet Multiple Additive Regression Trees）以及Tweedie Regression；支持分类、回归、排序任务；
- 二阶导信息。传统GBDT在优化时只用到一阶导数信息，xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。顺便提一下，xgboost工具支持自定义代价函数，只要函数可一阶和二阶求导。
- 正则化项。xgboost在代价函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variance tradeoff角度来讲，正则项降低了模型的variance，使学习出来的模型更加简单，防止过拟合，这也是xgboost优于传统GBDT的一个特性。
- 缩减（Shrinkage）。相当于学习速率（xgboost中的eta）。xgboost在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。实际应用中，一般把eta设置得小一点，然后迭代次数设置得大一点。（补充：传统GBDT的实现也有学习速率）
- 列抽样（column subsampling）。xgboost借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算，这也是xgboost异于传统gbdt的一个特性。
- 对缺失值的处理。xgboost把缺失值当做稀疏矩阵来对待，本身的在节点分裂时不考虑的缺失值的数值。缺失值数据会被分到左子树和右子树分别计算损失，选择较优的那一个。如果训练中没有数据缺失，预测时出现了数据缺失，那么默认被分类到右子树。
- 支持并行。boosting不是一种串行的结构吗?怎么并行的？注意xgboost的并行不是tree粒度的并行，xgboost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。xgboost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），xgboost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。
- 可并行的近似直方图算法。树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以xgboost还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点，大致的思想是根据百分位法列举几个可能成为分割点的候选者，然后从候选者中计算Gain按最大值找出最佳的分割点。
- 特征重要性。XGBoost在训练的过程中给出各个特征的评分，Gain、Cover、Frequency，从而表明每个特征对模型训练的重要性。
常见问题
XGBoost在什么地方做的剪枝，怎么做的？
答：XGBoost 先从顶到底建立树直到最大深度，再从底到顶反向检查是否有不满足分裂条件的结点，进行剪枝。XGBoost如何分布式？特征分布式和数据分布式？ 各有什么存在的问题？
答：XGBoost在训练之前，预先对数据按列进行排序，然后保存block结构。（1）特征分布式/特征间并行：由于将数据按列存储，可以同时访问所有列，那么可以对所有属性同时执行split finding算法，从而并行化split finding（切分点寻找）；（2）数据分布式/特征内并行：可以用多个block(Multiple blocks)分别存储不同的样本集，多个block可以并行计算。
问题：（1）不能从本质上减少计算量；（2）通讯代价高。
