【Method】Boosting（三）XGBoost
原理
(1) xgboost在目标函数中显示的加上了正则化项，基学习为CART时，正则化项与树的叶子节点的数量T和叶子节点的值有关。
\[L(\phi)=\sum_i l(\hat{y}_i, y_i) + \sum_k \Omega(f_k)\] \[where \Omega(f)=\gamma T + \frac{1}{2} \| w \|^2\](2) GB中使用Loss Function对f(x)的一阶导数计算出伪残差用于学习生成fm(x)，xgboost不仅使用到了一阶导数，还使用二阶导数。
第t次的loss：
\[L^{(t)} = \sum_{i=1}^n l(y_i, \hat{y}_i^{(t-1)} + f_t(x_i)) + \Omega(f_t)\]对上式做二阶泰勒展开：g为一阶导数，h为二阶导数
\[L^{(t)} \simeq \sum_{i=1}^n [l(y_i, \hat{y}^{(t-1)}) + g_i f_t(x_i)+\frac{1}{2}h_i f_i^2(x_i)] + \Omega(f_t)\]$$where g_i=\partial_{\hat{y}^{(t-1)}}l(y_i, \hat{y}^{(t-1)}) and h_i = \partial_{\hat{y}^{(t-1)}}^2 l(y_i, \hat{y}^{(t-1)})
(3) CART回归树中寻找最佳分割点的衡量标准是最小化均方差，xgboost寻找分割点的标准是最大化，lamda，gama与正则化项相关
\[L_{split} = \frac{1}{2}[\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\]xgboost算法的步骤和GBDT基本相同，都是首先初始化为一个常数，GBDT是根据一阶导数\(r_i\)，xgboost是根据一阶导数\(g_i\)和二阶导数\(h_i\)，迭代生成基学习器，相加更新学习器。
之所以XGBoost可以成为机器学习的大杀器，广泛用于数据科学竞赛和工业界，是因为它有许多优点：
- 使用许多策略去防止过拟合，如：正则化项、Shrinkage and Column Subsampling等。
- 目标函数优化利用了损失函数关于待求函数的二阶导数
- 支持并行化，这是XGBoost的闪光点，虽然树与树之间是串行关系，但是同层级节点可并行。具体的对于某个节点，节点内选择最佳分裂点，候选分裂点计算增益用多线程并行。训练速度快。
- 添加了对稀疏数据的处理。
- 交叉验证，early stop，当预测结果已经很好的时候可以提前停止建树，加快训练速度。
- 支持设置样本权重，该权重体现在一阶导数g和二阶导数h，通过调整权重可以去更加关注一些样本。