XGB
XGB 同随机森林一样，通过构建一系列决策树（准确说应该是CART树）来组成最终的预测模型，由 $K$ 棵函数为 $f _ k(x _ i)$ 树组成的 XGB 模型可写成：
$$\hat y _ i = \sum _ {k=1}^K f _ k(x _ i), \quad f _ k \in \mathcal{F}$$
模型的目标函数为：
$$Obj(\Theta) = \sum _ i^n l(y _ i,\hat y _ i) +\sum _ {k=1}^K\Omega(f _ k)$$
这个目标函数的第一部分就是损失函数，第二部分就是正则项。
模型的训练
模型的每次迭代都将生成一棵CART树，则经过$t$次训练后模型的输出 $\hat{y}$ 改为
$$\hat{y}=\hat{y}^t=\hat{y}^{t-1}+f _ t(x _ i)$$
其中$f _ t(x _ i)$为第$t$次生成的树模型的输出。
为了使 $\hat{y}\rightarrow y^*$，每次迭代过后，目标函数将更新为
$$Obj(\Theta^t) = \sum _ i^n l(y _ i,\hat y^t _ i) +\sum _ {k=1}^K\Omega(f _ k)+const=\sum _ i^n l(y _ i,\hat y^{t-1} _ i+f _ t(x _ i)) +\sum _ {k=1}^K\Omega(f _ t)+const$$
每棵树都是一个学习残差的一个过程。每次迭代都将生成一颗树$f _ t(x _ i)$使目标函数最小。
使用泰勒级数展开
目标函数可简化为
模型正则化项
模型的正则化将防止树模型过于复杂而过拟合，以下将定义树的复杂程度。
首先把树拆分成结构部分q和叶子权重部分w。结构函数q把输入映射到叶子的索引号上面去，而w给定了每个索引号对应的叶子分数是什么。
$$f _ t(x)=w _ q(x),\ w\in\mathbf{R}^T,\ q:\mathbf{R}^d\rightarrow{1,2,\cdots T}$$
则树的复杂程度可定义如下：
$$\Omega(f _ t)=\gamma T + {1\over 2}\lambda\sum\limits _ {j=1}^T{w _ j^2}$$
下一步
我们可以把目标函数进行如下改写，其中I被定义为每个叶子上面样本集合 $I _ j = { i|q(x _ i)=j}$
定义
$$G _ j = \sum _ {i \in I _ j} g _ i \quad H _ j = \sum _ {i \in I _ j} h _ i$$
那么这个目标函数可以进一步改写成如下的形式，假设我们已经知道树的结构q，我们可以通过这个目标函数来求解出最好的w，以及最好的w对应的目标函数最大的增益
$$Obj^{(t)} = \sum _ {j=1}^T [( \sum _ {i \in I _ j} g _ i)w _ j+\frac 1 2(\sum _ {i \in I _ j} h _ i + \lambda)w _ j^2] + \gamma T = \sum _ {j=1}^T [G _ j w _ j + \frac 1 2 (H _ j + \lambda) w _ j^2] + \gamma T$$
这两个的结果对应如下，左边是最好的w，右边是这个w对应的目标函数的值。到这里大家可能会觉得这个推导略复杂。其实这里只涉及到了如何求一个一维二次函数的最小值的问题12。如果觉得没有理解不妨再仔细琢磨一下
$$w _ j^* = - \frac {G _ j} {H _ j + \lambda} \quad Obj = - \frac 1 2 \sum _ {j=1}^T \frac {G _ j^2} {H _ j + \lambda} + \gamma T$$
优点
xgboost相对于普通gbm的实现，可能具有以下的一些优势：
- 显式地将树模型的复杂度作为正则项加在优化目标
- 公式推导里用到了二阶导数信息，而普通的GBDT只用到一阶
- 允许使用列抽样来防止过拟合，借鉴了Random Forest的思想
- 实现了一种分裂节点寻找的近似算法，用于加速和减小内存消耗。
- 节点分裂算法能自动利用特征的稀疏性。
- data事先排好序并以block的形式存储，利于并行计算