目录
微信公众号：AIKaggle
欢迎建议和拍砖，若需要资源，请公众号留言;
如果你觉得AIKaggle对你有帮助，欢迎赞赏
本系列文章将会梳理Boosting算法的发展，从Boosting算法入手，介绍Adaboost，GBDT/GBRT算法，XGBoost算法，LightGBM算法，CATBoost算法，Thunder GBM算法等，介绍Boosting算法族的原理，框架，推导等，Boosting算法的前世今生（上篇）将介绍AdaBoost算法和梯度提升树算法，中篇（本文）将会详细介绍陈天奇教主提出的XGBoost算法，下篇将会介绍LightGBM算法，CATBoost算法，Thunder GBM算法等。XGBoost是在2014年由华盛顿大学的陈天奇（教主）提出的，对损失函数进行了二阶泰勒展开，在优化时用到了一阶导数和二阶导数，而且采用结构损失最小化的原则，在损失函数中引入了关于树模型复杂度的函数。如果对机器学习算法和实战案例感兴趣，也可关注公众号：AIKaggle获取算法动态
泰勒展开：\[f(x+\Delta x)\simeq f(x)+f'(x)\Delta x + \frac{1}{2} f''(x)\Delta x^2\]
定义：
\[g_i = \partial_{\hat y^{(t-1)}}l(y_i, \hat y^{(t-1)})\]
\[h_i = \partial^2_{\hat y^{(t-1)}}l(y_i, \hat y^{(t-1)})\]
那么目标函数可以写为(公式1)：
\[Obj^{(t)} \simeq \sum_{i=1}^{n}[l(y_i, \hat y_i^{(t-1)})+g_if_t(x_i)+\frac{1}{2}h_if^2_t(x_i)]+\Omega(f_t)+constant \]
利用泰勒展开目标函数后，可以清晰地看到，最终的目标函数只依赖于每个数据点在误差函数上的一阶导数和二阶导数。暂且把这个目标函数放在这里，我们接下来短暂地研究一下树结构，以便弄清楚正则项\(\Omega(f_t)\)的表达式。
\(x = (x_1, x_2, ..., x_n)\in X\subset R^n\)为数据点，\(f\)为树结构的映射，它将数据点映射为一个数：
\[f: X \rightarrow R\]
接下来定义树的复杂度。
对于\(f\)的定义做一下细化，把树拆分成结构部分\(q\)和叶子权重部分\(w\)。下图是一个具体的例子，我会从下图开始，详细讲讲如何将映射\(f\)转化为一个由\(w\)和\(q\)表示的映射。结构函数\(q\)把输入\(x\)映射到叶子的索引号上，而\(w\)给定了索引号对应的叶子结点的叶子分数。
举例说明一下，蓝色衣服的小男孩记为样本点\(x_1\)，由于\(q\)是将数据点映射为叶子索引点号的函数，所以\(q(x_1)\)为1（对应着Leaf 1），\(w\)将索引号映射为索引号对应的叶子结点分数，所以\(w(1) = +2\)，将这两步复合起来就是\(w(q(x)) = w(1) = 2\)。
定义这个复杂度还包含了一棵树里面结点的个数，以及每个叶子结点上面输出分数的\(L_2\)模平方。当然这不是唯一的一种定义方式，不过这一定义方式学习出的树效果一般都比较不错。下图还给出了复杂度计算的一个例子。
说明一下上图，这棵树包含3个叶子结点，所以复杂度\(\Omega(f_t)\)的第一项\(\gamma T = 3\gamma\)，第二项\(\frac{1}{2}\lambda\sum_{j=1}^{T}w_j^2 = \frac{1}{2} \lambda \times((+2)^2+(0.1)^2+(-1)^2) = \frac{1}{2}\lambda \times(4+0.01+1)\)
将弄清楚的正则项代入到之前的公式1中，我们可以改写目标函数，以便目标函数和树结构的联系更为紧密。
\[Obj^{(t)}\simeq \sum_{i=1}^{n}[g_if_t(x_i)+\frac12h_if_t^2(x_i)]+\Omega(f_t)\]
引入每个叶子上面的样本点集合\(I\)，比如上图的Leaf 3包含3个样本点，分别是穿围裙的妈妈，爷爷和奶奶，所以\(I_3\)就是包含3个样本点{穿围裙的妈妈，爷爷和奶奶}的集合。将样本点的求和指标换成叶子结点的求和指标：（此处也许需要较长时间理解，看不懂可以先跳过）
\[Obj^{(t)}= \sum_{j=1}^{T}[(\sum_{i\in I_j}g_i)w_j+\frac12(\sum_{i\in I_j}h_i+\lambda)w_j^2]+\gamma T\]
写成这一形式后，目标包含了\(T\)个相互独立的单变量二次函数，我们可以定义
\[G_j = \sum_{i \in I_j}g_i, H_j = \sum_{i \in I_j} h_i\]
（类似于梯度和Hessian)，最终公式可以化简为
\[Obj^{(t)} = \sum_{j=1}^{T} [(\sum_{i\in I_j}g_i)w_j+\frac12(\sum_{i\in I_j}h_i+\lambda)w_j^2]+\gamma T\]
\[Obj^{(t)} = \sum_{j=1}^{T} [G_jw_j+\frac12(H_j+\lambda)w_j^2]+\gamma T\]
\[w_j^* = -\frac{G_j}{H_j+\lambda}\]
\[Obj = -\frac12 \sum_{j=1}^{T}\frac{G_j^2}{H_j+\lambda}+\gamma T\]
下图描述了结构分数的计算方法：
计算好结构分数之后，我们就可以去构造XGBoost算法中的单棵树了，接下来只需要说清楚我们是怎么分裂结点生成单棵树的，这是通过贪心法实现的。
每一次尝试去对已有的叶子加入一个分割：
对于每次扩展，我们还是要枚举所有可能的分割方案，如何高效地枚举所有的分割呢？我假设我们要枚举所有\(x<a\)这样的条件，对于某一个特定的分割\(a\)，我们要计算\(a\)左边的导数和右边的导数和。
在构造树结构时，每一次尝试对已有的叶子结点加入一个分割，选择具有最佳增益的分割对结点进行分裂。对于一个具体的分割方案，我们可以获得的增益可以由如下公式计算：
\[Gain = Obj(I) - [Obj(I_L)+Obj(I_R)]\]
\[Gain = \frac12[\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\]
\[Gain = \frac12[\frac{G_L}{H_L+\lambda}+\frac{G_R}{H_R+\lambda} - \frac{G}{H+\lambda}]-\gamma\]
其中\(I\)代表该结点下的所有样本集合（分割前），设\(I_L\)代表左子树，\(I_R\)代表右子树，也就有\(I = I_L \cup I_R\)
我们可以发现对于所有的\(a\)，我们只要做一遍从左到右的扫描就可以枚举出所有分割的梯度和\(G_L\)和\(G_R\)。然后用上面的公式计算每个分割方案的分数就可以了。
观察这个目标函数，大家会发现第二个值得注意的事情就是引入分割不一定会使得情况变好，因为我们有一个引入新叶子的惩罚项。优化这个目标对应了树的剪枝， 当引入的分割带来的增益小于一个阀值的时候，我们可以剪掉这个分割。大家可以发现，当我们正式地推导目标的时候，像计算分数和剪枝这样的策略都会自然地出现，而不再是一种因为heuristic（启发式）而进行的操作了。
原文：https://www.cnblogs.com/AIKaggle/p/11543255.html
