机器学习算法中GBDT和XGBOOST_基于gbdt和xgboost的预测模型

如果从形式化的角度来观察，则可以描述如下：

其中F代表一个泛函，表征决策树的函数空间，K表示构成GBDT模型的Tree的个数，T表示一个决策树的叶子结点的数目, w是一个向量。
看到上面X/Y的建模方式，也许我们会有一个疑问：上面的建模方式输出的会是一个浮点标量，这种建模方式，对于Regression Problem拟合得很自然，但是对于classification问题，怎样将浮点标量与离散分类问题联系起来呢？
理解这个问题，实际上，可以通过Logistic Regression分类模型来获得启发。
我们知道，LR模型的建模形式，输出的也会是一个浮点数，这个浮点数又是怎样跟离散分类问题（分类面）联系起来的呢？实际上，从广义线性模型[13]的角度，待学习的分类面建模的实际上是Logit[3]，Logit本身是是由LR预测的浮点数结合建模目标满足Bernoulli分布来表征的，数学形式如下：

对上面这个式子做一下数学变换，能够得出下面的形式：

这样一来，我们实际上将模型的浮点预测值与离散分类问题建立起了联系。
相同的建模技巧套用到GBDT里，也就找到了树模型的浮点预测值与离散分类问题的联系：

考虑到GBDT应用于分类问题的建模更为tricky一些，所以后续关于loss function以及实现的讨论都会基于GBDT在分类问题上的展开，后续不再赘述。

2.2. Loss Function设计
分类问题的典型Loss建模方式是基于极大似然估计，具体到每个样本上，实际上就是典型的二项分布概率建模式[1]：

经典的极大似然估计是基于每个样本的概率连乘，这种形式不利于求解，所以，通常会通过取对数来将连乘变为连加，将指数变为乘法，所以会有下面的形式：

再考虑到loss function的数值含义是最优点对应于最小值点，所以，对似然估计取一下负数，即得到最终的loss形式，这也是经典的logistic loss[2]：

有了每个样本的Loss，样本全集上的Loss形式也就不难构造出来：


2.3. 求解算法
GBDT的求解算法，具体到每颗树来说，其实就是不断地寻找分割点(split point)，将样本集进行分割，初始情况下，所有样本都处于一个结点（即根结点），随着树的分裂过程的展开，样本会
分配到分裂开的子结点上。分割点的选择通过枚举训练样本集上的特征值来完成，分割点的选择依据则是减少Loss。
给定一组样本，实际上存在指数规模的分割方式，所以这是一个NP-Hard的问题，实际的求解算法也没有办法在多项式时间内完成求解，而是采用一种基于贪心原则的启发式方法来完成求解。 也就是说，在选取分割点的时候，只考虑当前树结构到下一步树结构的loss变化的最优值，不考虑树分裂的多个步骤之间的最优值，这是典型的greedy的策略。
在XGBoost的实现， 为了便于求解，对loss function基于Taylor Expansion进行了变换：


在变换完之后的形式里， 就是为了优化loss function，待更新优化的变量（这里的变量是一个广义的描述）。
上面的loss function是针对一个样本而言的，所以，对于样本全集来说，loss function的形式是：


对这个loss function进行优化的过程，实际上就是对第k个树结构进行分裂，找到启发式的最优树结构的过程。而每次分裂，对应于将属于一个叶结点（初始情况下只有一个叶结点，即根结点）下的训练样本分配到分裂出的两个新叶结点上，每个叶结点上的训练样本都会对应一个模型学出的概率值，而loss function本身满足样本之间的累加特性，所以，可以通过将分裂前的叶结点上样本的loss function和与分裂之后的两个新叶结点上的样本的loss function之和进行对比，从而找到可用的分裂特征以及特征分裂点。
而每个叶结点上都会附著一个weight，这个weight会用于对落在这个叶结点上的样本打分使用，所以叶结点weight的赋值，也会影响到loss function的变化。基于这种考虑，也许将loss function从样本维度转移到叶结点维度也许更为自然，于是就有了下面的形式：

上面的loss function，本质上是一个包含T(T对应于Tree当前的叶子结点的个数)个自变量的二次函数，这也是一个convex function，所以，可以通过求函数极值点的方式获得最优解析解（偏导数为0的点对应于极值点），其形如下：

现在，我们可以把求解过程串接梳理一下：

I. 对loss function进行二阶Taylor Expansion，展开以后的形式里，当前待学习的Tree是变量，需要进行优化求解。
II. Tree的优化过程，包括两个环节：
I). 枚举每个叶结点上的特征潜在的分裂点
II). 对每个潜在的分裂点，计算如果以这个分裂点对叶结点进行分割以后，分割前和分割后的loss function的变化情况。
因为Loss Function满足累积性(对MLE取log的好处)，并且每个叶结点对应的weight的求取是独立于其他叶结点的（只跟落在这个叶结点上的样本有关），所以，不同叶结点上的loss function满足单调累加性，只要保证每个叶结点上的样本累积loss function最小化，整体样本集的loss function也就最小化了。
而给定一个叶结点，可以通过求取解析解计算出这个叶结点上样本集的loss function最小值。

有了上面的两个环节，就可以找出基于当前树结构，最优的分裂点，完成Tree结构的优化。
这就是完整的求解思路。有了这个求解思路的介绍，我们就可以切入到具体实现细节了。
注意，实际的求解过程中，为了避免过拟合，会在Loss Function加入对叶结点weight以及叶结点个数的正则项，所以具体的优化细节会有微调，不过这已经不再影响问题的本质，所以此处不再展开介绍。

3.单机实现
有了2里对XGBoost算法原理的介绍，不难推敲出单机的实现细节。实际上，对XGBoost的源码进行走读分析之后，从其代码主流程可以看到，