今天想起好久都没更新过我的博客了，最近都在忙着笔试面试之类的，还要毕业设计。刚好今天告一段落了，索性整理一下前几天复习的Xgboost模型，发一篇博文。
树的集成
集成算法在机器学习中是一个很广泛，很重要的算法，一般分为Bagging和Boosting两种。决策树的集成自然是一个惯用手段。对于树的集成，Bagging方法的代表是随机森林(Random Forest)，它将属性和数据随机分组进行决策树学习，最后再统计结果；Boosting方法的代表是AdaBoost、GBDT(梯度提升决策树)。这几个算法都挺重要的，不是一两句话能概括得了的，所以就不展开讲了。而在树的Boosting中，陈天奇大佬提出了一个新模型Xgboost。这个模型利用了目标函数的二阶导，同时加入了正则化项预防模型过拟合。以下就是关于Xgboost模型的解读。
目标函数
集成树模型的结果是由许多单体树模型的结果来生成的。Xgboost选择的单体树模型就是CART。CART模型与其它决策树树模型有点不同，它叶子的值是一个确定的分数而非实际的类别，这有利于实现高效率的优化算法。利用一堆CART树来作预测，我们可以简单地将各个CART模型的结果相加。于是可得到如下函数：
\[ \hat{y}_i = \Phi(\mathbf{x}_i) = \sum_{k=1}^K f_k(\mathbf{x}_i), \ f_k \in F \tag{1} \]
其中给定的数据集有n条数据，m个特征。 \(D=\{(\mathbf{x}_i,y_i)\}(\vert{D}\vert=n,\mathbf{x}_i\in R^m,y_i\in R)\) 并且使用加性算法。
\(F=\{f(\mathbf{x})=w_{q(\mathbf{x})}\}(q:R^m\rightarrow T.\ w\in R^T)\) 是整个可能的CART树空间，\(f(x)\)为单个CART树模型。\(T\)为树的叶子节点数，\(q(x)\)将样本映射到1到T的某个值，即分到某个叶子节点，其实就是代表了棵树的结构， \(w_{q(x)}\)就是这棵树对样本的预测值了。
之后优化的目标函数可以定义为：
\[ L(\Phi) = \sum_i l(\hat{y}_i, y_i)+\sum_k \Omega(f_k) \tag{2} \]
其中\(L(\hat{y}_i,y_i)\)为损失函数，后一项为正则化项，表示了树的复杂度：
\[ \Omega(f) = \gamma T+\frac{1}{2}\lambda{\Vert{w}\Vert}^2 \tag{3} \]
通常损失函数选用均方误差(MSE)，这会得到一个非常漂亮的形式：
\[ L^{(t)} = \sum_{i=1}^n [2(\hat{y}^{(t-1)}_i-y_i)f_t(x_i)+{f_t(x_i)}^2]+\Omega(f_t)+const \]
对于其它损失函数（只要保证它二阶导存在），使用泰勒公式将\(L^{(t)}(y_i,\hat{y}^{(t-1)}_i+f_t(x_i))\)展开至二阶，其中令\(x=\hat{y}_i^{(t-1)}+f_t(x_i), \ x_0=\hat{y}_i^{(t-1)}\)，有：
\[ \begin{aligned} L^{(t)}(y_i,x) & \simeq l(y_i,x_0)+l^\prime(y_i,x_0)\cdot(x-x_0)+\frac{1}{2!}l^{\prime\prime}(y_i,x_0)\cdot{(x-x_0)}^2+\Omega(f)+const \\ & = l(y_i,x_0)+\frac{\partial l(y_i,x_0)}{\partial x_0}f_t(x_i)+\frac{1}{2}\frac{\partial^2 l(y_i,x_0)}{\partial^2 x_0}f_t^2(x_i)+\Omega(f)+const \end{aligned} \tag{4} \]
可令\(g_i = \frac{\partial l(y_i,x_0)}{\partial x_0}\),\(h_i = \frac{\partial^2 l(h_i, x_0)}{\partial^2 x_0}\)，同时忽略常数项，得下式：
\[ \tilde{L}^{(t)} = \sum_{i=1}^n[g_if_t(x_i)+\frac{1}{2}h_if_i^2(x_i)]+\Omega(f_t) \tag{5} \]
定义 \(I_j=\\{i\vert q(\mathbf{x}_i)=j\\}\) 为归类到叶子j上的训练样本序号的集合。结合式子(3)、(5)可得：
\[ \begin{aligned} \tilde{L}^{(t)} & = \sum_{i=1}^n[g_if_t(x_i)+\frac{1}{2}h_if_i^2(x_i)]+\gamma T+\frac{1}{2}\lambda \sum_{j=1}^T{w_j}^2 \\ & = \sum_{j=1}^T[(\sum_{i \in I_j}g_i)w_i+\frac{1}{2}(\sum_{i \in I_j}h_i+\lambda){w_j}^2]+\gamma T \end{aligned} \tag{6} \]
对于已确定的树结构\(q(x)\)，可以通过下式计算叶子节点j的最佳权重\(w\)：
\[ w_j^* = -\frac{\sum_{i \in I_j}g_i}{\sum_{i \in I_j}h_i+\lambda} \tag{7} \]
对应的损失为：
\[ \tilde{L}^{(t)}(q) = -\frac{1}{2}\sum_{j=1}^{T}\frac{(\sum_{i \in I_j}g_i)^2}{\sum_{i \in I_j}h_i+\lambda}+\gamma T \tag{8} \]
式(8)可用于评估树模型的好坏，其值越小越好。 该值仅用来衡量树结构的好坏，与叶子节点的值无关。 这从推导过程可以看出，\(\tilde{L}^{(t)}(q)\)只与\(g_i\)和\(h_i\)有关，而这两个值只和树的结构有关，与叶子节点的值毫无关系。
树的生成
显然，CART树有无数种结构，生成树后再评估结构好坏并不现实。这里有一种贪婪算法采用按层生成树。即从根节点开始，逐层分枝。假设\(I_L\)和\(I_R\)分别为分枝后左右节点包含的实例，且\(I = I_L \bigcup I_R\)，则是否分枝的衡量标准为：
\[ L_{split} = \frac{1}{2}\left[\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}\right]-\gamma \tag{9} \]
\(L_{split}\)的值为正且越大，则越有分枝的价值，因为分枝后的\(\tilde{L}^{(t)}(q)\)会变得越小。其实，\(\gamma\)为阈值，该值越大，则分枝的标准越严格。
注意： Xgboost不需要进行单独的剪枝操作，因为在生成树的时候，树模型的复杂度已经纳入考虑，对应的即是参数\(\gamma\)。
基于贪婪算法寻找最佳分点的算法模型如下：
贪婪算法寻找分点是一种十分有效的算法，但是对于无法一次性装入内存的大型数据集来说，这种方法便失效了。这时候就需要使用近似方法寻找分点。
近似方法实际上就是根据特征分布的百分位数，提出候选划分点。之后将连续型特征映射到候选点划分的分桶中，具体如下：
其中，Global为学习每棵树前给出候选分点；Local为每次分裂前给出候选分点
加权分量草图
在上述的近似算法分枝中，重要的一步就是候选点的选取。假设集合\(D_k=\\{(x_{1k},h_1),(x_{2k},h_2)\cdots(x_{nk},h_n)\\}\)表示第k个特征的值及其二阶导的统计。定义一个分值函数\(r_k: \ R \rightarrow [0,+\infty)\):
\[ r_k(z) = \frac{1}{\sum_{(x,h) \in D_k}h}\sum_{(x,h) \in D_k, x \lt z}h \tag{10} \]
这代表了样本中对应特征值小于z的实例所占比例。我们的目标是找到最佳分点\(\\{s_{k1},s_{k2},\cdots,s_{kl}\\}\)，可采用下式：
\[ \vert r_k(s_{k,j})-r_k(s_{k,j+1})\vert \lt \epsilon, \ s_{k1}=min_i x_{ik}, s_{kl}=max_i x_{ik} \tag{11} \]
这里\(\epsilon\)是一个逼近因素，可以认为有大约\(\frac{1}{\epsilon}\)个候选分点。这里每个数据都有权重\(h_i\)。
稀疏数据分点搜寻
这一部分主要是处理样本缺失值问题的。方法就是分别考虑将缺失值划分到左右分枝，选取增益最大的一侧，具体如下：
缓存访问模式
为了加快模型运算，可以采用缓存访问模式，具体如下： - 针对贪婪搜索分点算法：采用缓存感知预取算法减缓内存访问问题。即为每一线程申请一个内部缓存，里面存放梯度统计信息，并以小批量的方式执行累积。 - 针对近似方法搜寻分点算法：采用合适的块大小来减缓内存访问问题。块过小会导致每个线程工作量小，效率低；块过大会导致缓存未命中，通常设置为\(2^{16} \ examples \ per \ block\)。
Note
Xgboost防止过拟合的手段： - 添加正则化项，即目标函数中的\(\Omega(f)\) - Shinkage(缩减)，在完成一次迭代后，会将将叶子节点上的权重乘上该系数，主要是削减每棵树的影响，让后面有更大的学习空间 - Column subsampling(列抽样)，类似于随机森林，支持特征抽样，防止过拟合的同时降低运算量