一文掌握XGBoost核心原理

2019-04-09 本文已影响9人心智万花筒

XGBoost是经典的提升树学习框架，其配套论文和PPT分享也相当经典，本文简单梳理其思路，原文见XGBoost原理简介。

整体思路

和一般提升模型一样，提升树模型也遵循相同的范式

采用加法模型「forward stage-wise manner」
每轮引入一weak learner「此处是一棵CART树」
学习之前weak learners的不足「用梯度表征」

同时要考虑过拟合等问题「overfitting is everywhere」。

Tree Ensemble

遵循李航老师统计学习三要素公式

$方法=模型+策略+算法$

假设空间「模型」

Tree Ensemble基本思想是将多棵树的结果融合作为最终输出，示意图如下

paper-xgboost-tree-ensemble

不难看出，模型的假设空间是一系列CART树的集成，输出为

$\hat y_i = \sum_{k=1}^{K} f_k(x_i), \quad f_k \in F$

其模型参数为 $K$ 颗树

$\circleddash = \{f_1, f_2, \dots, f_K\}$

目标函数「策略」

模型假设有了，另一个核心元素就是目标函数，和一般监督模型一样

$Obj(\circleddash)=L(\circleddash)+\Omega(\circleddash)$

目标函数分两部分「Bias-variance tradeoff is everywhere」

Training Loss measures how well model fit on training data
Regularization measures complexity of model

具体到Tree Ensemble，其目标函数为

$Obj = \sum_{i=1}^{n} l(y_i, \hat y_i) + \sum_{k=1}^{K}\Omega(f_k)$

优化求解「算法」

模型参数的最终求解。参数 $\circleddash = \{f_1, f_2, \dots, f_K\}$ 为 $K$ 颗树，无法用SGD类似方法优化求解，因为不是 $R^d$ 空间上的数值向量。一般采用Additive Training(Boosting)的思想求解。

Gradient Boosting

Tree Ensemble章节回答了what we are learning的问题，Gradient Boosting章节要回答how do we learn的问题。

Additive Traing范式

采用Additive Training(Boosting)的模式，即每一轮学习一颗新树 $f_t$

paper-xgboost-boosting

学习一颗新树

问题是每一轮 $\hat y_i^{(t)} = \hat y_i^{(t-1)} + f_t(x_i)$ 中， $f_t$ 如何学习？

Define objective(loss, regularization) and optimize it.

在第 $t$ 轮，树的每一次生长，确定选那个特征分裂/分裂点取在哪里即可。其依据是使Objective最小，这里涉及两点，即 $w\in R^T$ 取何值Objective最小，以及Objective最小值表达式是什么。

定义Objective及其近似

Objective是 $w$ 的一般函数，其最小值一般表达式并不完全确定「not general」。XGBoost对其进行二阶泰勒展开近似，推导变换后Objective可形式化为 $T$ 个独立的二项式，表达式可统一「只需Objective一阶二阶可导即可」。

以下简单梳理推导核心步骤。

paper-xgboost-taylor-expansion

其中每次迭代 $f_t(x)$ 视为 $\Delta x$ 泰勒近似展开，用一阶二阶导表示。对应到Square Loss后理解会更直观一些，一阶导正比于残差，二阶导为常数。

经过简化，现在Objective为

$Obj^{(t)} = \sum_{i=1}^{n}[g_if_t(x_i) + \frac{1}{2}h_if^2_t(x_i)] + \Omega(f_t)$

此时学习只依赖loss function一阶二阶导，理论理解和工程实现都简洁不少。

The learning of function only depend on the objective via $g_i$ and $h_i$ .

确定Objective最小值

为方便推导，需要一些符号表示上的辅助

变换树的表达方式，见下文「如何表征一棵树」章节
$I_j$ 表示落在第 $j$ 个叶子节点所有样本集合
详细符号含义见下文「符号约定」章节
「正则项」考虑叶子节点数以及叶子分的L2范数，见下图

paper-xgboost-regularization

不难推导如下式子

