GBDT和Xgboost可以说是目前比较流行的机器学习模型，在各大比赛中也是大放异彩，借着毕设以及天池智能制造比赛的机会，也深入了解了一下。
首先要明确一点，两者都是以树模型为基础的，所以本质上还是在节点分裂的时候，如何选择分裂点，分裂的依据是什么。
两者可以说都是Boosting算法的具体实现，而且十分相似，这里主要比较一下两个模型的不同点（主要讲回归），而对于模型的具体算法和推导过程，可以参考陈天奇的文章以及知乎的回答以及其中的PPT介绍，个人感觉是说的比较清楚的两个，这里也从中摘录了一些图和段落过来。
Boosting是一种加法模型，模型最终的结果是多个基模型结果相加得到的，GBDT和Xgboost在这一点上是相同的，个人认为两者比较大的区别在于，GBDT是在函数空间通过梯度下降法来求解，而Xgboost是在函数空间通过牛顿法来求解，同时Xgboost还加入了正则化项来进行bias-variance的tradeoff。当然还有一些具体实现上的区别，这个可以具体看一下上面知乎的回答。下面分别来看一下这两种算法。
GBDT
GBDT的算法流程如下图所示
这里需要解释一下的是，各种教程上都说，后续树的构建都是要拟合“残差”，但是为啥图中的流程就变成损失函数的负梯度了？原因就在于，对于特定的平方损失函数，其负梯度和残差是一样的。所以其实我不是很喜欢从“残差”这个角度去解释，而是从函数空间的角度去想，在参数空间内，梯度下降大家应该都很熟悉了，只需要不断将参数向着损失函数的负梯度方向调整就可以了，也就是说，最后的参数值或者说自变量的值，可以写作\(x = x_0 + \sum_{m=0}^Mx_m\),其中，\(x_m = -\rho_mg_m\),\(g_m\) 是损失函数的梯度方向，也就是从初值开始，不断进行负梯度方向的累加，直到达到最优值。
而GBDT的优化其实是在函数空间的，参数空间内的x变成了一个函数（或者说是一棵树），所以，我们树的输出也要向着损失函数的负梯度方向调整，下一棵树也就要拟合损失函数的负梯度。
这个思路是论文中的思路，可以查看Friedman的论文Greedy Function Approximation：A Gradient Boosing Machine
Xgboost
Xgboost的基本模型和GBDT还是很像的，区别在于，Xgboost在损失函数优化时，采用了牛顿法，也就是取了二阶的泰勒展开，包含了损失函数的二阶导数信息。同时还在损失函数中加入了正则项。
在建树的过程中，Xgboost只需要计算分裂前后损失函数的增益，选择最大的特征进行分裂。
另外，Xgboost的可并行，并不是说树的训练可以并行，而是说特征粒度的并行，也就是说不同特征分裂选择上可以选择并行。（这里其实我不是很明白，难道GBDT不可以并行？个人感觉这个应该只是实现上的一种优化吧）
总的来说，从参数空间到函数空间的变化对于理解GBDT和Xgboot来说是比较重要的，我认为也是想要深入理解这两种方法的正确途径。
Xgboost实现上的一些优化
Xgboost在实现上进行了很多优化，速度要比GBDT快不少。这里简单介绍一些，具体细节请看论文。
分裂点的选择
分裂点的选择一种方法是贪心法，每个值都尝试一次。Xgboost还采用了一种分位点分割的方法。分位点的确定是以每个数据点的二阶导数值为权重的，而不是简单地以个数分割。分裂点的选择可以在全局做一次，也可以在每次分裂时都做一次。
同时，Xgboost还能处理缺失值。对于缺失某些特征的样本，Xgboost会将它们都分到左节点或者右节点，然后观察哪个增益更大。
Column Block
Xgboost进行了特征预排序，并存储于内存中，这样可以在进行节点分裂时节省大量时间
Cache Aware Access
由于column block按特征大小排序存储，而相应的梯度信息是分散的，这回造成内存的不连续访问，降低cache命中率。为了优化，Xgboost会预读梯度数据到一个buffer中，将不连续的数据变得连续（这里其实我没太看懂，大概是这个意思）
红色方块为特征值，而黄色圆圈为对应的梯度信息。可以看到特征值对应的梯度信息是不连续的。
关于分类问题
上边说的好像都是用Xgboost或者GBDT来实现回归，那么分类问题如何解决呢？其实关键就在于损失函数的设计上。
对于GBDT而言，多分类（假设为K类）时，其实每一轮训练是训练了K棵树的，对某个样本x的预测值为\(f_1(x), f_2(x)...f_k(x)\)
这里我们使用softmax来产生概率，则x属于某个类别c的概率为
\[p_c = exp(f_c(x))/\sum_k^Kexp(f_k(x))\]此时该样本的loss即可以用log损失来表示，并对\(f_1\)~\(f_k\)都可以算出一个梯度，供下一轮迭代学习。
最终做预测时，输入的x会得到k个输出值，然后通过softmax获得其属于各类别的概率即可。
Xgboost的思路和这个应该是一样的，但是我没有看过源码，参考资料里知乎的那个回答中，答主说他看过源码，暂且可以这样认为。
参考资料
GBDT如何应用于二分类问题？具体如何使用logitloss？ - 晃荡青春的汪的回答 - 知乎
