一.Background
GBDT是一种常见的机器学习算法，在很多领域有广泛的应用，例如分类问题，点击率预测等。但在数据集比较大的时候，GBDT为了找到最适合的分割点，这个过程需要扫描所有的数据，所以复杂度随着数据样本的维度和特征的维度线性增长，需要在正确率和效率上做tradeoff。为了面对这样的挑战，最直接的想法就是减少数据量和特征数量。因此微软围绕这两点这GBDT做了两点改进[1]，并开源了代码。
二.GBDT复杂度
GBDT是决策树的集成模型，在每次迭代过程中，GBDT通过拟合负梯度（残差）学到决策树。GBDT主要的时间花销是学习决策树，学习决策树中的主要工作是找到分割点。被大家广泛采用的算法是通过预排序找到分割点，这种方法列举于预排序中所有可能的分割点，算法简单、精确，当时效率低下、内存消耗大。 另外一种算法是基于直方图的GBDT算法，不是直接扫描数据找到分割点，而是通过将连续的特征值映射到离散的区间中，使用这些离散的值构建特征，直方图算法效率更高，内存占用更少。基于直方图算法将复杂度从降低到，具体算法参考Algorithm 1。但这种方法这维度也很高的情况下，仍然复杂度很高。
下面谈一下微软的解决方案。
三.Gradient-based One-Side Sampling (GOSS)
对于数据量很大的问题，微软提出一种叫GOSS的方法，即基于梯度的单边采样。 在AdaBoost中，采样权重作为数据实例重要性的衡量指标。然而在GBDT中，没有内含的样本权重，于是基于采样方法的权重不能应用于GBDT中。但如果样本的梯度值小，这个样本的误差就小，说明这个样本已经训练得很好了，直接的想法就是抛弃拥有小梯度的实例数据，这样一来数据的分布就会发生改变，会损失学到的模型的精确度。 GOSS的基本思想就是保留梯度较大的样本，对于梯度比较小样本采用采样的方法。GOSS首先根据梯度绝对值排序，再选出大梯度样本数据。之后在余下的数据随机采样。
1.算法流程
GBDT使用决策树学习函数，这个函数将输入变量空间映射到梯度空间。假设我们有独立同分布的个实例，每个实例向量维度为空间中的。在每次梯度迭代过程中，关于模型输出变量的损失函数的负梯度表示为。 决策树在最大信息增益的地方为分割点。对于GBDT，通常通过方差衡量分割后的信息增益。
对于特征，决策树选取并计算最大的信息增益
GOSS的步骤： 1.首先我们根据梯度对训练样本进行降序排序； 2.我们抽取前的作为数据集A，对于剩余的数据集随机采样个样本作为数据集； 3.最后我们在来计算。即
2.理论分析
论文中也给出了这种做法可能带来的误差(证明不加赘述)：
（1）根据作者的证明，GOSS的近似比例为，在分割比较平衡的情况下，误差主要来源于上式的第二项，在趋于无限大的时候，误差趋向于0。 （2）对于的情况，是对数据集进行随机采样。
四.Exclusive Feature Bundling (EFB)
对于训练数据的特征维度很高的情况，微软提出了融合互斥特征的方法。
高维度数据通常具有稀疏的特征。稀疏特征如果在某些位置为0，而另外的稀疏特征在对应位置有数值，这个时候可以把这两个特征融合在一起，从而降低特征的稀疏性，同时也降低了特征的维度。 作者证明选择出最佳的绑定策略是NP-hard问题，所以微软提出了Algorithm3的绑定方法，该方法容忍了一定的特征互斥。再用Algorithm4对互斥特征进行融合。 EFB算法可以绑定大量的排他性特征到很少的密度特征中，这样可以有效避免零值的计算。事实上，我们可以使用表标记非零值，忽略零特征值达到优化基本的直方图算法的目的。通过扫描表中的数据，花销从降低到。这种在树构建构成中的方法需要额外的内存和计算开销维持预特征表。