$\begin{align} Obj^{(t)} &\approx \sum_{i=1}^{n} [g_if_t(x_i) + \frac{1}{2}h_if_t^2(x_i)] + \Omega(f_t) \\ &= \sum_{i=1}^{n} [g_iw_{q(x_i)} + \frac{1}{2}h_iw_{w_{q(x_i)}}^2] + \gamma T + \lambda\frac{1}{2}\sum_{j=1}^{T}w_j^2 \\ &= \sum_{j=1}^{T} [(\sum_{i\in I_j}g_j)w_j + \frac{1}{2}(\sum_{i\in I_j}h_j)w_j^2 + \lambda] + \gamma T \\ &= \sum_{j=1}^{T} [G_jw_j + \frac{1}{2}(H_j + \lambda)w_j^2] + \gamma T \end{align}$

对上述四个式子几点解释

式子1是经过泰勒展开近似的目标函数
式子2考虑树新表达方式，公式加入正则项
式子3将 $n$ 个样本，按划分的叶子节点重新group，整合train loss和regularization
式子4引入 $G_j$ 和 $H_j$ 简化表达
式子4是 $T$ 个独立的二项式

对二项式 $y = ax^2 + bx + c$ ，在 $x=-\frac{b}{2a}$ 取极值 $y=\frac{4ac-b^2}{4a}$ 。不难得出 $w^*$ 取值为

$w_j^* = -\frac{G_j}{H_j + \lambda}$

时，Obj有以下最小值

$Obj = -\frac{1}{2}\sum_{j=1}^{T} \frac{G_j^2}{H_j + \lambda} + \gamma T$

最小值中包含两项，第一项表示树拟合好坏，第二项表示树的复杂度。如此，即可根据gain选择分裂特征和分裂点了。

$Gain = \frac{1}{2}\big[\frac{G_L^2}{H_L+\lambda} + \frac{G_R^2}{H_R+\lambda} - \frac{(G_L+G_R)^2}{H_L + H_R + \lambda}\big] - \gamma$

一点验证

当模型为GBDT，Loss选为Square Loss，不加正则项，其结论应该跟上述推导完全一致。Square Loss

$l(y_i, \hat y_i^{(t-1)}) = \frac{1}{2}(y_i - \hat y_i^{(t-1)})^2$

求一阶导

$g_i = -(y_i - \hat y_i^{(t-1)})$

即其一阶导是负残差。求二阶导，其值为常数

$h_i = 1$

Square Loss情况下，取 $I_j$ 集合的均值「残差均值」作为该节点预测值「optimal weight」，应该跟 $w^*$ 保持一致。

$w_j^* = -\frac{G_j}{H_j + \lambda}$

不难看出

$\lambda=0$ 此处无正则
$H_j = \vert I_j\vert$ 为 $I_j$ 样本个数
$G_j$ 残差之和

综上，其optimal weight即为残差均值，其实是XGBoost里 $w_j^*$ 的特例。

如何表征一棵树

决策树可看做一系列If-Then规则的集合，但这样表示起来比较麻烦。为了方便公式的推导，XGBoost将其表示为一向量。

Think regression tree as a function that maps the attributes to the score. We define tree by a vector of scores in leafs, and a leaf index mapping function that maps an instance to a leaf.

即用长度为 $T$ 「叶子节点数」的向量 $w$ 和将样本实例映射到叶子索引的映射函数 $q(x)$ 表示。

paper-xgboost-tree

这样树的预测输出可直接用 $w$ 表示，跟正则项 $\vert w\vert ^2$ 保持一致，公式表示推导上比较方便。

如何防止过拟合

XGBoost中有很多防止过拟合手段，比如

正则化

每一轮树的目标函数Objective中可以包含正则项，是防止过拟合经典手段

$\Omega(f) = \gamma T + \frac{1}{2}\lambda||w||^2$

Shrinkage

每一轮树都不完全拟合残差或梯度，给后续学习器学习的空间

$y^{(t)} = y^{(t-1)} + \epsilon f_t(x_i)$

$\epsilon$ is called step-size or shrinkage, usually set around 0.1. This means we do not do full optimization in each step and reserve chance for future rounds, it helps prevent overfitting